數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-- 循環(huán)單鏈表

1、精品文檔信息科學與技術(shù)學院?數(shù)據(jù)結(jié)構(gòu)?課程設(shè)計報告題目名稱： 循環(huán)單鏈表(附加頭結(jié)點，引用)專業(yè)班級：計算機科學與技術(shù)2021級1班學生姓名：張峻學生學號：2021508004指導(dǎo)教師：高攀 歡迎下載精品文檔目 錄1 課程設(shè)計的目的11.1 課程設(shè)計的目的11.2 課程設(shè)計的題目11.3 題目要求12 概要設(shè)計12.1 存儲結(jié)構(gòu)12.2 根本操作13 詳細設(shè)計23.1 流程圖23.2 源程序74 測試125 課程設(shè)計總結(jié)196參考書目：20歡迎下載精品文檔1 課程設(shè)計的目的1.1 課程設(shè)計的目的更好的掌握數(shù)據(jù)結(jié)構(gòu)這門課程，會用數(shù)據(jù)結(jié)構(gòu)的根本思想及算法解決實際問題。更好的掌握循環(huán)鏈表，能進行各種

2、根本的操作，提高編程能力。1.2 課程設(shè)計的題目循環(huán)單鏈表(附加頭結(jié)點，引用)1.3 題目要求實現(xiàn)附加頭結(jié)點循環(huán)單鏈表的根本操作：創(chuàng)立空表、輸出、求表長、取元素、查找、替換、插入、刪除、清空。2 概要設(shè)計2.1 存儲結(jié)構(gòu)存儲結(jié)構(gòu)Ldatanextdatanextdatanextdatanext空閑typedef struct nodedatatype data;/*數(shù)據(jù)域*/struct node *next;/*指針域*/LNode,*LinkList;/*結(jié)點及結(jié)點的地址*/ 2.2 根本操作創(chuàng)立空表、輸出、求表長、取元素、查找、替換、插入、刪除、清空。3 詳細設(shè)計3.1 流程圖各個算法的

3、設(shè)計如下：1. 主函數(shù)： 開始結(jié)束調(diào)用菜單Menu()利用頭插法將數(shù)組中數(shù)據(jù)插入打鏈表創(chuàng)立空循環(huán)鏈表 2. 主菜單用于進行指示進行各種操作，是與每個函數(shù)都相聯(lián)系的一個函數(shù)結(jié)束開始輸入xz菜單退出清空刪除插入替換查找求表長顯示數(shù)據(jù)取元素3.顯示鏈表先讓指針指向首元結(jié)點，在判斷該指針是否為頭指針，不是那么輸入數(shù)據(jù)，實那么退出開始p=head->next;p = head->next;否while(p!= head)是cout<<p->data;p = p->next;結(jié)束 圖34.求表長先求表的初始長，在判斷鏈表是否為空，不是那么len自加，否那么結(jié)束p=hea

4、d;int i,len = ListLen(head)判斷鏈表是否為空結(jié)束+len;p=p->next;開始 是 否5. 取元素 是 否 先求表長，在判斷Index < 1 | Index > len，為否那么循環(huán)，一直活得該數(shù)據(jù)開始p = headIndex < 1 | Index > lenfor(i = 0; i <Index; +i,p = p->next);獲取該數(shù)據(jù)結(jié)束6. 查找開始 是 否 否 是 是求表長，在判斷鏈表是否為空，是那么結(jié)束，否那么判斷要查找的數(shù)據(jù)是否在鏈表中，是那么成功結(jié)束p = p->nextif(p->ne

5、xt->data= data)判斷鏈表是否為空p=head;int i,len = ListLen(head)7.替換判斷要替換的位置是否在鏈表范圍中，是那么循環(huán)找到要替換的數(shù)據(jù)替換，否那么結(jié)束 是 否 開始p=head;int i,len = ListLen(head)Index < 1 | Index > lenfor(i = 0; i <Index; +i,p = p->next);p->data=data結(jié)束8.插入判斷將要插入的位置是否在鏈表范圍內(nèi)，是那么循環(huán)將要插入的數(shù)據(jù)插入，否那么結(jié)束 是 否開始p=head;int i,len = ListL

6、en(head)Index < 1 | Index > lenfor(i=1;i<Index;+i,p=p->next);插入數(shù)據(jù)結(jié)束9.刪除判斷鏈表是否為空，否那么刪除該結(jié)點，是那么結(jié)束 是 否 否 是開始p = head判斷鏈表是否為空p->next->data = data刪除該結(jié)點結(jié)束10. 清空判斷聊表是夠為空，否那么依次釋放空間，否那么結(jié)束 是 否開始p = headp->next->data = data判斷鏈表是否為空依次釋放空間結(jié)束3.2 源程序#include <iostream>using namespace s

7、td;typedef int ElemType;typedef struct nodeElemType data;struct node *next;LNode,*LinkList,*pNODE;/ 創(chuàng)立一個有頭結(jié)點的空循環(huán)表。LinkList InitList(void) pNODE head = new LNode; head->next = head;return head;/ 頭插法。將給定結(jié)點插在鏈表頭部。void InsertHead(LinkList head,pNODE anode) anode->next = head->next; head->nex

8、t = 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; ret

9、urn 0;/ 獲取指定索引號的數(shù)據(jù)。void GetData(LinkList head,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 <<"獲取成功，其值為："<<dat

10、a <<endl;/ 用給定結(jié)點替換指定索引的結(jié)點。void NodeReplace(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 <<"替換成功" <&

11、lt;endl; /插入結(jié)點void ListInsert(LinkList head,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 <<"插入

12、成功" <<endl;/ 刪除數(shù)據(jù)域為data的結(jié)點。成功返回1，否那么返回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

13、= head;while(p->next != head)q = p->next;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 Me

14、nu(LinkList head)cout <<"*循環(huán)鏈表*" <<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

15、(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 <<"請輸入要獲取的數(shù)據(jù)的位置：" <&l

16、t;endl; cin >>Index; GetData(head,Index,data); system("pause"); system("cls"); Menu(head); break; case 4: cout <<"請輸入要查找的數(shù)據(jù) : " <<endl; cin >>data; if(ListSearch(head, data) cout <<"找到了" <<endl; else cout <<"對不起，沒

17、找到" <<data <<endl; system("pause"); system("cls"); Menu(head); break; case 5: cout <<"請輸入要替換的位置，其值為：" <<endl; cin >>Index >>data; NodeReplace(head,Index,data); system("pause"); system("cls"); Menu(head); break

18、; case 6: cout <<"請輸入插入的位置及數(shù)值：" <<endl; cin >>Index >>data; ListInsert(head,Index,data); system("pause"); system("cls"); Menu(head); break;case 7: cout <<"請輸入要刪除結(jié)點的數(shù)據(jù) : " <<endl; cin >>data; if(NodeErase(head,data) cou

19、t <<"成功刪除" <<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)

20、;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 < n; +i) / 頭插法 anode =new LNode;anode->data = ai;InsertHead(head,anode); Menu(head);return 0; 4 測試菜單界面 顯示各種功能需進行的各種操作，界面如下：選擇1時，顯示鏈表中的數(shù)據(jù)，如圖：選擇2時，可以得到鏈表長度，如圖：選擇3時，輸入要獲取的數(shù)據(jù)的位置，成功那么如圖：選擇4時，可以查找元素是否在該鏈表中，但該功能不能顯示出查找到的數(shù)據(jù)的位置，有所缺乏，如圖：選擇5時，可以替換你指定位置的數(shù)據(jù)，如圖：選擇1，顯示替換指定位置數(shù)據(jù)后鏈表中的所有數(shù)據(jù)，如圖：選擇6時，可以選擇要插入的位置及數(shù)值，插入成功，如圖：選擇1，插入后，鏈表中所有的數(shù)據(jù)