第二章 线性表.docx

第二章 线性表.docx

《第二章 线性表.docx》由会员分享，可在线阅读，更多相关《第二章 线性表.docx（70页珍藏版）》请在冰点文库上搜索。

第二章线性表

第二章　线性表

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语言中，可以使用一维数组来存储顺序表。

1）初始化两个线性表：

输入两个数组A和B。

2）调用子函数intcompare（intA[],intB[],intm）比较两个数组的大小：

比较A[i]和B[i]：

若A[i]>B[i]返回BIG

若A[i]

若A[i]==B[i]且i

3．程序源代码

该实例程序的源代码如下：

#include"stdio.h"

#defineMAXSIZE100/*最大数组元素个数*/

#defineBIG1

#defineSMALL-1

#defineEQUAL0

intcompare（intA[],intB[],intm）/*比较数组数据*/

{inti;

for（i=0;i

{if（A[i]>B[i]）

returnBIG;/*返回在A>B*/

else

if（A[i]

returnSMALL;/*返回在A

}

returnEQUAL;/*返回在A=B*/

}

/*主程序*/

main（）

{intA[MAXSIZE],B[MAXSIZE];

intm,s,i;

printf（"请输入数据的大小m（0-100）:

"）;

scanf（"%d",&m）;

while（m<=0&&m>=MAXSIZE）

{printf（"请输入数据的大小m（0-100）:

"）;

scanf（"%d",&m）;}

for（i=0;i

{printf（"请输入数组A的第%d个数组元素",i+1）;

scanf（"%d",&A[i]）;}

for（i=0;i

{printf（"请输入数组B的第%d个数组元素",i+1）;

scanf（"%d",&B[i]）;}

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】链表的应用

1．实训说明

本实训是有关线性表的链式存储结构的应用，在本实训的实例程序中，通过C语言中提供的结构指针来存储线性表，利用malloc函数动态地分配存储空间。

通过对本实训的学习，可以理解线性表在链序存储结构下的操作方法。

在实训中，我们设计一个程序求出约瑟夫环的出列顺序。

约瑟夫问题的一种描述是：

编号为1，2，…，n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。

例如，n=7,7个人的密码依次为：

3,1,7,2,4,8,4,m的初值取6，则正确的出列顺序应为6,1,4,7,2,3,5。

要求使用单向循环链表模拟此出列过程。

2．程序分析

约瑟夫环的大小是变化的，因此相应的结点也是变化的，使用链式存储结构可以动态的生成其中的结点，出列操作也非常简单。

用单向循环链表模拟其出列顺序比较合适。

用结构指针描述每个人：

structJoseph

{intnum;/*环中某个人的序号*/

intsecret;/环中某个人的密码*/

structJoseph*next;/指向其下一个的指针*/};

1）初始化约瑟夫环：

调用函数structJoseph*creat（）生成初始约瑟夫环。

在该函数中使用head指向表头。

输入序号为0时结束，指针p1指向的最后结束序号为0的结点没有加入到链表中，p2指向最后一个序号为非0的结点（最后一个结点）。

2）报数出列：

调用函数voilsort（structJoseph*head,intm），使用条件p1->next!

=p1判断单向链表非空，使用两个指针变量p1和p2，语句p2=p1;p1=p1->next;移动指针，计算结点数（报数）；结点p1出列时直接使用语句：

p2->next=p1->next，取出该结点中的密码作为新的循环终值。

3．程序源代码

该实例程序的源代码如下：

#defineNULL0

#defineLENGTHsizeof（structJoseph）

#include"stdlib.h"

#include"stdio.h"

structJoseph

{intnum;

intsecret;

structJoseph*next;

};/*定义结点num为序号，secret为密码*/

/*创建初始链表函数*/

structJoseph*creat（）

{structJoseph*head;

structJoseph*p1,*p2;

intn=0;

p1=p2=（structJoseph*）malloc（LENGTH）;

scanf（"%d,%d",&p1->num,&p1->secret）;

head=NULL;

while（p1->num!

=0）

{n=n+1;

if（n==1）head=p1;

elsep2->next=p1;

p2=p1;

p1=（structJoseph*）malloc（LENGTH）;

scanf（"%d,%d",&p1->num,&p1->secret）;

}

p2->next=head;

return（head）;

}

/*报数出列*/

voidsort（structJoseph*head,intm）

{structJoseph*p1,*p2;

inti;

if（head==NULL）

printf（"\n链表为空!

\n"）;

p1=head;

while（p1->next!

=p1）

{for（i=1;i

{p2=p1;p1=p1->next;}

p2->next=p1->next;

m=p1->secret;

printf（"%d",p1->num）;

p1=p2->next;

}

if（p1->next==p1）

printf（"%d",p1->num）;

}

main（）

{structJoseph*head;

intm;

printf（"\n输入数据:

数据格式为序号，密码\n输入0，0为结束\n"）;

head=creat（）;

printf（"输入m值\n"）;

scanf（"%d",&m）;

if（m<1）printf（"error!

请输入一个合法的m值!

"）;

printf（"出列的序号是:

\n"）;

sort（head,m）;

}

最后程序运行结果如下所示：

输入数据：

数据格式为序号，密码

输入0，0为结束

1，3↙<回车>

2，1↙<回车>

3，7↙<回车>

4，2↙<回车>

5，4↙<回车>

6，8↙<回车>

7，4↙<回车>

0，0↙<回车>

输入m值

6↙<回车>

出列的序号是

6147235

第三章栈和队列

3.4实训

【实训1】栈的应用

1．实训说明

本实训是关于栈的应用，栈在各种高级语言编译系统中应用十分广泛，在本实训程序中，利用栈的“先进后出”的特点，分析C语言源程序代码中的的括号是否配对正确。

通过本对本实训的学习，可以理解的基本操作的实现。

本实训要求设计一个算法，检验C源程序代码中的括号是否正确配对。

对本算法中的栈的存储实现，我们采用的是顺序存储结构。

要求能够在某个C源程序上文件上对所设计的算法进行验证。

2．程序分析

（1）intinitStack（sqstack**s）初始化一个栈

（2）intpush（sqstack*s,charx）入栈，栈满时返回FALSE

（3）charpop（sqstack*s）出栈，栈空时返回NULL

（4）intEmpty（sqstack*s）判断栈是否为空，为空时返回TRUE

（5）intmatch（FILE*f）对文件指针f对指的文件进行比较括号配对检验，从文件中每读入一个字符ch=fgetc（f），采用多路分支switch（ch）进行比较：

①若读入的是“[”、“{”或“（”，则压入栈中，

②若读入的是“]”，则：

若栈非空，则出栈，判断出栈符号是否等于“[”，不相等，则返回FALSE。

③若读入的是“}”，则：

若栈非空，则出栈，判断出栈符号是否等于“{”，不相等，则返回FALSE。

④若读入的是“）”，则：

若栈非空，则出栈，判断出栈符号是否等于“（”，不相等，则返回FALSE。

⑤若是其它字符，则跳过。

文件处理到结束时，如果栈为空，则配对检验正确，返回TRUE。

（6）主程序main（）中定义了一个文件指针，输入一个已经存在的C源程序文件。

3．程序源代码

#defineMAXNUM200

#defineFALSE0

#defineTRUE1

#include"stdio.h"

#include"stdlib.h"

#include"string.h"

typedefstruct{

charstack[MAXNUM];

inttop;}sqstack;/*定义栈结构*/

intinitStack（sqstack**s）

{/*初始化栈*/

if（（*s=（sqstack*）malloc（sizeof（sqstack）））==NULL）returnFALSE;

（*s）->top=-1;

returnTRUE;

}

intpush（sqstack*s,charx）

{/*将元素x插入到栈s中，作为s的新栈顶*/

if（s->top>=MAXNUM-1）returnFALSE;/*栈满*/

s->top++;

s->stack[s->top]=x;

returnTRUE;

}

charpop（sqstack*s）

{/*若栈s不为空，则删除栈顶元素*/

charx;

if（s->top<0）returnNULL;/*栈空*/

x=s->stack[s->top];

s->top--;

returnx;

}

intEmpty（sqstack*s）

{/*栈空返回TRUE,否则返回FALSE*/

if（s->top<0）returnTRUE;

returnFALSE;}

intmatch（FILE*f）

{charch,ch1;sqstack*S;

initStack（&S）;

while（!

feof（f））

{ch=fgetc（f）;

switch（ch）

{case'（':

case'[':

case'{':

push（S,ch）;printf（"%c",ch）;break;

case'）':

if（Empty（S）!

=TRUE）

{ch1=pop（S）;printf（"%c",ch）;

if（ch1=='（'）

break;

else

returnFALSE;}

else

returnFALSE;

case']':

if（Empty（S）!

=TRUE）

{ch1=pop（S）;printf（"%c",ch）;

if（ch1=='['）

break;

else

returnFALSE;}

else

returnFALSE;

case'}':

if（Empty（S）!

=TRUE）

{ch1=pop（S）;printf（"%c",ch）;

if（ch1=='{'）

break;

else

returnFALSE;}

else

returnFALSE;

default:

break;

}

}

if（Empty（S）!

=TRUE）

returnFALSE;

returnTRUE;}

voidmain（）

{FILE*fp;charfn[20];

printf（"请输入文件名：

"）;

scanf（"%s",fn）;

if（（fp=fopen（fn,"r"））==NULL）

{printf（"不能打开文件\n"）;

exit（0）;}

elseif（match（fp）==TRUE）

printf（"括号正确\n"）;

else

printf（"括号不正确\n"）;

fclose（fn）;

}

最后程序运行结果如下所示：

请输入文件名：

F:

\exam.c<回车>

（）{[]（）}括号正确

【实训2】队列的应用

1．实训说明

本实训是队列的一种典型的应用，队列是一种“先到先服务”的特殊的线性表，本实训要求模拟手机短信功能，使用链式存储结构的队列，进行动态地增加和删除结点信息。

通过本实训的学习，可以理解队列的基本操作的实现。

设计程序要求，模拟手机的某些短信息功能。

功能要求：

（1）接受短信息，若超过存储容量（如最多可存储20条），则自动将最早接受的信息删除。

（2）显示其中任意一条短信息。

（3）逐条显示短信息。

（4）删除其中的任意一条短信息。

（5）清除。

2．程序分析

采用结构体指针定义存储短信结点：

typedefstructQnode

{chardata[MAXNUM];/*字符数组存储短信*/

structQnode*next;

}Qnodetype;/*定义队列的结点*/

定义队列：

typedefstruct

{Qnodetype*front;/*头指针*/

Qnodetype*rear;/*尾指针*/

intnumber;/*短信数量*/

}Lqueue;

（1）intinitLqueue（Lqueue**q）初始化短信队列。

（2）intLInQueue（Lqueue*q,charx[]）入队列，将字符串x加入到队列尾部。

（3）char*LOutQueue（Lqueue*q）出队列，删除队头元素，返回其中的字符串。

（4）voidget（Lqueue*q,charx[]）接收短数，若短信数量超过20条，则删除队头短信。

（5）voiddeleteall（Lqueue*q）清除所有短信。

（6）voiddeleteone（Lqueue*q,intn）删除第n条短信。

（7）voiddisplayall（Lqueue*q）显示所有短信。

（8）voiddisplayone（Lqueue*q,intn）显示第n条短信。

在main（）函数中，采用菜单方式，菜单中同时显示出已有的短信数量，由用户选择输入命令，实现程序要求功能，命令说明：

R（r）：

接收短信

L（l）：

显示任意一条短信

A（a）：

显示所有短信

D（d）：

删除任意一条短信

U（u）：

删除所有短信

Q（q）：

退出

3．程序源代码

#defineMAXNUM70

#defineFALSE0

#defineTRUE1

#include"stdio.h"

#include"stdlib.h"

#include"string.h"

typedefstructQnode

{chardata[MAXNUM];

structQnode*next;

}Qnodetype;/*定义队列的结点*/

typedefstruct

{Qnodetype*front;/*头指针*/

Qnodetype*rear;/*尾指针*/

intnumber;/*短信数量*/

}Lqueue;

intinitLqueue（Lqueue**q）

{/*创建一个空链队列q*/

if（（（*q）->front=（Qnodetype*）malloc（sizeof（Qnodetype）））==NULL）returnFALSE;

（*q）->rear=（*q）->front;strcpy（（*q）->front->data,"head"）;

（*q）->front->next=NULL;（*q）->number=0;

returnTRUE;}

intLInQueue（Lqueue*q,charx[]）

{/*将元素x插入到链队列q中，作为q的新队尾*/

Qnodetype*p;

if（（p=（Qnodetype*）malloc（sizeof（Qnodetype）））==NULL）returnFALSE;

strcpy（p->data,x）;

p->next=NULL;　　　/*置新结点的指针为空*/

q->rear->next=p;/*将链队列中最后一个结点的指针指向新结点*/

q->rear=p;/*将队尾指向新结点*/

returnTRUE;

}

char*LOutQueue（Lqueue*q）

{/*若链队列q不为空，则删除队头元素，返回其元素值*/

charx[MAXNUM];

Qnodetype*p;

if（q->front->next==NULL）returnNULL;/*空队列*/

p=q->front->next;/*取队头*/

q->front->next=p->next;/*删除队头结点*/

if（p->next==NULL）q->rear=q->front;

strcpy（x,p->data）;

free（p）;

returnx;

}

voidget（Lqueue*q,charx[]）

{/*接受短信*/

intn;

if（q->number==20）

{LOutQueue（q）;q->number--;}

LInQueue（q,x）;

q->number++;}

voiddeleteall（Lqueue*q）

{/*删除所有短信*/

while（q->front!

=q->rear）

LOutQueue（q）;q->number=0;}

voiddeleteone（Lqueue*q,intn）

{/*删除第n条短信*/

Lqueue*p;Qnodetype*s;

inti;

p=q;i=1;

while（i

{p->front=p->front->next;

i=i+1;}

s=p->front->next;

p->front->next=p->front->next->next;

free（s）;

q->number--;}

voiddisplayall（Lqueue*q）

{/*显示所有短信*/

Lqueue*p;charx[MAXNUM];

p=q;

while（p->front!

=q->rear）

{

p->front=p->front->next;

printf（"%s\n",p->front->data）;

}printf（"\n"）;

}

voiddisplayone（Lqueue*q,intn）

{/*显示第n条短信*/

Lqueue*p;Qnodetype*s;

inti;

p=q;i=1;

while（i

{p->front=p->front->next;

i=i+1;}

s=p->front->next;

printf（"%s\n",s->data）;

}

voidmain（）

{Lqueue*Lp;inti;Qnodetype*headnode;

charcommand,ch[MAXNUM];

initLqueue（&Lp）;headnode=Lp->front;

while

（1）

{printf（"Getinformation（%d）,pleaseenterR\n",Lp->number）;

printf（"Displayoneinformation（%d）,pleaseenterL\n",Lp->number）;

printf（"Displayallinformation（%d）,pleaseenterA\n",Lp->number）;

printf（"Deleteoneinformation（%d）,pleaseenterD\n",Lp->number）;

printf（"Deleteallinformation（%d）,pleaseenterU\n",Lp->number）;

printf（"Quit,pleaseenterQ\n"）;

printf（"pleaseinputcommand:

"）;

scanf（"%c",&command）;

switch（command）

{case'r':

case'R':

gets（ch）;Lp->front=headnode;get（Lp,ch）;break;

case'l':

case'L':

printf（"enterNo.:

"）,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（"