数据结构课程设计综合实验报告.docx

数据结构课程设计综合实验报告.docx

《数据结构课程设计综合实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计综合实验报告.docx（48页珍藏版）》请在冰点文库上搜索。

数据结构课程设计综合实验报告

数据结构课程设计

班级：

08计算机2班

小组成员：

胡雪岩（0837043）

殷莹（0837049）

钟旭茂（0837064）

数据结构课程设计开题报告表

课

题

名

称

一.集合操作（2分）

二.双栈共享空间（2分）

三.一元多项式简单计算（2分）

四.停车场管理（4分）

五.单词频率统计（4分）

六.家谱（5分）

小组名单

胡雪岩

（0837043）

殷莹

（0837049）

钟旭茂

（0837064）

题目的设计思想及数据的存储结构：

1）集合操作：

以单链表的存储方式实现功能

2）双栈共享空间：

以顺序栈的存储方式实现功能

3）一元多项式简单计算：

以单链表的存储方式实现功能

4）停车场管理：

以顺序栈和顺序队列的存储方式实现功能

5）单词频率统计：

6）家谱：

进度安排：

集合操作：

2010/4/10

双栈共享空间：

2010/4/20

一元多项式简单计算：

2010/5/17

停车场管理：

2010/5/16

单词频率统计：

2010/6/10

家谱:

2010/6/20

课程设计1线性表课程设计

一、组长：

二、组员：

三、实验日期：

2010/4/10

四、实验任务：

集合操作（2分）

基本功能要求：

（1）从文件中读入集合数据建立单链表。

（2）分别求出集合的交、并、差。

五、实验原理：

。

（具体思路看注释）

（1）定义单链表结点类型；

（2）建立函数，将数组元素以尾插法的方法插入到单链表中；

（3）建立函数以指针移动的方式将单链表显示出来；

（4）建立求并集的函数，以指针移动的方式将L1和L2中的元素放入L3中；

（5）建立求交集的函数，以指针移动的方式将L1和L2中相同的元素放到L4中；

（6）建立求差集的函数，以指针移动的方式将L1有而L2中无的元素放到L5中；

（7）建立主函数，实现以上功能；

六、实验源程序：

#include

#include

typedefstructLNode//定义单链表结点类型

{

chardata;

structLNode*next;

}LinkList;

LinkList*CreatList（LinkList*L,chara[],intn）/*尾插法插入元素*/

{

LinkList*p,*r;

inti;

L=（LinkList*）malloc（sizeof（LinkList））;

L->next=NULL;

r=L;

for（i=0;i

{

p=（LinkList*）malloc（sizeof（LinkList））;

p->data=a[i];

r->next=p;

r=p;

}

r->next=NULL;

return（L）;

}

voidDispList（LinkList*L）/*显示链表*/

{

inti=0;

LinkList*p;

p=L->next;

while（p!

=NULL）

{

printf（"%c",p->data）;

p=p->next;

}

printf（"\n"）;

}

LinkList*BingJi（LinkList*L1,LinkList*L2,LinkList*L3）/*求两个集合的并集*/

{

LinkList*p1=L1->next,*p2=L2->next,*s,*t;

L3=（LinkList*）malloc（sizeof（LinkList））;

t=L3;

while（p1!

=NULL&&p2!

=NULL）/*当L1和L2都不为空的情况下比较各自数值的大小*/

{

if（p1->datadata）/*先记录较小的数值，并移动其指针*/

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=p1->data;

t->next=s;

t=s;

p1=p1->next;

}

elseif（p1->data>p2->data）

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=p2->data;

t->next=s;

t=s;

p2=p2->next;

}

else/*当两个数值相同时仅记录一个，并移动各自的指针*/

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=p1->data;

t->next=s;

t=s;

p1=p1->next;

p2=p2->next;

}

}

while（p1==NULL&&p2!

=NULL）/*当有一个单链表已经比较完毕时，将另外一个单链表的剩余数值全部记录下来*/

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=p2->data;

t->next=s;

t=s;

p2=p2->next;

}

while（p2==NULL&&p1!

=NULL）

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=p1->data;

t->next=s;

t=s;

p1=p1->next;

}

t->next=NULL;

return（L3）;

}

LinkList*JiaoJi（LinkList*L1,LinkList*L2,LinkList*L4）/*求两集合的交集*/

{

LinkList*p1=L1->next,*p2,*s,*t;

L4=（LinkList*）malloc（sizeof（LinkList））;

t=L4;

while（p1!

=NULL）/*在L1不为空时求交集，否则交集为空*/

{

p2=L2->next;

while（p2!

=NULL&&p2->datadata）/*按顺序比较各自数值的大小，若不相等就移动较小数值的指针*/

{

p2=p2->next;

}

if（p2!

=NULL&&p2->data==p1->data）/*若相等就记录下来*/

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=p1->data;

t->next=s;

t=s;

}

p1=p1->next;

}

t->next=NULL;

return（L4）;

}

LinkList*ChaJi（LinkList*L1,LinkList*L2,LinkList*L5）/*求两集合的差集*/

{

LinkList*p1=L1->next,*p2,*s,*t;

L5=（LinkList*）malloc（sizeof（LinkList））;

t=L5;

while（p1!

=NULL）/*仅在L1不为空的情况下求差集，否则差集为空*/

{

p2=L2->next;

while（p2!

=NULL&&p2->datadata）/*若L2的数值小于L1的数值就移动指针*/

{

p2=p2->next;

}

if（!

（p2!

=NULL&&p2->data==p1->data））/*记录L1中有而L2中无的数值*/

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=p1->data;

t->next=s;t=s;

}

p1=p1->next;

}

t->next=NULL;

return（L5）;

}

voidmain（）/*主函数，实现上述功能*/

{

chara[]={'2','4','5','8'};

charb[]={'1','2','3','6','8','9'};

LinkList*L1,*L2,*L3,*L4,*L5;

L1=（LinkList*）malloc（sizeof（LinkList））;

L2=（LinkList*）malloc（sizeof（LinkList））;

L3=（LinkList*）malloc（sizeof（LinkList））;

printf（"集合L1为：

"）;

L1=CreatList（L1,a,4）;

DispList（L1）;

printf（"集合L2为：

"）;

L2=CreatList（L2,b,6）;

DispList（L2）;

L3=BingJi（L1,L2,L3）;

printf（"两个集合的并集为:

"）;

DispList（L3）;

L4=（LinkList*）malloc（sizeof（LinkList））;

L4=JiaoJi（L1,L2,L4）;

printf（"两个集合的交集为:

"）;

DispList（L4）;

L5=（LinkList*）malloc（sizeof（LinkList））;

L5=ChaJi（L1,L2,L5）;

printf（"两个集合的差集为:

"）;

DispList（L5）;

}

七、实验结果截图：

八、实验任务分工：

课程设计2双栈共享空间

一、组长：

二、组员：

三、实验日期：

2010/4/20

四、实验任务：

设STACK[MAXSIZE]为n（n>2）个栈共享。

设各栈栈顶指针为top[n]，分别指向栈顶元素的位置；设各栈栈底指针为bot[n]，分别指向栈底元素的前一个位置，这里top[i]和bot[i]确定了栈i的空间。

初始时STACK[MAXSIZE]空间平分给n个栈。

基本功能要求：

设计算法对第i栈入栈操作：

Push（&S,i,e）仅当MAXSIZE个空间全部占用时才产生溢出。

（即当第i栈满时需要调整前后栈空间）

五、实验源程序：

#include

#include

#defineMAX100

typedefstructStack{

int*elem;

inttop[2];//两个栈顶

}Stack,*SStack;

voidInit_Stack（SStacks）

{

int*p;

s->elem=（int*）malloc（MAX*sizeof（int））;

if（!

p）

exit（0）;

s->top[0]=-1;//初始化栈顶指针

s->top[1]=MAX;

}

intPush_Stack（SStacks,inte,intw）

{

if（s->top[0]+1==s->top[1]）//判断栈是否空

{

return0;

}

switch（w）//对哪个栈进行操作

{

case0:

s->top[0]++;

s->elem[s->top[0]]=e;

break;

case1:

s->top[1]--;

s->elem[s->top[1]]=e;

break;

default:

printf（"error\n"）;

exit（0）;

break;

}

return1;

}

intPop_Stack（SStacks,int*e,intw）

{

switch（w）

{

case0:

//0栈出栈

if（s->top[0]==-1）

{

return0;

}

*e=s->elem[s->top[0]];

s->top[0]--;

break;

case1:

//1栈出栈

if（s->top[1]==MAX）

{

return0;

}

*e=s->elem[s->top[1]];

s->top[1]++;

break;

default:

printf（"error\n"）;

exit（0）;

break;

}

return1;

}

intmain（）

{

intaa,bb,i;

Stacks;

Init_Stack（&s）;

for（i=0;i<5;i++）

{

Push_Stack（&s,i,0）;

Push_Stack（&s,i+10,1）;

}

while（Pop_Stack（&s,&aa,0））

{

printf（"%d",aa）;

}

printf（"\n"）;

while（Pop_Stack（&s,&bb,1））

{

printf（"%d",bb）;

}

printf（"\n"）;

return0;

}

六、实验结果截图：

课程设计3多项式加减法

实验任务：

设计一个一元多项式简单的计算器。

基本要求：

一元多项式简单计算器的基本功能为：

（1）输入并建立多项式；

（2）输出多项式；

    （3）两个多项式相加，建立并输出和多项式；

    （4）两个多项式相减，建立并输出差多项式。

实验源程序：

#include

#include

#defineMAX20//多项式最多项数

typedefstruct//定义存放多项式的数组类型

{

floatcoef;//系数

intexp;//指数

}PolyArray[MAX];

typedefstructpnode//定义单链表结点类型

{

floatcoef;//系数

intexp;//指数

structpnode*next;

}PolyNode;

voidDispPoly（PolyNode*L）//输出多项式

{

PolyNode*p=L->next;

while（p!

=NULL）

{

printf（"%gX^%d",p->coef,p->exp）;

p=p->next;

}

printf（"\n"）;

}

voidCreateListR（PolyNode*&L,PolyArraya,intn）//尾插法建表

{

PolyNode*s,*r;inti;

L=（PolyNode*）malloc（sizeof（PolyNode））;//创建头结点

L->next=NULL;

r=L;//r始终指向终端结点,开始时指向头结点

for（i=0;i

{

s=（PolyNode*）malloc（sizeof（PolyNode））;//创建新结点

s->coef=a[i].coef;

s->exp=a[i].exp;

r->next=s;//将*s插入*r之后

r=s;

}

r->next=NULL;//终端结点next域置为NULL

}

voidSort（PolyNode*&head）//按exp域递减排序

{

PolyNode*p=head->next,*q,*r;

if（p!

=NULL）//若原单链表中有一个或以上的数据结点

{

r=p->next;//r保存*p结点后继结点的指针

p->next=NULL;//构造只含一个数据结点的有序表

p=r;

while（p!

=NULL）

{

r=p->next;//r保存*p结点后继结点的指针

q=head;

while（q->next!

=NULL&&q->next->exp>p->exp）

q=q->next;//在有序表中找插入*p的前驱结点*q

p->next=q->next;//将*p插入到*q之后

q->next=p;

p=r;

}

}

}

voidAdd（PolyNode*ha,PolyNode*hb,PolyNode*&hc）//求两有序集合的并

{

PolyNode*pa=ha->next,*pb=hb->next,*s,*tc;

floatc;

hc=（PolyNode*）malloc（sizeof（PolyNode））;//创建头结点

tc=hc;

while（pa!

=NULL&&pb!

=NULL）

{

if（pa->exp>pb->exp）

{

s=（PolyNode*）malloc（sizeof（PolyNode））;//复制结点

s->exp=pa->exp;s->coef=pa->coef;

tc->next=s;tc=s;

pa=pa->next;

}

elseif（pa->expexp）

{

s=（PolyNode*）malloc（sizeof（PolyNode））;//复制结点

s->exp=pb->exp;s->coef=pb->coef;

tc->next=s;tc=s;

pb=pb->next;

}

else//pa->exp=pb->exp

{

c=pa->coef+pb->coef;

if（c!

=0）//系数之和不为0时创建新结点

{

s=（PolyNode*）malloc（sizeof（PolyNode））;//复制结点

s->exp=pa->exp;s->coef=c;

tc->next=s;tc=s;

}

pa=pa->next;

pb=pb->next;

}

}

if（pb!

=NULL）pa=pb;//复制余下的结点

while（pa!

=NULL）

{

s=（PolyNode*）malloc（sizeof（PolyNode））;//复制结点

s->exp=pa->exp;s->coef=pa->coef;

tc->next=s;tc=s;

pa=pa->next;

}

tc->next=NULL;

}

voidSub（PolyNode*ha,PolyNode*hb,PolyNode*&hc）//求两有序集合的并

{

PolyNode*pa=ha->next,*pb=hb->next,*s,*tc;

floatc;

hc=（PolyNode*）malloc（sizeof（PolyNode））;//创建头结点

tc=hc;

while（pa!

=NULL&&pb!

=NULL）

{

if（pa->exp>pb->exp）

{

s=（PolyNode*）malloc（sizeof（PolyNode））;//复制结点

s->exp=pa->exp;s->coef=pa->coef;

tc->next=s;tc=s;

pa=pa->next;

}

elseif（pa->expexp）

{

s=（PolyNode*）malloc（sizeof（PolyNode））;//复制结点

s->exp=pb->exp;s->coef=-pb->coef;

tc->next=s;tc=s;

pb=pb->next;

}

else//pa->exp=pb->exp

{

c=pa->coef-pb->coef;

if（c!

=0）//系数之和不为0时创建新结点

{

s=（PolyNode*）malloc（sizeof（PolyNode））;//复制结点

s->exp=pa->exp;s->coef=c;

tc->next=s;tc=s;

}

pa=pa->next;

pb=pb->next;

}

}

if（pb!

=NULL）//复制余下的结点

{

while（pb!

=NULL）

{

s=（PolyNode*）malloc（sizeof（PolyNode））;//复制结点

s->exp=pb->exp;s->coef=-pb->coef;

tc->next=s;tc=s;

pb=pb->next;

}

tc->next=NULL;

}

if（pa!

=NULL）

{

while（pa!

=NULL）

{

s=（PolyNode*）malloc（sizeof（PolyNode））;//复制结点

s->exp=pa->exp;s->coef=pa->coef;

tc->next=s;tc=s;

pa=pa->next;

}

tc->next=NULL;

}

}

voidmain（）

{

PolyNode*ha,*hb,*hc;

PolyArraya={{1.2,0},{2.5,1},{3.2,3},{-2.5,5}};

PolyArrayb={{-1.2,0},{2.5,1},{3.2,3},{2.5,5},{5.4,10}};

CreateListR（ha,a,4）;

CreateListR（hb,b,5）;

printf（"原多项式A:

"）;DispPoly（ha）;

printf（"原多项式B:

"）;DispPoly（hb）;

Sort（ha）;

Sort（hb）;

printf（"有序多项式A:

"）;DispPoly（ha）;

printf（"有序多项式B:

"）;DispPoly（hb）;

Add（ha,hb,hc）;

printf（"多项式相加:

"）;DispPoly（hc）;

Sub（ha,hb,hc）;

printf（"多项式相减:

"）;DispPoly（hc）;

}

实验结果截图：

课程设计4停车场管理

实验任务：

停车场是一个能放n辆车的狭长通道，只有一个大门，汽车按到达的先后次序停放。

若车场满了，车要停在门外的便道上等候，一旦有车走，则便道上第一辆车进入。

当停车场中的车离开