数据结构实验报告（华夏）

武汉理工大学华夏学院

数 据 结 构

实验报告册

专 业________________ 班 级_________________ 学 号_________________ 姓 名_________________

信息工程系 2011.9

前 言

本讲义是为配合我院《数据结构》课程配套的实验讲义 。《数据结构》课是计算机及其相关专业的专业基础课，该课程一方面要求学会分析研究计算机加工的数据对象的特征以便选择合适的数据结构及其存储结构以及相应的算法 。另一方面，学习本课程的过程也是进行复杂程序设计的训练过程，要求学生编制的计算机程序结构清晰、正确易读 ，所以整个教学过程中，实验是一个重要的环节。为了帮助我院学生学好《数据结构》课程，提高学生使用数据结构和编制程序的能力 根据《数据结构》课程教学大纲，结合我院的教学特点和实际情况，我们编制了此讲义。

本讲义的实验内容涵盖了教学大纲的基本要求，既有实际操作步骤，又有完成操作后的小结。便于学生记录操作过程和总结经验，也是教师检查学生实验操作完成好坏的佐证。

使用本讲义方法是：在上实验课之前，学生预习教材和讲义上的相关内容，对需要完善补充或思考的内容做好准备，实验时再逐一验证、观察效果后强化动手能力，最后举一反三，反复动手，从而在理论和实践两个方面都有收获 。

本讲义准备了九个实验，其内容是： 实验一 顺序表的应用 实验二 链表的应用

实验三 稀疏矩阵的基本操作的实现 实验四 哈夫曼树及哈夫曼编码的实现 实验五 单源最短路径的实现算法 实验六 查找算法设计

实验七 散列（哈希）表的建立和查找算法设计 实验八 常规排序算法设计 实验九 快速排序算法设计

在每一个实验里面有一个演示题及一至二个巩固题。教师可以根据需要安排相关内容。对不同的实验学时，教师可选择进行。

本讲义也是一本作业，每当完成一个实验时，实验讲义要上交给任课老师批阅，从而使教师了解学生学习情况。

由于水平有限，讲义中错误和不足之处在所难免，恳请用户提出宝贵意见。

编者2010.3 于华夏学院

实验部分

实验一 顺序表的应用

一、预习报告

实验目的

1． 掌握用Turbo C上机调试线性表的基本方法；

2． 掌握线性表的基本操作：插入、删除、查找及线性表合并等运算在顺序存储结构

上的运算算法在C语言上的程序实现；

基本原理与方法 顺序表的操作算法用C语言编程实现 实验设备 PC机一台、配置Turbo C软件 二、实验内容

线性表基本操作的实现-----电子通信录的设计

[问题描述] 设计一个通信录，用顺序存储结构进行存储，设计出生成线性表、在第I

个结点位置插入结点、删除第I个结点、打印表中结点的算法。

[基本要求]

1． 模拟生成线性表：先用下面给出的程序，读懂，并上机运行，可以以最少数据

（如：每个结点只用一个字符表示）进行调试，元素通过键盘进行读取。 2． 根据自己手机中设置的电话本，设计通信录，写出完整程序并上机测试。 [参考程序] #include

typedef char datatype ; #define maxsize 1000 typedef struct

{ datatype data[maxsize] ; /*定义线性表为一个向量*/ int last; } sequenlist ; /* 插入函数*/

int insert(sequenlist *L,char x,int i) /*将新结点X插入到表L的第I个位置*/

/*L为指向线性表sequenlist类型的指针变量*/

{ int j ;

if ((*L).last= = maxsize-1)

{ printf(“overflow\\n”) ; return 0; }

else

if ((i<1 ) || (i>(*L).last+1))

{ printf(“error\\n”) ; /* 非法位置*/ return 0 ; } else

{ for (j=(*L).last ; j>=i-1 ; j- -) (*L).data[j+1]= (*L).data[j] ; (*L).data[i-1]= x ;

(*L).last = (*L).last +1 ; }

return (1) }

/* 删除函数*/ /*从表中删除第I个结点*/ int delete (sequenlist *L, int i) {

int j ;

if ((i<1 ) || (i>(*L).last+1) /* 非法位置*/ { printf(“error\\n”) ; return 0 ; } else

{ for ( j=i ; j<= (*L).last ; j++) (*L).data[j-1]= (*L).data[j] ; (*L).last = (*L).last -1 ; }

return (1) }

/* 生成线性表*/

void creatlist (sequenlist *L )

{ int i ,j,n ;

printf (“ input data\\n” ) /*输入N个数据*/ scanf(“%d”,&n) ;

for ( i=0 ;L=data;i

}

(*L).last=n-1 ; printf (“\\n”);

}

/* 输出线性表*/

printout (sequenlist *L) { int i;

for ( i=0 ; i< (*L).last ; i++) { printf (“ data[%d]=”, i ) printf (“ %c ”, *L.data[i] ) ; } } main ()

{ sequenlist *L; char cmd ,x; int i , s;