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

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. 主函数： 开始结束调用菜单Menu

3、()利用头插法将数组中数据插入打链表创建空循环链表2. 主菜单用于进行指示进行各种操作，是与每个函数都相联系的一个函数结束开始输入xz菜单退出清空删除插入替换查找求表长显示数据取元素3.显示链表先让指针指向首元结点，在判断该指针是否为头指针，不是则输入数据，实则退出开始p=head->next;p = head->next;否while(p!= head)是cout<<p->data;p = p->next;结束图34.求表长先求表的初始长，在判断链表是否为空，不是则len自加，否则结束p=head;int i,len = ListLen(head)判断链表

4、是否为空结束+len;p=p->next;开始 是 否5. 取元素 是 否 先求表长，在判断Index < 1 | Index > len，为否则循环，一直活得该数据开始p = headIndex < 1 | Index > lenfor(i = 0; i <Index; +i,p = p->next);获取该数据结束6. 查找开始 是 否 否 是 是求表长，在判断链表是否为空，是则结束，否则判断要查找的数据是否在链表中，是则成功结束p = p->nextif(p->next->data= data)判断链表是否为空p=head;in

5、t i,len = ListLen(head)7.替换判断要替换的位置是否在链表范围中，是则循环找到要替换的数据替换，否则结束 是 否 开始p=head;int i,len = ListLen(head)Index < 1 | Index > lenfor(i = 0; i <Index; +i,p = p->next);p->data=data结束8.插入判断将要插入的位置是否在链表范围内，是则循环将要插入的数据插入，否则结束 是 否开始p=head;int i,len = ListLen(head)Index < 1 | Index > lenfo

6、r(i=1;i<Index;+i,p=p->next);插入数据结束9.删除判断链表是否为空，否则删除该结点，是则结束 是 否 否 是开始p = head判断链表是否为空p->next->data = data删除该结点结束10. 清空判断聊表是够为空，否则依次释放空间，否则结束 是 否开始p = headp->next->data = data判断链表是否为空依次释放空间结束3.2 源程序#include <iostream>using namespace std;typedef int ElemType;typedef struct node

7、ElemType 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 hea

8、d) 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 hea

9、d,int Index,ElemType data) pNODE p = head; int i,len = ListLen(head); if(Index < 1 | Index > len) cout <<"获取失败" <<endl; for(i = 0; i <Index; +i,p = p->next); data = p->data; cout <<"获取成功，其值为："<<data <<endl;/ 用给定结点替换指定索引的结点。void NodeRep

10、lace(LinkList head, int Index, int data) pNODE p = head; int i,len = ListLen(head); if(Index < 1 | Index > len) cout <<"错误" <<endl; for(i = 0; i <Index; +i,p = p->next); p->data=data; cout <<"替换成功" <<endl; /插入结点void ListInsert(LinkList head,

11、int Index,int data)pNODE s,p=head;int i,len = ListLen(head); if(Index < 1 | Index > len) cout <<"错误" <<endl;for(i=1;i<Index;+i,p=p->next);s=new LNode;s->data=data;s->next=p->next;p->next=s;cout <<"插入成功" <<endl;/ 删除数据域为data的结点。成功返回1，

12、否则返回0。int NodeErase(LinkList head,ElemType data) pNODE q,p = head;while(p->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->nex

13、t;p->next = q->next;delete q; delete head;cout <<"释放成功" <<endl;/ 显示链表void ListShow(LinkList head) pNODE p = head->next; while(p != head) cout <<" "<<p->data; p = p->next; cout <<endl;void Menu(LinkList head)cout <<"*循环链表*&qu

14、ot; <<endl;cout <<"*" <<endl;cout <<"*1显示链表2求表长3取元素4查找5替换6插入7删除8清空9退出*" <<endl;cout <<"*" <<endl;cout<<"请选择您需要的操作："<<endl;int xz,Index,data;cin >>xz;switch(xz) case 1: ListShow(head); system("pau

15、se"); system("cls"); Menu(head); break; case 2: cout <<"链表长度为：" <<ListLen(head) <<endl; system("pause"); system("cls"); Menu(head); break; case 3: cout <<"请输入要获取的数据的位置：" <<endl; cin >>Index; GetData(head,Index

16、,data); system("pause"); system("cls"); Menu(head); break; case 4: cout <<"请输入要查找的数据 : " <<endl; cin >>data; if(ListSearch(head, data) cout <<"找到了" <<endl; else cout <<"对不起，没找到" <<data <<endl; system(&q

17、uot;pause"); system("cls"); Menu(head); break; case 5: cout <<"请输入要替换的位置，其值为：" <<endl; cin >>Index >>data; NodeReplace(head,Index,data); system("pause"); system("cls"); Menu(head); break; case 6: cout <<"请输入插入的位置及数值：&quo

18、t; <<endl; cin >>Index >>data; ListInsert(head,Index,data); system("pause"); system("cls"); Menu(head); break;case 7: cout <<"请输入要删除结点的数据 : " <<endl; cin >>data; if(NodeErase(head,data) cout <<"成功删除" <<data <&

19、lt;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

20、anode;int i,n = 10,a = 0,1,2,3,4,5,6,7,8,9;for(i = 0; i < n; +i) / 头插法 anode =new LNode;anode->data = ai;InsertHead(head,anode); Menu(head);return 0;4 测试菜单界面 显示各种功能需进行的各种操作，界面如下：选择1时，显示链表中的数据，如图：选择2时，可以得到链表长度，如图：选择3时，输入要获取的数据的位置，成功则如图：选择4时，可以查找元素是否在该链表中，但该功能不能显示出查找到的数据的位置，有所不足，如图：选择5时，可以替换你指定位置的数据，如图：选择1，显示替换指定位置数据后链表中的所有数据，如图：选择6时，可以选择要插入的位置及数值，插入成功，如图：选择1，插入后，链表中所有