实验一线性表和栈的应用.docx
《实验一线性表和栈的应用.docx》由会员分享，可在线阅读，更多相关《实验一线性表和栈的应用.docx（9页珍藏版）》请在冰点文库上搜索。
实验一线性表和栈的应用
实验一线性表和栈的应用
一、实验目的
1、了解线性表的顺序存储表示（结构）及实现。
2、掌握单链表的特点，掌握握单链表的基本操作：
插入、删除、查找等运算。
、3、掌握栈的基本操作：
初始化栈、判栈为空、出栈、入栈等运算。
二、实验内容
（一）线性表的顺序存储表示（结构）及实现。
阅读下列程序请注意几个问题：
（1）关于线性表的顺序存储结构的本质是：
在逻辑上相邻的两个数据元素ai-1,ai，在存储地址中也是相邻的,既地址连续。
不同的教材有不同的表示，有的直接采用一维数组，这种方法有些过时。
有的采用含‘动态分配’一维数组的结构体，这种方法过于灵活抽象（对读者要求过高）。
我们采用的是含‘静态’一维数组和线性表长的结构体：
typedefstruct
{ElemTypea[MAXSIZE];/*一维数组子域*/
intlength;/*表长度子域*/
}SqList;/*顺序存储的结构体类型*/
（2）本程序是一个完整的、子函数较多的源程序。
目的提供一个示范，提供顺序存储表示的资料，供学生参考。
[源程序]
#include
#include
#defineMAXSIZE20/*数组最大界限*/
typedefintElemType;/*数据元素类型*/
typedefstruct
{ElemTypea[MAXSIZE];/*一维数组子域*/
intlength;/*表长度子域*/
}SqList;/*顺序存储的结构体类型*/
SqLista,b,c;
/*函数声明*/
voidcreat_list（SqList*L）;
voidout_list（SqListL）;
voidinsert_sq（SqList*L,inti,ElemTypee）;
intlocat_sq（SqListL,ElemTypee）;
/*主函数*/
main（）
{inti,k,loc;ElemTypee,x;charch;
do{printf（"\n\n\n"）;
printf（"\n1.建立线性表"）;
printf（"\n2.在i位置插入元素e"）;
printf（"\n3.删除第i个元素，返回其值"）;
printf（"\n4.查找值为e的元素"）;
printf（"\n6.结束程序运行"）;
printf（"\n======================================"）;
printf（"\n请输入您的选择（1，2，3，4，6）"）;
scanf（"%d",&k）;
switch（k）
{case1:
{creat_list（&a）;out_list（a）;
}break;
case2:
{printf（"\ni,e=?
"）;scanf（"%d,%d",&i,&e）;
insert_sq（&a,i,e）;out_list（a）;
}break;
case4:
{printf（"\ne=?
"）;scanf（"%d",&e）;
loc=locat_sq（a,e）;
if（loc==-1）printf（"\n未找到%d",loc）;
elseprintf（"\n已找到，元素位置是%d",loc）;
}break;
}/*switch*/
}while（k!
=6）;
printf（"\n再见！
"）;
printf（“\n打回车键，返回。
”）;ch=getch（）;
}/*main*/
/*建立线性表*/
voidcreat_list（SqList*L）
{inti;
printf（"\nn=?
"）;scanf（"%d",&L->length）;
for（i=0;ilength;i++）{printf（"\ndata%d=?
",i）;
scanf（"%d",&（L->a[i]））;
}
}/*creat_list*/
/*输出线性表*/
voidout_list（SqListL）
{inti;charch;
printf（"\n"）;
for（i=0;i<=L.length-1;i++）printf（"%10d",L.a[i]）;
printf（“\n\n打回车键，继续。
”）;ch=getch（）;
}/*out_list*/
/*在线性表的第i个位置插入元素e*/
voidinsert_sq（SqList*L,inti,ElemTypee）
{intj;
if（L->length==MAXSIZE）printf（"\noverflow!
"）;
elseif（i<1||i>L->length+1）printf（"\nerroei!
"）;
else{for（j=L->length-1;j>i-1;j--）L->a[j+1]=L->a[j];
/*向后移动数据元素*/
L->a[i-1]=e;/*插入元素*/
L->length++;/*线性表长加1*/
}
}/*insert_sq*/
/*查找值为e的元素，返回它的位置*/
intlocat_sq（SqListL,ElemTypee）
{inti=0;
while（i<=L.length-1&&L.a[i]!
=e）i++;
if（i<=L.length-1）return（i+1）;
elsereturn（-1）;
}/*locat_sq*/
（二）单链表基本操作的实现，实现单链表的创建、插入、删除和查找。
请同学们先自己设计，然后与之对照，有错误的地方请修改：
实验要求：
1．认真阅读和掌握本实验的程序。
2．上机运行本程序。
3．保存和打印出程序的运行结果，并结合程序进行分析。
4．按照你对单链表的操作需要，重新改写主程序并运行
参考程序如下：
#include
typedefstructnode{
intdata;
structnode*next;
}NODE;
/******************************************/
NODE*Create（）{
NODE*p,*head;
intx;
head=（NODE*）malloc（sizeof（NODE））;
head->next=NULL;
printf（"Inputdata,-1toEnd!
\n"）;
scanf（"%d",&x）;
while（x!
=-1）{
p=（NODE*）malloc（sizeof（NODE））;
p->data=x;
p->next=head->next;
head->next=p;
scanf（"%d",&x）;
}
return（head）;
}
/******************************************/
voidOutput（NODE*head）{
NODE*p;
p=head;
printf（"BegintodumptheLinkList...\n"）;
while（p->next!
=NULL）{
printf（"->%d",p->next->data）;
p=p->next;
}
printf（"\nTheLinkListended!
\n"）;
}
/******************************************/
intListlen（NODE*head）{
inti=0;
NODE*p=head;
while（p->next!
=NULL）{
i++;
p=p->next;
}
return（i）;
}
/******************************************/
intGet（NODE*head,inti）{
intj=0;
NODE*p=head;
while（p->next&&jj++;
p=p->next;
}
if（!
p->next||j>i）return（0）;
elsereturn（p->data）;
}
/******************************************/
voidDel（NODE*head,inti）{
NODE*p=head;
intj=0;
while（p->next&&jj++;
p=p->next;
}
if（!
p->next||j>i-1）printf（"thepositioniswrong\n"）;
else
p->next=p->next->next;
}
/******************************************/
voidIns（NODE*head,inti,inte）{
NODE*p=head,*q;
intj=0;
while（p->next&&jj++;
p=p->next;
}
if（!
p->next&&j>i-1）printf（"Wrongposition\n"）;
else{
q=（NODE*）malloc（sizeof（NODE））;
q->data=e;
q->next=p->next;
p->next=q;
}
}
/******************************************/
main（）{
NODE*head;
intlength;
inti,element;
clrscr（）;
head=Create（）;
Output（head）;
length=Listlen（head）;
printf（"thelengthofthelinkis%d\n",length）;
printf（"inputtheorder:
\n"）;
scanf（"%d",&i）;
element=Get（head,i）;
printf（"theelementoftheorderis%d\n",element）;
printf（"inputthedelposition\n"）;
scanf（"%d",&i）;
Del（head,i）;
Output（head）;
printf（"Inputtheinsertposionandelement:
\n"）;
scanf（"%d%d",&i,&element）;
Ins（head,i,element）;
Output（head）;
getch（）;
}
（三）利用栈的基本操作实现将任意一个十进制整数转化为R进制整数
实验要求：
1．认真阅读和掌握本实验的算法。
2．上机将本算法实现。
3．保存和打印出程序的运行结果，并结合程序进行分析。
算法为：
1、定义栈的顺序存取结构
2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）
3、定义一个函数用来实现上面问题：
十进制整数X和R作为形参
初始化栈
只要Ｘ不为０重复做下列动作
将Ｘ％Ｒ入栈
X=X/R
只要栈不为空重复做下列动作
栈顶出栈
输出栈顶元素
参考程序：
（十进制转化成十六进制）
#defineMAXSIZE100
#include
structstack{
intdata[MAXSIZE];
inttop;
};
voidinit（structstack*s）{
s->top=-1;
}
intempty（structstack*s）{
if（s->top==-1）
return1;
else
return0;
}
voidpush（structstack*s,inti）{
if（s->top==MAXSIZE-1）{
printf（"Stackisfull\n"）;
return;
}
s->top++;
s->data[s->top]=i;
}
intpop（structstack*s）{
if（empty（s））{
printf（"stackisempty"）;
return-1;
}
return（s->data[s->top--]）;
}
voidtrans（intnum）{
structstacks;
intk;
init（&s）;
while（num）{
k=num%16;
push（&s,k）;
num=num/16;
}
while（!
empty（&s））{
k=pop（&s）;
if（k<10）
printf（"%d",k）;
else
printf（"%c",k+55）;
}
printf（"\n"）;
}
main（）{
intnum;
clrscr（）;
printf（"Inputanum,-1toquit:
\n"）;
scanf（"%d",&num）;
while（num!
=-1）{
trans（num）;
scanf（"%d",&num）;
}
}
作业：
从以下两个题目中任选一题,若选第一题两种方法都要做。
1、编写一个程序（ds_11.c），要求将一个带头结点的单链表倒置。
提示：
（方法一）借助栈的特征，先沿着链表从头至尾扫描一遍，将链表的每个结点的data域的值依次进栈，然后再沿着链表从头至尾扫描一遍，同时栈中元素依次出栈，并填入到链表的每个结点的data域中。
（方法二）不使用栈，先用一个指针p指向头结点以后的第一个结点（实际上是指向了一个无头结点的链表）；然后，再将该无头结点链表中的结点从前到后逐个插入到紧靠头结点的位置。
2、编写一个程序（ds_12.c），对无语法问题的表达式进行括号匹配的检验。
提示：
括号包括“（）[]”，利用栈，当在字符串中读到左括号时，将左括号进栈，当读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入，否则匹配失败，返回FALSE。
升级会员 