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

数据结构链表结构的相关函数库的设计学号20142014-2015学年第一学期《数据结构》课程设计报告题目：链表结构的相关函数库的设计专业：计算机科学与技术班级：12级计科（3）班姓名：指导教师：成绩：计算机与信息工程系数据结构链表结构的相关函数库的设计全文共19页，当前为第1页。2014年12月15日数据结构链表结构的相关函数库的设计全文共19页，当前为第1页。目录1问题分析和任务定义 概要设计和数据结构的选择2.1数据结构的选择本程序选择的数据结构是线性表中的链式结构（单链表），原因如下：单链表的定义：（1）单链表是线性表的链接存储表示。其各个数据元素可以相继存储，也可以不相继存储，不过它为每个数据元素附加了一个链接指针，并形成的一个结点。（2）单链表的每一个结点分为两个部分：data和link。（3）链表的第一个结点的地址可以通过链表的头指针first找到，其他结点的地址则在前趋结点的link域中，链表的最后一个结点没有后继，在结点的link域中放一个空指针NULL。（4）头指针first为空的单链表为空表，该链表一个结点也没有，相对地，头指针first不为空且首元结点存在的单链表为非空表，表中至少有一个结点。2.2结构图创建单链表输入数据创建单链表输入数据插入数据删除数据查找数据输出数据计算表长图SEQ图\*ARABIC1结构图数据结构链表结构的相关函数库的设计全文共19页，当前为第4页。数据结构链表结构的相关函数库的设计全文共19页，当前为第4页。2.3函数实现的具体算法举例（1）插入函数/*在带头结点的单链线性表L中第i个位置之前插入元素e*/intInsert_List(LinkListL,inti,ElemTypee){intj=0;LinkListp=L,s;while(p&&j<i-1){p=p->next;j++;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(structLNode));s->data=e;s->next=p->next;p->next=s;returnOK;}删除函数intDelete_List(LinkListL,inti,ElemType*e)/*在带头结点的单链线性表L中，删除第i个元素,并由e返回其值*/{intj=0;LinkListp=L,q;数据结构链表结构的相关函数库的设计全文共19页，当前为第5页。while(p->next&&j<i-1)数据结构链表结构的相关函数库的设计全文共19页，当前为第5页。{p=p->next;j++;}if(!p->next||j>i-1)return0;q=p->next;p->next=q->next;*e=q->data;free(q);return1;}（3）查找元素/*当按位置查找元素，第i个元素存在时,其值赋给e并返回1,否则返回0*/intGetElem_List(LinkListL,inti,ElemType*e){intj=0;LinkListp=L;while(p&&j<i){p=p->next;j++;}if(!p||j>i){printf("链表不存在或参数i错");return0;}*e=p->data;/*取第i个元素*/数据结构链表结构的相关函数库的设计全文共19页，当前为第6页。return1;数据结构链表结构的相关函数库的设计全文共19页，当前为第6页。}（5）显示单链表intDisp_List(LinkListL)/*显示单链表*/{LinkListp=L->next;if(p==Null)printf("单链表为空表");else{printf("输出单链表:\n");while(p!=Null){printf("%d",p->data);printf("->");p=p->next;}}printf("\n");return1;}（6）求单链表表长intLength_List(LinkListL){inti=0;LinkListp=L->next;while(p){i++;p=p->next;}数据结构链表结构的相关函数库的设计全文共19页，当前为第7页。returni;数据结构链表结构的相关函数库的设计全文共19页，当前为第7页。}3课程设计思路一般的说，其过程如下：A.分析链表特点B.分析链表功能以及操作C.设计函数库D.制定调试计划:初步调试计划E.编写主函数，方便后面的测试F.制定完整的程序测试计划G.书写文档，系统说明H.复查和审核：从技术的角度审查，从管理的角度审查3.1设计函数库设计函数库不能随心所欲，想编写什么函数就编写什么函数，而是要根据分析链表所得结果，从分析结果入手，由分析我们知道链表可以进行的操作有：输入、输出、插入一个元素、删除一个元素、查找一个元素、取出一个元素。根据这些操作分别写出函数：intInsert_List(); /*插入元素*/intDelete_List(); /*删除元素*/intGetElem_List(); /*查找元素*/intDisp_List(); /*显示元素*/数据结构链表结构的相关函数库的设计全文共19页，当前为第8页。intLength_List(); /*求表长*/数据结构链表结构的相关函数库的设计全文共19页，当前为第8页。4测试结果及其分析4.1初始化数据结构链表结构的相关函数库的设计全文共19页，当前为第9页。图SEQ图\*ARABIC2初始化数据结构链表结构的相关函数库的设计全文共19页，当前为第9页。4.2逆序输入元素图SEQ图\*ARABIC3逆序输入元素4.3单链表的长度图SEQ图\*ARABIC4计算长度4.4遍历输出单链表数据结构链表结构的相关函数库的设计全文共19页，当前为第10页。图SEQ图\*ARABIC5遍历数据结构链表结构的相关函数库的设计全文共19页，当前为第10页。4.5检索查找图SEQ图\*ARABIC6查找4.6输入插入元素的值和位置数据结构链表结构的相关函数库的设计全文共19页，当前为第11页。图7插入数据结构链表结构的相关函数库的设计全文共19页，当前为第11页。4.7删除元素图8插入5小结通过这次课设，我学会了如何把数据结构的知识应用到实践当中，同时也进一步加深了对c/c++语言语法的应用，以及深刻的掌握了数据结构和c/c++语言的结合运用。

在编程过程中，遇到了许多问题，在一次次的运行错误后，问题被一步步改正，也从中学到了许多知识。虽然我的程序还不够完善，还需加以改进以实现更多的功能，但是我会尽我最大的努力去完成它，我相信我会努力去把程序做的更加完美。参考文献［1］王昆仑,李红等编著.数据结构与算法.北京:中国铁道出版社,2007.［2］苏仕华等编著.数据结构课程设计.北京：机械工业出版社,2005.［3］苏仕华编著.数据结构与算法解析.合肥:中国科学技术大学出版社,2004.数据结构链表结构的相关函数库的设计全文共19页，当前为第12页。［4］郭嵩山等著国际大学生程序设计竞赛例题解北京:电子工业出版社,2008.数据结构链表结构的相关函数库的设计全文共19页，当前为第12页。附录：程序源代码#include<stdlib.h>#include<stdio.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineNull0typedefintElemType;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;/*初始化单链表，即产生一个带头结点的空表，创建成功则返回空表的头指针*/LinkListInit_List(void){LinkListL;L=(LinkList)malloc(sizeof(LNode));if(L)L->next=NULL;//产生空表，头结点的next域为空returnL;}/*按逆序产生一个长度为n链表，参数为初始化的空链表，及线性表长度n*/数据结构链表结构的相关函数库的设计全文共19页，当前为第13页。/*每个元素依次插入在头结点后*/数据结构链表结构的相关函数库的设计全文共19页，当前为第13页。intCreate_List(LinkListL,intn){inti;LinkLists;/*s变量用于保存新结点地址*/printf("生成有%d个元素的线性表:\n",n);for(i=n;i>0;i--){printf("请输入线性表中第%d个元素:\n",i);/*逆序输入元素*/s=(LinkList)malloc(sizeof(LNode));if(!s){printf("创建结点不成功\n");return0;}scanf("%d",&s->data);s->next=L->next;L->next=s;}return1;}/*求单链表表长，返回L中数据元素个数*/intLength_List(LinkListL){inti=0;LinkListp=L->next;while(p){i++;p=p->next;数据结构链表结构的相关函数库的设计全文共19页，当前为第14页。}数据结构链表结构的相关函数库的设计全文共19页，当前为第14页。returni;}/*当按位置查找元素，第i个元素存在时,其值赋给e并返回1,否则返回0*/intGetElem_List(LinkListL,inti,ElemType*e){intj=0;LinkListp=L;while(p&&j<i){p=p->next;j++;}if(!p||j>i){printf("链表不存在或参数i错");return0;}*e=p->data;/*取第i个元素*/return1;}/*按元素查找，查找链表中是否存在值为e的元素，存在，则返回L中第一个e元素的位序,若不存在,则返回值为0*/intLocate_List(LinkListL,ElemTypee){inti=0;LinkListp=L;while(p&&p->data!=e){p=p->next;数据结构链表结构的相关函数库的设计全文共19页，当前为第15页。i++;数据结构链表结构的相关函数库的设计全文共19页，当前为第15页。}if(p)returni;elsereturn0;}/*在带头结点的单链线性表L中第i个位置之前插入元素e*/intInsert_List(LinkListL,inti,ElemTypee){intj=0;LinkListp=L,s;while(p&&j<i-1){p=p->next;j++;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(structLNode));s->data=e;s->next=p->next;p->next=s;returnOK;}intDelete_List(LinkListL,inti,ElemType*e)/*在带头结点的单链线性表L中，删除第i个元素,并由e返回其值*/{intj=0;数据结构链表结构的相关函数库的设计全文共19页，当前为第16页。LinkListp=L,q;数据结构链表结构的相关函数库的设计全文共19页，当前为第16页。while(p->next&&j<i-1){p=p->next;j++;}if(!p->next||j>i-1)return0;q=p->next;p->next=q->next;*e=q->data;free(q);return1;}intDisp_List(LinkListL)/*显示单链表*/{LinkListp=L->next;if(p==Null)printf("单链表为空表");else{printf("输出单链表:\n");while(p!=Null){printf("%d",p->data);printf("->");p=p->next;}}printf("\n");return1;}数据结构链表结构的相关函数库的设计全文共19页，当前为第17页。/*显示选择提示信息函数*/数据结构链表结构的相关函数库的设计全文共19页，当前为第17页。voidShowSelect(){printf("\n请选择要执行的操作：\n");printf("\n");printf("1初始化\n");printf("2逆序输入元素\n");printf("3求单链表长度\n");printf("4遍历输出单链表\n");printf("5在单链表中检索查找\n");printf("6向单链表中插入元素\n");printf("7从单链表中删除元素\n");printf("0退出\n");printf("\n");printf("pleaseinputnumber0~~7\n\n");}intmain(void){LinkListPL=NULL;inti,x,flag;intlen;/*表示单链表长*/intselect;/*select变量表示用户的选择项*/ShowSelect();scanf("%d",&select);while(select!=0){switch(select){case1:PL=Init_List();break;case2:printf("请输入线性表中元素个数：\n");scanf("%d",&len);Create_List(PL,len);br