《数据结构实验指导书(1)》由会员分享，可在线阅读，更多相关《数据结构实验指导书(1)（36页珍藏版）》请在金锄头文库上搜索。
1、1第二章线性表2.5 实训【实训 1】顺序表的应用1实训说明本实训是有关线性表的顺序存储结构的应用，在本实训的实例程序中，通过 C 语言中提供的数组来存储两个已知的线性表，然后利用数组元素的下标来对线性表进行比较。通过对本实训的学习，可以理解线性表在顺序存储结构下的操作方法。在实训中，我们设 A=（a1,a2,an）和 B=（b1,b2,bm）是两个线性表，其数据元素的类型是整型。若 n=m,且 ai=bi,则称 A=B; 若 ai=bi，而 ajB。设计一比较大小的程序。 2程序分析已知 A 和 B 是两个线性表，且其数据元素为整型数据，因此，可以使用线性表的顺序存储结构来实现，在 C 语言
2、中，可以使用一维数组来存储顺序表。1）初始化两个线性表：输入两个数组 A 和 B。2）调用子函数 int compare(int A,int B,int m)比较两个数组的大小：比较 Ai和 Bi：若 AiBi 返回 BIG若 AiBi)return BIG; /*返回在 AB*/elseif (Ai=MAXSIZE)2 printf(请输入数据的大小 m(0-100):);scanf(%d,for(i=0;i请输入数据 A 的第 1 个数组元素 1请输入数据 A 的第 2 个数组元素 2请输入数据 A 的第 3 个数组元素 3请输入数据 B 的第 1 个数组元素 1请输入数据 B 的第 2
3、个数组元素 2请输入数据 B 的第 3 个数组元素 4数组 A 小于数组 B【实训 2】链表的应用1实训说明本实训是有关线性表的链式存储结构的应用，在本实训的实例程序中，通过 C 语言中提供的结构指针来存储线性表，利用 malloc 函数动态地分配存储空间。通过对本实训的学习，可以理解线性表在链序存储结构下的操作方法。在实训中，我们设计一个程序求出约瑟夫环的出列顺序。约瑟夫问题的一种描述是：编号为1，2，n 的 n 个人按顺时针方向围坐一圈，每个人持有一个密码（正整数） 。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人
4、出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直到所有人全部出列为止。例如，n=7,7 个人的密码依次为：3,1,7,2,4,8,4,m 的初值取 6，则正确的出列顺序应为 6,1,4,7,2,3,5。要求使用单向循环链表模拟此出列过程。 2程序分析约瑟夫环的大小是变化的，因此相应的结点也是变化的，使用链式存储结构可以动态的生成其中的结点，出列操作也非常简单。用单向循环链表模拟其出列顺序比较合适。用结构指针描述每个人：struct Josephint num;/*环中某个人的序号*/int secret;/环中某个人的密码*/struct Jos
5、eph *next;/指向其下一个的指针*/;1）初始化约瑟夫环：调用函数 struct Joseph *creat()生成初始约瑟夫环。在该函数中使用 head 指向表头。输入序号为 0 时结束，指针 p1 指向的最后结束序号为 0 的结点没有加入到链表中，p2 指向最后一3个序号为非 0 的结点（最后一个结点） 。2）报数出列：调用函数 voil sort(struct Joseph * head,int m)，使用条件 p1-next!=p1 判断单向链表非空，使用两个指针变量 p1 和 p2，语句 p2=p1;p1=p1-next;移动指针，计算结点数（报数） ；结点 p1 出列时直接
6、使用语句：p2-next=p1-next，取出该结点中的密码作为新的循环终值。3程序源代码该实例程序的源代码如下：#define NULL 0#define LENGTH sizeof(struct Joseph)#include stdlib.h#include stdio.hstruct Josephint num;int secret;struct Joseph *next; /*定义结点 num 为序号，secret 为密码*/*创建初始链表函数*/struct Joseph *creat()struct Joseph *head;struct Joseph *p1,*p2;int n
7、=0;p1=p2=(struct Joseph *)malloc(LENGTH);scanf(%d,%d,head=NULL;while(p1-num!=0)n=n+1;if(n= =1)head=p1;else p2-next=p1;p2=p1;p1=(struct Joseph *)malloc(LENGTH);scanf(%d,%d,p2-next=head;return(head); /*报数出列*/void sort(struct Joseph * head,int m)struct Joseph *p1,*p2;int i;if(head=NULL)printf(n 链表为空!n)
8、;p1=head;while(p1-next!=p1)for(i=1;inext;p2-next=p1-next;m=p1-secret;4printf(%d ,p1-num);p1=p2-next;if(p1-next= =p1)printf(%d ,p1-num);main()struct Joseph *head;int m;printf(n 输入数据:数据格式为序号，密码n 输入 0，0 为结束n);head=creat();printf(输入 m 值n);scanf(%d,if(m2，13，74，25，46，87，40，0输入 m 值6出列的序号是6 1 4 7 2 3 5第三章 栈
9、和队列3.4 实训【实训 1】栈的应用1实训说明本实训是关于栈的应用，栈在各种高级语言编译系统中应用十分广泛，在本实训程序中，利用栈的“先进后出”的特点，分析 C 语言源程序代码中的的括号是否配对正确。通过本对本实训的学习，可以理解的基本操作的实现。本实训要求设计一个算法，检验 C 源程序代码中的括号是否正确配对。对本算法中的栈的存储实现，我们采用的是顺序存储结构。要求能够在某个 C 源程序上文件上对所设计的算法进行验证。2程序分析（1）int initStack(sqstack *s) 初始化一个栈（2）int push(sqstack *s,char x) 入栈，栈满时返回 FALSE5（
10、3）char pop(sqstack *s) 出栈，栈空时返回 NULL（4）int Empty(sqstack *s) 判断栈是否为空，为空时返回 TRUE（5）int match(FILE *f) 对文件指针 f 对指的文件进行比较括号配对检验，从文件中每读入一个字符 ch=fgetc(f)，采用多路分支 switch(ch)进行比较：若读入的是“” 、 “”或“（” ，则压入栈中，若读入的是“” ，则：若栈非空，则出栈，判断出栈符号是否等于“” ，不相等，则返回FALSE。若读入的是“” ，则：若栈非空，则出栈，判断出栈符号是否等于“” ，不相等，则返回FALSE。若读入的是“） ”，则
11、：若栈非空，则出栈，判断出栈符号是否等于“（” ，不相等，则返回 FALSE。若是其它字符，则跳过。文件处理到结束时，如果栈为空，则配对检验正确，返回 TRUE。（6）主程序 main()中定义了一个文件指针，输入一个已经存在的 C 源程序文件。3程序源代码# define MAXNUM 200# define FALSE 0# define TRUE 1#include stdio.h#include stdlib.h#include string.htypedef struct char stackMAXNUM;int top; sqstack; /*定义栈结构*/int initStac
12、k(sqstack *s)/*初始化栈*/if (*s=(sqstack*)malloc(sizeof(sqstack)=NULL) return FALSE;(*s)-top=-1;return TRUE;int push(sqstack *s,char x)/*将元素 x 插入到栈 s 中，作为 s 的新栈顶*/if(s-top=MAXNUM-1) return FALSE; /*栈满*/s-top+;s-stacks-top=x;return TRUE;char pop(sqstack *s)/*若栈 s 不为空，则删除栈顶元素*/char x;if(s-topstacks-top;s-
13、top-;return x;int Empty(sqstack *s) /*栈空返回 TRUE,否则返回 FALSE*/if(s-top( ) ( )括号正确【实训 2】队列的应用1实训说明本实训是队列的一种典型的应用，队列是一种“先到先服务”的特殊的线性表，本实训要求模拟手机短信功能，使用链式存储结构的队列，进行动态地增加和删除结点信息。通过本实训的学习，可以理解队列的基本操作的实现。设计程序要求，模拟手机的某些短信息功能。 功能要求： （1）接受短信息，若超过存储容量（如最多可存储 20 条） ，则自动将最早接受的信息删除。 （2）显示其中任意一条短信息。 （3）逐条显示短信息。 （4）删
14、除其中的任意一条短信息。 （5）清除。2程序分析采用结构体指针定义存储短信结点：typedef struct Qnodechar dataMAXNUM;/*字符数组存储短信*/struct Qnode *next;Qnodetype; /*定义队列的结点*/定义队列：typedef struct Qnodetype *front;/*头指针*/Qnodetype *rear; /*尾指针*/int number;/*短信数量*/Lqueue;（1）int initLqueue(Lqueue *q) 初始化短信队列。（2）int LInQueue(Lqueue *q,char x) 入队列，将字
15、符串 x 加入到队列尾部。（3）char * LOutQueue(Lqueue *q) 出队列，删除队头元素，返回其中的字符串。（4）void get(Lqueue *q,char x) 接收短数，若短信数量超过 20 条，则删除队头短信。（5）void deleteall(Lqueue *q) 清除所有短信。（6）void deleteone(Lqueue *q,int n) 删除第 n 条短信。（7）void displayall(Lqueue *q) 显示所有短信。（8）void displayone(Lqueue *q,int n) 显示第 n 条短信。在 main()函数中，采用菜单方式，菜单中同时显示出已有的短信数量，由用户选择输入命令，实现程序要求功能，命令说明：R(r)：接收短信L(l)：显示任意一条短信A(a)：显示所有短信D(d)：删除任意一条短信U(u)：删除所有短信Q(q)：退出83程序源代码# define MAXNUM 70# define FALSE 0# define TRUE 1#include stdio.h#include stdlib.h#include string.htypedef struct Qnodechar dataMAXNUM;struct Qn
