數(shù)據(jù)結(jié)構(gòu)實驗一線性表及其應(yīng)用

1、-. z實驗一線性表及其應(yīng)用一、實驗?zāi)康?.熟悉C語言的上機環(huán)境，進一步掌握C語言的構(gòu)造特點。2.掌握線性表的順序存儲構(gòu)造的定義及C語言實現(xiàn)。3.掌握線性表的鏈式存儲構(gòu)造單鏈表的定義及C語言實現(xiàn)。4.掌握線性表在順序存儲構(gòu)造即順序表中的各種根本操作。5.掌握線性表在鏈式存儲構(gòu)造單鏈表中的各種根本操作。二、實驗容1.順序線性表的建立、插入及刪除。 2.鏈式線性表的建立、插入及刪除。三、實驗步驟1.建立含n個數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長度。2.利用前面的實驗先建立一個順序表L=21，23，14，5，56，17，31，然后在第i個位置插入元素68。3.建立一個帶頭結(jié)點的單鏈表，

2、結(jié)點的值域為整型數(shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來建立相應(yīng)單鏈表。四、實現(xiàn)提示1.由于C語言的數(shù)組類型也有隨機存取的特點，一維數(shù)組的機表示就是順序構(gòu)造。因此，可用C語言的一維數(shù)組實現(xiàn)線性表的順序存儲。在此，我們利用C語言的構(gòu)造體類型定義順序表：#define MA*SIZE 1024typedef int elemtype; /* 線性表中存放整型元素 */typedef struct elemtype vecMA*SIZE; int len; /* 順序表的長度 */sequenlist;將此構(gòu)造定義放在一個頭文件sqlist.h里，可防止在后面的參考程序中代碼重復(fù)書寫，另外在該頭文件里

3、給出順序表的建立及常量的定義。2. 注意如何取到第i個元素，在插入過程中注意溢出情況以及數(shù)組的下標與位序順序表中元素的次序的區(qū)別。3.單鏈表的結(jié)點構(gòu)造除數(shù)據(jù)域外，還含有一個指針域。用C語言描述結(jié)點構(gòu)造如下： typedef int elemtype;typedef struct node elemtype data; /數(shù)據(jù)域 struct node *ne*t; /指針域 linklist;注意結(jié)點的建立方法及構(gòu)造新結(jié)點時指針的變化。構(gòu)造一個結(jié)點需用到C語言的標準函數(shù)malloc()，如給指針變量p分配一個結(jié)點的地址：p=(linklist *)malloc(sizeof(linklist)

4、;該語句的功能是申請分配一個類型為linklist的結(jié)點的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點不需要時可以用標準函數(shù)free(p)釋放結(jié)點存儲空間，這時p為空值NULL。五、思考與提高1. 如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2. 在main函數(shù)里如果去掉L=&a語句，會出現(xiàn)什么結(jié)果？六、完整參考程序1.順序線性表的建立、插入及刪除。#include #include #define MA* 30 /定義線性表的最大長度enum BOOLFalse,True; /定義BOOL型typedef struct char elemMA*; /線性表 int last;

5、/last指示當(dāng)前線性表的長度sqlist;void initial(sqlist &); /初始化線性表BOOL insert(sqlist &,int,char); /在線性表中插入元素BOOL del(sqlist&,int,char &); /在線性表中刪除元素int locate(sqlist,char); /在線性表中定位元素void print(sqlist); /顯示線性表中所有元素void main()sqlist S; /S為一線性表 int loc,flag=1; char j,ch; BOOL temp;printf(本程序用來實現(xiàn)順序構(gòu)造的線性表。n); printf

6、(可以實現(xiàn)查找、插入、刪除等操作。n); initial(S); /初始化線性表 while(flag) printf(請選擇:n); printf(1.顯示所有元素n); printf(2.插入一個元素n); printf(3.刪除一個元素n); printf(4.查找一個元素n); printf(5.退出程序 n); scanf( %c,&j); switch(j)case 1:print(S); break; /顯示所有元素 case 2:printf(請輸入要插入的元素(一個字符)和插入位置:n); printf(格式：字符，位置；例如:a,2n); scanf( %c,%d,&ch,

7、&loc); /輸入要插入的元素和插入的位置 temp=insert(S,loc,ch); /插入 if(temp=False) printf(插入失敗!n); /插入失敗 else printf(插入成功!n); print(S); /插入成功 break; case 3:printf(請輸入要刪除元素的位置:); scanf(%d,&loc); /輸入要刪除的元素的位置 temp=del(S,loc,ch); /刪除 if(temp=True) printf(刪除了一個元素:%cn,ch); /刪除成功 else printf(該元素不存在!n); /刪除失敗 print(S); brea

8、k; case 4:printf(請輸入要查找的元素:); scanf( %c,&ch); /輸入要查找的元素 loc=locate(S,ch); /定位 if(loc!=-1) printf(該元素所在位置:%dn,loc+1); /顯示該元素位置 else printf(%c 不存在!n,ch);/當(dāng)前元素不存在 break; default:flag=0;printf(程序完畢，按任意鍵退出!n); getch();void initial(sqlist &v)/初始化線性表 int i; printf(請輸入初始線性表長度：n=); /輸入線性表初始化時的長度 scanf(%d,&v.

9、last); printf(請輸入從1到%d的各元素(字符)，例如:abcdefgn,v.last); getchar(); for(i=0;iv.last;i+) scanf(%c,&v.elemi); /輸入線性表的各元素BOOL insert(sqlist &v,int loc,char ch) /插入一個元素，成功返回True，失敗返回False int i; if(locv.last+1) printf(插入位置不合理!n); /位置不合理 return False; else if(v.last=MA*) /線性表已滿 printf(線性表已滿!n); return False;

10、else for(i=v.last-1;i=loc-1;i-) v.elemi+1=v.elemi;/其后元素依次后移 v.elemloc-1=ch; /插入元素 v.last+; /線性表長度加一 return True; BOOL del(sqlist &v,int loc,char &ch) /刪除一個元素，成功返回True，并用ch返回該元素值，失敗返回False int j; if(locv.last) /刪除位置不合理 return False; else ch=v.elemloc-1; /ch取得該元素值 for(j=loc-1;jv.last-1;j+) v.elemj=v.e

11、lemj+1; /其后元素依次前移 v.last-; /線性表長度減一 return True; int locate(sqlist v,char ch)/在線性表中查找ch的位置，成功返回其位置，失敗返回-1 int i=0; while(iv.last&v.elemi!=ch) i+; /當(dāng)前位置后移，直到找到為止 if(v.elemi=ch) /找到當(dāng)前元素 return i; else return(-1);void print(sqlist v) /顯示當(dāng)前線性表所有元素int i; for(i=0;iv.last;i+) printf(%c ,v.elemi); printf(n)

12、; 2.鏈式線性表的建立、插入及刪除。#include #include #include #define LEN sizeof(LNode) /定義LEN為一個節(jié)點的長度enum BOOLFalse,True; /定義BOOL型typedef struct nodechar data; /數(shù)據(jù)域 struct node *ne*t;/指向下一個節(jié)點的指針LNode,*LinkList;void CreatList(LinkList &,int); /生成一個單鏈表BOOL ListInsert(LinkList &,int,char); /在單鏈表中插入一個元素BOOL ListDelete

13、(LinkList &,int,char &); /在單鏈表中刪除一個元素BOOL ListFind_keyword(LinkList,char,int &); /按關(guān)鍵字查找一個元素BOOL ListFind_order(LinkList,char &,int); /按序號查找一個元素void ListPrint(LinkList); /顯示單鏈表所有元素void main()LinkList L; BOOL temp; int num,loc,flag=1; char j,ch; printf(本程序?qū)崿F(xiàn)鏈式構(gòu)造的線性表的操作。n); printf(可以進展插入，刪除，定位，查找等操作。n

14、); printf(請輸入初始時鏈表長度:); /輸入生成單鏈表時的元素個數(shù) scanf(%d,&num); CreatList(L,num); /生成單鏈表 ListPrint(L); while(flag) printf(請選擇:n); printf(1.顯示所有元素n); /顯示鏈表元素 printf(2.插入一個元素n); /插入鏈表元素 printf(3.刪除一個元素n); /刪除鏈表元素 printf(4.按關(guān)鍵字查找元素n); /按關(guān)鍵字查找 printf(5.按序號查找元素n); /按序號查找 printf(6.退出程序 n); /退出 scanf( %c,&j); switc

15、h(j)case 1:ListPrint(L); break; case 2:printf(請輸入元素(一個字符)和要插入的位置:n); printf(格式:字符，位置；例如:a,3n); scanf( %c,%d,&ch,&loc); /輸入要插入的元素和要插入的位置 temp=ListInsert(L,loc,ch); /插入 if(temp=False) printf(插入失敗!n); /插入失敗 else printf(插入成功!n); /成功插入 ListPrint(L); break; case 3:printf(請輸入要刪除的元素所在位置:); scanf(%d,&loc); /

16、輸入要刪除的節(jié)點的位置 temp=ListDelete(L,loc,ch); /刪除 if(temp=False) printf(刪除失敗!n); /刪除失敗 else printf(成功刪除了一個元素:%cn,ch); /刪除成功，顯示該元素 ListPrint(L); break; case 4:if(L-ne*t=NULL) /鏈表為空 printf(鏈表為空!n); elseprintf(請輸入要查找的元素(一個字符):); scanf( %c,&ch); /輸入要查找的元素 temp=ListFind_keyword(L,ch,loc); /按關(guān)鍵字查找 if(temp=False)

17、 printf(沒有找到該元素!n); /查找失敗 else printf(該元素在鏈表的第%d個位置。n,loc); /成功查找，顯示該元素位置 break; case 5:if(L-ne*t=NULL) /鏈表為空 printf(鏈表為空!n); elseprintf(請輸入要查找的位置:); scanf(%d,&loc); /輸入要查找的元素的位置 temp=ListFind_order(L,ch,loc); /按序號查找 if(temp=False) printf(該位置不存在!n); /查找失敗 else printf(第%d個元素是：%cn,loc,ch); /成功查找，顯示該元素

18、 break; default:flag=0;printf(程序完畢，按任意鍵退出!n); getch();void CreatList(LinkList &v,int n)/生成一個帶頭結(jié)點的有n個元素的單鏈表 int i; LinkList p; v=(LinkList)malloc(LEN); /生成頭結(jié)點 v-ne*t=NULL; printf(請輸入%d個字符：例如：abcdefgn,n); getchar(); for(i=n;i0;-i) p=(LinkList)malloc(LEN); /生成新結(jié)點 scanf(%c,&p-data); p-ne*t=v-ne*t; v-ne*

19、t=p; BOOL ListInsert(LinkList &v,int i,char e)/在單鏈表的第i各位置插入元素e，成功返回True，失敗返回False LinkList p,s; int j=0; p=v; while(p&jne*t;+j; /查找第i-1個元素的位置 if(!p|ji-1) return False; /沒有找到 s=(LinkList)malloc(LEN); /生成一個新結(jié)點 s-data=e; s-ne*t=p-ne*t; /將新結(jié)點插入到單鏈表中 p-ne*t=s; return True;BOOL ListDelete(LinkList &v,int i,char &e)/在單鏈表中刪除第i個元素，成功刪除返回True，并用e返回該元素值，失敗返回False LinkList p,q; int j=0; p=v; while(p-ne*t&jne*t;+j; if(!(p-ne*t)|ji-1) return False; /查找失敗 q=p-ne*t;p-ne*t=q-n