目录
1.单链表
2.双向链表
3.带头结点的链表
4.顺序栈
5.单链队列
6.循环队列
7.广义表头尾链表存储
8.广义表的扩展线性链表存储
9.二叉树二叉链表存储表示
10.树的双亲表示法
11.树的孩子链表存储表示(孩子表示法)
12.树的孩子兄弟表示法(二叉树表示法)
13.二叉树的二叉线索存储表示
14.哈夫曼树和哈夫曼编码的存储表示
15.图的邻接矩阵
16.图的邻接表
17.有向图的十字链表
18.无向图的邻接多重表
19.二叉排序树
20.B-树
1.单链表
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.双向链表
typedef struct DuLNode {
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
} DuLNode, *DuLinkList;
3.带头结点的链表
typedef struct LNode {
ElemType data;
struct LNode *next;
} *Link;
typedef struct {
Link head, tail;
int len;
} LinkList;
4.顺序栈
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
5.单链队列
typedef struct QNode {
QuElemType data;
struct QNode next;
} QNode, *QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
} LinkQueue;
6.循环队列
typedef struct {
QElemType *base;
int front;
int rear;
} SqQueue;
7.广义表头尾链表存储
typedef enum {ATOM, LIST} ElemTag;
typedef struct GLNode {
ElemTag tag;
union {
AtomType atom;
struct {
struct GLNode *hp, *tp;
} ptr; //ptr.hp, ptr.tp 分别表示子表的表头，表尾
};
} *GLsit;
8.广义表的扩展线性链表存储
typedef enum {ATOM, LIST} ElemTag;
typedef struct GLNode {
ElemTag tag;
union {
AtomType atom;
struct GLNode *hp;
};
struct GLNode *tp; //相当于next，指向下一个元素节点
} *GLsit;
9.二叉树二叉链表存储表示
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
10.树的双亲表示法
typedef struct PTNode {
TElemType data;
int parent;
} PTNode;
typedef struct {
PTNode node[MAX_TREE_SIZE];
int root, n; //根节点位置和节点数
} PTree;
11.树的孩子链表存储表示(孩子表示法)
typedef struct CTNode { //孩子节点
int child;
struct CTNode *next;
} *ChildPtr;
typedef struct {
TElemType data;
ChildPtr firstchild; //孩子链表头指针
} CTBox;
typedef struct {
CTBox node[MAX_TREE_SIZE];
int root, n;//根节点位置和节点数
} CTree;
12.树的孩子兄弟表示法(二叉树表示法)
typedef struct CSTNode {
TElemType data;
struct CSTNode *firstchild, *nextsibling;
} CSNode, *CSTree;
13.二叉树的二叉线索存储表示
typedef enum {Link, Thread} PointerTag;
typedef struct BiThrNode {
TElemType data;
struct BiThrNode *lchild, *rchild;
PointerTag LTag, RTag;
} BiThrNode, *BiThrTree;
14.哈夫曼树和哈夫曼编码的存储表示
typedef struct {
unsigned int weight;
unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree; //哈夫曼树
typedef char **HuffmanCode; //哈夫曼编码表
15.图的邻接矩阵
typedef struct ArcCell {
VRType adj;
InfoType *info;
} ArcCell, AdjMatrix[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];
typedef struct {
VertexType vexs[MAX_VERTEX_SIZE];
AdjMatrix arcs;
int vexnum, arcnum;
} MGraph;
16. 图的邻接表
typedef struct ArcNode {
int adjvex; //该边所指顶点
struct ArcNode *nextarc; //下一条边
InfoType *info; //边的信息
} ArcNode;
typedef struct VNode {
VertexType data; //顶点信息
ArcNode *firstarc; //该顶点发出的第一条边
} VNode, AdjList[MAX_VERTEX_SIZE];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} ALGraph;
17. 有向图的十字链表
typedef struct ArcBox {
int headvex, tailvex; //该边的头尾顶点
struct ArcBox *hlink, *tlink; //头顶点相同的下一条边和尾相同的下一条边
InfoType *info;
} ArcBox;
typedef struct VexNode {
VertexType data;
ArcBox *firstin, *firstout; //该点的第一条入边和出边
} VexNode;
typedef struct {
VexNode xlist[MAX_VERTEX_SIZE]; //表头
int vexnum, arcnum;
} OLGraph;
18.无向图的邻接多重表
typedef struct EBox {
VisitIf mark; //访问标记
int ivex, jvex; //该边的两个顶点
struct EBox *ilink, *jlink; //指向依附这两个顶点的下一条边
InfoType *info;
} EBox;
typedef struct VexBox {
VertexType data;
EBox *firstedge; //第一条依附该顶点的边
} VexBox;
typedef struct {
VexBox adjmulist[MAX_VERTEX_SIZE];
int vexnum, edgenum;
} AMLGraph;
19.二叉排序树
typedef struct BSTNode {
ElemType data;
int bf; //平衡因子
struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;
20.B-树
#define m 3 //B-树的阶
typedef struct BTNode {
int keynum; //节点关键字个数
struct BTNode *parent; //双亲结点
KeyType key[m + 1]; //关键字[1, ..., m]
struct BTNode *ptr[m + 1]; //子树指针
Record *recptr[m + 1]; //记录指针向量
} BTNode, *BTree;
typedef struct {
BTNode *pt; //指向找到的节点
int i; //结果的关键字序号 1...m
int tag; //1：查找成功，0：查找失败
} Result; //查找结果类型