第一章数据结构基本概念
1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。
2、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。
由于目前关于这个问题有许多说法，我们采用了一种最流行的说法，即coad与yourdon 给出的定义：面向对象 = 对象 + 类 + 继承 + 通信。
要点： 抽象数据类型的封装性
面向对象系统结构的稳定性
面向对象方法着眼点在于应用问题所涉及的对象
3、数据结构的抽象层次：理解用对象类表示的各种数据结构
4、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。
要点：·算法与程序的不同之处需要从算法的特性来解释
算法的正确性是最主要的要求
算法的可读性是必须考虑的
程序的程序步数的计算与算法的事前估计
程序的时间代价是指算法的渐进时间复杂性度量。
1.1 什么是数据结构。
1.1.1 计算机解决问题的步骤。
实际问题---数据模型---算法---程序---结果。
工程师数学家程序员。
1.1.2 计算机的用途。
1.1.2.1 科学计算（数值运算）：解方程（组），函数求值，概率统计等。
1.1.2.2 非数值运算：字符，**，图像，声音等。
1.1.3 计算机的用途——数值运算。
1.1.3.1 水库大坝的应力计算。
1.1.3.2 预报人口增长。
1.1.3.3 天气预报。
1.1.4 数据结构的定义。
1.1.4.1 描述非数值计算问题的模型是——
1.1.4.2 如表、树、图之类的数据结构。
1.1.5 数据结构是——
研究计算机的操作对象（数据）以及它们之间的关系和操作等的学科。
1.2 基本概念和术语。
1.2.1 数据：计算机程序处理的符号的总称。
1.2.2 数据元素：数据的基本单位。
通常作为一个整体进行处理。
1.2.3 数据项：数据的不可分割的最小单位。
1.2.3.1 一个数据元素可以由若干个数据项构成。
1.2.4 数据对象：性质相同的数据元素的集合。
1.2.5 数据结构：相互间存在一种或多种关系的数据元素的集合。
数据结构的数学定义。
数据结构是一个二元组。
data_structure=(d,s)
d—数据元素的有限集合。
s—定义在d上得关系的有限集合。
例如。complex=(c,r)c=r=
逻辑结构和物理结构。
逻辑结构：数据元素之间的逻辑关系。
物理结构：数据结构在计算机中的表示，又称存储结构。
算法的设计取决于选定的逻辑结构。
算法的事先依赖于采用的存储结构。
数据类型与抽象的数据类型。
数据类型(data type)：
值的集合以及定义在这个集合上打的一组操作。
例如：c语言中的整数类型。
抽象数据类型(adt)
数学模型以及定义在该模型上的一组操作。
与其在计算机中的表示和实现无关。
adt可用三元组表示：(d,s,p)
d—数据对象； s—d上的关系； p—对d的基本操作集。
抽象数据类型三元组的定义。
adt triplet
数据关系：r1=
基本操作：—inittriplet(&t,v1,v2,v3)
—初始条件：
—操作结果：构造三元组t，元素e1,e2和e3分别被赋予参数v1，v2和v3的值。
抽象数据类型三元组的定义(2)
—destroytriplet(&t)
—初始条件：三元组t已经存在。
—操作结果：销毁三元组t
—get(t,i,&e)
—初始条件：三元组t已经存在，1<=i<=3。
—操作结果：用e返回三元组t的第i个元素。
—put(&t,i,e)
—初始条件：三元组t已经存在，1<=i<=3。
—操作结果：用e值取代三元组t的第i个元素。
抽象数据类型三元组的定义(3)
—isascending(t)
—初始条件：三元组t已经存在。
—操作结果：如果三元组t的三个元素按升序排列，则返回ture；否则返回false。
—isdescending(t)
—初始条件：三元组t已经存在。
—操作结果：如果三元组t的三个元素按降序排列，则返回ture；否则返回false。
1.3 抽象数据类型的表示与实现。
类c语言（作了扩充和修改）的表示。
如：预定义常量和类型。
#define true 1
#define false 0
#define ok 1
#define error 0
#define infeasible -1
#define overflow -2
typedef int status
三元组基本操作实现——举例。
status get(triple t,int i, elemtype &e)
/初始条件：三元组t已经存在，1<=i<=3。
/操作结果：用e返回三元组t的第i个元素。
if(i<1||i>3)return error;
e=t[i-1];
return ok;
1.4 算法和算法的分析，1.4.1算法。
算法（algorithm）：对特定问题求解步骤的一种描述。
算法的五个重要特性：
1． 有穷性。
2． 确定性。
3． 可行性。
4． 输入。
5． 输出。
算法举例——气泡排序算法。
初始条件：n个待排序的数a[0]-a[n-1]
结果：排序后a[0]-a[n-1]从小到大排列。
1) 置标记change=true;
2) i从n-1直到i=2做（3）-（6）步。
3) change=false；
4) j从0直到j=i-1做(5)
5) 若a[j]>a[j+1]则交换他们并置change=true
6) 若change=false则结束。
7) 算法结束。
冒泡排序算法（1）
1） i从n-1直到i=2做（2）-（3）步。
2） j从0直到j=i-1做（3）
3） 若a[j]>a[j+1]则交换他们。
4） 算法结束。
void bb_sort(int a,int n)
//bb_sort
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...