线性表栈与队列和串.docx
《线性表栈与队列和串.docx》由会员分享，可在线阅读，更多相关《线性表栈与队列和串.docx（15页珍藏版）》请在冰点文库上搜索。
线性表栈与队列和串
线性表、栈与队列和串
一、实验目的：
1、了解线性表的定义，理解线性表的存储结构。
2、了解栈的定义以及与栈有关的一些操作。
3、了解队列的定义,队列的顺序结构其基本运算的实现以及队列链式结构。
4、掌握串的常用类型以及存储结构。
二、实验环境：
装有VisualC++6.0,的计算机一台
三、实验内容与步骤：
1.线性表的简单例题线性表的简单调用：
运算结果：
2.基于栈的迷宫问题：
试验一迷宫：
代码：
#include
#defineMaxSize100
#defineM8
#defineN8
intmg[M+2][N+2]=
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
intmgpath（intxi,intyi,intxe,intye）/*求解路径为:
（xi,yi）->（xe,ye）*/
{
struct
{
inti;/*当前方块的行号*/
intj;/*当前方块的列号*/
intdi;/*di是下一可走方位的方位号*/
}st[MaxSize];/*定义栈*/
inttop=-1;/*初始化栈指针*/
inti,j,k,di,find;
top++;/*初始方块进栈*/
st[top].i=xi;st[top].j=yi;
st[top].di=-1;mg[1][1]=-1;
while（top>-1）/*栈不空时循环*/
{
i=st[top].i;j=st[top].j;di=st[top].di;/*取栈顶方块*/
if（i==xe&&j==ye）/*找到了出口,输出路径*/
{
printf（"迷宫路径如下:
\n"）;
for（k=0;k<=top;k++）
{
printf（"\t（%d,%d）",st[k].i,st[k].j）;
if（（k+1）%5==0）/*每输出每5个方块后换一行*/
printf（"\n"）;
}
printf（"\n"）;
return
（1）;/*找到一条路径后返回1*/
}
find=0;
while（di<4&&find==0）/*找下一个可走方块*/
{
di++;
switch（di）
{
case0:
i=st[top].i-1;j=st[top].j;break;
case1:
i=st[top].i;j=st[top].j+1;break;
case2:
i=st[top].i+1;j=st[top].j;break;
case3:
i=st[top].i,j=st[top].j-1;break;
}
if（mg[i][j]==0）find=1;/*找到下一个可走相邻方块*/
}
if（find==1）/*找到了下一个可走方块*/
{
st[top].di=di;/*修改原栈顶元素的di值*/
top++;/*下一个可走方块进栈*/
st[top].i=i;st[top].j=j;st[top].di=-1;
mg[i][j]=-1;/*避免重复走到该方块*/
}
else/*没有路径可走,则退栈*/
{
mg[st[top].i][st[top].j]=0;/*让该位置变为其他路径可走方块*/
top--;/*将该方块退栈*/
}
}
return（0）;/*表示没有可走路径,返回0*/
}
voidmain（）
{
mgpath（1,1,M,N）;
}
运行结果：
3、基于队列的例题：
代码：
#include
#include
#defineMaxSize100
typedefcharElemType;
typedefstruct
{
ElemTypedata[MaxSize];
intfront,rear;/*队首和队尾指针*/
}SqQueue;
voidInitQueue（SqQueue*&q）
{
q=（SqQueue*）malloc（sizeof（SqQueue））;
q->front=q->rear=0;
}
voidClearQueue（SqQueue*&q）
{
free（q）;
}
intQueueEmpty（SqQueue*q）
{
return（q->front==q->rear）;
}
intenQueue（SqQueue*&q,ElemTypee）
{
if（（q->rear+1）%MaxSize==q->front）/*队满*/
return0;
q->rear=（q->rear+1）%MaxSize;
q->data[q->rear]=e;
return1;
}
intdeQueue（SqQueue*&q,ElemType&e）
{
if（q->front==q->rear）/*队空*/
return0;
q->front=（q->front+1）%MaxSize;
e=q->data[q->front];
return1;
}
结果：
4、基于串的小例题：
代码：
代码：
#include
#defineMaxSize100
typedefstruct
{
chardata[MaxSize];
intlen;/*串长*/
}SqString;
voidStrAssign（SqString&str,charcstr[]）/*str为引用型参数*/
{
inti;
for（i=0;cstr[i]!
='\0';i++）
str.data[i]=cstr[i];
str.len=i;
}
voidStrCopy（SqString&s,SqStringt）/*s为引用型参数*/
{
inti;
for（i=0;is.data[i]=t.data[i];
s.len=t.len;
}
intStrEqual（SqStrings,SqStringt）
{
intsame=1,i;
if（s.len!
=t.len）/*长度不相等时返回0*/
same=0;
else
for（i=0;iif（s.data[i]!
=t.data[i]）/*有一个对应字符不相同时返回0*/
{
same=0;
break;
}
returnsame;
}
intStrLength（SqStrings）
{
returns.len;
}
SqStringConcat（SqStrings,SqStringt）
{
SqStringstr;
inti;
str.len=s.len+t.len;
for（i=0;istr.data[i]=s.data[i];
for（i=0;istr.data[s.len+i]=t.data[i];
returnstr;
}
SqStringSubStr（SqStrings,inti,intj）
{
SqStringstr;
intk;
str.len=0;
if（i<=0||i>s.len||j<0||i+j-1>s.len）
returnstr;/*参数不正确时返回空串*/
for（k=i-1;kstr.data[k-i+1]=s.data[k];
str.len=j;
returnstr;
}
SqStringInsStr（SqStrings1,inti,SqStrings2）
{
intj;
SqStringstr;
str.len=0;
if（i<=0||i>s1.len+1）/*参数不正确时返回空串*/
returnstr;
for（j=0;jstr.data[j]=s1.data[j];
for（j=0;jstr.data[i+j-1]=s2.data[j];
for（j=i-1;jstr.data[s2.len+j]=s1.data[j];
str.len=s1.len+s2.len;
returnstr;
}
SqStringDelStr（SqStrings,inti,intj）
{
intk;
SqStringstr;
str.len=0;
if（i<=0||i>s.len||i+j>s.len+1）/*参数不正确时返回空串*/
returnstr;
for（k=0;kstr.data[k]=s.data[k];
for（k=i+j-1;kstr.data[k-j]=s.data[k];
str.len=s.len-j;
returnstr;
}
SqStringRepStr（SqStrings,inti,intj,SqStringt）
{
intk;
SqStringstr;
str.len=0;
if（i<=0||i>s.len||i+j-1>s.len）/*参数不正确时返回串s*/
returnstr;
for（k=0;kstr.data[k]=s.data[k];
for（k=0;kstr.data[i+k-1]=t.data[k];
for（k=i+j-1;kstr.data[t.len+k-j]=s.data[k];
str.len=s.len-j+t.len;
returnstr;
}
voidDispStr（SqStrings）
{
inti;
if（s.len>0）
{
for（i=0;iprintf（"%c",s.data[i]）;
printf（"\n"）;
}
}
结果：
四、实验过程与分析：
一、线性表是具有相同特性的数据元素的一个有限序列，线性表可以是一个空表，一般开头第一个元素叫表头，最后一个叫表尾。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的线性表的基本操做：
NextMakeEmpty（L）这是一个将L变为空表的方法。
Length（L）返回表L的长度，即表中元素个数。
Get（L，i）这是一个函数，函数值为L中位置i处的元素（1≤i≤n）。
Prev（L，i）取i的前驱元素。
Next（L，i）取i的后继元素。
Locate（L，x）这是一个函数，函数值为元素x在L中的位置。
Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置。
Delete（L，p）从表L中删除位置p处的元素。
IsEmpty（L）如果表L为空表（长度为0）则返回true，否则返回false。
Clear（L）清除所有元素。
Init（L）同第一个，初始化线性表为空。
Traverse（L）遍历输出所有元素。
Find（L，x）查找并返回元素。
Update（L，x）修改元素。
Sort（L）对所有元素重新按给定的条件排序。
strstr（string1,string2）用于字符数组的求string1中出现string2的首地址。
单链表只能从前向后访问即指向头结点。
双链表是双向的既可以从前访问也可以从后访问。
二、栈是一种只能在一端进行插入或删除操作的线性表，其中允许进行插入、删除操作的一端称为栈顶。
栈的主要特点是后进先出，栈也包括删除，插入，销毁，出栈，进栈等。
在栈的运算中注意表达式转换成后缀表达式时运算符的优先级。
栈在迷宫问题中的具体应运：
从入口出发沿某方向向前试探分别从上右下左四个方向找。
如果找到则压栈，在以栈顶为方向上右下左四方向继续寻找，如果找不到栈顶退栈，向前回溯到前一个方块继续寻找。
三、队列的特点是先进先出，后进后出，首尾相连成环状。
其只能在表的一端插入，在表的另一端进行删除。
在队列中容易造成假溢出。
队列包含空队、入队、队满、出队。
五、实验总结：
1、线性表是具有相同特性的数据元素的一个有限序列，线性表可以是一个空表，一般开头第一个元素叫表头，最后一个叫表尾。
线性表的基本操作有：
MakeEmpty，Length，Get，Prev，Nexti的后继元Locate，Insert，Delete，sEmpty否则返回false，Clear，Init，Travers，Find，Update，Sort，strstr，string1。
当两个顺序表合并时，需注意相互比较排序问题。
单链表只能从前向后访问即指向头结点。
双链表是双向的既可以从前访问也可以从后访问，在插入结点时可以从前插入也可以从后插入，即头插法与尾插法。
2、栈中有栈顶，栈的主要特点是后进先出，栈包括删除，插入，销毁，出栈，进栈等。
3、队列的特点是先进先出，后进后出，首尾相连成环状。
其只能在表的一端插入，在表的另一端进行删除。
在队列中容易造成假溢出。
队列包含空队、入队、队满、出队。
六、指导教师评语及成绩：
成绩
批阅日期
2012年10月15日
升级会员 