链表实现（线性，链表）

待我称王封你为后i 2022-05-22 00:55 195阅读 0赞

//顺序线性表  
/\*\#include<iostream>  
using namespace std;  
\#define Virtuallength 100  
\#define AddspaceList 50  
\#define TRUE 1  
\#define ERROR 0

class List  
\{  
private:  
int \*item;  
int length;  
int MAXlength;  
public:  
int InitList(int n=Virtuallength)  
\{  
item=new int \[n\];  
if(item==NULL) return ERROR;  
length=0;  
MAXlength=n>Virtuallength?n:Virtuallength;  
return TRUE;  
\}  
void DestroyList() //删除  
\{  
if(item)  
delete \[\] item;  
\}  
void output() //输出线性表  
\{  
if(length==0)  
\{  
cout<<"The List is null "<<endl;  
return ;  
\}  
cout<<"The length of the List is "<<length<<endl;  
cout<<"The content of the the List is ";  
for(int i=0;i<length;i++)  
cout<<item\[i\]<<" ";  
cout<<endl;  
\}  
int Getlength() //计算线性表的长度  
\{  
return length;  
\}  
int IsEmpty() //判断是否为空  
\{  
if(length==0)  
\{  
return ERROR;  
\}  
else  
\{  
return TRUE;  
\}  
\}  
int ListInser(int i,int e) //在第i个数前面插入元素e  
\{  
if(length==MAXlength)  
\{  
return ERROR;  
\}  
if((i<1)||(i>length+1))  
\{  
return ERROR;  
\}  
for(int j=length-1;j>=i-1;j--)  
item\[j+1\]=item\[j\]; //数组还是从0开始  
item\[i-1\]=e;  
length++;  
return 0;  
\}  
int ListDelete(int i,int &e) //删除第i个元素  
\{  
if(!IsEmpty())  
\{  
return ERROR;  
\}  
if((i<1)||(i>length))  
\{  
return ERROR;  
\}  
e=item\[i-1\];//因为这里是把item\[i-1\]给删除了，是把前面一个数字删除，所以i>0才满足  
for(int j=i-1;j<length-1;j++)  
item\[j\]=item\[j+1\];//for(int j=i;j<=length-1;j++)item\[j-1\]=item\[j\];  
length--;  
return TRUE;  
\}  
int addspace() //增加线性表的空间，扩大存储  
\{  
cout<<"每一次调用扩大空间的函数所增加的空间为:"<<AddspaceList<<endl;  
if(length>MAXlength)  
\{  
item=(int \*)realloc(item,AddspaceList+MAXlength);//使用了动态分配空间的函数  
\}  
if(item==NULL)return ERROR;  
MAXlength=MAXlength+AddspaceList;

return TRUE;  
\}  
int judgespace()  
\{  
double s;  
cout<<"最大长度为:"<<MAXlength<<endl;  
cout<<"实际长度为:"<<length<<endl;  
s=length\*1.0/MAXlength\*100;  
cout<<"实际长度占最大长度的:"<<s<<'%'<<endl;  
return TRUE;  
\}  
\};  
int main()  
\{  
List list;  
int i,s;  
list.InitList(500);  
list.output();  
list.DestroyList();  
list.InitList(100);  
list.output();  
for(i=0;i<10;i++) //因为实在线性表中数据的前面插入的  
list.ListInser(list.Getlength()+1,i);  
list.output();  
for(i=2;i<=list.Getlength()+1;i++)//0 2 4 6 8 9  
list.ListDelete(i,s);  
list.output();  
list.addspace();  
list.judgespace();  
return 0;  
\}\*/  
/\*\#include<iostream>  
using namespace std;  
\#define Virtuallength 100  
\#define AddspaceList 50  
\#define TRUE 1  
\#define ERROR 0

class List  
\{  
private:  
int \*item;  
int length;  
int MAXlength;  
public:  
int InitList(int n=Virtuallength)  
\{  
item=new int \[n\];  
if(item==NULL) return ERROR;  
length=0;  
MAXlength=n>Virtuallength?n:Virtuallength;  
return TRUE;  
\}  
void DestroyList() //删除  
\{  
if(item)  
delete \[\] item;  
\}  
void output() //输出线性表  
\{  
if(length==0)  
\{  
cout<<"The List is null "<<endl;  
return ;  
\}  
cout<<"The length of the List is "<<length<<endl;  
cout<<"The content of the the List is ";  
for(int i=0;i<length;i++)  
cout<<item\[i\]<<" ";  
cout<<endl;  
\}  
int Getlength() //计算线性表的长度  
\{  
return length;  
\}  
int IsEmpty() //判断是否为空  
\{  
if(length==0)  
\{  
return ERROR;  
\}  
else  
\{  
return TRUE;  
\}  
\}  
int ListInser(int i,int e) //在第i个数前面插入元素e  
\{  
if(length==MAXlength)  
\{  
return ERROR;  
\}  
if((i<1)||(i>length+1))  
\{  
return ERROR;  
\}  
for(int j=length-1;j>=i-1;j--)  
item\[j+1\]=item\[j\]; //数组还是从0开始  
item\[i-1\]=e;  
length++;  
return 0;  
\}  
int ListDelete(int i,int &e) //删除第i个元素  
\{  
if(!IsEmpty())  
\{  
return ERROR;  
\}  
if((i<1)||(i>length))  
\{  
return ERROR;  
\}  
e=item\[i-1\];//因为这里是把item\[i-1\]给删除了，是把前面一个数字删除，所以i>0才满足  
for(int j=i-1;j<length-1;j++)//注意要删除最后一个数，所以要减1  
item\[j\]=item\[j+1\];  
length--;  
return TRUE;  
\}  
int addspace() //增加线性表的空间，扩大存储  
\{  
cout<<"每一次调用扩大空间的函数所增加的空间为:"<<AddspaceList<<endl;  
if(length>MAXlength)  
\{  
item=(int \*)realloc(item,AddspaceList+MAXlength);//使用了动态分配空间的函数  
\}  
if(item==NULL)return ERROR;  
MAXlength=MAXlength+AddspaceList;

return TRUE;  
\}  
int judgespace()  
\{  
double s;  
cout<<"最大长度为:"<<MAXlength<<endl;  
cout<<"实际长度为:"<<length<<endl;  
s=length\*1.0/MAXlength\*100;  
cout<<"实际长度占最大长度的:"<<s<<'%'<<endl;  
return TRUE;  
\}  
\};  
int main()  
\{  
List list;  
int i,s;  
list.InitList(500);  
list.output();  
list.DestroyList();  
list.InitList(100);  
list.output();  
for(i=0;i<10;i++) //因为实在线性表中数据的前面插入的  
list.ListInser(list.Getlength()+1,i);  
list.output();  
for(i=2;i<=list.Getlength();i++)//删除最后一个数，所以要=  
list.ListDelete(i,s);//0 2 4 6 8 9  
list.output();  
list.addspace();  
list.judgespace();  
return 0;  
\}\*/

//线性表的链式存储  
/\*\#include<iostream>  
\#define TRUE 1 //执行完成的返回值  
\#define ERROR 0 //执行异常的返回值  
using namespace std;

struct A  
\{  
int data;  
A \*next;  
\};

class Linklist  
\{  
private:  
A \*head;  
int length;  
public:  
int Initlist() //初始化私有数据  
\{  
head=new A; //指向头结点  
if(head==NULL)return ERROR;//检验是否开辟成功  
head->next=NULL;  
length=0;  
return TRUE;  
\}  
void Destorylist() //销毁，对于每一个节点的删除  
\{  
int i;  
A \*temp;  
for(i=0;i<length+1;i++)//因为要销毁所有数据，则必须改变头指针的指向  
\{//为0是因为把头结点算了进去  
temp=head;//必须用temp保存head的指向  
head=head->next;  
delete temp;  
\}  
\}  
void output() //链表的输出  
\{  
if(length==0)  
\{  
cout<<"当前链表为空"<<endl;  
return;  
\}  
cout<<"当前链表长度为:"<<length<<endl;  
cout<<"链表的内容为:";  
A \*temp=head->next;  
for(int i=0;i<length;i++) //从第一个节点开始  
\{  
cout<<temp->data<<" ";  
temp=temp->next;  
\}  
cout<<endl;  
\}  
int Listlength() //测长度  
\{  
return length;  
\}  
int Insert(int s,int n) //插入数据，s表示在第s个前面插入，n表示插入的数据  
\{  
if(s<1||s>length+1) return ERROR;//判断插入数据是否超出了长度  
A \*t=new A;//开辟一个结构t存数据n  
if(t==NULL)return ERROR;  
t->data=n;  
A \*p=head;//不能让它只想head-next，因为有可能在第一个数据的前面插入,  
int i;  
for(i=0;i<s-1;i++)//当链表中没有数据，则不执行循环  
p=p->next;  
t->next=p->next;  
p->next=t;  
length++;  
return TRUE;  
\}  
int Listdelete(int s,int n)//删除第s个数据，并把数据保存在n中  
\{  
if(length==0)\{cout<<"当前链表为空，不能删除!"<<endl;return ERROR;\}  
if(s<1||s>length)return ERROR;  
A \*p=head;  
int i;  
for(i=0;i<s-1;i++)  
p=p->next;//p指向要删除数据的前一个  
A \*t=p->next;//t指向要删除的数据  
n=t->data;  
p->next=p->next->next;  
delete t;  
length--;  
return n;  
\}  
\};  
int main()  
\{  
Linklist a;  
a.Initlist();  
a.output();  
for(int i=1;i<=10;i++) //i从0开始时，则输出偶数时则要注意前面要连续删除两个0和1  
a.Insert(a.Listlength()+1,i);  
a.output();  
int s;  
cout<<"删除的数据为:";  
for(i=1;i<a.Listlength()+1;i++)  
\{  
s=a.Listdelete(i,s);  
cout<<s<<" ";  
\}  
cout<<endl;  
a.output();  
return 0;  
\}\*/

//两个非递减集合的合并  
/\*\#include<iostream>  
using namespace std;  
\#define Virtuallength 100  
\#define AddspaceList 50  
\#define TRUE 1  
\#define ERROR 0

void DestroyList() //删除  
\{  
if(item)  
delete \[\] item;  
\}

void output() //输出线性表  
\{  
if(length==0)  
\{  
cout<<"The List is null "<<endl;  
return ;  
\}  
cout<<"The length of the List is "<<length<<endl;  
cout<<"The content of the the List is ";  
for(int i=0;i<length;i++)  
cout<<item\[i\]<<" ";  
cout<<endl;  
\}

int Getlength() //计算线性表的长度  
\{  
return length;  
\}

int IsEmpty() //判断是否为空  
\{  
if(length==0)  
\{  
return ERROR;  
\}  
else  
\{  
return TRUE;  
\}  
\}

int ListInser(int i,int e) //???在第i个数前面插入元素e  
\{  
if(length==MAXlength)  
\{  
return ERROR;  
\}  
if((i<1)||(i>length+1))  
\{  
return ERROR;  
\}  
if(length+1>MAXlength)  
\{  
addspace();  
judgespace();  
\}  
for(int j=length-1;j>=i-1;j--)//当length=0的时候，根本就没有执行该语句，且i必须=1才满足条件  
item\[j+1\]=item\[j\];  
item\[i-1\]=e;  
length++;  
return 0;  
\}

int ListDelete(int i,int &e) //删除第i个元素  
\{  
if(!IsEmpty())  
\{  
return ERROR;  
\}  
if((i<1)||(i>=length))  
\{  
return ERROR;  
\}  
e=item\[i-1\];//因为这里是把item\[i-1\]给删除了，是把前面一个数字删除，所以i>0才满足  
for(int j=i-1;j<length;j++)  
item\[j-1\]=item\[j\];  
length--;  
return TRUE;  
\}

int addspace() //增加线性表的空间，扩大存储  
\{  
cout<<"每一次调用扩大空间的函数所增加的空间为:"<<AddspaceList<<endl;  
item=(int \*)realloc(item,AddspaceList+MAXlength);//使用了动态分配空间的函数  
if(item==NULL)return ERROR;  
MAXlength=MAXlength+AddspaceList;  
return TRUE;  
\}

//int addspace() //增加线性表的空间，扩大存储  
//\{  
// cout<<"每一次调用扩大空间的函数所增加的空间为:"<<AddspaceList<<endl;  
// if(length>MAXlength)  
// \{  
// item=(int \*)realloc(item,AddspaceList+MAXlength);//使用了动态分配空间的函数  
// \}  
// if(item==NULL)return ERROR;  
// MAXlength=MAXlength+AddspaceList;  
// return TRUE;  
//\}

int judgespace()  
\{  
double s;  
cout<<"最大长度为:"<<MAXlength<<endl;  
cout<<"实际长度为:"<<length<<endl;  
s=length\*1.0/MAXlength\*100;  
cout<<"实际长度占最大长度的:"<<s<<'%'<<endl;  
return TRUE;  
\}  
friend int together(List la,List lb,List &lc);  
\};

int together(List la,List lb,List &lc)  
\{  
lc.InitList(la.Getlength()+lb.Getlength());//分配空间  
int \*pa,\*pb,\*p1,\*p2,\*p3;  
pa=la.item+la.length-1;  
pb=lb.item+lb.length-1;  
p1=la.item; //必须把a，b，c三个链表的初始链表先存放起来  
p2=lb.item;  
p3=lc.item;  
while((p1<=pa)&&(p2<=pb)) //必须要考虑相同的情况  
\{

if(\*p1<\*p2)  
\{  
\*p3=\*p1;  
p3++;  
p1++;  
\}  
else  
if(\*p1>\*p2)  
\{  
\*p3=\*p2;  
p3++;  
p2++;  
\}  
else  
\{  
\*p3=\*p2;  
p3++;  
p2++;  
p1++;  
\}  
lc.length++; //lc的长度还没有赋初值,必须要把lc的长度每个都加1  
\}  
while(p1<=pa)  
\{  
\*p3=\*p1;  
p3++;  
p1++;  
lc.length++;  
\}  
while(p2<=pb)  
\{  
\*p3=\*p2;  
p3++;  
p2++;  
lc.length++;  
\}  
return 0;  
\}

int main()  
\{  
List a,b,c;int i;  
a.InitList(100);//初始化数组并分配空间  
b.InitList(100);  
for(i=0;i<5;i++)  
\{  
a.ListInser(a.Getlength()+1,i);  
b.ListInser(b.Getlength()+1,i\*i);  
\}  
together(a,b,c);  
a.output();  
a.judgespace();  
b.output();  
b.judgespace();  
c.output();  
c.judgespace();  
c.addspace();  
cout<<"对c扩大空间后的空间计算:"<<endl;  
c.judgespace();  
return 0;  
\}\*/