数据结构学习——5

一、链表队列

queue.h

/*===============================================
*   文件名称：queue.h
*   创 建 者：青木莲华     
*   创建日期：2025年07月31日
*   描    述：链式队列
================================================*/
#ifndef __QUEUE_H__
#define __QUEUE_H__

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int data_t;
typedef struct Node
{
    data_t data;
    struct Node *next;
}node_t;

typedef struct
{
    struct Node *front,*rear;
}queue_t;

//create
queue_t *queue_create();
//empty
int is_empty(queue_t *q);
//length
int queue_length(queue_t *q);
//show
void queue_show(queue_t *q);
//en
int queue_en(queue_t *q,data_t data);
//de
data_t queue_de(queue_t *q);
#endif

queue.c

/*===============================================
*   文件名称：queue.c
*   创 建 者：青木莲华    
*   创建日期：2025年07月31日
*   描    述：链式队列
================================================*/
#include "queue.h"

//create
queue_t *queue_create()
{
    queue_t *q = (queue_t *)malloc(sizeof(queue_t));
    if(q == NULL)
        return NULL;
    node_t *head = (node_t *)malloc(sizeof(node_t));
    if(head == NULL)
    {
        free(q);
        return NULL;
    }
    head->next = NULL;
    q->front = head;
    q->rear = head;
    return q;
}
//empty
int is_empty(queue_t *q)
{
    return q->front->next == NULL;
}
//length
int queue_length(queue_t *q)
{
    int count = 0;
    node_t *p = q->front->next;
    while(p != NULL)
    {
        count++;
        p = p->next;
    }
    return count;
}
//show
void queue_show(queue_t *q)
{
    if(is_empty(q))
    {
        printf("队已空!\n");
        return;
    }
    node_t *p = q->front->next;
    while(p != NULL)
    {
        printf("%4d ",p->data);
        p = p->next;
    }
    printf("\n");
}
//en
int queue_en(queue_t *q,data_t data)
{
    node_t *new = (node_t *)malloc(sizeof(node_t));
    if(new == NULL)
        return 0;
    new->next = NULL;
    new->data = data;
    q->rear->next = new;
    q->rear = new;
    return 1;
}
//de
data_t queue_de(queue_t *q)
{
    if(is_empty(q))
    {
        printf("队已空!\n");
        return 0;
    }
    node_t *p = q->front;
    q->front = q->front->next;
    free(p);
    return q->front->data;
}

main.c

/*===============================================
*   文件名称：main.c
*   创 建 者：青木莲华 
*   创建日期：2025年07月31日
*   描    述：链式队列
================================================*/
#include "queue.h"

int main(int argc, char *argv[])
{ 
    queue_t *q = queue_create();
    if(q == NULL)
        return 0;
    for(int i = 0 ; i < 10 ; i ++)
        queue_en(q,i+1);
    queue_show(q);
    
    while(!is_empty(q))
        printf("out : %4d\n",queue_de(q));
    queue_show(q);

    queue_en(q,11);
    queue_en(q,22);
    queue_en(q,33);
    queue_de(q);
    queue_show(q);
    return 0;
}

运行截图

alt

二、二叉树

1.性质

alt

2.度 概念

alt

3.二叉树的存储

alt

完全二叉树用顺序存储

非完全二叉树用链式存储

4.代码具体实现

结构

typedef char data_t;
typedef struct Node
{
    data_t data;
    struct Node *lchild;
    struct Node *rchild;
}bitree;

(1)初始化

//create   通过键盘输入递归方式初始化树
tree_t *tree_init()
{
    data_t ch;
    scanf("%c",&ch);
    if(ch == '#')
        return NULL;
    
    tree_t *root = (tree_t *)malloc(sizeof(tree_t));
    if(root == NULL)
        return NULL;

    root->data = ch;
    root->ichild = tree_create();
    root->rchild = tree_create();
    return root;
}

(2)遍历

alt

//先序遍历
void pre_order(tree_t *root)
{
    if(root == NULL)
        return;
    printf("%c ",root->data)
    pre_order(root->lchild);
    pre_order(root->rchild);
}

//中序遍历
void mid_order(tree_t *root)
{
    if(root == NULL)
        return;
    mid_order(root->lchild);
    printf("%c ",root->data);
    mid_order(root->rchild);
}

//后续遍历
void post_order(tree_t *root);
    if(root == NULL)
        return;
    post_order(root->lchild);
    post_order(root->rchild);
    printf("%c ",root->data);
}

三、作业

1.使用非递归实现层序遍历

队列使用的是 “一、链表队列”

//层序遍历  利用队列实现
void level_order(tree_t *root)
{
    if(root == NULL)
        return;
    queue_t *q = queue_create();
    if(q == NULL)
        return;
    //先将根节点入队
    queue_en(q,root);
    tree_t *temp = NULL;
    //用循环进行入队出队操作    队为空表示所有结点遍历完毕
    while(!is_empty(q))
    {
        temp = queue_de(q);             //进行出队操作
        if(temp->lchild != NULL)        //左子结点不为空 入队
            queue_en(q,temp->lchild);
        if(temp->rchild != NULL)        //右子结点不为空 入队
            queue_en(q,temp->rchild);
        printf("%c ",temp->data);       //打印当前结点的值
    }
    printf("\n");
}

运行结果

alt

2.使用非递归实现先序遍历

//非递归 先序遍历
void pre_non_R(tree_t *root)
{
    if(root == NULL)
        return;
    stack_t *s = stack_create();
    if(s == NULL)
        return;
    tree_t *temp = NULL;                //定义接收出栈结点的指针变量
    stack_push(s,root);                 //根节点入栈
    
    while(!stack_empty(s))              //终止条件 栈为空
    {
        temp = stack_pop(s);            //出栈
        printf("%c ",temp->data);       //打印
        if(temp->rchild != NULL)
            stack_push(s,temp->rchild); //根左右 右子结点应该先压栈 先找左结点
        if(temp->lchild != NULL)
            stack_push(s,temp->lchild); //左子结点入栈,下一次循环再出栈
    }
    printf("\n");
    free(s);                            //释放空间
}

运行截图

3.非递归 中序遍历

//非递归 中序遍历
void mid_non_R(tree_t *root)
{
    if(root == NULL)
        return;
    stack_t *s = stack_create();
    if(s == NULL)
        return;
    tree_t *temp = root;                //当前操作的结点，用于将所有左子结点入栈操作
    while(temp != NULL || !stack_empty(s))              //终止条件 栈为空
    {
        while(temp != NULL)             //temp会一直往左找 找到最左侧的结点,为空时再出栈往右
        {
            stack_push(s,temp);         //入栈
            temp = temp->lchild;        //temp继续往左子结点走
        }
        temp = stack_pop(s);            //当左字节点为空则出栈，并打印，然后往右找
        printf("%c ",temp->data);
        
        temp = temp->rchild;            //左子结点找完往右找, 继续重复所有左子结点压栈
    }
    free(s);                            //释放空间
    printf("\n");
}

运行结果

alt