2022年数据结构线性表单链表的查找、插入、删除知识 .pdf

《2022年数据结构线性表单链表的查找、插入、删除知识 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构线性表单链表的查找、插入、删除知识 .pdf（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告课程名称数据结构姓名学号专业班级指导教师名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 29 页 - - - - - - - - - 目录第二章线性表的查找、插入、删除. 11.1 顺序表的查找 . 1 1.2 顺序表的插入 . 2 1.3 顺序表的删除 . 4单链表的建立、插入、删除. . 62.1 单链表的建立（尾插法） . 6 2.2 单链表的插入 . 8 2.3 单链表的删除 . 10第三章栈. 143.1 链栈 . 14 3.2 顺序栈 . 163.3

2、队列 . . 183.4 杨辉三角. 20第四章串 .234.1 字符串的建立 .23 4.2 顺序串的插入 .25名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 29 页 - - - - - - - - - 1 1.线性表的查找、插入、删除1.1 顺序表的查找程序：#include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define ElemType

3、int #define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/ typedef struct ElemType 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，即从第一个元素开始比较*/ w

4、hile (i=L.last)&(L.elemi!=e) /* 顺序扫描表，直到找到值为e 的元素，或扫描到表尾仍没找到*/ i+; if(i=L.last) return (i+1); /*若找到值为 e 的元素，则返回其序号 */ else return(-1); /*若没找到，则返回空序号 */ void main() Seqlist l; int p,q,r; int i; printf(请输入线性标的长度 :); scanf(%d,&r); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -

5、- - - 第 3 页，共 29 页 - - - - - - - - - 2 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); else printf(该素在线性表中的位置为:%dn,p); 执行结果：错误分析：在编写过程中，在编写主函数的时候有落下未编写的，导致运行过程中不识别。1.2 顺序表的插入程序：#include

6、#include /#include #define OK 1 #define ERROR 0 #define TRUE 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 29 页 - - - - - - - - - 3 #define FALSE 0 #define ElemType int #define MAXSIZE 100 typedef struct ElemType elemMAXSIZE; int last; SeqList; /#include com

7、mon.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;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=

8、(SeqList*)malloc(sizeof(SeqList); printf(请输入线性表的长度 :); scanf(%d,&r); l-last = r-1; printf(请输入线性表的各元素值 :n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 29 页 - - - - - - - - - 4 for(i=0; ilast; i+) scanf(%d,&l-elemi); printf(请输入要插入的位置 :n); scanf(%d,&p); printf

9、(请输入要插入的元素值 :n); scanf(%d,&q); InsList(l,p,q); for(i=0; ilast; i+) printf(%d ,l-elemi); 执行结果：1.3 顺序表的删除程序：#include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define ElemType int #define MAXSIZE 100 typedef struct 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

10、- - - 名师精心整理 - - - - - - - 第 6 页，共 29 页 - - - - - - - - - 5 ElemType elemMAXSIZE; int last; 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;

11、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); 执行结果：名师资料总结 - -

12、-精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 29 页 - - - - - - - - - 6 2.单链表的建立、插入、删除2.1 单链表的建立（尾插法）程序：#include #include #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef char ElemType; typedef struct Node /*结点类型定义 */ ElemType data; struct Node * next; Node, *LinkLi

13、st; /* 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指针动态指向链表的当前表尾，以便于做尾插名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

14、- - - 名师精心整理 - - - - - - - 第 8 页，共 29 页 - - - - - - - - - 7 入，其初值指向头结点 */ 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); p

15、rintf(用尾插法建立单链表 , 请输入链表数据 , 以 a 结束!n); CreateFromTail(l); p = l-next; while(p!=NULL) printf(%cn,p-data); p=p-next; return 0; 执行结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 29 页 - - - - - - - - - 8 错误分析：在代码的时候忘记分号，导致运行错误；截图如下: 2.2 单链表的插入程序：#include common.h

16、 #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&knext; k=k+1; /* 查找第 i-1 结点*/ if(!pre) /*如当前位置 pre 为空表已找完还未数到第i 个，说明插入位置不合理 */ printf(插入位置不合理 !); return ERROR; s=(Node*)malloc(s

17、izeof(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(%cn,p-data); p=p-next; prin

18、tf(请输入插入的位置和元素 :n); scanf(%d,%c,&i,&c); printf(%cn,c); flag=InsList(l, i, c); if(flag) printf(插入操作成功 !n); else printf(插入操作失败 !n); p = l-next; while(p!=NULL) printf(%cn,p-data); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 29 页 - - - - - - - - - 10 p=p-next;

19、执行结果：2.3 单链表的删除程序：#include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef char ElemType; typedef struct Node /* 结点类型定义 */ ElemType data; struct Node * next; Node, *LinkList; /* LinkList为结构指针类型 */ void init_linklist(LinkList *l)/*对单链表进行初始化 */ *l=(LinkList)malloc

20、(sizeof(Node); (*l)-next=NULL; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 29 页 - - - - - - - - - 11 void CreateFromTail(LinkList L) Node *r, *s; char c; int flag =1; /* 设置一个标志，初值为1，当输入 $时，flag 为 0，建表结束 */ r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/ while(flag

21、) /* 循环输入表中元素值，将建立新结点 s 插入表尾 */ c=getchar(); if(c!=$) s=(Node*)malloc(sizeof(Node); s-data=c; r-next=s; r=s; else flag=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 29 页 - - - - - - - - - 12 r-next=NULL; /* 将最后一个结点的 next 链域置为空，表示链表的结束*/ int DelList(LinkLis

22、t L,int i,ElemType *e) /* 在带头结点的单链表L 中删除第 i 个元素，并将删除的元素保存到变量*e 中*/ Node *pre,*r; int k; 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(成功删除结

23、点 !n); /printf(被删除的元素是 :%cn,*e); return OK; void main() LinkList l; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 29 页 - - - - - - - - - 13 Node *p; int flag=0; int x; char*e; init_linklist(&l); printf(请输入链表数据 , 以$结束!n); CreateFromTail(l); p = l-next; while(p

24、!=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); 执行结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 29 页 - - - - - - -

25、 - - 14 3.栈3.1 链栈程序：#include #include #define TRUE 1 #define FALSE 0 #define StackElementType int typedef struct node StackElementType data; struct node *next; LinkStackNode; typedef LinkStackNode *LinkStack; int Push(LinkStack top,StackElementType x) LinkStackNode *temp; temp=(LinkStackNode *)mallo

26、c(sizeof(LinkStackNode); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 29 页 - - - - - - - - - 15 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=to

27、p-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);

28、else flag=0; while(top-next!=NULL) Pop(top,&x); printf(%dt,x); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 29 页 - - - - - - - - - 16 return 0; 执行结果3.2 顺序栈顺序栈进栈程序：#include #include #include #define stack_size 50 typedef struct int elemstack_size;

29、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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 29 页 - - - - - - - - - 17

30、 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)

31、; return 0; 执行结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 29 页 - - - - - - - - - 18 4.队列顺序队列基本操作：#include #include #include #define MaxSize 20 typedef int ElemType; typedef struct ElemType dataMaxSize; int front,rear; / SqQueue; /顺序队列类型 SqQueue的定义/ 初始化队列

32、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); / 进队列void enQueue( SqQueue *&q,ElemType e) if(q-rear+1)%MaxSize=q-f

33、ront) printf(目前顺序队列已满了 n); else q-rear=(q-rear+1)%MaxSize; q-dataq-rear=e; printf(此次进队元素是 :%dn,e); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 29 页 - - - - - - - - - 19 / 出队列void deQueue(SqQueue *&q,ElemType &e) if(q-front=q-rear) printf(目前此顺序队列为空 n); else

34、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(请继续此队头插入一个元素，或者停止插入队列元素，请按0n); scanf(%d,&e); QueueEmpty(q); int i; printf(如果想在此队尾出队一个元素，请按1n); scanf

35、(%d,&i); while(i=1) deQueue(q,e); if(q-front=q-rear) printf(顺序队列的基本运算操作到此结束了n); exit(0); else printf(如果想在此队尾继续出队一个元素，请按1n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 29 页 - - - - - - - - - 20 scanf(%d,&i); 执行结果：5.杨辉三角（1）程序：#include #include #define TRUE 1

36、 #define FALSE 0 #define MAXSIZE 50 /*队列的最大长度 */ typedef struct int elementMAXSIZE; /* 队列的元素空间 */ int front; /*头指针指示器 */ int rear; /*尾指针指示器 */ SeqQueue; /* 初始化操作 */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 29 页 - - - - - - - - - 21 void InitQueue(SeqQueu

37、e *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) /* 删

38、除队列的队头元素，用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); /*操作成功 */ vo

39、id YangHuiTriangle( ) int n; int i; int temp; int x; int N; SeqQueue Q; InitQueue(&Q); EnterQueue(&Q,1); /* 第一行元素入队 */ printf(请输入杨辉三角行数 N:); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 29 页 - - - - - - - - - 22 scanf(%d,&N); for(n=2;n=N;n+) /* 产生第 n 行元素并入队，

40、同时打印第n-1 行的元素*/ EnterQueue(&Q,1); /* 第 n 行的第一个元素入队 */ for(i=1;i=n-2;i+) /* 利用队中第n-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 行的最后一

41、个元素 */ EnterQueue(&Q,1); /* 第 n 行的最后一个元素入队 */ printf(n); int main() YangHuiTriangle( ); 执行结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 29 页 - - - - - - - - - 23 6.串6.1 字符串的建立程序：#include #include #define MAXLEN 40 #define MAXLEN 40 typedef struct /*串结构定义 *

42、/ 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 为空则返回，否则返回 */ 名师资料总结 - - -精品资料欢迎下载 - - -

43、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 29 页 - - - - - - - - - 24 if (s.len=0) return(1); else return(0); int main() SString str2; int flag=0; printf(建立字符串 !n); createstring(&str2); flag=StrEmpty(str2); if(flag = 1) printf(字符串为空 !); else printf(字符串不为空 !n); output(&str2); return

44、0; 执行结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 29 页 - - - - - - - - - 25 6.2 顺序串插入程序：#include #include #define MAXLEN 40 typedef struct /*串结构定义 */ char chMAXLEN; int len; SString; void createstring(SString *s) int i,j; char c; printf(请输入要建立的串的长度 :); sc

45、anf(%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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

46、师精心整理 - - - - - - - 第 27 页，共 29 页 - - - - - - - - - 26 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; else if (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=MAXL

47、EN; 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); pri

48、ntf(请输入要插入的位置 :); scanf(%d,&pos); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 28 页，共 29 页 - - - - - - - - - 27 flag=StrInsert(str1,pos,str2); if(flag = 0) printf(插入操作失败 !); else printf(插入后串为 :n); output(str1); 执行结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 29 页，共 29 页 - - - - - - - - -