《数据结构与算法》课间实习指导书

数据结构与算法

实验指导书

编写：程朋根

东华理工学院地测学院GIS系

二○○六 年九月

前 言

地理信息系统(Geographic Information System, GIS)专业的主要工作是利用计算机技术手段有效管理各类空间信息，并为各种与地学分布有关的研究领域提供决策服务。《数据结构》课程是地理信息系统专业一门重要的专业基础课程，主要涉及数据的表示与数据处理。通过本课程的教学，学生应该掌握算法分析、算法设计和为计算机加工处理的数据设计逻辑结构的基本方法和理论；学会分析研究数据结构的特性，以便为地理信息系统研究与应用领域所涉及的数据选择适当的逻辑结构，为GIS程序设计、二次开发打下扎实的基础。实验实习是理论教学向实践性转化的重要手段，通过实验可以使学生对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。根据本课程内容，结合GIS专业特点，同时从学时数的角度来考虑，我们选择了四个课内实验实习：线性表的插入和删除算法实现；栈和队列的插入和删除算法实现；二叉树的操作算法的实现；最短路径算法的实现。同时选择了两个可选实验：排序、查找。为了提高学生自学编程的积极性，本指导书还选择了八个课外上机实验源程序，有时间或感兴趣的同学可以利用课外时间上机编程实现。

本实验指导书的以程序或子程序的形式给出，编程语言为C或VC++，上机时同学们可以根据实际情况选择相应的语言加以调试实现，为了帮助同学们理解，本指导书同时给出了（子）程序实现思路或算法。本书给出的程序均为可运行程序的子程序，或可运行程序，同学们根据自己的理解增加主程序、头文件定义就可调用相应的子程序。最好在阅读本实验指导书源程序的基础上进行扩充，以便在更复杂数据元素的情况下，实现相应的数据结构与算法。

由于时间仓促，错误难免。希望同学们在学习过程中加以指正。

编者：程朋根 2006．9．28

目 录

第一部分：课内实验内容

实验一 线性表的插入和删除算法实………………………………………………………………1 实验二 栈和队列的插入和删除算法实现…………………………………………………………9 实验三 二叉树的操作算法的实现 ………………………………………………………………17 实验四 最短路径算法的实现 ……………………………………………………………………29 实验五 排序 ………………………………………………………………………………………40 实验六 查找 ………………………………………………………………………………………42

第二部分：课外上机实验源程序

1、 基本排序………………………………………………………………………………………45 2、 基数排序………………………………………………………………………………………51 3、 顺序查找………………………………………………………………………………………55 4、 折半查找………………………………………………………………………………………57 5、 二叉树的操作…………………………………………………………………………………58 6、 二叉排序树上的查找…………………………………………………………………………62 7、 以字符串为数据的单链表操作………………………………………………………………65 8、邻接表表示的图的深度优先搜索和广度优先搜索程序 ……………………………………67

第三部分：实验步骤、实验报告规范

………………………………………………………………………………………………………71

课内实验主程序

………………………………………………………………………………………………………73

第一部分：课内实验内容

实验一 线性表的插入和删除算法实现

一、实验目的

掌握用VC或Turbo C上机调试线性表的基本方法；掌握线性表的基本操作，以顺序表示、链式表示两种存储方式实现线性表的建立、插入、删除等算法；了解线性表的查找、合并算法的实现。

二、实验内容

熟悉在VC或Turbo C环境下的编程与调式程序的方法；在线性表的顺序表示和链式表示两种方式中选择一种存储方式，实现线性表的创建、插入、删除算法；编写主程序、定义相应的变量，上机调式实现本次实验内容。

三、提交成果

实习报告与可运行的源程序。

四、算法子程序

(一) 线性表的顺序表示时基本操作实现——静态数组 一) 基本思想

线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构如图1-1所示，其特点是：

1．第i个元素ai的存储位置可以用公式计 LOC(ai) = LOC(a1)+(i-1)*L

其中LOC(a1)第一个元素a1的存储位置，L素需占的存储单元

2．表中相邻的元素ai和ai+1赋以相邻的存LOC(ai)和LOC(ai+1)

3．是一种随机存储结构：只要知道线性表的置就可随机存取线性表中的任一元素。

图1-1 线性表的顺序存储结构示意图

起始位储位置每个元

二） 线性表的插入与删除操作思路

当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。它们的操作过程如图1-2所

示。

在线性表上的第i个位置插入一个元素e

删除线性表上第i个元素并赋给e 图1-2线性表的插入与删除操作示意图

三） 算法实现

1. 参数定义

typedef Null 0; typedef int datatype; #define maxsize 1024;

2. 结构定义 typedef struct {

datatype data[maxsize]; int last; }sequenlist;

3. 子程序

/*在线性表L的第i个位置插入元素x*/ int insert(L, x, i) sequenlist *L; int i; {

int j;

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

printf(“overflow”); return Null; } else

if ((i<1)‖(i>(*L).last+1){ printf(“error”); return Null; } 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); }

/*删除线性表L的第i个位置插入元素*/ int delete(L,i) sequenlist *L; int i; { int j;

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

printf (“error”); return Null; } else {

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

return(1); }

/*建立线性表*/ void creatlist( ) {

sequenlist *L; …… 此处隐藏：6360字，全部文档内容请下载后查看。喜欢就下载吧 ……