数据结构实验指导书

《数 据 结 构 与 算 法》

实 验 指 导 书

2013年8月

目 录

实验一 C语言编程复习 ..................................................................... 3 实验二 线形表基本操作的实现 ........................................................ 7 实验三 栈和队列基本操作的实现及应用 ...................................... 17 实验四 二叉树算法的实现 .............................................................. 29 实验五 图的算法的实现 .................................................................. 43 实验六 查找算法的实现 .................................................................. 60 实验七 排序算法的实现 ................................................................ 70

2

实验一 C语言编程复习

一、实验目的

1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.理解指针与应用的区别。 3.掌握结构体的使用。 4.掌握简单排序方法。 二、实验内容

(1) 输入一行字符，计算该行字符中包含多少个单词，单词之间用空格

分隔开。

(2) 利用add函数求两个复数2+3i和4+5i的和。（要求用结构体来定义

复数）

(3) 一个班上有30名学生，每个学生的数据作为一个记录，每个记录包

括学号、姓名、三门课程的成绩和三门课程平均成绩。从键盘输入学生的学号、姓名及三门课的成绩。要求打印三门课程平均成绩最高分的学生记录。

三、实验步骤

(1) 用数组或字符串获取字符，碰到空格即表示新单词的开始。 (2) 要求用结构体来定义复数，包括实部和虚部。

(3) 定义一个Student的结构体类型，包含学号、姓名、成绩等成员。 四、实现提示 struct student { char num[6]; string name;

float score[3]; float aver; };

3

五、思考与提高

思考为何void Swap1(Student, Student )这个函数无法实现两个学生的交换？

六、完整参考程序

1、

#include #include using namespace std; void main() { cout<<\输入n个单词，单词之间用空格隔开\ string str; getline(cin,str); int num=0; int len=str.size(); if(len!=0) num=1; for(int i=0;i

也可使用数组实现： #include using namespace std; void main() { cout<<\输入n个单词，单词之间用空格隔开\ char str[100]; cin>>str; int num=0; for(int i=0;str[i]!='\\0';i++)

4

{

if(str[i]=' ') {

num++; } }

cout<<\单词个数为：\

} 2、

#include using namespace std; struct complex { float real; float imag; };

complex add(complex x1,complex x2) { complex sum; sum.real=x1.real+x2.real; sum.imag=x1.imag+x2.imag; return sum; };

void main() { complex x1={2,3},x2={4,5},sum; complex add(complex x1,complex x2); sum=add(x1,x2); cout<<\ \ cout<<\} 3、

#include #include #include using namespace std;

5