数据结构复习#

栈#

栈(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;
    }
    
}