各种数据结构的存储结构汇总

数据结构的存储结构汇总"/>

各种数据结构的存储结构汇总

线性表

1. 线性顺序表

顺序表的索引从[0]开始，最后一个元素为[length - 1]

#define MaxSize 10		// 数组的最大长度
typedef int ElemType;	// 定义数组类型typedef struct SqList {ElemType data[MaxSize];		// 定长数组int length;					// 数组长度
}SqList;typedef struct SqList {ElemType *data;		// 不定长数组int length;			// 数组长度
}SqList;

测试用

void main() {SqList sqlist;		// 不需要分配地址空间sqlist.data = (ElemType *)malloc(MaxSize * sizeof(ElemType));// 指针类型必须分配空间
}

2、线性链表（单链表）

带头结点的单链表（L是头指针）：
L指向头结点，头结点的data域不作存储，next域指向第一个结点，链表为空next指向null
不带头节点的单链表：
L指向第一个结点，链表为空L指向null

#define MaxSize 10		// 数组的最大长度
typedef int ElemType;	// 定义数组类型typedef struct LNode {ElemType data;				// data域struct LNode *next;			// next域指针}LNode, *LinkList;

测试用

void main() {LNode *L;		// 头结点L = (LinkList)malloc(sizeof(LNode));L->data = -1;L->next = (LNode *)malloc(sizeof(LNode));// 注意L和L->next初始化时候的区别，L表示头结点，指向的是整个链表，在逻辑上用LinkList表示// L->next表示下一个结点，指向的是结点，在逻辑上用LNode *表示// LinkList 完全等于LNode *
}

3、双链表

带头结点的双链表：
L指向头结点，头结点的前驱指针不作存储，data域和next域和单链表使用方法一致

#define MaxSize 10		// 数组的最大长度
typedef int ElemType;	// 定义数组类型typedef struct DNode {ElemType data;struct DNode *prior, *next;		// 前驱指针和后继指针}DNode, *DLinkList;

测试用

void main() {DNode *D;		// 头结点D = (DLinkList)malloc(sizeof(DNode));D->prior = NULL;D->data = -1;D->next = (DNode *)malloc(sizeof(DNode));
}

4、循环链表

单链表的最后一个结点的next域一定指向NULL，循环链表的最后一个结点的next域指向头结点
单链表设头指针，循环链表设尾指针

5、循环双链表

循环链表+双链表

栈和队列

1、顺序栈

先进后出的特性，栈底指针不变，栈顶指针变换

#define MaxSize 10		// 数组的最大长度
typedef int ElemType;	// 定义数组类型typedef struct SqStack {ElemType data[MaxSize];int top;		// 栈顶指针// 因为栈底的地址不变，因此不需要用指针记录其位置}SqStack;

测试用

void main() {SqStack stack;stack.top = -1;// top始终指向栈顶元素的位置// 栈空：top = -1// 栈满：top == MaxSize - 1// 栈长：top + 1
}

2、链栈

链栈的本质是带头结点的单链表：
链栈的存储结构是基于单链表结构完成的
以单链表的头指针作为栈顶指针，允许出栈和入栈
以单链表的表尾作为栈底，不允许修改

#define MaxSize 10		// 数组的最大长度
typedef int ElemType;	// 定义数组类型typedef struct LSNode {ElemType data;struct LSNode *next;}LSNode, *LinkStack;

3、顺序队列（循环队列）

先进先出的特性，需要设置两个指针front和rear，分别指向队头和队尾
由于队列尾进头出，导致队列整体位置不断后移，导致前部分存储空间浪费和后部分存储空间减少，因此多数顺序队列被设计为循环队列

#define MaxSize 10		// 数组的最大长度
typedef int ElemType;	// 定义数组类型typedef struct SqQueue {ElemType data[MaxSize];int front, rear;} SqQueue;

测试用

void main() {SqQueue queue;queue.front = queue.rear = 0;// 初始front和rear都等于0，表示front指向队头结点，rear指向队尾结点的下一个结点// 队空：front == rear// 队满：(rear + 1) % MaxSize == front	牺牲一个存储单元用来区分队空和队满的情况// 队列中元素的个数：(rear - front + MaxSize) % MaxSize}

4、链队列（非重点）

带头指针、尾指针的链表：
头指针指向队头（front），尾指针指向队尾（rear）

#define MaxSize 10		// 数组的最大长度
typedef int ElemType;	// 定义数组类型typedef struct LQNode {ElemType data;struct LQNode *next;}LQNode, *LQPoint;typedef struct LinkQueue {LQPoint front, rear;}LinkQueue;

串

1、定长顺序存储

为了更方面理解字符串操作算法，[0]不作存储，从[1]位置开始存储

typedef struct SString {char ch[MaxSize];int length;
}SString;

2、堆分配存储表示

typedef struct HString {char *ch;int length;
}HString;

二叉树和森林

1、二叉树

#define MaxSize 10		// 数组的最大长度
typedef int ElemType;	// 定义数组类型typedef struct BiNode {ElemType data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode, *BiTree;

2、树的孩子兄弟表示法

3、森林的二叉树表示法

无论是树的孩子兄弟法，还是森林的二叉树表示法，都和二叉树的存储结构相同，只是指针域的名称改变罢了

图

1、邻接矩阵

有向图的邻接矩阵中行表示出度，列表示入度
无向图的邻接矩阵是对称矩阵，每一条边被存储两次，可以采用压缩存储的方式进行存储

#define MaxVertexNum 100	// 顶点数目的最大值
typedef char VertexType;	// 定义顶点数据类型
typedef int EdgeType;		// 定义边的数据类型typedef struct MGraph {VertexType Vex[MaxVertexNum];		// 顶点表EdgeType Edge[MaxVertexNum][MaxVertexNum];	// 边表int vexnum, arcnum;		// 当前图的顶点数和边数
}

2、邻接表

有向图的邻接表中，顶点的边表是出度集合；若想得到某顶点的入度集合，必须遍历全部边或者再建立一个逆邻接表
无向图的邻接表中，每一条边都被分配了两次存储空间，分别在两端顶点的边表中

#define MaxVertexNum 100	// 顶点数目的最大值
typedef int InfoType;
typedef char VertexType;typedef struct ArcNode {	// 边表结点int adjvex;		// 该弧所指向的顶点的位置struct ArcNode *next;	// 指向下一条弧的指针// InfoType info;
}ArcNode;typedef struct VexNode {	// 顶点表结点VertexType data;	// 顶点信息ArcNode *first;		// 指向依附该顶点的边表的第一个结点
}VexNode, AdjList[MaxVertexNum];typedef struct ALGraph {	// 图AdjList vertices;		// 邻接表int vexnum, arcnum;		// 图的顶点和弧数
}ALGraph;

3、邻接多重表

为了解决无向图的邻接表表示法中，每条边被存储两次的问题
（在形式上，只需要把1、3、5…结点的出度画出来就可以构造出邻接多层表）

#define MaxVertexNum 100	// 顶点数目的最大值
typedef int InfoType;
typedef char MarkedType;
typedef char VertexType;typedef struct ArcNode {	// 边表结点int ivex;		// 该边依附的结点vi在图中的位置ArcNode *ilink;		// 指向下一个依附vi结点的边int jvex;		// 该边依附的结点vj在图中的位置ArcNode *jlink;		// 指向下一个依附vj结点的边// InfoType info;// MarkedType mark;
}ArcNode;typedef struct VexNode {	// 顶点表结点VertexType data;	// 顶点信息ArcNode *firstedge;		// 指向依附该顶点的边表
}VexNode, AdjList[MaxVertexNum];typedef struct ALGraph {	// 图AdjList vertices;		// 邻接表int vexnum, arcnum;		// 图的顶点和弧数
}ALGraph;

4、十字链表

为了解决有向图的邻接表只能直接查询出度边表，而不能直接查询入度边表的问题
十字链表 = 邻接表 + 逆邻接表

#define MaxVertexNum 100	// 顶点数目的最大值
typedef int InfoType;
typedef char MarkedType;
typedef char VertexType;typedef struct ArcNode {	// 边表结点int tailvex;		// 尾域，弧尾结点在图中的位置int headvex;		// 头域，弧头结点在图中的位置ArcNode *tlink;		// 指向弧尾相同的下一条弧ArcNode *tlink;		// 指向弧头相同的下一条弧// InfoType info;// MarkedType mark;
}ArcNode;typedef struct VexNode {	// 顶点表结点VertexType data;		// 顶点信息ArcNode *firstin;		// 以该顶点为弧头的第一个弧顶点ArcNode *firstout;		// 以该顶点为弧尾的第一个弧顶点
}VexNode, AdjList[MaxVertexNum];typedef struct ALGraph {	// 图AdjList vertices;		// 邻接表int vexnum, arcnum;		// 图的顶点和弧数
}ALGraph;