4.队列
4.1.队列的数据结构定义
4.1.1.顺序队列
#define MAXSIZE 100 typedef struct Queue { int data[MAXSIZE]; int front, rear; }Queue;
4.1.2.链式队列
typedef struct LNode{ struct LNode *next; int data; }LNode; typedef struct Queue{ LNode *front, *rear; }Queue;
4.2.顺序队列的基本操作
4.2.1.初始化
void InitQueue(Queue &Q){ Q.front = Q.rear = 0; }
4.2.2.入队
bool EnQueue(Queue &Q, int key){ if (Q.front == (Q.rear + 1) % MAXSIZE) return false; //队满 Q.data[rear] = key; Q.rear = (Q.rear + 1) % MAXSIZE; return true; }
4.2.3.出队
bool DeQueue(Queue &Q, int &key){ if (Q.rear == Q.front) return false; //队空 key = Q.front; Q.front = (Q.front + 1) % MAXSIZE; return true; }
4.2.4.判断队空
bool IsEmpty(Queue Q){ if (Q.front == Q.rear) return true; else return false; }
4.3.链式队列的基本操作
4.3.1.初始化
void InitQueue(Queue &Q){ Q.front = Q.rear = (LNode*)maloc(sizeof(LNode)); Q.front->next = NULL; }
4.3.2.入队
void Queue(Queue &Q, int key){ LNode *p = (LNode*)malloc(sizeof(LNode)); //申明一个新结点 p->data = key; p->next = NULL; Q.rear->next = p; //尾插法插入到rear后 Q.rear = p; //更新rear }
4.3.3.出队
bool DeQueue(Queue &Q, int &key){ if (Q.front == Q.rear) return false; //队空 LNode *p = Q.front->next; key = p->data; //保存队首元素的数据 Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; //队列中只有一个元素 free(p); return true; }
4.3.4.判断队空
bool IsEmpty(Queue Q){ if (Q.rear == Q.front) return true; else return false; }
5.树
5.1.树的数据结构定义
5.1.1.二叉树的链式存储
typedef struct BiTree{ sturct BiTree *lchild, *rchild; //左右孩子指针 int value; //结点数据 }BiTNode, *BiTree;
5.1.2.二叉树的顺序存储
#define MAXSIZE 100 typedef struct TreeNode{ int value; //结点数据 bool IsEmpty; //该结点是否存在 }TreeNode; void InitTree(TreeNode T[], int len){ for (int i = 0; i < len; i++) T[i].IsEmpty = true; //将该结点初始化为空结点 } int main(){ TreeNode T[MAXSIZE]; //申明一个长度为MAXSIZE的TreeNode数组 InitTree(T); //初始化树 ... }
5.1.3.双亲表示法
#define MAXSIZE 100 //树中最多结点数 typedef struct TreeNode{ int data; //结点数据 int parent; //该结点的双亲结点在数组的下标 }TreeNode; typedef struct Tree{ TreeNode T[MAXSIZE]; //长度为MAXSIZE的TreeNode类型的数组 int treeNum; //结点数 }Tree;
5.1.4.孩子表示法
#define MAXSIZE 100 //孩子结点 typedef struct Child{ int index; //该结点的编号 struct Child *next; //指向该结点的下一个孩子结点的指针 }Child; //结点信息 typedef struct TreeNode{ Child *firstTNode; //指向该结点的第一个孩子结点的指针 int data; //该结点数据 }TreeNode; TreeNode T[MAXSIZE]; //定义一个长度为MAXSIZE的树
5.1.5.孩子兄弟表示法
#define MAXSIZE 100 typedef struct CSNode{ struct CSNode *firstChild, *nextSibling; //指向第一个孩子和右兄弟节点 int data; //该结点数据 }CSNode;
5.1.6.线索二叉树
typedef struct ThreadNode{ struct ThreadNode *lchild, *rchild; //左右孩子指针 int ltag, rtag; //左右线索标志 int data; //结点数据 }ThreadNode, *ThreadTree;
