《课程设计双链表的建立插入查找删除算法的实现》由会员分享，可在线阅读，更多相关《课程设计双链表的建立插入查找删除算法的实现（28页珍藏版）》请在金锄头文库上搜索。
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; head-next=head; head-prior=head; p=head; L.L=0; printf(请输入元素(0 结束)n); scanf(%d,&x); while(x!=0) s
