《双向循环链表基于邻接表的图的实现-数据结构课程设计说明书》由会员分享，可在线阅读，更多相关《双向循环链表基于邻接表的图的实现-数据结构课程设计说明书（20页珍藏版）》请在金锄头文库上搜索。
1、课程设计说明书题 目： 双向循环链表基于邻接表的图的实现课 程： 数据结构课程设计院 （部）： 计算机科学与技术专 业： 计算机科学与技术班 级：学生姓名：学 号：指导教师：完成日期：目 录课程设计任务书I课程设计任务书II双向循环链表的实现3一、问题描述3二、数据结构4三、逻辑设计5四、编码7五、测试数据9六、测试情况11基于邻接表的图的实现12一、问题描述12二、数据结构13三、逻辑设计13四、编码15五、测试数据16六、测试情况16结 论17参考文献18课程设计指导教师评语19I课程设计任务书I设计题目双向循环链表的实现已知技术参数和设计要求1. 建立一个空表。2. 向里插入新的元素。3
2、. 输出双向循环链表的元素以及其size4. 返回索引为i的元素。5. 返回元素x第一次出现在双向循环链表中的索引6. 删除索引为i的元素。7. 按从左到右或者从右到左的顺序输出元素设计内容与步骤1、 设计存储结构2、 设计算法3、 编写程序，进行调试4、 总结并进行讲解设计工作计划与进度安排2016.7.9-7.12写代码2016.7.13-7.14 完成课程设计说明书以及相关ppt设计考核要求1、 考勤20%2、 课程设计说明书40%3、 成果展示40%I课程设计任务书II设计题目基于邻接表的图的实现(insertEdge)已知技术参数和设计要求1、 建立一棵空表2、 输出图的顶点数3、
3、输出图的边数4、 判断是否是有向图5、 判断是否是加权图6、 检查边是否存在7、 插入边8、 输出顶点的度，只用于无向图9、 输出顶点的入度和出度设计内容与步骤1、 设计存储结构2、 设计算法3、 编写程序，进行调试4、 总结并进行演示、讲解设计工作计划与进度安排2016.7.9-7.12写代码2016.7.13-7.14完成课程设计说明书以及相关ppt设计考核要求1、 考勤20%2、 课程设计说明书40%3、 成果展示40%指导教师（签字）： 教研室主任（签字）：II双向循环链表的实现一、问题描述用图示的方法描述所处理的双向循环链表的建立，以及插入删除操作前后链表的状态1. 只有有头节点的双
4、向循环链表headerNode2. 有头节点的双向循环链表 a4HeaderNode a0 a1 a3p3. 双向循环链表的插入 ai-1 aiq34. 双向循环链表的删除deleteNodep二、数据结构template structchainNode/ data membersTelement;chainNode *right;chainNode *left;/ methodschainNode() left=NULL;right=NULL; chainNode(constT& element) this-element = element;left=NULL;right=NULL; ch
5、ainNode(constT& element,chainNode * left,chainNode* right) this-element = element;this-left = left;this-right = right; 4;三、逻辑设计1、总体思路(1)存储结构基于邻接表，继承linerlist类，具体实现双向循环链表的存储(2)基本函数双向循环链表的插入，删除2、模块划分(图示的方法)(1)erase（删除）开始checkIndex(theIndex) Yesp = headerNode;i=0;iright= deleteNode -right;deleteNode-ri
6、ght-left=p;listSize-;delete deleteNode;p=p-right；i+； Yes结束5(2)insert（插入）开始theIndexlistSizeNoYescout”无效索引”endl;p=headerNode;i=0;itheIndexNoq=new chainNode(theElement)q-right=p-right;q-left=p;p-right=q;q-right-left=q;listSize+Yesp=p-right结束64、 函数或类的具体定义和功能boolempty() const returnlistSize = 0;/是否为空ints
7、ize() const returnlistSize;T& get(int theIndex) const;intindexOf(constT& theElement) const;voiderase(int theIndex);voidinsert(int theIndex, constT& theElement);voidright_output(ostream& out) const;voidleft_output(ostream& out) const;四、编码templatevoiddoublechain:checkIndex(int theIndex) const/ Verify
8、that theIndex is between 0 and listSize - 1.if (theIndex = listSize) ostringstream s; s index = theIndex size = listSize;throwillegalIndex(s.str(); templateT& doublechain:get(int theIndex) const/ 返回索引为theIndex的元素./checkIndex(theIndex);if(theIndex=listSize)T a=0;return a;/ move to desired nodechainNo
9、de* currentNode = headerNode-right;for (int i = 0; i right;return currentNode-element;7templateintdoublechain:indexOf(constT& theElement) const/ 返回元素theElement首次出现时的索引./ Return -1 if theElement not in list.chainNode* currentNode = headerNode-right;int index = -1; / 当前节点的索引while (+index element != th
10、eElement) / move to next node currentNode = currentNode-right; / make sure we found matching elementif (index = listSize)return -1;elsereturn index;templatevoiddoublechain:erase(int theIndex)/ Delete the element whose index is theIndex./ Throw illegalIndex exception if no such element./checkIndex(th
11、eIndex);if (theIndex listSize) cout元素不存在endl;return; / valid index, locate node with element to deletechainNode* deleteNode;chainNode* p = headerNode;for (int i = 0; i right; deleteNode = p-right; p-right=deleteNode-right; deleteNode-right-left=p;listSize-;delete deleteNode;template8voiddoublechain:insert(int theIndex, constT& theElement)/ Insert theElement so that its index is theIndex.if (theIndex listSize) coutInsert index must be between 0 to listSizeendl;/ostringstream s;/s index = theIndex size = listSize;/throw illegalIndex(s.str();
