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

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顺序串的插入.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 /*此处的宏定义常量表示线性表可能达到的最大长度*/typedef struct ElemType 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("请输入线性标的长度:");scanf("%d"

4、;,&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 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("表已满无法插入");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("请输入线性表的长度:");scanf("%d",&r);l->last = r-1;printf("请输入线性表的各元素值:n");for(i=0; i<=l->last; i+)scanf("%d",&l->elemi);printf("请输入要插入的位置:n");scanf

8、("%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 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("请输入线性表的长度:");scanf("%d",&r);l->last = r-1;printf("请输入线性表的各元素值:n");for(i=0; i<=l->last; i+)scanf("%d&quo

11、t;,&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 ElemType;typedef struct

12、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; int flag =1; /*设置一个标志，初值为，当输入"$"时，flag为，建表结束*/ r=L;

13、/*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/ while(flag) /*循环输入表中元素值，将建立新结点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; /*将最后一个结点的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; /*从"头"开始，查找第i-1个结点*/while(pre!=NULL&&k<i-1) /*表未查完且未查到第i-1个时重复，找到pre指向第i-1个*/ pre=pre->next;k=k+1; /*查找第i-1结点*/if(!pre) /*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/ printf("插入位置不合理!");return ERROR;s=(Node*)malloc(sizeof(Node);

16、/*申请一个新的结点S */s->data=e; /*值e置入s的数据域*/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("请输入链表数据,以$结束!n");CreateFromTail(l);p = l->next;while(p!=NULL)printf("%cn",p->data);p=

17、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.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    /*结点类型定义*/  

19、;     ElemType data;       struct Node  * next;Node, *LinkList;  /* LinkList为结构指针类型*/ void init_linklist(LinkList *l)/*对单链表进行初始化*/       *l=(Link

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

21、0; flag =1; /*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/       r=L;                /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/       while(fla

22、g)         /*循环输入表中元素值，将建立新结点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;  /*将最后一个结点的next链域置为空，表示链表的结束*/                       int DelList(LinkList L,int i,ElemType *e)/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/  Node&

28、#160;*pre,*r;int k;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->next)     /* 即while循环是因为p->next=NULL或i<1而跳出的,而是因为没有找到合法的前驱位置，说明删除位置i不合法。*/printf("

29、删除结点的位置i不合理!");return ERROR;r=pre->next;pre->next=pre->next->next;    /*修改指针，删除结点r*/*e = r->data;free(r);    /*释放被删除的结点所占的内存空间*/printf("成功删除结点!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("请输入链表数据,以$结束!n");       CreateFromTail(l);       p = l->next;   

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

33、0;      printf("请输入要删除的元素位置：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");执行结果： 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("请输入链表的各元素值(输入0代表结束):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;执行结果3.2 顺序栈顺序栈进栈程序：#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("请输入长度:"); scanf("%d", &r); printf("请输入各元素值:n"); for (i = 0; i<r; i+) s->top+; scanf("%d", &s-&

41、gt;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 struct ElemType dataMaxSize; int front,rear; /SqQueue; /

42、顺序队列类型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"); else printf("目前此顺序队列非空n");/进队列

43、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(&quo

44、t;目前此顺序队列为空n"); else q->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("请继续此队头插入一个元素，

45、或者停止插入队列元素，请按0n"); scanf("%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); else printf("如果想在此队尾继续出队一个元素，请按1n"); scanf(&

46、quot;%d",&i); 执行结果： 5.杨辉三角（1）程序：#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初始化为一个空的循环队列*

47、/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) /*删除队列的队头元素，用x返回其值*

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

49、/void YangHuiTriangle( ) 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行的元素*/EnterQueue(&Q,1); /* 第n行的第一个元素入队*/for(i=1;i<=n-2;i+) /* 利用队中第n

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

51、tf("n"); 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&qu

52、ot;,&j);for(i=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(