C语言版 软件与理论教研室 张泽宝 哈尔滨工程大学计算机科学与技术学院

《数据结构》课程简介 一、课程性质与教学目的 二、基本要求 三、教学内容 四、学分及学时分配 五、参考书目 六、前期课程及后续课程 第一章

一、课程性质与教学目的 用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是《数据结构》要研究的内容。《数据结构》是计算机科学中一门综合性的专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。 通过本课程的学习，使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。

二、基本要求 1.了解数据结构及其分类、数据结构与算法的密切关系。 2.熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。 3.掌握设计算法的步骤和算法分析方法。 4.掌握数据结构在排序和查找等常用算法中的应用。 5.初步掌握文件组织方法和索引技术。

三、教学内容 见书目录

四、学分及学时分配 学时：课程讲授学时６４

五、参考书目 严蔚敏等著 《数据结构》 清华大学出版社 1997 范策等著 《算法与数据结构》 机械工业出版社 2004 严蔚敏等著 《数据结构》 清华大学出版社 1997 范策等著 《算法与数据结构》 机械工业出版社 2004 李春保 《数据结构与习题解析》 清华大学出版社 1997 谢楚屏等编著 《数据结构》 人民邮电出版社

六、前期课程及后续课程 前期：C语言，计算机基础，离散数学 后续：操作系统，数据库等

C语言版 软件与理论教研室 张泽宝 哈尔滨工程大学计算机科学与技术学院 第一章 绪论

本 章 说 明 1.1 数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示和实现 1.4 算法和算法分析 目 录 第一章 绪 论 1.1 数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示和实现 1.4 算法和算法分析 目 录 第一章 绪 论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 数组和广义表 第六章 树和二叉树 第七章 图 第八章 查 找 第九章 内部排序 第十章 文 件

本章说明 本章的主要内容 本章与后续各章的关系 基本概念和术语 抽象数据类型的表示与实现 算法和算法分析（掌握时间复杂度和空间复杂度） 本章是后续各章的准备

1.1 数据结构 1．什么是数据结构 我们大家知道许多非数值计算问题的数学模型常常是数学方程，如线性方程组、微分方程。所以这类非数值计算问题的解决就归结于对数学模型设计算法、编写程序。然而在现实社会中存在着许多非数值计算问题，其数学模型难以用数学方程描述。

计算机处理的对象之间存在着线性关系，称为线性的数据结构。 线性表 例1-1 书目检索自动化问题 书目文件 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目卡片 按书名 按作者名 按分类号 索引表 计算机处理的对象之间存在着线性关系，称为线性的数据结构。

例1-2 人机对奕问题 树 …….. …...

图 例1-3 多岔路口交通灯的管理问题 C E D A B AB AC AD BA BC BD DA DB DC EA EB EC ED

2.《数据结构》课程 1968年美国克努特教授开创了数据结构的最初体系： 数据的逻辑结构和存储结构及其操作。 数据结构是一门综合性的专业课程，是一门介于数学、计算机硬件、计算机软件之间的一门核心课程。是设计和实现编译系统、操作系统、数据库系统及其他系统程序和大型应用程序的基础。

数据结构定义 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科 主要研究和讨论以下三个方面的问题: (1) 数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构. (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构. (3)对各种数据结构进行的运算.

1.2 基本概念和术语 1．数据 2．数据对象、数据结构 3．数据的两种存储结构 4. 数据类型、抽象数据类型

1.2 基本概念和术语 1.数据 数据：是指所有能输入到计算机中并被计算机程序处理的符号的总称。是计算机加工的“原料”。 数据元素:是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，也称节点或记录 数据项:有时，一个数据元素可由多个数据项组成。数据项是数据的不可分割的最小单位。

1.2 基本概念和术语 2.数据对象、数据结构 数据对象：是性质相同的数据元素的集合，是数据的一个子集。 例：整数数据对象是集合N={0，±1，±2，……} 字母字符数据对象是集合C={“A”，“B”，……“Z”} 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

根据数据元素间关系的基本特性，有四种基本数据结构： 集 合——数据元素间除“同属于一个集合”外，无其它关系 线性结构——一个对一个，如线性表、栈、队列 树形结构——一个对多个，如树 图状结构——多个对多个，如图

1.2 基本概念和术语 数据结构的形式定义：数据结构是一个二元组 Data_Structure=(D,S) 其中，D 是数据元素的有限集,S 是D上关系的有限集 例1-4 复数 Complex=(C,R) 例1-5 课题小组 Group=(P,R) P={T,G1,…,Gn,S11,…,Snm}1≤n≤3，1≤m≤2， R={R1,R2} R1={<T,Gi> |1≤i≤n, 1≤n≤3,} R2={<Gi,Sij> |1≤i≤n, 1≤j≤m,1≤m≤2,}

1.2 基本概念和术语 数据的逻辑结构—只抽象反映数据元素的逻辑关系 数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现 位：在计算机中表示信息的最小单位，二进制数的一位 位串：由若干个位组合，表示一个数据元素。（以后称“元素”或“结点”） 例：整数用一个字长（16位）表示，字符用8位表示 子位串：表示一个数据项。（以后称“数据域” ）

1.2 基本概念和术语 3．数据的两种存储结构 存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据 元素间的逻辑关系 数据的逻辑结构与存储结构密切相关 算法设计 取决于选定的逻辑结构 算法实现 依赖于采用的存储结构

顺序存储 元素n …….. 元素i 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容 Loc(元素i)=Loc+（i-1)*m 顺序存储

h h 1345 元素1 1400 元素2 1536 元素3 1346 元素4 ∧ 存储地址 元素1 1400 元素2 1536 链式存储 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. 元素2 1536 元素3

数据的运算：检索、排序、插入、删除、修改等 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个方面：

4.数据类型 抽象数据类型 数据类型：是一个值的集合和定义在这个值集上的所有 的操作。如，整型。 4.数据类型 抽象数据类型 数据类型：是一个值的集合和定义在这个值集上的所有 的操作。如，整型。 数据类型可分为：非结构的原子类型和结构类型。 原子类型的值是不可分解的 结构类型的值是由若干成分按某种结构组成的。

数据类型在高级语言中指数据的取值范围及其上 可进行的操作的总称 例 C语言中，提供int, char, float, double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef 自己定义数据类型 typedef struct { int num; char name[20]; float score; }STUDENT; STUDENT stu1,stu2, *p; 数据类型可以看成是已经实现了的数据结构。

也就是说抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。 抽象数据类型： 是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，它仅取决于数据类型的逻辑性，而与其在计算机内部如何表示和实现是无关的。 也就是说抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。

按抽象数据类型值的不同特性，分为三种类型： ①原子类型:变量的值是不可分解的。 ②固定聚合类型:变量的值由确定数目的成分按 某种结构组成。 ③可变聚合类型:其值的成分数目不确定。 抽象数据类型的形式定义 我们用一个三元组来表示一个抽象数据类型：（D，S，P） D是数据对象，S是D上的关系集， P是对D的基本操作。

抽象数据类型格式：P8-9 ADT 抽象数据类型名{ 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 }ADT 抽象数据类型名。 数据对象和数据关系的定义用伪码描述。 数据基本操作的定义格式： 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉

例1-6 抽象数据类型三元组的定义： ADT Triplet{ 数据对象：D={e1，e2,e3 |e1,e2,e3∈Elemset (定义了关系运算的某个集合)} 数据关系：R1={〈e1,e2>,<e2,e3>〉 基本操作： InitTriplet(&T,v1,v2,v3)//构造三元组T， e1,e2,e3分别被赋以参数v1,v2,v3的值 DestroyTriplet（&T）//撤消三元组T

Get（T,i,&e）//三元组T已存在，1=<i<=3 用e返回第i元的值 Put(&T,i,e) //三元组T已存在，1=<i<=3 将T的第i元值变为e IsAscending(T)//三元组T已存在，1=<i<=3 三元素若升序排列返回1，否则返回0 IsDescending(T) Max(T,&e) Min(T,&e) }ADT Triplet

多形数据类型：是其值的成分不确定的数据类型。 如例1-6中定义的抽象数据类型Triplet，其元素e1,e2,e3可以是整数或字符串，也可以是由多种成分构成。

1.3 抽象数据类型的表示与实现 抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。

1．类C语言P10-11 精选了C 的一个子集，扩充修改，增强了语言的描述功能。 预定义常量和类型 数据结构的表示：存储结构用类型（typedef）定义来 描述。 数据元素类型约定为ElemType. 基本操作的算法用函数描述：

函数类型 函数名（函数参数表）{//算法说明 语句序列 }//函数名 增加了引用调用的参数传递方式。 赋值语句、选择语句(if else,switch)、循环语句(for,while,do while)、结束语句、输入输出语句(scanf,printf)、注释语句 基本函数 逻辑运算约定: && ||

例1-7 Triplet的表示和实现 //--采用动态分配的顺序存储结构 Typedef ElemType *Triplet;//由InitTriplet分配三个元素存储空间 //--基本操作的函数原型说明 Status InitTriplet(Triplet &T,ElemType v1, ElemType v2, ElemType v3) Status DestroyTriplet（&T） Status Get（T,i,&e）

Status Put(&T,i,e) Status IsAscending(T) Status IsDescending(T) Status Max(T,&e) Status Min(T,&e) //--基本操作的实现 Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3){ //构造三元组T，依次置T的三个元素的处值为v1,v2和v3。

T=(ElemType*)malloc(3*sizeof(ElemType)); //分配三个元素的存储空间 If(!T)exit(OVERFLOW);//分配存储空间失败 T[0]=v1; T[1]=v2; T[2]=v3; return OK; }//InitTriplet Status DestroyTriplet（Triplet &T）{//销毁T free(T); T=NULL; return OK; }//DestroyTriplet

Status Get（Triplet T,int i,ElemType &e）{ //1=<i=<3,用e返回T的第i元的值 if (i<1 || i>3) return ERROR; e=T[i-1]; return OK; }//Get

Status Put（Triplet T,int i,ElemType &e）{ //1=<i=<3,用e返回T的第i元的值 if (i<1 || i>3) return ERROR; T[i-1]=e; return OK; }//Put

Status Max（Triplet T,ElemType &e）{ e=(T[0]>=T[1])?((T[0]<=T[2])?T[0]:T[2]) :((T[1]>=T[2])?T[1]:T[2]); return OK; }//Max

1.4 算法和算法分析 1．算法（Algorithm） 是对特定问题求解步骤的一种描述，它是指令的有限序列。 算法的重要特性： 有穷性——算法必须在执行有限步骤后结束 确定性——算法的每一步必须是确切定义的，不能产生二义性 可行性——算法是能实现的 输 入——一个算法有零个或多个输入 输 出——一个算法有一个或多个输出

1.4 算法和算法分析 2．算法设计的要求——衡量算法优劣的标准 正确性 可读性 健壮性 效率与低存储量要求

1.4 算法和算法分析 3．算法效率的度量 算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量。（算法时间是由控制结构和原操作的决定的） 记号——引用了“O”。“O”表示一个 数量级的概念。 本书中根据算法中语句执行的最大次数（频度）来 估算一个算法执行时间的数量级。 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f（n）， T（n）=O（f（n）） 它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。 语句的频度：是该语句重复执行的次数。

例：求两个n阶方阵的乘积C=A×B #define n 100 void MatrixMultiply(int A[n][n],int B[n][n],int C[n][n]) { int i,j,k for (i=1;i<=n;++i) //n+1 for (j=1;j<=n;++j) // n*(n+1) { C[i][j]=0; //n2 for (k=1;k<=n,k++) n2(n+1) C[i][j]=C[i][j]+a[i][k]*b[k][j]; //n3 } T(n)=n+1+n*(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1 量级：T(n)=O(n3)

例： （a）{++x;s=0;} （b）for (i=1;i<=n;++i) {++x;s+=x;} （c）for (j=1;j<=n;++j) for (k=1;k<=n;k++){++x;s+=x;} 含基本操作“x增1”的语句的频度分别为1,n和n2 时间复杂度是O(1)、O(n)和O(n2)。 时间复杂度有时与输入有关。

4．算法的存储空间需求 亦可如上作类似分析。 空间复杂度：S（n）=O（f（n））（略）

小结 主要介绍了数据结构的基本概念，分类，算法分析评价。

课后习题 1. 简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 2. 在程序设计中，常用下列三种不同的出错处理方式： 　(1) 用exit语句终止执行并报告错误； 　(2) 以函数的返回值区别正确返回或错误返回； 　(3) 设置一个整型变量的函数参数以区别正确返回或某种错误返回。 　　试讨论这三种方法各自的优缺点，并编写算法，计算 i!×2i 的值并存入数组 a[0..arrsize-1] 的第 i-1 个分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为 maxint，则当 n>arrsize 或对某个 k(1≤k≤n) 使 k!×2k>maxint 时，应按出错处理。注意选择你认为较好的出错处理方法。

课后习题 3.在程序设计中，可采用下列三种方法实现输出和输入： 　(1) 通过 scanf 和 printf 语句； 　(2) 通过函数的参数显式传递； 　(3) 通过全局变量隐式传递。 　　试讨论这三种方法的优缺点，并编写算法求一元多项式 的值，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法，本题的输入为ai(i=0,1,…,n)，x0和n，输出为Pn(x0)。

课后习题 4. 设 n 为正整数。试确定下列各程序段中前置以记号 @ 的语句的频度： 　(1) i=1; k=0; 　　　while ( i<=n-1) { 　　　　@ k += 10 * i; 　　　　　 i++; 　　　} 　(2) i=1; k=0; 　　　do { 　　　　@ k +=10 * i; 　　　　　 i++; 　　　} while(i<=n-1);

课后习题 (3) i = 1; k = 0; 　　　while (i<=n-1) { 　　　　　　i++ ; 　　　　 @ k+= 10 * i; 　　　} (4) k=0; 　　　for( i=1; i<=n; i++) { 　　　　for (j=i ; j<=n; j++) 　　　　 @ k++; 　　　} (5) for( i=1; i<=n; i++) { 　　　　for (j=1; j<=i; j++) { 　　　　　for (k=1; k<=j; k++) 　　　　　 @ x += delta; 　　　　} 　　　}

课后习题 (7) x=n; y=0; // n 是不小于1的常数 while (x>=(y+1)*(y+1)) { @ y++; } (6) i=1; j=0; 　　　while (i+j<=n) { 　　　　@ if (i>j ) j++ ; 　　　　　 else i++ ; 　　　} 　(7) x=n; y=0; // n 是不小于1的常数 　　　while (x>=(y+1)*(y+1)) { 　　　@ y++; 　　　} 　(8) x=91; y=100; 　　　while (y>0 ) { 　　　@ if (x>100 ) { x -= 10; y- -; } 　　　　 else x++; 　　　}