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

1、實驗報告課程名稱數(shù)據(jù)結(jié)構(gòu)姓名學號專業(yè)班級指導教師目錄第二章線性表的查找、插入、刪除11.1 順序表的查找11.2 順序表的插入21.3 順序表的刪除4單鏈表的建立、插入、刪除.62.1 單鏈表的建立（尾插法）62.2 單鏈表的插入82.3 單鏈表的刪除10第三章棧143.1 鏈棧143.2順序棧163.3 隊列 .183.4 楊輝三角20第四章串 .234.1 字符串的建立234.2 順序串的插入251.線性表的查找、插入、刪除1.1 順序表的查找程序：#include <stdio.h>#include<stdlib.h>#include<malloc.h>

2、;#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#define MAXSIZE 100 /*此處的宏定義常量表示線性表可能達到的最大長度*/typedef structElemType elemMAXSIZE;/*線性表占用的數(shù)組空間 */int last; /* 記錄線性表中最后一個元素在數(shù)組 elem 中的位置（下標值），空表為 -1*/Seqlist;int Locate(Seqlist L,ElemType e)/* 在順序表 L 中查找與 e 相等的元素，若 L。elemi=e,

3、 則找到該元素，并返回 i+1 ，若找不到，則返回 -1*/ int i=0; /*i為掃描計數(shù)器，初值為 0，即從第一個元素開始比較 */while (i<=L.last)&&(L.elemi!=e)/* 順序掃描表，直到找到值為 e 的元素，或掃描到表尾仍沒找到 */ i+;if(i<=L.last)return (i+1); /* 若找到值為 e 的元素，則返回其序號 */ elsereturn(-1);/*若沒找到，則返回空序號*/void main()Seqlist l;int p,q,r;int i;printf("請輸入線性標的長度 :&qu

4、ot;);scanf("%d",&r);l.last=r-1;printf("請輸入線性表的各元素值：n");for (i=0;i<=l.last;i+)scanf("%d",&l.elemi);printf("請輸入要查找的元素值 :n");scanf("%d",&q);p=Locate(l,q);if(p=-1)printf("在此線性表中沒有該元素!n");elseprintf("該素在線性表中的位置為:%dn",p);

5、執(zhí)行結(jié)果：錯誤分析 ：在編寫過程中，在編寫主函數(shù)的時候有落下未編寫的，導致運行過程中不識別。1.2 順序表的插入程序：#include <stdio.h>#include <stdlib.h>/#include <malloc.h>#define OK1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#defineMAXSIZE 100typedef structElemType elemMAXSIZE;intlast;SeqList;/#include "common

6、.h"/#include "seqlist.h"int InsList(SeqList *L,int i,ElemType e)int k;if(i<1) | (i>L->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->el

7、emi-1=e;L->last+;return(OK);void main()SeqList *l;int p,q,r;int i;l=(SeqList*)malloc(sizeof(SeqList);printf("請輸入線性表的長度 :");scanf("%d",&r);l->last = r-1;printf("請輸入線性表的各元素值:n");for(i=0; i<=l->last; i+)scanf("%d",&l->elemi);printf("請輸

8、入要插入的位置 :n");scanf("%d",&p);printf("請輸入要插入的元素值 :n");scanf("%d",&q);InsList(l,p,q);for(i=0; i<=l->last; i+)printf("%d ",l->elemi);執(zhí)行結(jié)果：1.3 順序表的刪除程序：#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define OK1#defin

9、e ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#defineMAXSIZE 100typedef structElemType elemMAXSIZE;intlast;SeqList;int DelList(SeqList *L,int i,ElemType *e)int k;if(i<1)|(i>L->last+1)printf("刪除位置不合法 !");return(ERROR);*e = L->elemi-1;for(k=i; i<=L->last; k+)L-&

10、gt;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("請輸入線性表的長度 :");scanf("%d",&r);l->last = r-1;printf("請輸入線性表的各元素值:n");for(i=0; i<=l->last; i+)s

11、canf("%d",&l->elemi);printf("請輸入要刪除的元素位置:n");scanf("%d",&p);DelList(l,p,q);printf("刪除的元素值為 :%dn",*q);執(zhí)行結(jié)果：2.單鏈表的建立 、插入 、刪除2.1單鏈表的建立（尾插法）程序：#include<stdio.h>#include<stdlib.h>#define ERROR 0#define TRUE 1#define FALSE 0typedef char ElemTy

12、pe;typedef struct Node/*結(jié)點類型定義*/ElemType data;struct Node * next;Node, *LinkList; /* LinkList void init_linklist(LinkList *l)/*為結(jié)構(gòu)指針類型 */對單鏈表進行初始化*/*l=(LinkList)malloc(sizeof(Node);(*l)->next=NULL;void CreateFromTail(LinkList L)Node *r, *s;char c;intflag =1; /*設(shè)置一個標志，初值為，當輸入"$"時， flag為，

13、建表結(jié)束 */r=L;/*r指針動態(tài)指向鏈表的當前表尾，以便于做尾插入，其初值指向頭結(jié)點 */while(flag)/*循環(huán)輸入表中元素值，將建立新結(jié)點s 插入表尾*/c=getchar();if(c!='a')s=(Node*)malloc(sizeof(Node);s->data=c;r->next=s;r=s;elseflag=0;r->next=NULL;/*將最后一個結(jié)點的next 鏈域置為空，表示鏈表的結(jié)束 */int main()LinkList l;Node *p;init_linklist(&l);printf(" 用尾插法

14、建立單鏈表 , 請輸入鏈表數(shù)據(jù) , 以 a 結(jié)束 !n"); CreateFromTail(l);p = l->next;while(p!=NULL)printf("%cn",p->data);p=p->next;return 0;執(zhí)行結(jié)果：錯誤分析： 在代碼的時候忘記分號，導致運行錯誤；截圖如下:2.2單鏈表的插入程序：#include "common.h"#include "linklist.h"int InsList(LinkList L,int i,ElemType e)/* 在帶頭結(jié)點的單鏈表L

15、中第 i 個位置插入值為 e 的新結(jié)點 s*/Node *pre,*s;int k;pre=L;k=0;/*while(pre!=NULL&&k<i-1) /*從 " 頭 " 開始，查找第表未查完且未查到第i-1i-1個結(jié)點 */個時重復(fù)，找到pre指向第i-1個*/pre=pre->next;k=k+1;/*查找第i-1結(jié)點 */if(!pre)/*如當前位置pre為空表已找完還未數(shù)到第i 個，說明插入位置不合理*/printf("插入位置不合理!");return ERROR;s=(Node*)malloc(sizeof(

16、Node);s->data=e;/*s->next=pre->next;pre->next=s;/*/*申請一個新的結(jié)點S */值 e 置入 s 的數(shù)據(jù)域 */修改指針，完成插入操作*/return OK;void main()LinkList l;Node *p;int flag=0;int i;char c;init_linklist(&l);printf("請輸入鏈表數(shù)據(jù) , 以$結(jié)束 !n");CreateFromTail(l);p = l->next;while(p!=NULL)printf("%cn",p

17、->data);p=p->next;printf("請輸入插入的位置和元素: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

18、.3單鏈表的刪除程序：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1#defineERROR 0#defineTRUE1#defineFALSE0typedefcharElemType;typedefstructNode/* 結(jié)點類型定義 */ElemTypedata;structNode*next;Node,*LinkList;/*LinkList為結(jié)構(gòu)指針類型 */voidinit_linklist(LinkList*l)/*對單鏈表進行初始化 */*l=(LinkList)

19、malloc(sizeof(Node);(*l)->next=NULL;voidCreateFromTail(LinkListL)Node*r,*s;charc;intflag=1;/* 設(shè)置一個標志，初值為1，當輸入 "$"時， flag為 0，建表結(jié)束 */r=L;/*r指針動態(tài)指向鏈表的當前表尾，以便于做尾插入，其初值指向頭結(jié)點*/while(flag)/* 循環(huán)輸入表中元素值，將建立新結(jié)點 s 插入表尾 */c=getchar();if(c!='$')s=(Node*)malloc(sizeof(Node);s->data=c;r->

20、;next=s;r=s;elseflag=0;r->next=NULL;/* 將最后一個結(jié)點的 next 鏈域置為空，表示鏈表的結(jié)束*/intDelList(LinkListL,inti,ElemType*e)/* 在帶頭結(jié)點的單鏈表L 中刪除第 i 個元素，并將刪除的元素保存到變量*e 中*/Node*pre,*r;intk;pre=L;k=0;while(pre->next!=NULL&&k<i-1)/* 尋找被刪除結(jié)點i 的前驅(qū)結(jié)點 i-1 使 p指向它 */pre=pre->next;k=k+1; /*查找第 i-1個結(jié)點 */if(!(pre-

21、>next)/*即 while 循環(huán)是因為 p->next=NULL 或 i<1 而跳出的 , 而是因為沒有找到合法的前驅(qū)位置，說明刪除位置i 不合法。 */printf("刪除結(jié)點的位置 i 不合理 !");returnERROR;r=pre->next;pre->next=pre->next->next; /* 修改指針，刪除結(jié)點 r*/ *e = r->data;free(r);/* 釋放被刪除的結(jié)點所占的內(nèi)存空間*/printf("成功刪除結(jié)點 !n");/printf("被刪除的元素是

22、:%cn",*e);returnOK;voidmain()LinkListl;Node*p;intflag=0;intx;char*e;init_linklist(&l);printf("請輸入鏈表數(shù)據(jù) , 以$結(jié)束 !n");CreateFromTail(l);p=l->next;while(p!=NULL)printf("%cn",p->data);p=p->next;printf("請輸入要刪除的元素位置：n");scanf("%d",&x);e=(char*)ma

23、lloc(sizeof(char);DelList(l,x,e);p=l->next;while(p!=NULL)printf("%c",p->data);p=p->next;printf("n");執(zhí)行結(jié)果：3.棧3.1 鏈棧程序：#include<stdio.h>#include<malloc.h>#define TRUE 1#define FALSE 0#define StackElementType inttypedef struct nodeStackElementType data;struct no

24、de *next;LinkStackNode;typedef LinkStackNode *LinkStack;int Push(LinkStack top,StackElementType x)LinkStackNode *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,StackEle

25、mentType *x)LinkStackNode *temp;temp=top->next;if(temp=NULL)return(FALSE);top->next=temp->next;*x=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(" 請輸入鏈表的各元素值 ( 輸入 0 代表結(jié)束

26、):n"); while(flag)scanf("%d",&a);if(a!=0)Push(top,a);elseflag=0;while(top->next!=NULL)Pop(top,&x);printf("%dt",x);printf("n");return 0;執(zhí)行結(jié)果3.2順序棧順序棧進棧程序：#include<stdio.h>#include <stdlib.h>#include <malloc.h>#define stack_size 50typedef

27、 structint elemstack_size;int top;seqstack;void initstack(seqstack *s)s->top = -1;int push(seqstack *s, int 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->top<0)printf("This is a EmptyStack!n");for (i =

28、 p->top; i >= 0; i-)printf("%d", p->elemi);int main()int a;int i, r;seqstack *s;s = (seqstack*)malloc(sizeof(seqstack);initstack(s);printf("請輸入長度 :");scanf("%d", &r);printf("請輸入各元素值 :n");for (i = 0; i<r; i+)s->top+;scanf("%d", &

29、;s->elemi);printf("請輸入要進棧的值： ");scanf("%d", &a);push(s, a);OutStack(s);return 0;執(zhí)行結(jié)果：4.隊列順序隊列基本操作：#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define MaxSize 20typedef int ElemType;typedef structElemType dataMaxSize;int front,rear;/SqQueue;/順序隊列類

30、型SqQueue的定義/ 初始化隊列void InitQueue(SqQueue *&q)q=(SqQueue *)malloc(sizeof(SqQueue);q->front=q->rear=0;/ 銷毀隊列void ClearQueue(SqQueue *&q)free(q);/ 判斷順序隊列是否為空void QueueEmpty(SqQueue *q)if(q->front=q->rear)printf("目前此順序隊列為空 n");elseprintf("目前此順序隊列非空 n");/ 進隊列void e

31、nQueue( SqQueue *&q,ElemType e)if(q->rear+1)%MaxSize=q->front)printf("目前順序隊列已滿了n");elseq->rear=(q->rear+1)%MaxSize;q->dataq->rear=e;printf("此次進隊元素是 :%dn",e);/ 出隊列void deQueue(SqQueue *&q,ElemType &e)if(q->front=q->rear)printf("目前此順序隊列為空 n&

32、quot;);elseq->front=(q->front+1)%MaxSize;e=q->dataq->front;printf("此次出隊元素是 :%dn",e);void main()SqQueue *q;int e;InitQueue(q);QueueEmpty(q);printf("請在此隊頭插入一個元素:n");scanf("%d",&e);while(e!=0)enQueue(q,e);printf("請繼續(xù)此隊頭插入一個元素，或者停止插入隊列元素，請按0n");sca

33、nf("%d",&e);QueueEmpty(q);int i;printf("如果想在此隊尾出隊一個元素，請按1n");scanf("%d",&i);while(i=1)deQueue(q,e);if(q->front=q->rear)printf("順序隊列的基本運算操作到此結(jié)束了n");exit(0);elseprintf("如果想在此隊尾繼續(xù)出隊一個元素，請按1n");scanf("%d",&i);執(zhí)行結(jié)果：5.楊輝三角（ 1）程序

34、：#include<stdio.h>#include<malloc.h>#define TRUE 1#define FALSE 0#define MAXSIZE 50 /*隊列的最大長度 */typedef structint elementMAXSIZE; /*隊列的元素空間 */int front; /*int rear; /*頭指針指示器 */尾指針指示器 */SeqQueue;/*初始化操作*/void InitQueue(SeqQueue *Q)/*將*Q 初始化為一個空的循環(huán)隊列*/Q->front=Q->rear=0;/* 入隊操作 */int

35、 EnterQueue(SeqQueue *Q, int x)/* 將元素 x 入隊 */if(Q->rear+1)%MAXSIZE=Q->front) /* 隊列已經(jīng)滿了 */ return(FALSE);Q->elementQ->rear=x;Q->rear=(Q->rear+1)%MAXSIZE; /*重新設(shè)置隊尾指針 */return(TRUE); /*操作成功 */* 出隊操作 */int DeleteQueue(SeqQueue *Q, int *x)/*刪除隊列的隊頭元素，用x 返回其值 */if(Q->front=Q->rear)

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

37、 )int n;int i;int temp;int x;int N;SeqQueue Q;InitQueue(&Q);EnterQueue(&Q,1); /*第一行元素入隊 */printf("請輸入楊輝三角行數(shù)N:");scanf("%d",&N);for(n=2;n<=N;n+)/*產(chǎn)生第n 行元素并入隊，同時打印第n-1行的元素 */n-2EnterQueue(&Q,1);/*for(i=1;i<=n-2;i+) /*個元素并入隊 */第 n 行的第一個元素入隊 */利用隊中第n-1 行元素產(chǎn)生第n 行

38、的中間DeleteQueue(&Q,&temp);printf("%6d",temp);/*打印第GetHead(&Q,&x);temp=temp+x;/*利用隊中第 n-1EnterQueue(&Q,temp);n-1 行的元素 */行元素產(chǎn)生第n 行元素 */DeleteQueue (&Q,&x);printf("%6d",x); /* EnterQueue(&Q,1); /*打印第 n-1 行的最后一個元素第 n 行的最后一個元素入隊 */*/printf("n")

39、;int main()YangHuiTriangle( );執(zhí)行結(jié)果：6.串6.1 字符串的建立程序：#include <stdio.h>#include <malloc.h>#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("請輸入要建立的串的長度:");scanf("%d",&j);for(i=

40、0; i<j; i+)printf("請輸入串的第 %d個字符 :",i+1);fflush(stdin);scanf("%c",&c);s->chi = c;s->len = j;void output(SString *s)int i;for (i=0;i<s->len;i+)printf("%c",s->chi);printf("n");int StrEmpty(SString s)/* 若串 s 為空則返回，否則返回 */if (s.len=0)return(1)

41、;elsereturn(0);int main()SString str2;int flag=0;printf("建立字符串 !n");createstring(&str2);flag=StrEmpty(str2);if(flag = 1)printf("字符串為空 !");elseprintf("字符串不為空 !n");output(&str2);return 0;執(zhí)行結(jié)果：6.2 順序串插入程序：#include <stdio.h>#include <stdlib.h>#define MAXLEN 40typedef struct /*串結(jié)構(gòu)定義 */char chMAXLEN;int len;SString;void createstring(S