1、 数据结构数据结构课程设计课程设计 设计说明书设计说明书 双链表的建立插入查找删除算法的实现 学 生 姓 名 学号 班级 成绩 指 导 教 师 课程设计任务书 20112012 学年第二学期学年第二学期 课程设计名称： 数据结构课程设计 设 计 题 目： 双链表的建立插入查找删除算法的实现 完 成 期 限： 自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周 设计要求、设计依据、要求及主要内容（可另加附页） ： 设计内容：双链表的建立插入查找删除算法的实现，双链表具有双向链接的特点，克服了单链表的 单向性。要求通过结构体类型建立空的双链表，在此基础上调用函数实现双链表
2、的建立、插入、查 找和删除等基本操作。 设计要求：1.遵循结构化程序设计思想，采用 C/C+实现。 2.界面友好，操作简便，容错性好。 指导教师（签字） ： 教研室主任（签字） ： 批准日期： 年 月 日 摘要摘要 本课题主要讨论在链式结构中建立双向链表。双向链表有两个指针域，其一指向直接前趋，另 一指向直接后继。并合理利用插入、查找、删除运算。和单链的循环表类似，双链表也可以有相应 的循环表。用一个表头单元将双链表首尾相接，即将表头单元中的 head 指针指向表尾，并将表尾单 元的 next 指针指向表头单元。 关键词关键词：双向链表；链式结构；直接前趋；直接后继 目目 录录 1.1.课题描
3、述课题描述 1 1 2 2需求分析需求分析 1 1 2.1 程序功能说明 1 2.2 输入输出 2 3.3.程序流程图程序流程图 2 2 3.1 创建双向链表 2 3.2 按位次查找 3 3.3 插入新的元素 4 3.4 删除一个元素 5 4 4概要设计概要设计 6 6 4.1 程序模块 6 4.2 课题涉及的数据结构 6 4.2.1 双链表结点的插入 7 4.2.2 双链表结点的删除 7 5. 5. 调试分析以及设计体会调试分析以及设计体会 7 7 6 6源程序代码源程序代码 8 8 7.7.程序运行结果程序运行结果 1313 7.1 创建双链表 . 13 7.2 输入元素. 14 7.3
4、查找一个不属于链表的值 . 15 7.4 正确的查找 . 16 7.5 不合法的插入一个数 17 7.6 正确的插入一个数 18 7.7 删除不合法的位次 19 7.8 删除位次 . 20 总结总结 2121 参考文献参考文献 2323 1 1.1.课题描述课题描述 双（向）链表中有两条方向不同的链，即每个结点中除 next 域存放后继结点地址外，还 增加一个指向其直接前趋的指针域 prior。双链表有以下特点： 双链表由头指针 head 惟一确定的。 带头结点的双链表的某些运算变得方便。 将头结点和尾结点链接起来，为双（向）循环链表。 2 2需求分析需求分析 2 2.1.1 程序功能说明程序
5、功能说明 链表是线性表的链式表示，由于它不要求逻辑上相邻的元素在物理位置上也相邻，所以它没有 顺序存储结构在做插入删除操作时需要移动大量元素的弱点。 双链表的结点中有两个指针域， 一 个指向直接后继， 一个指向直接前驱。本程序包括了的功能有：查找、插入、删除。 2 在单循环链表中，虽然从任一单元出发，可以找到其前驱单元，但需要O(n)时间。如果我们希 望能快速确定表中任一个元素的前驱和后继元素所在的单元，可以在链表的每个单元中设置两个指 针，一个指向后继，另一个指向前驱，形成如图 2.1 所示的双向链表或简称为双链表。 图 2.1 双链表示意图 由于在双链表中可以直接确定一个单元的前驱单元和后
6、继单元，我们可以用一种更自然的方式 表示元素的位置，即用指向双链表中第 i 个单元而不是指向其前一个单元的指针来表示表的第 i 个 位置。 双链表的单元类型定义如下： Type struct DuLNode Elemtype data; Struct DuLNode *prior; Struct DuLNode *next; DuLNode,*DuLinkList; 2 2.2.2 输入输出输入输出 由于本程序为演示程序，需用户控制程序操作。输出方面主要是显示：经指针移动所变化后得 到的另一组新的元素。输入方面：运用双向循环链表，这样子较优与普通的双向链表，省去一个表 尾的指针，使查询代码更加清晰，程序也更加简介。. 3 3. .程序流程图程序流程图 3 3. .1 1 创建双创建双向链表向链表 如图 3.1 所示 建
