数据结构入门----链表的基本操作

一、实验目的 通过该实验，深入理解链表的逻辑结构、物理结构等概念，掌握链表基本操作的编程实现，熟练掌握C语言中指针的操作。和实验3对比，掌握线性结构两种不同存储方式的区别。 二、实验内容 编程实现链表的基本操作，最好用菜单形式对应各个操作，使其编程一个完整的小软件。注意，每个功能模块一定要考虑非法的情况，并作出相应的提示，例如：求前驱，要分别能够测试第一个元素的前驱、其他正常的元素的前驱、输入一个在表中不存在的元素求其前驱，这三种情况应给出相应的提示语和结果值。 三、主要源代码

#include "iostream" using namespace std; int checkStatus=0; typedef int Status; typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; static LinkList L; void selectFunc(int _select); void InitList(LinkList &L); void DestoryList(LinkList &L); void ListLength(LinkList &L); void GetData(LinkList &L); void LocateData(LinkList &L); void PriorData(LinkList &L); void NextData(LinkList &L); void ListInsert(LinkList &L); void ListDelete(LinkList &L); void Travel(LinkList &L); void InitList_Sq(LinkList &L); void ClearList(LinkList &L); void main() { cout<<"*********************************************************"<<endl; cout<<"*************** 1.初始化或重置链表 ***************"<<endl; cout<<"*************** 2.销毁链表 ***************"<<endl; cout<<"*************** 3.链表中数据元素个数 ***************"<<endl; cout<<"*************** 4.所指位序的元素值 ***************"<<endl; cout<<"*************** 5.链表已存在元素的位序 ***************"<<endl; cout<<"*************** 6.请输入元素，求直接前驱 ***************"<<endl; cout<<"*************** 7.请输入元素，求直接后继 ***************"<<endl; cout<<"*************** 8.在第i个位置插入元素 ***************"<<endl; cout<<"*************** 9.删除第i个元素 ***************"<<endl; cout<<"*************** 10.输出所输入的链表元素 ***************"<<endl; cout<<"*************** 11.初始化并输入链表元素 ***************"<<endl; cout<<"*************** 12.清空链表 ***************"<<endl; cout<<"*************** 13.退出 ***************"<<endl; cout<<"*********************************************************"<<endl; int _select; while(1) { cout<<"请输入功能前面的数字代号："; cin>>_select; if(!cin || _select==0 || _select>13) { cout<<"您输入的选项有误，请重新输入！"<<endl; cout<<endl; cin.clear(); cin.sync(); continue; } else { if(_select<0) { exit(1); } else { selectFunc(_select); } } cout<<endl; } system("pause"); } void selectFunc(int _select) { switch(_select) { case 1: { InitList(L); checkStatus=1; break; } case 2: { if(checkStatus==1) { DestoryList(L); } else { checkStatus=0; cout<<"尚未初始化链表，请先初始化!"<<endl; } break; } case 3: { if(checkStatus==1) { ListLength(L); } else { checkStatus=0; cout<<"尚未初始化链表，请先初始化!"<<endl; } break; } case 4: { if(checkStatus==1) { GetData(L); } else { checkStatus=0; cout<<"尚未初始化链表，请先初始化!"<<endl; } break; } case 5: { if(checkStatus==1) { LocateData(L); } else { checkStatus=0; cout<<"尚未初始化链表，请先初始化!"<<endl; } break; } case 6: { if(checkStatus==1) { PriorData(L); } else { checkStatus=0; cout<<"尚未初始化链表，请先初始化!"<<endl; } break; } case 7: { if(checkStatus==1) { NextData(L); } else { checkStatus=0; cout<<"尚未初始化链表，请先初始化!"<<endl; } break; } case 8: { if(checkStatus==1) { ListInsert(L); } else { checkStatus=0; cout<<"尚未初始化链表，请先初始化!"<<endl; } break; } case 9: { if(checkStatus==1) { ListDelete(L); } else { checkStatus=0; cout<<"尚未初始化链表，请先初始化!"<<endl; } break; } case 10: { if(checkStatus==1) { Travel(L); } else { checkStatus=0; cout<<"尚未初始化链表，请先初始化!"<<endl; } break; } case 11: { InitList_Sq(L); checkStatus=1; break; } case 12: { if(checkStatus==1) { ClearList(L); } else { checkStatus=0; cout<<"尚未初始化链表，请先初始化!"<<endl; } break; } case 13: { ClearList(L); DestoryList(L); exit(1); break; } default: { cout<<"输入不合法，请重新输入！"<<endl; break; } } } void InitList(LinkList &L) { L=(LinkList)malloc(sizeof(LNode)); if(!L) { cout<<"初始化失败！"<<endl; } else { L->data=NULL; L->next=NULL; cout<<"初始化链表成功！"<<endl; } } void DestoryList(LinkList &L) { LinkList p,q; p=L; q=L->next; while(p->next!=NULL) { free(p); p=q; q=q->next; } free(p); cout<<"销毁成功！"<<endl; } void ListLength(LinkList &L) { LinkList p; p=L; for(int n=0;p->next!=NULL;n++) { p=p->next; } cout<<"链表中数据元素有"<<n<<"个"<<endl; } void GetData(LinkList &L) { LinkList p,q; int e,i=1; cout<<"请输入要获取元素值的位置："; cin>>i; p=L; for(int n=0;p->next!=NULL;n++) { p=p->next; } if(i<1||i>n) { cout<<"输入的位置不合法！"<<endl; } else { q=L->next; int j=1; while(q&&j<i) { q=q->next; j++; } e=q->data; cout<<"第"<<i<<"个位置的元素值为："<<e<<endl; } } void LocateData(LinkList &L) { LinkList p; ElemType e; cout<<"请输入要获取位置的元素值："; cin>>e; p=L->next; int i=1; while(p&&p->data!=e) { p=p->next; i++; } if(!p) { cout<<"元素不存在链表中！"<<endl; } else { cout<<e<<"所在的位序是"<<i<<endl; } } void PriorData(LinkList &L) { LinkList p,q; ElemType e; cout<<"请输入要求取前驱的元素："; cin>>e; int j=0; p=L->next; if(p->data==e) { cout<<e<<"是链表中的第一个元素，没有前驱！"<<endl; j=1; } else { q=p->next; for(int i=1;p->next!=NULL;i++) { if(q->data==e) { cout<<e<<"的前驱为"<<p->data<<endl; j=1; } p=p->next; q=q->next; } if(j!=1) { cout<<"该元素不存在链表中，请重新输入！"<<endl; } } } void NextData(LinkList &L) { LinkList p,r,s; ElemType e; cout<<"请输入要求取后继的元素："; cin>>e; int j=0; p=L; for(int n=0;p->next!=NULL;n++) { p=p->next; } r=L->next; s=r->next; for(int i=1;r->next!=NULL;i++) { if(r->data==e) { cout<<e<<"的后继为"<<s->data<<endl; j=1; break; } r=s; s=s->next; } if(j==0) { cout<<"该元素没有后继！"<<endl; } } void ListInsert(LinkList &L) { int i,e; cout<<"请输入要插入元素的位置："; cin>>i; cout<<"请输入要插入元素的数值："; cin>>e; LinkList p,q; p=L; int j=0; while(p&&j<i-1) { p=p->next; ++j; } if(!p||j>i-1) { cout<<"输入的位置不合法！"<<endl; } else { q=(LinkList)malloc(sizeof(LNode)); q->data=e; q->next=p->next; p->next=q; cout<<"插入成功！"<<endl; } } void ListDelete(LinkList &L) { int i,e; cout<<"请输入要删除的位置："; cin>>i; LinkList p,q; p=L; int j=0; while(p->next!=0&&j<i-1) { p=p->next; j++; } if(!(p->next)||j>i-1) { cout<<"输入的位置不合法！"<<endl; } else { q=p->next; p->next=q->next; e=q->data; free(q); cout<<"删除的元素值为："<<e<<endl; } } void Travel(LinkList &L) { LinkList p; cout<<"建立的链表为："<<endl; for(p=L->next;p!=NULL;p=p->next) { cout<<p->data<<endl; } } void InitList_Sq(LinkList &L) { L=(LinkList) malloc(sizeof(LNode)); if(!L) { cout<<"初始化失败！"<<endl; } else { LinkList p,q; q=L; L->data=NULL; L->next=NULL; int n; cout<<"请输入链表元素的个数:"; cin>>n; cout<<"请输入链表元素值："; for(int i=1;i<=n;i++) { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; p->next=NULL;q->next=p; q=q->next; } cout<<"创建链表成功！"<<endl; } } void ClearList(LinkList &L) { LinkList p,q; if(L==NULL) { cout<<"链表为空！"<<endl; } p=L->next; while(p!=NULL) { q=p->next; free(p); p=q; } L->next=NULL; cout<<"清空链表成功！"<<endl; }

四、参考界面 增加了一个 清空链表。 注：销毁链表时需要循环释放每个结点所占用的空间。 注：求前驱是指，输入一个元素值（而不是位置），求该元素在顺序表中的直接前驱元素值。求后继是指：输入一个元素值（而不是位置），求该元素在顺序表中的直接后继元素值。