1、 课程设计说明书 题 目： 双向循环链表 基于邻接表的 图的实现 课 程： 数据结构课程设计 院 （部）： 计算机科学与技术 专 业： 计算机科学与技术 班 级： 学生姓名： 学 号： 指导教师： 完成日期： I 目 录 课程设计任务书 . 错误 !未定义书签。 课程设计任务书 . II 双向循环链表 的实现 . 2 一、问题描述 . 2 二、数据结构 . 4 三、逻辑设计 . 5 四、编码 . 7 五、测试数据 . 9 六、测试情况 . 11 基于邻接表的图 的实现 . 12 一、问题描述 . 12 二、数据结构 . 12 三、逻辑设计 . 14 四、编码 . 15 五、测试数据 . 16
2、六、测试情况 . 16 结 论 . 17 参考文献 . 18 课程设计指导教师评语 . 19 I 课程设计任务书 I 设计题目 双向循环链表的实现 已知技术参数和设计要求 1. 建立一个空表。 2. 向里插入新的元素。 3. 输出双向循环链表的元素以及其 size 4. 返回索引为 i的元素。 5. 返回元素 x 第一次出现在双向循环链表中的索引 6. 删除索引为 i的元素。 7. 按从左到右或者从右到左的顺序输出元素 设计内容与步骤 1、 设计存储结构 2、 设计算法 3、 编写程序，进行调试 4、 总结并进行讲解 设计工作计划与进度安排 2016.7.9-7.12 写代码 2016.7.1
3、3-7.14 完成课程设计说明书以及相关 ppt 设计考核要求 1、 考勤 20% 2、 课程设计说明书 40% 3、 成果展示 40% II 课程设计任务书 II 设计题目 基于邻接表的图的实现 (insertEdge) 已知技术参数和设计要求 1、 建立一棵空表 2、 输出图的顶点数 3、 输出图的边数 4、 判断是否是有向图 5、 判断是否是加权图 6、 检查边是否存在 7、 插入边 8、 输出顶点的度，只用于无向图 9、 输出顶点的入度和出度 设计内容与步骤 1、 设计存储结构 2、 设计算法 3、 编写程序，进行调试 4、 总结并进行演示、讲解 设计工作计划与进度安排 2016.7.
4、9-7.12 写代码 2016.7.13-7.14 完成课程设计说明书以及相关 ppt 设计考核要求 1、 考勤 20% 2、 课程设计说明书 40% 3、 成果展示 40% 指导教师（签字）： 教研室主任（签字）：3 双向 循环链表的实现 一、问题描述 用图示的方法描述所处理的双向循环链表的 建立 ， 以 及插入删除操作前后链表的状态 1.只有有头节点的双向循环链表 2.有头节点的双向循环链表 3.双向循环链表的插入 headerNode a3 a1 a0 HeaderNode a4 ai-1 ai q p 4 4.双向循环链表的删除 二、数据结构 template struct chain
5、Node / data members T element; chainNode *right; chainNode *left; / methods chainNode() left=NULL; right=NULL; chainNode(const T left=NULL; right=NULL; chainNode(const T this-left = left; this-right = right; deleteNode p 5 ; 三、逻辑设计 1、总体思路 (1)存储结构 基于邻接表，继承 linerlist 类，具体实现双向循环链表的存储 (2)基本函数 双向循环链表的插入，
6、删除 2、模块划分 (图示的方法 ) (1)erase（删除） Yes No Yes 开始 checkIndex(theIndex) p = headerNode;i=0; iright； i+； p-right= deleteNode -right; deleteNode-right-left=p; listSize-; delete deleteNode; 结束 6 (2)insert（插入） No Yes No Yes 开始 theIndexlistSize p=headerNode;i=0; coutright q=new chainNode(theElement) q-right=p
7、-right; q-left=p; p-right=q; q-right-left=q; listSize+ 结束 7 4、 函数或类的具体定义和功能 bool empty() const return listSize = 0;/是否为空 int size() const return listSize; T int indexOf(const T void erase(int theIndex); void insert(int theIndex, const T void right_output(ostream void left_output(ostream 四、编码 templat
8、e void doublechain:checkIndex(int theIndex) const / Verify that theIndex is between 0 and listSize - 1. if (theIndex = listSize) ostringstream s; s T if(theIndex=listSize) T a=0; return a; / move to desired node chainNode* currentNode = headerNode-right; for (int i = 0; i right; return currentNode-e
9、lement; 8 template int doublechain:indexOf(const T int index = -1; / 当 前节点的索引 while (+index element != theElement) / move to next node currentNode = currentNode-right; / make sure we found matching element if (index = listSize) return -1; else return index; template void doublechain:erase(int theInd
10、ex) / Delete the element whose index is theIndex. / Throw illegalIndex exception if no such element. /checkIndex(theIndex); if (theIndex listSize) cout* deleteNode; chainNode* p = headerNode; for (int i = 0; i right; deleteNode = p-right; p-right=deleteNode-right; deleteNode-right-left=p; listSize-; delete deleteNode; template
