实验报告课程名称数据结构姓名学号专业班级指导教师目录第二章线性表的查找、插入、删除 (1)1.1顺序表的查找 (1)1.2顺序表的插入 (2)1.3顺序表的删除 (4)单链表的建立、插入、删除 (6)2.1 单链表的建立（尾插法） (6)2.2 单链表的插入 (8)2.3 单链表的删除 (10)第三章栈 (14)3.1链栈 (14)3.2 顺序栈 (16)3.3队列 (18)3.4杨辉三角 (20)第四章串 (23)4.1字符串的建立 (23)4.2顺序串的插入 (25)1.线性表的查找、插入、删除1.1顺序表的查找程序：#include <stdio.h>#include<stdlib.h>#include<malloc.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/typedef struct{ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/int last; /*记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表为-1*/}Seqlist;int Locate(Seqlist L,ElemType e)/*在顺序表L中查找与e相等的元素，若L。

elem[i]=e,则找到该元素，并返回i+1，若找不到，则返回-1*/{ int i=0; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/while ((i<=st)&&(L.elem[i]!=e))/*顺序扫描表，直到找到值为e的元素，或扫描到表尾仍没找到*/i++;if(i<=st)return (i+1); /*若找到值为e的元素，则返回其序号*/elsereturn(-1); /*若没找到，则返回空序号*/}void main(){Seqlist l;int p,q,r;int i;printf("请输入线性标的长度:");scanf("%d",&r);st=r-1;printf("请输入线性表的各元素值：\n");for (i=0;i<=st;i++){scanf("%d",&l.elem[i]);}printf("请输入要查找的元素值:\n");scanf("%d",&q);p=Locate(l,q);if(p==-1)printf("在此线性表中没有该元素!\n");elseprintf("该素在线性表中的位置为:%d\n",p);}执行结果：错误分析：在编写过程中，在编写主函数的时候有落下未编写的，导致运行过程中不识别。

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#define MAXSIZE 100typedef struct{ElemType elem[MAXSIZE];int last;}SeqList;//#include "common.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->elem[k+1]=L->elem[k];L->elem[i-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->elem[i]);}printf("请输入要插入的位置:\n");scanf("%d",&p);printf("请输入要插入的元素值:\n");scanf("%d",&q);InsList(l,p,q);for(i=0; i<=l->last; i++){printf("%d ",l->elem[i]);}}执行结果：1.3顺序表的删除程序：#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#define MAXSIZE 100typedef struct{ElemType elem[MAXSIZE];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->elem[i-1];for(k=i; i<=L->last; k++)L->elem[k-1] = L->elem[k];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",&l->elem[i]);}printf("请输入要删除的元素位置:\n");scanf("%d",&p);DelList(l,p,q);printf("删除的元素值为:%d\n",*q);}执行结果：2.单链表的建立、插入、删除2.1 单链表的建立（尾插法）程序：#include<stdio.h>#include<stdlib.h>#define ERROR 0#define TRUE 1#define FALSE 0typedef char ElemType;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;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;}else{flag=0;r->next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/}}}int main(){LinkList l;Node *p;init_linklist(&l);printf("用尾插法建立单链表,请输入链表数据,以a结束!\n");CreateFromTail(l);p = l->next;while(p!=NULL){printf("%c\n",p->data);p=p->next;}return 0;}执行结果：错误分析：在代码的时候忘记分号，导致运行错误；截图如下:2.2 单链表的插入程序：#include "common.h"#include "linklist.h"int InsList(LinkList L,int i,ElemType e)/*在带头结点的单链表L中第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)); /*申请一个新的结点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("%c\n",p->data);p=p->next;}printf("请输入插入的位置和元素:\n");scanf("%d,%c",&i,&c);printf("%c\n",c);flag=InsList(l, i, c);if(flag)printf("插入操作成功!\n");elseprintf("插入操作失败!\n");p = l->next;while(p!=NULL){printf("%c\n",p->data);p=p->next;}}执行结果：2.3 单链表的删除程序：#include <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 /*结点类型定义*/{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; /*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag) /*循环输入表中元素值，将建立新结点s插入表尾*/{c=getchar();if(c!='$'){s=(Node*)malloc(sizeof(Node ));s->data=c;r->next=s;r=s;}else{flag=0;r->next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/}}}int DelList(LinkList L,int i,ElemType *e)/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/{Node *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不合法。