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

实验报告课程名称数据结构姓名学号专业班级指导教师目录第二章线性表的查找、插入、删除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 #include#include#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, 则找到该元素，并返回 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,&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);执行结果：错误分析 ：在编写过程中，在编写主函数的时候有落下未编写的，导致运行过程中不识别。1.2 顺序表的插入程序：#include #include /#include #define OK1#define ERROR 0#define TRUE 1#define FALSE 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-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+)scanf(%d,&l-elemi);printf(请输入要插入的位置 :n);scanf(%d,&p);printf(请输入要插入的元素值 :n);scanf(%d,&q);InsList(l,p,q);for(i=0; ilast; i+)printf(%d ,l-elemi);执行结果：1.3 顺序表的删除程序：#include #include #include #define OK1#define 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(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(请输入线性表的各元素值:n);for(i=0; ilast; i+)scanf(%d,&l-elemi);printf(请输入要删除的元素位置:n);scanf(%d,&p);DelList(l,p,q);printf(删除的元素值为 :%dn,*q);执行结果：2.单链表的建立 、插入 、删除2.1单链表的建立（尾插法）程序：#include#include#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;intflag =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_linklist(&l);printf( 用尾插法建立单链表 , 请输入链表数据 , 以 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.hint InsList(LinkList L,int i,ElemType e)/* 在带头结点的单链表L 中第 i 个位置插入值为 e 的新结点 s*/Node *pre,*s;int k;pre=L;k=0;/*while(pre!=NULL&knext;k=k+1;/*查找第i-1结点 */if(!pre)/*如当前位置pre为空表已找完还未数到第i 个，说明插入位置不合理*/printf(插入位置不合理!);return ERROR;s=(Node*)malloc(sizeof(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-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.3单链表的删除程序：#include#include#include#defineOK1#defineERROR 0#defineTRUE1#defineFALSE0typedefcharElemType;typedefstructNode/* 结点类型定义 */ElemTypedata;structNode*next;Node,*LinkList;/*LinkList为结构指针类型 */voidinit_linklist(LinkList*l)/*对单链表进行初始化 */*l=(LinkList)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-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&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);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*)malloc(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#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(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;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);elseflag=0;while(top-next!=NULL)Pop(top,&x);printf(%dt,x);printf(n);return 0;执行结果3.2顺序栈顺序栈进栈程序：#include#include #include #define 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 a;int i, r;seqstack *s;s = (seqstack*)malloc(sizeof(seqstack);initstack(s);printf(请输入长度 :);scanf(%d, &r);printf(请输入各元素值 :n);for (i = 0; itop+;scanf(%d, &s-elemi);printf(请输入要进栈的值： );scanf(%d, &a);push(s, a);OutStack(s);return 0;执行结果：4.队列顺序队列基本操作：#include#include#include#define MaxSize 20typedef int ElemType;typedef structElemType 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(目前此顺序队列非空 n);/ 进队列void enQueue( 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);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);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);elseprintf(如果想在此队尾继续出队一个元素，请按1n);scanf(%d,&i);执行结果：5.杨辉三角（ 1）程序：#include#include#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 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) /*队列为空 */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( )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 行的中间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);int main()YangHuiTriangle( );执行结果：6.串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(请输入要建立的串的长度:);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;执行结果：6.2 顺序串插入程序：#include #include #define MAXLEN 40typedef struct /*串结构定义 */char chMAXLEN;int len;SString;void createstring(SString *s)int i,j;char c;printf(请输入要建立的串的长度:);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 StrInsert(SString *s, int pos, SString t)/* 在串 s 中下标为 pos 的字符之前插入串t */int i;if (poss-len) /* 插入位置不合法 */ return(0);if (s-len + t.lenlen + t.len-1;i=t.len + pos;i-)s-chi=s-chi-t.len;for (i=0;ichi+pos=t.chi;s-len=s-len+t.len;elseif (pos+t.lenMAXLEN,但串 t 的字符序列可以全部插入 */for (i=MAXLEN-1;it.len+pos-1;i-)s-chi=s-chi-t.len;for (i=0;ichi+pos=t.chi;s-len=MAXLEN;else /*插入后串长 MAXLEN,并且串 t 的部分字符也要舍弃 */for (i=0;ichi+pos=t.chi;s-len=MAXLEN;return(1);void main()SString *str1;SString str2;int i,j,k,pos;int flag=0;str1 = (SString *)malloc(sizeof(SString);str1-len = 0;printf(建立字符串 1:n);createstring(str1);printf(建立字符串 2:n);createstring(&str2);printf(请输入要插入的位置 :);scanf(%d,&pos);flag=StrInsert(str1,pos,str2);if(flag = 0)printf(插入操作失败 !);elseprintf(插入后串为 :n);output(str1);执行结果：