數(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 #include#include#define OK 1#define ERROR 0#de

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

3、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)的長度 :);scanf(%d,&r);精選資料，歡迎下載。l.last=r-1;printf(請(qǐng)輸入線性表的各元素值：n)

4、;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í)候有落下未編寫的，導(dǎo)致運(yùn)行過程中不識(shí)別。1.2 順序表的插入程序：#include #include /#include #define OK1#define ERROR 0#define TRUE 1精選資料，歡迎下載。#define FALSE

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

6、emk+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)輸入線性表的長度 :);scanf(%d,&r);l-last = r-1;printf(請(qǐng)輸入線性表的各元素值:n);精選資料，歡迎下載。for(i=0; ilast; i+)scanf(%d,&l-elemi);printf(請(qǐng)輸入要插入的位置 :n);scanf(%d,&p);printf(請(qǐng)輸入要插入的元素值 :n);scanf(%d,&

7、q);InsList(l,p,q);for(i=0; ilast; i+)printf(%d ,l-elemi);執(zhí)行結(jié)果：1.3 順序表的刪除程序：#include #include #include #define OK1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#defineMAXSIZE 100typedef struct精選資料，歡迎下載。ElemType elemMAXSIZE;intlast;SeqList;int DelList(SeqList *L,int i,ElemType *e)int

8、 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)輸入線性表的長度 :);scanf(%d,&r);l-last = r-1;printf(請(qǐng)輸入線性表的各元素值:n);fo

9、r(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é)果：精選資料，歡迎下載。2. 單鏈表的建立 、插入、刪除2.1單鏈表的建立（尾插法）程序：#include#include#define ERROR 0#define TRUE 1#define FALSE 0typedef char ElemType;typedef struct Node/*結(jié)點(diǎn)類型定義 */ElemType data;struct Node * ne

10、xt;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;intflag =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)輸入表中元

11、素值，將建立新結(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_linklist(&l);printf( 用尾插法建立單鏈表 , 請(qǐng)輸入鏈表數(shù)據(jù) , 以 a 結(jié)束 !n); CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-nex

12、t;return 0;執(zhí)行結(jié)果：精選資料，歡迎下載。錯(cuò)誤分析：在代碼的時(shí)候忘記分號(hào)，導(dǎo)致運(yùn)行錯(cuò)誤；截圖如下:2.2單鏈表的插入程序：#include common.h#include linklist.hint InsList(LinkList L,int i,ElemType e)/* 在帶頭結(jié)點(diǎn)的單鏈表L 中第 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&knext;k=k+1;/* 查找第 i-1結(jié)點(diǎn) */if(!pre)/*如當(dāng)前位置 pre 為空表已找完還

13、未數(shù)到第i 個(gè)，說明插入位置不合理 */printf(插入位置不合理 !);return ERROR;s=(Node*)malloc(sizeof(Node);/*申請(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

14、;while(p!=NULL)printf(%cn,p-data);p=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單鏈表的刪除程序：#include#include#include#defineOK1#defineERROR 0#def

15、ineTRUE1#defineFALSE0typedefcharElemType;typedefstructNode/* 結(jié)點(diǎn)類型定義 */ElemTypedata;structNode*next;Node,*LinkList;/*LinkList為結(jié)構(gòu)指針類型 */voidinit_linklist(LinkList*l)/*對(duì)單鏈表進(jìn)行初始化 */*l=(LinkList)malloc(sizeof(Node);(*l)-next=NULL;精選資料，歡迎下載。voidCreateFromTail(LinkListL)Node*r,*s;charc;intflag=1;/* 設(shè)置一個(gè)標(biāo)志，

16、初值為1，當(dāng)輸入 $時(shí)， flag為 0，建表結(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!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s;elseflag=0;精選資料，歡迎下載。r-next=NULL;/* 將最后一個(gè)結(jié)點(diǎn)的 next 鏈域置為空，表示鏈表的結(jié)束*/intDelList(LinkListL,inti,ElemType*e)/* 在帶頭結(jié)點(diǎn)的單鏈表 L 中刪除第

17、i 個(gè)元素，并將刪除的元素保存到變量 *e 中 */Node*pre,*r;intk;pre=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);returnOK;voidmain()LinkL

18、istl;精選資料，歡迎下載。Node*p;intflag=0;intx;char*e;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)輸入要?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é)果

19、：精選資料，歡迎下載。3.棧3.1 鏈棧程序：#include#include#define TRUE 1#define FALSE 0#define StackElementType inttypedef struct nodeStackElementType data;struct node *next;LinkStackNode;typedef LinkStackNode *LinkStack;int Push(LinkStack top,StackElementType x)LinkStackNode *temp;temp=(LinkStackNode *)malloc(sizeof(

20、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=temp-data;free(temp);return(TRUE);int main()LinkStackNode *top;to

21、p=(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);elseflag=0;while(top-next!=NULL)Pop(top,&x);printf(%dt,x);printf(n);精選資料，歡迎下載。return 0;執(zhí)行結(jié)果3.2順序棧順序棧進(jìn)棧程序：#include#include #include #defi

22、ne stack_size 50typedef 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-toptop; i = 0; i-)printf(%d, p-elemi);int main()int

23、 a;int i, r;seqstack *s;s = (seqstack*)malloc(sizeof(seqstack);initstack(s);printf(請(qǐng)輸入長度 :);scanf(%d, &r);printf(請(qǐng)輸入各元素值 :n);for (i = 0; itop+;scanf(%d, &s-elemi);printf(請(qǐng)輸入要進(jìn)棧的值： );scanf(%d, &a);push(s, a);OutStack(s);return 0;執(zhí)行結(jié)果：精選資料，歡迎下載。4.隊(duì)列順序隊(duì)列基本操作：#include#include#include#define MaxSize 20ty

24、pedef int ElemType;typedef structElemType dataMaxSize;int front,rear;/SqQueue;/順序隊(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

25、);elseprintf(目前此順序隊(duì)列非空 n);/ 進(jìn)隊(duì)列void enQueue( SqQueue *&q,ElemType e)if(q-rear+1)%MaxSize=q-front)printf(目前順序隊(duì)列已滿了n);elseq-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)%Ma

26、xSize;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è)元素，或者停止插入隊(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-fro

27、nt=q-rear)printf(順序隊(duì)列的基本運(yùn)算操作到此結(jié)束了n);exit(0);elseprintf(如果想在此隊(duì)尾繼續(xù)出隊(duì)一個(gè)元素，請(qǐng)按1n);精選資料，歡迎下載。scanf(%d,&i);執(zhí)行結(jié)果：5.楊輝三角（ 1）程序：#include#include#define TRUE 1#define FALSE 0#define MAXSIZE 50 /*隊(duì)列的最大長度 */typedef structint elementMAXSIZE; /*隊(duì)列的元素空間 */int front; /*頭指針指示器 */int rear; /*尾指針指示器 */SeqQueue;/* 初始化操作

28、 */精選資料，歡迎下載。void InitQueue(SeqQueue *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)滿了 */ return(FALSE);Q-elementQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE; /*重新設(shè)置隊(duì)尾指針 */return(TRUE); /*操作成功 */* 出隊(duì)操作 */int DeleteQueue(Se

29、qQueue *Q, int *x)/* 刪除隊(duì)列的隊(duì)頭元素，用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); /

30、*操作成功 */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-1 行元素產(chǎn)生第n 行的中間n-2 個(gè)元素并入隊(duì) */Del

31、eteQueue(&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ì) */ printf(n);int main()YangHuiTriangle( );執(zhí)行結(jié)果：精選資料，歡迎下載。6.串6.1 字符串的建立程序：#include #

32、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)輸入要建立的串的長度:);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);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 順序串插入程序：#i