【数据结构】24王道考研笔记——树与二叉树

这篇具有很好参考价值的文章主要介绍了【数据结构】24王道考研笔记——树与二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

五、树与二叉树

树的基本概念

树是n个结点的有限集合,n=0时,称为空树。非空树满足:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

除了根节点外,任何一个结点都有且仅有一个前驱

  • 结点的层次(深度):从上往下数
  • 结点的高度:从下往上数
  • 树的高度(深度):总共有多少层
  • 结点的度:有几个孩子(分支)
  • 树的度:各节点的度的最大值
  • 森林:m课互不相交的树的集合(m可为0,空森林)

树的性质:

  1. 结点数=总度数+1
  2. 度为m的树、m叉树的区别【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记
  3. 度为m的树第i层至多有mi-1个结点(i>=1);m叉树第i层至多有mi-1个结点(i>=1)【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记
  4. 高度为h的m叉树至多有mh-1/m-1个结点【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记
  5. 高度为h的m叉树至少有h个结点;高度为h、度为m的树至少有h+m-1个结点【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记
  6. 具有n个结点的m叉树的最小高度为向上取整 logm(n(m-1)+1)【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

二叉树的概念

基础概念

二叉树时n个结点的有限集合(n可以为0)

由一个根节点和两个互不相交的被称为根的左子树和右子树组成,左子树和右子树又分别是一棵二叉树

  1. 每个结点至多只有两棵子树
  2. 左右子树不能颠倒(二叉树是有序树)

五种形态:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

特殊二叉树:

满二叉树、完全二叉树:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

二叉排序树:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

平衡二叉树:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

常考性质

二叉树常考性质:

  • 结点性质:n0=n2+1

    【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

  • 第i层结点数

    【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

  • 高度为h时最多结点数(满二叉树)

    【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

完全二叉树常考性质:

  • 具有n个(n>0)结点的完全二叉树高度(两种推导)【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记
  • 可以由结点数n退出度为0、1、2的结点个数n0、n1、n2【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

总结:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

存储方式

二叉树的顺序存储:

#define MaxSize 100

struct TreeNode {
    int value;//结点中的数据元素
    bool isEmpty;//判断结点是否为空
};

int main()
{
    TreeNode t[MaxSize];//定义一个长度为MaxSize的数组t,按照从上至下,从左至右的顺序依次存储二叉树中的各个结点

    for (int i = 0; i < MaxSize; i++)
    {
        t[i].isEmpty = true;//初始化时所有结点标记为空
    }
}

完全二叉树中,有着如下基本操作:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

非完全二叉树使用顺序存储:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

二叉树的链式存储:

//定义储存数据类型
struct ElemType {
    int value;
};

typedef struct BiTNode {
    ElemType data;//数据域
    struct BiTNode* lchild, * rchild;//左右孩子指针
} BiTNode, * BiTree;

//初始化
void InitTree(BiTree root) {
    root = (BiTree)malloc(sizeof(BiTNode));
    root->data = { 1 };
    root->lchild = NULL;
    root->rchild = NULL;
}

//插入新结点
bool InsertNode(BiTree T, ElemType val) {
    BiTNode* p = (BiTNode*)malloc(sizeof(BiTNode));
    p->data = val;
    p->lchild = NULL;
    p->rchild = NULL;
    T->lchild = p;//作为左孩子
}

n个结点的二叉链表共有n+1个空链域

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

二叉树遍历及线索二叉树

前中后以及层次遍历

递归法:

先序遍历

//先序遍历
void PreOder(BiTree T) {
    if (T != NULL) {
        visit(T);//访问根节点
        PreOder(T->lchild);//遍历左子树
        PreOder(T->rchild);//遍历右子树
    }
}

中序遍历

//中序遍历
void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);//遍历左子树
        visit(T);//访问根节点
        InOrder(T->rchild);//遍历右子树
    }
}

后序遍历

//后序遍历
void PostOder(BiTree T) {
    if (T != NULL) {
        PostOder(T->lchild);
        PostOder(T->rchild);
        visit(T);
    }
}

非递归法:

先序遍历(需要用到辅助栈)

//先序遍历
void PreOrder2(BiTree T)
{
    SqStack S;
    InitStack(S); BiTree p = T;//初始化栈S;p是遍历指针
    while (p || !IsEmpty(S)) //栈不空或p不空时循环
    {
        if (p) //一路向左
        {
            visit(p); Push(S, p);//访问当前结点,并入栈
            p = p->lchild;//左孩子不空,一直向左走
        }
        else //出栈,并转向出栈结点的右子树
        {
            Pop(S, p);//栈顶元素出栈
            p = p->rchild;//向右子树走,p赋值为当前结点的右孩子
        } //返回while循环继续进入if-else语句
    }
}

中序遍历

//中序遍历
void InOrder2(BiTree T)
{
    SqStack S;
    InitStack(S);//初始化栈
    BiTree p = T;//p为遍历指针
    while (p || !IsEmpty(S))
    {
        if (p)
        {
            Push(S, p);//当前结点入栈
            p = p->lchild;//左孩子不空,一直向左走
        }
        else //出栈,并转向出栈结点的右子树
        {
            Pop(S, p); visit(p);//栈顶元素出栈,访问出栈结点
            p = p->rchild;//向右子树走,p赋值为当前结点的右孩子
        }//返回while循环继续进入if-else语句
    }
}

层次遍历(需要用到辅助队列)

//用于层序遍历的辅助队列
typedef struct LinkNode {
    BiTNode* data;//存的是指针而非结点
    struct LinkNode* next;
} LinkNode;

typedef struct {
    LinkNode* front, * rear;//队头队尾
} LinkQueue;

void InitQueue(LinkQueue& Q) {
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    //初始化时,front 、rear 都指向头节点
    Q.front->next = NULL;
}

bool EnQueue(LinkQueue& Q, BiTNode* x) {
    //判满?链式存储一般不需要判满,除非内存不足
    LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
    if (s == NULL)return false;
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;//新节点插入到rear之后
    Q.rear = s;//修改表尾指针
    return true;
}

bool DeQueue(LinkQueue& Q, BiTNode* x) {
    if (Q.front == Q.rear)return false;//队空
    LinkNode* p = Q.front->next;//用指针p记录队头元素
    x = p->data;//用x变量返回队头元素
    Q.front->next = p->next;//修改头节点的next指针
    if (Q.rear == p)//此次是最后一个节点出队
        Q.rear = Q.front;//修改rear指针,思考一下为什么?
    free(p); //释放节点空间
    return true;
}

bool isEmpty(LinkQueue Q) {
    return Q.front == Q.rear ? true : false;
}

//层序遍历
void levelOrder(BiTree T) {
    LinkQueue Q;//辅助队列
    InitQueue(Q);//
    BiTree p;
    EnQueue(Q, T);
    while (!isEmpty(Q)) {
        DeQueue(Q, p);//队头结点出队
        visit(p);
        if (p->lchild != NULL)
            EnQueue(Q, p->lchild);
        if (p->rchild != NULL)
            EnQueue(Q, p->rchild);
    }
}

应用:求树的深度

//求树的深度
int treeDepth(BiTree T)
{
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        int l = treeDepth(T->lchild);
        int r = treeDepth(T->rchild);
        //树的深度=Max(左子树深度,右子树深度)+1
        return l > r ? l + 1 : r + 1;
    }
}

由二叉树的遍历序列可以构造出二叉树

前序+中序:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

后序+中序:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

层序+中序:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

若没有中序遍历则不能够构造出二叉树

线索二叉树

线索二叉树的存在,方便我们能够找到某个结点的前驱以及后继

线索二叉树利用叶子结点中的空链域对前驱线索以及后继线索进行存储,并且使用ltag、rtag进行标注,tag==0表示指针指向的是孩子,tag==1表示指针指向的是“线索”

新的结构体:

struct ElemType {
    int value;
};

typedef struct ThreadNode {
    ElemType data;//数据域
    struct ThreadNode* lchild, * rchild;//左右孩子指针
    int ltag, rtag;//左右线索标志
} ThreadNode, * ThreadTree;

ThreadNode* pre = NULL;//全局变量用于暂存当前访问结点的前驱

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

利用visit函数来进行线索化的操作:

void visit(ThreadNode* q) {
    if (q->lchild == NULL) {//左子树为空,建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {//建立前驱结点的后继线索
        pre->rchild = q;
        pre->rtag = 1;
    }
    pre = q;
}

中序线索化:

//中序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T) {
    if (T != NULL) {
        InThread(T->lchild);
        visit(T);
        InThread(T->rchild);
    }
}

//创建中序线索化二叉树T
void CreatInThread(ThreadTree T) {
    pre = NULL;
    if (T != NULL) {//非空二叉树才能线索化
        InThread(T);//中序线索二叉树
        if (pre->rchild == NULL) {
            pre->rtag = 1;//处理遍历的最后最后一个结点
        }
    }
}

//中序线索化(王道教材版)
void InThread_CSKaoYan(ThreadTree p, ThreadTree& pre) {
    if (p != NULL) {
        InThread_CSKaoYan(p->lchild, pre);//递归,线索化左子树
        if (p->lchild == NULL) {//左子树为空,建立前驱线索
            p->lchild = pre;
            p->ltag = 1;
        }
        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild == p;//建立前驱结点的后及线索
            pre->rtag = 1;
        }
        pre = p;
        InThread_CSKaoYan(p->rchild, pre);
    }
}

//中序线索化二叉树(王道教材版本)
void CreatInThread_CSKaoYan(ThreadTree T) {
    ThreadTree pre = NULL;
    if (T != NULL) {
        InThread_CSKaoYan(T, pre);
        pre->rchild = NULL;//思考:为什么处理最后一个结点时没有判断rchild 是否为NULL?
        pre->rtag = 1;//答:因为最后一个结点的右孩子必为空。
    }
}

先序线索化:

//先序线索化,一边遍历一边线索化
void PreThread(ThreadTree T) {
    if (T != NULL) {
        visit(T);
        if (0 == T->ltag) {//lchild不是前驱线索
            PreThread(T->lchild);
        }
        PreThread(T->rchild);
    }
}

//创建先序线索化二叉树T
void CreatPreThread(ThreadTree T) {
    pre == NULL;
    if (T != NULL) {
        PreThread(T);
        if (pre->rchild == NULL) {
            pre->rtag = 1;//处理遍历的最后一个结点
        }
    }
}

//先序线索化(王道教程版本)
void PreThread_CSKaoYan(ThreadTree p, ThreadTree& pre) {
    if (p != NULL) {
        if (p->lchild == NULL) {
            p->lchild = pre;
            p->ltag = 1;
        }
        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild == p;//建立前驱结点的后及线索
            pre->rtag = 1;
        }
        pre = p;
        if (0 == p->ltag) {
            PreThread_CSKaoYan(p->lchild, pre);
        }
        PreThread_CSKaoYan(p->rchild, pre);
    }
}

//先序线索化二叉树(王道教材版本)
void CreatPreThread_CSKaoYan(ThreadTree T) {
    ThreadTree pre = NULL;
    if (T != NULL) {
        PreThread_CSKaoYan(T, pre);
        if (pre->rchild = NULL)//处理遍历的最后一个结点
            pre->rtag = 1;
    }
}

后序线索化:

//后序线索二叉树
void PostThread(ThreadTree T) {
    if (T != NULL) {
        PostThread(T->lchild);
        PostThread(T->rchild);
        visit(T);
    }
}

//创建后序线索二叉树T
void CreatPostThread(ThreadTree T) {
    pre == NULL;
    if (T != NULL) {
        PostThread(T);
        if (pre->rchild == NULL) {
            pre->rtag = 1;//处理遍历的最后一个结点
        }
    }
}

//后序线索化(王道教程版本)
void PostThread_CSKaoYan(ThreadTree p, ThreadTree& pre) {
    if (p != NULL) {
        PostThread_CSKaoYan(p->lchild, pre);
        PostThread_CSKaoYan(p->rchild, pre);
        if (p->lchild == NULL) {
            p->lchild = pre;
            p->ltag = 1;
        }
        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild == p;//建立前驱结点的后及线索
            pre->rtag = 1;
        }
        pre = p;
    }
}
//后序线索化二叉树(王道教材版本)
void CreatPostThread_CSKaoYan(ThreadTree T) {
    ThreadTree pre = NULL;
    if (T != NULL) {
        PostThread_CSKaoYan(T, pre);
        if (pre->rchild = NULL)//处理遍历的最后一个结点
            pre->rtag = 1;
    }
}

而通过线索二叉树找到前驱后继又是另一大问题

中序线索二叉树找后继:

//中序线索二叉树找中序后继
//找到以P为根的子树中,第一个被中序遍历的结点
ThreadNode* FirstNode(ThreadNode* p) {
    //循环找到最左下结点(不一定是叶结点)
    while (0 == p->ltag) {
        p = p->lchild;
    }
    return p;
}

//在中序线索二叉树中找到结点p的后继结点
ThreadNode* NextNode(ThreadNode* p) {
    //在右子树中最左下结点
    if (0 == p->rtag)return FirstNode(p->rchild);
    else return p->rchild;
}

//对中序线索二叉树进行中序遍历(利用线索实现的非递归算法),空间复杂度为O(1);
void InOrder(ThreadNode* T) {
    for (ThreadNode* p = FirstNode(T); p != NULL; p = NextNode(p)) {
        visit(p);
    }
}

中序线索二叉树找前驱:

//中序线索二叉树找中序前驱
//找到以p为根的子树中,最后一个被中序遍历的结点
ThreadNode* LastNode(ThreadNode* p) {
    //循环找到最右下结点(不一定是叶结点)
    while (0 == p->rtag)p = p->rchild;
    return p;
}

//在中序线索二叉树中找到结点p的前驱结点
ThreadNode* PreNode(ThreadNode* p) {
    //左下子树中最右结点
    if (0 == p->ltag)return LastNode(p->lchild);
    else return p->lchild;
}

//对中序线索二叉树进行逆向中序遍历
void RevInOrder(ThreadNode* T) {
    for (ThreadNode* p = LastNode(T); p != NULL; p = PreNode(p)) {
        visit(p);
    }
}

先序以及后序找前驱后继的思路:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

对于先序线索二叉树找前驱以及后序线索二叉树找后继都较为复杂,需要对不同情况进行分类讨论。

树、森林

树的存储结构

双亲表示法

//树——双亲表示法(顺序存储法)
#define MAX_TREE_SIZE 100

typedef struct {
    int data; //数据元素
    int parent;//双亲位置域
}PTNode;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];//双亲表示
    int n;//结点数
}PTree;

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

优点:找双亲(父节点)很方便

缺点:找孩子不方便,只能从头到尾遍历整个数组

适用于“找父亲”多“找孩子”少的应用场景,如:并查集

孩子表示法(顺序存储+链式存储结合)

//树——孩子表示法(顺序+链式存储)
struct CTNode {
    int child;//孩子节点在数组中的位置
    struct CTNode* next;//下一个孩子
};
typedef struct {
    int data; //数据元素,数据元素类型不定
    struct CTNode* firstChild;//第一个孩子
}CTBox;
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];//双亲表示
    int n, r;//结点数和根的位置
}CTree;

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

优点:找孩子很方便

缺点:找双亲(父节点)不方便,只能遍历每个链表

适用于“找孩子”多,“找父亲”少的应用场景,如:服务流程树

孩子兄弟表示法

//树——孩子兄弟表示法(链式存储)
typedef struct CSNode {
    int data; //数据域,数据类型不定
    struct CSNode* firstChild, * nextsibiling;//第一个孩子和右兄弟指针
}CSNode, * CSTree;

与二叉树类似,采用二叉链表实现,每个结点内保存数据元素和两个指针,但两个指针的含义与二叉树结点不同。

用这种表示法存储树或森林时,从存储视角来看形态上与二叉树类似

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

树、森林与二叉树的转换

树转二叉树

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

森林转二叉树

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

二叉树转树

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

二叉树转森林

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

树、森林的遍历

树的先根遍历

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

与相应二叉树的先序序列相同

树的后根遍历

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

与相应二叉树的中序序列相同

层次遍历(广度优先)用队列实现

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

森林的先序遍历

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

效果等同于依次对各个树进行先根遍历,也等同于对相应二叉树先序遍历

森林中序遍历

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

效果等同于依次对各个树进行后根遍历,也等同于对相应二叉树中序遍历

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

树与二叉树应用

哈夫曼树

带权路径长度:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

哈夫曼树定义:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

哈夫曼树构造:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

哈夫曼编码:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

并查集

利用双亲表示法的存储方式,每个子集合以一棵树表示,所有表示子集合的树,构成表示全集合的森林,根节点的双亲结点为负数

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

初始化:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

#define SIZE 10
int UFSets[SIZE];//集合元素数组

//初始化
void Initial(int S[])
{
	for (int i = 0; i < SIZE; i++)
		S[i] = -1;
}

查:

//查,找到x所属集合(返回x所属根节点)
int Find(int S[], int x)
{
	while (S[x] >= 0)
		x = S[x];
	return x;//根节点S[]小于0
}

优化查:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

//查优化,压缩路径
int Find2(int S[], int x)
{
	int root = x;
	while (S[root] >= 0) root = S[root];//循环找到根
	while (x != root) //压缩路径
	{
		int t = S[x];//t指向x的父节点
		S[x] = root;//x直接挂到根节点下
		x = t;
	}
	return root;
}

并:(并之前要先找到两个元素根节点)

//并,将两个集合根节点传入,合并为一个
void Union(int S[], int Root1, int Root2)
{
	//判断为不同集合
	if (Root1 == Root2) return;
	//将根Root2连接到另一根Root1下面
	S[Root2] = Root1;
}

优化并:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

//并优化,让小树合并到大树,用根节点的绝对值表示树的结点总数
void Union2(int S[], int Root1, int Root2)
{
	if (Root1 == Root2) return;
	if (S[Root2] > S[Root2]) //Root2更大,绝对值更小,结点数更小
	{
		S[Root1] += S[Root2];//累加结点总数
		S[Root2] = Root1;//小树合并到大树
	}
	else
	{
		S[Root2] += S[Root1];
		S[Root1] = Root2;
	}
}

优化前后对比:

【数据结构】24王道考研笔记——树与二叉树,数据结构,数据结构,考研,笔记

主要参考:王道考研课程
后续会持续更新考研408部分的学习笔记,欢迎关注。
github仓库(含所有相关源码):408数据结构笔记文章来源地址https://www.toymoban.com/news/detail-537157.html

到了这里,关于【数据结构】24王道考研笔记——树与二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构笔记(王道考研) 第一章:绪论

    大部分内容基于中国大学MOOC的2021考研数据结构课程所做的笔记,该课属于付费课程(不过盗版网盘资源也不难找。。。)。后续又根据23年考研的大纲对内容做了一些调整,将二叉排序树和平衡二叉树的内容挪到了查找一章,并增加了并查集、平衡二叉树的删除、红黑树的内

    2024年02月14日
    浏览(49)
  • 【计算机组成原理】24王道考研笔记——第二章 数据的表示和运算

    1.1 进制转换 任意进制-十进制: 二进制-八进制、十六进制: 各种进制的常见书写方式: 十进制-任意进制:(用拼凑法最快) 真值:符合人类习惯的数字(带±号的数) 机器数:正负号被“数字化” 1.2 定点数 常规计数:定点数;科学计数法:浮点数 无符号数: 有符号定

    2024年02月16日
    浏览(53)
  • 【操作系统】24王道考研笔记——第三章 内存管理

    1.基本概念 2.覆盖与交换 覆盖技术: 交换技术: 总结: 3.连续分配管理方式 单一连续分配 固定分区分配 动态分区分配 动态分区分配算法: 总结: 4.基本分页存储管理 定义: 页表: 地址转换的实现: 子问题: 逻辑地址结构: 总结: 5.基本地址变换机构 流程: 原理:

    2024年02月11日
    浏览(66)
  • 【计算机组成原理】24王道考研笔记——第四章 指令系统

    指令是指示计算机执行某种操作的命令,是计算机运行的最小功能单位。一台计算机的所有指令的集合构成该 机的指令系统,也称为指令集。 指令格式: 1.1分类 按地址码数目分类: 按指令长度分类: 按操作码长度分类: 按操作类型分类: 1.2 扩展操作码 设地址长度为n,

    2024年02月13日
    浏览(51)
  • 【操作系统】24王道考研笔记——第一章 计算机系统概述

    1.1 定义 1.2 特征 并发 (并行:指两个或多个事件在同一时刻同时发生) 共享 (并发性指计算机系统中同时存在中多个运行着的程序,共享性指系统中的资源可供内存中多个并发执行的进程共同使用) 虚拟 异步 并发和共享互为存在条件。没有并发和共享,就谈不上虚拟和异

    2024年02月12日
    浏览(80)
  • 【计算机组成原理】24王道考研笔记——第三章 存储系统

    现代计算机的结构: 1.存储器的层次结构 2.存储器的分类 按层次: 按介质: 按存储方式: 按信息的可更改性: 按信息的可保存性: 3.存储器的性能指标 1.基本组成 半导体元件原理: 存储芯片原理:存储芯片由半导体元件组成而成 不同的寻址方式: 总结: 2.SRAM和DRAM 上一

    2024年02月13日
    浏览(63)
  • 数据结构【考研笔记】

    1、基本概念 1)数据 数据是 信息的载体 ,是描述客观事物属性的数、字符及所有 能输入到计算机中并被计算机程序识别和处理的符号 的集合。数据是计算机程序加工的原料。 2)数据元素、数据项 数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据

    2024年02月12日
    浏览(48)
  • 齐鲁工业大学872数据结构考研笔记

    笔者水平有限,错误之处请指出。 官网考纲https://yjszs.qlu.edu.cn/_upload/article/files/d6/51/76dd4bc8494eb8dbf1327a9fdeaa/3d1521b3-ce94-4de3-adc6-56a2f87aa7ef.pdf 1.  数据 :是客观事物的符号表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。 2. 数据元素 :是数据的基本单位,通常

    2024年02月15日
    浏览(50)
  • 【考研复习】24王道数据结构课后习题代码|2.3线性表的链式表示

    删除结点:1、2、4 就地逆置:5、 合并链表 分解链表:10、11、 去除重复元素:12、 并集:14、15 循环链表:17、18、19、20 头插法、尾插法重点基础必掌握。 判断是否有环:21 用函数递归调用删除结点。 注意删除结点的时候可能断链。 利用函数调用的特性反向输出。 设置保

    2024年02月13日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包