实训1顺序表的应用

1、第二章线性表2.5实训【实训1】顺序表的应用1实训说明本实训是有关线性表的顺序存储结构的应用，在本实训的实例程序中，通过c语言中提供的数组来存储两个已知的线性表，然后利用数组元素的下标来对线性表进行比较。通过对本实训的学习，可以理解线性表在顺序存储结构下的操作方法。在实训中，我们设a=（a1,a2,an）和b=（b1,b2,bm）是两个线性表，其数据元素的类型是整型。若n=m,且ai=bi,则称a=b; 若ai=bi，而ajbj,则称ab。设计一比较大小的程序。 2程序分析已知a和b是两个线性表，且其数据元素为整型数据，因此，可以使用线性表的顺序存储结构来实现，在c语言中，可以使用一维数组来存

2、储顺序表。1）初始化两个线性表：输入两个数组a和b。2）调用子函数int compare(int a,int b,int m)比较两个数组的大小：比较ai和bi：若aibi 返回big若aibi 返回small若ai= =bi且im，则i+，继续比较；否则返回equal3程序源代码该实例程序的源代码如下：#include stdio.h#define maxsize 100 /*最大数组元素个数*/#define big 1#define small -1#define equal 0int compare(int a,int b,int m) /*比较数组数据*/int i; for(i=0

3、;ibi) return big; /*返回在ab*/ else if (aibi) return small; /*返回在ab*/ return equal; /*返回在a=b*/ /*主程序*/main()int amaxsize,bmaxsize;int m ,s,i;printf(请输入数据的大小m(0-100):); scanf(%d,&m); while (m=maxsize) printf(请输入数据的大小m(0-100):); scanf(%d,&m); for(i=0;im;i+) printf(请输入数组a的第%d个数组元素,i+1); scanf(%d,&ai); for

4、(i=0;im;i+) printf(请输入数组b的第%d个数组元素,i+1); scanf(%d,&bi); s=compare(a,b,m); if (s= =big) printf(数组a大于数组b); else if (s= =small) printf(数组a小于数组b); else printf(数组a等于数组b); 最后程序运行结果如下所示：请输入数据的大小m(0-100)：3请输入数据a的第1个数组元素1请输入数据a的第2个数组元素2请输入数据a的第3个数组元素3请输入数据b的第1个数组元素1请输入数据b的第2个数组元素2请输入数据b的第3个数组元素4数组a小于数组b【实训2】

5、链表的应用1实训说明本实训是有关线性表的链式存储结构的应用，在本实训的实例程序中，通过c语言中提供的结构指针来存储线性表，利用malloc函数动态地分配存储空间。通过对本实训的学习，可以理解线性表在链序存储结构下的操作方法。在实训中，我们设计一个程序求出约瑟夫环的出列顺序。约瑟夫问题的一种描述是：编号为1，2，n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。例如，

6、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 joseph *next;/指向其下一个的指针*/;1）初始化约瑟夫环：调用函数struct joseph *creat()生成初始约

7、瑟夫环。在该函数中使用head 指向表头。输入序号为0时结束，指针p1指向的最后结束序号为0的结点没有加入到链表中，p2 指向最后一个序号为非0 的结点（最后一个结点）。2）报数出列：调用函数voil sort(struct joseph * head,int m)，使用条件p1-next!=p1判断单向链表非空，使用两个指针变量p1和p2，语句p2=p1;p1=p1-next;移动指针，计算结点数（报数）；结点p1出列时直接使用语句：p2-next=p1-next，取出该结点中的密码作为新的循环终值。3程序源代码该实例程序的源代码如下：#define null 0#define length

8、 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=0; p1=p2=(struct joseph *)malloc(length); scanf(%d,%d,&p1-num,&p1-secret); head=n

9、ull; 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,&p1-num,&p1-secret); p2-next=head; return(head); /*报数出列*/void sort(struct joseph * head,int m)struct joseph *p1,*p2; int i; if(head=null) printf(n链表为空!n); p1=head; while(p1-next!=p1

10、) for(i=1;inext; p2-next=p1-next; m=p1-secret; printf(%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,&m); if(m1)printf(error! 请输入一个合法的 m值!); printf(出列的序号是:n); sort(head,m);最后程序

11、运行结果如下所示：输入数据：数据格式为序号，密码输入0，0为结束1，32，13，74，25，46，87，40，0输入m值6出列的序号是6 1 4 7 2 3 5第三章 栈和队列3.4实训【实训1】栈的应用1实训说明本实训是关于栈的应用，栈在各种高级语言编译系统中应用十分广泛，在本实训程序中，利用栈的“先进后出”的特点，分析c语言源程序代码中的的括号是否配对正确。通过本对本实训的学习，可以理解的基本操作的实现。本实训要求设计一个算法，检验c源程序代码中的括号是否正确配对。对本算法中的栈的存储实现，我们采用的是顺序存储结构。要求能够在某个c源程序上文件上对所设计的算法进行验证。2程序分析（1）in

12、t initstack(sqstack *s) 初始化一个栈（2）int push(sqstack *s,char x) 入栈，栈满时返回false（3）char pop(sqstack *s) 出栈，栈空时返回null（4）int empty(sqstack *s) 判断栈是否为空，为空时返回true（5）int match(file *f) 对文件指针f对指的文件进行比较括号配对检验，从文件中每读入一个字符ch=fgetc(f)，采用多路分支switch(ch)进行比较：若读入的是“”、“”或“（”，则压入栈中，若读入的是“”，则：若栈非空，则出栈，判断出栈符号是否等于“”，不相等，则返回

13、false。若读入的是“”，则：若栈非空，则出栈，判断出栈符号是否等于“”，不相等，则返回false。若读入的是“）”，则：若栈非空，则出栈，判断出栈符号是否等于“（”，不相等，则返回false。若是其它字符，则跳过。文件处理到结束时，如果栈为空，则配对检验正确，返回true。（6）主程序main()中定义了一个文件指针，输入一个已经存在的c源程序文件。3程序源代码# define maxnum 200# define false 0# define true 1#include stdio.h#include stdlib.h#include string.h typedef struct

14、char stackmaxnum; int top; sqstack; /*定义栈结构*/int initstack(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(sqst

15、ack *s)/*若栈s不为空，则删除栈顶元素*/char x; if(s-topstacks-top; s-top-;return x;int empty(sqstack *s) /*栈空返回true,否则返回false*/ if(s-top0) return true; return false; int match(file *f) char ch,ch1; sqstack *s; initstack(&s); while(!feof(f) ch=fgetc(f); switch(ch) case (: case : case :push(s,ch);printf(%c,ch);brea

16、k; case ): if (empty(s)!=true)ch1=pop(s); printf(%c,ch);if (ch1=()break;elsereturn false; elsereturn false; case : if (empty(s)!=true)ch1=pop(s); printf(%c,ch);if (ch1=)break;elsereturn false; elsereturn false; case :if (empty(s)!=true)ch1=pop(s); printf(%c,ch);if (ch1=)break;elsereturn false; elser

17、eturn false; default:break; if (empty(s)!=true) return false; return true; void main()file *fp;char fn20;printf(请输入文件名：);scanf(%s,fn);if (fp=fopen(fn,r)=null) printf(不能打开文件n); exit(0);else if (match(fp)=true) printf(括号正确n); else printf(括号不正确n); fclose(fn); 最后程序运行结果如下所示：请输入文件名： f:exam.c( ) ( )括号正确【实训

18、2】队列的应用1实训说明本实训是队列的一种典型的应用，队列是一种“先到先服务”的特殊的线性表，本实训要求模拟手机短信功能，使用链式存储结构的队列，进行动态地增加和删除结点信息。通过本实训的学习，可以理解队列的基本操作的实现。设计程序要求，模拟手机的某些短信息功能。 功能要求： （1）接受短信息，若超过存储容量（如最多可存储20条），则自动将最早接受的信息删除。 （2）显示其中任意一条短信息。 （3）逐条显示短信息。 （4）删除其中的任意一条短信息。 （5）清除。2程序分析采用结构体指针定义存储短信结点：typedef struct qnodechar datamaxnum;/*字符数组存储短信

19、*/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) 入队列，将字符串x加入到队列尾部。（3）char * loutqueue(lqueue *q) 出队列，删除队头元素，返回其中的字符串。（4）void get(lqueue *q,ch

20、ar 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)：删

21、除所有短信q(q)：退出3程序源代码# define maxnum 70# define false 0# define true 1#include stdio.h#include stdlib.h#include string.h typedef struct qnodechar datamaxnum;struct qnode *next;qnodetype; /*定义队列的结点*/typedef struct qnodetype *front;/*头指针*/qnodetype *rear; /*尾指针*/int number;/*短信数量*/lqueue;int initlqueue(l

22、queue *q)/*创建一个空链队列q*/ if (*q)-front=(qnodetype*)malloc(sizeof(qnodetype)=null) return false; (*q)-rear=(*q)-front;strcpy(*q)-front-data,head);(*q)-front-next=null; (*q)-number=0; return true; int linqueue(lqueue *q,char x)/*将元素x插入到链队列q中，作为q的新队尾*/qnodetype *p;if (p=(qnodetype*)malloc(sizeof(qnodetyp

23、e)=null) return false;strcpy(p-data,x);p-next=null; /*置新结点的指针为空*/q-rear-next=p; /*将链队列中最后一个结点的指针指向新结点*/q-rear=p; /*将队尾指向新结点*/return true;char * loutqueue(lqueue *q)/*若链队列q不为空，则删除队头元素，返回其元素值*/char xmaxnum;qnodetype *p;if(q-front-next=null) return null; /*空队列*/p=q-front-next; /*取队头*/q-front-next=p-nex

24、t; /*删除队头结点*/if (p-next=null) q-rear=q-front ;strcpy(x,p-data);free(p);return x;void get(lqueue *q,char x) /*接受短信*/int n; if (q-number=20) loutqueue(q);q-number-; linqueue(q,x); q-number+;void deleteall(lqueue *q) /*删除所有短信*/while (q-front!=q-rear) loutqueue(q);q-number=0;void deleteone(lqueue *q,int

25、 n)/*删除第n条短信*/ lqueue *p;qnodetype *s; int i; p=q;i=1; while (ifront=p-front-next; i=i+1; s=p-front-next; p-front-next=p-front-next-next; free(s); q-number-;void displayall(lqueue *q)/*显示所有短信*/ lqueue *p;char xmaxnum; p=q; while(p-front!=q-rear) p-front=p-front-next; printf(%sn,p-front-data); printf

26、(n); void displayone(lqueue *q,int n)/*显示第n条短信*/ lqueue *p;qnodetype *s; int i; p=q;i=1; while (ifront=p-front-next; i=i+1; s=p-front-next; printf(%sn,s-data); void main() lqueue *lp; int i;qnodetype *headnode; char command,chmaxnum; initlqueue(&lp);headnode=lp-front; while (1) printf(get informatio

27、n(%d),please enter rn,lp-number); printf(display one information(%d),please enter ln,lp-number); printf(display all information(%d),please enter an,lp-number); printf(delete one information(%d),please enter dn,lp-number); printf(delete all information(%d),please enter un,lp-number); printf(quit,plea

28、se enter qn); printf(please input command:); scanf(%c,&command); switch (command) case r: case r: gets(ch);lp-front=headnode;get(lp,ch);break; case l: case l:printf(enter no.:),scanf(%d,&i); lp-front=headnode;displayone(lp,i);break; case a: case a:lp-front=headnode;displayall(lp);break; case d: case

29、 d:printf(enter no.:),scanf(%d,&i); lp-front=headnode;deleteone(lp,i);break; case u: case u:lp-front=headnode;deleteall(lp);break; case q: case q:printf(quit!); if (command=q|command=q) break;最后程序运行结果如下所示：get information(0),please enter rdisplay one information(0),please enter ldisplay all informati

30、on(0),please enter adelete one information(0),please enter ddelete all information(0),please enter uquit,please enter qplease input command:ri like c+get information(1),please enter rdisplay one information(1),please enter ldisplay all information(1),please enter adelete one information(1),please en

31、ter ddelete all information(1),please enter uquit,please enter qplease input command 第四章 串4.5 实训【实训】学生成绩管理系统1实训说明本实训是关于串的应用，在本实训中主要利用串的链式存储结构，对学生的各项记录动态的存储，并且将结果保存在文件中，可以调用以前的数据。从而加深对串的基本存储方法和基本运算的了解，以及简单的文件操作。设计要求：可以完成学生数据的输入输出，并进行简单的管理要求实现以下的基本功能模块：1、输入学生成绩；3、删除学生成绩；4、显示所有学生；5、保存为文本文件；6、从文件读取。完成以上

32、模块后，有兴趣可以考虑以下功能模块的实现：1、将文件进行复制；2、进行排序；3、将学生成绩追加到文本文件；2、进行分类汇总。2程序分析采用链式存储方式，要定义一个结构体：typedef struct z1 /*定义数据结构*/ char no11; char name15; int scoren; float sum; float average; int order; struct z1 *next; student;定义以下函数：1、student *init(); 初始化函数。2、student *create(); 创建链表，输入学生数据，当学号为时，停止输入。3、student *d

33、elete(student *h); 删除记录，根据学号进行删除，删除成功返回头指针。4、void print(student *h); 显示所有记录。5、void save(student *h); 以文本文件保存学生成绩，输入文件名要标明路径，如没有该文件则自动创建一个新文件。6、student *load(); 读取记录 3. 程序源代码#include stdio.h /*i/o函数*/#include stdlib.h /*其它说明*/#include string.h /*字符串函数*/#include conio.h /*屏幕操作函数*/#include mem.h /*内存操作

34、函数*/#include ctype.h /*字符操作函数*/#include alloc.h /*动态地址分配函数*/#define n 3 /*定义常数*/typedef struct z1 /*定义数据结构*/ char no11; char name15; int scoren; float sum; float average; int order; struct z1 *next; student;student *init(); /*初始化函数*/student *create(); /*创建链表*/student *delete(student *h); /*删除记录*/voi

35、d print(student *h); /* 显示所有记录*/void search(student *h); /*查找*/void save(student *h); /*保存*/student *load(); /*读入记录*/int menu_select(); /*菜单函数*/main() int i; student *head; /*链表定义头指针*/ head=init(); /*初始化链表*/ clrscr(); /*清屏*/ for(;) /*无限循环*/ switch(menu_select() /*调用主菜单函数，返回值整数作开关语句的条件*/ /*值不同，执行的函数不

36、同，break 不能省略*/case 0:head=init();break; /*执行初始化*/case 1:head=create();break; /*创建链表*/case 2:head=delete(head);break; /*删除记录*/case 3:print(head);break; /*显示全部记录*/case 4:search(head);break; /*查找记录*/case 5:save(head);break; /*保存文件*/case 6:head=load(); break; /*读文件*/case 14:exit(0); /*如菜单返回值为14程序结束*/ me

37、nu_select() char *menu=*menu*, /*定义菜单字符串数组*/ 0. init list, /*初始化*/ 1. enter list, /*输入记录*/ 2. delete a record from list, /*从表中删除记录*/ 3. print list , /*显示单链表中所有记录*/ 4. search record on name, /*按照姓名查找记录*/ 5. save the file, /*将单链表中记录保存到文件中*/ 6. load the file, /*从文件中读入记录*/ 7. quit; /*退出*/ char s3; /*以字符

38、形式保存选择号*/ int c,i; /*定义整形变量*/ gotoxy(1,25); /*移动光标*/ printf(press any key enter menu.n); /*压任一键进入主菜单*/ getch(); /*输入任一键*/ clrscr(); /*清屏幕*/ gotoxy(1,1); /*移动光标*/ textcolor(yellow); /*设置文本显示颜色为黄色*/ textbackground(blue); /*设置背景颜色为蓝色*/ gotoxy(10,2); /*移动光标*/ putch(0xc9); /*输出左上角边框*/ for(i=1;i44;i+) put

39、ch(0xcd); /*输出上边框水平线*/ putch(0xbb); /*输出右上角边框 */ for(i=3;i20;i+) gotoxy(10,i);putch(0xba); /*输出左垂直线*/ gotoxy(54,i);putch(0xba); /*输出右垂直线*/ gotoxy(10,20);putch(0xc8); /*输出左上角边框*/ for(i=1;i44;i+) putch(0xcd); /*输出下边框水平线*/ putch(0xbc); /*输出右下角边框*/ window(11,3,53,19); /* 制作显示菜单的窗口，大小根据菜单条数设计*/ clrscr();

40、 /*清屏*/ for(i=0;i16;i+) /*输出主菜单数组*/ gotoxy(10,i+1); cprintf(%s,menui); textbackground(black); /*设置背景颜色为黑色*/ window(1,1,80,25); /*恢复原窗口大小*/ gotoxy(10,21); /*移动光标*/ do printf(n enter you choice(06，14(exit):); /*在菜单窗口外显示提示信息*/ scanf(%s,s); /*输入选择项*/ c=atoi(s); /*将输入的字符串转化为整形数*/ while(c14); /*选择项不在014之间

41、重输*/ return c; /*返回选择项，主程序根据该数调用相应的函数*/student *init() return null;/*创建链表*/student *create() int i; int s; student *h=null,*info; /* student指向结构体的指针*/ for(;) info=(student *)malloc(sizeof(student); /*申请空间*/ if(!info) /*如果指针info为空*/ printf(nout of memory); /*输出内存溢出*/return null; /*返回空指针*/ inputs(ente

42、r no:,info-no,11); /*输入学号并校验*/ if(info-no0=) break; /*如果学号首字符为则结束输入*/ inputs(enter name:,info-name,15); /*输入姓名，并进行校验*/ printf(please input %d score n,n); /*提示开始输入成绩*/ s=0; /*计算每个学生的总分，初值为0*/ for(i=0;iscorei); /*输入成绩*/if(info-scorei100|info-scoreiscorei100|info-scoreiscorei; /*累加各门课程成绩*/ info-sum=s;

43、/*将总分保存*/ info-average=(float)s/n; /*求出平均值*/ info-order=0; /*未排序前此值为0*/ info-next=h; /*将头结点做为新输入结点的后继结点*/ h=info; /*新输入结点为新的头结点*/ return(h); /*返回头指针*/*输入字符串，并进行长度验证*/inputs(char *prompt, char *s, int count) char p255; do printf(prompt); /*显示提示信息*/ scanf(%s,p); /*输入字符串*/ if(strlen(p)count)printf(n to

44、o long! n); /*进行长度校验，超过count值重输入*/ while(strlen(p)count); strcpy(s,p); /*将输入的字符串拷贝到字符串s中*/*输出链表中结点信息*/void print(student *h) int i=0; /* 统计记录条数*/ student *p; /*移动指针*/ clrscr(); /*清屏*/ p=h; /*初值为头指针*/ printf(nnn*student*n); printf(|rec|no | name | sc1| sc2| sc3| sum | ave |order|n); printf(|-|-|-|-|-|-|-|-|-|n); while(p!=null) i+; printf(|%3d |%-10s|%-15s|%4d|%4d|%4d| %4.2f | %4.2f | %3d |n, i, p-no,p-name,p-score0,p-score1,p-score2,p-sum,p-average,p-order); p=p-next; printf(*end*n);/*删除记录*/student *delete(student *h) student *p,*q; /*p为查找到要删除的结点指针，q为其前驱指针*/ char s11; /*存