第一章 绪论.

Presentation on theme: "第一章 绪论."— Presentation transcript:

1 第一章 绪论

2 一、数据结构讨论的范畴 二、基本概念 三、算法和算法的度量

3 一、数据结构讨论的范畴 非数值计算程序设计问题 数据的逻辑结构 数据的存储结构

4 二、基本概念 1. 数据与数据结构 2. 抽象数据类型

5 1. 数据与数据结构 数据: 所有能被输入到计算机中，且能被计算机处理的符号的集合。 是计算机操作的对象的总称。
是计算机处理的信息的某种特定的符号表示形式。

6 数据元素: 是数据（集合）中的一个“个体” 是数据结构中讨论的基本单位

7 数据结构： 带结构的数据元素的集合 或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。

8 数据结构： 是研究数据的逻辑结构和物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算以后所得的新结构仍然是原来的结构类型

9 概括地说： 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。

10 数据的逻辑结构可归结为以下四类: 线性结构 树形结构 图状结构 集合结构

11 数据的存储结构 —— 逻辑结构在存储器中的映象 “数据元素”的映象 ？ “关系”的映象 ？

12 关系的映象方法： 顺序映象 用一组地址连续的存储单元 依次存储数据元素 x y

13 链式映象 以附加信息(指针)表示后继关系 需要用一个和 x 在一起的附加信息指示 y 的存储位置 y x

14 是指一个数学模型以及定义在此数学模型上的一组操作。
2. 抽象数据类型 (Abstract Data Type 简称ADT) 是指一个数学模型以及定义在此数学模型上的一组操作。

15 三、算法和算法的衡量 1.算法 2. 算法设计的原则 3. 算法效率的衡量方法和准则 4. 算法的存储空间需求

16 算法是对解决某类问题的方法的一种描述。一个算法必须满足以下五个重要特性：
1．有穷性 2．确定性 3．可行性 4．有输入 5．有输出

17 渐近时间复杂度 T (n) = O(f(n)) 随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同。

18 第二章 线性表

19 线性表的概念 ---顺序存储 ---链式存储 ---基本操作算法实现

20 顺序映象方法是： 逻辑关系相邻, 物理位置相邻. 依次存放线性表中的数据元素 基地址 用一组地址连续的存储单元
a1 a2 … ai-1 ai … an 基地址

21 线性表顺序存储结构 const int MaxSize=50; ElemType list[MaxSize];
struct List { ElemType list[MaxSize]; int size; //当前线性表长度 };

22 一、有关空表的操作   1.初始化操作 2.清空操作 3.判空操作 *当前线性表长度*

23 二、有关查找的操作 1.遍历线性表操作 2.查找具有给定值的元素 3.更新表中具有给定值的元素

24 从表头元素起依次访问每一个元素，并且每个元素只被访问一次
a1 a2 … ai-1 ai … an 基地址 最后一个 L.list[0] L.list[L.size-1]

25 三 、有关插入的操作   1.末尾添加一个元素 2. 表头插入一个元素 后移 3.插在i位置操作

26 … an a1 a2 … ai-1 ai … an a1 a2 … ai-1 ai e i位置 表的长度增1
for (int j=L.size; j<=i; j--) { L.list[j]=L.list[j-1]; } 最后的位置 L.size i位置 a1 a2 … ai-1 ai … an a1 a2 … ai-1 ai … an e 表的长度增1

27 四、有关删除的操作   1.删除表头元素操作 2.删除i位置元素操作 前移

28 改变为 <ai-1, e> 和<e, ai>
插入、删除、建立等操作 在单链表中的实现： 有序对 <ai-1, ai> 改变为 <ai-1, e> 和<e, ai> ai-1 ai-1 ai e

29 s s = new LNode; s->data = e; //生成新结点 s->next = p->next;
p->next = s; //插入 p ai-1 ai-1 ai e s

30 q = p->next; p->next = q->next; e = q->data; delete q;
ai-1 ai-1 ai ai+1

31 逆位序输入建立带头结点的单链表 一、建立一个“空表”； 二、输入数据元素an； 三、输入数据元素an-1， 建立结点并前插；
p->next = L->next; L->next = p; 四、依次类推，直至输入a1为止。

32 循环链表 a1 a2 … an 判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。
最后一个结点的指针域的指针又指回第一个结点 a a … an 判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。

33 p 双向链表 ai-1 ai-1 ai ai 插入 e s s->right = p->right; p->right = s; s->right->left = s; s->left = p;

34 删除 ai-1 ai-1 ai ai+1 p p->right = p->right->right;
p->right->left = p;

35 第三章 稀疏矩阵和广义表

36 稀疏矩阵的概念 压缩存储方法: 一、三元组顺序表 二、带行指针向量的链接存储 三、十字链表

37 一、三元组顺序表 用“三元组”表示实现矩阵转置 原矩阵 转置后矩阵

38 二、带行指针向量的链接存储 需要把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表，每个三元组结点的类型可定义为：
row col val next

39 行指针向量 vector /\ 三元组

40 三、 十字链表 cv ^ rv 1 1 3 1 4 5 ^ ^ 2 2 -1 ^ ^ 3 1 2 ^ ^

41 广义表的概念 广义表是递归定义的线性结构 广义表是多层次的线性结构

42 广义表结构的特点: 数据元素有相对次序； 2)长度为最外层包含元素个数； 3)深度为所含括弧的重数； 4)可以共享；
原子:深度为 0;空表:深度为 1; 4)可以共享； 5)可以是一个递归的表。

43 广义表的存储结构 采用头、尾指针的链表结构 tag=1 sublist next tag=0 data next 表结点: 原子结点：

44 广义表的运算 1.求广义表长度 2.求广义表的深度 递归函数 含直接或间接调用本函数语句的函数

45 1.求广义表长度的递归算法 int Lenth(GLNode* GL) { if(GL!=NULL) return 1+Lenth(GL->next); else return 0; }

46 非递归算法如下： int Lenth(GLNode* GL) { int len=0; while(GL!=NULL)
{ len++; GL=GL->next; } return len; }

47 深度=Max {子表的深度} +1 2.求广义表的深度 可以直接求解的两种简单情况为： 空表的深度 = 1 原子的深度 = 0
将广义表分解成 n 个子表，分别 (递归)求得每个子表的深度， 深度=Max {子表的深度} +1 可以直接求解的两种简单情况为： 空表的深度 = 1 原子的深度 = 0

48 …  L L L L 1 1 1 while(L!=NULL) { if(L->tag==true) {
L->sublist L->sublist L->sublist while(L!=NULL) { if(L->tag==true) { int dep=Depth(L->sublist); if(dep>max) max=dep; } L=L->next; }

49 第四章 栈和队列

50 栈的应用举例 例一、 数制转换 例二、 括号匹配的检验 表达式求值 递归

51 表达式求值 后缀式: a b  c d e /  f  +
后缀式算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。

52 如何从后缀式求值？ 先找运算符，再找操作数 设立操作数栈 如何从中缀式转换成后缀式？ 设立操作符栈

53 栈与递归 实现递归函数，必须利用“栈”。一个递归函数必定能改写为利用栈实现的非递归函数；反之，一个用栈实现的非递归函数可以改写为递归函数。
递归函数中的尾递归容易消除。

54 队列的定义 循环队列——顺序映象 链队列——链式映象

55 Q.front=(Q.front+1)%QueueMaxSize;
9 ... 求余: X %QueueMaxSize 结果在 0~ QueueMaxSize-1 之间 8 1 7 2 6 3 5 4 Q.front=(Q.front+1)%QueueMaxSize; Q.rear=(Q.rear+1)%QueueMaxSize;

56 循环队列的基本操作: 将新元素item的值插入到队尾 void Qinsert(QueueType& Q,
const ElemType& item); 从队列Q中删除队首元素并返回之 ElemType Qdelete (QueueType& Q);

57 队列的链接存储结构 struct LNode { ElemType data; LNode *next; } ;

58 链队列类型 struct LinkQueue{ LNode *front; //队头指针 LNode *rear; //队尾指针 } ; …
Q.front Q.rear a1 a2 an ∧

59 进队 ( 向链队中插入一个元素) … a1 a2 an an+1 /\ Q.rear->next=newptr;
Q.front Q.rear a1 a2 an ∧ an+1 /\ Q.rear->next=newptr; Q.rear=newptr; newptr

60 出队 ( 从链头取出一个元素) a1 a2 an p p=Q.front; Q.front=p->next; delete p;
Q.rear a1 a2 an ∧ p p=Q.front; Q.front=p->next; delete p;

61 出队的一种特殊情况 ( 只有一个结点时) a1 p=Q.front; Q.front=p->next; if Q.front=NULL
Q.rear=NULL; delete p; Q.front Q.rear a1 ∧ p