第二章 线性表.docx

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;

3、for(i=0;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,&A

4、i); for(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小于数

5、组B【实训2】链表的应用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

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

9、 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,&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-n

10、ext!=p1) 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,

11、m);最后程序运行结果如下所示：输入数据：数据格式为序号，密码输入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程序

12、分析（1）int 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

14、struct 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 p

15、op(sqstack *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,c

16、h);break; 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

17、; elsereturn 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(Lqueu

20、e *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)：删除任意一条短

21、信U(u)：删除所有短信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 initL

22、queue(Lqueue *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(Q

23、nodetype)=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-nex

24、t=p-next; /*删除队头结点*/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

25、 *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; 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);

26、 printf(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 inf

27、ormation(%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(Qu

28、it,please 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 D:printf(