数据结构实验报告.docx
《数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告.docx（14页珍藏版）》请在冰点文库上搜索。
数据结构实验报告
数据结构实验报告
第四次实验
学号：
20141060106姓名：
叶佳伟
一、实验目的
1、复习线性表、栈、队列的逻辑结构、存储结构及基本操作；
2、掌握顺序表、（带头结点）单链表、顺序栈、链队列；3、了解有顺表、链栈、循环队列。
3、了解有顺表、链栈、循环队列。
二、实验内容
1、（必做题）假设有序表中数据元素类型是整型，请采用顺序表或（带头结点）单链表实现：
（1）OrderInsert（&L,e,int（*compare）（a,b））//根据有序判定函数compare，在有序表L的适当位置插入元素e；
（2）OrderInput（&L,int（*compare）（a,b））//根据有序判定函数compare，并利用有序插入函数OrderInsert，构造有序表L；
（3）OrderMerge（&La,&Lb,&Lc,int（*compare）（））//根据有序判定函数compare，将两个有序表La和Lb归并为一个有序表Lc。
2、（必做题）假设栈中数据元素类型是字符型，请采用顺序栈实现栈的以下基本操作：
（1）StatusInitStack（&S）//构造空栈S；
（2）StatusPush（&S,e）//元素e入栈S；
（3）StatusPop（&S,&e）//栈S出栈，元素为e。
3、（必做题）假设队列中数据元素类型是字符型，请采用链队列实现队列的以下基本操作：
（1）StatusInitQueue（&Q）//构造空队列Q；
（2）StatusEnQueue（&Q,e）//元素e入队列Q；
（3）StatusDeQueue（&Q,&e）//队列Q出队列，
元素为e。
三、算法描述
（采用自然语言描述）
⒈⑴分别插入第一个链表和第二个链表的数据；
⑵根据有序判定函数compare，将两个有序表La和Lb归并为个有序表。
⑶输出归并后的有序表。
2.
⑴构造一个栈的结构体
⑵利用函数initstack构造空栈
⑶Push函数将元素依次存储到栈里
⑷利用pop函数输出栈顶元素
3.
1构造Queueptr的结构体
2构造一个队列的结构体
3利用函数InitQueue构造空队列
4EnQueue函数将元素依次存储到栈里
5利用DeQueue函数输出栈顶元素
四、详细设计
（画出程序流程图）
五、程序代码
（给出必要注释）
第一题：
#include
#include
typedefstructLNode
{intdate;
structLNode*next;
}LNode,*Link;
typedefstructLinkList
{Linkhead;
intlen;
}LinkList;
intcompare（LinkList*L,inte）
{intLc=0;
Linkp;
p=L->head;
p=p->next;
while（p!
=NULL）
{if（e>p->date）
{p=p->next;Lc++;}
else
returnLc;
}
returnLc;
}
voidOrderInsert（LinkList*L,inte,int（*compare）（））
{Linktemp,p,q;
intLc,i;
temp=（Link）malloc（sizeof（LNode））;
temp->date=e;
p=q=L->head;
p=p->next;
Lc=（*compare）（L,e）;
if（Lc==L->len）
{while（q->next!
=NULL）
{q=q->next;}
q->next=temp;
temp->next=NULL;
}
else
{for（i=0;i{p=p->next;q=q->next;}
q->next=temp;temp->next=p;
}
++L->len;
}
voidOrderMerge（LinkList*La,LinkList*Lb,int（*compare）（））
{inti,Lc=0;
Linktemp,p,q;
q=La->head->next;
while（q!
=NULL）
{p=Lb->head;
temp=（Link）malloc（sizeof（LNode））;
temp->date=q->date;
Lc=（*compare）（Lb,q->date）;
if（Lc==Lb->len）
{while（p->next!
=NULL）
{p=p->next;}
p->next=temp;
temp->next=NULL;
}
else
{for（i=0;i{p=p->next;}
temp->next=p->next;
p->next=temp;
}
q=q->next;
++Lb->len;
}
}
LinkList*Initialize（LinkList*NewList）
{inti;
Linktemp;
NewList=（LinkList*）malloc（（2+1）*sizeof（LinkList））;
for（i=0;i<2+1;i++）
{temp=（Link）malloc（sizeof（LNode））;
temp->date=0;
temp->next=NULL;
（NewList+i）->head=temp;
（NewList+i）->len=0;
}
returnNewList;
}
voidInsert（LinkList*NewList）
{inta,i;
charc;
printf（"在第1个表中插入数据，以空格和回车为间隔，输入”.”对下个表插入数据\n"）;
for（i=0;i<2;i++）
{while
（1）
{scanf（"%d",&a）;
c=getchar（）;
if（c=='.'）
{if（i<2-2）
printf（"在第%d个表中插入数据，以空格和回车为间隔，输入”.”对下个表插入数据\n",i+2）;
elseif（i==2-2）
printf（"在第%d个表中插入数据，以空格和回车为间隔，输入”.”结束输出\n",i+2）;
break;
}
else
{OrderInsert（（NewList+i）,a,compare）;}
}
}
}
voidShow（LinkList*L）
{Linkp;
p=L->head->next;
while（p!
=NULL）
{printf（"%d\t",p->date）;
p=p->next;
}
}
voidDisplay（LinkList*NewList,void（*Show）（））
{printf（"所有有序表如下\n"）;
printf（"第一个有序表为：
\n"）;
（*Show）（NewList+0）;
printf（"\n"）;
printf（"第二个有序表为：
\n"）;
（*Show）（NewList+1）;
printf（"\n"）;
printf（"归并后有序表为\n"）;
（*Show）（NewList+2）;
}
intmain（）
{LinkList*NewList=NULL;
inti;
printf（"\t开始插入数据\n"）;
NewList=Initialize（NewList）;
Insert（NewList）;
for（i=0;i<2;i++）
{OrderMerge（NewList+i,NewList+2,compare）;}
Display（NewList,Show）;
return0;
第二题：
#include
#include
#include
#defineM50
typedefstruct//定义一个栈结构
{
inttop;
intarray[M];
}Stack;
voidInit（Stack*s）;//初始化栈的函数
voidPush（Stack*s,intdata）;//进行压栈操作的函数
voidTraverse（Stack*s）;//遍历栈函数
charPop（Stack*s）;//进行出栈操作的栈函数
voidClear（Stack*s）;//清空栈的函数
intmain（）
{
Stacks;//定义一个栈
inti;
intnum;
chardata;//临时保存用户输入的数据
charre_num;//保存pop函数的返回值
Init（&s）;
printf（"你想输入几个数据:
"）;
scanf（"%d",&num）;
for（i=0;i{
printf（"第%d个字符:
",i+1）;
scanf（"%s",&data）;
Push（&s,data）;
}
Traverse（&s）;//调用遍历函数
printf（"你想去掉几个字符:
"）;
scanf（"%d",&num）;
printf（"你去掉的字符是:
"）;
for（i=0;i{
re_num=Pop（&s）;//调用Pop函数，并把返回至赋给re.num
printf（"%c",re_num）;
}
printf（"看看删除后还有啥:
"）;
Traverse（&s）;
printf（"\n"）;
Clear（&s）;//调用清空栈函数
printf（"遍历下看看栈空没\n"）;
Traverse（&s）;
printf（"\n"）;
return0;
}
voidInit（Stack*s）//进行栈的初始化函数
{
s->top=-1;
}
voidPush（Stack*s,intdata）/*进栈*/
{
if（s->top>=M-1）return;/*full*/
s->top++;
s->array[s->top]=data;
}
voidTraverse（Stack*s）//遍历栈的函数
{
inti;
for（i=0;i<=s->top;i++）
printf（"%2c",s->array[i]）;
}
charPop（Stack*s）//进行出栈操作函数
{
charx;
x=s->array[s->top];
s->top--;
returnx;
}
voidClear（Stack*s）//清空栈的函数
{
s->top=-1;
}
第三题：
#include
#include
typedefvoidStatus;
typedefintQElemType;
#defineSTACK_INIT_SIZE10//初始容量
#defineSTACKINCREMENT5//容量增量
typedefstructQNode{
QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct{
QueuePtrfront;//队头指针
QueuePtrrear;//队尾指针
}LinkQueue;
StatusInitQueue（LinkQueue&Q）{
//构造一个空对列Q
Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
if（!
Q.front）exit（-1）;
Q.front->next=NULL;
}
StatusEnQueue（LinkQueue&Q,QElemTypee）{
//插入元素e为对列Q的新元素
QueuePtrp;
p=（QueuePtr）malloc（sizeof（QNode））;
if（!
p）printf（"OVERFLOW"）;
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
StatusDeQueue（LinkQueue&Q,QElemTypee）{
//若对列不空，用e返回其值，并返回OK
//否则返回ERROR
QueuePtrp;
if（Q.front==Q.rear）printf（"ERROR"）;
p=Q.front->next;
e=p->data;
printf（"对列中的队头元素为:
%d\n",e）;
Q.front->next=p->next;
if（Q.rear==p）Q.rear=Q.front;
free（p）;
}
main（）
{LinkQueueQ;
intn,i;
QElemTypee;
InitQueue（Q）;
printf（"请输入队列中要入队列的元素个数:
\n"）;
scanf（"%d",&n）;
for（i=0;i{printf（"队列里的第%d个元素为:
",i+1）;
scanf（"%d",&e）;
EnQueue（Q,e）;}
printf（"\n"）;
DeQueue（Q,e）;
}
六、测试和结果
（给出测试用例以及测试结果）
第二题：
：
第三题：
七、用户手册
（告诉用户如何使用程序）
1.使用MicrosoftVisualC++
2.使用MicrosoftVisualC++
3.使用MicrosoftVisualC++
升级会员 