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

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

2、點(diǎn)的值域?yàn)檎蛿?shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來(lái)建立相應(yīng)單鏈表。四、實(shí)現(xiàn)提示1.由于C語(yǔ)言的數(shù)組類型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。在此，我們利用C語(yǔ)言的結(jié)構(gòu)體類型定義順序表：#define MAXSIZE  1024typedef  int  elemtype;    /*  線性表中存放整型元素  */typedef struct elemtype vecMAXSIZE;  int len;   &#

3、160;         /*  順序表的長(zhǎng)度  */ sequenlist;將此結(jié)構(gòu)定義放在一個(gè)頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書(shū)寫(xiě)，另外在該頭文件里給出順序表的建立及常量的定義。2. 注意如何取到第i個(gè)元素，在插入過(guò)程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。3.單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個(gè)指針域。用C語(yǔ)言描述結(jié)點(diǎn)結(jié)構(gòu)如下：    typedef int elemtype;typedef str

4、uct node    elemtype data;   /數(shù)據(jù)域      struct node *next; /指針域     linklist;    注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個(gè)結(jié)點(diǎn)的地址：p=(linklist *)malloc(sizeof(linklist);該語(yǔ)句的功能是申請(qǐng)分配一個(gè)類型為linklist的結(jié)點(diǎn)的地址空間

5、，并將首地址存入指針變量p 中。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p為空值（NULL）。五、思考與提高1. 如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2. 在main函數(shù)里如果去掉L=&a語(yǔ)句，會(huì)出現(xiàn)什么結(jié)果？六、完整參考程序 1.順序線性表的建立、插入及刪除。#include <stdio.h>#include <conio.h>#define MAX 30 /定義線性表的最大長(zhǎng)度enum BOOLFalse,True; /定義BOOL型typedef struct char elemMAX; /線性表 int la

6、st; /last指示當(dāng)前線性表的長(zhǎ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("

7、本程序用來(lái)實(shí)現(xiàn)順序結(jié)構(gòu)的線性表。n"); printf("可以實(shí)現(xiàn)查找、插入、刪除等操作。n"); initial(S); /初始化線性表 while(flag) printf("請(qǐng)選擇:n"); printf("1.顯示所有元素n"); printf("2.插入一個(gè)元素n"); printf("3.刪除一個(gè)元素n"); printf("4.查找一個(gè)元素n"); printf("5.退出程序 n"); scanf(" %c",

8、&j); switch(j)case '1':print(S); break; /顯示所有元素 case '2':printf("請(qǐng)輸入要插入的元素(一個(gè)字符)和插入位置:n"); printf("格式：字符，位置；例如:a,2n"); scanf(" %c,%d",&ch,&loc); /輸入要插入的元素和插入的位置 temp=insert(S,loc,ch); /插入 if(temp=False) printf("插入失敗!n"); /插入失敗 else

9、printf("插入成功!n"); print(S); /插入成功 break; case '3':printf("請(qǐng)輸入要?jiǎng)h除元素的位置:"); scanf("%d",&loc); /輸入要?jiǎng)h除的元素的位置 temp=del(S,loc,ch); /刪除 if(temp=True) printf("刪除了一個(gè)元素:%cn",ch); /刪除成功 else printf("該元素不存在!n"); /刪除失敗 print(S); break; case '4'

10、;:printf("請(qǐng)輸入要查找的元素:"); 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("程序結(jié)束，按任意鍵退出!n"); getch();void initial(sqlist &v)/初始化

11、線性表 int i; printf("請(qǐng)輸入初始線性表長(zhǎng)度：n="); /輸入線性表初始化時(shí)的長(zhǎng)度 scanf("%d",&v.last); printf("請(qǐng)輸入從1到%d的各元素(字符)，例如:abcdefgn",v.last); getchar(); for(i=0;i<v.last;i+) scanf("%c",&v.elemi); /輸入線性表的各元素BOOL insert(sqlist &v,int loc,char ch) /插入一個(gè)元素，成功返回True，失敗返回Fal

12、se int i; if(loc<1)|(loc>v.last+1) printf("插入位置不合理!n"); /位置不合理 return False; else if(v.last>=MAX) /線性表已滿 printf("線性表已滿!n"); return False; else for(i=v.last-1;i>=loc-1;i-) v.elemi+1=v.elemi;/其后元素依次后移 v.elemloc-1=ch; /插入元素 v.last+; /線性表長(zhǎng)度加一 return True; BOOL del(sqlist

13、&v,int loc,char &ch) /刪除一個(gè)元素，成功返回True，并用ch返回該元素值，失敗返回False int j; if(loc<1|loc>v.last) /刪除位置不合理 return False; else ch=v.elemloc-1; /ch取得該元素值 for(j=loc-1;j<v.last-1;j+) v.elemj=v.elemj+1; /其后元素依次前移 v.last-; /線性表長(zhǎng)度減一 return True; int locate(sqlist v,char ch)/在線性表中查找ch的位置，成功返回其位置，失敗返回-

14、1 int i=0; while(i<v.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;i<v.last;i+) printf("%c ",v.elemi); printf("n"); 2.鏈?zhǔn)骄€性表的建立、插入及刪除。#include <conio.h>#include <stdio.h

15、>#include <stdlib.h>#define LEN sizeof(LNode) /定義LEN為一個(gè)節(jié)點(diǎn)的長(zhǎng)度enum BOOLFalse,True; /定義BOOL型typedef struct nodechar data; /數(shù)據(jù)域 struct node *next;/指向下一個(gè)節(jié)點(diǎn)的指針LNode,*LinkList;void CreatList(LinkList &,int); /生成一個(gè)單鏈表BOOL ListInsert(LinkList &,int,char); /在單鏈表中插入一個(gè)元素BOOL ListDelete(LinkList

16、 &,int,char &); /在單鏈表中刪除一個(gè)元素BOOL ListFind_keyword(LinkList,char,int &); /按關(guān)鍵字查找一個(gè)元素BOOL ListFind_order(LinkList,char &,int); /按序號(hào)查找一個(gè)元素void ListPrint(LinkList); /顯示單鏈表所有元素void main()LinkList L; BOOL temp; int num,loc,flag=1; char j,ch; printf("本程序?qū)崿F(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)的線性表的操作。n"); printf(&

17、quot;可以進(jìn)行插入，刪除，定位，查找等操作。n"); printf("請(qǐng)輸入初始時(shí)鏈表長(zhǎng)度:"); /輸入生成單鏈表時(shí)的元素個(gè)數(shù) scanf("%d",&num); CreatList(L,num); /生成單鏈表 ListPrint(L); while(flag) printf("請(qǐng)選擇:n"); printf("1.顯示所有元素n"); /顯示鏈表元素 printf("2.插入一個(gè)元素n"); /插入鏈表元素 printf("3.刪除一個(gè)元素n");

18、 /刪除鏈表元素 printf("4.按關(guān)鍵字查找元素n"); /按關(guān)鍵字查找 printf("5.按序號(hào)查找元素n"); /按序號(hào)查找 printf("6.退出程序 n"); /退出 scanf(" %c",&j); switch(j)case '1':ListPrint(L); break; case '2':printf("請(qǐng)輸入元素(一個(gè)字符)和要插入的位置:n"); printf("格式:字符，位置；例如:a,3n"); sc

19、anf(" %c,%d",&ch,&loc); /輸入要插入的元素和要插入的位置 temp=ListInsert(L,loc,ch); /插入 if(temp=False) printf("插入失敗!n"); /插入失敗 else printf("插入成功!n"); /成功插入 ListPrint(L); break; case '3':printf("請(qǐng)輸入要?jiǎng)h除的元素所在位置:"); scanf("%d",&loc); /輸入要?jiǎng)h除的節(jié)點(diǎn)的位置 tem

20、p=ListDelete(L,loc,ch); /刪除 if(temp=False) printf("刪除失敗!n"); /刪除失敗 else printf("成功刪除了一個(gè)元素:%cn",ch); /刪除成功，顯示該元素 ListPrint(L); break; case '4':if(L->next=NULL) /鏈表為空 printf("鏈表為空!n"); elseprintf("請(qǐng)輸入要查找的元素(一個(gè)字符):"); scanf(" %c",&ch); /輸

21、入要查找的元素 temp=ListFind_keyword(L,ch,loc); /按關(guān)鍵字查找 if(temp=False) printf("沒(méi)有找到該元素!n"); /查找失敗 else printf("該元素在鏈表的第%d個(gè)位置。n",loc); /成功查找，顯示該元素位置 break; case '5':if(L->next=NULL) /鏈表為空 printf("鏈表為空!n"); elseprintf("請(qǐng)輸入要查找的位置:"); scanf("%d",&

22、;loc); /輸入要查找的元素的位置 temp=ListFind_order(L,ch,loc); /按序號(hào)查找 if(temp=False) printf("該位置不存在!n"); /查找失敗 else printf("第%d個(gè)元素是：%cn",loc,ch); /成功查找，顯示該元素 break; default:flag=0;printf("程序結(jié)束，按任意鍵退出!n"); getch();void CreatList(LinkList &v,int n)/生成一個(gè)帶頭結(jié)點(diǎn)的有n個(gè)元素的單鏈表 int i; LinkL

23、ist p; v=(LinkList)malloc(LEN); /生成頭結(jié)點(diǎn) v->next=NULL; printf("請(qǐng)輸入%d個(gè)字符：例如：abcdefgn",n); getchar(); for(i=n;i>0;-i) p=(LinkList)malloc(LEN); /生成新結(jié)點(diǎn) scanf("%c",&p->data); p->next=v->next; v->next=p; BOOL ListInsert(LinkList &v,int i,char e)/在單鏈表的第i各位置插入元素e，

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