绪论

算法+数据结构=程序

程序设计语言 识字

数据结构 写小作文

算法设计与分析 写大文章

第一章

数据：

对信息的符号表示

数据和计算机没有必然的联系

数据元素

能描述完整信息的数据的基本单位(DataFrame中的一列)

数据项：

最小单位，例如学号，姓名

数据对象：

相同性质的若干个数据元素的集合

一个班所有的学号(DataFrame中的行)

数据元素之间存在关系，则称为数据结构

分析 设计 编码实现

逻辑结构(与计算机无关) 相对于物理结构(存储结构)

1.表格

2.二元组

B = (D,R)

<x,y> 固定前后顺序

3.图形

逻辑结构类型

1.集合

2.线性结构

3.树形结构

4.图结构

存储结构

关系

1.顺序映象

存储位置的相邻表示逻辑的相邻

2.链式映象

以附加信息(指针)表示后继关系

3.数据类型

Fortran和C的二维数组行和列存储的时候是反的

4.抽象数据类型

抽象数据类型 = 逻辑结构 + 抽象运算

过程

问题描述

设计存储结构

算法设计

算法分析

编码实现

算法

为了解决某类问题而规定的一个有限长的操作序列

五个重要特性

有穷性

确定性

可行性

有输入

有输出

原则

正确性

可读性

健壮性

高效率低存储量

时间

如何表示算法运行时间

不用绝对时间

对于特定输入，算法基本操作的执行次数

独立于具体的机器

算法执行时间的增长率和f(n)的增长率相同

T(n) = O(f(n))

最坏情况运行时间更有意义

增长的量级

只考虑最高次项

冒泡

n(n-1)/2

空间

S(n) = O(g(n))

原地工作

额外空间相对于输入数据量来说是个常量

比如冒泡 复杂度是1

第二章 线性表

线性表是一个具有相同特性的数据元素的有限序列

ADT

引用型操作

加工型操作

顺序存储

以存储位置相邻表示逻辑相邻

所有数据元素的存储位置均取决于第一个数据元素的存储位置

typedef struct{

​ ElemType *elem; 指向0号地址

​ int length;

​ int listsize;

}SqList;

单链表

头指针–>头节点–>a1……an->空

Typedef struct LNode{

​ ElemType data;

​ struct LNode * next

}LinkList;

顺序存取

双链表

多了个指向前一个的指针

Typedef struct DuLNode{

​ ElemType data;

​ struct LNode * prior;

​ struct LNode * next;

}DuLinkList;

循环链表

连表是一种动态分配空间的存储结构，能更有效地利用存储空间

插入或删除元素时不需要移动元素

由于链表是”顺序存取“随机存取元素和在表尾插入等操作带来不便

第三章 栈和队列

操作只能搞尾部