数据结构
数据元素的集合+数据之间的相互关系
1)逻辑结构
数据之间的相互关系
线性结构：线性表、队列、栈
非线性结构：树、图
2)存储结构（又称物理结构）
元素和元素之间关系在计算机的存储形式
线性表
n个元素组成的有限序列。n为线性表的长度，长度0为空表。
非空线性表的线性结构有以下特点：
存在唯一一个被称为“第一个”、“最后一个”的数据元素。
第一个元素 前驱 后继 最后一个元素
线性表的存储结构
顺序存储、链接存储
1）顺序存储 通常用一个数组来实现，依次有序存储。线性表第i个结点是数组的第i个结点。
2）链接存储：有表头指针head
一个数据元素用结点存储。结点=数据域+指针域
数据域存放数据，指针域指向直接后继
代码编写时候：插入新结点，注意先赋值新结点的指针域到下一结点的数据域
栈
只允许在同一段插入和删除操作的线性表
先进后出
允许插入和删除的一端称为栈顶，另一端称为栈底
初始情况下top= -1
队列
只允许在一端插入元素--队尾rear
而在另一端删除元素的线性表-队头front
先进先出
循环队列
将顺序队列假想成一个环形，称为循环队列
队空：rear = front
队满：rear =（rear+1)%m
数组
n维数组是一种“同构”的数据结构
同构：类型相同，结构一致
二维数组
二维数组的存储结构：
二维数组地址计算
行存储：计算loc[i][j]的地址 = (n*i+j)*b
n：每行有n个元素
j : i 这一行前面的个数（j个）
b: i前面每个元素占用的存储单元
列存储：同理
稀疏矩阵
非零元素个数小于 零元素个数并且分布没有规律
稀疏矩阵存储方式：
1）三元组存储 （行，列，元素本身数据）-->(0，0，5) 零行零列 5
2）十字链表存储
矩阵的压缩存储其实是将数组的存储和稀疏矩阵结合起来考察
字符串
有限字符序列
空串：不包含任何字符 “”
空格串：由一个或多个空格组成的串
字符串的比较
从第一个字符开始比较，比较ASCII码，依次比较
越靠后的ASCII码越大
小写字母ASCII码比大写字母ASCII码大
