A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

[我的日记] 学海无涯苦作舟

© 你已成为群主 初级黑马   /  2020-1-10 13:51  /  4102 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

一、链表的实现(核心代码)
1.定义
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
2.
(1)节点头插法的说明
见《万门终身VIP》1-1页
(2)头插法代码实现
#include<stdio.h>
struct Node
{
    int data;
    struct Node *next;
};

int main()
{
    int n;
    struct Node *L,*p;
    L = (struct Node *)malloc(sizeof(struct Node));
    L->next = NULL;
    printf("请输入一个节点数据");
    scanf("%d",&n);
    while(n!=9999){
        p = (struct Node *)malloc(sizeof(struct Node));
        p->data=n;
        p->next=L->next;
        L->next=p;
        scanf("%d",&n);
    }
    return 0;
}
3.尾插法
#include<stdio.h>
struct Node
{
    int data;
    struct Node *next;
};

int main()
{
    int n;
    struct Node *L,*r,*p;
    L = (struct Node *)malloc(sizeof(struct Node));
    r = L;
    printf("请输入一个整数");
    scanf("%d",&n);
    while(n!=9999)
    {
        p = (struct Node *)malloc(sizeof(struct Node));
        p->data = n;
        r->next=p;
        r=p;
        scanf("%d",&n);
    }
    r->next = NULL;
    return 0;
}

二、栈和队列的实现(数组与链表的)

1.栈和队列的定义
(1)队列是一种先进先出的数据结构
(2)栈是一种先进后出的数据结构
2.用数据和链表实现栈
(1)用数组实现栈
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 50
typedef struct QueStack
{
    int top;
    int data[MaxSize];
};
int main()
{
    struct QueStack *s;
    InitQueStack(&s);
    int isEmpty = IsEmptyQueStack(&s);
    printf("%d \n",isEmpty);
    push(&s,6);
    push(&s,19);
    pop(&s,9);
    getTop(&s,10);
    return 0;
}
// 出栈
int pop(struct QueStack *s,int n){
    if(s->top == -1){
        return 0;
    }else{
        n = s->data[s->top--];
        printf("出栈成功 %d,当前指针移动到:%d \n",n,s->top);
        return 1;
    }
}
// 获得栈顶元素
int getTop(struct QueStack *s,int n){
    if(s->top == -1){
        return 0;
    }else{
        n = s->data[s->top];
        printf("该栈顶的元素为:%d \n",n);
    }
}
// 入栈
int push (struct QueStack *s,int n){
    if(s->top == MaxSize-1){
        return 0;
    }else{
        s->data[++(s->top)] = n;
        printf("入栈成功 %d \n",s->data[s->top]);
        return 1;
    }
}
// 初始化栈
void InitQueStack(struct QueStack *s)
{
    s->top = -1;
    printf("初始化成功%d \n",s->top);
}
// 判读栈是否为空
int IsEmptyQueStack(struct QueStack* s)
{
    if(s->top == -1)
         return 1;
    else
        return 0;
}

(2)用链表实现栈
我们知道栈的特点是先进后出,而链表中的头插法正好满足我们的需求,因为头插法后面插入的节点位于链表的开头,所以我们可以使用头插法来插入节点,在弹出节点的时候弹出链表的第一个节点即可,而第一个节点是很容易找出来的,所以可以很轻松地实现栈的压入和弹出操作;
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 50
struct Node
{
    int data;
    struct Node *next;
};

int main()
{
    // 用链标实现栈,我们都知道栈是先进后出的线性表,然后
    // 链标的头插法真好是先进后出的,所有可以用链表的头插法来模仿栈
    struct Node *L;
    L = (struct Node *)malloc(sizeof(struct Node));
    L->next = NULL;
    for(int i = 0; i < 6; i ++)
    {
        push(L,i);
    }
    int n;

    printf("%d \n",Getlength(L));
    pop(L,n);
    Getlength(L);
    return 0;
}


int Getlength(struct Node *head)
{
    int i=0;
    struct Node *p;
    if(head->next==NULL)
        return 0;
    else
    {
        p=head->next;
        printf("第%d个链表的数据是%d \n",i,p->data);
        while(p && p->next != NULL)
        {
            i++;
            p=p->next;
            printf("第%d个链表的数据是%d \n",i,p->data);
        }
        return i;
    }
}

// 出栈
int pop(struct Node *L,int n)
{
    printf("将%d弹出栈 \n",n);
    struct Node *p;
    if(L->next == NULL)
    {
        return 0;
    }
    else
    {
        p = L->next;
        n = p->data;
        L->next = p->next;
        free(p);
        return 1;
    }
}
// 人栈
void push(struct Node *L,int n)
{
    printf("将%d压入栈 \n",n);
    struct Node *p = (struct Node *)malloc(sizeof(struct Node));
    p->data = n;
    p->next = L->next;
    L->next = p;
}



3.用数组和链表实现队列
(1)用数组实现队列
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MaxSize 50
typedef struct Queue
{
    int data[MaxSize];
    int front; // 队首元素在数组中的下标
    int rear; // 队尾元素在数组中的下标
};
int main()
{
    int n;
    struct Queue *q;
    q = (struct Queue *)malloc(sizeof(struct Queue));
    InitQueue(q);
    enQueue(q,1);
    enQueue(q,2);
    enQueue(q,3);
    enQueue(q,6);
    enQueue(q,10);
    traverseQuene(q);
    outQueue(q,2);
    traverseQuene(q);
    int A = is_fullQueue(q);
    printf("%d",A);
    destroyQueue(q);
    return 0;

}
// 初始化队列
void InitQueue(struct Queue *q)
{
    q->front = 0;
    q->rear = 0;
}
// 判断队列是否为满队列
int is_fullQueue(struct Queue *q)
{
    if((q->rear + 1) % MaxSize == q->front)
        return 1;
    else
        return 0;
}
// 判断是否是队空
int is_emptyQueue(struct Queue *q)
{
    if(q->front == q->rear)
        return 1;
    else
        return 0;
}
// 入队
int enQueue(struct Queue *q,int n)
{
    if(is_fullQueue(q) == 1)
    {
        return 0;
    }
    else
    {
        printf("入队%d成功 \n",n);
        q->data[q->rear] = n;
        q->rear = (q->rear + 1)%MaxSize;
        return 1;
    }
}
// 出队
int outQueue(struct Queue *q,int n)
{
    if(is_emptyQueue(q) == 1)
    {
        return 0;
    }
    else
    {
        n = q->data[q->front];
        q->front = (q->front + 1)%MaxSize;
        printf("删除的元素是:%d\n",q->data[q->front-1]);
        return 1;
    }
}
// 遍历队列
void traverseQuene(struct Queue *q)
{
    int i=q->front;
    while(i!=q->rear)
    {
        i=(i+1)%MaxSize;
        printf("%d ",q->data[i-1]);
    }
    printf("\n");
}

// 销毁队列
void destroyQueue(struct Queue *q)
{
    free(q);
    q=NULL;
}

(2)用栈实现队列
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MaxSize 50
typedef struct Node
{
    int data;
    struct Node *next;
};
typedef struct Queue
{
    struct Node *front,*rear;
};
int main()
{
    int i = 5,j = 5;
    struct Queue *q = (struct Queue *)malloc(sizeof(struct Queue));
    InitQueue(q);
    printf("开始入队:\n");
    while(i--)
    {
        printf("元素%c入队,队列为:",i);
        insertQueue(q,i);
        display(q);
    }
    printf("开始出队:\n");
    while(j--)
    {
        printf("第%d个元素出队,队列为:",5-j);
        deleteQueue(q);
        display(q);
    }
    printf("\n");
    return 0;
}
// 初始队列
void InitQueue(struct Queue *q)
{

    q->front = q->rear = NULL;
}
// 判断队列是否为空
int is_emptyQueue(struct Queue *q)
{
    if(q->front == NULL)
        return 1;
    else
        return 0;
}
// 入队
void insertQueue(struct Queue *q,int data)
{
    struct Node *node = (struct Node *)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;// 尾插法,插入元素指向空
    if(q->rear == NULL)
    {
        q->front = node;
        q->rear = node;
    }
    else
    {
        // 让node成为当前尾部节点的下一个节点
        q->rear->next = node;
        // 尾部指针指向node
        q->rear = node;
    }
}
// 出队 删除首元素
void deleteQueue(struct Queue *q)
{
    struct Node *node = q->front;
    if(is_emptyQueue(q) == 1)
    {
        return;
    }
    // 是否只有一个元素
    if(q->front == q->rear)
    {
        q->front = NULL;
        q->rear = NULL;
    }
    else
    {
        q->front = q->front->next;
        free(node);
    }
}
void display(struct Queue *q)
{
    struct Node *n = (struct Node *)malloc(sizeof(struct Node));
    n = q->front;
    if(n == NULL)
    {
        return;
    }
    while(n!=NULL)
    {
        printf("%d",n->data);
        n = n->next;
    }
    printf("\n");

}



4.循环队列(为什么)

为什么要使用循环队列?

    防止空间的避免浪费  
为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。

什么是队列队空?

队满:
if((q->rear + 1) % MaxSize == q->front)
队空:
q->front == q->rear


本周的作业要求:

1.给出循环队列的存储结构定义。
2.完成循环队列的基本操作函数。
         1)      初始化循环队列;
         2)      建立循环队列;
         3)      实现入队和出队操作;
         4)     采用下面两种方法实现对满和队空的判断操作:

   方法一:修改队满条件,浪费一个元素空间,队满时数组中只有一个空闲单元(必做);
   方法二:设置标志flag,当front==rear且flag=0时为队空,当front==rear且flag=1时为队满(必做);

三、树的定义(出度、入度、叶节点、树的高度)

二叉树的前中后序遍历,以及非递归算法;P340-341
typedef struct TreeNode{
    int data; // 数据元素
    struct TreeNode *lchild,*rchild; // 左右孩子指针
    int ltag,rtag;  // 左右线索标志
}TreeNode,*BitTree;
1.二叉树的前序遍历
// 前序遍历
void PreOrder(BitTree *BT)
{
    if(BT != NULL)
    {
        printf("%C",BT->data) // 访问更节点
        PreOrder(BT->lchild);  // 递归遍历左子树
        PreOrder(BT->rchild);  // 递归遍历右子树
    }
}

// 层次序遍历
void LevelOrder(BitTree BT){
    BitTree *Q[stackSize];
    int rear,front;
    rear = 0;
    front = 0;
    BitTree *p = BT;    //队列初始化
    Q[rear++] = p;      //p是遍历指针,跟进队
    while(rear != front){
        p = Q[front];
        front = (front + 1)%queueSize;
        printf("%c",p->data); //访问
        if(p->lchild != NULL){  // 若有左子对进队
            Q[rear] = p->lchild;
            rear = (rear + 1)%queueSize;
        }
        if(p->rchild != NULL){  // 若有右子对进队
            Q[rear] = p->rchild;
            rear = (rear + 1)%queueSize;
        }
    }
}

2.二叉树的中序遍历
// 中序遍历
void InOrder(BitTree *BT)
{
    if(BT != NULL)
    {
        InOrder(BT->lchild);  // 递归遍历左子树
        printf("%c",BT->data);// 访问跟节点
        InOrder(BT->rchild);   // 递归遍历右子树
    }
}


// 中序遍历非递归算法
#define stackSize 20 // 预定义栈大小,相当于树高
void InOrder(BitTree BT){
    BitTree *S[stackSize];
    int top = -1;
    BitTree *p = BT;    // p是遍历指针
    do{
        while(p != NULL){   // 遍历左子树节点
            S[++top] = p;
            p = p->lchild;
        }
        if(top > -1){       // 栈不空时退栈
            p=S[top--];
            printf("%c",p->data);// 退栈,访问
            p=p->rchild;    // 遍历指针进到右子树的节点
        }
    }while(p != NULL || top > -1)

}

3.二叉树的后序遍历
// 后序遍历
void PostOrder(BitTree *BT)
{
    if(BT != NULL)
    {
        PostOrder(BT->lchild);   // 递归遍历左子树
        PostOrder(BT->rchild);   //递归遍历右子树
        printf("%c",BT->data);  // 访问根节点
    }
}

// 后序遍历的非递归算法
void PostOrder(BitTree BT){
    BitTree *S[stackSize];
    int top = -1;
    BitTree *p = BT,*pre = NULL;    // p是遍历指针,pre是前驱指针
    do{
        while(p != NULL){   // 左子树进栈
            S[++top] = p;
            p = p->lchild;  // 向最左下节点走下去
        }
        if(top > -1){
            p = S[top];  // 用p元素记忆栈顶
            if(p->rchild != NULL && p->rchild != pre){
                p = p->rchild;
            }else{
                printf("%c",p->data);   // 访问
                pre = p;    // 记忆刚访问过的接电脑
                p = NULL;   // 转遍历右子树或访问跟节点
                top--;
            }
        }
    }while(p != NULL || top != -1);
}


四、Huffmun实现,求最小权值

Huffmun树的代码:
#include<stdio.h>
#define MAX 30
#define inf 100000000
typedef char valType;
typedef int wghType;
struct HFMnode
{
    valType data;
    wghType weight;
    int parent;
    int lchild;
    int rchild;
};
struct HFMcode
{
    char code[MAX];
    int start;
};
void createHFMtree(HFMnode *node,int n)
{
    int i,m1,m2,l,r;
    for(i=n+1; i<=2*n-1; i++)
    {
        m1=m2=inf;
        l=r=0;
        int k;
        for(k=1; k<=i-1; k++)
            if(node[k].parent==0)
            {
                if(node[k].weight<m1)
                {
                    m2=m1;
                    r=l;
                    m1=node[k].weight;
                    l=k;
                }
                else if(node[k].weight<m2)
                {
                    m2=node[k].weight;
                    r=k;
                }
            }
        node.weight=node[l].weight+node[r].weight;
        node.lchild=l;
        node.rchild=r;
        node[l].parent=i;
        node[r].parent=i;
    }
}
void createHFMcode(HFMnode *node, HFMcode *hcode,int n)
{
    int i;
    for(i=1; i<=n; i++)
    {
        HFMcode d;
        d.start=n;
        int num=i;
        int father=node[num].parent;
        while(father!=0)
        {
            if(node[father].lchild==num)
                d.code[d.start--]='0';
            else
                d.code[d.start--]='1';
            num=father;
            father=node[num].parent;
        }
        hcode=d;
    }
}
void printHFMcode(HFMnode * node,HFMcode * hcode,int n)
{
    int i;
    for(i=1; i<=n; i++)
    {
        printf("%c: ",node.data);
        for(int k=hcode.start+1; k<=n; k++)
            putchar(hcode.code[k]);
        puts("");
    }
}
void main()
{
    HFMnode node[2*MAX];
    HFMcode hcd[MAX];
    int n;
    scanf("%d\n",&n);
    for(int i=1; i<=n; i++)
    {
        printf("输入第%d个节点的值\n",i);
        scanf("%c",&node.data);
        printf("输入它的权重\n");
        scanf("%d\n",&node.weight);
    }
    for(int i=1; i<=2*n-1; i++)
        node.parent=node.lchild=node.rchild=0;
    createHFMtree(node,n);
    createHFMcode(node,hcd,n);
    printHFMcode(node,hcd,n);
}


定义:
即求带权路径长度,WPL最小的二叉树被称为最优二叉树;

https://blog.csdn.net/qq_29519041/article/details/81428934


五、平衡二叉树(AVL)

1、判断是否平衡?
父节点的右子树层数减去左子树层数,当取值为-1,0,1时,该节点为平衡点;
如下图:

2、判断哪个是不平衡节点?
当该节点数大于等于2或者小于等于-2时,为不平衡节点;
如下图:






3、依据图示辨别是LL旋转、LR旋转、RR旋转、RL旋转;
旋转注意点:

(1)LL旋转或RR旋转注意点:
1)

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马