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

线性表

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;