双链表的建立插入查找删除算法的实现

1、数据结构课程设计设计说明书双链表的建立插入查找删除算法的实现 学生姓名程站伟学号1221024049班级信管1202成绩指导教师申静数学与计算机科学学院2014年3月7日课程设计任务书20132014学年第二学期课程设计名称： 数据结构课程设计 课程设计题目： 双链表的建立插入查找删除算法的实现 完 成 期 限：自 2014年 2 月24日至 2014年 3 月 7 日共 2 周设计内容：1.任务说明（1）任意输入一组数据，能得到一个带头结点的双向链表；（2）查找数据域为一特定值的某个结点时，从表头结点往后依次比较各结点数据域的值，若正是该特定值，则返回指向结点的指针，否则继续往后查，直到表尾

2、；（3）可以随意地在某已知结点p前或者p后插入一个新的结点；（4）删除某个结点，即插入某个结点的逆操作。2.要求1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？ 2）逻辑设计：写出抽象数据类型的定义，各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7）编写课程设计报告；3

3、.参考资料指导教师：申静 教研室负责人：申静课程设计评阅评语：指导教师签名： 年 月 日摘要此课题讨论如何在链式结构中建立双向链表，并且合理利用如何在双链表中引用插入、查找、删除运算。双向链表又名双链表，它有两个指针域，其一指向直接前驱，另一指向直接后继。双链表由头指针head唯一确定的。带头结点的双链表的某些运算变得方便。和单链的循环表类似，双链表也可以有相应的循环表。用一个表头单元将双链表首尾相接，即将表头单元中的head指针指向表尾，并将表尾单元的next指针指向表头单元。 关键词：双向链表；链式结构；直接前趋；直接后继 目录1.课题描述12需求分析22.1序功能说明23概要设

4、计33.1 程序描述33.2双链表元素的插入33.4双链表的删除34程序流程图44.1创建双向链表44.2插入新的元素54.3删除元素64.4查找元素75程序编码86程序调试分析137结果分析147.1 进行双链表的创建147.2 进行插入操作147.3 进行查找操作157.4 删除操作15总结16参考文献171. 课题描述双链表双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。双链表由头指针head惟一确定的。 带头结点的双链表的某些运算变得方便。 将头结点和尾结点链接起来，为双（向）循环链表。双链表的的存储结构Type

5、def struct DuLNode ElemType date;struct DuLNode *prior;struct DuLNode *next;DuLNode,*DuLinkList;2需求分析2.1序功能说明链表是线性表的链式表示，由于它不要求逻辑上相邻的元素子在物理位置上也相邻，所以它没有顺序存储结构在插入删除操作时需要移动大量元素的弱点。双链表有两个指针域，一个指向指针前驱，一个指向指针后继。本程序包括的功能：插入、查找、删除。如图2.11为双链表的流程示意图：图2.1如图2.12是在双向链表中插入结点时指针变化状况： 图2.2插入元素如图2.13是在双向链表中删除结点时指针变化

6、状况： 图2.3删除结点3概要设计3.1 程序描述本次程序设计包括双链表的建立,链表的输出,数值的插入,数值的删除,数值的查找,输出菜单列表等六大函数.主要分为双链表创建，双链表创建指针变化，结果输出，三大步骤。 3.2双链表元素的插入Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) /在表L中第i个位置插入元素e/ if(!(s=(DuLinklist)malloc(sizeof(DuLNode) return ERROR;s->data=e; s->prior=p->prior; p->piror

7、-next=s; s->next=p; p->prior=s; return OK; 3.4双链表的删除Status ListDelete_DuL(DuLinkList&L,int i,ElemType e) /表L中第i个位置删除元素e/ e=p->data; p->prior->next=p->next; p->next->prior=p->prior; free(p); return OK;4程序流程图4.1创建双向链表图4.1创建表4.2插入新的元素图4.2插入4.3删除元素图4.3删除数4.4查找元素 图4.4查找数5程序

8、编码#include<stdio.h>#include<stdlib.h>#define ok 1#define LEN sizeof(linknode)typedef struct nodeint date;node *next;node *prior;linknode,*linklist;linknode* chuangjian() /*创建一个双链表*/ linknode *h,*s,*r; int n,x; h=(linknode*)malloc(LEN); /*设置头结点*/ h->next=NULL; h->prior=NULL; r=h; pr

9、intf("输入想要建的链表的长度："); scanf("%d",&n); /*输入想建链表的长度*/ for(int i=0;i<n;i+) printf("输入链表第%d个元素：",i+1); s=(linknode*)malloc(LEN); scanf("%d",&x); s->date=x; s->next=NULL; s->prior=r; /*令当前元素向前指的指针指向前一个元素地址*/ r->next=s; r=s; printf("nn&qu

10、ot;); return h;int ListLength(linknode *head )int i=0;linknode *p=head->next;/p指向第一个结点while(p!=NULL)/p没到表头i+;p=p->next;return i;void print(linknode *h) /*输出建立的双向链表*/linklist p=h->next;printf("生成链表如下：n");while(p!=NULL) /*如果当前元素不为空输出*/printf("%d ",p->date);p=p->next;

11、printf("nn");void insert(linknode *head) /*建立函数向链表中某个位置插入指定元素*/int x,y;linknode *h,*p,*q;printf("输入想要插入的数和位置（中间用空格隔开）：");scanf("%d%d",&x,&y);h=(linknode*)malloc(LEN);h->date=x;p=head;q=p->next;for(int i=1;i<y;i+) /*查找制定的位置*/p=p->next;q=p->next;if(

12、q=NULL)p->next=h; h->prior=p; h->next=q;elsep->next=h; h->prior=p; h->next=q; q->prior=h; /*插入后调用函数输出*/print(head);void delet(linknode *head) /*建立函数删除指定元素*/int x;printf("输入想要删除的数：");scanf("%d",&x);linknode *p,*q;p=head->next;while(p->date!=x&&am

13、p;p->next!=NULL) /*查找指定删除的元素*/q=p;p=p->next;if(p->date=x)if(p=head->next) /*如果指定删除元素为首元结点进行如下操作*/head->next=p->next;p->next->prior=head;elseq->next=p->next;p->next->prior=q; free(p);int find(linknode* head) /*建立函数查找某个元素前后两个元素值*/int x,j;linknode *p;printf("输入想

14、要查找的数：");scanf("%d",&x);p=head->next; for(j=0;j<ListLength(head);j+) if(p->date=x) printf("要查找的是第%d个元素n",j+1); break; else p=p->next; if(j>=ListLength(head)/第i个元素不存在printf("n不存在n"); return(ok);void menu()printf("*双向链表的建立及操作*n");printf(&

15、quot; 1:构建双向链表n"); printf(" 2:输出双向链表n");printf(" 3:双向链表插入n");printf(" 4:双向链表查找n");printf(" 5:双向链表删除n"); printf(" 0:退出n" );printf("*n");void main() linknode *head; int i; head=NULL; do menu(); i=-1; / while(i<0|i>5) / printf("

16、;请选择0到5的操作:");scanf("%d",&i);if(i>=6|i<=0) /判断出入的i是否在0-5之间printf("你的输入非法！");exit(0);printf("n");switch(i)case 1: printf("建立双向链表"); head=chuangjian(); break; case 2: printf("输出双向链表"); print(head); break; case 3: printf("双向链表插入"

17、;); insert(head);print(head); break; case 4:int m; printf("双向链表查找"); m=find(head); break; case 5: printf("双向链表删除"); delet(head);print(head); break; default: printf("退出"); exit (0); while(i!=0);printf(" 谢谢使用！ "); 6程序调试分析在程序中调试中我遇到的的问题以及如何解决了问题。主要是在结点查找和插入方面有问题。

18、首先对结点的插入不是很准确，最后在书上查找了相关代码进行了分析，还与同学共同探讨，最终也解决了这个问题。对于查找问题就是输入查找的数，但在输出的时候不能进行输出查找数的位置。经过咨询同学，在他们的帮助下找出了问题，并且进行了改正。7结果分析此程序通过进行输入数据进行一系列操作。7.1 进行双链表的创建如图7.1输入数据：图7.1表的创建7.2进行插入操作如图7.2插入一个数：图7.2数的插入7.3 进行查找操作如图7.3输入要查找的数：图7.3数的查找7.4删除操作如图7.4入要删除：图7.4数的删除总结在这次数据结构课程设计中，由于自己的基础知识不是很好，出现了许多问题。1、在编程方面不精通，写的代码总是会出错；2、c语言、数据结构课程基础不是很好，在构建程序数据时频频出错。例如，对于c语言中的（.）和（->）概念混淆。在同学的帮助下，再通过查阅资料，最后终于写出了可以正确运行结果的代码，所以非常感谢给我帮助的同学。此外，经过这么长时间的努力，最终完成这个课设，也很有成就感。在此次完成作业中，我意识到一个程序代码的成功不仅仅是消除语法错误，还要注意