数据结构复习
栈
栈(stack)是限定仅在表尾进行插入和删除操作的线性表。表尾端被称为栈顶,相对地,表头端称为栈底。向一个栈插入新元素称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它会把栈顶元素删除掉。换句话说,栈的修改是按后进先出的原则进行的。因此,栈又称为后进先出(last in first out)的线性表
栈的顺序存储结构
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
//栈的初始化
typedef struct stack
{
int data[MAX];
int top;
} Stack;
void initStack(Stack* stack)
{
stack -> top = -1;
}
int isEmpty(const Stack* stack)//const 保证函数不会修改它指向的数据
{
return stack -> top == -1;
}
void push(Stack* stack, int value)
{
if (stack -> top < MAX-1)
{
stack -> top++;
stack -> data[stack -> top] = value;
}
}
int pop(Stack* stack)
{
if (!isEmpty(stack))
{
const int value = stack -> data[stack -> top];
stack -> top--;
return value;
} else
{
printf("栈为空,无法出栈\n");
return -1;
}
}
int main()
{
Stack stack;
initStack(&stack);
push(&stack,1);
push(&stack,2);
push(&stack,3);
while (!isEmpty(&stack))
{
const int poppedValue = pop(&stack);
if (poppedValue != -1)
{
printf("出栈元素:%d\n",poppedValue);
}
}
system("pause");
return 0;
}
栈的链式存储结构
#include <stdio.h>
#include <stdlib.h>
//栈的初始化
typedef struct Stack//添加和删除在同一个节点,这个链表就是栈
{
int data;
struct Stack* next;
} Stack;
int push(Stack *head, const int e)//头插法
{
Stack *newNode = (Stack*)malloc(sizeof(Stack));
newNode->data = e;
newNode->next = head->next;
head->next = newNode;
return 1;
}
int pop(Stack *head, int *value)
{
if (head->next == NULL)
{
printf("空栈\n");
return 0;
}
*value = head->next->data;
const Stack *tempNode = head->next;
head->next = tempNode->next;
free(tempNode);
return 1;
}
int main()
{
Stack *head = (Stack*)malloc(sizeof(Stack));
head->next = NULL;
push(head,1);
push(head,2);
push(head,3);
int value;
while (pop(head,&value))
{
printf("%d\n",value);
}
system("pause");
return 0;
}
队列
队列(Queue)是一种先进先出(First In First Out,FIFO)的线性表。**它只允许在表的一端进行插入,而在另一端删除元素。**在队列中,允许插入的一端称为队尾(rear),允许删除的一端则称为队头(front)。队列的操作与栈的操作类似,不同的是,删除是在表的头部(即队头)进行。
队列的顺序存储结构
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
//队列的顺序定义
typedef struct
{
int data[MAX];
int front;
int rear;
} Queue;
void initQueue(Queue *q)
{
q->front = 0;
q->rear = 0;
}
int isEmpty(const Queue *q)
{
return q->rear == q->front;
}
int deQueue(Queue *q)
{
if (isEmpty(q))
{
printf("队列为空,无法出队\n");
return -1;
}
const int value = q->data[q->front];
q->front = q->front+1;
return value;
}
int isFull(const Queue *q)
{
if (q->rear>=MAX-1)
return 1;
return 0;
}
void enQueue(Queue *q,int value)
{
if (isFull(q))
{
if (q->front>0)
{
for (int i = 0;i < q->rear - q->front;i++)
{
q->data[i] = q->data[q->front+i];//如果队尾所在指针为最大值,则移动元素
}
q->rear = q->rear - q->front;
q->front = 0;
}else
{
//队列真的满了
printf("队列已满,无法入队");
return;
}
}
//在队尾添加元素
q->data[q->rear] = value;
q->rear++;
}
int main() {
Queue q;
initQueue(&q);
printf("初始化队列并填充元素\n");
// 先用100个数据填充队列,此时队列已经满了
for (int i = 0; i < 100; i++) {
enQueue(&q, i);
}
printf("队列已填满,front=%d, rear=%d\n", q.front, q.rear);
// 出队3个元素,制造前3个位置为空的情况
for (int i = 0; i < 3; i++) {
printf("出队元素:%d\n", deQueue(&q));
}
printf("出队3个元素后,front=%d, rear=%d\n", q.front, q.rear);
// 尝试继续入队,此时会触发元素移动
printf("尝试继续入队新元素\n");
enQueue(&q, 1001);
enQueue(&q, 1002);
enQueue(&q, 1003);
printf("移动元素后,front=%d, rear=%d\n", q.front, q.rear);
printf("队头元素:%d\n", q.data[q.front]);
printf("队尾元素:%d\n", q.data[q.rear - 1]);
return 0;
}
这里队列的使用栈存储,如果想使用堆进行存储,修改为以下部分:
typedef struct
{
int *data;
int front;
int rear;
}Queue;
Queue* initQueue()
{
Queue *q = (Queue *)malloc(sizeof(Queue));
q->data = (int *)malloc(MAX * sizeof(int));
q->front = 0;
q->rear = 0;
return q;
}
int main() {
Queue *q = initQueue();
//测试逻辑
return 0;
}
循环队列
由于数据量过多的情况下,普通队列若队满会造成大量数据的移动,对性能产生较大的影响,所以我们需要使用循环队列。
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
//队列的顺序定义
typedef struct
{
int data[MAX];
int front;
int rear;
} Queue;
void initQueue(Queue *q)
{
q->front = 0;
q->rear = 0;
}
void enQueue(Queue *q, const int value)
{
if ((q->rear+1) % 100 == q->front)
{
//队列真的满了
printf("队列已满\n");
return;
}
//在队尾添加元素
q->data[q->rear] = value;
q->rear = (q->rear + 1) % 100;
}
int deQueue(Queue *q)
{
if (q->front == q->rear)
{
printf("队列为空,无法出队");
return -1;
}
const int value = q->data[q->front];
q->front = (q->front + 1) % 100;
return value;
}
int main() {
Queue q;
initQueue(&q);
// 先用99个数据填充队列,循环队列最多只能存储99个元素
for (int i = 0; i < 99; i++) {
enQueue(&q, i);
}
printf("队列已填满, front=%d, rear=%d\n", q.front, q.rear);
// 把前两个元素出队
printf("出队元素: %d\n", deQueue(&q));
printf("出队元素: %d\n", deQueue(&q));
printf("出队后, front=%d, rear=%d\n", q.front, q.rear);
// 尝试继续入队
printf("尝试继续入队新元素\n");
enQueue(&q, 1001);
printf("入队1001后, 该元素位于data[%d]=%d\n", (q.rear - 1 + 100) % 100, q.data[(q.rear - 1 + 100) % 100]);
enQueue(&q, 1002);
printf("入队1002后, 该元素位于data[%d]=%d\n", (q.rear - 1 + 100) % 100, q.data[(q.rear - 1 + 100) % 100]);
printf("最终, front=%d, rear=%d\n", q.front, q.rear);
printf("队头元素: %d\n", q.data[q.front]);
printf("队尾元素: %d\n", q.data[(q.rear - 1 + 100) % 100]);
return 0;
}
为什么要取余,尽管引索的最大值为100,但是取余可以很好的在引索过大时使其变为0,而不用再次判断。
多少元素问题
不能让队尾和队头指向同一个位置,因为判断队列是否为空就是判断队尾是否等于队头。
队列的链式存储结构
#include <stdio.h>
#include <stdlib.h>
typedef struct QueueNode
{
int data;
struct QueueNode *next;
}QueueNode;
typedef struct
{
QueueNode *front;
QueueNode *rear;
}Queue;
Queue* initQueue()
{//带头节点的链表
Queue *newQueue = (Queue *)malloc(sizeof(Queue));
QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
newNode->data = 0;
newNode->next = NULL;
newQueue->front = newNode;
newQueue->rear = newNode;//判空f=r
return newQueue;
}
int enQueue(Queue *queue, const int element)
{
QueueNode *nNode = (QueueNode*)malloc(sizeof(QueueNode));
nNode->data = element;
nNode->next = NULL;
queue->rear->next = nNode;
queue->rear = nNode;
return 1;
}
int deQueue(Queue *queue, int *element)
{
QueueNode *node = queue->front->next;
*element = node->data;
queue->front->next = node->next;
if (queue->rear == node)//队列是否为空
{
queue->rear = queue->front;
}
free(node);
return 1;
}
int isEmpty(const Queue *queue)
{
if (queue->front == queue->rear)
{
return 1;
}
return 0;
}
void printQueue(const Queue *queue)
{
const QueueNode *ptr = queue->front;
while (ptr != queue->rear)
{
printf("%d ",ptr->next->data);
ptr = ptr->next;
}
}
int main() {
// 初始化队列
Queue *queue = initQueue();
// 入队操作
enQueue(queue, 1);
enQueue(queue, 2);
enQueue(queue, 3);
// 第一次出队并打印
int element;
if (deQueue(queue, &element)) {
printf("出队元素: %d\n", element);
}
// 打印剩余元素
printf("剩余元素: ");
printQueue(queue);
printf("\n");
// 循环出队直到队列为空
while (deQueue(queue, &element)) {
printf("出队元素: %d\n", element);
}
return 0;
}
二叉树
二叉树的创建,前中后序遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define TElemType int
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree; //重命名节点结构体(这里没变化)和定义指向根节点的指针
BiTree CreateBiTreeFromStr(const char *str) {
if (**str == '\0') return NULL;
if (**str == ' ') {
(*str)++;
return NULL;
}
BiTree T = (BiTree)malloc(sizeof(BiTNode));
T->data = **str;
(*str)++;
T->lchild = CreateBiTreeFromStr(str);
T->rchild = CreateBiTreeFromStr(str);
return T;
}
bool PreOT(BiTree T)//依赖于递归的思想
{
if (T)
{
printf("%d",(*T).data);
PreOT(T->lchild);
PreOT(T->rchild);
}
}
bool MidOT(BiTree T)//依赖于递归的思想
{
if (T)
{
MidOT(T->lchild);
printf("%d",(*T).data);
MidOT(T->rchild);
}
}
bool AftOT(BiTree T)
{
if (T)
{
AftOT(T->lchild);
AftOT(T->rchild);
printf("%d",(*T).data);
}
}
int main() {
BiTree root = NULL;
CreateBiTree(&root);
printf("创建完成。\n");
PreOT(root);
printf("\n");
MidOT(root);
printf("\n");
AftOT(root);
return 0;
}
非递归的方式遍历二叉树
在前序情况下
前序遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define TElemType char
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 用二级指针推进字符串
BiTree CreateBiTreeFromStr(const char **str) {
if (**str == '\0') return NULL;
if (**str == '#') {
(*str)++;
return NULL;
}
BiTree T = (BiTree)malloc(sizeof(BiTNode));
T->data = **str;
(*str)++;
T->lchild = CreateBiTreeFromStr(str);
T->rchild = CreateBiTreeFromStr(str);
return T;
}
#define MAX 100
//栈的初始化
typedef struct stack
{
BiTree data[MAX];
int top;
} Stack;
void initStack(Stack* stack)
{
stack -> top = -1;
}
int isEmpty(const Stack* stack)//const 保证函数不会修改它指向的数据
{
return stack -> top == -1;
}
void push(Stack* stack, BiTree value)
{
if (stack -> top < MAX-1)
{
stack -> top++;
stack -> data[stack -> top] = value;
}
}
BiTree pop(Stack* stack)
{
if (!isEmpty(stack))
{
BiTree value = stack -> data[stack -> top];
stack -> top--;
return value;
} else
{
printf("栈为空,无法出栈\n");
return NULL;
}
}
void preOT(BiTree root){
Stack stack;
initStack(&stack);
push(&stack, root);
while(!isEmpty(&stack)) {
BiTree node = pop(&stack);
if (node != NULL) {
printf("%c ", node->data);
if(node->rchild != NULL) {//先入后出
push(&stack, node->rchild); // 先右
}
if(node->lchild != NULL){
push(&stack, node->lchild); // 再左
}
}
}
}
int main() {
const char *input = "ABD##E##C#F##";
const char *p = input;
BiTree T = CreateBiTreeFromStr(&p);
printf("前序遍历结果:");
preOT(T);
printf("\n");
return 0;
}
此为前序遍历:根 左 右;对其进行两次反转:
1.根 右 左 2.左 右 根
后序遍历
void postOT(BiTree root){
Stack s1, s2;
initStack(&s1);
initStack(&s2);
push(&s1, root);
while(!isEmpty(&s1)) {
BiTree node = pop(&s1);
push(&s2,node);
if (node != NULL) {
if(node->lchild != NULL){
push(&s1, node->lchild); // 左
}
if(node->rchild != NULL) {
push(&s1, node->rchild); // 右
}
}
}
while(!isEmpty(&s2)){
BiTree node = pop(&s2);
printf("%c ", node->data);
}
}
中序遍历
1.不停往左访问,每访问一个节点入栈。
2.如果访问到空节点,就从栈中取出元素,打印输出
3.左边走到尽头时,访问右孩子并入栈,如果右孩子为空,就从栈中取出元素,打印输出。
重复1-3步骤
void inOT(BiTree root)
{
Stack s;
initStack(&s);
BiTree current = root;
while (current != NULL || !isEmpty(&s))
{
while (current != NULL)
{
push(&s, current);
current = current->lchild; // 先走到最左
}
// 此时左子树为空,取出栈顶元素
current = pop(&s);
printf("%c ", current->data); // 访问当前节点
current = current->rchild; // 访问右子树
}
}
线索二叉树
创建二叉树与正常相似,在创建完节点后需要判断l,f是否为孩子节点,给tag赋值0。
线索化
void inorderThreading(ThreadTree *head, ThreadTree T)
{
//第一步
*head = (ThreadTree)malloc(sizeof(TreeNode));
(*head)->ltag=0;//头节点左孩子为遍历中首节点
(*head)->rtag=1;//其余都为线索
(*head)->right = *head;
(*head)->left = T;
prev = *head;//上一个节点
threading(T);
//处理最后一个节点,把线索指向头节点
prev->right = *head;
prev->rtag = 1;
//把头节点右孩子指向最后一个节点
(*head)->right = prev;
}
线索化关键函数
//中序遍历左中右
void threading(ThreadTree T){
if(T != NULL){
threading(T->left);
if(T->left == NULL){
T->ltag = 1;
T->left = prev;//外部定义全局变量,前驱节点
}
if(prev != NULL && prev->right == NULL){
prev->rtag = 1;
prev->right = T;//定义前驱节点的线索
}
prev = T;
threading(T->right);
}
}
线索化作用
不递归访问二叉树
// 中序遍历线索二叉树
void inOrderTraversal(ThreadTree head) {
ThreadTree curr;
curr = head->left;//头节点left就是根
while (curr != head) {//遍历结束后curr==head
// 找到最左边的节点
while (curr->ltag == 0) {
curr = curr->left;
}
// 访问当前节点
printf("%c ", curr->data);
// 通过线索遍历后继节点
while (curr->rtag == 1 && curr->right != head) {
curr = curr->right;
printf("%c ", curr->data);
}
// 转向右子树
curr = curr->right;
}
}
哈夫曼树
评级 | 不及格 | 及格 | 良好 | 优秀 |
---|---|---|---|---|
分数 | 0-59 | 60-75 | 75-90 | 90-100 |
人数 | 1 | 46 | 40 | 13 |
这个二叉树不够高效,左右子树不均匀。哈夫曼树就是类似如下的更改:
哈夫曼树的概念
路径:是指从树中一个结点到另一个结点的分支所构成的路线。
路径长度:路径上的分支数目
树的路径长度:指从根结点到每个叶子结点的路径之和。
结点的权:树中结点被赋予一个表示某种意义的数值
带权路径长度:从结点到根之间的路径长度乘以结点的权值
树的带权路径长度(WPL):所有叶子结点的带权路径长度之和
哈夫曼树就是树的带权路径长度最小的树。
如何构造哈夫曼树
第一步:选取最小的两个结点,组成一个新结点,新结点的权值为两个结点的权值之和 第二步:把新结点加入到原来的集合中,重复第一步,直到集合中只剩下一个结点为止。
哈夫曼编码
先按照以下编码字符串:
A | B | C | D | E |
---|---|---|---|---|
000 | 001 | 010 | 011 | 100 |
如何表示:A B C D A A B
000 001 010 011 000 000 001
可是这段二进制编码太长了,我们可以使用哈夫曼编码。
构建哈夫曼树
字母出现的频率为字母的权重,令左分支为0又分支为1,得出哈夫曼编码,可以大大减少二进制编码的长度。
树转化为二叉树
只保留长子
怎么看出来这是一棵二叉树?对于每个结点,第一个孩子是当前结点的左孩子(蓝线)。兄弟是结点的右孩子(红线)
二叉树转换为树
先把每个左孩子的所有右结点以及右结点的右结点与父结点连线。
再去掉原来二叉树里的右孩线,最后分别压扁到同一层。
森林转换为二叉树
多棵树组成的集合被称作森林。
先把每棵树转变为二叉树,然后再组装
具体的方法是,按照顺序把后一个树的根拼接到上一个树的根节点。
二叉树转换为森林
去掉全部的右孩子线,孤立所有的二叉树再还原。
树的遍历
先根遍历
且任何一颗树其先根遍历结果与转化为二叉树的先序遍历结果相同。
后根遍历
与之类似,后根遍历的结果与转化后的二叉树中序遍历结果相同。
森林的遍历
树 | 森林 | 二叉树 |
---|---|---|
先根遍历 | 前序遍历 | 前序遍历 |
后根遍历 | 中序遍历 | 中序遍历 |
按照表格,先把森林转换为二叉树后进行遍历。