数据结构实验指导书.docx

数据结构实验指导书.docx

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

数据结构实验指导书

《数据结构》实验指导书

计算机专业实验中心编

2020年7月11日

《数据结构》上机实验容和要求

通过上机实验加深对课程容的理解，增加感性认识，提高程序设计、开发及调试能力。

序号

实验

名称

容

提要

每组

人数

实验

时数

实验

要求

实验

类别

分值（总100分）

1

顺序表的实现及应用

掌握顺序表结构，实现其插入、删除等算法。

利用顺序表将两个有序线性表合并为一个有序表。

1

2

必做

设计

10分

2

链表的实现及应用

掌握单链表结构，实现其插入、删除、查找等算法。

利用单链表将两个有序链表合并为一个有序链表。

1

2

必做

设计

10分

3

栈的实现及应用

掌握栈的结构，将栈应用于表达式计算问题

1

2

必做

设计

15分

4

队列的实现及应用

掌握队列的结构，将队列应用于模拟服务台前的排队现象问题

1

2

必做

设计

15分

5

二叉树操作及应用

掌握二叉树的存储，实现三种遍历的递归算法、实现前序或中序的非递归遍历算法

1

2

必做

设计

15分

6

图的遍历操作及应用

实现图的存储、深度遍历和广度遍历算法

1

2

必做

设计

10分

7

查找算法的实现

实现顺序表的二分查找算法

1

2

必做

设计

10分

8

排序算法的实现

实现直接插入排序、快速排序等算法

1

2

必做

设计

15分

本实验指导书适用于16学时《数据结构》实验课，实验项目具体容如下：

实验报告要求

请按照实验教师要求，按时提交实验报告电子版文件。

实验报告格式可个性化定义，容包括但不限于以下容：

1、题目、、学号、班级（首页）

2、需求分析：

述程序设计的任务，强调程序要做什么，明确规定：

（1）输入的形式和输出值的围；

（2）输出的形式；

（3）程序所能达到的功能；

（4）测试数据：

包括正确的输入输出结果和错误的输入及输出结果。

3、概要设计：

说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。

4、详细设计：

提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。

5、调试分析：

（1）调试过程中所遇到的问题及解决方法；

（2）算法的时空分析；

（3）经验与体会。

6、用户使用说明：

说明如何使用你设计的程序，详细列出每一步操作步骤。

（如果程序操作简单，可略去）

7、测试结果：

列出对于给定的输入所产生的输出结果。

（若有可能，测试随输入规模的增长所用算法的实际运行时间的变化）

8、总结

实验一、顺序表的实现及应用

一、实验目的

了解和掌握线性表的顺序存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：

插入、删除、查找以及线性表合并等运算在顺序存储结构和存储结构上的运算，以及对相应算法的性能分析。

二、实验要求

给定一段程序代码，程序代码所完成的功能为：

（1）建立一个线性表；

（2）依次输入数据元素1,2,3,4,5,6,7,8,9,10；（3）删除数据元素5；（4）依次显示当前线性表中的数据元素。

假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用顺序表。

程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，修改后上机调试得到正确的运行结果。

三、程序代码

#include

#defineMaxSize100

typedefintDataType;

typedefstruct

{

DataTypelist[MaxSize];

intsize;

}SeqList;

voidListInitiate（SeqList*L）/*初始化顺序表L*/

{

L->size=0;/*定义初始数据元素个数*/

}

intListLength（SeqListL）/*返回顺序表L的当前数据元素个数*/

{

returnL.size;

}

intListInsert（SeqList*L,inti,DataTypex）

/*在顺序表L的位置i（0≤i≤size）前插入数据元素值x*/

/*插入成功返回1，插入失败返回0*/

{

intj;

if（L->size>=MaxSize）

{

printf（"顺序表已满无法插入!

\n"）;

return0;

}

elseif（i<0||i>L->size）

{

printf（"参数i不合法!

\n"）;

return0;

}

else

{//此段程序有一处错误

for（j=L->size;j>i;j--）L->list[j]=L->list[j];/*为插入做准备*/

L->list[i]=x;/*插入*/

L->size++;/*元素个数加1*/

return1;

}

}

intListDelete（SeqList*L,inti,DataType*x）

/*删除顺序表L中位置i（0≤i≤size-1）的数据元素值并存放到参数x中*/

/*删除成功返回1，删除失败返回0*/

{

intj;

if（L->size<=0）

{

printf（"顺序表已空无数据元素可删!

\n"）;

return0;

}

elseif（i<0||i>L->size-1）

{

printf（"参数i不合法"）;

return0;

}

else

{//此段程序有一处错误

*x=L->list[i];/*保存删除的元素到参数x中*/

for（j=i+1;j<=L->size-1;j++）L->list[j]=L->list[j-1];/*依次前移*/

L->size--;/*数据元素个数减1*/

return1;

}

}

intListGet（SeqListL,inti,DataType*x）

/*取顺序表L中第i个数据元素的值存于x中，成功则返回1，失败返回0*/

{

if（i<0||i>L.size-1）

{

printf（"参数i不合法!

\n"）;

return0;

}

else

{

*x=L.list[i];

return1;

}

}

voidmain（void）

{SeqListmyList;

inti,x;

ListInitiate（&myList）;

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

ListInsert（&myList,i,i+1）;

ListDelete（&myList,4,&x）;

for（i=0;i

{

ListGet（,i,&x）;//此段程序有一处错误

printf（"%",x）;

}

}

四、实验任务

1.改正上述程序中的错误（必作）。

2.编写合并函数，将两个有序线性表合并为一个有序表并在主函数中加以测试（选作）。

3.完成实验报告的撰写。

实验二、链表的实现及应用

一、实验目的

了解和掌握线性表的链式存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：

插入、删除、查找以及线性表合并等运算在顺序存储结构和存储结构上的运算，以及对相应算法的性能分析。

二、实验要求

给定一段程序代码，程序代码所完成的功能为：

（1）建立一个线性表；

（2）依次输入数据元素1,2,3,4,5,6,7,8,9,10；（3）删除数据元素5；（4）依次显示当前线性表中的数据元素。

假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用单链表。

程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，上机调试并得到正确的运行结果。

三、程序代码：

#include/*该文件包含pringtf（）等函数*/

#include/*该文件包含exit（）等函数*/

#include/*该文件包含malloc（）等函数*/

typedefintDataType;/*定义DataType为int*/

typedefstructNode

{

DataTypedata;

structNode*next;

}SLNode;

voidListInitiate（SLNode**head）/*初始化*/

{

/*如果有存空间，申请头结点空间并使头指针head指向头结点*/

if（（*head=（SLNode*）malloc（sizeof（SLNode）））==NULL）exit

（1）;

（*head）->next=NULL;/*置链尾标记NULL*/

}

intListLength（SLNode*head）/*单链表的长度*/

{

SLNode*p=head;/*p指向首元结点*/

intsize=0;/*size初始为0*/

while（p->next!

=NULL）/*循环计数*/

{

p=p->next;

size++;

}

returnsize;

}

intListInsert（SLNode*head,inti,DataTypex）

/*在带头结点的单链表head的数据元素ai（0≤i≤size）结点前*/

/*插入一个存放数据元素x的结点*/

{

SLNode*p,*q;

intj;

p=head;/*p指向首元结点*/

j=-1;/*j初始为-1*/

while（p->next!

=NULL&&j

/*最终让指针p指向数据元素ai-1结点*/

{

p=p->next;

j++;

}

if（j!

=i-1）

{

printf（"插入位置参数错！

"）;

return0;

}

/*生成新结点由指针q指示*/

if（（q=（SLNode*）malloc（sizeof（SLNode）））==NULL）exit

（1）;

q->data=x;

//此段程序有一处错误

p->next=q->next;/*给指针q->next赋值*/

p->next=q;/*给指针p->next重新赋值*/

return1;

}

intListDelete（SLNode*head,inti,DataType*x）

/*删除带头结点的单链表head的数据元素ai（0≤i≤size-1）结点*/

/*删除结点的数据元素域值由x带回。

删除成功时返回1；失败返回0*/

{

SLNode*p,*s;

intj;

p=head;/*p指向首元结点*/

j=-1;/*j初始为-1*/

while（p->next!

=NULL&&p->next->next!

=NULL&&j

/*最终让指针p指向数据元素ai-1结点*/

{

p=p->next;

j++;

}

if（j!

=i-1）

{

printf（"插入位置参数错！

"）;

return0;

}

//此段程序有一处错误

s=p->next;/*指针s指向数据元素ai结点*/

*x=s->data;/*把指针s所指结点的数据元素域值赋予x*/

p->next=s->next;/*把数据元素ai结点从单链表中删除指*/

free（s）;/*释放指针s所指结点的存空间*/

return1;

}

intListGet（SLNode*head,inti,DataType*x）

/*取数据元素ai和删除函数类同，只是不删除数据元素ai结点*/

{

SLNode*p;

intj;

p=head;

j=-1;

while（p->next!

=NULL&&j

{

p=p->next;j++;

}

if（j!

=i）

{

printf（"取元素位置参数错！

"）;

return0;

}

//此段程序有一处错误

*x=p->next;

return1;

}

voidDestroy（SLNode**head）

{

SLNode*p,*p1;

p=*head;

while（p!

=NULL）

{

p1=p;

p=p->next;

free（p1）;

}

*head=NULL;

}

voidmain（void）

{

SLNode*head;

inti,x;

ListInitiate（&head）;/*初始化*/

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

{

if（ListInsert（head,i,i+1）==0）/*插入10个数据元素*/

{

printf（"错误!

\n"）;

return;

}

}

if（ListDelete（head,4,&x）==0）/*删除数据元素5*/

{

printf（"错误!

\n"）;

return;

}

for（i=0;i

{

if（ListGet（head,i,&x）==0）/*取元素*/

{

printf（"错误!

\n"）;

return;

}

elseprintf（"%d",x）;/*显示数据元素*/

}

Destroy（&head）;

}

三、实验任务

1.改正上述程序中的错误（必作）。

2.编写合并函数，将两个有序的单链表合并成一个有序单链表（选作）。

3.完成实验报告的撰写。

实验三、栈的实现及应用

一、实验目的

1.掌握栈的存储表示和实现

2.掌握栈的基本操作实现。

3.掌握栈在解决实际问题中的应用。

二、实验要求

问题描述：

编写程序实现算术表达式的求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。

主要功能描述如下：

1、从键盘上输入表达式。

2、分析该表达式是否合法。

3、若上述处理过程中没有发现错误，则认为该表达式合法，计算并打印处理结果。

三、主要功能函数参考

程序中主要包含下面几个功能函数：

voidinitstack（）：

初始化堆栈

intMake_str（）：

语法检查

intpush_operate（intoperate）：

将操作码压入堆栈

intpush_num（doublenum）：

将操作数压入堆栈

intprocede（intoperate）：

处理操作码

intchange_opnd（intoperate）：

将字符型操作码转换成优先级

intpush_opnd（intoperate）：

将操作码压入堆栈

intpop_opnd（）：

将操作码弹出堆栈

intcaculate（intcur_opnd）：

简单计算+，-，*，/

doublepop_num（）：

弹出操作数

四、实验任务

认真阅读与理解实验容的具体要求，参考教材相关章节，结合实验容的要求，编写实验程序并上机调试与测试，完成实验报告的撰写。

实验四、队列的实现及应用

一、实验目的

1.掌握队列的存储表示和实现。

2.掌握队列的基本操作实现。

3.掌握队列在解决实际问题中的应用。

二、实验要求

利用队列模拟服务台前的排队现象问题。

问题描述：

某银行有一个客户办理业务站，在单位时间随机地有客户到达，设每位客户的业务办理时间是某个围的随机值。

设只有一个窗口，一位业务人员，要求程序模拟统计在设定时间，业务人员的总空闲时间和客户的平均等待时间。

假定模拟数据已按客户到达的先后顺序依次存于某个文本数据文件中，对应每位客户有两个数据：

到达时间和需要办理业务的时间。

三、实验任务

认真阅读与理解实验容的具体要求，参考教材相关章节，结合实验容的要求，编写实验程序并上机调试与测试，完成实验报告的撰写。

实验五、二叉树操作及应用

一、实验目的

掌握二叉树的定义、结构特征，以及各种存储结构的特点及使用围，各种遍历算法。

掌握用指针类型描述、访问和处理二叉树的运算。

掌握前序或中序的非递归遍历算法。

二、实验要求

有如下二叉树：

程序代码给出了该二叉树的链式存储结构的建立、前序、中序、后序遍历的算法，同时也给出了查询“E”是否在二叉树里的代码。

代码有三处错误，有标识，属于逻辑错误，对照书中的代码仔细分析后，请修改了在电脑里运行。

#include

#include

typedefcharDataType;

typedefstructNode

{

DataTypedata;/*数据域*/

structNode*leftChild;/*左子树指针*/

structNode*rightChild;/*右子树指针*/

}BiTreeNode;/*结点的结构体定义*/

/*初始化创建二叉树的头结点*/

voidInitiate（BiTreeNode**root）

{

*root=（BiTreeNode*）malloc（sizeof（BiTreeNode））;

（*root）->leftChild=NULL;

（*root）->rightChild=NULL;

}

voidDestroy（BiTreeNode**root）

{

if（（*root）!

=NULL&&（*root）->leftChild!

=NULL）

Destroy（&（*root）->leftChild）;

if（（*root）!

=NULL&&（*root）->rightChild!

=NULL）

Destroy（&（*root）->rightChild）;

free（*root）;

}

/*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/

/*原curr所指结点的左子树成为新插入结点的左子树*/

/*若插入成功返回新插入结点的指针，否则返回空指针*/

BiTreeNode*InsertLeftNode（BiTreeNode*curr,DataTypex）

{

BiTreeNode*s,*t;

if（curr==NULL）returnNULL;

t=curr->leftChild;/*保存原curr所指结点的左子树指针*/

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

s->data=x;

s->leftChild=t;/*新插入结点的左子树为原curr的左子树*/

s->rightChild=NULL;

curr->leftChild=s;/*新结点成为curr的左子树*/

returncurr->leftChild;/*返回新插入结点的指针*/

}

/*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/

/*原curr所指结点的右子树成为新插入结点的右子树*/

/*若插入成功返回新插入结点的指针，否则返回空指针*/

BiTreeNode*InsertRightNode（BiTreeNode*curr,DataTypex）

{

BiTreeNode*s,*t;

if（curr==NULL）returnNULL;

t=curr->rightChild;/*保存原curr所指结点的右子树指针*/

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

s->data=x;

s->rightChild=t;/*新插入结点的右子树为原curr的右子树*/

s->leftChild=NULL;

curr->rightChild=s;/*新结点成为curr的右子树*/

returncurr->rightChild;/*返回新插入结点的指针*/

}

voidPreOrder（BiTreeNode*t,voidvisit（DataTypeitem））

//使用visit（item）函数前序遍历二叉树t

{

if（t!

=NULL）

{//此小段有一处错误

visit（t->data）;

PreOrder（t->rightChild,visit）;

PreOrder（t->leftChild,visit）;

}

}

voidInOrder（BiTreeNode*t,voidvisit（DataTypeitem））

//使用visit（item）函数中序遍历二叉树t

{

if（t!

=NULL）

{//此小段有一处错误

InOrder（t->leftChild,visit）;

InOrder（t->rightChild,visit）;

visit（t->data）;

}

}

voidPostOrder（BiTreeNode*t,voidvisit（DataTypeitem））

//使用visit（item）函数后序遍历二叉树t

{

if（t!

=NULL）

{//此小段有一处错误

visit（t->data）;

PostOrder（t->leftChild,visit）;

PostOrder（t->rightChild,visit）;

}

}

voidVisit（DataTypeitem）

{

printf（"%c",item）;

}

BiTreeNode*Search（BiTreeNode*root,DataTypex）//需找元素x是否在二叉树中

{

BiTreeNode*find=NULL;

if（root!

=NULL）

{

if（root->data==x）

find=root;

else

{

find=Search（root->leftChild,x）;

if（find==NULL）

find=Search（root->rightChild,x）;

}

}

returnfind;

}

voidmain（void）

{

BiTreeNode*root,*p,*pp,*find;

charx='E';

Initiate（&root）;

p=InsertLeftNode（root,'A'）;

p=InsertLeftNode（p,'B'）;

p=InsertLeftNode（p,'D'）;

p=InsertRightNode（p,'G'）;

p=InsertRightNode（root->leftChild,'C'）;

pp=p;

InsertLeftNode（p,'E'）;

InsertRi