数据结构之链表基础

实验4、链表的基本操作 （4学时） （1）实验目的 通过该实验，深入理解链表的逻辑结构、物理结构等概念，掌握链表基本操作的编程实现，熟练掌握C语言中指针的操作。和实验3对比，掌握线性结构两种不同存储方式的区别。 （2）实验内容 编程实现链表下教材第二章定义的线性表的基本操作，最好用菜单形式对应各个操作，使其编程一个完整的小软件。注意，每个功能模块一定要考虑非法的情况，并作出相应的提示，例如：求前驱，要分别能够测试第一个元素的前驱、其他正常的元素的前驱、输入一个在表中不存在的元素求其前驱，这三种情况应给出相应的提示语和结果值。 （3）参考界面 注意：增加一个 13.清空链表。 要求：所有的提示语不允许出现在自己定义的函数中，只能在main函数中出现提示语。 注：销毁链表时需要循环释放每个结点所占用的空间。 注：求前驱是指，输入一个元素值（而不是位置），求该元素在顺序表中的直接前驱元素值。求后继是指：输入一个元素值（而不是位置），求该元素在顺序表中的直接后继元素值。 （4）验收/测试用例

#include<stdio.h> #include<stdlib.h> #define LIST_INIT 100 #define LISTINCREMENT 10 #define ERROR 0 #define OK 1 #define OVERFLOW 0 typedef int status ; typedef int ElemType; typedef struct Lnode{ ElemType data; struct Lnode *next; }LNode,*LinkList; status judgement(LinkList P);//判断是否链表存在 void menu(); status intlist(LinkList &); //初始化链表 status destroylist(LinkList &); //销毁链表 status clearlist(LinkList &); //清空链表 status emptylist (LinkList ); //判断是否为空 status lengthlist(LinkList ); //求链表长度 status getlist(LinkList ,int ,ElemType &); //获取指定位置的元素 status getelemlist(LinkList,int,ElemType &); //获取元素所在位置 status prrorlist(LinkList,ElemType,ElemType &); //求前驱 status nextlist(LinkList,ElemType,ElemType &); //求后继 status insertlist(LinkList &,ElemType,int); //指定位置插入元素 status deleteelemlist(LinkList &,int); //删除指定位置元素 void viewlist(LinkList P); //输出链表 int main() { LinkList L; L=NULL; int select,m,n; while(1) { menu(); printf("\n请输入你的选择是:\n"); scanf("%d",&select); if(select<=0||select>14) printf("输入不合法，请重试。\n"); else switch(select) { case 1: if(intlist(L)) printf("初始化成功。\n"); else printf("初始化失败。\n"); break; case 2: if(judgement(L)) { if(L->next!=NULL) { if(destroylist(L)) printf("销毁成功。\n"); else printf("销毁失败。\n"); break; } printf("此为空链表。"); break; } printf("未初始化链表。"); break; case 3: if(judgement(L)) { if(L->next!=NULL) { if(clearlist(L)) printf("清空完成。\n"); break; } printf("此为空链表。"); break; } printf("未初始化链表。"); break; case 4: if(judgement(L)) { if(emptylist(L)) printf("链表不为空。\n"); else printf("链表为空。"); break; } printf("未初始化链表。"); break; case 5: if(judgement(L)) { if(emptylist(L)) { printf("链表长度为%d",lengthlist(L)); break; } printf("链表为空。"); break; } printf("未初始化链表。"); break; case 6: if(judgement(L)) { if(emptylist(L)) { printf("请输入你想获取元素的位置："); scanf("%d",&m); if(m<=0||m>lengthlist(L)) { printf("超出长度范围！"); break; } getlist(L,m,n); printf("元素为%d",n); break; } printf("链表为空。"); break; } printf("未初始化链表。"); break; case 7: if(judgement(L)) { if(emptylist(L)) { printf("请输入你想获取位置的元素："); scanf("%d",&m); if(getelemlist(L,m,n)) { printf("位置为%d",n); break; } printf("链表无此元素。"); break; } printf("链表为空。"); break; } printf("未初始化链表。"); break; case 8: if(judgement(L)) { if(emptylist(L)) { printf("请输入你想求前驱的元素："); scanf("%d",&m); if(getelemlist(L,m,n)) { if(prrorlist(L,m,n)) { printf("元素为%d",n); break; } printf("此为第一位元素，无前驱。"); break; } printf("链表无此元素。"); break; } printf("链表为空。"); break; } printf("未初始化链表。"); break; case 9: if(judgement(L)) { if(emptylist(L)) { printf("请输入你想求后继的元素："); scanf("%d",&m); if(getelemlist(L,m,n)) { if(nextlist(L,m,n)) { printf("元素为%d",n); break; } printf("此为最后一位元素，无后继。"); break; } printf("链表无此元素。"); break; } printf("链表为空。"); break; } printf("未初始化链表。"); break; case 10: if(judgement(L)) { printf("请输入你想插入的元素和位置："); scanf("%d %d",&m,&n); if(n<0||n>lengthlist(L)+1) { printf("插入超出长度。"); break; } else { if(insertlist(L,m,n)) { printf("插入完成！"); break; } } } printf("未初始化链表"); break; case 11: if(judgement(L)) { printf("请输入你想删除的位置："); scanf("%d",&m); if(m<=0||m>lengthlist(L)) { printf("删除超出长度。"); break; } else { if(deleteelemlist(L,m)) { printf("删除完成！"); break; } } } printf("未初始化链表"); break; case 12: if(judgement(L)) { viewlist(L); break; } printf("未初始化链表"); break; case 13: return 0; } } return 0; } status judgement(LinkList P) { if(P) return OK; else return ERROR; } void menu() { printf("\n"); printf("1-----初始化一个链表\n"); printf("2-----销毁链表\n"); printf("3-----清空链表\n"); printf("4-----判断链表是否为空\n"); printf("5-----求链表长度\n"); printf("6-----获取链表中指定位置元素\n"); printf("7-----获取链表元素的位置\n"); printf("8-----求前驱\n"); printf("9-----求后继\n"); printf("10-----链表指定位置插入元素\n"); printf("11-----删除链表指定位置元素\n"); printf("12-----显示链表\n"); printf("13-----退出\n"); } status intlist(LinkList &P) //1初始化 { P=(LNode*)malloc(sizeof(LNode)); if(!P) exit(OVERFLOW); P->next=NULL; return OK; } status destroylist(LinkList &P) //2销毁 { LinkList L,M; L=P; while(L) { M=L->next; free(L); L=M; } P=NULL; return OK; } status clearlist(LinkList &P) //3重置链表 { LinkList L,M; L=P->next; while(L) { M=L->next; free(L); L=M; } P=NULL; return OK; } status emptylist(LinkList P) //判读是否为空 { if(P->next) return OK; else return ERROR; } status lengthlist(LinkList P) //求链表长度 { int i; LinkList L=P->next; for(i=0;L!=NULL;i++) { L=L->next; } return i; } status getlist(LinkList P,int m,ElemType &n) //获取指定所在位置的元素 { int i=1; LinkList L=P->next; for(i=1;i<m;i++) { L=L->next; } n=L->data; return OK; } status getelemlist(LinkList P,ElemType m,int &n)//获取元素所在位置 { int i=1; LinkList L=P->next; while(L) { if(L->data==m) { n=i; return OK; } else { L=L->next; i+=1; } } return ERROR; } status prrorlist(LinkList P,ElemType m,ElemType &n) //求前驱 { int j=0,a=0; getelemlist(P,m,a); if(a==1) return ERROR; else{ getlist(P,a-1,j); n=j; return OK; } } status nextlist(LinkList P,ElemType m,ElemType &n) //求后继 { getelemlist(P,m,n); if(n==lengthlist(P)) return ERROR; getlist(P,n+1,m); n=m; return OK; } status insertlist(LinkList &P,ElemType m,int n) //指定位置插入元素 { int i; LinkList L=P; LinkList M; intlist(M); M->data=m; for(i=1;i<n;i++) { L=L->next; } M->next=L->next; L->next=M; return OK; } status deleteelemlist(LinkList &P,int m) //删除指定位置元素 { LinkList L=P,Q; for(int i=1;i<m;i++) { L=L->next; } Q=L->next; //移到删除位 L->next=L->next->next; //链接 free(Q); return OK; } void viewlist(LinkList P) { LinkList L=P->next; while(L) { printf("%d\t",L->data); L=L->next; } }