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

1、实验报告课程名称数据结构姓名学号专业班级指导教师目录第二章线性表的查找、插入、删除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;/*线性表占用的数组空间 */int last; /* 记录线性表中最后一个元素在数组 elem 中的位置（下标值），空表为 -1*/Seqlist;int Locate(Seqlist L,ElemType e)/* 在顺序表 L 中查找与 e 相等的元素，若 L。elemi=e,

3、 则找到该元素，并返回 i+1 ，若找不到，则返回 -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("请输入线性标的长度 :&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、执行结果：错误分析 ：在编写过程中，在编写主函数的时候有落下未编写的，导致运行过程中不识别。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);执行结果：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);执行结果：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/*结点类型定义*/ElemType 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;intflag =1; /*设置一个标志，初值为，当输入"$"时， flag为，

13、建表结束 */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_linklist(&l);printf(" 用尾插法

14、建立单链表 , 请输入链表数据 , 以 a 结束 !n"); CreateFromTail(l);p = l->next;while(p!=NULL)printf("%cn",p->data);p=p->next;return 0;执行结果：错误分析： 在代码的时候忘记分号，导致运行错误；截图如下:2.2单链表的插入程序：#include "common.h"#include "linklist.h"int InsList(LinkList L,int i,ElemType e)/* 在带头结点的单链表L

15、中第 i 个位置插入值为 e 的新结点 s*/Node *pre,*s;int k;pre=L;k=0;/*while(pre!=NULL&&k<i-1) /*从 " 头 " 开始，查找第表未查完且未查到第i-1i-1个结点 */个时重复，找到pre指向第i-1个*/pre=pre->next;k=k+1;/*查找第i-1结点 */if(!pre)/*如当前位置pre为空表已找完还未数到第i 个，说明插入位置不合理*/printf("插入位置不合理!");return ERROR;s=(Node*)malloc(sizeof(

16、Node);s->data=e;/*s->next=pre->next;pre->next=s;/*/*申请一个新的结点S */值 e 置入 s 的数据域 */修改指针，完成插入操作*/return OK;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

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;执行结果：2

18、.3单链表的删除程序：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1#defineERROR 0#defineTRUE1#defineFALSE0typedefcharElemType;typedefstructNode/* 结点类型定义 */ElemTypedata;structNode*next;Node,*LinkList;/*LinkList为结构指针类型 */voidinit_linklist(LinkList*l)/*对单链表进行初始化 */*l=(LinkList)

19、malloc(sizeof(Node);(*l)->next=NULL;voidCreateFromTail(LinkListL)Node*r,*s;charc;intflag=1;/* 设置一个标志，初值为1，当输入 "$"时， flag为 0，建表结束 */r=L;/*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag)/* 循环输入表中元素值，将建立新结点 s 插入表尾 */c=getchar();if(c!='$')s=(Node*)malloc(sizeof(Node);s->data=c;r->

20、;next=s;r=s;elseflag=0;r->next=NULL;/* 将最后一个结点的 next 链域置为空，表示链表的结束*/intDelList(LinkListL,inti,ElemType*e)/* 在带头结点的单链表L 中删除第 i 个元素，并将删除的元素保存到变量*e 中*/Node*pre,*r;intk;pre=L;k=0;while(pre->next!=NULL&&k<i-1)/* 寻找被删除结点i 的前驱结点 i-1 使 p指向它 */pre=pre->next;k=k+1; /*查找第 i-1个结点 */if(!(pre-

21、>next)/*即 while 循环是因为 p->next=NULL 或 i<1 而跳出的 , 而是因为没有找到合法的前驱位置，说明删除位置i 不合法。 */printf("删除结点的位置 i 不合理 !");returnERROR;r=pre->next;pre->next=pre->next->next; /* 修改指针，删除结点 r*/ *e = r->data;free(r);/* 释放被删除的结点所占的内存空间*/printf("成功删除结点 !n");/printf("被删除的元素是

22、:%cn",*e);returnOK;voidmain()LinkListl;Node*p;intflag=0;intx;char*e;init_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*)ma

23、lloc(sizeof(char);DelList(l,x,e);p=l->next;while(p!=NULL)printf("%c",p->data);p=p->next;printf("n");执行结果：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 代表结束

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;执行结果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;执行结果：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("请继续此队头插入一个元素，或者停止插入队列元素，请按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("顺序队列的基本运算操作到此结束了n");exit(0);elseprintf("如果想在此队尾继续出队一个元素，请按1n");scanf("%d",&i);执行结果：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 初始化为一个空的循环队列*/Q->front=Q->rear=0;/* 入队操作 */int

35、 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)/*删除队列的队头元素，用x 返回其值 */if(Q->front=Q->rear)

36、 /*队列为空 */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 YangHuiTriangle(

37、 )int n;int i;int temp;int x;int N;SeqQueue Q;InitQueue(&Q);EnterQueue(&Q,1); /*第一行元素入队 */printf("请输入杨辉三角行数N:");scanf("%d",&N);for(n=2;n<=N;n+)/*产生第n 行元素并入队，同时打印第n-1行的元素 */n-2EnterQueue(&Q,1);/*for(i=1;i<=n-2;i+) /*个元素并入队 */第 n 行的第一个元素入队 */利用队中第n-1 行元素产生第n 行

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

39、;int main()YangHuiTriangle( );执行结果：6.串6.1 字符串的建立程序：#include <stdio.h>#include <malloc.h>#define MAXLEN 40#define MAXLEN 40typedef struct/*串结构定义 */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;执行结果：6.2 顺序串插入程序：#include <stdio.h>#include <stdlib.h>#define MAXLEN 40typedef struct /*串结构定义 */char chMAXLEN;int len;SString;void createstring(S