《数据结构课程设计循环单链表》由会员分享,可在线阅读,更多相关《数据结构课程设计循环单链表(22页珍藏版)》请在金锄头文库上搜索。
1、信息科学与技术学院数据结构课程设计报告题目名称: 循环单链表(附加头结点,引用)专业班级:计算机科学与技术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 课程设计的
2、题目循环单链表(附加头结点,引用)1.3 题目要求实现附加头结点循环单链表的基本操作:创建空表、输出、求表长、取元素、查找、替换、插入、删除、清空。2 概要设计2.1 存储结构存储结构Ldatanextdatanextdatanextdatanext空闲typedef struct nodedatatype data;/*数据域*/struct node *next;/*指针域*/LNode,*LinkList;/*结点及结点的地址*/ 2.2 基本操作创建空表、输出、求表长、取元素、查找、替换、插入、删除、清空。3 详细设计3.1 流程图各个算法的设计如下:1. 主函数: 开始结束调用菜单M
3、enu()利用头插法将数组中数据插入打链表创建空循环链表 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;开
4、始 是 否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
5、)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判断链表是否为空依次释放空间
6、结束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 =
7、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;
8、/ 获取指定索引号的数据。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 = ListL
9、en(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 插入成功 endl;/ 删除数据域为data的结点。成功返回1,否则返回0。int NodeErase(Lin