对于程序设计，先是问题描述，数据表示，设计数据结构，然后设计算法。数据结构直接关系到程序的效率（时间和空间消耗，timeandspaceoverhead)。经典的数据结构就那几种，但其组合及其细节，确是挺复杂和微妙的。

数据结构的抽象层次：

0数组

数组是固定大小的结构，可以容纳相同数据类型的项目。它可以是整数数组、浮点数数组、字符串数组或甚至是数组数组（例如二维数组）。数组已建立索引，这意味着可以进行随机访问。

1顺序表

1.1静态顺序表：结构体封装数组+元素数量，让数组具有长度信息，并可以实现数据元素访问的边界检查；

{DataTypedata;structLNode*prev;structLNode*next;}LNode,*list;

3线性表

顺序存储和逻式存储本身的存储关系即是线性关系。

类别

基本运算

逻辑结构

存储结构

优缺点

LinearList

初始化→计算表长→获取结点→查找结果→插入结点→删除结果；

一个开始和终点结点，其余的内部结点有且只有一个直接前趋结点和一个直接后趋结点；

顺序存储

LinkedList

对链表的访问只能从表头逐个寻找；

逻辑上相邻的结点在内存中并不一定相邻；

链式存储

浪费存储空间；

广义表，一个n个数据元素的序列，数据元素可以是原子数据类型，也可以是递归定义的广义表。

templatetypenameTstructGLNode{//广义表节点inttag;//公共部分，用于区分结点类型，0表示原子，1表示子表union{Tdata;//原子结点的值域struct{GLNodeT*hp,*tp;//hp指向子表的表头结点，tp指向下一层下一个表结点}ptr;//表结点的指针域，分别指向表头和表尾}};

4栈和队列

我们知道，线性表可以任意位置增删改查，如头插、尾插、任意位置插入、删除等；

如果将增删改查的操作函数限制在头部，便是栈；

如果将增删改查的操作函数限制在头尾，便是队列；

栈是实现递归、深度优先遍历、回溯算法的一种很重要的辅助数据结构；

队列是实现广度优先遍历、分支限界算法的一种很重要的辅助数据结构；

ref:

数组结构｜用数组和链表分别实现栈和队列

5串

字符顺序表或字符链表，栈和队列是顺序表运算的限定，对于线性表的元素类型限定到字符便是串，让字符串的表示摆脱单纯对'\0'的依赖；

6二叉树

线性表组织成适当的二叉树，并可以实现较为平衡的增删改查的操作；

二叉树递归定义，用结构体封装数据和两个自指的指针（自指左子二叉树和右子二叉树）；

二叉树的顺序存储：

#defineMAXNODE//二叉树的最大节点数typedefelemtypeSqBiTree[MAXNODE];//0号单元存放根节点SqBiTreebt;

二叉链表存储：

typedefstruct{intnum;}NodeData;typedefstructtreenode{NodeDatadata;structtreenode*left,*right;}TreeNode,*TreeNodePtr;

二叉树与搜索、排序：

二叉树左右建立顺序关系：二叉搜索树；

二叉树上下建立顺序关系：堆与堆排序。

7图

顶点可以用一维数组表示，顶点的关系（边或弧）可以用邻接矩阵（二维数组）或邻接表（一个结点与其它结点的邻接关系用一个链表表示，全部顶点组成邻接表）表示；

7.1顺序表存储图：

templatetypenameElemTypeclassVector{protected://定义顺序表存储结构intlength;intcapacity;ElemType*elem;};templatetypenameTclassGraph{protected:intn;//顶点总数inte;//边总数};templatetypenameTclassMGraph:publicGraphT{//顺序表存储图VectorTvertex;VectorVectorintedges;};

7.2邻接表存储图

templatetypenameElemTypeclassVector{protected://定义顺序表存储结构intlength;intcapacity;ElemType*elem;};templatetypenameTstructLNode{Tdata;//存储数据LNodeT*next;//后继指针//构造函数LNode(){}LNode(Te,LNodeT*n=NULL):data(e),next(n){}};templatetypenameTclassList{protected:int_size;LNodeT*header;};templatetypenameTclassGraph{protected:intn;//顶点总数inte;//边总数};templatetypenameTstructVNode{intadjvex;//顶点位置Tdata;//顶点数据intweight;//权值VNode(){}VNode(inta,Td,intw=INT_MAX):adjvex(a),data(d),weight(w){}};templatetypenameTclassLGraph:publicGraphT{private:VectorListVNodeTAdjList;};

7.3十字链表存储稀疏矩阵

将每个非零元素存储为一个节点，节点由5个域组成。分别是行、列、值、下一个元素的行、列偏移。

templatetypenameElemTypeclassVector{protected://定义顺序表存储结构intlength;intcapacity;ElemType*elem;};templatetypenameTclassGraph{protected:intn;//顶点总数inte;//边总数};//十字链表中弧的结构体structArcBox{inttailvex,headvex,weight;//弧的尾和头顶点位置及权值ArcBox*hlink,*tlink;//弧头相同和弧尾相同的弧的链域};//十字链表中头节点的结构体templatetypenameTstructVNode{Tdata;//顶点信息ArcBox*firstIn,*firstOut;//该顶点的第一条入弧和出弧};//用十字链表表示图templatetypenameTclassOLGraph:publicGraphT{private:VectorVNodeTOList;};

复杂的数据结构由简单数据结构构造。

树，是一种特殊的图（简单版）。

树，可以用广义表表示。

树的孩子兄弟表示法可以将在与二叉树相互转换。

非线性聚类的遍历就是变非线性为线性，深度优先遍历由栈数据结构辅助，广度优先遍历由队列数据结构辅助。

－－