数据结构实验指导书

《数据结构》实验指导书

杨先凤 朱小梅 编

西南石油大学计算机科学学院

二零零七年九月

目 录

写在上机实习之前 ........................................ I 实验一 顺序表的建立和基本运算 ........................... 1 实验二 实验三 实验四 实验五 实验六 实验七 实验八 实验九

链表的建立和基本运算 ............................. 8 栈结构及其应用 .................................. 14 队列应用 ....................................... 17 串的操作及应用 .................................. 18 二叉树的建立和遍历 .............................. 19 图的应用及其算法 ................................ 23 查找 ........................................... 27 内排序 ......................................... 28

写在上机实习之前

上机实践是学生对本门课程所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节，也是对课堂教学与实践教学效果的一种检验。通常，实习题中的问题比平时的习题复杂得多，也更接近实际。实习着眼于原理与应用的结合，使学生学会如何把书上学到的知识运用于解决实际问题的过程中去，培养从事软件开发设计工作所必需的基本技能；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，多人合作，以至一整套软件工程规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师都严厉的主考者。

为了达到上述目的，本书安排了9个实习项目，各项目的训练重点在于基本的数据结构，而不强调面面俱到。各实习项目与教材的各章具有紧密的对应关系，在个别实习项目中安排有难度差别不等的多个实习题，以便学生选做。

在一些实习项目中提供了完整的算法实现代码，仅供同学们参考，绝大多数的同学在上机实习时千万不要机械的照抄本书提供的代码，而是应该自己独立的思考和设计你的算法和程序，并争取在规定的时间内如期完成上机实验任务。对于个别成绩较差的同学，实在是没法完成任务的建议你不妨抄一遍本指导书的代码，以增强你的感性认识，强化你的实践基础，提高你的实践能力。本指导书的代码全部用C或C++语言编写，并全部上机调试通过，但由于时间比较仓促，本书中提供的算法和程序并不是最好的算法和程序，相信不少的同学一定有能力设计出更好的算法和程序。

本书可作为学校各专业开设数据结构课程的实验指导书，教师可根据学时、专业和学生的实际情况，选作其中一部分实验项目。

I

实验一 顺序表的建立和基本运算

一、实验目的

1、 掌握顺序表存储结构的定义及C/C++语言实现 2、 掌握顺序表的各种基本操作及C/C++语言实现

3、 设计并实现有序表的遍历、插入、删除等常规算法

二、实验环境

PC微机，Windows，DOS，Turbo C或Visual C++

三、实验内容

1、顺序表的建立和基本运算

（1）问题描述

顺序表经常进行的运算包括：创建顺序表、销毁顺序表、求顺序表的长度、在顺序表中查找某个数据元素、在某个位置插入一个新数据元素、在顺序表中删除某个数据元素等操作。试编程实现顺序表的这些基本运算。

（2）基本要求

实现顺序表的每个运算要求用一个函数实现。

（3）算法描述

参见教材算法2.3、算法2.4、算法2.5等顺序表的常规算法。

（4）算法实现——示例程序

#include // malloc()等

#include // NULL, printf()等 #include // exit() // 函数结果状态代码 #define OVERFLOW -2 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define INFEASIBLE -1

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE //-------- 线性表的动态分配顺序存储结构 -----------

#define LIST_INIT_SIZE 10 // 线性表存储空间的初始分配量 #define LIST_INCREMENT 2 // 线性表存储空间的分配增量 typedef int ElemType; struct SqList {

ElemType *elem; // 存储空间基址

1

int length; // 当前长度

int listsize; // 当前分配的存储容量(以sizeof(int)为单位) };

void InitList(SqList &L) // 算法2.3

{ // 操作结果：构造一个空的顺序线性表L L.elem=new ElemType[LIST_INIT_SIZE]; if(!L.elem) exit(OVERFLOW); // 存储分配失败 L.length=0; // 空表长度为0

L.listsize=LIST_INIT_SIZE; // 初始存储容量 }

void DestroyList(SqList &L)

{ // 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L delete []L.elem; L.elem=NULL; L.length=0; L.listsize=0; }

void ClearList(SqList &L)

{ // 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 L.length=0; }

Status ListEmpty(SqList L)

{ // 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE

if(L.length==0) return TRUE; else return FALSE; }

int ListLength(SqList L)

{ // 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 return L.length; }

Status GetElem(SqList L,int i,ElemType &e)

{ // 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值 if(i<1||i>L.length)

2

return ERROR; e=*(L.elem+i-1); return OK; }

//int LocateElem(SqList L,int e,Status(*compare)(int,int))

int LocateElem(SqList L,ElemType e, Status(*compare)(ElemType,ElemType))

{//初始条件：顺序线性表L已存在，compare( )是数据元素判定函数(满足为1，否则为0) // 操作结果：返回L中第1个与e满足关系compare( )的数据元素的位序。 // 若这样的数据元素不存在，则返回值为0。算法2.6 ElemType *p;

int i=1; // i的初值为第1个元素的位序

p=L.elem; // p的初值为第1个元素的存储位置 while(i<=L.length&&!compare(*p++,e)) ++i;

if(i<=L.length) return i; else return 0; }

Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e) { // 初始条件：顺序线性表L已存在

// 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， // 否则操作失败，pre_e无定义 int i=2;

ElemType *p=L.elem+1;

while(i<=L.length&&*p!=cur_e){ p++; i++; }

if(i>L.length) return INFEASIBLE; // 操作失败 else{ pre_e=*--p; return OK; } }

Status NextElem(SqList L,ElemType cur_e,ElemType &next_e) { // 初始条件：顺序线性表L已存在 // 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， // 否则操作失败，next_e无定义 int i=1;

3

ElemType *p=L.elem; while(i

Status ListInsert(SqList &L,int i,ElemType e) // 算法2.4

{ // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1

// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 ElemType *newbase,*q,*p; if(i<1||i>L.length+1) // i值不合法 return ERROR; if(L.length>=L.listsize){ // 当前存储空间已满,增加分配 if(!(newbase=(int *)realloc(L.elem,(L.listsize+LIST_INCREMENT)*sizeof(int)))) exit(OVERFLOW); // 存储分配失败 L.elem=newbase; // 新基址 L.listsize+=LIST_INCREMENT; // 增加存储容量 } q=L.elem+i-1; // q为插入位置 for(p=L.elem+L.length-1;p>=q;--p) // 插入位置及之后的元素右移 *(p+1)=*p; *q=e; // 插入e ++L.length; // 表长增1 return OK; }

Status ListDelete(SqList &L,int i,ElemType &e) // 算法2.5 { // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)

// 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 ElemType *p,*q; if(i<1||i>L.length) // i值不合法 return ERROR; p=L.elem+i-1; // p为被删除元素的位置 e=*p; // 被删除元素的值赋给e q=L.elem+L.length-1; // 表尾元素的位置 for(++p;p<=q;++p) // 被删除元素之后的元素左移 *(p-1)=*p;

4

L.length--; // 表长减1 return OK; }

void ListTraverse(SqList L,void(*vi)(ElemType&)) { // 初始条件：顺序线性表L已存在

// 操作结果：依次对L的每个数据元素调用函数vi() // vi()的形参加'&'，表明可通过调用vi()改变元素的值 ElemType *p; int i; p=L.elem; for(i=1;i<=L.length;i++) vi(*p++); printf(\}

Status sq(ElemType c1,ElemType c2)

{ // 数据元素判定函数(平方关系)，LocateElem()调用的函数 if(c1==c2*c2) return TRUE; else return FALSE; }

void dbl(ElemType &c)

{ // ListTraverse()调用的另一函数(元素值加倍) c*=2; }

Status equal(ElemType c1,ElemType c2) { // 判断是否相等的函数 if(c1==c2) return TRUE; else return FALSE; }

void print1(ElemType &c) { printf(\}

void main() { SqList L; int e,e0;

5

Status i; int j,k; InitList(L); printf(\初始化L后：L.elem=%u L.length=%d L.listsize=%d\\n\ for(j=1;j<=5;j++) i=ListInsert(L,1,j); printf(\在L的表头依次插入1～5后：*L.elem=\ for(j=1;j<=5;j++) printf(\ printf(\ printf(\ i=ListEmpty(L); printf(\是否空：i=%d(1:是 0:否)\\n\ ClearList(L); printf(\清空L后：L.elem=%u L.length=%d L.listsize=%d \ i=ListEmpty(L); printf(\是否空：i=%d(1:是 0:否)\\n\ for(j=1;j<=10;j++) ListInsert(L,j,j); printf(\在L的表尾依次插入1～10后：*L.elem=\ for(j=1;j<=10;j++) printf(\ printf(\ printf(\ ListInsert(L,1,0); printf(\在L的表头插入0后：*L.elem=\ for(j=1;j<=ListLength(L);j++) // ListLength(L)为元素个数 printf(\ printf(\ printf(\有可能改变) L.length=%d(改变) L.listsize=%d(改变)\\n\ GetElem(L,5,e); printf(\第5个元素的值为：%d\\n\ for(j=10;j<=11;j++){ k=LocateElem(L,j,equal); if(k) // k不为0，表明有符合条件的元素，且其位序为k printf(\第%d个元素的值为%d\\n\ else printf(\没有值为%d的元素\\n\ } for(j=3;j<=4;j++){ k=LocateElem(L,j,sq); if(k) // k不为0，表明有符合条件的元素，且其位序为k printf(\第%d个元素的值为%d的平方\\n\

6

}

else printf(\没有值为%d的平方的元素\\n\}

for(j=1;j<=2;j++){// 测试头两个数据 GetElem(L,j,e0); // 把第j个数据赋给e0 i=PriorElem(L,e0,e); // 求e0的前驱 if(i==INFEASIBLE) printf(\元素%d无前驱\\n\ else printf(\元素%d的前驱为：%d\\n\}

for(j=ListLength(L)-1;j<=ListLength(L);j++){ // 最后两个数据 GetElem(L,j,e0); // 把第j个数据赋给e0 i=NextElem(L,e0,e); // 求e0的后继 if(i==INFEASIBLE) printf(\元素%d无后继\\n\ else printf(\元素%d的后继为：%d\\n\}

k=ListLength(L); // k为表长 for(j=k+1;j>=k;j--) { i=ListDelete(L,j,e); // 删除第j个数据 if(i==ERROR) printf(\删除第%d个元素失败\\n\ else printf(\删除第%d个元素成功，其值为：%d\\n\}

printf(\依次输出L的元素：\

ListTraverse(L,print1); // 依次对元素调用print1()，输出元素的值 printf(\的元素值加倍后：\

ListTraverse(L,dbl); // 依次对元素调用dbl()，元素值乘2 ListTraverse(L,print1); DestroyList(L);

printf(\销毁L后：L.elem=%u L.length=%d L.listsize=%d\\n\

2、顺序表的就地逆转

（1）问题描述

顺序表的就地逆转是指在顺序表现有空间的基础上，将顺序表中的数据元素交换位置排列，排列完之后，新的顺序序列与原来的顺序序列刚好相反。如原来顺序序列“abcdef”，就地逆转之后的新顺序序列为“fedcba”。 （2）基本要求

充分理解题目的要求，在对顺序表实现逆转时，必须是在顺序表原有空间的基础上进行，不能带借助临时变量所申请的临时空间，也不能借助其他形式的临时空间。

7

四、实验要求

1、认真阅读和掌握、上机调试并运行实验内容1的程序；保存和打印出程序的运行结果，并结合程序进行分析。

2、用C/C++完成实验内容2的算法设计和程序设计并上机调试通过。要求： （1）给出程序设计的基本思想、原理和算法描述。 （2）对源程序给出注释。

（3）保存和打印出程序的运行结果，并结合程序进行分析。 3、撰写实验报告，提供实验结果和数据。

实验二 链表的建立和基本运算

一、实验目的

1、 掌握链表存储结构的定义及C/C++语言实现

2、 掌握双链表的特点和基本运算及C/C++语言实现

3、 建立并正反序显示双链表结点数据，并执行结点插入操作

二、实验环境

PC微机，Windows，DOS，Turbo C或Visual C++

三、实验内容

1、实现链表的运算

（1）问题描述

链表经常进行的运算操作有创建链表、求链表的长度、在链表中查找某个数据元素、在某个位置插入一个新数据元素、在链表中删除某个数据元素等操作。试编程实现链表的这些基本运算。

（2）基本要求

实现链表的每个运算要求用一个函数实现。

（3）算法描述

在设计链表的各种运算之前，最重要的准备工作是定义链式存储（即链表）的结点类型，最简单的链表的结点类型可由数据域data和指针域next两部分组成。然后再分别设计各种运算的具体函数。最后在主函数中实现链表的各种运算时，分别调用相应的函数即可。

首先，在主函数中创建一个包含若干个结点的链表，在此基础上，就可以调用插入函数在链表的某个位置插入结点，调用求长度函数求出链表的长度，当然其他运算依次类推。为方便地实现上述的个种基本运算，可以再设计一个操作方便的主菜单。 在整个算法中有一个贯穿各个运算函数之间的线索，那就是链表。因此各个函数中的运算对象都是针对同一个链表的。为了参数的传递方便，可以把指向链表的表头指针设定为全局变量。

（4）算法实现——示例程序

#define null 0;

typedef int ElemType; typedef struct node

8

{

ElemType data; /*数据域*/ struct node *next; /*指针域*/

}Lnode; /*定义基本线性表的结点结构* /

Lnode *head; /*定义基本线性表的表头指针为全局变量* / int length(Lnode *p) /*求指针p指向的基本线性表的长度* / {

int n=0; /*结点位置计数器* / Lnode *q=p; /* 定义临时指针q */

while(q!=null) /* 当基本线性表不空时，统计基本线性表中的结点数 {

n++; a=q->next; }

return (n); /*返回统计的结点数*/ }

ElemType get(Lnode *p,int i)

/*求指针p指向的基本线性表中第i个结点的值* / {

int j=1; /*查找结点位置的计数器*/ Lnode *q=p; /* 定义临时指针q */ while(j

q=q->next; j++; }

if(q!=null) /*如果存在，返回其数据域的值 */ return (q->data);

else /*否则，输出其位置参数不正确*/ printf(\位置参数不正确！\\n\}

int Locate(Lnode *p,ElemType x)

/*求指针p指向的基本线性表中的数据元素X的位置序号 */ {

int n=0; /* 结点位置计数器 */ Lnode *q=p; /* 定义临时指针q */ while (q!=null && q->data!=x)

/* 在基本线性表中查找数据元素x的位置 * / {q=q->next; n++; }

if(q==null) /*如果不存在，则返回-1 */ return (-1);

else /* 否则，返回结点的位置序号 */

9

*/

return (n+1); }

void insert(ElemType x,int i)

/* 在基本线性表的的位置i，插入数据元素 * / {

int j=1; /* 结点位置计数器 */ Lnode *s,*q; /* 定义临时指针s，q */ s=(Lnode *)malloc(sizeof(Lnode)); /*生成新结点*/ s->data=x; /*将新结点的数据域置为x*/ q=head;

if(i==1) /*如果插入位置是1，则将新结点插入到表头 */ {

s->next=q; head=s; }

else /*否则，查找插入位置*/ {

while((jnext!=null)) {

q=q->next; j++; }

if(j==i-1) {

s->next=q->next;

q->next=s; }

else /*插入位置不存在*/

printf(\位置参数不正确！\\n\} }

void delete(Lnode *p,int i)

/* 将指针p指向的基本线性表中的位置i的数据元素删除 * / {

int j=1; /* 结点位置计数器 */ Lnode *q=p,*t;

if(i==1)

/*如果位置序号为1，则将基本线性表的第1个数据元素结点删除 */ {

t=q;

p=q->next; }

else /*否则，从表头查找相应的位置序号i*/ {

10

while((jnext!=null)) {

q=q->next; j++; }

if(q->next!=null && j==i-1)

/*如果找到位置i，则将该位置的结点删除*/ {

t=q->next;

q->next=t->next; }

else /*否则位置i不存在*/

printf(\位置参数不正确！\\n\}

if(t!=null) free(t); }

void display(Lnode *p) {

Lnode *q; q=p;

printf(\单链表显示：\ if(q==null)

printf(\链表为空\ else if(q->next==null) printf(\ else {

while(q->next!=null) {

printf(\ q=q->next; }

printf(\}

printf(\}

main( ) {

Lnode *q;

int d,i,n,select,k,flag=1; head=null;

printf (\请输入数据长度：\ scanf(\

11

for(i=1;i<=n;i++)

{

printf (\将数据到插入到链表中：\ scanf(\ insert(d,i);

}

display(head); printf(\while(flag) {

printf(\求长度\\n\ printf(\取结点\\n\ printf(\求值查找\\n\ printf(\增加结点\\n\ printf(\删除结点\\n\ printf(\退出\\n\ printf(\ scanf(\ switch(select) {

case 1:{

d=length(head);

printf(\单链表的长度为：%d\ printf(\ display(head); printf(\ }

break; case 2: {

printf(\请输入取得结点的位置：\ scanf(\ k=get(head,d); printf(\ display(head); printf(\ }

break; case 3:{

printf(\请输入要查找的数据：\ scanf(\ k=locate(head,d); printf(\ display(head); printf(\

12

}

break;

case 4:{

printf(\请输入增加结点的位置：\ scanf(\

printf(\请输入增加结点的数据：\ scanf(\ insert(d,k); display(head); printf(\ }

break;

case 5:{

printf(\请输入删除结点的位置：\ scanf(\ delete(head,d); printf(\ display(head); printf(\ }

break;

case 6: flag=0;

break;

} } }

2、求集合的并、交和差集

（1）问题描述

求出任意两个正整数集合的的交、并和差集。

（2）基本要求

程序运行后显现提示信息，由用户输入两组整数分别作为两个集合的元素。程序将自动滤去由程序计算它们的交、并和差集，并将运算结果输出。 3、火车票销售

（1）问题描述

试编制一个简单的火车票销售系统，可完成售票、退票、车票剩余情况查询等功能。每张车票包含车次、座位信息。

（2）基本要求

在售票、退票、查询剩余票等环节中，都必须显示出车票的信息，即车次、座位情况。为简单起见，在此假设所有出售的车票均为同一车次的车票。退票时，必须是车站售出的列车票才能退，否则视为无效票，不能办理退票业务。

13

四、实验要求

1、认真阅读和掌握、上机调试并运行实验内容1的程序；保存和打印出程序的运行结果，并结合程序进行分析。

2、用C/C++完成实验内容2、3的算法设计和程序设计并上机调试通过。要求： （1）给出程序设计的基本思想、原理和算法描述。 （2）对源程序给出注释。

（3）保存和打印出程序的运行结果，并结合程序进行分析。 3、撰写实验报告，提供实验结果和数据。

实验三 栈结构及其应用

一、实验目的

1、 掌握栈的存储结构表示方法 2、 掌握栈基本运算实现

3、 设计并实现算术表达式括号匹配算法

二、实验环境

PC微机，Windows，DOS，Turbo C或Visual C++

三、实验内容

1、简单编译器的实现（括号配对）

（1）问题描述

通常在程序调试时都有对源代码编译的过程，而判断左括号是否匹配也是编译过程中的一个重要环节，试设计一个程序对任意输入的语句或数学表达式，判断其左右括号是否匹配。 （2）基本要求

采用栈实现算法。由于括号有多种类型，这里可以以圆括号为例来判断输入的程序语句和数学表达式中的左右括号是否匹配。

（3）算法描述

首先，建立一个栈结构，且初始化为空，即令栈顶指针top=0。然后由键盘上随机输入一个带括号的语句或带括号数学表达式，同时将它们 保存在一个字符型数组中，再对字符数组中的每个元素进行访问，若是遇到右括号，则将栈中的栈顶元素出栈。当字符数组所有元素都访问完之后，再根据栈顶指针top的值判断左右括号是否匹配，若top=0时，则左右括号匹配，否则，左右括号不匹配。

在进行出栈运算时，通常在栈顶指针top=0时，就不能进行出栈运算了，为正确判断形如“x*(y+z))”类型的表达式，在出栈运算时，可将栈空的判断步骤取消。也就是说，允许栈顶指针为小于0的数，如-1，-2等，此时是右半括号数多于左半括号数，是不匹配的一种情形。

（4）算法实现——示例程序

#include #include #define m 20;

14

typedef char ElemType;

typedef struct /* 栈类型定义 */ {

ElemType stack[m ]; /*数据域为字符型*/ int top; /*栈顶指针*/ }stacknode; stacknode *sp;

init(stacknode *st) /*初始化栈*/ {

st->top=0; /*栈顶指针为0*/ return }

void push(stacknode *st,ElemType x) /*将元素x入栈*/ {

if(st->top==m) /*判断栈st是否已满*/ printf(\

else /*不满，则将元素x加入栈st中*/ {

st->top=st->top+1; st->stack[st->top]=x; } }

void pop(stacknode *st) /*将栈st的栈顶元素出栈*/ {

st->top=st->top-1; }

main() {

char s[m]; int i,k;

printf(\init(sp);

printf(\

gets(s); /*输入表达式*/ for (i=0;i

if(s[i]=='(') /*遇到表达式中的左括号，则将其入栈*/ push(sp,s[i]);

if(s[i]==')') /*遇到表达式中的左括号，则将其出栈*/ pop(sp); }

if(sp->top==0) /*如果栈最后恢复为空，则表达式中的左右括号是匹配的*/ printf(\左右括号是匹配的！\\n\

15

else /*否则表达式中的左右括号是不匹配的*/ printf(\左右括号不匹配！\\n\} 2、迷宫问题 （1）问题描述

以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和故障。设计一个程序，对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

（2）基本要求

首先实现一个以链表做存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,k）的形式输出，其中：（i,j）指迷宫中的一个坐标，d表示走到下一坐标的方向。 （3）实现提示

计算机解迷宫通常采用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未达到出口，则所设定的迷宫没有通路。 可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为(n，n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。

? 选作内容：

1）编写递归形式的算法，求得迷宫中所有可能的通路； 2）以方阵形式输出迷宫及其通路。 3、算术表达式求值演示

（1）问题描述

表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。

（2）基本要求

以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教材表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教材的例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。

四、实验要求

1、认真阅读和掌握、上机调试并运行实验内容1的程序；保存和打印出程序的运行结果，并结合程序进行分析。

2、用C/C++完成实验内容2、3的算法设计和程序设计并上机调试通过。要求： （1）给出程序设计的基本思想、原理和算法描述。 （2）对源程序给出注释。

（3）保存和打印出程序的运行结果，并结合程序进行分析。 3、撰写实验报告，提供实验结果和数据。

16

实验四 队列应用

一、实验目的

1、 掌握队列结构及其基本运算的实现 2、 编程实现排队问题的系统仿真

二、实验环境

PC微机，Windows，DOS，Turbo C或Visual C++

三、实验内容

排队问题的系统仿真

（1）问题描述

使用队列模拟理发馆的排队现象，通过仿真手法评估其营业状况。

设理发馆有N把理发椅，可同时为N位顾客进行理发。当顾客进门时，若有空椅，则可立即坐下理发，否则需要依次排队等候。一旦有顾客理完发离去时，排在队头的顾客便可开始理发。若理发馆每天连续营业了T小时，求一天内顾客在理发馆内的平均逗留时间、顾客排队等候理发的队列长度平均值、营业时间到点后仍需完成服务的收尾工作时间。 （2）基本要求

1）设计程序模拟理发馆排队现象。当给定理发椅数及营业时间后，由随机数确定顾客理发时间及进门间隔时间，可以求出一天内在理发馆平均逗留时间，平均队长及关门后收尾工作的时间。

2）设计的程序由用户读入的数据仅为理发椅数及营业时间。营业的时间以分钟计，理发椅数及关门时间均为整型，且均大于1。

3）运行程序后得到结果为顾客数、平均等候时间、平均队长时间和收尾工作的时间。

四、实验要求

1、用C/C++完成实验内容的算法设计和程序设计并上机调试通过。要求： （1）给出程序设计的基本思想、原理和算法描述。 （2）对源程序给出注释。

（3）保存和打印出程序的运行结果，并结合程序进行分析。 2、撰写实验报告，提供实验结果和数据。

17

实验五 串的操作及应用

一、实验目的

1、 掌握串的顺序存储和链式存储的类型定义及实现 2、 掌握串的基本运算及其实现

3、 掌握字符串运算在解决实际问题中的应用

二、实验环境

PC微机，Windows，DOS，Turbo C或Visual C++

三、实验内容

1、文学研究助手

（1）问题描述

文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。 （2）基本要求

英文小说存放于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。 （3）实现提示

约定小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中的出现次数。出现位置所在的行号可以用链表存储。若某行中出现了不止一次的出现了不止一次，不必存多个相同的行号。

2、程序分析

（1）问题描述

读入一个C程序，统计程序中代码、注释和空行的行数以及函数的个数和平均行数。 （2）基本要求

1）把C程序文件按字符顺序读入源程序；2）边读入程序，边识别统计代码行、注释行和空行，同时还要识别函数的开始和结束，以便统计其个数和平均行数。

四、实验要求

1、用C++/C完成实验内容的算法设计和程序设计并上机调试通过。要求： （1）给出程序设计的基本思想、原理和算法描述。 （2）对源程序给出注释。

（3）保存和打印出程序的运行结果，并结合程序进行分析。 2、撰写实验报告，提供实验结果和数据。

18

实验六 二叉树的建立和遍历

一、实验目的

1、掌握二叉树链式存储的类型定义及实现。

2、掌握二叉树链式存储的各种基本运算方法。如二叉树的创建、遍历、查找等运算。 3、掌握二叉树用不同方法表示所对应的不同输入形式。 4、掌握二叉树中各重要性质在解决实际问题中的应用。

二、实验环境

PC微机，Windows，DOS，Turbo C或Visual C++

三、实验内容

1、建立二叉树并实现各种遍历

（1）问题描述

对二叉树的各种结点都访问，而且每个结点只访问一次的过程称为二叉树的遍历。根据访问二叉树中左子树、根、右子树的不同顺序，可先分为先根遍历、中根遍历、后根遍历三种访问方法。

另外，由于二叉树中所有结点有相应的层次顺序，则按照从第1层到最后一层的访问顺序，并且每层都从左到右进行访问，又可得到层序遍历的访问方法。试编程完成：

? 用递归方法完成二叉树的创建、先根遍历、中根遍历、后根遍历。

? 用非递归方法完成完成二叉树的创建、按层遍历、中根遍历、后根遍历。 （2）基本要求

程序运行时，先输入二叉树结点的值（一个字符），先建立二叉树，然后对建立的二叉树分别进行先序、中序和后序遍历；要求格式化输出遍历结果：每一序列数据之间用“－>”分开；三种遍历结果应分行显示；输出结果之前最好给出提示，如：InOrderTraverse: ； （3）算法描述

在算法实现上，从算法的效率看，非递归方法具有较好的时间效率，递归方法书写形式较为简捷，更为直观，一般具有较好的空间效率。在此选用非递归方法。用非递归方法对二叉树进行不同顺序的遍历，比递归方法要复杂得多。可以说二叉树的先根、中根、后根、按层顺序遍历的四种不同方法，其非递归的实现过程差别非常大。 1）创建树

将读入的字符串转换成二叉树

用ch扫描采用括号法表示二叉树的字符串。分以下几种情况： a）、ch=?(? 则将前面创建的结点作为双亲结点进栈，并置k=1,表示后面创建的结点作为 这个结点的左孩子结点： b）、ch=?)? 表示栈中的左右孩子处理完毕，退栈： c）、ch=?,? 表示其后面创建的结点作为这个结点的右孩子结点： d）、其它情况创建结点，根据k值建立它与栈中结点之间的关系， 当k=1时，表示结点作为栈中结点的左孩子结点;

19

当k=2时，表示结点作为栈中结点的右孩子结点

如此循环直到客串处理完毕。算法中使用的栈st保存双亲结点，top为其栈指针，k 为其后处理结点是双亲结点的左结点还是右结点。 2）先序遍历

a）访问根结点； b）先序遍历左结点; c) 先序遍历右结点; 3）中序遍历

a) 中序遍历左结点; b）访问根结点； c) 中序遍历右结点; 4）后序遍历

a) 后序遍历左结点; b) 后序遍历右结点; c）访问根结点； （4）算法实现——示例程序 #include #include using namespace std; typedef struct tnode {

char data;

struct tnode *lchild,*rchild; }BTNode; class Tree {

public:

void CreateBTree(BTNode *&bt,char *str) {

BTNode *st[100],*p=NULL; int top=-1,k,j=0; char ch; bt=NULL; ch=str[j];

while(ch!='\\0') {

switch(ch) {

case '(':

top++;st[top]=p;k=1; break; case ')': top--;

20

break; case ',': k=2; break; default:

p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(bt==NULL) ////////// {

cout<<\根结点: \ bt=p; } else {

switch(k) { case 1:

st[top]->lchild=p;cout<data<<\的左孩子:\

case 2:

st[top]->rchild=p;cout<data<<\的右孩子:\

} } } j++;

ch=str[j]; }

cout<<\二叉树构建成功!\ }

//先序遍历

void PreOrder(BTNode *bt) {

if(bt!=NULL) {

cout<<\ PreOrder(bt->lchild); PreOrder(bt->rchild); } }

//中序遍历

void InOrder(BTNode *bt) {

if(bt!=NULL) {

InOrder(bt->lchild);

21

cout<<\ InOrder(bt->rchild); } }

//后序遍历

void PostOrder(BTNode *bt) {

if(bt!=NULL) {

PostOrder(bt->lchild); PostOrder(bt->rchild); cout<<\ } }

void input(char treeList[]) {

//char treeList;

cout<<\ cin>>treeList; //return treeList; } };

int main(int argc, char *argv[]) {

BTNode *tree; Tree tr;

char treeList[50];

cout<<\读入二叉树：\ tr.input(treeList);

cout<<\开始构建二叉树...\ tr.CreateBTree(tree,treeList); cout<

cout<

cout<

return EXIT_SUCCESS; }

2、求二叉树的宽度

（1）问题描述

对任意建立的一颗二叉树求其中的结点数和叶结点数。

22

（2）基本要求

在输入数据创建二叉树的过程中，要求以二叉树遍历的先根顺序输入。统计结点总数和页结点总数的功能分别用一个函数编程实现，在主函数中调用相应子函数。在实现统计时，注意局部变量和全局变量对统计结果正确性的影响。 3、哈夫曼树在通信编码中的应用

（1）问题描述

根据哈夫曼算法，对电文中的不同字符，构造出一棵哈夫曼树，对每个字符进行编码。 （2）基本要求

采用顺序存储方式创建哈夫曼树和进行哈夫曼编码。

四、实验要求

1、认真阅读和掌握、上机调试并运行实验内容1的程序；保存和打印出程序的运行结果，并结合程序进行分析。

2、用C++/C完成实验内容2、3的算法设计和程序设计并上机调试通过。要求： （1）给出程序设计的基本思想、原理和算法描述。 （2）对源程序给出注释。

（3）保存和打印出程序的运行结果，并结合程序进行分析。 3、撰写实验报告，提供实验结果和数据。

实验七 图的应用及其算法

一、实验目的

1、 掌握图的邻接矩阵、邻接表、十字链表等不同存储形式的表示方法。 2、 掌握图的两种不同遍历方法的基本思想并能编程实现。 3、 掌握求最小生成树的的两种算法，即Prim算法和Kruscal算法的思想，并能用C/C++

语言编程实现。

4、 掌握求最短路径的两种不同情形的算法，即单源最短路径和任何一对顶点之间的最

短路径，并能用C/C++语言编程实现。 5、 掌握求关键路径的算法，并能编程实现。

6、 能够灵活运用图的相关算法解决相应的实际问题。

二、实验环境

PC微机，Windows，DOS，Turbo C或Visual C++

三、实验内容

1、工程造价最小问题 （1） 问题描述

如果以无向网表示n个城市之间的交通网络建设规划，顶点表示城市，边上的权表示该线路的造价，试设计一个方案，使这个交通网的总造价最小。 （2）基本要求

23

该问题描述的内容实际上在生活中有相同的情形，解决的方法是构造一个带权无向图（即无向连通网），然后利用Kruscal算法求最小生成树。

（3）算法描述

假设连通网N=(V,{E}),则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有的顶点都在同一连通分量上为止。 （4）算法实现——示例程序

#include #define Maxvex 20 using namespace std; static c=1;

typedef struct ArcCell { int adj; int info;

}AdjMatrix[Maxvex][Maxvex];

typedef struct { AdjMatrix arcs; int vex[Maxvex]; int vexnum,arcnum; }MGraph;

void display(MGraph G) { int i,j;

for(i=0;i

int Locate(MGraph &G,int v) { return G.vex[v-1]; }

void CreateAdjMatrix(MGraph &G) { int v1,v2,weight,i,j,l,m;

cout<<\请输入顶点数：\ cin>>G.vexnum;

cout<<\请输入边数：\ cin>>G.arcnum;

for( i=0;i

{ cout<<\请输入各个顶点的编号\

24

cout<<\ \ cin>>G.vex[i]; }

for(i=0;i

{ G.arcs[i][j].adj=100; G.arcs[i][j].info=0; } for(i=0;i

{ cout<<\请输入边所依附的顶点及其权值：\ cout<<\ cin>>v1; cout<<\

cout<<\ cin>>weight; l=Locate(G,v1); m=Locate(G,v2); G.arcs[l][m].adj=weight; }

for(l=0;l

{ G.arcs[m][l].adj=G.arcs[l][m].adj; G.arcs[m][l].info=G.arcs[l][m].info; } }

void minimun(MGraph &G,int *p) { int i,j,l,m,Min=100,temp; for(i=0;i

//if(Min!=100)

{ if(!(*(p+l))&&!(*(p+m))) { *(p+l)=*(p+m)=c; c++;

cout<<\ } else if(*(p+l)!=*(p+m)) { if(*(p+l)==0) { *(p+l)=*(p+m); cout<<\ else if(*(p+m)==0) { *(p+m)=*(p+l); cout<<\ else

25

} }

{ cout<<\ temp=*(p+m); for(i=0;i

G.arcs[l][m].info=1; } }

void MidSpanTree_Kruskal(MGraph G) { int vertex[Maxvex]; int *p=vertex; int i;

for(i=0;i

vertex[i]=0;

for(i=0;i

void main() { MGraph G;

CreateAdjMatrix(G); display(G);

cout<<\ MidSpanTree_Kruskal(G);

cout<<\ }

2、旅游导游系统问题

（1）问题描述

假设一个旅游景区由n个不同景点组成（有向网），并用带权邻接矩阵表示，权值表示两个景点间的步行时间，试编写程序求任意两个景点间的最短步行时间。

（2）基本要求

实际上是求有向图中任意两顶点间的最短路径问题。利用Floyed算法编写函数实现求图的任意两点间的最短路径。

四、实验要求

1、认真阅读和掌握、上机调试并运行实验内容1的程序；保存和打印出程序的运行结果，

26

并结合程序进行分析。

2、用C++/C完成实验内容2的算法设计和程序设计并上机调试通过。要求： （1）给出程序设计的基本思想、原理和算法描述。

（2）对源程序给出注释。

（3）保存和打印出程序的运行结果，并结合程序进行分析。 3、撰写实验报告，提供实验结果和数据。

实验八 查找

一、实验目的

1、 掌握顺序表查找中不同查找方法的查找思想，并能用C/C++语言实现。

2、 掌握树表查找中二叉排序树查找、平衡二叉树查找的查找思想，并能用C/C++语言

实现。

3、 掌握Hash表查找中的查找思想，并能用C/C++语言实现。 4、 能够针对具体实际，灵活选用适宜的查找方法。

二、实验环境

PC微机，Windows，DOS，Turbo C或Visual C++

三、实验内容

1、二叉排序树查找

（1）问题描述

查找是计算机操作中的一种重要应用技术，查找的方法有许多，不同的查找方法有不同的查找效率，而二叉排序树查找就是效率较高的查找方法之一。

所谓二叉排序树，就是指将原来已有数据根据大小构成一棵二叉树，二叉树中的所有结点数据满足一定的大小关系，所有左子树中的结点均比根结点小，所有右子树中的结点均比根结点大。

二叉排序树查找是指按照二叉排序树中结点的关系进行查找，查找关键字首先同树根结点进行比较，如果相等则查找成功；如果比根结点小，则在左子树中查找；如果比根结点大，则在右子树中进行查找。这种查找方法可以快速缩小查找范围，大大减少了查找关键字的比较次数，从而提高了查找效率。

（2）基本要求

编程实现时，体现查找的全过程，即二叉排序树的创建、查找关键字的输入、查找关键字的查找、查找结果的输出等。 2、通讯录的管理

（1）问题描述

试编程完成通讯录的一般性管理工作，如通讯录中记录的增加、修改、查找、删除、输出等功能。每个记录包含姓名、电话号码、住址等个人基本信息。 （2）基本要求

27

将建立的通讯录以磁盘文件的形式存储，所有的通讯录管理均以文件操作的方式进行。在查找通讯录中的记录时，以记录的“姓名”为查找关键字进行查找。由于“姓名”是字符串类型的数据，其查找过程比整形关键字的查找过程要复杂，关键字比较过程可调用字符串函数，也可以自己实现其比较过程。

四、实验要求

1、用C++/C完成实验内容1和2的算法设计和程序设计并上机调试通过。要求： （1）给出程序设计的基本思想、原理和算法描述。 （2）对源程序给出注释。

（3）保存和打印出程序的运行结果，并结合程序进行分析。 2、撰写实验报告，提供实验结果和数据。

实验九 内排序

一、实验目的

1、掌握插入排序、选择排序、交换排序、归并排序等各种排序方法的基本思想并能用C/C++语言实现。

2、掌握各种排序方法的特点及适用情形，并能在解决实际问题的过程中灵活选用不同的排 序方法。

3、掌握各种排序方法的操作过程及其依据。，

二、实验环境

PC微机，Windows，DOS，Turbo C或Visual C++

三、实验内容

1、学生成绩统计、排序的实现

（1）问题描述

在学生成绩管理中，经常会遇到求平均成绩，统计不几个学生成绩，统计优秀学生人数，以及按成绩对学生进行排名等。现假设有某个班级的若干名学生，每个学生都考试完成了相同的4门课程，试对所有学生的成绩完成以下工作：

1） 求每门课程的平均成绩。

2） 输出有课程不及格学生的姓名、学号及其各门课程的成绩。 3） 输出个人平均分超过90分的学生姓名、学号。

4） 对4门课程中的任何一门，可随意抽取1门按学生成绩进行排序。 （2）基本要求

由于问题描述中涉及的学生个人信息包含的内容较多，要完成所有工作必须设计较为合理的数据结构，否则在算法实现时，可能会增加不少难度。在对某门课程按成绩进行排序时，要根据实际情况，灵活选用排序方法。在编程实现时，一定要体现清晰的算法思想，注重程序的实现性和通用性。 2、多种基本内排序方法的实现

（1）问题描述

教材中关于排序的方法介绍了许多种，如果不深刻理解它们的排序思想，实际应用中非

28

常容易混淆，不易于在算法设计中灵活运用。准确掌握不同排序排序方法的有效手段就是比较。试比较直接插入排序法、冒泡排序、简单选择排序、快速排序和堆排序的思想，并编程实现它们。

（2）基本要求

输入各种不同的数据检验在各种排序方法下的结果，比较结果是否一样。

四、实验要求

1、用C++/C完成实验内容1和2的算法设计和程序设计并上机调试通过。要求： （1）给出程序设计的基本思想、原理和算法描述。 （2）对源程序给出注释。

（3）保存和打印出程序的运行结果，并结合程序进行分析。 2、撰写实验报告，提供实验结果和数据。

29