数据结构(C语言版)第1章

发布时间：2024-08-29

数据结构(C语言版)计算机教学PPT,教材作者：Ellis Horowitz Sartaj Sahni Susan Anderson-Freed,机械工业出版社风格不同于清华大学严蔚敏教材,作者论证严密,算法独特,注重引导创新思维!

数据结构( 语言版) 数据结构(C语言版)2011-2012学年第 2011-2012学年第1学期学年第1 Ellis Horowitz Sartaj Sahni Susan Anderson-Freed

机械工业出版社

授课班级：授课班级：计算机科学技术

2012-2-19

本书目录第 1章：第 2章：第 3章：第 4章：第 5章：基本概念数组结构栈和队列线性表树第 6章：图第7章：排序第8章：散列第9章：堆结构 10章第10章：查找结构

2012-2-19

第1章基本概念本章主题：本章主题：数据结构的基本概念和术语教学重点：熟悉数据结构常用术语，掌握基本概念，了解算法教学重点：熟悉数据结构常用术语，掌握基本概念，了解算法时间复杂度和空间复杂度的分析与评价教学难点：教学难点：算法性能分析主要内容：主要内容： 1.1 系统生命周期 1.2 1.3 1.4 1.42012-2-19

算法描述数据抽象算法性能分析与评价3

教学引入：教学引入：数据结构概念补充数据结构是一门研究非数值计算数据结构是一门研究非数值计算的程序设计问题中计算机的操作非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科.主要有三个方面的内容：对象以及它们之间的关系和操作的学科.主要有三个方面的内容：数据的逻辑结构、数据的存储结构和对数据的算法。数据的逻辑结构、数据的存储结构和对数据的算法。逻辑结构：数据间的逻辑关系，有集合、线性表、树、图等四种逻辑关系，集合、线性表、逻辑结构：数据间的逻辑关系结构。结构。物理结构：数据在计算机内部的存储安排，是数据结构在计算机存储安排，物理结构：数据在计算机内部的存储安排中的实现方法。主要有顺序、链接、散列、索引等四种基本存储结构，中的实现方法。主要有顺序链接、散列、索引等四种基本存储结构，顺序、等四种基本存储结构并可以根据需要组合成其它更复杂的结构。并可以根据需要组合成其它更复杂的结构。算法：数据进行处理的方法。算法：数据进行处理的方法。2012-2-19 4

数据结构示例:在表中会按登录号形成一种次序关系，数据结构示例:在表中会按登录号形成一种次序关系，即整个二维表就是图书数据的一个线性序列。这种关系被称为线性结构就是图书数据的一个线性序列。这种关系被称为线性结构。线性结构。

表 1-1 图书目录表登录号 1 2 3 4 5 6 7 …2012-2-19

书号

书名

作者

出版社

定价 22 17.3 29 25

ISBN 7-302-02368-9 / TP. 1185 数据结构 ISBN 7-302-00860-4 / TP. 312 C 程序设计 ISBN 7-5053-9279-4 / TP. 311 数据结构 ISBN 7-5053-8168-7 / TP. 4757 计算机系统原理 ISBN 7-5609-2351-8

/ TP. 316 操作系统原理 ISBN 7-304-01404-0 / TP. 68

严蔚敏清华大学谭浩强清华大学徐孝凯电子工业张基温电子工业

庞丽萍华中科技大学 22.8 23.3 20 …

数据库基础与应用王利中央电大

ISBN 7-5084-1648-1 / TP. 706 网页制作实例教程齐建玲中国水利水电 …

…

返回5

【例1-2】磁盘目录结构和文件管理系统root bin math ds sw lib user zhao jiang shao li etc描述磁盘目录和文件结构时，描述磁盘目录和文件结构时，假设每个磁盘包括一个根目录 root)和若干个一级子目录， (root)和若干个一级子目录，每个一级子目录中又包含若干个二级子目录… 子目录…. 这种关系很像自然界中的树，这种关系很像自然界中的树，所以称为目录树。如左图所示。所以称为目录树。如左图所示。

queue stack tree graph

在这种结构中，目录和目录以及目录和文件之间呈现出一对多的非在这种结构中，线性关系。即根root有多个下属(也称为后代),每一后代又有属于自己有多个下属( ),每一后代又有属于自己线性关系。即根root有多个下属也称为后代), 的后代；而任一个子目录或文件都只有一个唯一的上级(也称为双亲)。的后代；而任一个子目录或文件都只有一个唯一的上级(也称为双亲)。称这种数学模型为树型数据结构树型数据结构。称这种数学模型为树型数据结构。2012-2-19 6

【例1-3】教学计划编排问题课编程号 C1 C2 C3 C4 C5 C6 C7 C8 C9 课名称程计算机论导数据结构汇编语言 C 程序计设计算机形图学接口技术数据库理原编译原理操作系统先课修程无 C1, C4 C1 C1 C2, C3, C4 C3 C2, C9 C4 C2 C8 C7 C1 C1 C2 C4 C9 C3 C6 C5

一个教学计划中包含许多课程。在课程之间，一个教学计划中包含许多课程。在课程之间，有些必须按规定的先后次序排课， C6课程必须先学C3课课程必须先学C3 C3课程必须先学C1课课程必须先学C1 先后次序排课，如：学C6课程必须先学C3课，学C3课程必须先学C1课。这些课程之间存在先修和后续的关系。在这种结构中，这些课程之间存在先修和后续的关系。在这种结构中，表示课程的数据之间呈现多对多的非线性关系，称这类数学模型为图形结构多对多的非线性关系图形结构。之间呈现多对多的非线性关系，称这类数学模型为图形结构。

2012-2-19

四类数据基本结构的示意图：四类数据基本结构的示意图：

(a)集合结构 a)集合结构

(b)线性结构 b)线性结构

(c)树型结构 c)树型结构

(d)图形结构 d)图形结构

由以上例子可见，描述这类非数值计算问题的数学模型由以上例子可见，和方法不再是数学方

程，而是诸如线性表、和方法不再是数学方程，而是诸如线性表、树和图之类的数据结构。据结构。

2012-2-19

基本概念和术语 1.1 综述：系统生命周期综述：准备知识：准备知识：结构化程序设计 C语言考查学习目的：掌握设计大规模复杂系统的工具技术-学习目的：掌握设计大规模复杂系统的工具技术-- 数据抽算法描述、象，算法描述、性能分析 1. 2. 3. 4. 5. 需求：已知条件(输入、应该产生结果(输出) 需求：已知条件(输入、应该产生结果(输出) 分析：分解为子问题分析：分解为子问题-自顶向上和自顶向下设计：分析阶段的延续，设计：分析阶段的延续，逐步求精和编码：逐步求精和编码：数据对象的存储方法验证：输入数据测试、验证：输入数据测试、排错

2012-2-19

1.2 算法描述1.2.1 算法(Algorithm) 算法(Algorithm) 1、算法：是一组完成特定任务的有穷指令序列。算法：是一组完成特定任务的有穷指令序列。 2、特点：特点：1)输入：具有0个或多个由外界提供的量(输入) 1)输入：具有0个或多个由外界提供的量(输入)。输入 2)输出：产生1个或多个结果。 2)输出：产生1个或多个结果。输出 3)确定性：算法中的每条指令都必须是清楚的，指令无二义性。 3)确定性：算法中的每条指令都必须是清楚的，指令无二义性。确定性 4)动态有穷：当执行一个算法时，不论是何种情况， 4)动态有穷：当执行一个算法时，不论是何种情况，在经过了有限步动态有穷骤后，这个算法一定要终止。骤后，这个算法一定要终止。 5)可行性：每条指令都充分基本， 5)可行性：每条指令都充分基本，即：序列中的每个操作都是可以简可行性单完成的，都可以通过已经实现的基本操作运算的有限次来实现。单完成的，都可以通过已经实现的基本操作运算的有限次来实现。

2012-2-19

1.2.2 算法描述一个算法可用自然语言、数字语言或流程图等来描述，一个算法可用自然语言、数字语言或流程图等来描述，也可以用计算机高级程序语言来描述， Pascal语言计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等，本书语言、语言或伪代码伪代码等选用C语言作为描述算法的工具。选用C语言作为描述算法的工具。 1.用自然语言描述算法优点：简单，便于人们对算法的阅读。缺点：不够严谨。优点：简单，便于人们对算法的阅读。缺点：不够严谨。 2.用流程图描述算法特点简洁、明了。目前在一些高级语言程序设计中仍然被采用。特点简洁、明了。目前在一些高级语言程序设计中仍然被采用。 3.用程序设计(C或C++)

语言描述算法用程序设计( C++) 不太容易且不直观，且需要借助于注释才能看明白。不太容易且不直观，且需要借助于注释才能看明白。一般采用伪代码来描述算法。为解决理解与执行的矛盾一般采用伪代码来描述算法。为解决理解与执行的矛盾一般采用伪代码来描述算法2012-2-19 11

选择排序]把个整数排序其中n≥1,给出方案？个整数排序，例1[选择排序把n个整数排序，其中选择排序，给出方案？给出算法与程序：P4 自然语言：自然语言：从未被排序的整数中找出最小的整数，将其放在已排序整数列中的下一个位置。伪代码：伪代码： for(i=0;i<n;i++){ Examine list[i] to list[n-1] and suppose that the smallest integer is at list[min]; interchange list[i] and list[min]; }

2012-2-19

#include<stdio.h> #include<math.h> 程序1- : 程序 -1:选择排序 #define MAX_SIZE 101 #define swap(x,y,t)((t)=(x),(x)=(y),(y)=(t)) void sort(int list[],int n) void swap(int *x,*y,int temp) void main( ) { temp=*x; {int i,n; *x=*y; int list[MAX_SIZE]; *y=temp; printf("Enter the number to generate:"); } scanf("%d",&n); if(n<1||n>MAX_SIZE) printf("Improper value of n\n"); void sort(int list[],int n) for(i=0;i<n;i++) { int i,j,min,temp; {list[i]=rand()%1000; for(i=0;i<n-1;i++){ printf("%d ",list[i]); min=i; } for(j=i+1;j<n;j++) sort(list,n); if(list[j]<list[min]) min=j; printf("\n Sorted array:\n"); swap(list[i],list[min],temp); } for(i=0;i<n;i++) printf("%d ",list[i]); } printf("\n"); }2012-2-19 13

例1-2[折半查找]假定有n个不同的整数n≥1,且它们已经排 2[折半查找]假定有n个不同的整数n≥1,且它们已经排序并存放在数据list中。即list[0]≤list[1]≤…≤list[n-1].要求序并存放在数据list中。即list[0]≤list[1]≤…≤list[n-1].要求判定某个整数是否在数组中，如果在数据中，返回下标i ,使判定某个整数是否在数组中，如果在数据中，返回下标i ,使得list[i]=searchnum 。如果不在，则返回-1。。如果不在，则返回给出算法描述(伪代码): 给出算法描述(伪代码): while (there are mor integers to check){ middle=(left+right)/2; if(searchnum<list[middle]) right=middleright=middle-1; else if(searchnum==list[middle] return middle; else left=middle+1; }2012-2-19 14

1.2.2 递归算法函数可以调用其自身或其他函数，不仅用于类似计算阶乘算法，任何函数可以调用其自身或其他函数，不仅用于类似计算阶乘算法，赋值语句、if-else、 while结构语句都可以使用例如：结构语句都可以使用。赋值语句、if-else、 while结构语句都可以使用。例如：二项式公式 3[折半查找的递归构造：折半查找] 例1-3[折半查找]的递归构造：构造递归调用终止的边界条件实现递归调用，每次调用向最终解逼近一步,给出

算法与程序：实现递归调用，每次调用向最终解逼近一步,给出算法与程序： int binsearch(int list[], int searchnum, int left, int right) { int middle; if (left<=right) { middle=(left+right)/2; switch(compare(list[middle],searchnum)) { case -1: return binsearch(list,searchnum,middle+1,right); case 0: return middle; case 1: return binsearch(list,searchnum,left,middle-1); } binsearch(list,searchnum,left,middle} }2012-2-19 15

1.3 数据抽象定义1 定义1:数据类型 data type struct student{ char last_name; int student_id; char grade; } 定义2 定义2:抽象数据型 ADT (1)生成器/ (1)生成器/构造器 (2)转换器 (2)转换器 (3)观察器 (3)观察器

2012-2-19

数据结构(C语言版)第1章.doc 将本文的Word文档下载到电脑

下载这篇word文档

上一篇：税法练习题(判断、单选、多选)

下一篇：Server2008微软官方教程 8 Windows Server 2008 安装和部署