數(shù)據(jù)結(jié)構(gòu)實驗1順序表_鏈表

1、psme淮海工學(xué)院計算機科學(xué)系實驗報告書課程名：數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)試驗題目:班級：軟件112學(xué)號：姓名：評語:成績： 指導(dǎo)教師： 批閱時間:線性表實驗報告要求1 目的與要求 :1）掌握線性表數(shù)據(jù)結(jié)構(gòu)的基本概念和抽象數(shù)據(jù)類型描述；2）熟練掌握線性表數(shù)據(jù)結(jié)構(gòu)的順序和鏈式存儲存表示；3）熟練掌握線性表順序存儲結(jié)構(gòu)的基本操作算法實現(xiàn)；4）熟練掌握線性表的鏈式存儲結(jié)構(gòu)的基本操作算法實現(xiàn);5）掌握線性表在實際問題中的應(yīng)用和基本編程技巧;6）按照實驗題目要求獨立正確地完成實驗內(nèi)容（提交程序清單及相關(guān)實驗數(shù)據(jù)與運行結(jié) 果）；7）按照報告格式和內(nèi)容要求， 認真書寫實驗報告， 并在試驗后的第三天提交電子 （全

2、班同 學(xué)提交到學(xué)委，再統(tǒng)一打包提交給老師）和紙質(zhì)（每班每次 5 份，學(xué)委安排，保證每個同學(xué)至 少提交一次） ；8）積極開展實驗組組內(nèi)交流和輔導(dǎo)，嚴禁復(fù)制和剽竊他人實驗成果，一旦發(fā)現(xiàn)嚴肅處理；9）上實驗課前，要求每個同學(xué)基本寫好程序，并存儲在自己的U 盤上，用于實驗課堂操作時調(diào)試和運行。凡不做準備，沒有提前編寫程序者，拒絕上機試驗。2 實驗內(nèi)容或題目一、順序表的基本操作實現(xiàn)實驗要求：數(shù)據(jù)元素類型 ElemType取整型int。按照順序存儲結(jié)構(gòu)實現(xiàn)如下算法：1）創(chuàng)建任意整數(shù)線性表 （即線性表的元素值隨機在鍵盤上輸入） 的順序存儲結(jié)構(gòu) （即順序表）長度限定在 25 之內(nèi)；2）打印 /顯示（遍歷）該線

3、性表（依次打印 /顯示出表中元素值） ；3）在順序表中查找第 i 個元素，并返回其值；4）在順序表第 i 個元素之前插入一已知元素；5）在順序表中刪除第 i 個元素；6）求順序表中所有元素值（整數(shù)）之和；二、鏈表（帶頭結(jié)點）基本操作實驗要求：數(shù)據(jù)元素類型 ElemType取字符型char。按照動態(tài)單鏈表結(jié)構(gòu)實現(xiàn)如下算法：1） 按照頭插法或尾插法創(chuàng)建一個帶頭結(jié)點的字符型單鏈表（鏈表的字符元素從鍵盤輸入），長度限定在 10 之內(nèi)；2） 打?。ū闅v）該鏈表（依次打印出表中元素值，注意字符的輸入順序與鏈表的結(jié)點順序）；3） 在鏈表中查找第 i 個元素， i 合法返回元素值，否則，返回FALSE；4）

4、在鏈表中查找與一已知字符相同的第一個結(jié)點，有則返回TRUE ，否則，返回 FALSE ；5）在鏈表中第 i 個結(jié)點之前插入一個新結(jié)點；6）在線性表中刪除第 i 個結(jié)點；7) 計算鏈表的長度。3 實驗步驟與源程序#include #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#define MAXSIZE 25 /* 此處的宏定義常量表示線性表可能達到的最大長度 */ using namespace std;typedef struct，空表ElemType elemMAXSIZE; /*

5、線性表占用的數(shù)組空間 */int last; /* 記錄線性表中最后一個元素在數(shù)組elem 中的位置(下標值)置為 -1*/SeqList;void OutputSeqList(SeqList *L)cout 順序表如下： endl;int i; for(i=0;ilast;i+)coutelemin;coutendl;int GetDate(SeqList *L)int t;cout 請輸入要查找的元素的序數(shù)： t;if( tL-last)coutelemt-1);int InsList(SeqList *L)int i,e;cout 請輸入要插入的元素插入位置及要插入的元素 ie;int

6、k;if(iL-last+2) /* 首先判斷插入位置是否合法 */printf( 插入位置 i 值不合法 );return(ERROR);if(L-last= MAXSIZE-1)printf( 表已滿無法插入 );return(ERROR);for(k=L-last;k=i-1;k-) /* 為插入元素而移動位置 */ L-elemk+1=L-elemk;L-elemi-1=e; /* 在 C 語言數(shù)組中，第 i 個元素的下標為 i-1*/ L-last+;return(OK);int DelList(SeqList *L,ElemType *m)int w;cout 請輸出要刪除的元素位

7、置： w;int k;if(wL-last+1)cout 刪除位置不合法 !elemw-1; /* 將刪除的元素存放到 e 所指向的變量中 */ for(k=w; klast; k+)L-elemk-1 = L-elemk; /*將后面的元素依次前移 */L-last-;return(OK);int sum(SeqList *L)int i,n=0;for(i=0;ilast+1;i+) n=n+L-elemi;return(n);void main()int *q,n;SeqList *L;L=(SeqList*)malloc(sizeof(SeqList);q = (int*)malloc

8、(sizeof(int);coutn;L-last=n-1;cout 請輸入順序表： endl;int i;for(i=0;iL-elemi;char c=y;while(c!=n)cout 請選擇你要進行的操作： endl;刪除元cout1. 輸出順序表； n2. 查找元素； n3. 插入元素； n4. 素； n5. 求和 xuanze;switch(xuanze)case 1:OutputSeqList( L);break;case 2:coutGetDate( L)endl;break;case 3:InsList( L);break;case 4:DelList(L,q);break;

9、case 5:coutsum( L)endl;break;cout 是否要繼續(xù)進行操作 y/n:c;#include #include #define MAX 15 #define TURE 1 #define FALSE 0 typedef char ElemType; typedef struct Node char date;struct Node * next; Node,*LinkList;void InitList(LinkList *L)*L=(LinkList)malloc(sizeof(char);(*L)-next=NULL;void PrintfLink(LinkList

10、 L)LinkList p; p=L-next; printf( 鏈表為 :); while(p!=NULL) printf(%c ,p-date); p=p-next;void Create(LinkList L)LinkList s,r; char c; int flag=1; int n; r=L;printf( 元素個數(shù) :); scanf(%d,&n); if(nMAX)printf( 超出限定長度 !); elseprintf( 輸入字符 (以 #鍵結(jié)束 ):); while(flag) scanf(%c,&c); if(c!=#) s=(Node*)malloc(sizeof(c

11、har); s-date=c;r-next=s; r=s; elseflag=0; r-next =NULL;void Order(LinkList L)char c;Node *r,*q,*p;for(r=L-next;r-next!=NULL;r=r-next ) p=r;for(q=r-next;q;q=q-next )if(q-date)date) p=q;if(p!=r)c=r-date;r-date=p-date; p-date=c; PrintfLink(L);void Get(LinkList L, int i, ElemType *e)int j; Node *p;p=L;

12、j=-1;while (p-next!=NULL)&(jnext;j+;*e=p-date ;if(i=j)printf( 第 %d 個元素為 :%c,i,*e);elseprintf(FALSE);void Locate(LinkList L, ElemType e)int i=1;LinkList p;p=L-next ;while(p&p-date!=e)i=i+;p=p-next;if(!p)printf(FALSEn);elseprintf(TRUEn);printf( 該元素在第 %d 個位置 !,i-1); void InsList(LinkList L,int i,ElemTy

13、pe e)Node *p,*s;int k=0;p=L; while(p!=NULL&knext; k=k+;if(!p)printf( 插入位置不合理 !); s=(Node*)malloc(sizeof(char); s-date=e;s-next=p-next;p-next=s;Order(L);void DelList(LinkList L,int i,ElemType *e)Node *p,*r;int j;j=0;p=L; while(p-next!=NULL)&(jnext; j+; if(p-next!=NULL) p-next=p-next-next; r=p-next;*e

14、=r-date ; printf( 刪除第 %d 個元素 :%cn,i,*e);elseprintf( 刪除結(jié)點的位置 i 不合理 !); void ListLength(LinkList L)Node *p;int j=0; p=L-next; while(p!=NULL) p=p-next;j+; printf( 單鏈表的長度 :%d,j);void menu()printf(n*菜單*);printf（n1.創(chuàng)建任意字符型單循環(huán)鏈表）;printf（n2.打?。ū闅v）該鏈表 ）;printf（n3.查找第 i 個元素 ）;printf（n4.查找與一已知字符相同的元素）;printf（n

15、5.插入元素 ）;printf（n6.刪除第 i 個結(jié)點）;printf（n7.計算鏈表的長度）;printf（n8.退出 ）;printf(n*);void main()int i;int flag=0;ElemType e;LinkList L;L=(LinkList)malloc(sizeof(char);InitList(&L);menu();while(!flag)printf(nn 請輸入你的選擇 (18):);scanf(%d,&i);switch(i)case 1:Create(L); break;case 2:Order(L);break;case 3:printf( 輸入要

16、查找的第 i 個元素 :); scanf(%d,&i);Get(L,i,&e);break;case 4:printf( 輸入查找的元素 :); rewind(stdin);scanf(%c,&e);Locate(L,e);break;case 5:printf( 輸入插入的元素 :); rewind(stdin);scanf(%c,&e);InsList(L,i,e); break;case 6:printf( 輸入要刪除第幾個結(jié)點 :);scanf(%d,&i);DelList(L,i,&e); break;case 7:ListLength(L); break;case 8:flag=1

17、;break;4 測試數(shù)據(jù)與實驗結(jié)果（可以抓圖粘貼）作操的-T逝爲 你順元元一兀岀找入除和 選整9 曰疋y請1 2 3 4 5 4進講表； 續(xù)要唾畫 繼你順元元 要摂岀找入除和 否詵鑿是9號 i個元：3素：2、主g捌 輸八.:c遠逋入你的選擇 們8：2鏈表為：？黑選擇5心 侍 以$鍵結(jié)束：abcde$ eC:UsersuserDesktopDebugCppl.exee入子 請元輸匸-tK12345678表 鏈 環(huán)I相 單鏈符 rl素吟& 字辱已弋的 二-素詒表 任第與元第鏈 創(chuàng)打查查ib 選的加 你杳O 入要E 輸訂 請5結(jié)果分析與實驗體會1. 編程時，要注意隨時寫點注釋，有利于編譯;2. 要

18、先熟悉書本上的內(nèi)容，否則編譯會有困難;3. 不能太過死板，要靈活運用所學(xué)知識。僅供個人用于學(xué)習(xí)、研究；不得用于商業(yè)用途For personal use only in study and research; not for commercial use.Nur f u r den pers?nlichen f u r Studien, Forschung, zu kommerziellen Zwecken verwendet werden.Pour l e tude et la recherche uniquementa des fins personnelles; pasa des fins commerciales.to員bko gA.nrogeHKO TOpBieno 員 b3ymm(acH6yqeHu兄 cj egoB u HHue肉go 員冶hbiUCnO 員 B3OBaTbCEb KOMMepqeckux以下無正文僅供個人用于學(xué)習(xí)、研究；不得用于商業(yè)用途For personal use only in study and research; not for commercial use