Dong
C语言 链表 栈与队列 二叉树遍历
2024-09-01
课程学习
00
c语言链表操作c语言栈与队列实现c语言二叉树遍历数据结构链表教程数据结构二叉树算法

目录

0 链表
1 栈
1.1 数组实现的栈
1.2 链表实现的栈
2 队列
2.1 数组实现的队列
2.1 链表实现的队列
3 二叉树遍历
3.1 迭代版本
3.2 用栈的遍历 先序中序后序
3.3 用队列(链表队列)进行层次遍历

http://data.biancheng.net/

参考

https://blog.csdn.net/song_hui_xiang/category_5675971.html

0 链表

1 链表在物理空间的存储不是连续的，全是操作指针。但也是线性结构。

2 分单向链表和双向链表。

3 链表节点一般是一个结构体，每个链表节点有自己的数据块，也有指针，指针指向下一个链表节点，这是单向链表。双向链表多了一个指针。

4 下面的程序有一些规定：

NODE *create(); 创建链表只是创建了一个链表头，链表头是作为哨兵的，不存储实际的数据。链表头暂且叫做标号0。

void insert(NODE *head, NODE *pnew, int i) 向链表中插入一个新的节点，i=0代表插入到标号0的后面，插入后新节点其实是标号1。

void delete(NODE *head, int i); 删除列表中的一个节点，i=0表示删除标号0后面那个节点。

void allClear(NODE *head);删除所有节点但是不包含头节点

在这里插入图片描述

c
展开代码
#include <stdio.h>
#include <stdlib.h>
struct student {
    int score;
    struct student *next;
};
typedef struct student NODE; //typedef为C语言的关键字，作用是为一种数据类型定义一个新名字。简化一些比较复杂的类型声明。
NODE *create(); //创建链表
void insert(NODE *head, NODE *pnew, int i); //插入
void delete(NODE *head, int i); //删除
void allClear(NODE *head); //清除链表的所有节点，不包含头节点。
void display(NODE *head); //打印链表
int main(int argc, const char * argv[]) {
    NODE *head, *pnew;
    //创建链表
    head = create();
    //插入一个新节点
    pnew = (NODE*)malloc(sizeof(NODE));
    pnew->score = 1;
    pnew->next = NULL;
    insert(head, pnew, 0);
    //插入一个新节点
    pnew = (NODE*)malloc(sizeof(NODE));
    pnew->score = 2;
    pnew->next = NULL;
    insert(head, pnew, 1);
    //打印链表
    display(head);
    //删除
    delete(head, 0);
    //打印链表
    display(head);
    //清除链表的所有节点，包含头节点。
    allClear(head);
    //打印链表
    display(head);
    return 0;
}
//创建链表
NODE *create() {
    NODE *head;
    int score;
    head = (NODE*)malloc(sizeof(NODE)); //创建头节点。
    if (head == NULL) {
        printf("创建失败!");
        return NULL;
    }
    head->score = 0;
    head->next = NULL;
    return head;
}
//插入 头结点不算，从有数据的开始算第一个
void insert(NODE *head, NODE *pnew, int i) {
    NODE *p = head;
    int j;
    //从链表头开始往下找，找到第i个位置
    for (j = 0; j < i && p != NULL; j++) {
        p = p->next;
        if (p == NULL) {
            printf("\n与插入的节点不存在！");
            return;
        }
    }
    pnew->next = p->next;
    p->next = pnew;
}
//删除 头结点不算，从有数据的开始算第一个
void delete(NODE *head, int i) {
    NODE *p = head, *pnew;
    int j;
    for (j = 0; j < i && p != NULL; j++) {
        p = p->next;
        if (p == NULL) {
            printf("\n删除的节点不存在！");
            return;
        }
    }
    pnew = p->next;
    p->next = pnew->next;
    free(pnew);
}
//清除链表的所有节点，不包含头节点。
void allClear(NODE *head) {
    NODE *p, *q;
    p = head;
    while (p->next != NULL) {
        q = p->next;
        p->next = q->next;
        free(q);
    }
    //free(head); //删除头节点
}
//打印链表
void display(NODE *head) {
    NODE *p;
    printf("\n学生成绩分别是：");
    for (p = head->next; p != NULL; p = p->next) {
        printf("%d  ", p->score);
    }
}

1 栈

1.1 数组实现的栈

堆栈的数组实现，关注点：初始化、入栈、出栈。

c
展开代码
//堆栈的数组实现
#include <stdio.h>
#include <stdlib.h>
#define ElementType int //存储数据元素的类型
#define MAXSIZE 1024 //存储数据元素的最大个数
#define ERROR -99 //ElementType的特殊值，标志错误
//堆栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成
typedef struct {
    ElementType data[MAXSIZE];
    int top;
}Stack;
//初始化栈
Stack* InitStack() {
    Stack* stack;
    stack = (Stack*)malloc(sizeof(Stack));
    if (!stack) {
        printf("空间不足\n");
        return NULL;
    }
    stack->top = -1;
    return stack;
}
int IsFull(Stack* stack) {
    if (stack->top == MAXSIZE - 1) {
        printf("堆栈已满\n");
        return 1;
    }
    return 0;
}
int IsEmpty(Stack* stack) {
    if (stack->top == -1) {
        printf("堆栈空\n");
        return 1;
    }
    return 0;
}
//入栈
void Push(Stack* stack, ElementType item) {
    if (IsFull(stack)) {
        return;
    }
    stack->data[++(stack->top)] = item;//数据存入栈顶
}
//出栈
ElementType Pop(Stack* stack) {
    if (IsEmpty(stack)) {
        return ERROR;
    }
    return stack->data[stack->top--];//数据出栈
}
void PrintStack(Stack* stack) {
    printf("当前栈中的元素:\n");
    int i;
    for (i = stack->top; i >= 0; i--) {
        printf("%d\n", stack->data[i]);
    }
}
int main(int argc, const char * argv[]) {
    Stack* stack;
    stack = InitStack();
    Push(stack, 1);
    Push(stack, 2);
    Push(stack, 3);
    Push(stack, 4);
    Push(stack, 5);
    PrintStack(stack);
    Pop(stack);
    Pop(stack);
    PrintStack(stack);
    return 0;
}

1.2 链表实现的栈

链表更灵活，每次入栈才新建一个节点，每次出栈释放节点的空间。

c
展开代码
#include <stdio.h>
#include <stdlib.h>
#define ElementType int
#define ERROR -99
typedef struct Node {
    ElementType data;
    struct Node* next;
}LinkStack;
//初始化堆栈
LinkStack* InitLinkStack() {
    LinkStack* s;
    s = (LinkStack*)malloc(sizeof(LinkStack));
    if (!s) {
        printf("空间不足\n");
    }
    s->next = NULL;
    return s;
}
int IsEmpty(LinkStack* s) {
    return (s->next == NULL);
}
void Push(LinkStack* s, ElementType data) {
    LinkStack* cell;
    cell = (LinkStack*)malloc(sizeof(LinkStack));
    if (!cell) {
        printf("空间不足\n");
    }
    cell->data = data;
    cell->next = s->next;
    s->next = cell;
}
ElementType Pop(LinkStack* s) {
    LinkStack* firstCell;
    ElementType topData;
    if (IsEmpty(s)) {
        printf("空栈\n");
        return ERROR;
    }
    firstCell = s->next;
    s->next = firstCell->next;
    topData = firstCell->data;
    free(firstCell);
    return topData;
}
void PrintLinkStack(LinkStack* s) {
    printf("当前栈中的元素:\n");
    LinkStack* p;
    p = s;
    while (p->next != NULL) {
        p = p->next;
        printf("%d\n",p->data);
    }
}
int main(int argc, const char * argv[]) {
    LinkStack* s;
    s = InitLinkStack();
    Pop(s);
    Push(s, 1);
    Push(s, 2);
    Push(s, 3);
    Push(s, 4);
    Push(s, 5);
    PrintLinkStack(s);
    Pop(s);
    Pop(s);
    PrintLinkStack(s);
    return 0;
}

2 队列

2.1 数组实现的队列

c
展开代码
#include <stdio.h>
#include <stdlib.h>
#define ElementType int //存储数据元素的类型
#define MAXSIZE 6 //存储数据元素的最大个数
#define ERROR -99 //ElementType的特殊值，标志错误
typedef struct {
    ElementType data[MAXSIZE];
    int front; //记录队列头元素位置
    int rear; //记录队列尾元素位置
    int size; //存储数据元素的个数
}Queue;
Queue* CreateQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    if (!q) {
        printf("空间不足\n");
        return NULL;
    }
    q->front = -1;
    q->rear = -1;
    q->size = 0;
    return q;
}
int IsFullQ(Queue* q) {
    return (q->size == MAXSIZE);
}
void AddQ(Queue* q, ElementType item) {
    if (IsFullQ(q)) {
        printf("队列已满\n");
        return;
    }
    q->rear++;
    q->rear %= MAXSIZE;
    q->size++;
    q->data[q->rear] = item;
}
int IsEmptyQ(Queue* q) {
    return (q->size == 0);
}
ElementType DeleteQ(Queue* q) {
    if (IsEmptyQ(q)) {
        printf("空队列\n");
        return ERROR;
    }
    q->front++;
    q->front %= MAXSIZE; //0 1 2 3 4 5
    q->size--;
    return q->data[q->front];
}
void PrintQueue(Queue* q) {
    if (IsEmptyQ(q)) {
        printf("空队列\n");
        return;
    }
    printf("打印队列数据元素：\n");
    int index = q->front;
    int i;
    for (i = 0; i < q->size; i++) {
        index++;
        index %= MAXSIZE;
        printf("%d ", q->data[index]);
    }
    printf("\n");
}
int main(int argc, const char * argv[]) {
    Queue* q = CreateQueue();
    AddQ(q, 0);
    AddQ(q, 1);
    AddQ(q, 2);
    AddQ(q, 3);
    AddQ(q, 4);
    AddQ(q, 5);
    PrintQueue(q);
    DeleteQ(q);
    DeleteQ(q);
    DeleteQ(q);
    PrintQueue(q);
    AddQ(q, 6);
    AddQ(q, 7);
    AddQ(q, 8);
    PrintQueue(q);
    return 0;
}

2.1 链表实现的队列

c
展开代码
#include <stdio.h>
#include <stdlib.h>
#define ElementType int
#define ERROR -99 //ElementType的特殊值，标志错误
typedef struct Node {
    ElementType data;
    struct Node* next;
}QNode;
typedef struct {
    QNode* front; //指向对头节点
    QNode* rear; //指向队尾节点
}Queue;
Queue* CreateQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    if (!q) {
        printf("空间不足！\n");
        return NULL;
    }
    q->front = NULL;
    q->rear = NULL;
    return q;
}
void AddQ(Queue* q, ElementType item) {
    QNode* qNode = (QNode*)malloc(sizeof(QNode));
    if (!qNode) {
        printf("空间不足！\n");
        return;
    }
    qNode->data = item;
    qNode->next = NULL;
    if (q->front == NULL) {
        q->front = qNode;
    }
    if (q->rear == NULL) {
        q->rear = qNode;
    }
    else {
        q->rear->next = qNode;
        q->rear = qNode;
    }
}
int IsEmptyQ(Queue* q){
    return (q->front == NULL);
}
ElementType DeleteQ(Queue* q) {
    if (IsEmptyQ(q)) {
        printf("空队列\n");
        return ERROR;
    }
    QNode* temp = q->front;
    ElementType item;
    if (q->front == q->rear) { //若队列只有一个元素
        q->front = NULL;
        q->rear = NULL;
    }
    else {
        q->front = q->front->next;
    }
    item = temp->data;
    free(temp);
    return item;
}
void PrintQueue(Queue* q) {
    if (IsEmptyQ(q)) {
        printf("空队列\n");
        return;
    }
    printf("打印队列数据元素：\n");
    QNode* qNode = q->front;
    while (qNode != NULL) {
        printf("%d " , qNode->data);
        qNode = qNode->next;
    }
    printf("\n");
}
int main(int argc, const char * argv[]) {
    Queue* q = CreateQueue();
    AddQ(q, 1);
    PrintQueue(q);
    DeleteQ(q);
    PrintQueue(q);
    AddQ(q, 2);
    AddQ(q, 3);
    AddQ(q, 4);
    PrintQueue(q);
    DeleteQ(q);
    DeleteQ(q);
    PrintQueue(q);
    AddQ(q, 5);
    AddQ(q, 6);
    PrintQueue(q);
    return 0;
}

3 二叉树遍历

3.1 迭代版本

先序遍历 => A B D F E C G H I

中序遍历 => D B E F A G H C I

后序遍历 => D E F B H G I C A

在这里插入图片描述

在这里插入图片描述

迭代版本

c
展开代码
#include <stdio.h>
#include <stdlib.h>
#define ElementType char
typedef struct Node {
    ElementType data;
    struct Node *lchild;
    struct Node *rchild;
}BinaryTree;
//创建二叉树节点
BinaryTree* CreateBinaryTree(data) {
    BinaryTree* t = (BinaryTree*)malloc(sizeof(BinaryTree));
    if (!t) {
        printf("空间不足！\n");
        return NULL;
    }
    t->lchild = NULL;
    t->rchild = NULL;
    t->data = data;
    return t;
}
/*
 (1)先序遍历 递归解法
 遍历过程为：
    1.访问根节点
    2.遍历其左子树
    3.遍历其右子树
*/
void PreOrderTraversal(BinaryTree* BT) {
    if (BT) {
        printf("%c", BT->data);
        PreOrderTraversal(BT->lchild);
        PreOrderTraversal(BT->rchild);
    }
}
/*
 (2)中序遍历 递归解法
 遍历过程：
    1.遍历其左子树
    2.访问根节点
    3.遍历其右子树
*/
void InOrderTraversal(BinaryTree* BT) {
    if (BT) {
        InOrderTraversal(BT->lchild);
        printf("%c", BT->data);
        InOrderTraversal(BT->rchild);
    }
}
/*
 (3)后序遍历 递归解法
 遍历过程：
    1.遍历其左子树
    2.遍历其右子树
    3.访问根节点
*/
void PostOrderTraversal(BinaryTree* BT) {
    if (BT) {
        PostOrderTraversal(BT->lchild);
        PostOrderTraversal(BT->rchild);
        printf("%c", BT->data);
    }
}
int main(int argc, const char * argv[]) {
    BinaryTree* tree_A = CreateBinaryTree('A');
    BinaryTree* tree_B = CreateBinaryTree('B');
    tree_A->lchild = tree_B;
    BinaryTree* tree_C = CreateBinaryTree('C');
    tree_A->rchild = tree_C;
    BinaryTree* tree_D = CreateBinaryTree('D');
    tree_B->lchild = tree_D;
    BinaryTree* tree_F = CreateBinaryTree('F');
    tree_B->rchild = tree_F;
    BinaryTree* tree_E = CreateBinaryTree('E');
    tree_F->lchild = tree_E;
    BinaryTree* tree_G = CreateBinaryTree('G');
    tree_C->lchild = tree_G;
    BinaryTree* tree_I = CreateBinaryTree('I');
    tree_C->rchild = tree_I;
    BinaryTree* tree_H = CreateBinaryTree('H');
    tree_G->rchild = tree_H;
    //先序遍历 => A B D F E C G H I
    PreOrderTraversal(tree_A);
    printf("\n");
    //中序遍历 => D B E F A G H C I
    InOrderTraversal(tree_A);
    printf("\n");
    //后序遍历 => D E F B H G I C A
    PostOrderTraversal(tree_A);
    return 0;
}

3.2 用栈的遍历 先序中序后序

c
展开代码
#include <stdio.h>
#include <stdlib.h>
#define ElementType char
typedef struct Node {
    int isFirst;
    ElementType data;
    struct Node *lchild;
    struct Node *rchild;
}BinaryTree;
typedef struct StackNode {
    BinaryTree* data;
    struct StackNode* next;
}Stack;
//初始化堆栈
Stack* CreateStack() {
    Stack* s;
    s = (Stack*)malloc(sizeof(Stack));
    if (!s) {
        printf("空间不足\n");
    }
    s->next = NULL;
    return s;
}
int IsEmpty(Stack* s) {
    return (s->next == NULL);
}
//入栈
void Push(Stack* s, BinaryTree* data) {
    Stack* cell;
    cell = (Stack*)malloc(sizeof(Stack));
    if (!cell) {
        printf("空间不足\n");
    }
    cell->data = data;
    cell->next = s->next;
    s->next = cell;
}
//出栈
BinaryTree* Pop(Stack* s) {
    Stack* firstCell;
    BinaryTree* topData;
    if (IsEmpty(s)) {
        printf("空栈\n");
        return NULL;
    }
    firstCell = s->next;
    s->next = firstCell->next;
    topData = firstCell->data;
    free(firstCell);
    return topData;
}
//创建二叉树节点
BinaryTree* CreateBinaryTree(data) {
    BinaryTree* t = (BinaryTree*)malloc(sizeof(BinaryTree));
    if (!t) {
        printf("空间不足！\n");
        return NULL;
    }
    t->lchild = NULL;
    t->rchild = NULL;
    t->data = data;
    return t;
}
//先序遍历非递归遍历解法
void PreOrderTraversal(BinaryTree* BT) {
    BinaryTree* T = BT;
    Stack* s = CreateStack(); //创建并初始化栈s
    while (T || !IsEmpty(s)) {
        while (T) { //一直向左并将沿途节点压入栈
            Push(s, T);
            printf("%c", T->data);
            T = T->lchild;
        }
        if (!IsEmpty(s)) {
            T = Pop(s); //节点弹出栈
            T = T->rchild; //转向右子树
        }
    }
}
//中序遍历非递归遍历解法
void InOrderTraversal(BinaryTree* BT) {
    BinaryTree* T = BT;
    Stack* s = CreateStack(); //创建并初始化栈s
    while (T || !IsEmpty(s)) {
        while (T) { //一直向左并将沿途节点压入栈
            Push(s, T);
            T = T->lchild;
        }
        if (!IsEmpty(s)) {
            T = Pop(s); //节点弹出栈
            printf("%c", T->data);
            T = T->rchild; //转向右子树
        }
    }
}
//后序遍历非递归遍历解法
void PostOrderTraversal(BinaryTree* BT) {
    BinaryTree* T = BT;
    Stack* s = CreateStack(); //创建并初始化栈s
    while (T || !IsEmpty(s)) {
        while (T) { //一直向左并将沿途节点压入栈
            T->isFirst = 1;
            Push(s, T);
            T = T->lchild;
        }
        if (!IsEmpty(s)) {
            T = Pop(s); //节点弹出栈
            if(T->isFirst == 1) { //表示是第一次出现在栈顶
                T->isFirst = 0;
                Push(s, T);
                T = T->rchild;
            }
            else { //第二次出现在栈顶
                printf("%c", T->data);
                T = NULL;
            }
        }
    }
}
int main(int argc, const char * argv[]) {
    BinaryTree* tree_A = CreateBinaryTree('A');
    BinaryTree* tree_B = CreateBinaryTree('B');
    tree_A->lchild = tree_B;
    BinaryTree* tree_C = CreateBinaryTree('C');
    tree_A->rchild = tree_C;
    BinaryTree* tree_D = CreateBinaryTree('D');
    tree_B->lchild = tree_D;
    BinaryTree* tree_F = CreateBinaryTree('F');
    tree_B->rchild = tree_F;
    BinaryTree* tree_E = CreateBinaryTree('E');
    tree_F->lchild = tree_E;
    BinaryTree* tree_G = CreateBinaryTree('G');
    tree_C->lchild = tree_G;
    BinaryTree* tree_I = CreateBinaryTree('I');
    tree_C->rchild = tree_I;
    BinaryTree* tree_H = CreateBinaryTree('H');
    tree_G->rchild = tree_H;
    printf("先序遍历非递归遍历算法：");
    //先序遍历 => A B D F E C G H I
    PreOrderTraversal(tree_A);
    printf("\n中序遍历非递归遍历算法：");
    //中序遍历 => D B E F A G H C I
    InOrderTraversal(tree_A);
    printf("\n后序遍历非递归遍历算法：");
    //后序遍历 => D E F B H G I C A
    PostOrderTraversal(tree_A);
    return 0;
}

3.3 用队列(链表队列)进行层次遍历

层次遍历就是依照节点深度从小到大、从左到右遍历整个数

在这里插入图片描述

c
展开代码
#include <stdio.h>
#include <stdlib.h>
//树节点
typedef struct TreeNode {
    char data;
    struct TreeNode *lchild;
    struct TreeNode *rchild;
} BinaryTree;
//创建二叉树节点
BinaryTree *CreateBinaryTree(data) {
    BinaryTree *t = (BinaryTree *) malloc(sizeof(BinaryTree));
    if (!t) {
        printf("空间不足！\n");
        return NULL;
    }
    t->lchild = NULL;
    t->rchild = NULL;
    t->data = data;
    return t;
}
//队列节点
typedef struct Node {
    BinaryTree* data;
    struct Node *next;
} QNode;
typedef struct {
    QNode *front; //指向对头节点
    QNode *rear; //指向队尾节点
} Queue;
Queue *CreateQueue() {
    Queue *q = (Queue *) malloc(sizeof(Queue));
    if (!q) {
        printf("空间不足！\n");
        return NULL;
    }
    q->front = NULL;
    q->rear = NULL;
    return q;
}
void AddQ(Queue *q, BinaryTree* item) {
    QNode *qNode = (QNode *) malloc(sizeof(QNode));
    if (!qNode) {
        printf("空间不足！\n");
        return;
    }
    qNode->data = item;
    qNode->next = NULL;
    if (q->front == NULL) {
        q->front = qNode;
    }
    if (q->rear == NULL) {
        q->rear = qNode;
    } else {
        q->rear->next = qNode;
        q->rear = qNode;
    }
}
int IsEmptyQ(Queue *q) {
    return (q->front == NULL);
}
//出队
BinaryTree* DeleteQ(Queue *q) {
    if (IsEmptyQ(q)) {
        printf("空队列\n");
        return NULL;
    }
    QNode *head = q->front;//队列头
    if (q->front == q->rear) { //若队列只有一个元素
        q->front = NULL;
        q->rear = NULL;
    } else {
        q->front = q->front->next;
    }
    return head->data;
}
//输出函数
void displayNode(BinaryTree *node){
    printf("%c",node->data);
}
int main(int argc, const char *argv[]) {
    Queue *queue = CreateQueue();//队列
    BinaryTree *tree_A = CreateBinaryTree('A');
    BinaryTree *tree_B = CreateBinaryTree('B');
    tree_A->lchild = tree_B;
    BinaryTree *tree_C = CreateBinaryTree('C');
    tree_A->rchild = tree_C;
    BinaryTree *tree_D = CreateBinaryTree('D');
    tree_B->lchild = tree_D;
    BinaryTree *tree_F = CreateBinaryTree('F');
    tree_B->rchild = tree_F;
    BinaryTree *tree_E = CreateBinaryTree('E');
    tree_F->lchild = tree_E;
    BinaryTree *tree_G = CreateBinaryTree('G');
    tree_C->lchild = tree_G;
    BinaryTree *tree_I = CreateBinaryTree('I');
    tree_C->rchild = tree_I;
    BinaryTree *tree_H = CreateBinaryTree('H');
    tree_G->rchild = tree_H;
    //根结点入队
    AddQ(queue, tree_A);
    BinaryTree *head_q;//队列头的元素
    while(IsEmptyQ(queue)!=1) //队列不是空
    {
        head_q = DeleteQ(queue);
        displayNode(head_q);//队头结点出队，打印出队元素
        //将队头结点的左右孩子依次入队
        if (head_q->lchild != NULL) {
            AddQ(queue, head_q->lchild);
        }
        if (head_q->rchild != NULL) {
            AddQ(queue, head_q->rchild);
        }
    }
    return 0;
}
如果对你有用的话，可以打赏哦
打赏
ali pay
wechat pay

本文作者:Dong

本文链接:

版权声明:本博客所有文章除特别声明外，均采用 CC BY-NC。本作品采用《知识共享署名-非商业性使用 4.0 国际许可协议》进行许可。您可以在非商业用途下自由转载和修改，但必须注明出处并提供原作者链接。 许可协议。转载请注明出处！