1.数据结构
相互之间存在一种或多种特定关系的数据元素的集合。
数据与数据的关系
逻辑结构
- 集合：所有数据在同一个集合中，关系平等。
- 线性：数据和数据之间是一对一的关系
- 树： 一对多
- 图：多对多
物理结构
在内存当中的存储关系
- 顺序存储：数据存放在连续的存储单位中，逻辑关系和物理关系一致。
- 链式存储：数据存放的存储单位是随机或任意的，可以连续也可以不连续。
算法
是解决特定问题求解步骤的描述，计算机中表现为指令的有限序列，每条指令表示一个或多个操作。
算法的特征
算法的设计
时间复杂度
算法的时间复杂度也就是执行这个算法所花时间的度量 n1 = O(n) O(1)。
推导时间复杂度：
O(1)<O(logn)<O(N)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
2. 线性表
顺序表
零个或多个数据元素的有限序列元素之间是有顺序的。如果存在多个元素，第一个元素无前驱，最有一个没有后继，其他的元素只有一个前驱和一个后继。
当线性表元素的个数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);
线性表顺序存储的优点和缺点：
- 优点
- 缺点
单向链表
解决顺序存储的缺点，插入和删除，动态存储问题。
动态存储：程序运行起来后，决定链表的容量。内存的使用率，比较高。
线性表链式存储结构的特点是一组任意的存储单位存储线性表的数据元素，存储单元可以是连续的，也可以不连续。可以被存储在任意内存未被占用的位置上。
所以前面的顺序表只需要存储数据元素信息就可以了。在链式结构中还需要一个元素存储下一个元素的地址。
为了表示每个数据元素，ai与其直接后继数据元素ai+1之间的逻辑关系，对ai来说，除了存储其本身的信息外，还需要存一个指示器直接后续的信息。把存储元素信息的域叫数据域，把存储直接后继位置的域叫指针域。这两部分信息组成数据元素ai的存储映像，叫结点(Node)。
typedef struct person {
char name[32];
char sex;
int age;
int score;
}DATATYPE;
typedef struct node {
DATATYPE data;
struct node *next;
}LinkNode;
typedef struct list {
LinkNode *head;
int tlen;
int clen;
}LinkList;
LinkList *CreateLinkList(int len);
int InsertHeadLinkList(LinkList *list, DATATYPE *data);
int InsertTailLinkList(LinkList *list, DATATYPE* data);
int ShowLinkList(LinkList *list);
LinkNode *FindLinkList(LinkList *list, char *name);
int DeleteLinkList(LinkList *list, char *name);
int ModifyLinkList(LinkList *list, char *name, DATATYPE* data);
int DestroyLinkList(LinkList *list)；
