计算机软件基础二数据结构实验指导.docx

计算机软件基础二数据结构实验指导.docx

《计算机软件基础二数据结构实验指导.docx》由会员分享，可在线阅读，更多相关《计算机软件基础二数据结构实验指导.docx（36页珍藏版）》请在冰点文库上搜索。

计算机软件基础二数据结构实验指导

实验一线性表的应用

1．实验名称

商品信息管理程序。

2．实验学时

4学时。

3.实验目的

（1）复习和巩固线性表中的相关概念和知识；

（2）熟悉线性表的顺序存储或链式存储结构的具体实现方法；

（3）掌握线性表的建立、插入、删除、查找、输出等基本操作算法；

（4）提高灵活运用所学算法、采用顺序线性表或链式线性表处理实际问题的能力；

（5）提高学生综合运用所学知识分析问题和解决问题的能力。

4．实验要求

本实验要求使用高级编程语言C语言编写一个商品信息管理程序，商品信息表采用顺序存储结构或链式存储结构存放。

该程序中各功能均需采用独立的模块实现；程序应具有菜单选择功能；并允许用户在运行该程序过程中多次选择执行不同的功能。

要求学生对整个系统的框架进行设计，规划数据的存储结构，编写出重要模块的算法。

每人一组完成，上机之前要有预习准备。

有兴趣的同学可在程序中增加商品入库的功能。

实验设备：

PC机一台，C语言IDE编程环境MicorosoftVisualC++6.0或者TurboC2.0。

5.实验内容

编写一个超市商品信息管理程序，实现超市商品信息管理中的录入、插入、删除、查找、销售及显示等功能。

商品信息包括商品的编号、名称、单价和数量等四项。

具体商品信息的数据类型定义如下：

typedefstructgoodstype

{longintnum;

charname[20];

intprice;

intstock;}GOODS;

（1）录入功能：

录入商品信息表中所有商品的信息，以顺序或链式存储结构存放，原始商品信息表中的商品信息按商品编号升序排列；

（2）插入功能：

输入一种新商品的信息，将新商品信息插入到线性表中的恰当位置，使商品信息表中的商品信息依然按商品编号有序排列；

（3）删除功能：

给定一种商品的编号，删除线性表中该商品的信息；

（4）查找功能：

给定一种商品的编号，在线性表中查找该商品的信息；

（5）显示功能：

输出线性表中所有商品的信息；

（6）销售功能：

输入客户选择的商品编号和所需数量，若该商品存在，计算应付的钱数并修改该商品的库存量；若无该商品或商品数量不足，则给出相应的提示信息；（必做）

能够一次售出多种不同的商品并打印购物小票（选做）

6.算法说明

（1）录入功能

即完成线性表的建立，输入商品信息时，最好以结束标志控制输入过程的进行。

例如当输入的商品编号为-1时，商品信息录入结束。

参考程序一：

（顺序线性表）

typedefstruct

{GOODSlist[MAXLEN];

intlength;

}SeqList;//顺序表类型定义，list为存放元素值的一维数组，length用于存放表长

voidInit_List（SeqList*L）

//初始化顺序表，以输入商品编号为-1作为输入结束标志

{longtnum;

intn=0;

printf（"inputnum:

"）;

scanf（"%ld",&tnum）;

while（tnum!

=-1）

{L->list[n].num=tnum;

printf（"inputname:

"）;

scanf（"%s",（L->list[n]）.name）;

printf（"inputprice:

"）;

scanf（"%d",&（L->list[n].price））;

printf（"inputstock:

"）;

scanf（"%d",&（L->list[n].stock））;

n++;

printf（"inputnum:

"）;

scanf（"%ld",&tnum）;

}

L->length=n;

}

参考程序二：

（链式线性表）

//结点类型定义，data用于存放结点的数据值，next用于存放下一结点的地址

typedefstructnodetype

{GOODSdata;

structnodetype*next;

}NODE;

NODE*Create_Link（）

//尾接法创建链表，以输入商品编号为-1作为输入结束标志

{NODE*head,*p,*s;

GOODSx;

longtnum;

head=（NODE*）malloc（LEN）;

head->next=NULL;

p=head;

printf（"inputnum:

"）;

scanf（"%ld",&tnum）;

while（tnum!

=-1）

{x.num=tnum;

printf（"inputname:

"）;

scanf（"%s",x.name）;

printf（"inputprice:

"）;

scanf（"%f",&x.price）;

printf（"inputstock:

"）;

scanf（"%d",&x.stock）;

s=（NODE*）malloc（LEN）;

s->data=x;

s->next=NULL;

p->next=s;

p=s;

printf（"inputnum:

"）;

scanf（"%ld",&tnum）;

}

return（head）;

}

（2）插入功能

编写该插入算法的关键是要找到插入的恰当位置；若从线性表的前端向后找插入位置，则需找到第一个比待插元素的关键字大的元素，新元素插在该元素之前；若从线性表的后端向前找插入位置，则需找到第一个比待插元素关键字小的元素，新元素插在该元素之后。

插入算法的程序流程图如图1-1所示。

注意：

在链式线性表的查找只能从前向后找；

顺序线性表插入新元素之前，必然要对插入位置后面的所有元素进行后移。

（3）删除功能

编写该算法的关键是先要在线性表上找到待删元素，之后才能进行删除。

删除算法的程序流程图如图1-2所示。

（4）查找功能

查找的过程和思想与删除算法中进行的查找相同。

参考程序一：

（顺序线性表）

intSearchList（SeqList*L,longtnum）

//在顺序表上从后向前查找编号为tnum的元素

//查找成功返回元素所在的位置，查找失败返回-1

{inti;

i=L->length-1;

while（L->list[i].num!

=tnum&&i>=0）

i--;

return（i）;

}

参考程序二：

（链式线性表）

NODE*SearchLink（NODE*head,longknum）

//在单链表上从前向后查找编号为tnum的结点

//查找成功返回结点的地址，查找失败返回空指针NULL

{NODE*p;

p=head->next;

while（p!

=NULL&&p->data.num!

=knum）

p=p->next;

return（p）;

}

（5）显示功能

即对线性表中的元素从前到后逐个进行输出。

参考程序一：

（顺序线性表）

voidOutputList（SeqList*L）

//显示功能函数，逐个输出顺序表中各个元素的值

{inti;

printf（"numnamepricestock\n"）;

for（i=0;ilength;i++）

printf（"%6ld%16s%10d%6d\n",L->list[i].num,L->list[i].name,L->list[i].price,L->list[i].stock）;

}

参考程序二：

（链式线性表）

voidOutputLink（NODE*head）

//显示功能函数，逐个输出链表中各个结点的数据值

{NODE*p;

p=head->next;

printf（"numnamepricestock\n"）;

while（p!

=NULL）

{printf（"%6ld%16s%10.2f%6d\n",p->data.num,p->data.name,p->data.price,p->data.stock）;

p=p->next;}

}

（6）销售功能

基本的销售功能流程如下图所示，若要实现一次售出多种货物则需在此基础上加入循环结构，另外需累计所有商品的钱数并将所有售出的商品信息存储下来（可存放在一个一维数组中）以便打印出购物小票。

最基本的销售功能算法的程序流程图如图1-3所示。

（7）菜单函数

输出系统功能菜单信息并允许用户输入选项。

参考程序：

intmenu（）

//菜单函数，返回用户输入的选项

{intch;

printf（"*****************************\n"）;

printf（"*1------------input*\n"）;

printf（"*2------------output*\n"）;

printf（"*3------------insert*\n"）;

printf（"*4------------delete*\n"）;

printf（"*5------------search*\n"）;

printf（"*6------------sale*\n"）;

printf（"*0------------exit*\n"）;

printf（"*****************************\n"）;

printf（"pleaseinputyourchoice:

（0-6）\n"）;

scanf（"%d",&ch）;

return（ch）;

}

（8）主函数

主要是利用循环结构实现对系统各个功能的多次选择，每次选择之前应先输出系统功能菜单信息，当用户选择后根据用户的选项调用相应功能模块，完成特定的任务。

参考程序：

（主要给出主函数的框架语句，具体功能的实现语句在此略去）

voidmain（）

{intch;

//主函数中其它变量的定义在此略去

ch=1;

while（ch!

=0）

{ch=menu（）;

switch（ch）

{case1:

//调用线性表的录入函数，语句略

break;

case2:

//调用线性表的显示函数，语句略

break;

case3:

//进行线性表的插入，语句略

break;

case4:

//进行线性表的删除，语句略

break;

case5:

//进行线性表的查找，语句略

break;

case6:

//调用商品的销售函数，语句略

}/*switch*/

}/*while*/

}

实验二栈、队列的应用

1．实验名称

回文数的判断

2．实验学时

4学时

3．实验目的

（1）掌握栈的先进后出和队列先进先出的基本思想；

（2）掌握顺序栈和链栈、循环队列和链队的建立方法及其基本操作算法的实现

（3）灵活运用栈和队列解决实际问题。

4．实验要求

本实验要求使用高级编程语言C语言编写一个判断任意正整数是否回文数或将一个十进制数转换为二进制数的程序。

回文数的判断（用栈和队列）、数制转换（用栈）可选择一个实验，其中都是对整型数的操作。

存储方式可采用顺序或链式存储，但两种存储方式及其上的操作都应该掌握。

要求独立功能尽量用函数来实现，要有菜单选择。

每人一组完成，上机之前要有预习准备。

实验设备：

PC机一台，C语言IDE编程环境MicorosoftVisualC++6.0或者TurboC2.0。

5．实验内容

（1）首先建立栈或队列，并实现如初始化、入队（入栈）、出队（出栈）等功能函数。

（2）建立菜单能够实现用户的选择调用及有退出功能。

（3）运用取余及取整的方法，来得到各个数位相应的数字。

（4）将取得的数字依次入队列或栈中，利用栈的后进先出和队列的先进先出的特性来判断是否为回文数。

6.算法说明

此程序以链式存储为例。

（1）定义结点类型

typedefstructnode

{

intdata;

structnode*next;

}NodeType;

（2）定义栈类型

typedefstruct

{

NodeType*top;

}Linstack;

（3）定义队列类型，采用链队列

typedefstruct

{

NodeType*front;

NodeType*rear;

}LinQueue;

voidInitStack（Linstack*s）//链栈初始化,带头节点

{

s->top=（NodeType*）malloc（sizeof（NodeType））;

if（!

s->top）

printf（"\n存储分配失败!

"）;

else

s->top->next=NULL;

}

（4）判断一个栈是否为空，若空返回1，非空返回0

intStackEmpty（Linstack*s）

{

return（s->top->next==NULL）;

}

（5）入栈函数

voidPushStack（Linstack*s,Intx）{

NodeType*node;

node=（NodeType*）malloc（sizeof（NodeType））;

if（!

node）

printf（"存储分配失败!

\n"）;

else

{

node->data=x;

node->next=s->top->next;

s->top->next=node;

}

}

（6）出栈函数

IntPopStack（Linstack*s）

{

Intx;

NodeType*p;

if（StackEmpty（s））

{

printf（"empty"）;

exit

（1）;

}

p=s->top->next;

x=p->data;

s->top->next=p->next;

free（p）;

returnx;

}

（7）队列初始化,带头结点

voidInitQueue（LinQueue*q）

{

q->front=q->rear=（NodeType*）malloc（sizeof（NodeType））;

if（!

q->front）

printf（"\n存储分配失败!

"）;

else

q->front->next=NULL;

}

（8）判队空,空返回1，非空返回0

intQueueEmpty（LinQueue*q）

{

return（q->front==q->rear）;

}

（9）入队函数

voidEnQueue（LinQueue*q,Intx）

{

NodeType*p;

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

if（!

p）

{

printf（"\n存储分配失败!

"）;

return;

}

p->data=x;

p->next=NULL;

q->rear->next=p;

q->rear=p;

}

（10）出队函数

IntDelQueue（LinQueue*q）//出队

{

NodeType*p;

Intx;

if（QueueEmpty（q））

{

printf（"队空！

"）;

exit

（1）;

}

p=q->front->next;

x=p->data;

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

if（q->rear==p）

q->rear=q->front;

free（p）;

return（x）;

}

实验三树的存储和遍历

1．实验名称

二叉树的存储和遍历。

2．实验学时

4学时。

3.实验目的

（1）复习和巩固二叉树的相关概念和知识；

（2）掌握二叉树的存储结构；

（3）掌握二叉树的的建立及各种遍历算法，进一步理解递归的执行过程；

（4）掌握二叉排序树的建立及查找算法。

4．实验要求

本实验要求使用高级编程语言C语言编写一个有关二叉树的建立、遍历、查找操作的程序。

分别要实现普通二叉树的建立功能和二叉排序树的建立功能。

二叉树的存储方式采用链式存储结构。

要求独立功能尽量用函数来实现，要有菜单选择。

有兴趣的同学可选做统计二叉树的叶子结点数。

每人一组完成，上机之前要有预习准备。

实验设备：

PC机一台，C语言IDE编程环境MicorosoftVisualC++6.0或者TurboC2.0。

5．实验内容

（1）二叉树的建立：

将一棵普通二叉树通过补空格变成满二叉树，递归构造二叉树。

（2）二叉排序树的建立：

输入一个序列，按课本的程序生成二叉排序树。

（3）二叉树的遍历：

针对上面建立的二叉树或二叉排序树，进行三种遍历。

（4）二叉排序树的查找：

在一棵二叉排序树上查找一个指定的结点。

6．算法说明

（1）二叉树的数据结构定义

structBiTNode

{

chardata;

structBiTNode*lchild;

structBiTNode*rchild;

};

typedefstructBiTNodeBiTNode,*BiTree;

（2）二叉树的建立

参考程序：

voidCreateBiTree（BiTree*Tree）

{

charch;

if（（ch=getchar（））==''）

*Tree=NULL;

else

{

*Tree=（BiTree）malloc（sizeof（BiTNode））;

（*Tree）->data=ch;

CreateBiTree（&（（*Tree）->lchild））;

CreateBiTree（&（（*Tree）->rchild））;

}

}

（3）二叉排序树的建立

二叉排序树的建立过程是，逐个顺次插入结点，插入结点时要注意找到应该插入的位置。

参考程序：

BiTreeCreateBST（）

{

inti,ele;

BiTreeTree=NULL;

for（i=0;i

{

scanf（"%d",&ele）;

InsertBST（&Tree,ele）;

}

returnTree;

}

voidInsertBST（BiTree*Tree,intele）

{

BiTreepos,p=*Tree;

while（p）

{

if（p->data==ele）return;

pos=p;

if（eledata）p=p->lchild;

elsep=p->rchild;

}

p=（BiTree）malloc（sizeof（structBiTNode））;

p->data=ele;

p->lchild=p->rchild=NULL;

if（!

*Tree）*Tree=p;

elseif（eledata）pos->lchild=p;

elsepos->rchild=p;

}

（4）二叉树的遍历

注意：

二叉树的遍历是一个递归的过程，如先序遍历是，先遍历根，再先序遍历左子树，再先序遍历右子树，程序代码非常简洁，但实际执行过程较复杂，希望同学能理解。

voidPreOrder（BiTreeTree）

//二叉树的先序遍历算法

{

if（Tree）

{

putchar（Tree->data）;

PreOrder（Tree->lchild）;

PreOrder（Tree->rchild）;

}

}

voidInOrder（BiTreeTree）

//二叉树的中序遍历算法

{

if（Tree）

{

InOrder（Tree->lchild）;

putchar（Tree->data）;

InOrder（Tree->rchild）;

}

}

voidPostOrder（BiTreeTree）

//二叉树的后序遍历算法

{

if（Tree）

{

PostOrder（Tree->lchild）;

PostOrder（Tree->rchild）;

putchar（Tree->data）;

}

}

（5）二叉排序树的查找

参考程序：

BiTreeSearchBST（BiTreeTree,intele）

{

while（Tree!

=NULL）

{

if（ele==Tree->data）returnTree;

else

{

if（eledata）Tree=Tree->lchild;

elseTree=Tree->rchild;

}

}

returnNULL;

}

实验四查找算法的应用

1．实验名称

哈希表的创建及查找。

2．实验学时

4学时。

3.实验目的

（1）进一步了解查找算法的用途；

（2）复习巩固哈希函数及哈希表等有关概念；

（3）掌握哈希表的创建及查找的过程和方法；

（4）比较哈希查找与其它查找算法的不同，体会哈希查找的优缺点。

4．实验要求

本实验完成一个查找算法的应用程序，使用高级编程语言C语言编写，算法要求采用哈希查找算法。

最好使用复杂的结构体类型作为元素的类型，查找关键字应为整型。

可先创建一个哈希表，输出哈希表的内容，验证其是否正确；哈希表正确后，再给定关键字进行查找，验证查找结果是否正确。

原始的数据元素可以先放在一个线性表中，再将其放入哈希表中。

但建议同学每输入一个元素，将其直接放入哈希表中。

每人一组完成，上机之前要有预习准备。

实验设备：

PC机一台，C语言IDE编程环境MicorosoftVisualC++6.0或者TurboC2.0。

5.实验内容

预先给定N个元素，用除留余数法设计哈希函数，结合线性探测再散列的方法建立哈希表，在哈希表中进行查找，并在屏幕上显示哈希表及查找结果。

6.算法说明

（1）哈希函数的构造

在哈希查找中，哈希函数的构造十分关键。

对于不同的问题，应根据数据的实际情况选择合适的哈希函数，使数据的哈希地址分布均匀，避免或减少冲突的出现。

除留余数法是一种最简单、最常用的哈希函数构造方法。

取关键字被某个不大于哈希表表长m的数p除后所得的余数作为哈希地址，其形式为：

H（k）=k%p

此方法中p的选择十分重要，选择不当时会造成大量冲突。

一般情况下，可以选p为不大于m的最大质数。

哈希表表长m必须大于等于数据元素的个数，虽然m较大时，冲突的概率较小，但空间浪费严重。

根据数学分析可知：

一般给定N个元素，则m取大于N的最小质数。

例如：

给定10个元素，则m=p