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

1、数据结构课程设计设计说明书双链表的建立插入查找删除算法的实现 学生姓名张鑫学号1021024077班级信管103成绩指导教师李婧数学与计算机科学学院2012年3月2日数据结构课程设计评阅书题目双链表的建立插入查找删除算法的实现学生姓名张鑫学号1021024077指导教师评语及成绩指导教师签名： 年 月 日答辩评语及成绩答辩教师签名： 年 月 日教研室意见：总成绩： 室主任签名：年 月 日课程设计任务书20112012学年第二学期专业： 信息管理与信息系统 学号： 1021024077 姓名： 张鑫 课程设计名称： 数据结构课程设计 设 计 题 目： 双链表的建立插入查找删除算法的实现 完 成

2、期 限：自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周 设计要求、设计依据、要求及主要内容（可另加附页）：设计内容：双链表的建立插入查找删除算法的实现，双链表具有双向链接的特点，克服了单链表的单向性。要求通过结构体类型建立空的双链表，在此基础上调用函数实现双链表的建立、插入、查找和删除等基本操作。设计要求：1.遵循结构化程序设计思想，采用c/c+实现。 2.界面友好，操作简便，容错性好。 指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日摘要本课题主要讨论在链式结构中建立双向链表。双向链表有两个指针域，其一指向直接前趋，另一指向直接后继。并合理利用插

3、入、查找、删除运算。和单链的循环表类似，双链表也可以有相应的循环表。用一个表头单元将双链表首尾相接，即将表头单元中的head指针指向表尾，并将表尾单元的next指针指向表头单元。关键词：双向链表；链式结构；直接前趋；直接后继目 录1.课题描述12需求分析22.1程序功能说明22.2输入输出23.程序流程图33.1创建双向链表33.2按位次查找43.3插入新的元素53.4删除一个元素64概要设计74.1 程序模块74.2 课题涉及的数据结构74.2.1 双链表结点的插入74.2.2 双链表结点的删除75. 调试分析以及设计体会86源程序代码97.程序运行结果147.1创建双链表147.2 输入元

4、素157.3 查找一个不属于链表的值167.4 正确的查找177.5不合法的插入一个数187.6正确的插入一个数197.7删除不合法的位次207.8删除位次21总结22参考文献231.课题描述双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。双链表有以下特点：双链表由头指针head惟一确定的。 带头结点的双链表的某些运算变得方便。 将头结点和尾结点链接起来，为双（向）循环链表。2需求分析2.1程序功能说明链表是线性表的链式表示，由于它不要求逻辑上相邻的元素在物理位置上也相邻，所以它没有顺序存储结构在做插入删除操作时需要移动

5、大量元素的弱点。 双链表的结点中有两个指针域， 一个指向直接后继， 一个指向直接前驱。本程序包括了的功能有：查找、插入、删除。在单循环链表中，虽然从任一单元出发，可以找到其前驱单元，但需要o(n)时间。如果我们希望能快速确定表中任一个元素的前驱和后继元素所在的单元，可以在链表的每个单元中设置两个指针，一个指向后继，另一个指向前驱，形成如图2.1所示的双向链表或简称为双链表。图2.1双链表示意图由于在双链表中可以直接确定一个单元的前驱单元和后继单元，我们可以用一种更自然的方式表示元素的位置，即用指向双链表中第i个单元而不是指向其前一个单元的指针来表示表的第i个位置。双链表的单元类型定义如下： t

6、ype struct dulnode elemtype data; struct dulnode *prior;struct dulnode *next; dulnode,*dulinklist;2.2输入输出由于本程序为演示程序，需用户控制程序操作。输出方面主要是显示：经指针移动所变化后得到的另一组新的元素。输入方面：运用双向循环链表，这样子较优与普通的双向链表，省去一个表尾的指针，使查询代码更加清晰，程序也更加简介。.3.程序流程图3.1创建双向链表如图3.1所示 建立一个双链表最后以0判断是否结束接收数据。start建立一个双向链表有p和s两个指针来接收元素是否以0结束 是否 继续接收数

7、据 s-data=x; s-next=p-next; s-prior=p; p-next-prior=s; p-next=s; p=s; return ok stop图3.1 创建双链表流程图 3.2按位次查找如图2.2所示 查找元素，判断位置是否合法，若合法进行查找运算。start引用dulinklist接收查找的元素位置双链表中有此元素否是进行查找运算输出数据 return ok stop图3.2 双链表查找运算流程图3.3插入新的元素如图2.3所示 查找元素，判断位置是否合法，若合法进行查插入运算。start引用dulinklist引用dulinklist接收插入元素以及位次双链表中有合

8、适的位置否 否是进行插入运算 输出数据return okstop图3.3 双链表插入运算流程图3.4删除一个元素如图3.4所示删除元素，判断位置是否合法，若合法进行查删除运算。start接收删除的位次及元素双向链表中有对应的值 否 进行删除运算是输出数据return ok; stop图3.4 双链表删除运算流程图4概要设计4.1 程序模块本程序实现双链表的创建、查找、插入、删除、显示、菜单为主的六个函数组成。大致分为：双链表创建演示主程序，双链表创建指针变化演示，结果输出，三大模块。4.2 课题涉及的数据结构本课题所用到的数据结构主要是双向链表4.2.1 双链表结点的插入 status lis

9、tinsert_dul(dulinklist &;l, int i, elemtype 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; 4.2.2 双链表结点的删除 status listdelete_dul(dulinklist&;l,int i,elemtype &;e) e=p-data; p-prior-next=p-next; p-next-prior=p-prior;

10、 free(p); return ok;5. 调试分析以及设计体会 程序调试中遇到的问题以及解决问题的方法。主要是在结点插入判断方面有难度，一开始不能准确的进行结点的判断和插入，然后就是插入结点的过程中位置不对，后面在网上找到了一段演示代码，通过研究这段代码解决了这个问题。还有就是在显示指针变化方面有问题，经过查询资料，解决结点插入方面的问题，用画箭头的方式来表现指针的变化。在运行程序时发现程序不能对不合法的位置进行判断，最后通过修改加上一个计数的变量解决了这个问题。6源程序代码#include#include#include#define list_init_size 100 /线性表存储空

11、间的初始分配量#define listincrement 10 /线性表存储空间的增配量#define ok 1#define error 0#define overflow -2typedef struct dulnodeint data;struct dulnode *prior, *next;int l;dulinklist;dulinklist *head;int putyuansu_dul(dulinklist &l) dulinklist *p,*s; int x; head=(dulinklist*)malloc(sizeof(dulinklist); head-data=-1;

12、 head-next=head; head-prior=head; p=head; l.l=0; printf(请输入元素(0 结束)n); scanf(%d,&x); while(x!=0) s=(dulinklist*)malloc(sizeof(dulinklist); s-data=x; s-next=p-next; s-prior=p; p-next-prior=s; p-next=s; p=s; scanf(%d,&x); l.l+; return ok;void display_dul(dulinklist &l)dulinklist * p=head-next;while(p!

13、=head)printf(%d ,p-data);p=p-next;printf(n);int locate_dul(dulinklist &l,int e) /查找 dulinklist * p=head-next; int i=1;if(p=null) return error; while(p-data!=e& p-next!=head) /寻找值为x的元素 p=p-next; i+; if(p-data=e) printf(查找出的位次是：%d n,i); else printf(t没有这个元素n); return ok;int listinsert_dul(dulinklist &l

14、,int i,int e) /插入 int j;j=0;dulinklist *p=head-next,*s;while(p-next!=head)&(jnext;j+;if(i0)&(j=i-1) s=(dulinklist*)malloc(sizeof(dulinklist);s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s; display_dul(l);return ok;int listdelet_dul(dulinklist &l,int i) /删除 int e,j=0; dulinklist *p=head-n

15、ext;while(p-next!=head)&(jnext;j+; if(i0)&(j=i)e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);display_dul(l);return ok;int menu_select() int a; dosystem(cls); /*运行前清屏*/ printf(tt*查找、插入、删除 system*n); /*菜单选择*/ printf(tt | 1. 输入元素 n); printf(tt | 2. 查找 n); printf(tt | 3. 插入 n); printf(tt | 4

16、. 删除 n); printf(tt | 5. 显示数据 n); printf(tt | 6. quit n); printf(tttgive your choice(1-6):); scanf(%d,&a); while(a6); return (a);int main(int argc, char* argv) dulinklist l;for(;) switch(menu_select() int e,i; case 1:putyuansu_dul(l); system(pause); break; case 2:printf(请输入查找的元素：); scanf(%d,&e); loca

17、te_dul(l,e); system(pause); break; case 3:printf(输入插入的数的位次); scanf(%d,&i); if(il.l) printf(t输入不合法t); system(pause); break; printf(请输入插入元素); scanf(%d,&e); listinsert_dul(l,i,e); system(pause); break; case 4:printf(输入删除的位次); scanf(%d,&i); if(il.l) printf(t输入不合法t); system(pause); break; listdelet_dul(l

18、,i); system(pause); break; case 5:display_dul(l); system(pause); case 6:printf(ttthave a good luck,bye-bye!n); printf(ttt); system(pause); exit(0); return 0;7.程序运行结果 本程序是演示程序，根据提示输入数据，也可以在等待所有过程结束后再退出。7.1创建双链表如图7.1所示 用户进入菜单开始操作程序 图7.1 菜单7.2 输入元素如图7.2所示 用户输入元素最后以0结束 图7.2 在双链表中输入元素7.3 查找一个不属于链表的值如图7.3

19、所示 用户输出一个不合法的位置 图7.3 不合法的查找7.4 正确的查找如图7.4所示 用户输入正确的位置并且输出正确的结果 图7.4 查找成功7.5不合法的插入一个数 如图7.5所示 用户输入一个不合法的插入位次图7.5 不合法的插入7.6正确的插入一个数 如图7.6所示 用户输入一个正确的位次并且输出正确的结果 图7.6 插入成功7.7删除不合法的位次如图7.7所示 用户输入一个不合法的删除位次图7.7不合法的删除7.8删除位次如图7.8所示 用户输入正确的删除位次并且删除所选元素 图7.8 删除成功总结在进行本次课程设计的实验操作中，由于自己的基础知识不是很好，出现了一些问题：在编程方面不熟，所以写出的代码总是出错；数据结构课程以前也没有好好学过，造成在构建程序数据结构时出现由于概念模糊而写错功能的问题。 但是在老师和同学们的帮助下，再通过查阅资料，最后终于写出了可以正确运行结果的代码，所以要感谢给我帮助的老师和同学。以前用 c 编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之