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

数据结构课程设计设计说明书双链表的建立插入查找删除算法的实现 学生姓名程站伟学号1221024049班级信管1202成绩指导教师申静数学与计算机科学学院2014年3月7日课程设计任务书20132014学年第二学期课程设计名称： 数据结构课程设计 课程设计题目： 双链表的建立插入查找删除算法的实现 完 成 期 限：自 2014年 2 月24日至 2014年 3 月 7 日共 2 周设计内容：1.任务说明（1）任意输入一组数据，能得到一个带头结点的双向链表；（2）查找数据域为一特定值的某个结点时，从表头结点往后依次比较各结点数据域的值，若正是该特定值，则返回指向结点的指针，否则继续往后查，直到表尾；（3）可以随意地在某已知结点p前或者p后插入一个新的结点；（4）删除某个结点，即插入某个结点的逆操作。2.要求1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？ 2）逻辑设计：写出抽象数据类型的定义，各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7）编写课程设计报告；3.参考资料指导教师：申静 教研室负责人：申静课程设计评阅评语：指导教师签名： 年 月 日摘要此课题讨论如何在链式结构中建立双向链表，并且合理利用如何在双链表中引用插入、查找、删除运算。双向链表又名双链表，它有两个指针域，其一指向直接前驱，另一指向直接后继。双链表由头指针head唯一确定的。带头结点的双链表的某些运算变得方便。和单链的循环表类似，双链表也可以有相应的循环表。用一个表头单元将双链表首尾相接，即将表头单元中的head指针指向表尾，并将表尾单元的next指针指向表头单元。 关键词：双向链表；链式结构；直接前趋；直接后继目录1.课题描述12需求分析22.1序功能说明23概要设计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惟一确定的。 带头结点的双链表的某些运算变得方便。 将头结点和尾结点链接起来，为双（向）循环链表。双链表的的存储结构Typedef 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是在双向链表中删除结点时指针变化状况： 图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-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程序编码#include#include#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; printf(输入想要建的链表的长度：); scanf(%d,&n); /*输入想建链表的长度*/ for(int i=0;idate=x; s-next=NULL; s-prior=r; /*令当前元素向前指的指针指向前一个元素地址*/ r-next=s; r=s; printf(nn); 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;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;inext;q=p-next;if(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&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(输入想要查找的数：);scanf(%d,&x);p=head-next; for(j=0;jdate=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( 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(i5) / printf(请选择0到5的操作:);scanf(%d,&i);if(i=6|i）概念混淆。在同学的帮助下，再通过查阅资料，最后终于写出了可以正确运行结果的代码，所以非常感谢给我帮助的同学。此外，经过这么长时间的努力，最终完成这个课设，也很有成就感。在此次完成作业中，我意识到一个程序代码的成功不仅仅是消除语法错误，还要注意一些细节。编程者还必须时刻保持头脑清醒，要细心的进行书写代码操作。数据结构的设计不仅仅考验我们对课本中一些知识的掌握，还考验我们思维逻辑是否紧密。通过这次课程设计，使我意识到作为一名计算机系的学生，正确掌握一门程序语言和数据结构的重要性