顺序表和链表的基本操作：C++ 代码实现

顺序表的基本操作/n/nc++/n#include <iostream.h>/n/n// 顺序表的定义/n#define MAX 15/ntypedef struct{/n int elem[MAX];/n int length;/n}Sqlist;/n/nvoid Initlist_sq(Sqlist &L);/nvoid ListInsert_sq(Sqlist &L,int i, int e);/nvoid ListDel_sq(Sqlist &L,int i, int &e);/nvoid print_sq(Sqlist L);/n/n// 函数的定义/nvoid Initlist_sq(Sqlist &L)/n{/n L.length =0;/n}/n/nvoid ListInsert_sq(Sqlist &L,int i, int e)/n{/n int *p,*q;/n if(i<1||i>L.length +1) return;/n q=&L.elem[i-1]; // 插入位置/n for(p=&L.elem[L.length -1];p>=q;--p )/n *(p+1)=*p;/n *q=e;/n ++L.length ;/n return;/n}/n/nvoid ListDel_sq(Sqlist &L,int i, int &e)/n{/n if(i<1||i>L.length ) return;/n e=L.elem[i-1]; /n for(int j=i;j<L.length ;j++)/n L.elem[j-1]=L.elem[j];/n --L.length ;/n}/n/nvoid print_sq(Sqlist L)/n{/n int *p,*q=L.elem+L.length-1 ;/n for(p=L.elem;p<=q;p++ )/n cout<<*p<<' ';/n cout<<'//n';/n}/n/nvoid main()/n{/n int a[11]={10,20,30,40,50,60,70,80,90,100};/n Sqlist L;/n // 初始化顺序表/n Initlist_sq(L);/n cout<<'现在的表长： '<<L.length <<endl;/n // 插入 10 个数据元素/n for( int i=1;i<=10;++i)/n ListInsert_sq(L, i, a[i-1]);/n cout<<'插入 10 个元素后的线性表：'<<endl;/n // 遍历/n print_sq( L);/n cout<<'现在的表长： '<<L.length <<endl;/n // 删除第 5 个元素/n int x;/n ListDel_sq(L,5, x);/n cout<<'删除的元素值是：'<<x<<endl;/n cout<<'删除第 5 个元素后的表：'<<endl;/n print_sq( L);/n cout<<'现在的表长： '<<L.length <<endl;/n}/n/n/n## 单链表的操作/n/nc++/n#include <iostream.h>/nstruct NODE/n{/n int data;/nNODE *next;/n} ;/n/nvoid print(NODE *&head); // 遍历/nint data[6]={25,41,17,98,5,6};/nvoid Setup_L(NODE *&head,int n); // 生成单链表/nvoid Insert_L(NODE *&head, int I, int e); // 插入/nvoid Delete_L(NODE * &head, int I,int &e); // 删除/nvoid Convert_L(NODE *&head)； // 逆序/n/nvoid main()/n {/n NODE *L;/n Setup_L(L,6);/n print(L);/n //Insert_L(L,7,50);/n print(L);/n int x;/n Delete_L(L,0,x);/n cout<<'X='<<x<<endl;/n print(L);/n Convert_L(L);/n print(L);/n }/n/nvoid print(NODE *&head)/n{/nNODE *p;/n p=head->next ;/n while(p)/n{/n cout<<p->data<<', ' ; // 输出元素值/n p=p->next; // 后移指针/n}/n cout<<endl; /n}/n/nvoid Setup_L(NODE * &head,int n)/n{/n NODE *q,*p;/n head=(NODE*)new NODE;/n head->next=NULL; // 先建立一个带头结点的单链表/n q=head; /n for(int i=0;i<n;i++){/n p=(NODE *)new NODE; // 生成新结点/n p->data=data[i];/n q->next=p; q=p; // 插入到表头/n}/n q->next =NULL;/n}/n/nvoid Insert_L(NODE *&L,int i, int e)/n{/n NODE *p=L,*q;/n int j=0;/n while(p&&j<i-1)/n {/n p=p->next ;/n j++;/n }/n if(!p||j>i-1)/n{/n cout<<'插入值超出范围！'<<endl;/n return;/n}/n q=(NODE*)new NODE;/n q->data=e;/n q->next =p->next ;/n p->next =q;/n}/n/nvoid Delete_L(NODE *&L,int i,int &e)/n{/nNODE *p=L,*q;/n int j=0;/n while(p&&j<i-1)/n {/n p=p->next ;/n j++;/n }/n if(!p||j>i-1)/n{/n cout<<'删除值超出范围！'<<endl;/n return;/n}/n q=p->next ;/n e=q->data ;/n p->next =q->next;/n delete q;/n}/n/nvoid Convert_L(NODE *&L)/n{/nNODE *p,*q,*r;/n p=L->next;/n q=p->next ;/n p->next =NULL;/n while(q)/n{/n r=q->next;/n q->next =p;/n L->next=q;/n p=q;/n q=r;/n}/n}/n/n/n## 双链表的基本操作/n/nc++/nstruct NODE/n{/n int data;/nNODE *next;/nNODE *prior;/n};/nint data[6]={3,5,7,19,20,21}; // 测试用数据/n/n// 函数声明/nvoid print(NODE *&head);/nvoid Setup_L(NODE*&head,int n);/nvoid Insert_L(NODE *&L,int i,int e);/nvoid Delete_L(NODE *&L,int i,int &e);/nvoid Convert_L(NODE*&L);/n/n// 主函数和各函数的定义/nvoid main()/n{/nNODE *L;/n Setup_L(L,6);/n print(L);/n Insert_L(L,7,50);/n print (L);/n int x;/n Delete_L(L,1,x);/n cout<<'X='<<x<<endl;/n print(L);/n}/n/nvoid print(NODE *&head)/n{/n // 从头开始顺序输出双连表中的数据/nNODE *p;/n p=head->next;/n while(p)/n{/n cout<<p->data<<',;/n p=p->next;/n}/n cout<<endl;/n}/n/nvoid Setup_L(NODE *&head,int n)/n{// 创建一个带头结点的双连表/nNODE *q,*p;/n head=(NODE*)new NODE;/n head->next=NULL;/n q=head;/n for(int i=0;i<n;i++){/n p=(NODE*)new NODE;/n p->data=data[i];/n //cin>>p->data;/n p->prior=q;q->next=p;q=p;/n}/n q->next=NULL;/n //return(head);/n}/n/nvoid Insert_L(NODE *&L,int i,int e)/n{// 在带头结点的双链表中第i个位置插入元素e/nNODE*p=L,*q;/n int j=0; //j为计数器/n while(p&&j<i-1) /n{/n p=p->next;/n j++;/n } // 寻找第i-1个结点/n if(!p||j>i-1) //i小于1或大于表长/n{/n cout<<'插入值超出范围!'<<endl;/n return;/n}/n q=(NODE*)new NODE; // 生成新结点/n q->data=e;/n if(p->next==NULL)/n{/n q->next=p->next;p->prior=q;p->next=q;/n}/n else /n{/n q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;/n } // 插入/n L中/n}/n/nvoid Delete_L(NODE*&L,int i,int &e)/n{// 在带头结点的双链表L中，删除第i个元素，并由e返回其值/nNODE *p=L,*q;/n int j=0;/n while(p&&j<i-1) // 寻找第i-1个结点/n{/n p=p->next;/n j++;/n}/n if(!p||j>i-1)/n{/n cout<<'删除值超出范围!'<<endl;// 删除位置不合理/n return;/n}/n q=p->next;/n e=q->data;/n q->next->prior=p;/n p->next=q->next;/n delete q;/n}// 删除并释放结点/n/n