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

1、實(shí)驗(yàn)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu)姓 名 學(xué) 號(hào) 專業(yè)班級(jí) 指導(dǎo)教師 目錄第二章線性表的查找、插入、刪除11.1順序表的查找11.2順序表的插入21.3順序表的刪除4 單鏈表的建立、插入、刪除62.1 單鏈表的建立（尾插法）62.2 單鏈表的插入82.3 單鏈表的刪除10第三章棧143.1鏈棧143.2 順序棧163.3隊(duì)列183.4楊輝三角20第四章串.234.1字符串的建立.234.2順序串的插入.25 1.線性表的查找、插入、刪除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 /*此處的宏定義常量表示線性表可能達(dá)到的最大長(zhǎng)度*/typedef struct ElemType elemMAXSIZE; /*線性表占用的數(shù)組空間*/int last; /*記錄線性表中最后一個(gè)元素在數(shù)組elem中的位置（下標(biāo)值），空表為-1*/Seqlist;int Locate(Seqlist L,ElemType e) /*在順序表L中查找與e相等的元素，若L。elemi=e,則找到該元素，并返

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

4、;,&r);l.last=r-1;printf("請(qǐng)輸入線性表的各元素值：n");for (i=0;i<=l.last;i+)scanf("%d",&l.elemi);printf("請(qǐng)輸入要查找的元素值:n");scanf("%d",&q);p=Locate(l,q);if(p=-1)printf("在此線性表中沒有該元素!n");elseprintf("該素在線性表中的位置為:%dn",p);執(zhí)行結(jié)果：錯(cuò)誤分析：在編寫過程中，在編寫主函數(shù)的時(shí)

5、候有落下未編寫的，導(dǎo)致運(yùn)行過程中不識(shí)別。1.2順序表的插入程序：#include <stdio.h>#include <stdlib.h>/#include <malloc.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#defineMAXSIZE 100 typedef struct ElemType elemMAXSIZE; int last; SeqList;/#include "common.h"/#include &qu

6、ot;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("表已滿無(wú)法插入");return(ERROR);for(k=L->last;k>=i-1;k-) L->elemk+1=L->elemk;L->elemi-1=e; L->last+;r

7、eturn(OK);void main()SeqList *l;int p,q,r;int i;l=(SeqList*)malloc(sizeof(SeqList);printf("請(qǐng)輸入線性表的長(zhǎng)度:");scanf("%d",&r);l->last = r-1;printf("請(qǐng)輸入線性表的各元素值:n");for(i=0; i<=l->last; i+)scanf("%d",&l->elemi);printf("請(qǐng)輸入要插入的位置:n");scanf

8、("%d",&p);printf("請(qǐng)輸入要插入的元素值: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 OK 1#define ERROR 0#define TRUE 1#

9、define FALSE 0#define ElemType int#defineMAXSIZE 100 typedef struct ElemType elemMAXSIZE; int last; 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->elemk-1 = L-&g

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

11、t;,&l->elemi);printf("請(qǐng)輸入要?jiǎng)h除的元素位置: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 ElemType;typedef struct

12、Node /*結(jié)點(diǎn)類型定義*/ ElemType data; struct Node * next;Node, *LinkList; /* LinkList為結(jié)構(gòu)指針類型*/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)志，初值為，當(dāng)輸入"$"時(shí)，flag為，建表結(jié)束*/ r=L;

13、/*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; else flag=0; r->next=NULL; /*將最后一個(gè)結(jié)點(diǎn)的next鏈域置為空，表示鏈表的結(jié)束*/ int main() LinkList l; Node *p; init_linklist(&l); printf("用尾插

14、法建立單鏈表,請(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é)果：錯(cuò)誤分析：在代碼的時(shí)候忘記分號(hào)，導(dǎo)致運(yùn)行錯(cuò)誤；截圖如下: 2.2 單鏈表的插入程序：#include "common.h"#include "linklist.h"int InsList(LinkList L,int i,ElemType e)/*在帶頭結(jié)點(diǎn)的單鏈表L中第

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

16、/*申請(qǐng)一個(gè)新的結(jié)點(diǎn)S */s->data=e; /*值e置入s的數(shù)據(jù)域*/s->next=pre->next;/*修改指針，完成插入操作*/pre->next=s;return OK;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=

17、p->next;printf("請(qǐng)輸入插入的位置和元素: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 單鏈表的刪除程序：#in

18、clude <stdio.h>#include <stdlib.h>#include <malloc.h>#define OK  1#define ERROR  0#define TRUE 1#define FALSE 0typedef char ElemType;typedef struct Node    /*結(jié)點(diǎn)類型定義*/  

19、;     ElemType data;       struct Node  * next;Node, *LinkList;  /* LinkList為結(jié)構(gòu)指針類型*/ void init_linklist(LinkList *l)/*對(duì)單鏈表進(jìn)行初始化*/       *l=(Link

20、List)malloc(sizeof(Node);       (*l)->next=NULL;void CreateFromTail(LinkList L)       Node *r, *s;       char c;       int 

21、0; flag =1; /*設(shè)置一個(gè)標(biāo)志，初值為1，當(dāng)輸入"$"時(shí)，flag為0，建表結(jié)束*/       r=L;                /*r指針動(dòng)態(tài)指向鏈表的當(dāng)前表尾，以便于做尾插入，其初值指向頭結(jié)點(diǎn)*/       while(fla

22、g)         /*循環(huán)輸入表中元素值，將建立新結(jié)點(diǎn)s插入表尾*/                     c=getchar();             

23、60;if(c!='$')                                   s=(Node*)malloc(sizeof(Node);      

24、0;              s->data=c;                     r->next=s;          &#

25、160;          r=s;                            else          

26、                         flag=0;                     r->next=NULL;&

27、#160;  /*將最后一個(gè)結(jié)點(diǎn)的next鏈域置為空，表示鏈表的結(jié)束*/                       int DelList(LinkList L,int i,ElemType *e)/*在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素，并將刪除的元素保存到變量*e中*/  Node&

28、#160;*pre,*r;int k;pre=L;k=0;while(pre->next!=NULL && k<i-1) /*尋找被刪除結(jié)點(diǎn)i的前驅(qū)結(jié)點(diǎn)i-1使p指向它*/ pre=pre->next; k=k+1; /*查找第i-1個(gè)結(jié)點(diǎn)*/if(!(pre->next)     /* 即while循環(huán)是因?yàn)閜->next=NULL或i<1而跳出的,而是因?yàn)闆]有找到合法的前驅(qū)位置，說明刪除位置i不合法。*/printf("

29、刪除結(jié)點(diǎn)的位置i不合理!");return ERROR;r=pre->next;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()&

30、#160;      LinkList l;       Node *p;       int flag=0;       int x;   char*e;       init_linkl

31、ist(&l);                  printf("請(qǐng)輸入鏈表數(shù)據(jù),以$結(jié)束!n");       CreateFromTail(l);       p = l->next;   

32、    while(p!=NULL)                     printf("%cn",p->data);              p=p->next;

33、0;      printf("請(qǐng)輸入要?jiǎng)h除的元素位置：n");scanf("%d",&x);            e = (char*)malloc(sizeof(char);            DelList(l,x,e)

34、;            p = l->next;                 while(p!=NULL) printf("%c",p->data);       

35、0;      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 node StackElementType data; struct node *next;LinkStackNode;typedef LinkStackNode *LinkSta

36、ck;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,StackElementType *x) LinkStackNode *temp; temp=top-&g

37、t;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("請(qǐng)輸入鏈表的各元素值(輸入0代表結(jié)束):n"); while(flag) scanf("%

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

39、; 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 = p->top; i &

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

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

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

43、void enQueue( SqQueue *&q,ElemType e) if(q->rear+1)%MaxSize=q->front) printf("目前順序隊(duì)列已滿了 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(&quo

44、t;目前此順序隊(duì)列為空n"); else q->front=(q->front+1)%MaxSize; e=q->dataq->front; printf("此次出隊(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); printf("請(qǐng)繼續(xù)此隊(duì)頭插入一個(gè)元素，

45、或者停止插入隊(duì)列元素，請(qǐng)按0n"); 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) printf("順序隊(duì)列的基本運(yùn)算操作到此結(jié)束了n"); exit(0); else printf("如果想在此隊(duì)尾繼續(xù)出隊(duì)一個(gè)元素，請(qǐng)按1n"); scanf(&

46、quot;%d",&i); 執(zhí)行結(jié)果： 5.楊輝三角（1）程序：#include<stdio.h>#include<malloc.h> #define TRUE 1#define FALSE 0#define MAXSIZE 50 /*隊(duì)列的最大長(zhǎng)度*/typedef structint elementMAXSIZE; /* 隊(duì)列的元素空間*/int front; /*頭指針指示器*/int rear; /*尾指針指示器*/SeqQueue;/*初始化操作*/void InitQueue(SeqQueue *Q) /* 將*Q初始化為一個(gè)空的循環(huán)隊(duì)列*

47、/Q->front=Q->rear=0;/*入隊(duì)操作*/int EnterQueue(SeqQueue *Q, int x) /*將元素x入隊(duì)*/if(Q->rear+1)%MAXSIZE=Q->front) /*隊(duì)列已經(jīng)滿了*/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ì)頭元素，用x返回其值*

48、/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); /*操作成功*

49、/void YangHuiTriangle( ) int n;int i;int temp;int x;int N;SeqQueue Q;InitQueue(&Q);EnterQueue(&Q,1); /* 第一行元素入隊(duì)*/printf("請(qǐng)輸入楊輝三角行數(shù) N:");scanf("%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

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

51、tf("n"); 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("請(qǐng)輸入要建立的串的長(zhǎng)度:");scanf("%d&qu

52、ot;,&j);for(i=0; i<j; i+)printf("請(qǐng)輸入串的第%d個(gè)字符:",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(