链表的实现

#include <bits/stdc++.h> #define OK 1 #define ERROR 0 using namespace std; typedef int ElemType; typedef int Status; typedef struct LNode{ ElemType data; struct LNode *next; }Lnode,*LinkList; //初始化 Status InitList(LinkList &L){ L=(LinkList)malloc(sizeof(LNode)); if(!L){ exit(OVERFLOW);} L->next=NULL; return OK; } /*单链表的读取 读取链表的第i个位置的元素，由e返回其值 1. 声明一个结点 p 指向链表第一个结点，初始化 j 从 1 开始; 2. 当 j<i 时，就遍历链裴，让 p 的指针向后移动，不断指向下一结点， j 累加 1; 3. 若到链表末尾 p 为空，则说明第 i 个元素不存在; 4. 否则查找成功，返回结点 p 的数据。 */ Status GetElem(LinkList L,int i,ElemType &e){ LinkList p=L->next;//p指向首元结点 int j=1;//j用于计数 while(j<i&&p){ p=p->next; j++; } if(!p||j>i) return ERROR;//健壮性 e=p->data; return OK; } /*插入算法: L的第i个位置之前插入元素e 1. 声明一结点 p 指向链表头结点，初始化 j 从 0 开始; 2. 当 j<i-1 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点， j 累加 1; 3. 若到链表末尾 p为空，则说明第 i 元素不存在; 4. 否则查找成功，在系统中生成一个空结点 s; 5. 将数据元素 e 赋值给 s->data ; 6. 单链表的插入标准语旬 s->next=p->next；p->next=s; 7. 返回成功。 */ Status ListInsert(LinkList &L,int i,ElemType e){ LinkList p=L,s; int j=0; while(j<i-1&&p){ j++; p=p->next; } if(j>i-1||!p){ return ERROR; } s=(LinkList)malloc(sizeof(LNode));//建立一个新节点 s->data=e;//赋值 //插入过程 s->next=p->next; p->next=s; return OK; } /*删除算法 删除L的第i个元素，并由e返回其值 1. 声明一结点 p 指向链表第一个结点，初始化j从0开始 2. 当 j<i-1同时，就遍历链表,让p的指针向后移动，不断指向下一个结点，j累加1 3. 若到链表末尾 p为空，则说明第i个元素不存在; 4. 否则查找成功，将欲删除的结点 p->next 赋值给 q; S. 单链表的删除标准语句 p->next=q->next; 6. 将 q 结点中的数据赋值给 e， 作为返回; 7. 释放 q 结点; 8. 返回成功。*/ Status ListDelete(LinkList &L,int i,ElemType e){ LinkList p=L; int j=0; while(j<i-1&&p->next){ p=p->next; j++; } if(j>i-1||(!p->next)){ return ERROR; } LinkList q; q=p->next;p->next=q->next;//删除结点 e=q->data; free(q);//释放结点空间 return OK; } /*按值查找 按值查找是在链表中，查找是否有结点值等于给定值key的结点， 若有的话，则返回首次找到的其值为key的结点的存储位置； 否则返回NULL。*/ Status LinkSearch(LinkList L,ElemType key,LNode *e){ LinkList p=L; while(p->next&&p->next->data!=key){ p=p->next; } if(!p->next)return ERROR; e=p->next; return OK; } //前驱 Status LinkPiror(LinkList L,ElemType cur_e,ElemType &e){ LinkList p=L->next; while(p->next){//p有后继 if(p->next->data==cur_e){//p的后继 e=p->data; return OK; } p=p->next; } return ERROR; } //后继 Status LinkNext(LinkList L,ElemType cur_e,ElemType &e){ LinkList p=L->next; while(p->next){ if(p->data==cur_e){ e=p->next->data; return OK; } p=p->next; } return ERROR; } /*销毁 1. 声明一个节点q 2. 让q等于L的下一个地址 3. 释放L，循环，直到表为空*/ void DestroyList(LinkList &L){ LinkList q; while(L){ q=L->next; free(L); L=q; } } /*清空 让头结点指针域为空*/ void ClearList(LinkList L){ LinkList p=L->next; L->next=NULL; DestroyList(p); } //判空 void ListEmpty(LinkList L){ int k; if(L->next==NULL)k=1; else k=0; if(k==1) printf("表为空\n") ; else printf("表不为空\n"); } //求长(求元素个数) int ListLength(LinkList L){ int i=0; LinkList p=L->next; while(p){ i++; p=p->next; } return i; } /*创建链表(头插法) 1. 声明一结点 p 和计数器变量 i 2. 初始化一空链表 L 3. 让 L 的头结点的指针指向 NULL，即建立一个带头结点的单链表 4. 循环: 1生成一新结点赋值给 p; 2将待插入的数字赋值给p的数据域 p->data; 3将p插入到头结点与前一新结点之间。*/ void CreateListHead(LinkList &L,int n){ //建立带头结点的链表L，逆位序输入n个元素值 LinkList p; int i; InitList(L); for(i=0;i<n;i++){ p=(LinkList)malloc(sizeof(LNode));//建立新节点 cin>>p->data; p->next=L->next;L->next=p;//插表头 } } //创建链表(尾插法) void CreateListTail(LinkList &L,int n){ //建立带头结点的链表L，逆位序输入n个元素值 LinkList p,r; int i; InitList(L); r=L; for(i=0;i<n;i++){ p=(LinkList)malloc(sizeof(LNode));//建立新节点 cin>>p->data; r->next=p;//将表尾终端节点的指针指向新结点 r=r->next;// 将当前的新节点定义为农表位终端节点 } p->next=NULL;//表示当前列表结束 } //遍历 void show(LinkList L){ LinkList p=L->next; while(p!=NULL){ printf("%d ",p->data); p=p->next; } cout<<endl; } int main() { LinkList L; ElemType e,e0; int i,j,k; InitList (L);//初始化 cout<<"请输入待插入链表的5个数"<<endl; CreateListHead(L,5);//头插法 show(L); ListEmpty(L);//判空 printf("%d\n",ListLength(L));//求长度 ClearList(L);//清空 ListEmpty(L);//判空 printf("%d\n",ListLength(L));//求长度 DestroyList(L); cout<<"请输入待插入链表的5个数"<<endl; CreateListTail(L,5);//尾插法 show(L); ListInsert(L,2,9); show(L); ClearList(L);//清空 for(j=1;j<=10;j++){ ListInsert(L,1,j);//表尾插入 } show(L); //前驱，测试头两个元素 for(j=1;j<=2;j++){ GetElem(L,j,e0); i=LinkPiror(L,e0,e); if(i==ERROR)printf("元素%d无前驱\n",e0); else printf("元素%d的前驱为%d\n",e0,e); } //后继，测试后两个元素 for(j=ListLength(L)-1;j<=ListLength(L);j++){ GetElem(L,j,e0); i=LinkNext(L,e0,e); if(i==ERROR)printf("元素%d无后继\n",e0); else printf("元素%d的后继为%d\n",e0,e); } //删除 i=ListDelete(L,5,e); if(i==ERROR)printf("删除第5个元素失败\n"); else printf("删除第5个元素成功，其值为%d\n",e); i=ListDelete(L,12,e); if(i==ERROR)printf("删除第12个元素失败\n"); else printf("删除第12个元素成功，其值为%d\n",e); DestroyList(L);//销毁L printf("销毁L后，L=%u\n",L); return 0; }

结果：

请输入待插入链表的5个数 1 2 3 4 5 5 4 3 2 1 表不为空 5 表为空 0 请输入待插入链表的5个数 5 4 3 2 1 5 4 3 2 1 5 9 4 3 2 1 10 9 8 7 6 5 4 3 2 1 元素10无前驱 元素9的前驱为10 元素2的后继为1 元素1无后继 删除第5个元素成功，其值为1 删除第12个元素失败 销毁L后，L=0