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

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

2、检索查找 94.6 输入插入元素的值和位置 94.7 删除元素 105小结 10参考文献 10附录：程序源代码 111问题分析和任务定义1.1 任务定义设计出链表结构的相关函数库，以便在程序设计中调用。进行链表中元素的 输入、查找、插入、删除等操作的课程设计。要求：(1)所设计的数据结构应尽可能节省存储空间。(2)程序的运行时间应尽可 能少。从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据链表的特点即存储空间的连续，从创建链表到插入，删除，查找元素以及输出一系列的步骤，连贯而下。算法的实现依赖于所采用的存 储结构，所以选择什么样的存储方式在课程设计中尤为

3、重要，这也是本程序好坏 的一个评定。1.2 面临的问题，进行分析解决，模块之间的联系。(1)在内存中开辟一块连续的内存空间，进行分析解决(2)利用物理位置的相邻来表示变量，达到预期效果，很好的完成任务。查找 元素以及输出一系列的步骤，连贯而下。(3)使用链表的数据结构来满足尽可能节省存储空间的要求，达到要求，从创 建链表到插入，删除，查找元素以及输出一系列的步骤，连贯而下。(4)输出界面设计与各个模块的联系，设计出链表结构的相关函数库，以便在 程序设计中调用，进行链表中元素的分析。2概要设计和数据结构的选择2.1 数据结构的选择本程序选择的数据结构是线性表中的链式结构(单链表)，原因如下：单链

4、表的定义：(1)单链表是线性表的链接存储表示。其各个数据元素可以相继存储，也可以 不相继存储，不过它为每个数据元素附加了一个链接指针，并形成的一个结点。(2)单链表的每一个结点分为两个部分：data和link。(3)链表的第一个结点的地址可以通过链表的头指针 first找到，其他结点的 地址则在前趋结点的link域中，链表的最后一个结点没有后继，在结点的 link 域中放一个空指针NULL(4)头指针first为空的单链表为空表，该链表一个结点也没有，相对地，头指 针first不为空且首元结点存在的单链表为非空表，表中至少有一个结点。2.2 结构图图1结构图2.3 函数实现的具体算法举例(1)

5、插入函数/*在带头结点的单链线性表L中第i个位置之前插入元素e */int Insert_List(LinkList L,int i,ElemType e)int j=0;LinkList p=L,s;while(p&&j<i-1)p=p->next;j+；if(!p|j>i-1)return ERROR;s=(LinkList)malloc(sizeof(struct LNode);s->data=e;s->next=p->next;p->next=s;return OK;(2)删除函数int Delete_List(LinkList

6、 L,int i,ElemType *e) /*在带头结点的单链线性表L中，删除第i个元素，并由e返回其值*/int j=0;LinkList p=L,q;while(p->next&&j<i-1)p=p->next;j+；if(!p->next|j>i-1)return 0;q=p->next;p->next=q->next;*e=q->data;free(q)；return 1;(3)查找元素/*当按位置查找元素，第i个元素存在时，其值赋给e并返回1,否则返回0 */int GetElem_List(LinkList L

7、,int i,ElemType *e)int j=0;LinkList p=L;while(p&&j<i)p=p->next;j+;if(!p|j>i) printf("链表不存在或参数i错)return 0;*e=p->data; /* 取第 i 个元素 */return 1;(5)显示单链表int Disp_List(LinkList L)/* 显示单链表 */LinkList p=L->next;if(p=Null) printf("单链表为空表");elseprintf("输出单链表:n")

8、;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;3课程设计思路一般的说，其过程如下：A.分析链表特点B.分析链表功能以及操作C.设计函数库D.制定调试计划：初步调试计划E.编写主函数，方便后面的测试F.制定完整的程序测试计

9、划G.书写文档，系统说明H.复查和审核：从技术的角度审查，从管理的角度审查3.1设计函数库设计函数库不能随心所欲，想编写什么函数就编写什么函数，而是要根据分 析链表所得结果，从分析结果入手，由分析我们知道链表可以进行的操作有：输入、输出、插入一个元素、删除一个元素、查找一个元素、取出一个元素。根据 这些操作分别写出函数：intInsert_List();/*插入元素 */intDelete_List();/*删除元素 */intGetElem_List();/*查找元素 */intDisp_List();/*显示元素 */intLength_List();/*求表长 */word资料4测试结果

10、及其分析4.1初始化word资料1请选癌要执行的操作II X ：U$ERSADM) N|$TRATORDES kt。P方阳 gbug'tes lee-找*M 查元元 表/除检滞 元者n 口口| 二please input ntinber H r图2初始化4.2逆序输入元素please input number 0 ,输入线性表中元素个数， 戢嘉髓磐在 1输入线性表中第4个元素; 髯输入线性表中第3个元素;66用输入线性表巾第2个元素;88端输入线性表中第1个元素;上图3逆序输入元素,34单链表的长度please input number 0?金链表表长为5图4计算长度遍历输出单链表pl

11、ease input numb看冲 0?*出单链表: 99->S8->t6->12->5->图5遍历4.5 检索查找输出单链表:请选择要执行的操作:找* 查元元元售一口 口口人春表表表强程3瞿链链出 第单津单墨 -1二二二12 3 4 5 6please input nunner 0 J请输你想查找的越据;12 核元素在顺序表中笛也置是：4图6查找4.6 输入插入元素的值和位置请输入要插入的元素的值和位置，用空格分隔:黔霍鳏窄的操作：找霍查元元 表京除 tin 元首一m:口口 人表出表表表 莺链链上 43t单津单晶 、嘉求普向性 -12 3 4 5 6 7plea

12、se input numbep 01Plm7篇出单链表:99->12->88->66->12->5->图7插入4.7 删除元素请输入要删除的元素的位置: 鑫i螂的操传12345670元占一口 口口人表出表表表找手 查元元please input numher4输出单链表:99->88->66->12->5->图8插入5小结通过这次课设，我学会了如何把数据结构的知识应用到实践当中， 同时也进 一步加深了对C/C+语言语法的应用，以及深刻的掌握了数据结构和C/C+语言的 结合运用。在编程过程中，遇到了许多问题，在一次次的运行错误后，

13、问题被一步 步改正，也从中学到了许多知识。虽然我的程序还不够完善，还需加以改进以实 现更多的功能，但是我会尽我最大的努力去完成它， 我相信我会努力去把程序做 的更加完美。参考文献1王昆仑，李红等编著.数据结构与算法.北京：中国铁道出版社，2007.2苏仕华等编著.数据结构课程设计.北京：机械工业出版社，2005.3苏仕华编著.数据结构与算法解析.合肥：中国科学技术大学出版社，2004.4郭嵩山等著国际大学生程序设计竞赛例题解北京：电子工业出版社,2008.附录：程序源代码#include<stdlib.h>#include<stdio.h># define TRUE 1

14、# define FALSE 0# define OK 1# define ERROR 0# define Null 0typedef int ElemType;typedef struct LNode ElemType data;struct LNode *next;LNode ,*LinkList;/*初始化单链表，即产生一个带头结点的空表，创建成功则返回空表的头指针*/ LinkList Init_List(void) LinkList L;L=(LinkList) malloc(sizeof(LNode);if(L)L->next=NULL; /产生空表，头结点的 next域为空

15、return L;/*按逆序产生一个长度为n链表，参数为初始化的空链表，及线性表长度n*/*每个元素依次插入在头结点后*/int Create_List(LinkList L,int n)int i;LinkList s; /*s变量用于保存新结点地址*/printf(" 生成有cK"元素的线性表：n",n);for(i=n;i>0;i-) printf("请输入线性表中第%d个元素:n”,i); /*逆序输入元素*/s=(LinkList)malloc(sizeof(LNode);if(!s)printf("创建结点不成功n"

16、);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;return i;/*当按位置查找元素，第i个元素存在时，其值赋给e并返回1,否则返回0 */int GetElem_List(LinkList L,int i,ElemType *e)int j=0;LinkList

17、p=L;while(p&&j<i)p=p->next;j+;if(!p|j>i) 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(p&&p->data!=e) p=p->next;i+;if(p)re

18、turn i;elsereturn 0;/*在带头结点的单链线性表L中第i个位置之前插入元素e */int Insert_List(LinkList L,int i,ElemType e)int j=0;LinkList p=L,s;while(p&&j<i-1)p=p->next;j+；if(!p|j>i-1)return ERROR;s=(LinkList)malloc(sizeof(struct LNode);s->data=e;s->next=p->next;p->next=s;return OK;int Delete_List

19、(LinkList L,int i,ElemType *e) /*在带头结点的单链线性表L中，删除第i个元素，并由e返回其值*/int j=0;LinkList p=L,q;while(p->next&&j<i-1)p=p->next;j+；if(!p->next|j>i-1)return 0;q=p->next;p->next=q->next;*e=q->data;free(q)；return 1;int Disp_List(LinkList L)/* 显示单链表 */LinkList p=L->next;if(p=

20、Null) printf("单链表为空表");elseprintf("输出单链表:n");while(p!=Null)printf("%d”,p->data);printf("->");p=p->next;printf("n");return 1;/*显示选择提示信息函数*/void ShowSelect() printf("n请选择要执行的操作：n");printf("n");printf(" 1-初始化 n");printf

21、(" 2-逆序输入元素n");printf(" 3-求单链表长度n");printf(" 4-遍历输出单链表n");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(select)case 1: PL=Init_List()