数据结构链表结构的相关函数库的设计

1、数据结构课程设计报告学号1208210146 数据结构课程设计报告题目：链表结构的相关函数库的设计专业：计算机科学与技术班级：12 级计科（ 3）班姓名：指导教师：成绩：计算机与信息工程系2014 年 12月 15 日2014-2015学年 第一学期数据结构课程设计报告目录1 问题分析和任务定义 . 11.1 任务定义 . 11.2 面临的问题，进行分析解决，模块之间的联系。. 12 概要设计和数据结构的选择. 22.1 数据结构的选择. 22.2 结构图 . 22.3 函数实现的具体算法举例. 33 课程设计思路 . 63.1 设计函数库 . 64 测试结果及其分析 . 74.1 初始化 .

2、 74.2 逆序输入元素 . 84.3 单链表的长度 . 84.4 遍历输出单链表. 84.5 检索查找 . 94.6 输入插入元素的值和位置 . 94.7 删除元素 . 10 5 小结. 10 参考文献 . 10 附录：程序源代码 . 11 数据结构课程设计报告1 1 问题分析和任务定义1.1 任务定义设计出链表结构的相关函数库， 以便在程序设计中调用。 进行链表中元素的输入、查找、插入、删除等操作的课程设计。要求：（1）所设计的数据结构应尽可能节省存储空间。 （2）程序的运行时间应尽可能少。从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据链表的特点即

3、存储空间的连续，从创建链表到插入， 删除，查找元素以及输出一系列的步骤，连贯而下。 算法的实现依赖于所采用的存储结构，所以选择什么样的存储方式在课程设计中尤为重要，这也是本程序好坏的一个评定。1.2 面临的问题，进行分析解决，模块之间的联系。（1）在内存中开辟一块连续的内存空间，进行分析解决（2）利用物理位置的相邻来表示变量，达到预期效果，很好的完成任务。查找元素以及输出一系列的步骤，连贯而下。（3）使用链表的数据结构来满足尽可能节省存储空间的要求，达到要求，从创建链表到插入，删除，查找元素以及输出一系列的步骤，连贯而下。（4）输出界面设计与各个模块的联系，设计出链表结构的相关函数库，以便在程

4、序设计中调用，进行链表中元素的分析。数据结构课程设计报告2 2 概要设计和数据结构的选择2.1 数据结构的选择本程序选择的数据结构是线性表中的链式结构（单链表），原因如下：单链表的定义：（1）单链表是线性表的链接存储表示。其各个数据元素可以相继存储，也可以不相继存储，不过它为每个数据元素附加了一个链接指针，并形成的一个结点。（2） 单链表的每一个结点分为两个部分：data 和link 。（3） 链表的第一个结点的地址可以通过链表的头指针first找到，其他结点的地址则在前趋结点的link 域中，链表的最后一个结点没有后继，在结点的link域中放一个空指针 null 。（4）头指针first为空

5、的单链表为空表，该链表一个结点也没有，相对地，头指针first不为空且首元结点存在的单链表为非空表，表中至少有一个结点。2.2 结构图图 1 结构图创建单链表输入数据插入数据删除数据查找数据输出数据计算表长数据结构课程设计报告3 2.3 函数实现的具体算法举例（1）插入函数/* 在带头结点的单链线性表l中第i 个位置之前插入元素 e */ int insert_list(linklist l,int i,elemtype e) int j=0; linklist p=l,s; while(p&jnext; j+; if(!p|ji-1) return error; s=(linklis

6、t)malloc(sizeof(struct lnode); s-data=e; s-next=p-next; p-next=s; return ok; （2）删除函数int delete_list(linklist l,int i,elemtype *e) /* 在带头结点的单链线性表l中，删除第 i 个元素, 并由e返回其值 */ int j=0; linklist p=l,q; while(p-next&jnext; j+; if(!p-next|ji-1) return 0; q=p-next; p-next=q-next; *e=q-data; free(q); return

7、 1; （3）查找元素/* 当按位置查找元素，第 i 个元素存在时 , 其值赋给 e并返回 1, 否则返回 0 */ int getelem_list(linklist l,int i,elemtype *e) int j=0; linklist p=l; while(p&jnext; j+; if(!p|ji) printf(链表不存在或参数 i 错); return 0; *e=p-data; /* 取第i 个元素 */ return 1; 数据结构课程设计报告5 （5）显示单链表int disp_list(linklist l)/*显示单链表 */ linklist p=l-ne

8、xt; if(p=null) printf(单链表为空表 ); else printf(输出单链表 :n); while(p!=null) printf(%d,p-data); printf(-); p=p-next; printf(n); return 1; （6）求单链表表长int length_list(linklist l) int i=0; linklist p=l-next; while(p) i+; p=p-next; return i; 数据结构课程设计报告6 3 课程设计思路一般的说，其过程如下：a. 分析链表特点b. 分析链表功能以及操作c. 设计函数库d. 制定调试计划

9、:初步调试计划e. 编写主函数，方便后面的测试f. 制定完整的程序测试计划g . 书写文档，系统说明h. 复查和审核：从技术的角度审查，从管理的角度审查3.1 设计函数库设计函数库不能随心所欲， 想编写什么函数就编写什么函数，而是要根据分析链表所得结果， 从分析结果入手， 由分析我们知道链表可以进行的操作有：输入、输出、插入一个元素、删除一个元素、查找一个元素、取出一个元素。根据这些操作分别写出函数：int insert_list(); /* 插入元素 */ int delete_list(); /* 删除元素 */ int getelem_list(); /* 查找元素 */ int dis

10、p_list(); /* 显示元素 */ int length_list(); /* 求表长 */ 数据结构课程设计报告7 4 测试结果及其分析4.1 初始化图 2 初始化数据结构课程设计报告8 4.2 逆序输入元素图 3 逆序输入元素4.3 单链表的长度图 4 计算长度4.4 遍历输出单链表图 5 遍历数据结构课程设计报告9 4.5 检索查找图 6 查找4.6 输入插入元素的值和位置图 7 插入数据结构课程设计报告10 4.7 删除元素图 8 插入5 小结通过这次课设， 我学会了如何把数据结构的知识应用到实践当中，同时也进一步加深了对 c/c+ 语言语法的应用，以及深刻的掌握了数据结构和c/

11、c+ 语言的结合运用。在编程过程中， 遇到了许多问题， 在一次次的运行错误后， 问题被一步步改正，也从中学到了许多知识。 虽然我的程序还不够完善， 还需加以改进以实现更多的功能，但是我会尽我最大的努力去完成它，我相信我会努力去把程序做的更加完美。参考文献1王昆仑 , 李红等编著 . 数据结构与算法 . 北京: 中国铁道出版社 ,2007. 2苏仕华等编著 . 数据结构课程设计 . 北京：机械工业出版社 ,2005. 3 苏仕华编著 . 数据结构与算法解析 . 合肥: 中国科学技术大学出版社,2004. 4郭嵩山等著国际大学生程序设计竞赛例题解北京: 电子工业出版社 ,2008.数据结构课程设计

12、报告11 附录：程序源代码#include #include #define true 1 #define false 0 #define ok 1 #define error 0 #define null 0 typedef int elemtype; typedef struct lnode elemtype data; struct lnode *next; lnode ,*linklist; /* 初始化单链表， 即产生一个带头结点的空表， 创建成功则返回空表的头指针*/ linklist init_list(void) linklist l; l=(linklist) malloc(

13、sizeof(lnode); if(l) l-next=null; /产生空表，头结点的next 域为空 return l; /* 按逆序产生一个长度为n 链表，参数为初始化的空链表，及线性表长度n*/ /* 每个元素依次插入在头结点后*/ 数据结构课程设计报告12 int create_list(linklist l,int n) int i; linklist s; /*s变量用于保存新结点地址 */ printf(生成有 %d个元素的线性表 :n,n); for(i=n;i0;i-) printf(请输入线性表中第 %d 个元素 :n,i); /*逆序输入元素 */ s=(linklis

14、t)malloc(sizeof(lnode); if(!s) printf(创建结点不成功 n); return 0; scanf(%d,&s-data); s-next=l-next; l-next=s; return 1; /* 求单链表表长，返回 l 中数据元素个数 */ int length_list(linklist l) int i=0; linklist p=l-next; while(p) i+; p=p-next; 数据结构课程设计报告13 return i; /* 当按位置查找元素，第i 个元素存在时 , 其值赋给 e 并返回 1, 否则返回 0 */ int ge

15、telem_list(linklist l,int i,elemtype *e) int j=0; linklist p=l; while(p&jnext; j+; if(!p|ji) printf(链表不存在或参数i 错); return 0; *e=p-data; /* 取第 i 个元素 */ return 1; /* 按元素查找， 查找链表中是否存在值为e 的元素，存在，则返回 l 中第一个e 元素的位序 , 若不存在 , 则返回值为 0 */ int locate_list(linklist l,elemtype e) int i=0; linklist p=l; while(

16、p&p-data!=e) p=p-next; i+; 数据结构课程设计报告14 if(p) return i; else return 0; /* 在带头结点的单链线性表l 中第 i 个位置之前插入元素e */ int insert_list(linklist l,int i,elemtype e) int j=0; linklist p=l,s; while(p&jnext; j+; if(!p|ji-1) return error; s=(linklist)malloc(sizeof(struct lnode); s-data=e; s-next=p-next; p-nex

17、t=s; return ok; int delete_list(linklist l,int i,elemtype *e) /* 在带头结点的单链线性表 l 中，删除第 i 个元素 , 并由 e 返回其值 */ int j=0; linklist p=l,q; 数据结构课程设计报告15 while(p-next&jnext; j+; if(!p-next|ji-1) return 0; q=p-next; p-next=q-next; *e=q-data; free(q); return 1; int disp_list(linklist l)/*显示单链表 */ linklist p

18、=l-next; if(p=null) printf(单链表为空表 ); else printf(输出单链表 :n); while(p!=null) printf(%d,p-data); printf(-); p=p-next; printf(n); return 1; /* 显示选择提示信息函数 */ 数据结构课程设计报告16 void showselect() printf(n请选择要执行的操作： n); printf(-n); printf( 1-初始化 n); printf( 2-逆序输入元素 n); printf( 3-求单链表长度 n); printf( 4-遍历输出单链表 n);

19、 printf( 5-在单链表中检索查找 n); printf( 6-向单链表中插入元素 n); printf( 7-从单链表中删除元素 n); printf( 0- 退出n); printf(-n); printf(please input number 07 nn); int main(void) linklist pl=null; int i,x,flag; int len; /*表示单链表长 */ int select; /*select变量表示用户的选择项 */ showselect(); scanf(%d,&select); while(select!=0) switch(selec