目录
数据结构
逻辑结构
物理结构（在内存当中的存储关系）
数据的类型，ADT（abstruct datatype）
算法
算法的特征
算法的设计
算法时间复杂度
推导时间复杂度
线性表
线性表顺序存储的优点缺点
优点
缺点
内存泄漏工具
数据结构
相互之间存在一种或多种特定关系的数据元素的集合
逻辑结构
集合，所有数据在同一个集合中，关系平等
线性，数据和数据是一对一的关系
树，一对多
图，多对多
物理结构（在内存当中的存储关系）
顺序存储（顺序表），数据存放在连续的存储单元中。逻辑关系与物理关系一致
链式存储（链表），数据存放的存储单位是随机或任意的，可以连续也可以不连续，由于是malloc申请，一般来说不一定连续
struct Per 数据元素
{
char name; // 数据项
int age;
char phone;
}
struct Per list[100]; // 数据对象
数据的类型，ADT（abstruct datatype）
是指一组性质相同的值的集合及定义在此集合上的一些操作的总称
原子类型：int char float
结构类型：struct union
抽象数据类型（ADT），数据模型+操作
程序=数据+算法
算法
是解决特定问题求解步骤的描述，计算机中表现为有指令的有限序列，每条指令表示一个或多个操作。
算法的特征
算法的设计
1、正确性
- 语法正确
- 合法的输入能得到合理的结果
- 对非法的输入，给出满足要求的规格说明
- 对精心选择、甚至刁难的测试都能正常运行
2、可读性
- 便于交流阅读理解
3、健壮性
- 输入非法数据，能进行相应的处理，而不是产生异常
4、高效，存储低，效率高
算法时间复杂度
也就是执行这个算法所花时间的度量
时间复杂度 O (・) 描述的是算法执行时间随输入规模 n 增长的趋势，忽略常数项、低次项和系数，只保留主导增长的项，比如3n+5的时间复杂度是 O (n)，n²+2nlogn是 O (n²)。
2n+3, o(N) 3n+1; o(N) 4n+8 ,2n^2 +10; o(n^2) 2n^2+3n+1, 2n^3+3n+1; 2n^2,3n+1,2n^2+3n+1;
推导时间复杂度
- 用常数1 取代运行时间中的所有加法常数
- 在修改后的运行函数中，只保留最高阶项。
- 如果最高阶存在且不是1，则取除这个项相乘的常数。
O(1)<O(logn)<O(N)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
线性表
一对一的关系
零个或多个数据元素的有限序列
元素之间是有顺序了。如果存在多个元素，第一个元素无前驱，最有一个没有后继，其他的元素只有 一个前驱和一个后继。 当线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，为空表。在非空的表中每个元素都 有一个确定的位置，如果a1是第一个元素，那么an就是第n个元素。
ADT 抽象数据类型 typedef struct person { char name[32]; char sex; int age; int score; }DATATYPE; 通用数据类型 typedef int DATATYPE; typedef struct list { DATATYPE *head; int tlen; int clen; }SeqList; SeqList *CreateSeqList(int len); int DestroySeqList(SeqList *list); int ShowSeqList(SeqList *list); int InsertTailSeqList(SeqList *list, DATATYPE data); int IsFullSeqList(SeqList *list); int IsEmptySeqList(SeqList *list); int InsertPosSeqList(SeqList *list, DATATYPE data, int pos); int FindSeqList(SeqList *list, char *name); int ModifySeqList(SeqList *list, char *old, DATATYPE new); int DeleteSeqList(SeqList *list, char *name); int ClearSeqList(SeqList *list);
线性表顺序存储的优点缺点
优点
1.无需为表中的逻辑关系增加额外的存储空间
2、可以快速随机访问元素o(1)
缺点
1、插入，删除元素需要移动元素o(n)
2、无法动态存储
内存泄漏工具
valgrind ./a.out
