2022年2022年静态链表 .pdf

《2022年2022年静态链表 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年静态链表 .pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第页，共14 页1 兰州城市学院实验报告院、系：信息工程学院姓名白丽丽学号20070801050101 专业、班级计算机科学与技术071 本课程名称数据结构及算法实验室名称微机实验室实验名称静态链表存储结构及其实现日期、时间2009 年 12 月 10 日同组者无天气晴气压室（气）温实验报告内容：1实验目的本次实验的主要目的是： （ 1）理解静态链表的概念； （2）掌握静态链表存储结构的特点和数据结构的定义； （3）熟练掌握静态链表的基本操作的实现；（4）通过静态链表实际应用，提高学生分析和解决实际问题的能力。2实验内容（ 1）掌握静态链表存储结构的初始化（InitList ） 、清空（ Cl

2、earList ） 、判空（ ListEmpty ） 、求长度（ListLength ） 、 查询（LocateElem ） 、 插入（ ListInsert ） 、 删除（ListDelete） 、 前驱（PriorElem ） 、后继（ NextElem） 、输出（ ListTraverse ）等基本操作。（ 2）主控程序设计；3实验要求（ 1）各基本操作设计要求如下：void InitList(SLinkList L) 功能：产生空的静态链表L。Status ListEmpty(SLinkList L) 功能：若L 为空表，则返回OK，否则返回ERROR int ListLength(D

3、uLinkList L)功能：返回L 中数据结点个数。Status ListInsert(SLinkList L,int i,ElemType e) 功能：在L 中第 i 个元素之前插入新的数据元素e。Status GetElem(SLinkList L,int i,ElemType &e) 功能：用e返回 L 中第 i 个元素的值。Status PriorElem(SLinkList L,ElemType cur_e,ElemType &pre_e) 功能：若cur_e 是 L 的数据结点，且不是第一个，则用pre_e 返回它的前驱，否则操作失败， pre_e 无定义。Status Next

4、Elem(SLinkList L,ElemType cur_e,ElemType &next_e) 功能： 若 cur_e 是 L 的数据元素， 且不是最后一个，则用 next_e 返回它的后继， 否则操作失败， next_e 无定义。Status ListTraverse(SLinkList L,void(*vi)(ElemType) 功能：依次对L 的每个数据元素调用函数vi()。一旦 vi() 失败,则操作失败。Status ListTraverseBack(SLinkList L,void(*vi)(ElemType) 功能：逆序对L 的每个数据元素调用函数vi()。一旦 vi() 失

5、败,则操作失败。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - 第页，共14 页2 Status ListDelete(SLinkList L,int i,ElemType &e) 功能：删除在L 中第 i 个数据元素e，并返回其值int LocateElem(SLinkList L,ElemType e) 功能：在静态单链线性表L 中查找第 1 个值为 e 的元素。若找到，则返回它在L 中的位序，否则返回0。Status C

6、learList(SLinkList L) 功能：将L 重置为空表。4实验程序清单#include #include #include #include #define OK 1 #define ERROR 0 typedef int Status; typedef int ElemT ype; #define MAXSIZE 100 / 链表的最大长度typedef struct ElemType data; int cur; component,SLinkListMAXSIZE;void InitList(SLinkList L) int i; LMAXSIZE-1.cur=0; for(

7、i=0;iMAXSIZE-2;i+) Li.cur=i+1; LMAXSIZE-2.cur=0; int Malloc(SLinkList space) / 若备用链表非空,则返回分配的结点下标(备用链表的第一个结点),否则返回0 int i=space0.cur; if(i) / 备用链表非空space0.cur=spacei.cur; / 备用链表的头结点指向原备用链表的第二个结点return i; / 返回新开辟结点的坐标 void Free(SLinkList space,int k) / 将下标为k 的空闲结点回收到备用链表(成为备用链表的第一个结点) spacek.cur=spac

8、e0.cur; / 回收结点的游标指向备用链表的第一个结点space0.cur=k; / 备用链表的头结点指向新回收的结点 Status ClearList(SLinkList L) / 初始条件：线性表L 已存在。操作结果：将L 重置为空表名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - 第页，共14 页3 int i,j,k; i=LMAXSIZE-1.cur; / 链表第一个结点的位置LMAXSIZE-1.cur=0; /

9、 链表空k=L0.cur; / 备用链表第一个结点的位置L0.cur=i; / 把链表的结点连到备用链表的表头while(i) / 没到链表尾 j=i; i=Li.cur; / 指向下一个元素 Lj.cur=k; / 备用链表的第一个结点接到链表的尾部return OK; Status ListEmpty(SLinkList L) / 若 L 是空表，返回TRUE；否则返回FALSE if(LMAXSIZE-1.cur=0) / 空表return OK; else return ERROR; int ListLength(SLinkList L) / 返回 L 中数据元素个数int j=0,i

10、=LMAXSIZE-1.cur; / i指向第一个元素while(i) / 没到静态链表尾 i=Li.cur; / 指向下一个元素j+; return j; Status GetElem(SLinkList L,int i,ElemType &e) / 用 e 返回 L 中第 i个元素的值int l,k=MAXSIZE-1; / k指向表头序号if(iListLength(L) return ERROR; for(l=1;l=i;l+) / 移动到第i个元素处k=Lk.cur; e=Lk.data; return OK; int LocateElem(SLinkList L,ElemT ype

11、 e) / / 在静态单链线性表L 中查找第 1 个值为 e 的元素。若找到，则返回它在L 中的/ 位序，否则返回0。 （与其它LocateElem()的定义不同 ) int i=LMAXSIZE-1.cur; / i指示表中第一个结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - 第页，共14 页4 while(i&Li.data!=e) / 在表中顺链查找(e不能是字符串) i=Li.cur; return i; Stat

12、us PriorElem(SLinkList L,ElemType cur_e,ElemT ype &pre_e) / 初始条件：线性表L 已存在/ 操作结果：若cur_e 是 L 的数据元素，且不是第一个，则用pre_e返回它的前驱，/ 否则操作失败，pre_e 无定义int j,i=LMAXSIZE-1.cur; / i指示链表第一个结点的位置do / 向后移动结点j=i; i=Li.cur; while(i&cur_e!=Li.data); if(i) / 找到该元素 pre_e=Lj.data; return OK; return ERROR; Status NextElem(SLin

13、kList L,ElemT ype cur_e,ElemType &next_e) / 初始条件：线性表L 已存在/ 操作结果：若cur_e 是 L 的数据元素，且不是最后一个，则用next_e返回它的后继，/ 否则操作失败，next_e 无定义int j,i=LocateElem(L,cur_e); / 在 L 中查找第一个值为cur_e的元素的位置if(i) / L 中存在元素cur_e j=Li.cur; / cur_e的后继的位置if(j) / cur_e 有后继 next_e=Lj.data; return OK; / cur_e元素有后继 return ERROR; / L不存在c

14、ur_e元素 ,cur_e 元素无后继 Status ListInsert(SLinkList L,int i,ElemType e) / 在 L 中第 i 个元素之前插入新的数据元素e int l,j,k=MAXSIZE-1; / k指向表头if(iListLength(L)+1) return ERROR; j=Malloc(L); / 申请新单元if(j) / 申请成功名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - 第页

15、，共14 页5 Lj.data=e; / 赋值给新单元for(l=1;li;l+) / 移动 i-1 个元素k=Lk.cur; Lj.cur=Lk.cur; Lk.cur=j; return OK; return ERROR; Status ListDelete(SLinkList L,int i,ElemT ype &e) / 删除在 L 中第 i 个数据元素e，并返回其值int j,k=MAXSIZE-1; / k指向表头if(iListLength(L) return ERROR; for(j=1;j=1;i-) vi(Li.data); return OK; void visit(El

16、emT ype c) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - 第页，共14 页6 printf(%d ,c); void showmenu() printf(nn * * * * * * * * * * * * * * * * * * * * * * *n); printf( * 选择相应的操作*n); printf( * * * * * * * * * * * * * * * * * * * * * * *n); p

17、rintf( * * * *n); printf( * * 【 1】 建 表【 8 】 判 空* *n); printf( * * 【 2】 插 入【 9 】 按元素查找* *n); printf( * * 【 3】 删 除【 10】 按位置查找* *n); printf( * * 【 4】 置 逆【 11】前 驱* *n); printf( * * 【 5】 清 空【 12】 后 继* *n); printf( * * 【 6】 长 度【 0 】 退 出* *n); printf( * * 【 7】 打 印* *n); printf( * * * * * * * * * * * * * *

18、* * * * * * * * *n); printf( * * * * * * * * * * * * * * * * * * * * * * *n); void main() int j,k,select; Status i; ElemType e,e0; SLinkList L; InitList(L); printf( 空的静态链表已初始化成功!); while(1) showmenu(); scanf(%d,&select); switch(select) case 0:exit(1); case 1: system(CLS); for(j=1;j=10;j+) i=ListInse

19、rt(L,j,j); printf( 建立表成功 !所建表为： L=); ListTraverse(L,visit); printf(n 按任意键返回：); scanf(%d,&select); system(CLS); break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - 第页，共14 页7 case 2: system(CLS); printf( 请输入插入位置:); scanf(%d,&k); printf( 请

20、输入插入的元素:); scanf(%d,&j); i=ListInsert(L,k,j); if(i=1) printf( 插入成功 !链表中元素如下:n); ListTraverse(L,visit); else printf( 插入失败 !n); printf(n按任意键返回：); scanf(%d,&select); system(CLS); break; case 3: system(CLS); printf( 请输入删除元素的位置:); scanf(%d,&j); i=ListDelete(L,j,e); if(i) printf( 删除的元素为：%dn,e); printf( 删除

21、元素后链表中元素如下:n); ListTraverse(L,visit); else printf( 删除第 %d 个数据失败 (不从在此元素)!n,j); printf(n按任意键返回：); scanf(%d,&select); system(CLS); break; case 4: system(CLS); printf( 输出元素如下 :n); ListTraverseBack(L,visit); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 14 页 - - -

22、 - - - - - - 第页，共14 页8 printf(n 按任意键返回：); scanf(%d,&select); system(CLS); break; case 5: system(CLS); i=ClearList(L); printf( 清空 L 后： L=); ListTraverse(L,visit); i=ListEmpty(L); printf(L是 否 空 :i=%d (1: 是0: 否 ) 表L的 长 度=%dn,i,ListLength(L); printf(n 按任意键返回：); scanf(%d,&select); system(CLS); break; cas

23、e 6: system(CLS); printf( 表 L 的长度 =%dn,ListLength(L); printf(n按任意键返回：); scanf(%d,&select); system(CLS); break; case 7: system(CLS); printf( 依次输出 L 的元素： ); ListTraverse(L,visit); printf(n 按任意键返回：); scanf(%d,&select); system(CLS); break; case 8: system(CLS); i=ListEmpty(L); printf(L是否空 :i=%d(1:是0:否),i

24、); printf(n 按任意键返回：); scanf(%d,&select); system(CLS); break; case 9: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - 第页，共14 页9 system(CLS); printf( 请输入一个元素:n); scanf(%d,&j); k=LocateElem(L,j); if(k) printf( 值为 %d 的元素在静态链表中的位序为%dn,j,k); els

25、e printf( 没有值为 %d 的元素 n,j); printf(n 按任意键返回：); scanf(%d,&select); system(CLS); break; case 10: system(CLS); printf( 请输入元素位置:); scanf(%d,&j); k=GetElem(L,j,e); printf( 第%d 个元素的值为：%dn,j,k); printf(n 按任意键返回：); scanf(%d,&select); system(CLS); break; case 11: system(CLS); printf( 请输入元素位置:); scanf(%d,&j);

26、 GetElem(L,j,e0); i=PriorElem(L,e0,e); if(!i) printf( 元素 %d 无前驱 n,e0); else printf( 元素 %d 的前驱为： %dn,e0,e); printf(n按任意键返回：); scanf(%d,&select); system(CLS); break; case 12: system(CLS); printf( 请输入元素位置:); scanf(%d,&j); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9

27、 页，共 14 页 - - - - - - - - - 第页，共14 页10 GetElem(L,j,e0); i=NextElem(L,e0,e); if(!i) printf( 元素 %d 无后继 n,e0); else printf( 元素 %d 的后继为： %dn,e0,e); printf(n按任意键返回：); scanf(%d,&select); system(CLS); break; default: system(CLS); printf( 请选择菜单中的操作,按 0 退出程序 n); 5实验程序执行结果（ 1）主界面（2）新建名师资料总结 - - -精品资料欢迎下载 - -

28、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - 第页，共14 页11 （ 3）插入（ 4）删除名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - 第页，共14 页12 （ 5）查找（ 6）前驱名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师

29、精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - 第页，共14 页13 （ 7）后继5执行结果的分析：程序执行结果用菜单显示，通过switch （） case 语句，做出菜单，使操作人性化，操作简单明确。 静态链表存储结构中的操作，算法单一， 多用 while 语句和 for 循环实现。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - 第页，共14 页14 程序有些繁琐，有的

30、操作算法的时间和空间复杂度都比较大，所以程序不是很理想。6.试验心得及收获通过本实验，我了解并基本掌握了静态链表存储的结构及其算法，并通过对程序执行结的分析， 使程序不断的完善，并对静态链表存储这种存储结构有了更深的认识，明白了静态链表的存储结构及特点，对以后的学习有很大的帮助，通过本实验， 我感觉自己的c 语言基础太差，编程思想很弱，在静态链表基本操作程序实现时有一定的困难，本实验对我的收获很大，我将在以后的学习中，更加努力，希望可以做到学以致用的效果。教师意见成绩批改日期教师姓名名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -