本文主要是介绍设计一个静态链表（或称为数组链表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
设计一个静态链表（或称为数组链表），该链表储存的数据类型为string，请实现以下的功能。
public:
List(); //构造函数
List(int size); //含参构造函数-创建最大长度为size的静态链表
int Size() const; //返回链表的长度
bool IsFull() const; //返回链表是否已满
bool IsEmpty()const; //返回链表是否已空
void Clear(); //清空链表
int Retrieve( int position, string &x ) const; //获取链表第position位置的元素到x，成功返回0，否则返回-1
int Replace( int position, const string &x ); //将链表第position位置的元素换为x，成功返回0，否则返回-1
int Remove( int position, string &x ); //获取并删除链表第position位置的元素，成功返回0，否则返回-1
int Insert(int position, const string &x ); //将元素x插入到链表第position位置，成功返回0，否则返回-1
要求：
在实现要求的结构的基础上，需在main函数中编写下面所述的简单测试程序，请使用屏幕输入输出。
（1）按输入序列：Jan、Feb、Mar、Apr、May 建立初始链表。
（2）在Feb 之前，May 之后，先后插入Jun、Oct。
（3）先后删除Mar 和 Jan 。
（4）在Apr之前插入Dec。
在每一步执行后，输出链表状态。链表的状态请按照position：content：index输出。并输出当前链表。
注释：1. 第一个元素的Position的index为0；
2.插入元素操作Insert为在指定位置之前插入；
代码如下：
#include<iostream>
#include<string>
using namespace std;
typedef int index;
const int max_list=11;
class Node
{
public:
string entry;
index next;
};
class List
{
public:
List(); //构造函数
List(int size);//含参构造-创建最大长度为size的静态链表
int Size() ; //返回链表的长度
bool IsFull() const; //返回链表是否已满
bool IsEmpty() const; //返回链表是否已空
void Clear(); //清空链表
int Retrieve( int position, string &x ) ; //获取链表第position位置的元素到x，成功返回0，否则返回-1
int Replace( int position, const string &x ); //将链表第position位置的元素换为x，成功返回0，否则返回-1
int Remove( int position, string &x ); //获取并删除链表第position位置的元素，成功返回0，否则返回-1
int Insert( int position, const string &x ); //将元素x插入到链表第position位置，成功返回0，否则返回-1
void Print();
void PrintElement();
protected:
Node workspace[max_list];
index avaliable,last_used,head;
int count;
index new_node();
void delete_node(index n);
int current_position(index n)const;
index set_position(int position)const;
};
index List::new_node()
{
index new_index;
if(avaliable!=-1)
{
new_index=avaliable;
avaliable=workspace[avaliable].next;
}
else if(last_used<max_list-1)
{
new_index=++last_used;
}
else return -1;
workspace[new_index].next=-1;
return new_index;
}
void List::delete_node(index old_index)
{
index previous;
if (old_index == head) head = workspace[old_index].next;
else
{
previous = set_position(current_position(old_index) - 1);
workspace[previous].next = workspace[old_index].next;
}
workspace[old_index].next = avaliable;
avaliable = old_index;
}
int List::current_position(index n) const
{
index newindex=head;
int position=0;
for(;newindex!=-1;newindex=workspace[newindex].next)
{
if(newindex==n)
{
return position;
}
position++;
}
return -1;
}
index List::set_position(int position) const
{
index current=head;
if(position<0||position>count)
{
return -1;
}
for(int ix=0;ix!=position;ix++)
{
current=workspace[current].next;
}
return current;
}
List::List()
{
head=-1;
avaliable=-1;
last_used=-1;
count=0;
}
int List::Size()
{
index newindex=head;
index current;
while(workspace[newindex].next!=-1)
{
current=workspace[newindex].next;
workspace[newindex]=workspace[current];
count++;
}
return count;
}
bool List::IsFull()const
{
if(workspace[avaliable].next==-1&&last_used==max_list-1)
{
return true;
}
else
{
return false;
}
}
bool List::IsEmpty() const
{
if(workspace[head].next==-1)
{
return true;
}
else
{
return false;
}
}
void List::Clear()
{
workspace[0].next=-1;
int i = 1;
for (; i < max_list-1; i++)
{
workspace[i].entry="/0";
workspace[i].next=i+1;
}
workspace[i+1].entry="/0";
workspace[i+1].next=-1;
}
int List::Retrieve( int position, string &x )
{
if(position<0||position>count-1)
return -1;
else
{
index newindex=set_position(position);
x=workspace[newindex].entry;
return 0;
}
}
int List::Replace( int position, const string &x )
{
if(position<0||position>count)
return -1;
else
{
index newindex=set_position(position);
workspace[newindex].entry=x;
return 0;
}
}
int List::Remove( int position, string &x )
{ index following;index previous;
if(position<0||position>count-1)
return -1;
if(position>0)
{
previous=set_position(position-1); ///?????
following=workspace[workspace[previous].next].next;
}
x=workspace[previous].entry;
workspace[previous].entry="/0";
delete_node(previous);
workspace[previous].next=following;
count--;
return 0;
}
int List::Insert(int position,const string &x)
{
index new_index,previous,following;
if(position<0||position>count)
return -1;
if(position>0)
{
previous=set_position(position-1);
following=workspace[previous].next;
}
else following=head;
if((new_index=new_node())==-1)
return -1;
workspace[new_index].entry=x;
workspace[new_index].next=following;
if(position==0)
head=new_index;
else
workspace[previous].next=new_index;
count++;
return 0;
}
void List::Print()
{
for (int i = 0; i <count; i++)
{ cout<<i<<":" <<(workspace[i].entry =="/0" ?"N/A": workspace[i].entry )<<":"<<workspace[i].next<<" ";
if(i%3==2||i==count-1)
cout<<endl;
}
}
void List::PrintElement()
{
index newindex=head;
cout<<"当前链表为： ";
while(workspace[newindex].next!=-1)
{
cout<<workspace[newindex].entry<<" ";
newindex=workspace[newindex].next;
}
cout<<workspace[newindex].entry<<endl;
}
int main()
{
List lis;
cout<<"1)按输入序列：Jan、Feb、Mar、Apr、May 建立初始链表。"<<endl;
lis.Insert(0,"/0");
lis.Insert(1,"/0");
lis.Insert(2,"Jan");
lis.Insert(3,"Feb");
lis.Insert(4,"Mar");
lis.Insert(5,"Apr");
lis.Insert(6,"May");
cout<<endl;
lis.Print();
cout<<endl;
lis.PrintElement();
cout<<endl;
cout<<"2)在Feb之前，May之后先后插入Jun,Oct"<<endl;
lis.Insert(7,"Jun");
lis.Insert(8,"Oct");
cout<<endl;
lis.Print();
cout<<endl;
lis.PrintElement();
cout<<endl;
cout<<"3)先后删除Mar和Jan"<<endl;
string a,b;
lis.Remove(5,a);
lis.Remove(3,b);
//cout<<a<<endl; //输出要删的单词
cout<<endl;
lis.Print();
cout<<endl;
lis.PrintElement();
cout<<endl;
cout<<"4)在Apr之前插入Dec"<<endl;
lis.Insert(3,"Dec");
cout<<endl;
lis.Print();
cout<<endl;
lis.PrintElement();
cout<<endl;
return 0;
}
这篇关于设计一个静态链表（或称为数组链表）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
