數(shù)據(jù)結(jié)構(gòu)線(xiàn)性表單鏈表的查找、插入、刪除

1、實(shí)驗(yàn)報(bào)告課程名稱(chēng)姓 名學(xué) 號(hào)專(zhuān)業(yè)班級(jí)數(shù)據(jù)結(jié)構(gòu)指導(dǎo)教師目錄第二章線(xiàn)性表的查找、插入、刪除 11.1 順序表的查找 11.2 順序表的插入 21.3 順序表的刪除 4單鏈表的建立、插入、刪除 . 62.1 單鏈表的建立（尾插法） 62.2 單鏈表的插入 82.3 單鏈表的刪除 10第三章棧 143.1 鏈棧 143.3 隊(duì)列 . 3.4 楊輝三角 第四章串4.1 字符串的建立4.2 順序串的插入3.2 順序棧 1618. 20 2323251.線(xiàn)性表的查找、插入、刪除1.1 順序表的查找程序：#include #include #include#define OK 1 #define ERROR

2、0#define TRUE 1#define FALSE 0 #define ElemType int#define MAXSIZE 100 /* 此處的宏定義常量表示線(xiàn)性表可能達(dá)到的最大長(zhǎng)度 */typedef structElemType elemMAXSIZE; /* 線(xiàn)性表占用的數(shù)組空間 */ int last; /* 記錄線(xiàn)性表中最后一個(gè)元素在數(shù)組 elem 中的位置(下 標(biāo)值)，空表為 -1*/Seqlist;int Locate(Seqlist L,ElemType e)/*在順序表L中查找與e相等的元素，若L。elemi=e,則找到該元素，并返回 i+1 ，若找不到，則返回 -

3、1*/ int i=0; /*i 為掃描計(jì)數(shù)器，初值為 0，即從第一個(gè)元素開(kāi)始比較 */while (i=L.last)&(L.elemi!=e)/* 順序掃描表，直到找到值為 e 的元素，或掃描到表尾仍沒(méi)找到 */ i+;if(i=L.last)return (i+1); /* 若找到值為 e 的元素，則返回其序號(hào) */ elsereturn(-1); /* 若沒(méi)找到，則返回空序號(hào) */void main()Seqlist l;int p,q,r;int i;printf( 請(qǐng)輸入線(xiàn)性標(biāo)的長(zhǎng)度 :);scanf(%d,&r);I.last=r-1;prin tf(請(qǐng)輸入線(xiàn)性表的各元素值：n)

4、;for (i=O;i=I.Iast;i+)sca nf(%d,&l.elemi);printf(請(qǐng)輸入要查找的元素值:n);sca nf(%d,&q);p=Locate(l,q);if(p=-1)printf(在此線(xiàn)性表中沒(méi)有該元素!n);elseprintf(該素在線(xiàn)性表中的位置為:%dn,p);執(zhí)行結(jié)果:錯(cuò)誤分析 :在編寫(xiě)過(guò)程中，在編寫(xiě)主函數(shù)的時(shí)候有落下未編寫(xiě)的，導(dǎo)致運(yùn)行過(guò)程中不 識(shí)別。1.2順序表的插入程序：#i nclude #i nclude #in clude #defi ne OK 1#defi ne ERROR 0#defi ne TRUE 1#define FALSE 0

5、#define ElemType int#define MAXSIZE 100typedef structElemType elemMAXSIZE; int last;SeqList;/#include common.h/#include seqlist.h int InsList(SeqList *L,int i,ElemType e) int k;if(iL-last+2)printf( 插入位置 i 值不合法 ); return(ERROR);if(L-last= MAXSIZE-1)printf( 表已滿(mǎn)無(wú)法插入 ); return(ERROR);for(k=L-last;k=i-1;

6、k-)L-elemk+1=L-elemk;L-elemi-1=e;L-last+;return(OK);void main()SeqList *l;int p,q,r;int i; l=(SeqList*)malloc(sizeof(SeqList); printf( 請(qǐng)輸入線(xiàn)性表的長(zhǎng)度 :); scanf(%d,&r);l-last = r-1;printf( 請(qǐng)輸入線(xiàn)性表的各元素值 :n);for(i=0; ilast; i+)sca nf(%d,&l-elemi);printf(請(qǐng)輸入要插入的位置:n);scan f(%d,&p);printf(請(qǐng)輸入要插入的元素值:n);scan f(

7、%d,&q);In sList(l,p,q);for(i=0; ilast; i+)prin tf(%d ,l-elemi);執(zhí)行結(jié)果：1.3順序表的刪除程序：#i nclude #i nclude #i nclude #defi ne OK 1#defi ne ERROR 0#defi ne TRUE 1#defi ne FALSE 0#defi ne ElemType int#defi neMAXSIZE 100typedef structElemType elemMAXSIZE;int last; SeqList;int DelList(SeqList *L,int i,ElemType

8、 *e) int k;if(iL-last+1)printf( 刪除位置不合法 !); return(ERROR);*e = L-elemi-1;for(k=i; ilast; k+)L-elemk-1 = L-elemk;L-last-;return(OK); void main()SeqList *l;int p,r;int *q;int i;l = (SeqList*)malloc(sizeof(SeqList);q = (int*)malloc(sizeof(int);printf( 請(qǐng)輸入線(xiàn)性表的長(zhǎng)度 :); scanf(%d,&r);l-last = r-1;printf( 請(qǐng)輸入

9、線(xiàn)性表的各元素值 :n); for(i=0; ilast; i+) scanf(%d,&l-elemi);printf( 請(qǐng)輸入要?jiǎng)h除的元素位置 :n); scanf(%d,&p);DelList(l,p,q);printf( 刪除的元素值為 :%dn,*q); 執(zhí)行結(jié)果：H flC:UscrsW，. - X請(qǐng)輸入線(xiàn)性恚的長(zhǎng)度;6 請(qǐng)輸入線(xiàn)性表的各元素值：12 25 12 65 15 65 請(qǐng)輸入要?jiǎng)h除的元素位置：3刪除的元素值為：12Press any key to continue2單鏈表的建立、插入、刪除2.1單鏈表的建立（尾插法）程序：#i nclude#i nclude#defi n

10、e ERROR 0#defi ne TRUE 1#defi ne FALSE 0typedef char ElemType;typedef struct Node /*結(jié)點(diǎn)類(lèi)型定義 */ElemType data;struct Node * n ext;Node, *LinkList; /* LinkList為結(jié)構(gòu)指針類(lèi)型 */void init_linklist(LinkList *1)/*對(duì)單鏈表進(jìn)行初始化 */ _*l=(Li nkList)malloc(sizeof(Node);(*l)- next=NULL;void CreateFromTail(Li nkList L)Node *

11、r, *s;char c;int flag =1; /*設(shè)置一個(gè)標(biāo)志，初值為，當(dāng)輸入$時(shí)，flag為，建表結(jié)束*/r=L;/*r指針動(dòng)態(tài)指向鏈表的當(dāng)前表尾，以便于做尾插入，其初值指向頭結(jié)點(diǎn) */while(flag) /* 循環(huán)輸入表中元素值，將建立新結(jié)點(diǎn) s 插入表尾 */c=getchar();if(c!=a)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s;elseflag=0;r-next=NULL; /* 將最后一個(gè)結(jié)點(diǎn)的 next 鏈域置為空，表示 鏈表的結(jié)束 */int main()LinkList l;Node *p;init

12、_linklist(&l);printf( 用尾插法建立單鏈表 , 請(qǐng)輸入鏈表數(shù)據(jù) , 以 a 結(jié)束 !n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;return 0;執(zhí)行結(jié)果：匚:Usc冷奏轡DktopDcb用尾插法建立單鏈表，請(qǐng)輸人鏈表數(shù)據(jù)，以a結(jié)束!156 26 56 23 122a13ress any key tc continue錯(cuò)誤分析： 在代碼的時(shí)候忘記分號(hào)，導(dǎo)致運(yùn)行錯(cuò)誤；截圖如下Cp|j 1 _obj -1 errur(b), 0 Wdriilng(b)2.2單鏈表的插入程序：

13、#i nclude common .h#include linklist.hint In sList(L in kList L,i nt i,ElemType e)/*在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置插入值為e的新結(jié)點(diǎn)s*/Node *pre,*s;int k;pre=L;k=0;/*從頭開(kāi)始，查找第i-1個(gè)結(jié)點(diǎn)*/while(pre!=NULL&knext; k=k+1; if(!pre) 位置不合理 */printf( 插入位置不合理 !); return ERROR; s=(Node*)malloc(sizeof(Node); /* s-data=e; /* s-next=pre-nex

14、t;pre-next=s;return OK;/*如當(dāng)前位置 pre/* 查找第 i-1 結(jié)點(diǎn) */ 為空表已找完還未數(shù)到第 i 個(gè)，說(shuō)明插入申請(qǐng)一個(gè)新的結(jié)點(diǎn) S */值 e 置入 s 的數(shù)據(jù)域 */* 修改指針，完成插入操作 */void main()LinkList l;Node *p;int flag=0;int i;char c;init_linklist(&l);printf(請(qǐng)輸入鏈表數(shù)據(jù),以$結(jié)束!n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;printf( 請(qǐng)輸入插入的位置和元

15、素 :n);scanf(%d,%c,&i,&c);printf(%cn,c);flag=InsList(l, i, c);if(flag) printf( 插入操作成功 !n);elseprintf( 插入操作失敗 !n);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;執(zhí)行結(jié)果：2.3 單鏈表的刪除程序：#include#include#include#defineOK 1#defineERROR 0#defineTRUE 1#defineFALSE 0/* 結(jié)點(diǎn)類(lèi)型定義 */typedef char ElemType; typede

16、f struct NodeElemType data;struct Node * next;Node, *LinkList; /* LinkList 為結(jié)構(gòu)指針類(lèi)型 */ void init_linklist(LinkList *l)/* 對(duì)單鏈表進(jìn)行初始化 */*l=(LinkList)malloc(sizeof(Node);(*l)-next=NULL;void CreateFromTail(LinkList L)Node *r, *s;char c;int flag =1; /* 設(shè)置一個(gè)標(biāo)志，初值為 1，當(dāng)輸入 $ 時(shí)， flag 為 0，建表結(jié)束 */r=L; /*r 指針動(dòng)態(tài)指向鏈

17、 表的當(dāng)前表尾，以便于做尾插入，其初值指向頭結(jié)點(diǎn) */while(flag) /* 循環(huán)輸入表中元素值，將建 立新結(jié)點(diǎn) s 插入表尾 */c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node );s-data=c;r-next=s;r=s;elseflag=0;r-next=NULL; /* 將最后 一個(gè)結(jié)點(diǎn)的 next 鏈域置為空，表示鏈表的結(jié)束 */int DelList(LinkList L,int i,ElemType *e)/*在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素，并將刪除的元素保存到變量*e中*/Node *pre,*r;int k;pre

18、=L;k=0;while(pre-next!=NULL & knext;k=k+1; /* 查找第 i-1 個(gè)結(jié)點(diǎn) */if(!(pre-next)/* 即 while 循環(huán)是因?yàn)?p-next=NULL 或 inext;pre-next=pre-next-next;/* 修改指針，刪除結(jié)點(diǎn) r*/*e = r-data;free(r);/* 釋放被刪除的結(jié)點(diǎn)所占的內(nèi)存空間 */printf( 成功刪除結(jié)點(diǎn) !n);/printf(被刪除的元素是 :%cn,*e);return OK;void main()LinkList l;Node *p;int flag=0;int x;char*e;i

19、nit_linklist(&l);printf(請(qǐng)輸入鏈表數(shù)據(jù),以$結(jié)束!n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;printf( 請(qǐng)輸入要?jiǎng)h除的元素位置： n);scanf(%d,&x);e = (char*)malloc(sizeof(char);DelList(l,x,e);p = l-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);執(zhí)行結(jié)果： ,C;UscrsWDesktopDcbug1 ,exc-f請(qǐng)輸入鏈表數(shù)搖，以

20、S結(jié)束！12 23 4$1234請(qǐng)輸入要?jiǎng)t除的元素位置：2成功刪除結(jié)點(diǎn)！1 23 4Press any key to continue3. 棧3.1鏈棧程序：#i nclude#i nclude#defi ne TRUE 1#defi ne FALSE 0#defi ne StackEleme ntType int typedef struct nodeStackEleme ntType data; struct node *n ext;Li nkStackNode;typedef Lin kStackNode *Lin kStack;int Push(L in kStack top,Stac

21、kEleme ntType x)Lin kStackNode *temp;temp=(LinkStackNode *)malloc(sizeof(LinkStackNode);if(temp=NULL) return(FALSE);temp-data=x;temp-next=top-next;top-next=temp;return(TRUE);int Pop(LinkStack top,StackElementType *x)LinkStackNode *temp;temp=top-next;if(temp=NULL) return(FALSE);top-next=temp-next;*x=

22、temp-data;free(temp);return(TRUE);int main()LinkStackNode *top;top=(LinkStackNode *)malloc(sizeof(LinkStackNode); top-next=NULL;int flag=1;int a,x=0;printf( 請(qǐng)輸入鏈表的各元素值 (輸入 0 代表結(jié)束 ):n); while(flag) scanf(%d,&a);if(a!=0) Push(top,a);else flag=0; while(top-next!=NULL)Pop(top,&x); printf(%dt,x);printf(n

23、);return 0;執(zhí)行結(jié)果 1 C ;U scD eskto pDc bu g1 * exe X卩青輸入鏈表的各兀素值(輸入0代表結(jié)束丿:1 25 2 32 65 66006065322251Press any key to continup3.2順序棧順序棧進(jìn)棧程序：#i nclude#i nclude #i nclude #defi ne stack_size 50typedef structint elemstack_size;int top;seqstack;void in itstack(seqstack *s)s-top = -1;int push(seqstack *s, i

24、nt x)if (s-top = stack_size - 1) return 0; s-top+;s-elems-top = x;return 1;void OutStack(seqstack *p)int i;if (p-toptop; i = 0; i-)prin tf(%d , p-elemi);int main()int a;int i, r;seqstack *s;s = (seqstack*)malloc(sizeof(seqstack); in itstack(s);printf(請(qǐng)輸入長(zhǎng)度:);scan f(%d, &r);printf(請(qǐng)輸入各元素值:n);for (i =

25、 0; itop+;scanf(%d, &s-elemi);printf(請(qǐng)輸入要進(jìn)棧的值：);scan f(%d, & a);push(s, a);OutStack(s);return 0;執(zhí)行結(jié)果: 1 C;UscrsDesktopDcbug1 ,exe X請(qǐng)輸入長(zhǎng)嗟;5卩青輸入各元素值：12 23 32 45 56 陽(yáng)輸入要進(jìn)棧的值:445645322312 Press any key to continue4. 隊(duì)列順序隊(duì)列基本操作：#include#include #include #define MaxSize 20 typedef int ElemType; typedef st

26、ruct ElemType dataMaxSize; int front,rear; /SqQueue;/順序隊(duì)列類(lèi)型SqQueue的定義/ 初始化隊(duì)列void InitQueue(SqQueue *&q)q=(SqQueue *)malloc(sizeof(SqQueue); q-front=q-rear=0;/ 銷(xiāo)毀隊(duì)列void ClearQueue(SqQueue *&q)free(q);/ 判斷順序隊(duì)列是否為空 void QueueEmpty(SqQueue *q) if(q-front=q-rear) printf( 目前此順序隊(duì)列為空 n);elseprintf( 目前此順序隊(duì)列非

27、空 n);/ 進(jìn)隊(duì)列void enQueue( SqQueue *&q,ElemType e) if(q-rear+1)%MaxSize=q-front) printf( 目前順序隊(duì)列已滿(mǎn)了 n);else q-rear=(q-rear+1)%MaxSize; q-dataq-rear=e;printf( 此次進(jìn)隊(duì)元素是 :%dn,e);/ 出隊(duì)列void deQueue(SqQueue *&q,ElemType &e)if(q-front=q-rear)printf( 目前此順序隊(duì)列為空 n);elseq-front=(q-front+1)%MaxSize;e=q-dataq-front;p

28、rintf( 此次出隊(duì)元素是 :%dn,e);void main()SqQueue *q;int e;InitQueue(q);QueueEmpty(q);printf( 請(qǐng)?jiān)诖岁?duì)頭插入一個(gè)元素 :n);scanf(%d,&e);while(e!=0)enQueue(q,e);0n);printf( 請(qǐng)繼續(xù)此隊(duì)頭插入一個(gè)元素，或者停止插入隊(duì)列元素，請(qǐng)按 scanf(%d,&e);QueueEmpty(q);int i;printf( 如果想在此隊(duì)尾出隊(duì)一個(gè)元素，請(qǐng)按 1n); scanf(%d,&i);while(i=1)deQueue(q,e);if(q-front=q-rear)print

29、f( 順序隊(duì)列的基本運(yùn)算操作到此結(jié)束了 n);exit(0);elseprintf( 如果想在此隊(duì)尾繼續(xù)出隊(duì)一個(gè)元素，請(qǐng)按 1n);sea nf(%d,&i);執(zhí)行結(jié)果:5. 楊輝三角(i)程序：#i nclude#i nclude#defi ne TRUE 1#defi ne FALSE 0#define MAXSIZE 50 /* 隊(duì)列的最大長(zhǎng)度*/typedef structint elementMAXSIZE; /*隊(duì)列的元素空間 */int front; /*頭指針指示器*/int rear; /* 尾指針指示器*/SeqQueue;/*初始化操作*/void InitQueue(S

30、eqQueue *Q)/*將*Q初始化為一個(gè)空的循環(huán)隊(duì)列*/Q-front=Q-rear=0;/* 入隊(duì)操作 */int EnterQueue(SeqQueue *Q, int x)/* 將元素 x 入隊(duì)*/if(Q-rear+1)%MAXSIZE=Q-front) /* 隊(duì)列已經(jīng)滿(mǎn)了 */ return(FALSE);Q-elementQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE; /* 重新設(shè)置隊(duì)尾指針 */ return(TRUE); /* 操作成功 */* 出隊(duì)操作 */ int DeleteQueue(SeqQueue *Q, int *x)/* 刪除隊(duì)列的隊(duì)

31、頭元素，用 x 返回其值 */ if(Q-front=Q-rear) /* 隊(duì)列為空 */ return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE; /* 重新設(shè)置隊(duì)頭指針 */ return(TRUE); /* 操作成功 */int GetHead(SeqQueue *Q, int *x)/* 提取隊(duì)列的隊(duì)頭元素，用 x 返回其值 */ if(Q-front=Q-rear) /* 隊(duì)列為空 */ return(FALSE);*x=Q-elementQ-front;return(TRUE); /* 操作成功 */void Ya

32、ngHuiTriangle( )int n;int i;int temp;int x;int N;SeqQueue Q;InitQueue(&Q);EnterQueue(&Q,1); /* 第一行元素入隊(duì) */ printf( 請(qǐng)輸入楊輝三角行數(shù) N:);sea nf(%d,&N);for(n=2;n=N;n+) /* 產(chǎn)生第n行元素并入隊(duì)，同時(shí)打印第n-1行的元素*/EnterQueue(&Q,1); /* 第n行的第一個(gè)元素入隊(duì)*/ for(i=1;i=n-2;i+) /*利用隊(duì)中第n-1行元素產(chǎn)生第n行的中間n-2個(gè)元素并入隊(duì)*/DeleteQueue(&Q,& temp);printf

33、(%6d,temp);/*打印第 n-1 行的元素 */GetHead(&Q, &x);temp=temp+x; /* 利用隊(duì)中第n-1行元素產(chǎn)生第n行元素*/ En terQueue(&Q,temp);DeleteQueue (&Q,& x);printf(%6d,x);/*打印第n-1行的最后一個(gè)元素*/EnterQueue(&Q,1); /* 第n行的最后一個(gè)元素入隊(duì)*/ prin tf(n);int mai n()Yan gHuiTria ngle();12Q165220286-1 u127810220715194訂16549S 12871721Wft執(zhí)行結(jié)果:l日冊(cè)聞M號(hào)同177 B

34、 40 2 4 _b.15 55060 O-B5 13731391 lnv3 4 711112113346151016151T21182819361104?1115q112S611378Press any key to contFl 5fi6. 串6.1 字符串的建立程序：#include #include #define MAXLEN 40#define MAXLEN 40typedef struct /* 串結(jié)構(gòu)定義 */ char chMAXLEN;int len;SString;void createstring(SString *s)int i,j;char c;printf( 請(qǐng)輸

35、入要建立的串的長(zhǎng)度 :); scanf(%d,&j);for(i=0; ichi = c; s-len = j;void output(SString *s)int i;for (i=0;ilen;i+) printf(%c ,s-chi);printf(n);int StrEmpty(SString s)/* 若串 s 為空則返回，否則返回 */if (s.len=0) return(1);else return(0); int main()SStri ng str2;int flag=0;printf(建立字符串!n);createstri ng(&str2); flag=StrEmpty(str2);if(flag = 1)printf( 字符串為空!); elseprintf(字符串不為空!n);output(&str2);return 0;執(zhí)行結(jié)果:g ;Dacmeirts and. SettingsVAdsinis-tratorV桌面DeTbu.g串5時(shí)壬士于姑個(gè)個(gè)個(gè)個(gè)個(gè)1 2 3 4 5 *辛立串e時(shí)囪的抑阿為 菱宙呂a呂a不 入入入入入串otpy6.2 順序串插入程序：#include #include #define MAXLEN 40typedef struct /* 串結(jié)構(gòu)定義