实训1顺序表的应用.doc

《实训1顺序表的应用.doc》由会员分享，可在线阅读，更多相关《实训1顺序表的应用.doc（36页珍藏版）》请在三一办公上搜索。

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(); /*清屏*/ for(i=0;i16;i+) /*输出主菜单数组*/ gotoxy(10,i+1); cprintf(%s,menui); textbackground(BLACK); /*设置背景颜色为黑色*/ window(1,1,80,25); /*恢复原窗口大小*/ go