双向循环链表基于邻接表的图的实现-数据结构课程设计说明书

课程设计说明书题 目： 双向循环链表 基于邻接表的图的实现 课 程： 数据结构课程设计院 （部）： 计算机科学与技术专 业： 计算机科学与技术班 级： 学生姓名： 学 号： 指导教师： 完成日期： 目 录课程设计任务书I 课程设计任务书II双向循环链表的实现3一、问题描述3二、数据结构4三、逻辑设计5四、编码7五、测试数据9六、测试情况11基于邻接表的图的实现12一、问题描述12二、数据结构13三、逻辑设计13四、编码15五、测试数据16六、测试情况16结 论17参考文献18课程设计指导教师评语19I课程设计任务书I设计题目双向循环链表的实现已知技术参数和设计要求1. 建立一个空表。2. 向里插入新的元素。3. 输出双向循环链表的元素以及其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、 输出图的边数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. 只有有头节点的双向循环链表headerNode 2. 有头节点的双向循环链表 a4HeaderNode a0 a1 a3p3. 双向循环链表的插入 ai-1 aiq 34. 双向循环链表的删除deleteNodep二、数据结构template struct chainNode / data members T element; chainNode *right; chainNode *left; / methods chainNode() left=NULL; right=NULL; chainNode(const T& element) this-element = element; left=NULL; right=NULL; chainNode(const T& 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-right-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、 函数或类的具体定义和功能bool empty() const return listSize = 0;/是否为空 int size() const return listSize;T& get(int theIndex) const; int indexOf(const T& theElement) const; void erase(int theIndex); void insert(int theIndex, const T& theElement); void right_output(ostream& out) const; void left_output(ostream& out) const;四、编码templatevoid doublechain:checkIndex(int theIndex) const/ Verify that theIndex is between 0 and listSize - 1. if (theIndex = listSize) ostringstream s; s index = theIndex size = listSize; throw illegalIndex(s.str(); templateT& doublechain:get(int theIndex) const/ 返回索引为theIndex的元素./checkIndex(theIndex);if(theIndex=listSize) T a=0;return a; / move to desired node chainNode* currentNode = headerNode-right; for (int i = 0; i right; return currentNode-element;7templateint doublechain:indexOf(const T& theElement) const/ 返回元素theElement首次出现时的索引. / Return -1 if theElement not in list. chainNode* currentNode = headerNode-right; 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;templatevoid doublechain:erase(int theIndex)/ Delete the element whose index is theIndex. / Throw illegalIndex exception if no such element. /checkIndex(theIndex);if (theIndex listSize) cout元素不存在endl; return; / valid index, locate node with element to delete chainNode* deleteNode; chainNode* p = headerNode; for (int i = 0; i right; deleteNode = p-right; p-right=deleteNode-right; deleteNode-right-left=p; listSize-; delete deleteNode;template8void doublechain:insert(int theIndex, const T& 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(); chainNode* q= new chainNode(theElement); chainNode* p = headerNode; for (int i = 0; i right; q-right=p-right; q-left=p; p-right=q; q-right-left=q; listSize+;templatevoid doublechain:right_output(ostream& out) const/ Put the list into the stream out.chainNode* currentNode = headerNode-right;for (int i = 0;i listSize;i+)out element right;templatevoid doublechain:left_output(ostream& out) const/ Put the list into the stream out.chainNode* currentNode = headerNode-left;for (int i = 0;i listSize;i+)out element left;五、测试数据1、对每个函数的测试数据(1)新建一个链表y.insert(0, 2);9 y.insert(1, 6); y.insert(0, 1); y.insert(2, 4); y.insert(3, 5); y.insert(2, 3);insert的异常测试y.insert(7,4);(2)删除元素异常条件测试y.erase(7);正常条件测试y.erase(1);y.erase(0);y.erase(2);边缘条件测试(将剩余的元素删除)y.erase(0);y.erase(0);y.erase(0);2、对程序整体的测试数据(1)判断链表是否为空y.empty();(2)测试链表长度y.size();(3)通过索引查找值y.get(-1);y.get(3);(4)通过值查找索引y.indexOf(7);y.indexOf(4);10六、测试情况1.新建一个链表2. 测试indexOf3.测试get4测试erase5. 插入（insert）（theIndexlistSize）11基于邻接表的图的实现(insertEdge)一、 问题描述邻接表的形态aList weighted0elementListListListListListList110weightedelementweightedelement20weightedelement0weightedelement0weightedelement0weightedelement图42313221412插入一条边21321243451二数据结构template struct wEdge/ vertex and weight pair int vertex; T weight; wEdge(int theVertex = 0, T theWeight = 0) vertex = theVertex; weight = theWeight; operator int() const return vertex;三、逻辑设计1.基本函数图的边插入2.模块划分(1)插入一条边13开始existsEdge(v1,v2)v1=theEdge-vertex1();v2=theEdge-vertex2();开NoaListv1.push_back( wEdge(v2, theEdge-weight() ); aListv2.push_back( wEdge(v1, theEdge-weight() ); e+;Yes结束3、函数或类的具体定义和功能int numberOfVertices() const;/返回图的顶点数 int numberOfEdges() const;/返回图的边数 bool existsEdge(int, int) const;/if 边（ ,）存在，返回true，否则返回false void insertEdge(edge *theEdge);/插入边（i，j） void eraseEdge(int, int);/删除边 int degree(int) const;/返回顶点的度，只用于无向图 int inDegree(int) const;/返回顶点的入度 int outDegree(int) const;/返回顶点的出度 bool directed() const;/有向图 bool weighted() const;/加权图 void checkVertex(int theVertex) const; void output(ostream& out) const;144、 编码templateint graph:numberOfVertices() constreturn n;templateint graph:numberOfEdges() constreturn e;templatebool graph:directed() constreturn false;templatebool graph:weighted() constreturn true;templatevoid graph:insertEdge(edge *theEdge) int v1 = theEdge-vertex1(); int v2 = theEdge-vertex2(); if ( existsEdge(v1,v2) ) return; aListv1.push_back( wEdge(v2, theEdge-weight() );