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

1、淮海工學院計算機科學系實驗報告書課程名： 數(shù)據(jù)結(jié)構(gòu) 題 目： 線性表數(shù)據(jù)結(jié)構(gòu)試驗 班 級： 軟件112 學 號： 姓 名： 評語：成績： 指導(dǎo)教師： 批閱時間： 年 月 日 數(shù)據(jù)結(jié)構(gòu) 實驗報告 - 13 -線性表實驗報告要求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、求，認真書寫實驗報告，并在試驗后的第三天提交電子（全班同學提交到學委，再統(tǒng)一打包提交給老師）和紙質(zhì)（每班每次5份，學委安排，保證每個同學至少提交一次）；8）積極開展實驗組組內(nèi)交流和輔導(dǎo)，嚴禁復(fù)制和剽竊他人實驗成果，一旦發(fā)現(xiàn)嚴肅處理；9）上實驗課前，要求每個同學基本寫好程序，并存儲在自己的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)；

3、2）打印/顯示（遍歷）該線性表（依次打印/顯示出表中元素值）；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）打印（遍歷）該鏈表（依次打印出表中元素值，注意字符的輸入順序與鏈表的結(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#defineMAXSIZE 25 /*此處的宏定義常量表示線性表可能達到的最大長度*/using namespace std;typedef struct ElemType elemMAXSIZE; /*線性表占用的數(shù)組空間*/int last;

5、/*記錄線性表中最后一個元素在數(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 k;if(iL-last+2) /*首先判斷插入位置是

6、否合法*/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請輸出要刪除的元素位置：w;int k;if(wL-last+1) cout刪除位置不合法!elemw-1;

7、/* 將刪除的元素存放到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(sizeof(int);coutn;L-last=n-1;cout請輸入順序表：endl;int i;

8、 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;case 5:coutsum( L)endl;break;cout是否要繼續(xù)進行操作y/n:c;#include#include#

9、define MAX 15#define TURE 1#define FALSE 0typedef char ElemType;typedef struct Nodechar date;struct Node * next;Node,*LinkList;void InitList(LinkList *L)*L=(LinkList)malloc(sizeof(char);(*L)-next=NULL;void PrintfLink(LinkList L) LinkList p; p=L-next; printf(鏈表為:);while(p!=NULL) printf(%c ,p-date);p=

10、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(char); s-date=c;r-next=s;r=s;elseflag=0; r-next =NULL;void Order(LinkList L)char c;Node *r,*q,*p

11、;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; j=-1;while (p-next!=NULL)&(jnext; j+; *e=p-date ;if(i=j) printf(第%d個元素為:%c,i,*e); else printf(FALS

12、E); 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);else printf(TRUEn);printf(該元素在第%d個位置!,i-1);void InsList(LinkList L,int i,ElemType e)Node *p,*s; int k=0; p=L; while(p!=NULL&knext; k=k+; if(!p) printf(插入位置不合理!); s=(Node*)malloc(s

13、izeof(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=r-date ;printf(刪除第%d個元素:%cn,i,*e);else printf(刪除結(jié)點的位置i不合理!); void ListLength(LinkList L)Node *p

14、;int j=0;p=L-next;while(p!=NULL)p=p-next;j+;printf(單鏈表的長度:%d,j);void menu()printf(n*菜單*);printf(n 1.創(chuàng)建任意字符型單循環(huán)鏈表);printf(n 2.打?。ū闅v）該鏈表);printf(n 3.查找第i個元素);printf(n 4.查找與一已知字符相同的元素);printf(n 5.插入元素);printf(n 6.刪除第i個結(jié)點);printf(n 7.計算鏈表的長度);printf(n 8.退出);printf(n*);void main()int i;int flag=0;ElemTyp

15、e 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(輸入要查找的第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)