数据结构线性表单链表的查找、插入、删除

1、实验报告课程名称姓 名学 号专业班级数据结构指导教师目录第二章线性表的查找、插入、删除 11.1 顺序表的查找 11.2 顺序表的插入 21.3 顺序表的删除 4单链表的建立、插入、删除 . 62.1 单链表的建立（尾插法） 62.2 单链表的插入 82.3 单链表的删除 10第三章栈 143.1 链栈 143.3 队列 . 3.4 杨辉三角 第四章串4.1 字符串的建立4.2 顺序串的插入3.2 顺序栈 1618. 20 2323251.线性表的查找、插入、删除1.1 顺序表的查找程序：#include #include #include#define OK 1 #define ERROR

2、0#define TRUE 1#define FALSE 0 #define ElemType int#define MAXSIZE 100 /* 此处的宏定义常量表示线性表可能达到的最大长度 */typedef structElemType elemMAXSIZE; /* 线性表占用的数组空间 */ int last; /* 记录线性表中最后一个元素在数组 elem 中的位置(下 标值)，空表为 -1*/Seqlist;int Locate(Seqlist L,ElemType e)/*在顺序表L中查找与e相等的元素，若L。elemi=e,则找到该元素，并返回 i+1 ，若找不到，则返回 -

3、1*/ int i=0; /*i 为扫描计数器，初值为 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( 请输入线性标的长度 :);scanf(%d,&r);I.last=r-1;prin tf(请输入线性表的各元素值：n)

4、;for (i=O;i=I.Iast;i+)sca nf(%d,&l.elemi);printf(请输入要查找的元素值:n);sca nf(%d,&q);p=Locate(l,q);if(p=-1)printf(在此线性表中没有该元素!n);elseprintf(该素在线性表中的位置为:%dn,p);执行结果:错误分析 :在编写过程中，在编写主函数的时候有落下未编写的，导致运行过程中不 识别。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( 表已满无法插入 ); 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( 请输入线性表的长度 :); scanf(%d,&r);l-last = r-1;printf( 请输入线性表的各元素值 :n);for(i=0; ilast; i+)sca nf(%d,&l-elemi);printf(请输入要插入的位置:n);scan f(%d,&p);printf(请输入要插入的元素值:n);scan f(

7、%d,&q);In sList(l,p,q);for(i=0; ilast; i+)prin tf(%d ,l-elemi);执行结果：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( 请输入线性表的长度 :); scanf(%d,&r);l-last = r-1;printf( 请输入

9、线性表的各元素值 :n); for(i=0; ilast; i+) scanf(%d,&l-elemi);printf( 请输入要删除的元素位置 :n); scanf(%d,&p);DelList(l,p,q);printf( 删除的元素值为 :%dn,*q); 执行结果：H flC:UscrsW，. - X请输入线性恚的长度;6 请输入线性表的各元素值：12 25 12 65 15 65 请输入要删除的元素位置：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 /*结点类型定义 */ElemType data;struct Node * n ext;Node, *LinkList; /* LinkList为结构指针类型 */void init_linklist(LinkList *1)/*对单链表进行初始化 */ _*l=(Li nkList)malloc(sizeof(Node);(*l)- next=NULL;void CreateFromTail(Li nkList L)Node *

11、r, *s;char c;int flag =1; /*设置一个标志，初值为，当输入$时，flag为，建表结束*/r=L;/*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点 */while(flag) /* 循环输入表中元素值，将建立新结点 s 插入表尾 */c=getchar();if(c!=a)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s;elseflag=0;r-next=NULL; /* 将最后一个结点的 next 链域置为空，表示 链表的结束 */int main()LinkList l;Node *p;init

12、_linklist(&l);printf( 用尾插法建立单链表 , 请输入链表数据 , 以 a 结束 !n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;return 0;执行结果：匚:Usc冷奏轡DktopDcb用尾插法建立单链表，请输人链表数据，以a结束!156 26 56 23 122a13ress any key tc continue错误分析： 在代码的时候忘记分号，导致运行错误；截图如下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)/*在带头结点的单链表L中第i个位置插入值为e的新结点s*/Node *pre,*s;int k;pre=L;k=0;/*从头开始，查找第i-1个结点*/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;/*如当前位置 pre/* 查找第 i-1 结点 */ 为空表已找完还未数到第 i 个，说明插入申请一个新的结点 S */值 e 置入 s 的数据域 */* 修改指针，完成插入操作 */void main()LinkList l;Node *p;int flag=0;int i;char c;init_linklist(&l);printf(请输入链表数据,以$结束!n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;printf( 请输入插入的位置和元

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;执行结果：2.3 单链表的删除程序：#include#include#include#defineOK 1#defineERROR 0#defineTRUE 1#defineFALSE 0/* 结点类型定义 */typedef char ElemType; typede

16、f struct NodeElemType data;struct Node * next;Node, *LinkList; /* LinkList 为结构指针类型 */ void init_linklist(LinkList *l)/* 对单链表进行初始化 */*l=(LinkList)malloc(sizeof(Node);(*l)-next=NULL;void CreateFromTail(LinkList L)Node *r, *s;char c;int flag =1; /* 设置一个标志，初值为 1，当输入 $ 时， flag 为 0，建表结束 */r=L; /*r 指针动态指向链

17、 表的当前表尾，以便于做尾插入，其初值指向头结点 */while(flag) /* 循环输入表中元素值，将建 立新结点 s 插入表尾 */c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node );s-data=c;r-next=s;r=s;elseflag=0;r-next=NULL; /* 将最后 一个结点的 next 链域置为空，表示链表的结束 */int DelList(LinkList L,int i,ElemType *e)/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/Node *pre,*r;int k;pre

18、=L;k=0;while(pre-next!=NULL & knext;k=k+1; /* 查找第 i-1 个结点 */if(!(pre-next)/* 即 while 循环是因为 p-next=NULL 或 inext;pre-next=pre-next-next;/* 修改指针，删除结点 r*/*e = r-data;free(r);/* 释放被删除的结点所占的内存空间 */printf( 成功删除结点 !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(请输入链表数据,以$结束!n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;printf( 请输入要删除的元素位置： 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);执行结果： ,C;UscrsWDesktopDcbug1 ,exc-f请输入链表数摇，以

20、S结束！12 23 4$1234请输入要则除的元素位置：2成功删除结点！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( 请输入链表的各元素值 (输入 0 代表结束 ):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;执行结果 1 C ;U scD eskto pDc bu g1 * exe X卩青输入链表的各兀素值(输入0代表结束丿:1 25 2 32 65 66006065322251Press any key to continup3.2顺序栈顺序栈进栈程序：#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(请输入长度:);scan f(%d, &r);printf(请输入各元素值:n);for (i =

25、 0; itop+;scanf(%d, &s-elemi);printf(请输入要进栈的值：);scan f(%d, & a);push(s, a);OutStack(s);return 0;执行结果: 1 C;UscrsDesktopDcbug1 ,exe X请输入长嗟;5卩青输入各元素值：12 23 32 45 56 阳输入要进栈的值:445645322312 Press any key to continue4. 队列顺序队列基本操作：#include#include #include #define MaxSize 20 typedef int ElemType; typedef st

26、ruct ElemType dataMaxSize; int front,rear; /SqQueue;/顺序队列类型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( 目前此顺序队列非

27、空 n);/ 进队列void enQueue( SqQueue *&q,ElemType e) if(q-rear+1)%MaxSize=q-front) printf( 目前顺序队列已满了 n);else q-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);elseq-front=(q-front+1)%MaxSize;e=q-dataq-front;p

28、rintf( 此次出队元素是 :%dn,e);void main()SqQueue *q;int e;InitQueue(q);QueueEmpty(q);printf( 请在此队头插入一个元素 :n);scanf(%d,&e);while(e!=0)enQueue(q,e);0n);printf( 请继续此队头插入一个元素，或者停止插入队列元素，请按 scanf(%d,&e);QueueEmpty(q);int i;printf( 如果想在此队尾出队一个元素，请按 1n); scanf(%d,&i);while(i=1)deQueue(q,e);if(q-front=q-rear)print

29、f( 顺序队列的基本运算操作到此结束了 n);exit(0);elseprintf( 如果想在此队尾继续出队一个元素，请按 1n);sea nf(%d,&i);执行结果:5. 杨辉三角(i)程序：#i nclude#i nclude#defi ne TRUE 1#defi ne FALSE 0#define MAXSIZE 50 /* 队列的最大长度*/typedef structint elementMAXSIZE; /*队列的元素空间 */int front; /*头指针指示器*/int rear; /* 尾指针指示器*/SeqQueue;/*初始化操作*/void InitQueue(S

30、eqQueue *Q)/*将*Q初始化为一个空的循环队列*/Q-front=Q-rear=0;/* 入队操作 */int EnterQueue(SeqQueue *Q, int x)/* 将元素 x 入队*/if(Q-rear+1)%MAXSIZE=Q-front) /* 队列已经满了 */ return(FALSE);Q-elementQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE; /* 重新设置队尾指针 */ return(TRUE); /* 操作成功 */* 出队操作 */ int DeleteQueue(SeqQueue *Q, int *x)/* 删除队列的队

31、头元素，用 x 返回其值 */ if(Q-front=Q-rear) /* 队列为空 */ return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE; /* 重新设置队头指针 */ return(TRUE); /* 操作成功 */int GetHead(SeqQueue *Q, int *x)/* 提取队列的队头元素，用 x 返回其值 */ if(Q-front=Q-rear) /* 队列为空 */ 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); /* 第一行元素入队 */ printf( 请输入杨辉三角行数 N:);sea nf(%d,&N);for(n=2;n=N;n+) /* 产生第n行元素并入队，同时打印第n-1行的元素*/EnterQueue(&Q,1); /* 第n行的第一个元素入队*/ for(i=1;i=n-2;i+) /*利用队中第n-1行元素产生第n行的中间n-2个元素并入队*/DeleteQueue(&Q,& temp);printf

33、(%6d,temp);/*打印第 n-1 行的元素 */GetHead(&Q, &x);temp=temp+x; /* 利用队中第n-1行元素产生第n行元素*/ En terQueue(&Q,temp);DeleteQueue (&Q,& x);printf(%6d,x);/*打印第n-1行的最后一个元素*/EnterQueue(&Q,1); /* 第n行的最后一个元素入队*/ prin tf(n);int mai n()Yan gHuiTria ngle();12Q165220286-1 u127810220715194订16549S 12871721Wft执行结果:l日冊闻M號同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 /* 串结构定义 */ char chMAXLEN;int len;SString;void createstring(SString *s)int i,j;char c;printf( 请输

35、入要建立的串的长度 :); 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;执行结果:g ;Dacmeirts and. SettingsVAdsinis-tratorV桌面DeTbu.g串5时壬士于姑个个个个个1 2 3 4 5 *辛立串e时囱的抑阿为 菱宙呂a吕a不 入入入入入串otpy6.2 顺序串插入程序：#include #include #define MAXLEN 40typedef struct /* 串结构定义