《数据结构C语言版》----第01章

《数据结构C语言版》----第01章

数据结构 使用C语言(第4版)朱战立 电子工业出版社 2009.1.

《数据结构C语言版》----第01章

第1章 绪论数据结构的基本概念

主 要 知 识 点

抽象数据类型和软件构造 方法

算法和算法的时间复杂度

《数据结构C语言版》----第01章

1.1 数据结构的基本概念基本术语(1)数据：人们利用文字符号、数字符号以及其他规定的符号 对现实世界的事物及其活动所做的抽象描述。 (2)数据元素：表示一个事物的一组数据。 (3)数据项：构成数据元素的数据。 例如，学生信息可包括学生的学号、姓名、性别、年龄等 数据。这些数据构成学生情况的描述的数据项；包括学号、 姓名、性别、年龄等数据项的一组数据就构成学生信息的 一个数据元素。

《数据结构C语言版》----第01章

学生信息数据元素的C语言表示方法是：

struct Student{ long number; char name[10]; char sex[3];

int age;};

《数据结构C语言版》----第01章

基本术语(4)抽象数据元素：没有实际含义的数据元素。 (5)抽象数据元素的类型：没有确切定义的数据类型。 (6)数据的逻辑结构：数据元素之间的相互联系方式。 (7)数据的存储结构：数据元素在计算机中的存储方式。 (8)数据的操作：对一种数据类型的数据进行的某种处理。 (9)数据的操作集合：对一种数据类型的数据进行的所有操 作。

《数据结构C语言版》----第01章

数 据 的 逻 辑 结 构

线性结构：除第一个和最后一个数据元素外，每个 数据元素只有一个前驱和一个后继数据元素。 树结构：除根结点外，每个数据元素只有一个前驱 数据元素，可有0个或若干个后继数据元素。 图结构：每个数据元素可有0个或若干个前驱数据 元素和0个或若干个后继数据元素。

《数据结构C语言版》----第01章

线性结构

树结构

图结构

《数据结构C语言版》----第01章

数 据 的 存 储 结 构

顺序存储结构：把数据元素存储在一块连续地址空 间的内存中，其特点是逻辑上相邻的数据元素在物 理上也相邻，数据间的逻辑关系表现在数据元素存 储位置关系上。 指针是指向物理存储单元地址的变量。由数据元素 域和指针域组成的一个结构体称为结点。

链式存储结构：使用指针把相互直接关联的结点 (即直接前驱结点或直接后继结点)链接起来，其特 点是逻辑上相邻的数据元素在物理上不一定相邻， 数据间的逻辑关系表现在结点的链接关系上。

《数据结构C语言版》----第01章

数 据 的 操 作

从抽象角度，数据的操作主要讨论某种数据类型 数据应具备的操作的逻辑功能，抽象角度下的操 作一般和数据的逻辑结构一起讨论； 具体来说，数据的操作主要讨论操作的具体实现 算法。具体问题的操作实现必须在数据的存储结 构确定后才能进行。

数据结构课程主要讨论表、堆栈、队列、串、 数组、树、二叉树、图等典型的常用数据结构。 在讨论这些典型数据结构时，主要从它们的逻辑 结构、存储结构和数据操作三个

方面进行分析讨 论。

《数据结构C语言版》----第01章

1.2 抽象数据类型和软件构造方法类型是一组值的集合。 数据类型是指一个类型和定义在这个类型上的操作集合。

抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合。 数据类型和抽象数据类型的不同之处仅仅在于数 据类型指的是高级程序设计语言支持的基本数据类型， 而抽象数据类型指的是在基本数据类型支持下用户新 设计的数据类型。

《数据结构C语言版》----第01章

抽象数据类型使软件设计成为工业化流水线生产 的一个中间环节。一方面，根据给出的抽象数据类型的功能定义，负责设计这些抽象数据类型的专门公司设 计该抽象数据类型的具体存储结构以及在具体存储结构 下各操作的具体实现算法；另一方面，利用已设计实 现的抽象数据类型模块，负责设计应用软件的专门公司 可以安全、快速、方便的完成该应用软件系统的设计。 软件的设计采用模块化方法，抽象数据类型就是 构造大型软件的最基本模块。

《数据结构C语言版》----第01章

1.3 算法及其时间复杂度算法是描述求解问题方法的操作步骤集合。描 述 算 法 的 语 言 形 式 1.文字形式:用中文或英文这样的文字来描述算 法。 2.伪码形式:用一种仿程序设计语言的语言来描 述算法。 3.程序设计语言形式:用某种程序设计语言描述 算法。其优点是算法不用修改，直接作为程序语 句键入计算机，计算机能调用和运行。

《数据结构C语言版》----第01章

例1-1:设计一个把存储在数组中的有n个抽象数据元素a0, a1,…,an-1逆置的算法，即要求逆置后的数组中数据元素序列 为an-1 , … , a1 , a0 ,并要求原数组中的数据元素值不能被改变。void Reverse(int n, DataType a[], DataType b[]) { int i; for(i=0;i<n;i++) b[i]=a[n-1-i]; } //把数组a的元素逆置后赋给数组b

《数据结构C语言版》----第01章

例1-2:设计一个把存储在数组中的有n个抽象数据元素a0, a1,…,an-1逆置的算法，即要求逆置后的数组中数据元素序列 为an-1 , … , a1 , a0 ,并要求原数组中的数据元素值被改变。void Reverse(int n, DataType a[]) { int i,m=n/2; DataType temp; for(i=0;i<m;i++) { temp=a[i]; a[i]=a[n-1-i]; a[n-1-i]=temp; } } //进行m次调换

《数据结构C语言版》----第01章

算法满足以下性质: (1)输入性(2)输出性 (3)有限性 (4)确定性 (5)可执行性 算法设计满足以下目标: (1)正确性 (2)可读性 (3)健壮性 (4)高时间效率 (5)高空间效 率 算法时间效率的度量 算法的执行时间需通过根据该算法编制的程序在计算机上运 行时所消耗的时间来度量。方法有两种: (1)事后统计方法 (2)事前分析方法

《数据结构C语言版》----第01章

程序运行消耗时间的有关因素: (1)书写算法的程序设计语言 (2)编译产生的机器语言代码质量 (3)机器执行指令的速度 (4)问题的规模，即算法的时间效率与算法所处理的数据个 数n的函数关系。 算法的时间效率是算法所处

理的数据个数n的函数，算法 的时间效率也称作算法的时间复杂度。 定义:T(n)=O(f(n)),当且仅当存在正常数c和n0,对所有的 n(n≥ n0)满足T(n)≤c×f(n) 。