数据结构课程设计-- 循环单链表.doc

信息科学与技术学院数据结构课程设计报告题目名称： 循环单链表(附加头结点，引用)专业班级：计算机科学与技术2011级1班学生姓名：张峻学生学号：2011508004指导教师：高攀 目 录1 课程设计的目的11.1 课程设计的目的11.2 课程设计的题目11.3 题目要求12 概要设计12.1 存储结构12.2 基本操作13 详细设计23.1 流程图23.2 源程序74 测试125 课程设计总结196参考书目：201 课程设计的目的1.1 课程设计的目的更好的掌握数据结构这门课程，会用数据结构的基本思想及算法解决实际问题。更好的掌握循环链表，能进行各种基本的操作，提高编程能力。1.2 课程设计的题目循环单链表(附加头结点，引用)1.3 题目要求实现附加头结点循环单链表的基本操作：创建空表、输出、求表长、取元素、查找、替换、插入、删除、清空。2 概要设计2.1 存储结构存储结构Ldatanextdatanextdatanextdatanext空闲typedef struct nodedatatype data;/*数据域*/struct node *next;/*指针域*/LNode,*LinkList;/*结点及结点的地址*/ 2.2 基本操作创建空表、输出、求表长、取元素、查找、替换、插入、删除、清空。3 详细设计3.1 流程图各个算法的设计如下：1. 主函数： 开始结束调用菜单Menu()利用头插法将数组中数据插入打链表创建空循环链表 2. 主菜单用于进行指示进行各种操作，是与每个函数都相联系的一个函数结束开始输入xz菜单退出清空删除插入替换查找求表长显示数据取元素3.显示链表先让指针指向首元结点，在判断该指针是否为头指针，不是则输入数据，实则退出开始p=head-next;p = head-next;否while(p!= head)是coutdata;p = p-next;结束 图34.求表长先求表的初始长，在判断链表是否为空，不是则len自加，否则结束p=head;int i,len = ListLen(head)判断链表是否为空结束+len;p=p-next;开始 是 否5. 取元素 是 否 先求表长，在判断Index len，为否则循环，一直活得该数据开始p = headIndex lenfor(i = 0; i next);获取该数据结束6. 查找开始 是 否 否 是 是求表长，在判断链表是否为空，是则结束，否则判断要查找的数据是否在链表中，是则成功结束p = p-nextif(p-next-data= data)判断链表是否为空p=head;int i,len = ListLen(head)7.替换判断要替换的位置是否在链表范围中，是则循环找到要替换的数据替换，否则结束 是 否 开始p=head;int i,len = ListLen(head)Index lenfor(i = 0; i next);p-data=data结束8.插入判断将要插入的位置是否在链表范围内，是则循环将要插入的数据插入，否则结束 是 否开始p=head;int i,len = ListLen(head)Index lenfor(i=1;inext);插入数据结束9.删除判断链表是否为空，否则删除该结点，是则结束 是 否 否 是开始p = head判断链表是否为空p-next-data = data删除该结点结束10. 清空判断聊表是够为空，否则依次释放空间，否则结束 是 否开始p = headp-next-data = data判断链表是否为空依次释放空间结束3.2 源程序#include using namespace std;typedef int ElemType;typedef struct nodeElemType data;struct node *next;LNode,*LinkList,*pNODE;/ 创建一个有头结点的空循环表。LinkList InitList(void) pNODE head = new LNode; head-next = head;return head;/ 头插法。将给定结点插在链表头部。void InsertHead(LinkList head,pNODE anode) anode-next = head-next; head-next = anode;/ 返回链表长度。int ListLen(LinkList head) int len = 0;pNODE p = head;while(p-next != head) +len; p = p-next; return len;/ 查找。成功返回1，否则返回0。int ListSearch(LinkList head, ElemType data) pNODE p = head; while(p-next != head) if(p-next-data = data) return true; p = p-next; return 0;/ 获取指定索引号的数据。void GetData(LinkList head,int Index,ElemType data) pNODE p = head; int i,len = ListLen(head); if(Index len) cout 获取失败 endl; for(i = 0; i next); data = p-data; cout 获取成功，其值为：data endl;/ 用给定结点替换指定索引的结点。void NodeReplace(LinkList head, int Index, int data) pNODE p = head; int i,len = ListLen(head); if(Index len) cout 错误 endl; for(i = 0; i next); p-data=data; cout 替换成功 endl; /插入结点void ListInsert(LinkList head,int Index,int data)pNODE s,p=head;int i,len = ListLen(head); if(Index len) cout 错误 endl;for(i=1;inext);s=new LNode;s-data=data;s-next=p-next;p-next=s;cout 插入成功 next != head) if(p-next-data = data) q = p-next; p-next = q-next;delete q;return 1; p = p-next; return 0;/ 释放链表void ListDestroy(LinkList head) pNODE q,p = head;while(p-next != head)q = p-next;p-next = q-next;delete q; delete head;cout 释放成功 next; while(p != head) cout data; p = p-next; cout endl;void Menu(LinkList head)cout *循环链表* endl;cout * endl;cout *1显示链表2求表长3取元素4查找5替换6插入7删除8清空9退出* endl;cout * endl;cout请选择您需要的操作：xz;switch(xz) case 1: ListShow(head); system(pause); system(cls); Menu(head); break; case 2: cout 链表长度为： ListLen(head) endl; system(pause); system(cls); Menu(head); break; case 3: cout 请输入要获取的数据的位置： Index; GetData(head,Index,data); system(pause); system(cls); Menu(head); break; case 4: cout 请输入要查找的数据 : data; if(ListSearch(head, data) cout 找到了 endl; else cout 对不起，没找到 data endl; system(pause); system(cls); Menu(head); break; case 5: cout 请输入要替换的位置，其值为： Index data; NodeReplace(head,Index,data); system(pause); system(cls); Menu(head); break; case 6: cout 请输入插入的位置及数值： Index data; ListInsert(head,Index,data); system(pause); system(cls); Menu(head); break;case 7: cout 请输入要删除结点的数据 : data; if(NodeErase(head,data) cout 成功删除 data endl; else cout 没有找到 data endl; system(pause); system(cls); Menu(head); break; case 8: ListDestroy(head); system(pause); system(cls); Menu(head); break; case 0: exit(1);int main() LinkList head = InitList();pNODE anode;int i,n = 10,a = 0,1,2,3,4,5,6,7,8,9;for(i = 0; i data = ai;InsertHead(head,anode); Menu(head);return 0; 4 测试菜单界面 显示各种功能需进行的各种操作，界面如下：选择1时，显示链表中的数据，如图：选择2时，可以得到链表长度，如图：选择3时，输入要获取的数据的位置，成功则如图：选择4时，可以查找元素是否在该链表中，但该功能不能显示出查找到的数据的位置，有所不足，如图：选择5时，可以替换你指定位置的数据，如图：选择1，显示替换指定位置数据后链表中的所有数据，如图：选择6时，可以选择要插入的位置及数值，插入成功，如图：选择1，插入后，链表中所有的数据，如图：选择7时，可以删除你要删除的数据，成功删除则如图：选择7，删除失败，如图：选择8时，可以清空链表，如图：5 课程设计总结通过这次课程设计,我又收获到很多,平时的在做作业时,因为题形与结构都是很简单的,并且每一章的内容都是有相应的例题可以参考,所以在做题时没有遇到过很麻烦的问题,而这次不同了,一个课题拿到手时,给我的感觉是无从下手,而且要求很多,使得题目要求更大了.通过本次课程设计，我最大的收获就是自己的动手能力得到了很大的提升，我发现只有自己动手才能更好的了解到自己的知识漏洞，很多小问题可能对代码的编写都有很大影响，像在编写过程中我有时漏掉半撇括号，而在查找时就相当费力，所以多敲代码很重要啊。对语言也得到了更深的了解。语言等于算法加数据结构，这句话确实很有道理，数据结构给了我一种更好的思路，一种更好的思想，掌握一种思想远比会很多语言来的重要，只有我们有了思路，有了更好的算法，我们的程序才会更加优秀，空间复杂度，时间复杂度才