精华内容
下载资源
问答
  • 计算机考研数据结构总结.pdf
  • 考研数据结构算法总结
  • 考研期间总结数据结构代码大全,包括列表,栈,队列,树,图,查找,字符串,排序等数据结构的实现C语言实现版本,需要的朋友可以参考一下。
  • 考研数据结构经典算法总结,很全的,很强大。
  • 分析《数据结构》重难点(顺着大纲整理分析各项知识点,主要以理论为主),考点用阴影标注,注意内容用下划线标出。
  • 西安理工大学考研数据结构真题
  • 数据结构总结(针对考研)

    千次阅读 2019-08-06 14:23:45
    1. 深刻理解数据结构的概念,掌握数据结结构的“三要素”: 逻辑结构、 物理(存储)结构 在这种结构上所定义的运算。 2. 掌握计算语句频度和估算算法时间复杂度的方法。 掌握常见算法、经典算法的时间复杂度和空间...

    第一章

    1. 深刻理解数据结构的概念,掌握数据结结构的“三要素”:
    • 逻辑结构、
    • 物理(存储)结构
    • 在这种结构上所定义的运算。
    2. 掌握计算语句频度和估算算法时间复杂度的方法。
    • 掌握常见算法、经典算法的时间复杂度和空间复杂度。

    第二章 线性表

    大纲要求
    1. 线性表的逻辑
    2.线性表的顺序存储结构
    3.线性表的链式存储结构
    • 单链表
      链表头节点的俩个优点:
      1. 由于开始节点位置被存放在头节点的指针域中,所以在链表的第一个位置的上的操作就和在表的其它位置上的操作一致,无须特殊处理。
      2. 无论链表是否为空,其头指针是指向头节点的非空指针(空表中头结点的指针域为空),因此空表和非空表的处理也就统一了。
    • 其它形式的链表:
      • 循环链表、
        最后一个结点的指针域的指针又指回第一个节点的链表。
        和单链表的差异仅仅在于,判断链表中的最后一个结点的条件不再是“后继是否为空”,而是“后继是否为头节点”
        特点:

        1. 对于单链表只能从头节点开始遍历整个链表,而对于单循环链表,则可以从表中任意结点开始遍历整个链表。
        2. 有事对于链表常做的操作是在表尾、表头进行,此时可以改变一下链表的标识方法,不用头指针而用一个指向尾结点的指针R来标识,可以使得操作效率得以提高。
        3. 在做链表合并和分裂时,如果不是必须从链表头开始,则可以直接在链表指针处合并,时间复杂度可达O(1)。
      • 双向链表、双向循环链表

        • 对于前驱的操作方便
        • 双向循环链表 空表时 头节点的next指向自己,头结点prior也指向自己。
        • 缺点:存储密度更低
        • 特点:
          • 从某个结点出发到其直接前驱结点或直接后继结点,时间复杂度均为O(1)。
          • 查找第i个结点、向第i个结点插入或删除第i个结点,都要区分是哪个方向。
          • 如果是双向循环链表,修改指针要同时考虑在前驱环链和后继环链上的修改。
          • 某个结点的直接前驱的直接后继,或它的直接后继的直接前驱,即为该结点本身。
      • 静态链表
        借助数组来描述线性表的链式存储结构,结点也有数据域data和指针域next,与前面所见的链表中的指针不同的是,这里的指针式结点的相对地址(数组的下标),称之为静态指针。
        静态链表适用于不支持“指针”的高级语言,或者最大元素数固定但插入、删除操作频繁的链表应用中。有关基于静态链表上的线性表的操作基本与动态链表相同,除了一些描述方法有些区别外,算法思路是相同的。

        特点:

        • 所有数据元素均存储在一个连续的空间段,但是相邻俩个元素不一定处于相邻的空间;
        • 修改指针域即可完成插入和删除操作,不需要移动数据元素,但是也不能随机访问静态链表中的元素;
        • 一次性分配所有存储空间,插入、删除时无需再向操作系统中申请或释放空间,但也限制了最大表长。
      • 顺序表和链表的各自的优缺点以及适用的场合.

      • t

    顺序表和链表的比较:

    1.顺序表和链表各有优缺点。
    顺序存储有点:

    1. 方法简单,各种高级语言中都有数组,容易实现。
    2. 不用为表示结点间的逻辑关系而增加额外的存储开销。
    3. 顺序表具有按元素序号随机访问的特点。

    缺点:
    4. 在顺序表中做插入删除操作时,平均移动大约表中一半的元素,因此对n较大的顺序表效率低。
    5. 需要预先分配足够大的存储空间。估计过大,可能会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。

    链表中的优缺点与顺序表相反。
    在实际中怎样选取存储结构?
    1. 基本存储的考虑
      顺序表在程序之前必须明确规定它的存储规模,也就是说事先对“MAX_SIZE”要有合适的设定,过大造成浪费,过小造成溢出,可见线性表的长度或存储规模难以估计时,不宜采用顺序表;
      链表不用事先估计处处规模,但链表的存储密度较低。显然链式存储结构的存储密度是小于1倍。

    2. 基于运算的考虑
      在顺序表中按序号访问ai 的时间性能时O(1)。而链表中按序号访问的时间性能O(n),所以如果经常做的运算时按序号访问数据元素,显然顺序表优于链表;而在顺序表中做插入、删除时平均移动表中一半的元素,当数据元素的信息量较大且表较长时,这一点是不应忽视的,在链表中作插入、删除。虽然也要找插入位置,但操作主要是比较操作,从这个角度考虑显然后者优于前者。

    3. 基于环境的考虑
      顺序表容易实现,任何高级语言中都有数组类型,链表的操作是基于指针的,相对来讲,前者简单些,也是对用户考虑的有一个因素。
      总之,俩种存储结构各有长短,选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储。而频繁做插入删除的即动态较强的线性表适宜算则链式存储。

    本章重点
    1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中表示这俩种关系的俩类不同的存储结构是顺序存储结构和链式存储结构。
    2. 熟练掌握这俩类存储结构的描述方法,以及线性表的各种基本操作的实现。重点掌握:初始化、查找、插入、删除、遍历、逆置、合并、分解等操作
    3. 能够从时间和空间复杂度的角度综合比较线性表俩种存储结构的不同特点及其适用场合。
    展开全文
  • 408计算机考研数据结构常用算法背诵,经典常考算法代码,适合考试前冲刺背诵。预祝考研成功!
  • 数据结构考研总结

    2021-10-17 22:20:05
    数据结构基本概念 基本概念和术语 术语 定义 数据 数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合 数据元素 数据元素是数据的基本单位,...

    绪论

    数据结构基本概念

    基本概念和术语

    术语定义
    数据数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合
    数据元素数据元素是数据的基本单位,通常作为一个整体进行考虑和处理,含有多个数据项
    数据项是构成数据元素的不可分割的最小单位
    数据对象具有相同性质的数据元素的集合,是数据的一个子集
    数据类型一个值的集合和定义在此集合上的一组操作的总称{原子类型、结构类型、抽象数据类型}
    数据结构相互之间存在一种或多种特定关系的数据元素的集合

    数据类型

    数据类型定义
    原子类型其值不可再分的数据类型
    结构类型其值可以再分解为若干成分的数据类型
    抽象数据类型ADT抽象数据组织及与之相关的操作

    抽象数据类型的定义格式

    ADT 抽象数据类型名{//抽象数据类型定义格式
    	数据对象:<数据对象的定义>		//自然语言
    	数据关系:<数据关系的定义>		//自然语言
    	基本操作:<基本操作的定义>
    }ADT 抽象数据类型名;
    
    //基本操作的定义格式
    基本操作名(参数表)	//参数表中赋值参数只提供输入值,引用参数以&打头,可提供输入值和返回操作结果
        初始条件:<初始条件描述>
        操作结果:<操作结果描述>
    

    数据结构三要素

    逻辑结构

    定义:逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据。

    分类:

    • 线性结构:一般线性表、受限线性表(栈和队列)、线性表推广(数组)
    • 非线性结构:集合结构、树结构、图结构

    存储结构

    定义:存储结构是指数据结构在计算机中的表示,也称物理结构

    分类:

    存储结构定义优点缺点
    顺序存储把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现随机存取,占用空间少使用一整块相邻的存储单元,产生较多碎片
    链式存储不要求逻辑上相邻的元素在物理位置上也相邻,借助指示元素存储地址的指针来表示元素之间的逻辑关系不会出现碎片,充分利用所有存储单元需要额外空间,只能顺序存取
    索引存储在存储元素信息的同时,还建立附加的索引表。检索速度快附加的索引表需要额外空间。增删数据修改索引表时花费时间
    散列存储根据元素的关键字直接计算出该元素的存储地址,又称哈希(Hash)存储。检索、增加和删除结点的操作很快可能出现元素存储单元的冲突,解决冲突会增加时间和空间开销

    数据的运算

    定义:施加在数据上的运算包括运算的定义和实现。定义是针对逻辑结构的,指出运算的功能;运算的实现是针对存储结构的,指出运算的具体操作步骤。

    算法和算法评价

    算法的定义、特性和评价标准

    • 定义:算法是针对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。
    • 特性:输入、输出、确定性、有穷性、可行性
    • 评价标准
      • 正确性:正确结果
      • 可读性
      • 健壮性:输入数据非法时,能够适当的作出反应或相应处理,不会产生莫名其妙的输出结果
      • 高效性:时间和空间

    算法效率的度量

    • 算法效率分为时间效率和空间效率
    • 定义

    T ( n ) = O ( f ( n ) ) , S ( n ) = O ( g ( n ) ) T(n)=O(f(n)),S(n)=O(g(n)) T(n)=O(f(n)),S(n)=O(g(n))

    • 函数的渐进的界 O ( g ( n ) ) O(g(n)) O(g(n))

      (存在正数c和 n 0 n_0 n0使得对于一切 n ≥ n 0 n\geq n_0 nn0), 0 ≤ f ( n ) ≤ c g ( n ) 0\leq f(n)\leq cg(n) 0f(n)cg(n)

    • 算法复杂度分析步骤

      1. 确定表示输入规模的参数
      2. 找出算法的基本操作
      3. 检查基本操作的执行次数是否只依赖于输入规模。这决定是否需要考虑最差、平均以及最优情况下的复杂性
      4. 对于非递归算法,建立算法基本操作执行次数的求和表达式;对于递归算法,建立算法基本操作执行次数的递推关系及其初始条件
      5. 利用求和公式和法则建立一个操作次数的闭合公式,或者求解递推公式,确定增长的阶
    • 递归算法两类复杂度分析


      T ( n ) = { O ( 1 ) n = 1 a T ( n − 1 ) + f ( n ) n > 1 T(n)= \begin{cases} O(1) & n=1\\ aT(n-1)+f(n)& n>1 \end{cases} T(n)={O(1)aT(n1)+f(n)n=1n>1

      T ( n ) = a n − 1 T ( 1 ) + ∑ i = 2 n a n − i f ( i ) T(n)=a^{n-1}T(1)+\sum_{i=2}^n a^{n-i}f(i) T(n)=an1T(1)+i=2nanif(i)


      T ( n ) = { O ( 1 ) n = 1 a T ( n b ) + f ( n ) n > 1 T(n)= \begin{cases} O(1) & n=1\\ aT(\frac nb)+f(n)& n>1 \end{cases} T(n)={O(1)aT(bn)+f(n)n=1n>1

      T ( n ) = n l o g b a T ( 1 ) + ∑ j = 0 l o g b n − 1 a j f ( n b j ) T(n)=n^{log_b a}T(1)+\sum_{j=0}^{log_b n-1}a^jf(\frac n{b^j}) T(n)=nlogbaT(1)+j=0logbn1ajf(bjn)

    线性表

    线性表的定义和基本操作

    定义

    线性表是具有相同数据类型的n个数据元素的有限序列。其中n为表长,当n=0时线性表是一个空表。若用L命名线性表,则其一般表示为 L = ( a 1 , a 2 , . . . , a i , a i + 1 , . . . , a n ) L=(a_1,a_2,...,a_i,a_{i+1},...,a_n) L=(a1,a2,...,ai,ai+1,...,an)

    特点

    • a 1 a_1 a1是唯一的“第一个”数据元素,又称表头元素
    • a n a_n an是唯一的“最后一个”数据元素,又称表尾元素
    • 除第一个元素外,每个元素有且仅有一个直接前驱。除最后一个元素外,每个元素有且仅有一个直接后继。

    基本操作

    InitList(&L):初始化表。构造一个空的线性表
    Length(L):求表长
    LocateElem(L,e):按值查找操作
    GetElem(L,i):按位查找操作
    ListInsert(&L,i,e):插入操作
    ListDelete(&L,i,&e):删除操作,并用e返回删除元素的值
    PrintList(L):输出操作
    Empty(L):判断操作
    DestoryList(&L):销毁操作
    

    线性表的顺序表示

    顺序表的定义

    线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点是表中元素的逻辑顺序与物理顺序相同。

    • 线性表A中第i个元素的内存地址:&(A[0])+i*sizeof(ElemType)
    • 一维数组可以是静态分配,也可以动态分配
    • 静态分配时,数组的大小和空间事先已经固定,一旦空间占满,再加入新的数据就会产生溢出,进而导致程序崩溃
    • 动态分配时,存储数组的空间是在程序执行过程中通过动态存储分配语句分配的,一旦数据空间占满,就另外开辟一块更大的存储空间,用以替换原来的存储空间。

    静态分配的实现

    #define MaxSize 50				//定义线性表的最大长度
    typedef struct{
    	ElemType data[MaxSize];		//顺序表的元素
    	int length;					//顺序表的当前长度
    }SqList;						//顺序表的类型定义
    

    动态分配的实现

    #define InitSize 100			//表长度的初始定义
    typedef struct{				
    	ElemType *data;				//指示动态分配数组的指针
    	int MaxSize,length;			//数组的最大容量和当前个数
    }SqList;						//动态分配数组顺序表的类型定义
    //C的初始动态分配语句
    L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
    free(L);
    //C++的初始动态分配语句
    L.data = new ElemType[InitSize];
    delete L;
    

    特点

    • 随机访问
    • 存储密度高
    • 插入删除需要移动大量元素

    顺序表的实现

    注意算法对i的描述是第i个元素,它是以1为起点的

    bool ListInset(SqList &L,int i,ElemType e){
        if(i<1||i>L.length+1) return false;	//判断插入位置是否有效
        if(L.length>=MaxSize) return false;	//判断存储空间是否已满
        for(int j=L.length;j>=i;j--) L.data[j] = L.data[j-1];	//将插入位置之后的元素后移
        L.data[i-1] = e;		//赋值
        L.length++;				//线性表长度+1
        return true;
    }
    
    bool ListDelete(SqList &L,int i,ElemType &e){
        if(i<1||i>L.length)	return false;	//判断值是否有效
        e = L.data[i-1];		//赋值,用于返回
        for(int j = i;j<L.length;j++) L.data[j-1] = L.data[j];	//删除元素后的元素前移
        L.length--;	//线性表长度-1
        return true;	
    }
    
    int LocateElem(SqList L,ElemType e){
        int i;
        for(i=0;i<L.length;i++)
            if(L.data[i] == e)
                return i+1;			//注意这里的下标
        return 0;
    }
    

    线性表的链式表示

    单链表

    • 结点描述:
    typedef struct LNode{		//定义单链表结点类型
    	ElemType data;			//数据域
        struct LNode *next;		//指针域
    }LNode, *LinkList;		//LinkList为指向结构体LNODE的指针类型
    
    • 通常用头指针来标示一个单链表。
    • 有头结点或者没头结点之分
    • 头结点的作用
      • 便于首元结点的处理,对链表的第一个数据元素的操作与其他数据元素相同,无需特殊处理
      • 便于空表与非空表的统一处理:头指针永远不为空

    单链表的实现

    LinkList List_HeadInsert(LinkList &L){
        LNode *s;int x;
        L=(LinkList)malloc(sizeof(LNode));//创建头结点
        L->next = NULL;					//初始为空链表
        scanf("%d",&x);
        while(x!=9999){
            s = (LNode*)malloc(sizeof(LNode));
            s->data = x;
            s->next = L->next;
            L->next = s;
            scanf("%d",&x);
        }
        return L;
    }
    
    LinkList List_TailInsert(LinkList &L){
        int x;
        L = (LinkList)malloc(sizeof(LNode));
        LNode *s,*r=L;			//r为表尾指针
        scanf("%d",&x);
        while(x!=9999){
            s = (LNode *)malloc(sizeof(LNode));
            s->data = x;
            r->next = s;
            r = s;
            scanf("%d",&x);
        }
        r->next = NULL;				//尾结点指针置空
        return L;
    }
    
    LNode *LocateElem(LinkList L,ElemType e){//按值查找
    	LNode *p = L->next;
        while(p!=NULL&&p->data!=e)
            p = p->next;
        return p;
    }
    

    双链表

    typedef struct DNode{
    	ElemType data;
        struct DNode *prior,*next;	//前驱和后继指针
    }DNode,*DLinkList;
    

    循环链表

    • 循环单链表
    • 循环双链表

    静态链表

    借助数组来描述线性表的链式存储结构,结点也有数据域data和指针域next,这里的指针是节点的相对地址(数组下标),又称游标

    #define MaxSize 50
    typedef struct{
    	ElemType data;
        int next;
    }SLinkList[MaxSize];
    

    栈和队列

    栈的基本概念

    栈的定义

    • 栈是只允许在一端进行插入或删除操作的线性表。后进先出LIFO
    • 栈顶(Top):线性表允许进行插入删除的那一端。
    • 栈底(Bottom):固定的,不允许进行插入和删除的另一端
    • 空栈:不包含任何元素的空表

    栈的基本操作

    InitStack(&S):初始化一个空栈S
    StackEmpty(S):判断一个栈是否为空,若栈S为空则返回true,否则返回false
    Push(&S,x):进栈,若栈S未满,则将x加入使之成为新栈顶
    Pop(&S,&x):出栈,若栈S非空,则弹出栈顶元素,并用x返回
    GetTop(S,&x):读取栈顶元素,若栈S非空,则用x返回栈顶元素
    DestroyStack(&S):销毁栈,并释放栈S占用的存储空间
    

    栈的顺序存储结构

    顺序栈的实现

    利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,并附设一个指针top指示当前栈顶元素的位置

    #define MaxSize 50			//定义栈中元素最大个数
    typedef struct{
        Elemtype data[MaxSize];	//存放栈中元素
        int top;//栈顶指针
    }
    
    • 栈顶指针:S.top,初始时设置S.top=-1;栈顶元素:S.data[S.top]
    • 进栈操作:栈不满时,栈顶指针先加1,再送值到栈顶元素
    • 出栈操作:栈非空时,先取栈顶元素值,再将栈顶指针减1
    • 栈空条件:S.top==-1;栈满条件:S.top==MaxSize-1;栈长:S.top+1

    共享栈

    利用栈底位置相对不变的特性,可让两个顺序栈共享一个一维数组空间,将两个栈的栈底分别设置在共享空间的两端,两个栈顶共享空间的中间延伸。

    • 两个栈的栈顶指针都指向栈顶元素

    • top0=-1时0号栈为空,top1=MaxSize1号栈为空

    • top1-top0==1为栈满

    • 0号栈进栈时top0先加1再赋值,1号栈进栈时top1先减1再赋值;出栈是刚好相反

    栈的链式存储结构

    采用链式存储的栈称为链栈,链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。这里规定链栈没有头结点,Lhead指向栈顶元素

    typedef struct Linknode{
        ElemType data;//数据域
        struct Linknode *next;//指针域
    } *LiStack;//栈类型定义	
    

    队列

    队列的基本概念

    队列的定义

    • 队列简称队,也是一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。
    • 向队列中插入元素称为入队进队
    • 删除元素称为出队离队
    • 操作的特性是先进先出

    队列常见的基本操作

    InitQueue(&Q):初始化队列,构造一个空队列Q
    QueueEmpty(Q):判队列空
    EnQueue(&Q,x):入队,若队列Q非满,将x加入,使之成为新的队尾
    DeQueue(&Q,&x):出队,若队列Q非空,删除队头元素,并用x返回
    GetHead(Q,&x):读队头元素,若队列Q非空,则将队头元素赋值给x
    

    队列的顺序存储结构

    队列的顺序存储

    队列的顺序实现是指分配一块连续的存储单元存放队列中的元素,并附设两个指针:队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置

    #define MaxSize 50//定义队列中元素的最大个数
    typedef struct{
    	ElemType data[MaxSize];//存放队列元素
    	int front,rear;//队头指针和队尾指针
    } SqQueue;
    
    • 初始状态:Q.front==Q.rear==0
    • 进队操作:队不满时,先送值到队尾元素,再将队尾指针加1
    • 出队操作:队不空时,先取队头元素值,再将队头指针加1

    循环队列

    将顺序队列臆造为一个环状的空间,即把存储队列元素的表从逻辑上视为一个环,称为循环队列。当队首指针Q.front=MaxSize-1后,再前进一个位置就自动到0,这可以利用除法取余运算%来实现

    • 初始状态:Q.front=Q.rear=0
    • 队首指针进1:Q.front=(Q.front+1)%MaxSize
    • 队尾指针进1:Q.rear=(Q.rear+1)%MaxSize
    • 队列长度:(Q.rear+MaxSize-Q.front)%MaxSize
    • 出队入队时:指针都按顺时针方向进1

    判断循环队列队空或队满的三种方式

    1. 牺牲一个单元来区分队空和队满,入队时少用一个队列单元,约定以“队头指针在队尾指针的下一位置作为队满的标志”

      • 队满条件:(Q.rear+1)%MaxSize==Q.front
      • 队空条件:Q.front=Q.rear
      • 队列中元素的个数:(Q.rear-Q.front+MaxSize)%MaxSize
    2. 类型中增设表示元素个数的数据成员。

      • 队空条件:Q.size==0
      • 队满条件:Q.size==MaxSize
    3. 类型中增设tag数据成员,以区分是队满还是队空。

      • tag=0时,若因删除导致Q.front==Q.rear,则为队空

      • tag=1时,若因插入导致Q.front==Q.rear,则为队满

    队列的链式存储结构

    队列的链式存储

    队列的链式表示称为链队列,它实际是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点,尾指针指向队尾结点。

    typedef struct{//链式队列结点
    	ElemType data;
    	struct LinkNdoe *next;
    }LinkNode;
    typedef struct{//链式队列
    	LinkNode *front,*rear;//队列的队头和队尾指针
    }LinkQueue;
    

    通常将链式队列设计成一个带头结点对的单链表,这样插入和删除就统一了

    双端队列

    双端队列是指允许两端都可进行入队和出队操作的队列,其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端。

    • 输出受限的双端队列:允许在一端进行插入和删除,另一端只允许插入的双端队列
    • 输入受限的双端队列:允许在一端进行插入和删除,另一端只允许删除的双端队列

    栈和队列的应用

    栈在括号匹配中的应用

    • 初始设置一个空栈,顺序读入括号
    • 若是右括号,则或者置于栈顶的最急迫期待得以消解,或者是不合法的情况
    • 若是左括号,则作为一个新的更急迫的期待压入栈中
    • 算法结束时,栈为空,否则括号序列不匹配

    栈在表达式求值中的应用

    后续表达式计算方式

    顺序扫描表达式的每一项,然后根据它的类型作出如下相应操作:若该项是操作数,则将其压入栈中;若该项是操作符<op>,则连续从栈中退出两个操作数YX,形成运算指令X<op>Y,并将计算结果重新压入栈中。当表达式的所有项扫描并处理完毕后,栈顶存放的就是最后的结果

    中缀表达式转换为前缀或后缀表达式的手工做法
    • 按照运算符的优先级对所有的运算单位加括号
    • 转换为前缀或后缀表达式。前缀把运算符移动到对应的括号前面,后缀把运算符移动到对应的括号后面
    • 把括号去掉
    中缀表达式转换为后缀表达式的算法思路
    • 从左向右开始扫描中缀表达式
    • 遇到数字时,加入后缀表达式
    • 遇到运算符时
      • 若为(,入栈
      • 若为),则依次把栈中的运算符加入后缀表达式,直到出现(,从栈中删除(
      • 若为除括号外的其他运算符,当其优先级高于除(外的栈顶运算符时,直接入栈。否则从栈顶开始,依次弹出比当前处理的运算符优先级高和优先级相等的运算符,直到一个比它优先级低的或遇到一个左括号为止。

    栈在递归中的应用

    可以将递归算法转换为非递归算法。通常需要借助栈来实现这种转换

    队列在层次遍历中的应用

    1. 根节点入队
    2. 若队空,则结束遍历;否则重复3操作
    3. 队列中第一个结点出队,并访问之。若其没有左孩子,则将左孩子入队,若其有左孩子,则将其右孩子入队,返回2

    队列在计算机系统中的应用

    • 解决主机与外部设备之间速度不匹配的问题
    • 解决由多用户引起的资源竞争问题

    特殊矩阵的压缩存储

    数组的定义

    数组是由n个相同类型的数据元素构成的有限序列,每个数据元素成为一个数据元素,每个元素在n个线性关系中的序号称为该元素的下标,下标的取值范围称为数组的维界

    数组是线性表的推广。一维数组可视为一个线性表;二维数组可视为其元素也是定长线性表的线性表。

    数组的存储结构

    多维数组的映方法:按行优先和按列优先

    矩阵的压缩存储

    指为多个值相同的元素只分配一个存储空间,对零元素不分配存储空间。其目的是节省存储空间

    稀疏矩阵

    矩阵中非零元素的个数远远小于矩阵元素的个数

    使用三元组(行、列、值)或十字链表法存储,失去了随机存取特性

    串的定义和实现

    串的定义

    • (String)是由零个或多个字符组成的有限序列。记为 S = ′ a 1 a 2 . . . a n ′ S='a_1a_2...a_n' S=a1a2...an

    • 串中任意多个连续的字符组成的子序列称为该串的子串

    • 包含子串的串称为主串

    • 由一个或多个空格组成的串称为空格串

    串的存储结构

    定长顺序存储表示

    用一组地址连续的存储单元存储串值的字符序列

    #define MAXLEN 255//预定义最大串长为255
    typedef struct{
    	char ch[MAXLEN];//每个分量存储一个字符
    	int length;//串的实际长度
    }SString;
    

    堆分配存储表示

    堆分配存储仍然以一组地址连续的存储单元存放串值的字符序列,但他们的存储空间是在程序执行过程中动态分配得到的

    typedef struct{
    	char *ch;//按串分配存储区,ch指向串的基地址
    	int length;//串的长度
    }HString;
    

    C语言中,存在一个称之为的自由存储区,并用malloc()free()函数来完成动态存储管理

    利用malloc()为每个新产生的串分配一块实际串长所需要的存储空间,若分配成功,则返回一个指向起始地址的指针,称为串的基地址,这个串由ch指针来指示;若分配失败,则返回NULL。已分配的空间可用free()释放掉

    块链存储表示

    类似于线性表的链式存储结构,也可采用链表方式存储串值。由于串的特殊性,在具体实现时,每个节点即可以存放一个字符,也可以存放多个字符,每个节点称为,整个链表称为块链结构

    串的基本操作

    StrAssign(&T,chars):赋值操作。把串T赋值为chars
    StrCopy(&T,S):复制操作。由串S复制得到串T
    StrEmpty(S):判空操作。若S为空串,则返回TRUE,否则返回FALSE
    StrCompare(S,T):比较操作,S>T则返回值>0;k若S=T,返回0,否则返回<0
    StrLength(S):求串长
    SubString(&Sub,S,pos,len):求子串。用Sub返回串S的第pos个字符起长度为len的子串
    Concat(&T,S1,S2):串联接。用T返回S1和S2的联接
    Index(S,T):定位操作
    ClearString(&S):清空
    DestroyString(&S):销毁串
    

    串的模式匹配

    简单的模式匹配算法BF

    子串的定位操作通常称为串的模式匹配,它求的是子串在主串中的位置

    KMP算法

    基础概念

    • 前缀:除最后一个字符以外,字符串的所有头部子串
    • 后缀:除第一个字符外,字符串的所有尾部子串
    • 部分匹配值PM:字符串的前缀和后缀的最长相等前后缀长度

    算法原理

    编号描述12345
    S字符abcac
    PM子串右移位数=已匹配的字符数-对应的部分匹配值:Move=(j-1)-PM[j-1]00010
    next(PM右移一位)子串右移位数:Move=(j-1)-next[j],子串的比较指针回退到:j=next[j]+1-10001
    next=next+1在子串的第j个字符与主串发生失配时,则跳到子串的next[j]位置重新与主串当前位置进行比较01112

    next[]推导方法

    • n e x t [ j ] = { 0 j = 1 m a x { k ∣ 1 < k < j 且 ′ p 1 . . . p k − 1 ′ = ′ p j − k + 1 . . . p j − 1 ′ } 当 此 集 合 不 空 时 1 其 他 情 况 (next[ ]推导公式) next[j]= \begin{cases} 0 & j=1\\ max\{k|1<k<j且'p_1...p_{k-1}'='p_{j-k+1}...p_{j-1}'\}& 当此集合不空时 \\ 1& 其他情况 \end{cases} \tag{next[ ]推导公式} next[j]=0max{k1<k<jp1...pk1=pjk+1...pj1}1j=1(next[ ])

    • next的推导步骤,next[j]=k,求next[j+1]

      next[j]=k表明 p 1 . . . p k − 1 = p j − k + 1 . . . p j − 1 p_1...p_{k-1}=p_{j-k+1}...p_{j-1} p1...pk1=pjk+1...pj1

      1. p k = p j p_k=p_j pk=pj,则next[j+1]=next[j]+1
      2. p k ≠ p j p_k \neq p_j pk=pj。用前缀 p 1 . . . p k p_1...p_k p1...pk去跟后缀 p j − k + 1 . . . p j p_{j-k+1}...p_j pjk+1...pj匹配,则当 p k ≠ p j p_k \neq p_j pk=pj是应将 p 1 . . . p k p_1...p_k p1...pk向右滑动至以第next[k]个字符与 p j p_j pj比较,如果 p n e x t [ k ] p_{next[k]} pnext[k] p j p_j pj还是不匹配,那么需要寻找长度更短的相等前后缀,下一步继续用 P n e x t [ n e x t [ k ] ] P_{next[next[k]]} Pnext[next[k]] p j p_j pj比较,直到找到k'=next[next...[k]]满足条件 ′ p 1 . . . p k ′ ′ = ′ p j − k ′ + 1 . . . p j ′ 'p_1...p_{k'}'='p_{j-k'+1}...p_{j}' p1...pk=pjk+1...pj,则next[j+1]=k'+1

    说明

    • 为什么next[1]=0:当模式串中的第一个字符与主串的的当前字符比较不相等时,next[1]=0,表示模式串应该右移一位,主串当前指针后移一位,再和模式串的第一个字符进行比较
    • 为什么要取max{k}:当主串的第i个字符与模式串的第j个字符失配时,主串i不回溯,则假定模式串的第k个字符与主串的第i个字符比较,k应满足条件 1 < k < j 且 ′ p 1 . . . p k − 1 ′ = ′ p j − k + 1 . . . p j − 1 ′ 1<k<j且'p_1...p_{k-1}'='p_{j-k+1}...p_{j-1}' 1<k<jp1...pk1=pjk+1...pj1。为了不使向右移动丢失可能的匹配,右移距离应该取最小,由于 j − k j-k jk表示右移距离,所以取 m a x { k } max\{k\} max{k}

    KMP算法的进一步优化

    nextval[],如果出现了 p j = p n e x t [ j ] p_j=p_{next[j]} pj=pnext[j],则将next[j]修正为next[ next[j] ],直到两者不相等

    树与二叉树

    树的定义

    • 有且仅有一个特定的称为根的结点
    • n > 1 n>1 n>1时,其余结点可分为 m m m个互不相交的有限集 T 1 , T 2 , . . . , T m T_1,T_2,...,T_m T1,T2,...,Tm,其中每个集合本身又是一棵树,并且称为根的子树

    基本术语

    祖先、子孙、双亲、孩子、兄弟

    结点的度、树的度

    分支结点、叶子节点

    节点的深度、高度、层次

    有序树和无序树

    路径和路径长度

    森林

    树的性质

    • 树中的节点数等于所有结点的度数之和加1
    • 总结点数= n 0 + n 1 + n 2 + . . . + n m n_0+n_1+n_2+...+n_m n0+n1+n2+...+nm
    • 总分支数= 1 n 1 + 2 n 2 + . . . + m n m 1n_1+2n_2+...+mn_m 1n1+2n2+...+mnm
    • 总结点数=总分支数+1

    二叉树

    二叉树的定义及其主要特性

    定义

    每个节点至多只有两棵子树,并且二叉树的子树有左右之分,不能颠倒

    几个特殊的二叉树

    • 满二叉树:一棵高度为h,且含有 2 h − 1 2^h-1 2h1个结点的二叉树称为满二叉树,除叶子结点外每个结点度数为2
    • 完全二叉树:每个结点都与同等高度的满二叉树有同样的编号
      • i ≤ ⌊ n / 2 ⌋ i\leq \lfloor n/2 \rfloor in/2,则结点i为分支结点,否则为叶子结点
      • 2 i ≤ n 2i\leq n 2in时,结点i的左孩子编号为 2 i 2i 2i,否则无左孩子
      • 2 i + 1 ≤ n 2i+1\leq n 2i+1n时,结点i的右孩子编号为 2 i + 1 2i+1 2i+1,否则无右孩子
      • 结点i所在的层次为 ⌊ l o g 2 i ⌋ + 1 \lfloor log_2i \rfloor +1 log2i+1
      • 叶子结点只可能在层次最大的两层上出现,对于最大层次中的叶子结点,都依次排列在该层最左边的位置上
      • 若有度为1的节点,则只可能有一个,且只有左孩子没有右孩子
      • 若n为奇数,则每个分支结点都有左孩子和右孩子;若n为偶数,则编号最大的分支结点只有左孩子,没有右孩子
    • 二叉排序树:左子树上所有节点的关键字小于根节点的关键字;右子树上的所有节点的关键字均大于根节点的关键字
    • 平衡二叉树:树上任一节点的左子树和右子树的深度之差不超过1

    二叉树的性质

    • 非空二叉树上的叶子结点数等于度为2的结点数+1,即 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1

    二叉树的存储结构

    顺序存储结构

    将完全二叉树上编号为i的结点元素存储在一维数组下标为i-1的分量中

    注意:这种存储结构建议从数组下标1开始存储树中的结点,若从数组下标0开始存储,则计算其孩子结点时与之前描述的计算公式不一致,在书写程序时需要注意。

    链式存储结构

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

    n个结点的二叉链表中,含有n+1个空链域

    二叉树的遍历和线索二叉树

    二叉树的遍历

    二叉树的遍历是按照某条搜索路径访问树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。共有先序遍历(NLR)、中序(LNR)、后续(LRN)三中遍历方法

    递归遍历算法

    void PreOrder(BiTree T){//PreOrder-先序、InOrder-中序、PostOrder-后序
    	if(T!=NULL){
    		visit(T);//访问根结点
    		PreOrder(T->lchild);//遍历访问左子树
    		PreOrder(T->rchlid);//遍历访问右子树
    	}
    }
    

    非递归遍历算法

    • 先序遍历
    void PreOrder2(BiTree T){
        InitStack(S);BiTree p=T;
        while(p||!IsEmpty(S)){
            if(p){
                visit(p);Push(S,p);
                p = p->lchild;
            }
            else{
                Pop(S,p);
                p = p->rchild;
            }
        }
    }
    
    • 中序遍历
    void Inorder2(BiTree T){
        InitStack(S);BiTree p = T;//初始化S,p是遍历指针
        while(p||!IsEmpty(S)){
            if(p){//一路向左
                Push(S,p);//当前结点入栈
                p = p->lchild;//左孩子不空,一直往左走
            }
            else{//出栈,并转向出栈结点的左子树
                Pop(S,p);visit(p);//栈顶元素出栈,访问出栈结点
                p = p->rchild;//向右子树走
            }
        }
    
    }
    
    • 后序遍历
    void PostOrder(BiTree T){
        InitStack(S);
        P = T;
        r = NULL;
        while(p||!IsEmpty(S)){
            if(p){					//走到最左边
                push(S,p);
                p = p->lchild;
            }
            else{							//向右
                GetTop(S,p);				//读栈顶结点(非出栈)
                if(p->rchild&&r->rchild!=r)	//若右子树存在,且未被访问过
                    p = p->rchild;			//转向右
                else{						//否则,弹出结点并访问
                    pop(S,p);				//将结点弹出
                    cisit(p->data);			//访问该结点
                    r = p;					//记录最近访问过的结点
                    p = NULL;				//结点访问完,重置p指针
                }
            }//else
        }//while
    }
    
    • 层次遍历
    void LevelOrder(BiTree T){
        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);
        }
    }
    

    由遍历序列构造二叉树

    由二叉树中序遍历结果和前序、后序、层次中的一个组合,就可唯一确定一棵二叉树

    线索二叉树

    线索二叉树的基本概念

    在含n个结点的二叉树中,有n+1个空指针。引入线索二叉树正是为了加快查找结点前驱和后继的速度。

    规定:若无左子树,令lchild指向其前驱结点;若无右子树,令rchild指向其后继结点

    lchildltagdatartagrchild

    l c h i l d = { 0 , l c h i l d 域 指 示 结 点 的 左 孩 子 1 , l c h i l d 域 指 示 结 点 的 前 驱 r c h i l d = { 0 , r c h i l d 域 指 示 结 点 的 右 孩 子 1 , r c h i l d 域 指 示 结 点 的 后 继 lchild= \begin{cases} 0,&lchild域指示结点的左孩子\\ 1,&lchild域指示结点的前驱 \end{cases}\\ rchild= \begin{cases} 0,&rchild域指示结点的右孩子\\ 1,&rchild域指示结点的后继 \end{cases} lchild={0,1lchildlchildrchild={0,1rchildrchild

    typedef struct ThreadNode{
    	ElemType data;
        struct ThreadNode *lchild,*rchild;
        int ltag,rtag;
    }ThreadNode,*ThreadTree;
    

    中序线索二叉树的构造

    线索化的实质就是遍历一次二叉树

    中序线索二叉树的遍历

    在对其进行遍历时,只要先找到序列中的第一个节点,然后依次找结点的后继,直至后继为空。在中序线索二叉树中找结点后继的规律是:若其右标志为“1”,则右链为线索,指示其后继,否则遍历右子树中第一个访问的结点为其后继。

    先序线索二叉树和后序线索二叉树

    后序线索二叉树上找后继时需要知道结点双亲,即需采用带标志域的三叉链表作为存储结构。

    树、森林

    树的存储结构

    双亲表示法

    采用一组连续空间来存储每个结点,同时在每个结点中增设一个伪指针,指示其双亲结点在数组中的位置。

    根节点的下标为0,其伪指针域为-1

    该存储结构利用了每个结点只有唯一双亲对的性质,可以很快的得到每个结点的双亲结点,但求结点的孩子需要遍历整个结构。

    dataparent_pos

    孩子表示法

    将每个结点的孩子结点都用单链表链接起来形成一个线性结构

    这种存储方式寻找子女的操作非常直接,而寻找双亲的操作需要遍历n个结点中孩子结点指针域指向的n个孩子链表

    孩子兄弟表示法

    又称二叉树表示法。孩子兄弟表示法使每个结点包括三部分内容:结点值、指向结点第一个孩子结点的指针,及指向结点下一个兄弟结点的指针。

    datafirstchildnextsibling

    树、森林与二叉树的转化

    • 树转换为二叉树

      • 规则:左孩子右兄弟。每个结点左指针指向它的第一个孩子,右指针指向它在树中的相邻右兄弟

      • 画法:1.在兄弟结点之间加一连线;2.对每个结点,只保留它与第一个孩子的连线,而与其他孩子的连线全部抹掉;3.以树为轴心,顺时针旋转45°

      • 特点:根无右子树

    • 森林转换二叉树

      • 规则:先将森林中的每棵树转换为二叉树;把第二棵树的根作为第一课树根的右兄弟,以此类推
      • 画法:1.森林中的每棵树转换为相应的二叉树2.每棵树的根也可视为兄弟关系,在每棵树的根之间加一根连线;3.以第一棵树的根为轴心顺时针旋转45°
      • 特点:森林中每棵树的根节点从第二个开始依次连接到前一棵树的根的右孩子,因此最后一棵树的根节点的右指针为空。另外,每个非终端节点,其所有孩子结点在转换后,最后一个孩子的右指针也为空。
    • 二叉树转换为森林

      • 若二叉树非空,则二叉树的根及其左子树为第一棵树的二叉树形式,故将根的右链断开。二叉树根的右子树又可视为由除第一棵树外的森林转换后的二叉树。

    树和森林的遍历

    树的遍历

    • 先根遍历
    • 后根遍历

    森林的遍历

    • 先序遍历森林
      • 访问森林中第一棵树的根节点
      • 先序遍历第一棵树的根节点的子树森林
      • 先序遍历除去第一棵树后剩余的树构成的森林
    • 中序遍历森林(又称后根遍历)
      • 中序遍历森林中第一课树的根节点的子树森林
      • 访问第一课树的根结点
      • 中序遍历除去第一棵树后剩余的树构成的森林

    树与二叉树的应用

    二叉排序树BST

    • 二叉排序树的定义

      • 左子树上所有节点的关键字小于根节点的关键字;右子树上的所有节点的关键字均大于根节点的关键字
    • 二叉排序树的查找、插入、构造

    • 二叉排序树的剔除

      • 若被删除结点z是叶子结点,则直接删除
      • 若结点z只有一棵左子树或右子树,则让z的子树成为z父节点的子树,替代z的位置
      • 若结点z有左、右两棵子树,则令z的直接后继替代z,然后从二叉排序树中删去这个直接后继,这样就转换成了上面的两种情况
    • 二叉排序树的查找效率分析

      • O ( l o g 2 n ) ( 平 衡 二 叉 树 ) O(log_2n)(平衡二叉树) O(log2n)~ O ( n ) O(n) O(n)
      • A S L a ASL_a ASLa:平均查找长度

    平衡二叉树

    • 定义

      • 任意结点的左右子树高度差的绝对值不超过1的二叉排序树
    • 二叉排序树的插入

    情况具体
    LL平衡旋转(右单旋转)
    RR平衡旋转(左单旋转)
    LR平衡旋转(先左后右双旋转)
    RL平衡旋转(先右后左双旋转)
    • 平衡二叉树的查找
      • 含有n个结点的平衡二叉树的最大深度为 O ( l o g 2 n ) O(log_2n) O(log2n),平均查找长度为 O ( l o g 2 n ) O(log_2n) O(log2n)
    • 平衡二叉树结点数的递推关系 n h = 1 + n h − 1 + n h − 2 , n 0 = 0 , n 1 = 1 , n 2 = 2 n_h=1+n_{h-1}+n_{h-2},n_0=0,n_1=1,n_2=2 nh=1+nh1+nh2,n0=0,n1=1,n2=2, n h n_h nh为构造此高度的平衡二叉树所需的最少结点数

    哈夫曼树和哈夫曼编码

    定义

    • 带权路径长度: W P L = ∑ i = 1 n w i l i WPL=\sum_{i=1}^nw_il_i WPL=i=1nwili

    • 含有n个带权结点的二叉树中,带权路径长度WPL最小的二叉树称为哈夫曼树

    哈夫曼树的构造

    1. 将n个结点分别作为n棵仅含有一个结点的二叉树,构成森林F

    2. 构造一个新结点,从F中选取两棵根结点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左、右子树上根结点的权值之和

    3. F中删除刚才选出的两棵树,同时将新得到的树加入F

    4. 重复2-3步骤

    哈夫曼树特点

    • 每个初始节点最终都成为叶结点
    • 构造过程中新建了n-1个结点,哈夫曼树中结点总数为2n-1
    • 不存在度为1的节点

    哈夫曼编码

    • 固定长度编码:对每个字符用相等长度的二进制位表示

    • 可变长度编码:允许对不同字符用不等长的二进制位表示

    • 前缀编码:没有一个编码是另一个编码的前缀

    • 使用哈夫曼树得到哈夫曼编码:默认为左边为0,右边为1(不唯一,没明确规定)

    图的基本概念

    图的定义

    G G G由顶点集 V V V和边集 E E E组成,记为 G = ( V , E ) G=(V,E) G=(V,E),其中 V ( G ) V(G) V(G)表示图 G G G中顶点的有限非空集; E ( G ) E(G) E(G)表示图 G G G中顶点之间的关系集合。 V = { v 1 , v 2 , . . . , v n } V=\{v_1,v_2,...,v_n\} V={v1,v2,...,vn}, ∣ V ∣ |V| V表示顶点个数, E = { ( u , v ) ∣ u ∈ V , v ∈ V } E=\{(u,v)|u \in V,v\in V\} E={(u,v)uV,vV}, ∣ E ∣ |E| E表示图 G G G中边的条数

    基本术语

    • 有向图
    • 无向图
    • 简单图、多重图
    • 完全图
    • 子图
    • 连通、连通图和连通分量
    • 强连通图、强连通分量
    • 生成树、生成森林
    • 顶点的度、入度和出度
    • 边的权和网
    • 稠密图、稀疏图
    • 路径、路径长度和回路
    • 简单路径、简单回路
    • 距离
    • 有向树

    图的存储及基本操作

    • 必须完整、准确地反映顶点集合边集的信息

    邻接矩阵法

    • 一个一维数组存储图中顶点的信息
    • 一个二维数组存储图中边的信息,称为邻接矩阵
    • 设图 G G G的邻接矩阵为 A A A, A n A^n An的元素等于从顶点i到j的长度为n的路径数目

    邻接表法

    • 顶点表结点

      边表的头指针和顶点的数据信息采用顺序存储

    顶点域边表头指针
    datafirstarc
    • 边表结点

      对每个顶点 v i v_i vi建立一个单链表,第 i i i个单链表中的结点表示依附于顶点 v i v_i vi的边,这个单链表为顶点 v i v_i vi边表

    邻接点域指针域
    adjvexnextarc
    • 若存储的是无向图,空间复杂度为 O ( ∣ V ∣ + 2 ∣ E ∣ ) O(|V|+2|E|) O(V+2E);若为有向图,空间复杂度为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(V+E)

    十字链表

    • 有向图的一种链式存储结构
    • 对应于有向图中的每条弧有一个结点,对应于每个顶点也有一个结点
    • 弧结点
    尾域头域链域->弧头相同的下一条弧链域->弧尾相同的下一条弧弧信息
    tailvexheadvexhlinktlinkinfo
    • 顶点结点
    数据第一条出弧第一条入弧
    datafirstinfirstout

    邻接多重表

    • 无向图的链式存储结构
    • 与邻接表的区别是,同一条边在邻接多重表中只有一个结点
    • 边结点
    标志域依附的结点下一条依附于ivex的边依附的结点下一条依附于jvex的边边信息
    markivexilinkjvexjlinkinfo
    • 顶点结点
    数据第一条依附于该顶点的边
    datafirstedge

    图的基本操作

    Adjacent(G,x,y):判断图G是否存在边<x,y>
    Neighbors(G,x):列出图G中与结点x邻接对的边
    InsertVertex(G,x):在图G中插入顶点x
    DeleteVertex(G,x):从图G中删除顶点x
    AddEdge(G,x,y):若边<x,y>不存在,则向图G中添加该边
    RemoveEdge(G,x,y):若边<x,y>存在,则从图G中删除该边
    FirstNeighbor(G,x,y):求图G中顶点x的第一个邻接点,若有则返回顶点号。否则返回-1
    NextNeighbor(G,x,y):假设图G中顶点y是顶点x的一个邻接点,返回除y外顶点x的下一个邻接点的顶点号,若没有返回-1
    Get_edge_value(G,x,y):获取图G中边<x,y>的权值
    Set_edge_value(G,x,y,v):设置图G中边<x,y>对应的权值为v
    

    图的遍历

    • 图的遍历是从图中某一顶点出发,按照某种搜索方法沿着图中的对边对图中所有顶点访问且只访问一次。

    广度优先算法

    Breadth-Frist-Search,BFS

    • 基本思想

      首先访问起始顶点 v v v,接着由 v v v出发,依次访问v的各个未访问过的邻接顶点 w 1 , w 2 , . . . , w i w_1,w_2,...,w_i w1,w2,...,wi,然后一次访问 w 1 , w 2 , . . . , w i w_1,w_2,...,w_i w1,w2,...,wi的所有未被访问的邻接顶点。

      换句话说,BFS是以v为起始点,由近及远依次访问和v有路径相通且路径长度为1,2,…的顶点

    bool visited[MAX_VERTEX_NUM];//访问标记数组
    void BFSTraverse(Graph G){	//对图G进行广度优先遍历
        for(i=0;i<G.vexnum;i++)
            visited[i] = FALSE;
        InitQueue(Q);
        for(i=0;i<G.vexnum;++i)
            if(!visited[i])		//对每个连通分量调用一次BFS
                BFS(G,i);
    }
    void BFS(Graph G,int v){//从顶点v出发,广度优先遍历图G
        visit(v);
        visited[v] = TRUE;
        EnQueue(Q,v);
        while(!isEmpty(Q)){
            DeQueue(Q,v);
            for(w=FirstNeighbor(G,v);w>=0;w=Neighbor(G,v,w))
                if(!visited[w]){
                    visit(w);
                    visited[w] = TRUE;
                    EnQueue(Q,w);
                }
        }
    }
    

    深度优先搜索

    Depth-First-Search,DFS

    • 基本思想

      首先访问图中某一起始顶点 v v v,然后由 v v v出发,访问与 v v v邻接且未被访问的任一顶点 w 1 w_1 w1,再访问与 w 1 w_1 w1邻接且未被访问的任一顶点,重复上述过程

    bool visited[MAX_VERTEX_NUM];
    void DFSTraverse(Graph G){
    	for(v=0;v<G.vexnum;++v)
            visited[v] = FALSE;
        for(v=0;v<G.vexnum;++v)
            if(!visited[v])
    			DFS(G,v);        
    }
    void DFS(Graph G,int v){
        visit(v);
        visited[v] = TRUE;
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            if(!visited[w]){
                DFS(G,w);
            }
    }
    

    性能

    性能广度优先搜索/深度优先搜索
    空间复杂度$O(
    时间复杂度-邻接矩阵$O(
    时间复杂度-邻接表$O(
    生成树广度深度优先生成树,邻接表不唯一,邻接矩阵唯一

    图的应用

    最小生成树

    求一个带权连通图的最小生成树Minimum-Spanning-Tree,MST

    Prim算法

    • 基本思想

      • 初始时从图中任取一顶点加入树T,此时树中只含有一个顶点

      • 之后选择一个与当前T中顶点集合距离最近的顶点,且加入后不能出现环,并将该顶点和相应的边加入T,每次操作后T中的顶点数和边数都增1。

      • 重复直到加满

    • 时间复杂度: O ( ∣ V ∣ 2 ) O(|V|^2 ) O(V2)

    Kruskal算法

    • 基本思想
      • 初始时为只有n个顶点而无边的非连通图T,每个顶点自成一个连通分量
      • 按照边的权值由小到大,加入到非连通图T中,不能形成环
      • 重复直到加满
    • 时间复杂度: O ( ∣ E ∣ l o g ∣ E ∣ ) O(|E|log|E|) O(ElogE)

    最短路径

    Dijkstra算法求单源最短路径

    • 辅助数组

      • 集合S:记录以求得的最短路径的顶点
      • dist[]:记录从源点 v 0 v_0 v0到其他各顶点当前的最短路径长度
      • path[]path[i]表示从源点到顶点i之间的最短路径的前驱结点。可用于回溯找最短路径
    • 算法步骤

      1. 初始化:集合S初始化为{0},dist[]的初始值dist[i]=arcs[0][i]

      2. 从顶点集合V-S中选出 v j v_j vj,满足 d i s t [ j ] = M i n { d i s t [ i ]   ∣ v i ∈ V − S } dist[j]=Min\{dist[i] \ |v_i \in V-S\} dist[j]=Min{dist[i] viVS},令 S = S ∪ { j } S=S\cup\{j\} S=S{j}

      3. 根据公式修改从 v 0 v_0 v0出发到集合V-S上任一顶点 v k v_k vk可达的最短路径长度

        dist[j]+arcs[j][k]<dist[k],则更新

      4. 重复步骤2-3操作共n-1

    • 时间复杂度: O ( ∣ V ∣ 2 ) O(|V|^2) O(V2)

    Floyd算法求个定点之间最短路径

    • 算法描述

      • 定义一个n阶方阵 A ( − 1 ) , A ( 0 ) , . . . , A ( n − 1 ) A^{(-1)},A^{(0)},...,A^{(n-1)} A(1)A(0)...,A(n1),其中 A ( − 1 ) [ i ] [ j ] = a r c s [ i ] [ j ] A^{(-1)}[i][j]=arcs[i][j] A(1)[i][j]=arcs[i][j],

      • 根据递推公式重复n次,计算出 A ( 0 ) , . . . , A ( n − 1 ) A^{(0)},...,A^{(n-1)} A(0)...,A(n1)

        A ( k ) [ i ] [ j ] = M i n { A ( k − 1 ) [ i ] [ j ] , A ( k − 1 ) [ i ] [ k ] + A ( k − 1 ) [ k ] [ j ] } , k = 0 , 1 , . . , n − 1 A^{(k)}[i][j]=Min\{A^{(k-1)}[i][j],A^{(k-1)}[i][k]+A^{(k-1)}[k][j]\},k=0,1,..,n-1 A(k)[i][j]=Min{A(k1)[i][j],A(k1)[i][k]+A(k1)[k][j]},k=0,1,..,n1

        其中, A ( 0 ) [ i ] [ j ] A^{(0)}[i][j] A(0)[i][j]是从顶点 v i v_i vi v j v_j vj、中间路径是 v 0 v_0 v0的最短路径的长度, A ( k ) [ i ] [ j ] A^{(k)}[i][j] A(k)[i][j]是从顶点 v i v_i vi v j v_j vj、中间顶点的序号不大于k的最短路径的长度

    • 时间复杂度 O ( ∣ V ∣ 3 ) O(|V|^3) O(V3)

    有向无环图描述表达式

    有向无环图DAG

    有向无环图是描述含有公共子式的表达式的有效工具,可实现对相同子式的共享,从而节省存储空间

    拓扑排序

    • AOV网:若用AVG表示一个工程,其顶点表示活动,用有向边 < V i , V j > <V_i,V_j> <Vi,Vj>表示活动 V i V_i Vi必须先于活动 V j V_j Vj进行的这样一种关系,则将这种有向图称为顶点表示活动的网络

    • 拓扑排序:在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序

      • 每个顶点出现且只出现一次
      • 若顶点A在序列中排在顶点B的前面,则在图中不存在从顶点B到顶点A的路径
    • 拓扑排序算法

      1. AOV网中选择一个没有前驱的顶点并输出
      2. 从网中删除该顶点和所有以它为起点的有向边
      3. 重复1-2,直到当前AOV网为空
    • 时间复杂度 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(V+E)

    • 逆拓扑排序

      1. AOV网中选择一个没有后继的顶点并输出
      2. 从网中删除该顶点和所有以它为重点的有向边
      3. 重复1-2直到AOV为空

    关键路径

    • 在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销,称之为用边表示活动的网络,简称AOE网

    • AOE网中仅有一个入度为0的顶点,称为开始顶点(源点);只存在一个出度为0的顶点,称之为结束顶点(汇点)

    • 具有最大路径长度的路径称为关键路径,而把关键路径上的活动称为关键活动

    • 关键路径并不唯一,只提高其中一条关键路径上的关键活动速度不能缩短整个工程的工期。

    • 计算参数

      1. 事件 v k v_k vk的最早发生时间 v e ( k ) ve(k) ve(k)

        • v e ( 源 点 ) = 0 ve(源点)=0 ve()=0
    • v e ( k ) = M a x { v e ( j ) + W e i g h t ( v j , v k } ve(k)=Max\{ve(j)+Weight(v_j,v_k\} ve(k)=Max{ve(j)+Weight(vj,vk}

      • 按拓扑排序,依次计算
      1. 事件 v k v_k vk的最迟发生时间 v l ( k ) vl(k) vl(k)
    • v l ( 汇 点 ) = v e ( 汇 点 ) vl(汇点)=ve(汇点) vl()=ve()

      • v l ( k ) = M i n { v l ( j ) − W e i g h t ( v k , v j } vl(k)=Min\{vl(j)-Weight(v_k,v_j\} vl(k)=Min{vl(j)Weight(vk,vj}
      • 按逆拓扑排序依次计算
      1. 活动 a i a_i ai的最早开始时间 e ( i ) e(i) e(i)
      • 它是指该活动弧的起点所表示的事件最早发生时间。
        • 若边 < v k , v j > <v_k,v_j> <vk,vj>表示活动 a i a_i ai,则有 e ( i ) = v e ( k ) e(i)=ve(k) e(i)=ve(k)
    1. 活动 a i a_i ai的最迟开始时间 l ( i ) l(i) l(i)

      • 它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差
        • 若边 < v k , v j > <v_k,v_j> <vk,vj>表示活动 a i a_i ai,则有 l ( i ) = v l ( j ) − W e i g h t ( v k , v j ) l(i)=vl(j)-Weight(v_k,v_j) l(i)=vl(j)Weight(vk,vj)
    2. 一个活动 a i a_i ai的最迟开始时间 l ( i ) l(i) l(i)和其最早开始时间 e ( i ) e(i) e(i)的差额 d ( i ) = l ( i ) − e ( i ) d(i)=l(i)-e(i) d(i)=l(i)e(i)

      • d ( i ) = 0 d(i)=0 d(i)=0++的活动 a i a_i ai是关键活动

    查找

    查找的概念

    • 查找:在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果分为成功失败
    • 查找表:用于查找的数据集合称为查找表。对查找表进行的操作一般有四种
      • 查询
      • 查询关键字的其他信息
      • 插入
      • 删除
    • 静态查找表:不涉及插入和删除的查找表
    • 关键字:数据元素中唯一标识该元素的某个数据项的值
    • 平均查找长度: A S L = ∑ i = 1 n P i C i ASL=\sum_{i=1}^nP_iC_i ASL=i=1nPiCi, P i P_i Pi是概率, C i C_i Ci是比较次数

    顺序查找和折半查找

    顺序查找

    一般线性表的顺序查找

    typedef struct{
    	ElemType *elem;
        int TableLen;
    }SSTable;
    int Search_Seq(SSTable ST,ElemType key){
        ST.elem[0] = key;	//哨兵
        for(i=ST>TableLen;ST.elem[i]!=key;--i);	//从后往前找
        return i;//若表中不存在关键字为key的元素,将查找到i为0时退出循环
    }
    
    • 哨兵:引入它的目的是可以不必判断数组是否会越界。引入哨兵可以避免很多不必要的判断语句,从而提高程序效率

    有序表的顺序查找

    • 由于表的关键字是有序的,查找失败时可以不用比较到表的另一端就能返回失败信息

    折半查找

    • 折半查找又称二分查找,仅适用于有序的顺序表

    • 仅适用于顺序存储结构,不适用于链式存储结构

    • 生成的判定树

      • 是平衡二叉树
      • 有n个圆形结点代表原数据或成功结点,n+1个方框结点代表不成功结点
      • 每个圆形结点都不是叶子结点,一定有方框子结点
      • 倒数第二层圆结点个数= n − 前 面 层 所 有 结 点 数 n-前面层所有结点数 n
      • 倒数第二层方形结点个数= 2 h − 1 − 倒 数 第 二 层 圆 结 点 2^{h-1}-倒数第二层圆结点 2h1,最后一层方结点个数= n + 1 − 倒 数 第 二 层 方 形 结 点 个 数 n+1-倒数第二层方形结点个数 n+1
      • 如果判定树是向上取整,则所有结点的左子树结点总数永远不小于右子树结点整数,向下取整同理
    • 基本思想

      首先将给定的key与表的中间位置的关键字比较,成功后返回;否则根据key与关键字的大小判断查找左边还是右边

      折半查找整个算法中,关于mid的取值向上/向下需要统一

    int Binary_Search(SeqList L,ElemType key){
        int low=0,high=L.TableLen-1,mid;
        while(low<=high){
            mid = (low+high)/2;		//取中间位置
            if(L.elem[mid]==key)
                return mid;	
            else if(L.elem[mid]>key)
                high = mid-1;//从前半部分继续查找
            else
                low = mid+1;//从后半部分继续查找
        }
        return -1;		//查找失败,返回-1
    }
    

    分块查找

    • 又称索引顺序查找,它吸取了顺序查找和折半查找各自的优点,既有动态结构,又适合快速查找

    • 基本思想

      将查找表分成若干块。块内的元素可以是无序的。但块之间按照每个块的最大关键字进行排序

      建立一个索引表,索引表中的每个元素含有各块的最大关键字和各块的第一个元素的地址,索引表按关键字有序排列

    • 分块查找的过程

      • 在索引表中确定待查记录所在的块,可以顺序查找或折半查找索引表
      • 在块内顺序查找
    • 索引查找的平均查找长度 L I L_I LI,块内查找的平均查找长度 L S L_S LS

    时间复杂度评价

    查找算法 A S L 成 功 ASL_{成功} ASL A S L 失 败 ASL_{失败} ASL
    顺序查找-无序表 n + 1 2 \frac{n+1}{2} 2n+1 n + 1 n+1 n+1
    顺序查找-有序表 n + 1 2 \frac{n+1}{2} 2n+1 n 2 + n n + 1 \frac n2+\frac n{n+1} 2n+n+1n
    折半查找 s u m ( 圆 形 结 点 ∗ 对 应 层 数 ) / n sum(圆形结点*对应层数)/n sum()/n s u m ( 方 结 点 ∗ 对 应 层 数 − 1 ) / ( n + 1 ) sum(方结点*对应层数-1)/(n+1) sum(1)/(n+1)
    分块查找 A S L = L I + L S ASL=L_I+L_S ASL=LI+LS

    B树和B+树

    B树及其基本操作

    B树又称多路平衡查找树,B树中所有结点的孩子个数的最大值称为B树的阶,通常用m表示。

    定义

    • 树中每个结点至多有m棵子树,即至多含有m-1个关键字
    • 若根结点不是终端节点,则至少有两棵子树
    • 除根结点外的所有非叶结点至少有 ⌈ m / 2 ⌉ \lceil m/2 \rceil m/2棵子树,即至少含有 ⌈ m / 2 ⌉ − 1 \lceil m/2 \rceil-1 m/21个关键字
    • 所有非叶子结点的结构如下
    n P 0 P_0 P0 K 1 K_1 K1 P 1 P_1 P1 K 2 K_2 K2 P 2 P_2 P2 . . . ... ... K n K_n Kn P n P_n Pn

    ​ 其中, K i K_i Ki为结点的关键字, P i P_i Pi为指向子树根结点的指针,且指针 P k − 1 P_{k-1} Pk1所指子树中所有结点的关键字均小于 K i K_i Ki P i P_i Pi所指子树中所有结点的关键字均大于 K i K_i Ki

    ​ 结点的孩子个数等于该节点中关键字个数加1

    • 所有的叶节点都出现在同一层次上,并且不带信息,称为外部结点

    B树是所有结点的平衡因子都等于0的多路平衡查找树

    B树的高度

    B树的高度不包括最后的外部结点那一层

    log ⁡ m ( n + 1 ) ≤ h ≤ log ⁡ ⌈ m / 2 ⌉ ( ( n + 1 ) / 2 ) + 1 \log_m(n+1) \leq h \leq \log_{\lceil m/2\rceil}((n+1)/2)+1 logm(n+1)hlogm/2((n+1)/2)+1

    B树的查找

    • 在B树中找结点,在磁盘中进行
    • 在结点在找关键字,在内存中进行

    B树的插入

    1. 定位:利用B树的查找算法,找出插入该关键字的最低层中的某个非叶结点
    2. 插入:在B树中,每个失败结点的关键字个数都在区间 [   ⌈ m / 2 ⌉ − 1. m − 1   ] [\ \lceil m/2 \rceil-1.m-1\ ] [ m/21.m1 ]内。插入后的结点关键字个数小于m,可以直接插入。如果插入后关键字个数大于m-1,必须进行分裂
      • 分裂方法是
        • 取一个新结点,在插入key后的原结点,从中间位置将其中的关键字分为两部分
        • 左部分包含的关键字放在原结点中,右部分包含的关键字放到新结点中
        • 中间位置1的节点插入原节点的父节点。
        • 若此时导致父节点也超过了上限,则对父节点继续分裂

    B树的删除

    • 当被删关键字k不在终端结点时,可以用k的前驱或后继k'替代k,然后在相应的结点中删除k'。关键字k'必定落在某个终端节点中,则转换成了被删关键字在终端结点中的情形

    • 当被删关键字k在终端结点中时

      • 直接删除关键字:若被删除关键字所在结点的关键字个数 > ⌈ m / 2 ⌉ >\lceil m/2 \rceil >m/2,表明删除该关键字后仍满足B树的定义,则直接是删除该关键字

      • 兄弟够借:若被删除关键字所在结点的关键字个数 = ⌈ m / 2 ⌉ − 1 =\lceil m/2 \rceil-1 =m/21,且与此节点相邻的右(左)兄弟节点的关键字个数 ≥ ⌈ m / 2 ⌉ \geq \lceil m/2 \rceil m/2,则需要调整该节点、右(左)兄弟结点及其双亲结点(父子换位法),以达到新的平衡

      • 兄弟不够借:若被删除关键字所在结点的关键字个数 = ⌈ m / 2 ⌉ − 1 =\lceil m/2 \rceil-1 =m/21,且与此节点相邻的右(左)兄弟节点的关键字个数均$ \lceil m/2 \rceil-1$,则将关键字删除后与左(或右)兄弟结点及双亲结点中的关键字进行合并。

        在合并过程中,双亲结点中的关键字个数会减1。若其双亲结点是根结点且关键字个数减少至0,则直接将根结点删除,合并后的新结点成为根;若其双亲结点不是根结点,且关键字减少超过下限,在继续合并操作。

    B+树的基本概念

    • 每个分支结点最多有m棵子树
    • 非叶根结点至少有两棵子树,其他每个分支结点至少有 ⌈ m / 2 ⌉ \lceil m/2 \rceil m/2棵子树
    • 结点的子树个数与关键字个数相等
    • 所有叶结点包含全部关键字及指向相应记录的指针,叶节点中将关键字按大小顺序排雷,并且相邻叶节点按大小顺序相互链接起来
    • 所有分支结点中仅包含它的各个子节点中关键字的最大值及指向其子结点的指针

    在B+树中查找时,非叶结点上的关键字值等于查找值时并不停止,而是继续往下找,直到叶结点上的该关键字为止。无论成功与否,每次查找都是一条从根结点到叶结点的路径

    B树VSB+树

    B树B+树
    关键字个数为n的结点的子树个数n-1n
    结点关键字个数n范围 ⌈ m / 2 ⌉ ≤ n ≤ m \lceil m/2 \rceil \leq n \leq m m/2nm ⌈ m / 2 ⌉ − 1 ≤ n ≤ m − 1 \lceil m/2 \rceil -1\leq n \leq m -1 m/21nm1
    叶结点包含信息,所有非叶结点仅起索引作用,非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址
    叶结点包含的关键字和其他结点包含的关键字是不重复的叶节点包含了全部关键字,即在非叶结点中出现的关键字也会出现在叶结点中

    散列表

    散列表的基本概念

    • 散列函数:一个把查找表中关键字映射成该关键字对应的地址的函数,记为Hash(key)=Addr
    • 冲突:散列函数把两个或两个以上的不同关键字映射到同一地址的现象
    • 同义词:引起冲突的关键字
    • 散列表:根据关键字而直接进行访问的数据结构。散列表建立了关键字和存储地址之间的一种直接映射关系

    散列函数的构造方法

    散列函数的要求

    • 定义域包含全部关键字,值域依赖于散列表的大小或地址范围
    • 散列函数计算出的地址应该能等概率、均匀的分布在整个地址空间中,减少冲突发生
    • 尽可能简单,能够快速计算出散列地址
    常见构造函数公式评价
    直接定地法 H ( k e y ) = k e y H(key)=key H(key)=key H ( k e y ) = a × k e y + b H(key)=a \times key+b H(key)=a×key+b最简单,不会产生冲突。适合关键字的分布基本连续的情况
    除留余数法 H ( k e y ) = k e y H(key)=key%p H(key)=key p p p为不大于散列表表长 m m m但最接近或等于 m m m的质数
    数字分析法设关键字是r进制数,选取数码分布比较均匀的若干位作为散列地址适合于一直的关键字集合,若更换了关键字,则需要重新构造新的散列函数
    平方取中法取关键字对的平方值的中间几位作为散列值适用于关键字的每位取值都不均匀或均小于散列地址所需的位数

    处理冲突的方法

    • 开放定址法, H i = ( H ( k e y ) + d i ) % m H_i=(H(key)+d_i)\%m Hi=(H(key)+di)%m, m m m表示散列表表长, d i d_i di为增量序列
    开放定址法 d i d_i di补充说明
    线性探测法 0 , 1 , 2 , . . . , m − 1 0,1,2,...,m-1 0,1,2,...,m1可能出现大量元素在相邻地址上聚集,降低查找效率
    平方探测法 0 2 , 1 2 , − 1 2 , 2 2 , − 2 2 , . . . , k 2 , − k 2 0^2,1^2,-1^2,2^2,-2^2,...,k^2,-k^2 02,12,12,22,22,...,k2,k2散列表长度m必须是一个可以表示成4k+3的素数
    再散列法 i ∗ H a s h 2 ( k e y ) i*Hash_2(key) iHash2(key) i i i是冲突的次数
    伪随机序列法 d i = d_i= di=随机序列
    • 拉链法

      把所有的同义词存储在一个线性链表中,这个线性链表由其散列地址唯一标识

    散列查找及性能分析

    查找过程

    1. 初始化Addr=Hash(key)
    2. 检测查找表中地址为Addr的位置上是否有记录,若无记录,返回查找失败;若有记录。比较它与key的值,若相等,则返回查找成功的标志,否则执行步骤3
    3. 用给定的处理冲突方法计算“下一个散列地址”,并将Addr置为此地址,转入步骤2

    散列表的查找效率取决于散列函数、处理冲突的方法和装填因子

    • 装填因子 α \alpha α定义为一个表的装满程度
      α = 表 中 记 录 数 n 散 列 表 长 度 m \alpha = \frac{表中记录数n}{散列表长度m} α=mn

    排序

    排序的基本概念

    • 排序:就是重新排列表中的元素,使表中的元素满足按关键字有序的过程
    • 算法的稳定性:在排序之前关键字相同的元素,在排序后相对位置不变的排序算法是稳定的
    • 内部排序:排序期间元素全部存放在内存中的排序
    • 外部排序:排序期间元素无法全部同时同放在内存中,必须在排序的过程中根据要求不断的在内、外存之间移动的排序
    • 可将排序算法分为:插入排序、交换排序、选择排序、归并排序和基数排序五大类

    插入排序

    基本思想:每次讲一个待排序的记录按其关键字大小插入前面已排好序的子序列,直到全部记录插入完成

    直接插入排序

    要将L(i)插入已有序的子序列L[1...i-1],需要执行以下操作

    • 查找出L(i)L[1...i-1]中的插入位置k

    • L[k...i-1]中的所有元素依次后移一个位置

    • L(i)复制到L(k)

    void InsertSort(ElemType A[],int n){
        int i,j;
        for(i=2;i<=n;i++)	//依次将A[2]...A[n]插入到前面已排序的序列
            if(A[i]<A[i-1]){	//若A[i]小于前驱,则将其插入前面的有序表
                A[0] = A[i];	//哨兵
                for(j=i-1;A[0]<A[j];--j)	//从i-1开始比较,比较一次,向后移动一次
                    A[j+1] = A[j];	
                A[j+1] = A[0];		//找到插入位置,赋值
            }
    }
    

    折半插入排序

    • 查找有序子表时用折半查找来实现
    • 确定待插入位置后,同意以地向后移动元素
    void InsertSort(ElemType A[],int n){
        int i,j,low,high,mid;
        for(i=2;i<=n;i++){		//依次将A[2]...A[n]插入到前面已排序的序列
            A[0] = A[i];		//暂存单元,不是哨兵
            low = 1;high = i-1;	
            while(low<=high){		//折半查找
                mid = (low+high)/2;
                if(A[min]>A[0]) high = mid-1;
                else low = mid+1;
            }
            for(j=i-1;j>=high+1;--j)	//统一后移元素
                A[j+1] = A[j];
            A[high+1] = A[0];			//赋值
        }
    } 
    

    希尔排序

    基本思想:先将待排序表分割成若干形如L[i,i+d,i+2d,...,i+kd]的特殊子表,即把相隔某个“增量”的记录组成一个子表,对每个子表分别进行直接插入排序,当整个表中的元素已呈“毕本有序”时,再对全体记录进行一次直接插入排序

    过程

    • 先取一个小于n的步长 d 1 d_1 d1,把表中的全部记录分成 d 1 d_1 d1组,所有距离为 d 1 d_1 d1的倍数的记录放在同一组,在各组内进行直接插入排序
    • 然后取第二个步长 d 2 < d 1 d_2<d_1 d2<d1.
    • 重复上述过程,直到所取到的 d t = 1 d_t=1 dt=1,即所有记录已放在同一组,再进行直接插入排序

    增量序列: d 1 = n / 2 , d i + 1 = ⌊ d i / 2 ⌋ d_1=n/2,d_{i+1}=\lfloor d_i/2 \rfloor d1=n/2,di+1=di/2,最后一个增量等于1

    void ShellSort(ElemType A[],int n){
        //A[0]只是暂存单元,不是哨兵
        for(dk=n/2;dk>=1;dk=dk/2)		//步长变换
            for(i=dk+1;i<=n;i++)		//对d_i个组进行直接插入排序
                if(A[i]<A[i-dk]){		//需要将A[i]插入所在的有序子表中
                    A[0] = A[i];		//暂存A[i]
                    for(j=i-dk;j>0&&A[0]<A[j];j-=dk)//寻找插入位置
                        A[j+dk] = A[j];		//记录后移
                    A[j+dk] = A[0];			//插入
                }
    }
    

    交换排序

    冒泡排序

    基本思想:从后往前(或从前往后)两两比较相邻元素的值,若为逆序则交换,指导序列比较完。

    void BubbleSort(ElemType A[],int n){
        for(i=0;i<n-1;i++){
            flag = false;				//表示本趟冒泡是否发生交换的标志
            for(j=n-1;j>i;j--)			//一趟冒泡过程
                if(A[j-1]>A[j]){		//若为逆序
                    swap(A[j-1],A[j]);	//交换
                    flag = true;
                }
            if(flag==false)
                return;			//本趟遍历后没有发生交换,说明表已经有序
        }
    }
    

    注意:冒泡排序所产生的有序子序列是全局有序的。每一趟排序都会将一个元素放置到其最终的位置上

    快速排序

    基本思想:在待排序表L[1...n]中任取一个元素pivot作为枢轴,通过一趟排序将待排序表划分为独立的两个部分L[1...k-1]L[k+1...n],使得L[1...k-1]中的所有元素小于pivot,L[k+1...n]中的所有元素大于等于pivot,则pivot放在了其最终位置L(k)上,这个过程称为一趟快速排序。然后分别对左右两部分重复上述过程,直到每个部分只有一个元素。

    void QuickSort(ElemType A[],int low,int high){
    	if(low<high){
            //Partition()就是划分操作,将表划分成满足条件的两个子表
            int pivotpos=Partition(A,low,high);	//划分
            QuickSort(A,low,pivotpos-1);
            QuickSort(A,pivots+1,high);
        }
    }
    
    int Partition(ElemType A[],int low,int high){	//一趟划分
        ElemType pivot=A[low];
        while(low<high){
            while(low<high&&A[high]>=pivot) --high;
            A[low] = A[high];		//将比枢轴小的元素移动到左边
            while(low<high&&A[low]<=pivot) ++low;
            A[high] = A[low];		//将比枢轴大的元素移动到右边
        }
        A[low] = pivot;			//枢轴放到最终位置
        reutrn low;
    }
    

    快速排序是所有内部排序算法中平均性能最优的排序算法

    选择排序

    简单选择排序

    基本思想:假设排序表为L[1...n],第i趟排序即从L[i...n]中选择关键字最小的元素与L(i)交换,每一趟排序可以确定一个元素的最终位置,经过n-1趟排序可以使整个排序表有序

    void SelectSort(ElemType A[],int n){
        for(i=0;i<n-1;i++){				//一共进行n-1趟
            min = i;					//记录最小元素位置
            for(j=i+1;j<n;j++)			//在A[1...n-1]中选择最小的元素
                if(A[j]<A[min]) min = j;	//更新最小的元素
            if(min!=j) swap(A[i],A[min]);	//封装的swap()函数共移动3次
        }
    }
    

    堆排序

    • 大根堆:L(i)>=L(2i) & L(i)>=L(2i+1),最大元素在根结点

    • 小根堆:L(i)<=L(2i) & L(i)<=L(2i+1),最小元素在根结点

    • 堆的插入:把新结点放到堆的末端,后进行向上调整

    • 构造初始堆:

      • n个结点的完全二叉树,最后一个结点是第 ⌊ n / 2 ⌋ \lfloor n/2 \rfloor n/2个结点的孩子。对第 ⌊ n / 2 ⌋ \lfloor n/2 \rfloor n/2个结点为根的子树筛选(对于的大根堆,若根结点的关键字小于左右孩子中关键字较大者,则交换),使该子树成为堆。
      • 之后向前依次对各节点 ⌊ n / 2 ⌋ − 1 ∼ 1 \lfloor n/2 \rfloor-1 \sim 1 n/211为根的子树进行筛选,看该结点值是否大于其左右子节点的值,不大于的话进行交换
      • 交换后可能会破坏下一级的堆,使用上述办法继续构造下一级的堆,直到以根结点形成堆为止
    • 输出堆顶元素,重新构建堆,重复这一过程

    void BuildMaxHead(ElemType A[],int len){
        for(int i=len/2;i>0;i--)	//从i=n/2开始,反复调整堆
            HeadAdjust(A,i,len);	
    }
    void HeadAdjust(ElemType A[],int k,int len){
        //将元素k为根的子树进行调整
        A[0] = A[k];	//A[0]暂存子树的根节点
        for(i=2*k;i<=len;i*2){		//沿key较大的子节点向下筛选
            if(i<len&&A[i]<A[i+1])i++;	//取i为较大子结点
        	if(A[0]>=A[i])break;	//筛选结束
            else{
                A[k]=A[i];			//将A[i]调整到双亲结点上
                k=i;		//修改k值,继续向下筛选
            }
        }
        A[k] = A[0];		//被筛选结点的值放入最终位置
    }
    
    void HeapSort(ElemType A[],int len){
        BuildMAxHeap(A,len);
        for(i=len;i>1;i--){		//n-1趟的交换和建堆过程
            Swap(A[i],A[1]);	//输出堆顶元素,和堆底元素交换
            HeadAdjust(A,1,i-1);//调整,把剩余的i-1个元素整理成堆
        }
    }
    

    归并排序和基数排序

    归并排序

    假定待排序表含有n个记录,则可将其视为n个有序的子表,每个子表的长度为1,然后两两合并,得到 ⌈ n / 2 ⌉ \lceil n/2 \rceil n/2个长度为2或1的有序表,继续两两合并。这种排序方法称为2路归并排序。

    一趟归并排序的操作是,调用 ⌈ n / 2 h ⌉ \lceil n/2h \rceil n/2h次算法merge(),将L[1...n]中前后相邻且长度为h的有序段进行两两归并,得到前后相邻、长度为2h的有序段进行两两归并,得到前后相邻、长度为2h的有序段,整个归并排序需要进行 ⌈ l o g 2 n ⌉ \lceil log_2n\rceil log2n

    ELemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));	//辅助数组B
    void Merge(ElemType A[],int low,int mid,int high){
    	for(int k=low;k<=high;k++)B[k] = A[k];	//将A中元素放到B中
        for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
            if(B[i]<=B[j])A[k] = B[i++];	//将较小值赋值到A中
            else A[k] = B[j++];
        }
        while(i<=mid) A[k++] = B[i++];	//若一个表未检测完,赋值
        while(j<=high) A[k++] = B[j++];	//若第二个表未检测完,赋值
    }
    void MergeSort(ElemType A[],int low,int high){
        if(low<high){
            int mid = (low+high)/2;
            MergeSort(A,low,mid);
            MergeSort(A,mid+1,high);
            Merge(A,low,mid,high);	//归并
        }
    }
    

    基数排序

    • 最高位优先法MSD:将关键字位权重递减一次逐层划分成若干更小的子序列,最后将所有子序列依次连接成一个有序序列
    • 最低位优先法LSD:将关键字权重递增一次进行排序,最后形成一个有序序列

    排序过程:

    • 在排序中,使用r个队列 Q 0 , Q 1 , . . . , Q r − 1 Q_0,Q_1,...,Q_{r-1} Q0,Q1,...,Qr1

    • i = 0 , 1 , . . . , d − 1 i=0,1,...,d-1 i=0,1,...,d1,依次做一次分配收集,每个关键字结点 a j a_j aj由d元组组成

    • 分配:开始时,把 Q 0 , Q 1 , . . . , Q r − 1 Q_0,Q_1,...,Q_{r-1} Q0,Q1,...,Qr1各个队列置成空队列,然后依次考察线性表中的每个结点 a j a_j aj,若 a j a_j aj的关键字 k j i = k k_j^i=k kji=k,就把 a j a_j aj放进 Q k Q_k Qk队列中

    • 收集:把 Q 0 , Q 1 , . . . , Q r − 1 Q_0,Q_1,...,Q_{r-1} Q0,Q1,...,Qr1各个队列中的结点依次首尾相连,得到新的结点序列,从而组成新的线性表

    各种内部排序算法比较及应用

    内部排序算法的比较

    算法种类时间复杂度-最好时间复杂度-平均时间复杂度-最坏空间复杂度是否稳定
    直接插入排序 O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)
    冒泡排序 O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)
    简单选择排序 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)
    希尔排序 O ( 1 ) O(1) O(1)
    快速排序 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n) O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n) O ( n 2 ) O(n^2) O(n2) O ( log ⁡ 2 n ) O(\log_2n) O(log2n)
    堆排序 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n) O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n) O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n) O ( 1 ) O(1) O(1)
    2路归并排序 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n) O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n) O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n) O ( n ) O(n) O(n)
    基数排序 O ( d ( n + r ) ) O(d(n+r)) O(d(n+r)) O ( d ( n + r ) ) O(d(n+r)) O(d(n+r)) O ( d ( n + r ) ) O(d(n+r)) O(d(n+r)) O ( r ) O(r) O(r)

    应用

    选取排序方法需要考虑的因素

    • 待排序的元素数目n:较小考虑直接插入和简单选择排序,较大考虑快排】堆排序、归并排序
    • 元素本身信息量的大小:是否选取移动量较少的排序方法
    • 关键字的结构及其分布情况:如已经有序,则选取直接插入或冒泡排序
    • 稳定性的要求
    • 语言工具的要求,存储结构及辅助空间的大小等

    外部排序

    • 外部排序指待排序文件较大,内存一次放不下,需存放在外存的文件的排序
    • 为减少平衡归并中外存读写次数所采取的方法:增大归并路数和减少归并段个数
    • 利用败者树增大归并路数
    • 利用置换-选择排序增大归并段长度来减少归并段的个数

    外部排序的基本概念

    在许多应用中,经常需要对大文件进行排序,因为文件中的记录很多、信息量庞大,无法将整个文件复制进内存中进行排序。因此,需要将待排序的记录存储在外存之上,排序时再把数据一部分一部分地调进内存进行排序,在排序过程中需要多次进行内存和外存之间的交换。这种排序方法就称为外部排序

    外部排序的方法

    • 根据内存缓冲区的大小,将外存上的文件分成若干长度为 l l l的子文件,依次读入内存并利用内部排序方法对它们进行排序,并将排序后得到的有序子文件重新写回外存,称这些有序子文件称为归并段或顺串
    • 对这些归并段进行逐趟归并,使归并段逐渐由小到大,直至得到整个有序文件为止
    • 外部排序的总时间=内部排序所需时间+外存信息读写的时间+内部归并所需的时间
    • 在进行归并的时候,需要使用输入缓冲区和输出缓冲区,在内存和外存中传输数据
    • r个初始段归并,做k路平衡归并,归并树可用严格k叉树来表示,树的高度= ⌈ log ⁡ k r ⌉ \lceil \log_kr\rceil logkr=归并趟数S

    多路平衡归并与败者树

    • 做内部归并时,在k个元素中选择关键字最小的记录需要比较k-1次,S趟归并总需的比较次数是 S ( n − 1 ) ( k − 1 ) = ⌈ log ⁡ k r ⌉ ( n − 1 ) ( k − 1 ) = ⌈ log ⁡ 2 r ⌉ ( n − 1 ) ( k − 1 ) ⌈ log ⁡ 2 k ⌉ S(n-1)(k-1)=\lceil \log_kr\rceil(n-1)(k-1)=\lceil \log_2r \rceil (n-1)(k-1)\lceil \log_2k \rceil S(n1)(k1)=logkr(n1)(k1)=log2r(n1)(k1)log2k

    • 引入败者树后,在k个元素中选择关键字最小的记录需要比较 ⌈ log ⁡ 2 k ⌉ \lceil \log_2k \rceil log2k次,内部归并的比较次数与k无关。因此只要内存允许,增大归并路数k将有效减少归并树的高度,提高外部排序饿的速度

    • 败者树

      • k个叶结点分别存放k个归并段在归并过程中当前参加比较的记录
      • 内存结点用来记忆左右子树中的失败者,而让胜者往上继续比较,一直到根结点
      • 根结点记录胜者
      • 叶结点进行编号 b 0 ∼ b k b0 \sim bk b0bk,内存结点编号 l s [ 0 ] ∼ l s [ k ] ls[0] \sim ls[k] ls[0]ls[k], l s [ 0 ] ls[0] ls[0]为根结点

    置换-选择排序(生成初始归并段)

    初始待排文件FI,初始归并段输出文件为FO,内存工作区为WA,FOWA的初始状态为空,WA可容纳 w w w个记录

    1. FI输入w个记录到工作区WA
    2. WA中选出其中关键字取最小值的记录,记为MINIMAX
    3. MINIMAX就输出到FO中去
    4. FI不为空,则从FI输入下一个记录到WA
    5. WA中鄋关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录,作为新的MINIMAX
    6. 重复3-5,直至在WA中选不出新的MINIMAX记录为止,由此得到一个初始归并段,输出一个归并段的结束标志至FO中去
    7. 重复2-6,直至WA为空,由此得到全部初始归并段

    最佳归并树

    把归并段的长度作为权值,进行严格k叉树的哈夫曼树思想,构造最佳归并树

    • ( n 0 − 1 ) % ( k − 1 ) = 0 (n_0-1)\%(k-1)=0 (n01)%(k1)=0,不需要添加
    • ( n 0 − 1 ) % ( k − 1 ) = u ≠ 0 (n_0-1)\%(k-1)=u\neq0 (n01)%(k1)=u=0,需要添加 k − 1 − u k-1-u k1u个长度为0的虚段
    展开全文
  • 考研数据结构代码总结

    千次阅读 多人点赞 2020-10-30 15:51:05
    数据结构所有代码总结

    一、线性表

    1.1 顺序表

    • 顺序表的结构描述
    typedef struct
    {
    	int data[maxSize];
    	int length;
    }Sqlist;
    
    • 插入元素
    int insertElem(int A[],int &len,int p,int k) //考试中顺序表常用方式(一般不使用结构体) p为要插入的位置,k为插入值 
    {
    	int i;
    	if(p<0 || p>len || len==maxSize)
    		return 0;
    	for(i=len-1;i>=p;i--)
    	{
    		A[i+1]=A[i];//元素后移 
    	}
    	A[p]=k;
    	len++;
    	return 1;
    }
    
    • 删除元素
    int delElem(int A[],int &len,int p)
    {
    	int i;
    	if(p<0 || p>len-1)
    		return 0;
    	for(i=p;i<len-1;i++) //注意i<len-1,不需要让i到达最后一个元素 
    		A[i]=A[i+1]; //前移
    	--len;
    	return 1;
    }
    

    1.2 单向链表

    #include <iostream>
    using namespace std;
    //类型描述
    typedef struct LNode
    {
    	int data;
    	struct LNode *next;
    }LNode;
    
    //尾插法创建 
    void createlistR(LNode *&C,int a[],int n)
    {
    	LNode *s,*r;//r是尾指针,s指向每一次的新节点 
    	int i;
    	C=(LNode *)malloc(sizeof(LNode));
    	C->next=NULL;
    	r=C;
    	for(i=0;i<n;i++)
    	{
    		s=(LNode*)malloc(sizeof(LNode));
    		s->data=a[i];
    		s->next=NULL;
    		r->next=s;
    		r=s; 
    	}
    }
    //头插法创建 
    void createlistF(LNode *&C,int a[],int n)
    {
    	//关键代码:
    	LNode *s;
    	s->data=a[i];
    	s->next=C->next;
    	C->next=s; 
    }
    //插入节点
    void insert()
    {
    	//keycode:
    	LNode *s,*p;
    	s->next=p->next;
    	p->next=s;
    } 
    //删除节点
    void del(LNode *L)
    {
    	//关键代码: 
    	LNode *p,*q;//删除p的后继
    	q=p->next;
    	p->next=q->next;
    	free(q); 
    }
    int main()
    {
    	return 0;
    }
    

    1.3 单向循环链表

    #include <iostream>
    using namespace std;
    //类型描述
    typedef struct LNode
    {
    	int data;
    	struct LNode *next;
    }LNode;
    // 初始化
    int init(LNode *&L)
    {
    	L=(LNode *)malloc(sizeof(LNode));
    	L->next=L;
    }
    // 插入节点
    int insert(LNode *L,int i,int x)//插入到第i-1到i个位置之间 
    {
    	LNode *p;
    	int pos;
    	// 让p指向第i-1个节点
    	while(p->next!=L && pos<i-1) //注意结束条件 
    	{
    		p=p->next;
    		pos++;
    	}
    	if(p->next==L && pos<i-1||pos>i-1)
    		return 0;
    	LNode *s=(LNode*)malloc(sizeof(LNode));
    	s->data=x;
    	s->next=p->next;
    	p->next=s;
    	return 1;
    }
    // 删除节点
    int del(LNode *L,int i,int x) //删除第i个节点 
    {
    	LNode *p;
    	int pos=0;
    	//让p指向第i-1个节点 
    	while(p->next!=L && pos<i-1)
    	{
    		p=p->next;
    		pos++;
    	}
    	if(p->next==L || pos>i-1)
    		return 0;
    	LNode *q=p->next;
    	p->next=q->next;
    	free(q);
    	return 1;
    }
    

    1.4 双向循环链表

    #include <iostream>
    using namespace std;
    //类型描述
    typedef struct DLNode
    {
    	int data;
    	struct DLNode *prior;
    	struct DLNode *next;
    }DLNode;
    // 初始化
    int init(DLNode *L)
    {
    	L=(DLNode*)malloc(sizeof(DLNode));
    	L->next=L->prior=L;
    }
    // 插入节点
    int insert(DLNode *L,int i,int x)
    {
    	DLNode *p=L,*s;
    	int j=0;
    	// 让p指向第i-1个结点
    	while(p->next!=L && j<i-1)
    	{
    		p=p->next;
    		j++;
    	}
    	if(p->next==L && j<i-1||j>i-1)
    		return 0;
    	DLNode *s=(DLNode*)malloc(sizeof(DLNode));
    	s->data=x;
    	s->prior=p;
    	s->next=p->next;
    	p->next->prior=s;
    	p->next=s;
    	return 1;
    }
    //删除结点
    inr del(DLNode *L,int i,int x)
    {
    	DLNode *p,*q;
    	// 让p指向第i-1个节点
    	p=L;
    	int j=0;
    	while(p->next!=L && j<i-1)
    	{
    		p=p->next;j++;
    	}
    	if(p->next==L||j>i-1)
    		return 0;
    	q=p->next;
    	p->next=q->next;
    	q->next->prior=p;
    	free(q);
    	return 1;
    }
    //遍历
    void disp(DLNode *L)
    {
    	// 后继遍历
    	DLNode *p=L->next;
    	while(p!=L) //结束条件 
    	{
    		p=p->next;
    	}
    	// 前驱遍历
    	p=L->prior;
    	while(p!=L)
    	{
    		p=p->next;
    	 } 
    }
    int main()
    {
    	return 0;
    }
    

    1.5 线性表的应用

    1.5.1 两个线性表的合并

    #include <iostream>
    using namespace std;
    typedef struct LNode
    {
    	int data;
    	struct LNode *next;
    }LNode;
    /*方法一假设合并的链表上的结点空间是原来的空间,其算法设计的主要思想是将
    其中一个链表上的结点逐个插人到另一个链表中。*/
    void merge1(LNode *La,LNode *Lb)//合并到La 
    {
    	LNode *pa,*pb,*qa,*qb;
    	q=La;pa=La->next;pb=qb=Lb->next;
    	while(pa&&pb)
    	{
    		if(pb->data<=pa->data)//插入到qa和pa之间 (qa始终是pa的前驱结点) 
    		{
    			qb=qb->next;//key
    			pb->next=pa;
    			qa->next=pb;
    			pa=qa->next;//key error 调整pa,让其前驱为qa 
    			pb=qb;//key
    		}
    		else
    		{
    			qa=pa;
    			pa=pa->next;
    		}
    	}
    	if(pb) qa->next=pb;//剩余结点 
    	free(Lb);
    }
    /*
    方法二假设合并的链表上的结点空间是重新申请的空间,其算法设计的主要思想是
    将原来的两个链表上的结点依次比较逐个插入到新链表中。 
    */
    void merge2(LNode *La,LNode *Lb,LNode *&Lc)
    {
    	LNode *pa,*pb,*pc,*s;
    	pa=La->next;
    	pb=Lb->next;
    	Lc=(LNode*)malloc(sizeof(LNode));
    	pc=Lc;
    	while(pa&&pb)
    	{
    		if(pb->data<=pa->data)
    		{
    			s=(LNode*)malloc(sizeof(LNode));
    			s->data=pb->data;
    			s->next=NULL;
    			pc->next=s;
    			pc=s;
    			pb=pb->next;//后移 
    		}
    		else
    		{
    			s=(LNode*)malloc(sizeof(LNode));
    			s->data=pa->data;
    			s->next=NULL;
    			pc->next=s;
    			pc=s;
    			pa=pa->next;//后移 
    		}
    	}
    	//收尾
    	while(pb)
    	{
    		s=(LNode*)malloc(sizeof(LNode));
    		s->data=pb->data;
    		s->next=NULL;
    		pc->next=s;
    		pc=s;
    		pb=pb->next;
    	}
    	while(pa)
    	{
    		s=(LNode*)malloc(sizeof(LNode));
    		s->data=pa->data;
    		s->next=NULL;
    		pc->next=s;
    		pc=s;
    		pa=pa->next;
    	}
    }
    int main()
    {
    	return 0;
    }
    

    1.5.2 一元函数的求和与求积

    #include <iostream>
    using namespace std;
    //类型描述
    typedef struct
    {
    	float coef;//存放系数
    	int exp;//存放指数 
    }Term;
    typedef struct Pnode
    {
    	Term data;
    	struct Pnode *next;
    }Pnode;
    //插入节点
    void insert(Pnode *L,Term x)
    {
    	Pnode *p=L,*q=L->next,*s;//p q 记住相邻的两个结点 
    	while(p)
    	{
    		if(q!=NULL && x.exp>p->data.exp && x.exp<q->data.exp) //插入到p、q之间 
    		{
    			s=(Pnode*)malloc(sizeof(Pnode));
    			s->data=x;
    			s->next=q;
    			p->next=s;
    			return;
    		}
    		else if(q!=NULL && x.exp==q.data.exp)
    		{
    			if(fabs(q.data.coef + x.coef) < 1.0E-6) //指数相等,系数符号相反,绝对值相等 
    			{
    				p->next=q->next; //删除q结点 
    				free(q);
    				return ;
    			}
    			else
    			{
    				q->data.coef = x.coef + q->data.coef; //指数相等,系数不同,合并 
    				return ;
    			}
    		}
    		else if(q==NULL && x.exp > p->data.exp) //插入到最后 
    		{
    			s=(Pnode*)malloc(sizeof(Pnode));
    			s->data=x;
    			s->next=NULL;
    			p->next=s;
    			return;
    		}
    		else  //后移,寻找插入位置 
    		{
    			p=q;
    			q=q->next;
    		}
    	}
    }
    //两个一元函数多项式的加法
    void add(Pnode *La,Pnode *Lb,Pnode *Lc)
    {
    	Pnode *s,*pa,*pb,*pc;
    	Lc=(Pnode*)malloc(sizeof(Pnode));
    	Lc->data.exp=-1;
    	Lc->next=NULL;
    	pa=La->next;
    	pb=Lb->next;
    	pc=Lc;
    	while(pa&&pb)
    	{
    		if(pa->data.exp < pb.data.exp)
    		{
    			s=(Pnode*)malloc(sizeof(Pnode));
    			s->data=pa->data;
    			s->next=NULL;
    			pc->next=s;
    			pc=s;
    			pa=pa->next;//后移 
    		}
    		else if(pa->data.exp == pb->data.exp)//合并同类项 
    		{
    			if(fabs(pa->data.coef + pb->data.coef) > 1.0E-6)//之后和不为零才会插入 
    			{
    				s=(Pnode*)malloc(sizeof(Pnode));
    				s->data.coef = pa->data.coef + pb->data.coef;
    				s->data.exp = pa->data.exp;
    				s->next = NULL;
    				pc->next=s;
    				pc=s;
    			}
    			pa=pa->next;
    			pb=pb->next;
    		}
    		else
    		{
    			s=(Pnode*)malloc(sizeof(Pnode));
    			s->data=pb->data;
    			s->next=NULL;
    			pc->next=s;
    			pc=s;
    			pb=pb->next;
    		}
    	}
    	while(pa)
    	{
    		s=(Pnode*)malloc(sizeof(Pnode));
    		s->data=pb->data;
    		s->next=NULL;
    		pc->next=s;
    		pc=s;
    		pa=pa->next;
    	}
    	while(pb)
    	{
    		s=(Pnode*)malloc(sizeof(Pnode));
    		s->data=pb->data;
    		s->next=NULL;
    		pc->next=s;
    		pc=s;
    		pb=pb->next;
    	}
    }
    //乘法
    /*
    将第1个一元多项式的每一项与第2个一元多项式的各项相乘,再插人到新的一元
    多项式中。 
    */ 
    void mul(Pnode *La,Pnode *Lb,Pnode *Lc)
    {
    	Pnode *pa,*pb;
    	Term x;
    	Lc=(Pnode*)malloc(sizeof(Pnode));
    	Lc->data.exp=-1;
    	Lc->next=NULL;
    	pa=La->next;
    	while(pa)
    	{
    		pb=Lb->next;
    		while(pb)
    		{
    			x.coef = pa->data.coef * pb->data.coef;//系数相乘 
    			x.exp = pa->data.exp + pb->data.exp;//指数相加 
    			insert(Lc,x);
    			pb=pb->next;
    		}
    		pa=pa->next;
    	}
    }
    int main()
    {
    	return 0;
    }
    

    二、栈和队列

    2.1 表达式求值的两种方法

    [分析]后缀表达式是一个字符串,为了方便处理,以’#‘结束。用一个栈(假定数据元素类型为整型)来存放操作数和中间的计算结果。对后缀表达式从左向右依次扫
    描,若是操作数,则将字符转换成整数进栈;若是运算符,则连续出栈两次,第一次出栈的元素是第二个操作数,第二次出栈的元素是第一个操作数,根据当前的运算符做相应的运算,并将计算结果进栈,直到遇到’#'为止。此时栈中只剩下一个元素,即最后的运算结果,出栈即可。

    #include <iostream>
    using namespace std;
    
    //后缀表达式求值(仅仅适用于个位数)
    void suffix_value(char a[])
    {
    	int i=0,x1,x2;
    	char s[maxSize];
    	int top=-1;
    	while(a[i]!='#')
    	{
    		switch(a[i])
    		{
    			case'+':x2=pop(s); x1=pop(s); push(s,x1+x2);break;
    			case'-':x2=pop(s); x1=pop(s); push(s,x1-x2);break;
    			case'*':x2=pop(s); x1=pop(s); push(s,x1*x2);break;
    			case'/':x2=pop(s); x1=pop(s);
    			if(x2!=0) push(s,x1/x2);
    			else
    			{
    				cout<<"分母为0"<<endl;
    				return ;
    			}
    			break;
    			default: push(s,a[i]-'0');//将字符转换为数字 
    		}
    		i++; //处理下一个a[i] 
    	}
    	cout<<"结果为"<<pop(s)<<endl;
    }
    //将中缀表达式转换为后缀表达式
    //判断字符优先级 
    int prior(char a)
    {
    	if(a=='*' || a=='/') return 4;
    	else if(a=='+' || a=='-') return 3;
    	else if(a== '(') return 2;
    	else if(a=='#') return 1;
    	else return 0;
    }
    //转换函数
    void transform(char a[],char suff[]) //a指向算术表达式,suff存储后缀表达式 
    {
    	int i=0,k=0,n;
    	char ch;
    	Stack s;
    	push(s,'#');
    	n=strlen(a);
    	a[n]='#';a[n+1]='\0';
    	while(a[i]!='\0')
    	{
    		if(a[i]>='0' && a[i]<='9')//操作数,直接存入后缀表达式 
    		suff[k++]=a[i];
    		else
    		switch(a[i])
    		{
    			case'(':push(s,a[i]);break;
    			case')':
    				ch=pop(s);
    				while(ch!='(')
    				{
    					suff[k++]=ch;
    					ch=pop(s);
    				}
    				break;
    			default:
    				ch=gettop(s);
    				while(prior(ch)>=prior(a[i]))
    				{
    					suff[k++]=ch;
    					ch=pop(s);
    					ch=gettop(s);
    				}
    				if(a[i]!='#') push(s,a[i]);
    		}
    		i++;
    	}
    	suff[k]='\0';
    }
    /*
    (代码层面)将计算后缀表达式的函数和将中缀表达式转换为后缀表达式的函数结合
    即可计算出中缀表达式的值 
    (手工求值层面)看参考书 
    */
    /*
    以上算法仅适用于操作数是个位数。如果对任意的实数都能计算,需要解决如下
    问题:
    (1)后缀表达式中的操作数与操作数之间用空格隔开;
    (2)操作数栈的元素类型为实数;
    (3)将一个数字串转换为一个实数的算法;
    (4)操作数为负数的情况。.
    例如,原表达式为: -3+(-15. 7+9) *4. 25+7/8.2
    (1)处理负数的情况
    原则:第1个字符为'-',前面加0;'('之后是'-',在'('之后加0。
    原表达式变为: 0-3+(0-15. 7+9) *4. 25+7/8.2
    (2)在操作数与操作数之间加空格
    后缀表达式为: 03- 0 15.7 -9 + 4.25 *+7 8.2/+
    请读者将上述的有关算法进行修改,使其可以计算任意实数的算术表达式。
    
    */
    int main()
    {
    	return 0;
    }
    

    三、树和二叉树

    3.1 二叉树的类型描述

    typedef struct BTNode
    {
    	char data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode;
    

    3.2 二叉树的创建

    #include <iostream>
    using namespace std;
    typedef struct BTNode
    {
    	char data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode;
    /*
    以“根 左子树 右子树”的字符串形式读人结点值
    的递归算法按先序遍历顺序(空结点以#表示)读人每个结点值建立二叉链表。
    */
    void  crt_tree(BTNode *T)//递归创建(先序遍历) 
    {
    	char c;
    	cin>>c;
    	if(ch=='#') T=NULL;
    	else
    	{
    		T=(BTNode*)malloc(sizeof(BTNode));
    		T->data=ch;
    		crt_tree(&T->lchild);
    		crt_tree(&T->rchild);
    	}
    }
    // 层次遍历可以实现非递归创建 详见p183 
    void Creat_BiTree(BTNode *T)
    {
    	Queue q;
    	T=NULL;
    	char fa,ch,lrflag;//fa为父亲节点 
    	cin>>fa>>ch>>lrflag;
    	while(ch!='#')
    	{
    		BTNode *p=(BTNode*)malloc(sizeof(BTNode));
    		p->data=ch;
    		p->lchild=p->rchild=NULL;
    		EnQueue(Q,p);
    		if(fa=='#') T=p; //根节点
    		else
    		{
    			BTNode *s=GetHead(Q);
    			while(s->data!=fa)//寻找当前节点的父亲节点(该过程中遇到的非父亲节点一定已经创建完成) 
    			{
    				DeQueue(Q,p);
    				s=GetHead(Q); 
    			}
    			if(lrflag==0) s->lchild=p;
    			else s->rchild=p;
    		}
    		cin>>fa>>ch>>lrflag;
    	}
    }
    

    3.3 二叉树的递归遍历(以先序遍历为例)

    void preorder(BTNode *p)
    {
    	if(p!=NULL)
    	{
    		cout<<p->data<<endl;
    		preorder(p->lchild);
    		preorder(p->rchild);	
    	}
    }
    

    3.4 二叉树的非递归遍历

    // 非递归先序遍历
    void preorderNO(BTNode *bt)
    {
    	if(bt!=NULL)
    	{
    		BTNode *stack[maxSize];
    		int top=-1;
    		// 根节点入栈 
    		top++;
    		stack[top] = bt;
    		//开始遍历
    		BTNode *p;
    		while(top!=-1)
    		{
    			p=stack[top--];
    			cout<<p->data<<endl; //先序遍历(先右孩子进栈,然后是左孩子) 
    			if(p->rchild != NULL)
    			{
    				stack[++top] = p->rchild; 
    			}
    			if(p->lchild != NULL)
    			{
    				stack[++top] = p->lchild;
    			 } 
    		} 
    	}
    }
    
    // 非递归中序遍历
    void inorderNo(BTNode *bt)
    {
    	if(bt!=NULL)
    	{
    		BTNode *stack[maxSize];
    		int top=-1;
    		BTNode *p;
    		p=bt;
    		while(top!=-1 || p!=NULL)
    		{
    			while(p!=NULL) //左孩子不断入栈 ,直到最左边的结点 
    			{
    				stack[++top] = p;
    				p= p->lchild;
    			}
    			if(top!=-1)
    			{
    				p=stack[top--];
    				cout<<p->data<<endl;
    				p=p->rchild; //后访问右孩子(最左边结点是没有右孩子的,这一步会赋值为NULL,然后退回到最近的根节点进行访问,然后再对其右子树进行同样的操作) 
    			}
    		}
    	}
    } 
    
    // 非递归后序遍历
    void postorder(BTNode *bt)
    {
    	if(bt!=NULL)
    	{
    		BTNode *stack1[maxSzie]; int top1=-1;
    		BTNode *stack2[maxSize]; int top2=-1;
    		BTNode *p;
    		stack1[++top1]=bt;
    		while(top1!=-1)
    		{
    			p = stack1[top1--];
    			stack2[++top2] = p; // 出一个进一个,实现逆序
    			if(p->lchild!=NULL)
    			{
    				stack1[++top1] = p->lchild;
    			}
    			if(p->rchild!=NULL)
    			{
    				stack1[++top] = p->rchild;
    			}
    		}
    		while(top2!=-1)
    		{
    			p = stack2[top2--];
    			cout<<p->data<<endl;
    		}
    	}
    }
    

    3.5 二叉树的层次遍历

    // 层次遍历 
    void level(BTNode *p)
    {
    	int front,rear;
    	BTNode *que[15];
    	front=rear=0;
    	BTNode *q;
    	if(p!=NULL)
    	{
    		rear = (rear+1) % maxSize;
    		que[rear] = p;
    		while(front!=rear)
    		{
    			//出队
    			front = (front+1)%maxSize;
    			q = que[front];
    			cout<<q->data<<endl;
    			if(q->lchild != NULL)
    			{
    				rear = (rear+1) % maxSize;
    				que[rear] = q->lchild;	
    			}
    			if(q->rchild != NULL)
    			{
    				rear = (rear+1) % maxSize;
    				que[rear] = q->rchild;
    			}
    		}
    	}
    }
    

    3.6 树的创建

    • 孩子链表表示法(邻接表)
    /*--------孩子链表表示法(邻接表)---------*/
    typedef struct CTNode //表节点 
    {
    	int child;
    	struct CTNode *next;
    }CTNode;
    typedef struct CTbox //表头节点 
    {
    	char data;
    	CTNode *first;
    }CTbox;
    typedef struct
    {
    	CTbox nodes[maxSize];
    	int n,r;//节点数目和根节点的位置 
    }ChildList;
    void createPtree(ChildList *T)
    {
    	int i,j,k;
    	CTNode *p,*s;
    	char father,child;
    	cout<<"请输入结点数"<<endl;
    	cin>>T->n;
    	getchar();
    	cout<<"请按照层次依次输入"<<T->n<<"个结点的值"<<endl;
    	for(i=0;i<T->n;i++)
    	{
    		cin>>T->nodes[i].data;
    		T->nodes[i].first=NULL; 
    	}
    	getchar();
    	cout<<"请按照格式(双亲,孩子)输入"<<T->n-1<<"分支(按照层次)"<<endl;
    	for(i=1;i<=T->n-1;i++)
    	{
    		cin>>father>>child;
    		getchar();
    		for(j=0;j<T->n;j++) //找到父节点的值 
    		{
    			if(father==T->nodes[j].data);
    			break;
    		}
    		if(j>=T->n)
    		{
    			cout<<"error"<<endl;
    			return ;
    		}
    		for(k=0;k<T->n-1;k++)//找孩子节点的值 
    		{
    			if(child==T->nodes[j].data)
    			break;
    		}
    		if(k>=T->n)
    		{
    			cout<<"error"<<endl;
    			return ;
    		}
    		p=T->nodes[j].first;
    		if(p==NULL)//第一个孩子结点 
    		{
    			s=(CTNode*)malloc(sizeof(CTNode));
    			s->child=k;
    			s->next=NULL;
    			T->nodes[j].first=s;
    		}
    		else //不是第一个孩子 
    		{
    			while(p->next) p=p->next;
    			s=(CTNode*)malloc(sizeof(CTNode));
    			s->child=k;
    			s->next=NULL;
    			p->next=s; 
    		}
    	}
    }
    
    • 孩子兄弟链表表示法
    /*--------孩子兄弟链表表示法---------*/
    typedef struct CSNode
    {
    	char data;
    	struct CSNode *fch,*nsib;//第一个孩子和下一个兄弟 
    }CSNode;
    void createCSTree(CSNode *T)
    {
    	Queue q;//队列(伪代码形式)
    	CSNode *p,*s,*r; 
    	T=NULL;
    	char fa,ch;
    	cin>>fa>>ch;
    	while(ch!='#')
    	{
    		p=(CSNode*)malloc(sizeof(CSNode));
    		p->data=ch;
    		p->fch=p->nsib=NULL;
    		EnQueue(q,p);	//指针入队列
    		if(fa=='#')
    			T=p;	//建立根节点
    		else
    		{
    			s=getHead(Q);
    			while(s->data!=fa) //在队列中找到双亲节点 
    			{
    				DeQueue(Q);
    				s=getHead(Q);
    			}
    			if(s->fch==NULL)//第一个孩子节点 
    			{
    				s->fch=p;
    				r=p;
    			}
    			else	//不是第一个孩子 
    			{
    				r->nsib=p;
    				r=p;
    			}
    		}
    		cin>>fa>>ch;
    	}
    }
    

    3.7 树的查找算法

    /*--------树的查找算法---------*/
    void preSearch(CSNode *T,char val[],CSNode *p)
    {
    	if(T)
    	{
    		if(strcmp(val,T->data)==0)//查找成功 
    		{
    			p=T;
    			return ;
    		}
    		preSearch(T->fch,val,p);
    		preSearch(T->nsib,val,p);
    	}
    }
    

    3.8 树的插入算法

    /*--------树的结点插入---------*/
    int insert(CSNode *T,char fa[],char ch[])
    {
    	CSNode *s,*p=NULL,*q;
    	//fa是双亲,ch是孩子
    	preSearch(T,fa,&p);	//查找双亲节点
    	if(p)
    	{
    		s=(CSNode*)malloc(sizeof(CSNode));
    		strcpy(s->data,ch);
    		s->fch=s->nsib=NULL;
    		if(p->fch==NULL)
    			p->fch=s;//第一个孩子结点
    		else
    		{
    			q=p->fch;
    			while(q->nsib) q=q->nsib;
    			q->nsib=s;
    		}
    		return 1;
    	}
    	return 0;
    }
    

    3.9 树的删除算法

    删除树中的一个结点,约定删除以该结点为根的子树。首先根据双亲和孩子的值在孩子,兄弟链表中分别进行查找,如果有一个不存在,不能进行删除操作;否则得到双亲结点和孩子结点的地址。如果删除的结点是双亲结点的第一个孩子,重新链接其他的孩子结点,再删除第一个孩子子树;如果删除的结点不是第一个孩子,继续寻找该结点的前一个兄弟,将该结点的其他兄弟与前一个兄弟链接,再刪除以该结点为根的子树。

    /*
    其中函数deleteRoot()是完成子树的删除,并重接其他子树;函数postDelTree()是按照
    后序遍历的顺序释放每一个结点的空间。
    
    */
    void deleteRoot(CSNode *p,CSNode *f) //从树中删除一结点p为根的子树 ,f是p在存储结构上的双亲节点 
    {
    	if(f->fch==p)	//p是f的第一个孩子,是双亲关系 
    	{
    		f->fch=p->nsib;
    		p->nsib=NULL;
    		postDelTree(p);
    	}
    	if(f->nsib==p)	//p与f是兄弟关系 
    	{
    		f->nsib=p->nsib;
    		p->nsib=NULL;
    		postDelTree(p);
    	}
    }
    void postDelTree(CSNode *T)
    {
    	if(T)
    	{
    		postDelTree(T->fch);
    		postDelTree(T->nsib);
    		free(T);
    	}
    }
    void deleteTree(CSNode *T,char fa[],char ch[])
    {
    	CSNode *pfa=NULL,*pch=NULL;
    	if(strcmP(fa,"#")==0)	//删除的是整棵树 
    	{
    		postDelTree(T);
    		T=NULL;
    		return;
    	}
    	else
    	{
    		preSearch(T,fa,&pfa);	//查找双亲 
    		preSearch(T,ch,&pch);	//查找孩子
    		if(pfa==NULL || pch=NULL)
    		{
    			cout<<"error"<<endl;
    			return;
    		}
    		else
    		{
    			if(pfa->fch != pch)
    			{
    				pfa=pfa->fch;
    				while(pfa)
    				{
    					if(pfa->nsib == pch) break;
    					pfa=pfa->nsib;
    				}
    			}
    			deleteRoot(pch,pfa);
    		}
    	}
    }
    

    3.10 树的深度

    在树的孩子兄弟链表中,每棵子树根与它的左子树根是双亲与孩子的关系,每棵子树根与它的右子树根是兄弟关系,所以每棵子树的高度是(左子树高度+1)和右子树高度的最大值。

    int depth(CSNode *T)
    {
    	int d1,d2;
    	if(T==NULL) return 0;
    	d1=depth(T->fch);
    	d2=depth(T->nsib);
    	return d1+1>d2 ? d1+2:d2;
    }
    

    3.11 输出树中的所有叶子节点路径

    输出树中所有从根到叶子的路径的主要步骤:
    (1)树不空,将根结点进栈。
    (2)如果栈顶元素的第一棵孩子树为空,路径找到,输出栈内的所有结点,转向(3);
    否则继续寻找第一棵子树上的叶子路径。
    (3)栈顶元素出栈。如果栈顶元素有其余的兄弟子树,回到(1)继续寻找其余的兄弟
    子树上的叶子路径。

    void AllTreePath(CSNode *T,Stack *s)
    {
    	//非递归形式(可以更改为递归形式,可参考二叉树的叶子节点求法) 
    	while(T)
    	{
    		Push(S,T->data);
    		if(T->fch==NULL) PrintStack(S);//只把数据打印一遍,不出栈
    		else
    		AllTreePath(T->fch,S);
    		Pop(s);//出栈
    		T=T->nsib;
    	}
    }
    

    3.12 二叉树的应用

    3.12.1 输出二叉树的叶子节点路径

    #include <iostream>
    using namespace std;
    #define maxSize 1500
    typedef struct BTNode
    {
    	char data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode;
    /*--------输出二叉树中所有叶子节点的路径---------*/
    void AllTreePath(BTNode *T,Stack *s)
    {
    	if(T)
    	{
    		Push(S,T->data);
    		if(T->lchild==NULL && T->rchild==NULL)
    			PrintStack(S);//只打印数据,不出栈
    		else
    		{
    			AllTreePath(T->lchild,S);
    			AllTreePath(T->rchild,S);
    		}
    		Pop(s);//出栈 
    	}
    }
    

    3.12.2 表达式二叉树

    #include <iostream>
    using namespace std;
    //类型描述
    typedef struct BTNode
    {
    	char data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode; //二叉树节点
    int isOperator(char ch){}//判断是否为运算符(暂时未写) 
    //判断字符优先级 
    int prior(char a)
    {
    	if(a=='*' || a=='/') return 4;
    	else if(a=='+' || a=='-') return 3;
    	else if(a== '(') return 2;
    	else if(a=='#') return 1;
    	else return 0;
    }
    //创建子节点并入子树栈 
    void CrtNode(BTNode subTreeStack[],int &top,char ch)//subTreeStack是存储子树的栈 
    {
    	BTNode *T;
    	T=(BTNode*)malloc(sizeof(BTNode));
    	T->data=ch;
    	T->lchild=T->rchild=NULL;
    	subTreeStack[++top]=T;
    }
    //创建子树并入子树栈
    void CrtSubTree(BTNode subTreeStack[],int &top,char c)
    {
    	BTNode *T;
    	BTNode lc,rc;//一次性出栈两个元素,一个左孩子,一个右孩子
    	T=(BTNode*)malloc(sizeof(BTNode));
    	T->data=c;
    	lc=subTreeStack[top--];
    	rc=subTreeStack[top--];
    	T->lchild=lc;
    	T->rchild=rc;
    	subTreeStack[++top]=T;//新生成的子树的根节点入栈 
    }
    //核心函数,创建表达式二叉树
    void CrtExptree(BTNode *T,char exp[])
    {
    	BTNode subTreeStack[maxSize];int subTreeTop=-1;//子树栈
    	BTNode charStack[maxSize];int charStackTop=-1;//运算符栈
    	charStack[++top]='#';//结束符入栈
    	char ch,c;
    	int i=0;
    	while( (c=charStack[top])!='#' || exp[i]!='#' )
    	{
    		if(!isOperator(exp[i]))
    		CrtNode(subTreeStack,subTreeTop,exp[i]);//非运算符,直接建立叶节点并入子树栈中 
    		else
    		{
    			switch(exp[i])
    			{
    				case'(':charStack[++charStackTop]=exp[i];break;//左括号 
    				case')':c=charStack[charStackTop--];//右括号 
    						while(c!='(')
    						{
    							CrtSubTree(subTreeStack,c);
    							c=charStack[charStackTop--];
    						}
    				default:
    					while( (c=charStack[charStackTop])!='#' && prior(c)>prior(exp[i]))
    					{
    						/*
    						当栈顶运算符不是#号且优先级高于表达式中的当
    						前运算符,则取栈顶的运算符建子树,再出栈
    						*/
    						CrtSubTree(subTreeStack,subTreeTop,c);
    						charStackTop--;//出栈
    					}
    					if(exp[i]!='#')
    					charStack[++charStackTop]=exp[i];
    			}
    		}
    		if(exp[i]!='#') i++;
    	}
    	T=subTreeStack[top--];//二叉树根节点出栈 
    }
    /*
    表达式二叉树的计算(使用后序遍历) 
    */
    double culExp(BTNode *T)
    {
    	double result,a,b;
    	if(T)
    	{
    		if(!isOperator(T->data))//如果不是运算符,说明是字母变量,需要输入具体值,同时也是叶子节点 
    		{
    			cout<<"请输入变量"<<T->data<<"的值"<<endl;
    			cin>>result;
    			return result; 
    		}
    		a=culExp(T->lchild);
    		b=culExp(T->rchild);
    		//后序遍历进行计算
    		switch(T->data)
    		{
    			case'+':return a+b;
    			case'-':return a-b;
    			case'*':return a*b;
    			case'/':
    					if(b!=0)
    						return a/b;
    					else
    					{
    						cout<<"分母为0";
    						exit(0);
    					}
    		}
    	}
    }
    int main()
    {
    	return 0;
    }
    

    四、图

    4.1 图的创建

    4.1.1 邻接矩阵创建

    /***********邻接矩阵***********/ 
    typedef struct
    {
    	int edges[maxSize][maxSize];
    	int n,e;
    }MGraph;
    /*邻接矩阵创建(以无向图为例)*/
    void crt_graph(MGraph *G)
    {
    	cin>>G->n>>G->e;//输入顶点数和边数
    	/*初始化*/
    	for(int i=0;i<G->n;i++)
    		for(int j=0;j<G->n;j++)
    		G->edges[i][j]=0;
    	for(int k=0;k<G->e;k++)
    	{
    		int i,j;
    		cin>>i>>j;
    		G->edges[i][j]=G->edges[j][i]=1;
    	}
    }
    

    4.1.2 邻接表创建

    /***********邻接表存储法***********/ 
    // 被指向的点 
    typedef struct ARCNode
    {
    	int vex;
    	struct ARCNode *next;
    	char info;
    }ARCNode;
    // 顶点
    typedef struct VNode
    {
    	int data;
    	ARCNode *first;
    }VNode;
    //邻接表
    typedef struct
    {
    	VNode list[maxSize];
    	int n,e; 
    }AGraph;
    //邻接表创建(以有向图为例) 
    void build_list(AGraph *G)
    {
    	cin>>G->n>>G->e;//顶点数和边数
    	for(int i=0;i<G->n;i++)
    	{
    		// 创建表节点(以编号形式输入)
    		cin>>G->list[i].data;
    		G->list[i].first=NULL;
    	}
    	for(int k=0;k<G->e;k++)//创建边 
    	{
    		int i,j;
    		cin>>i>>j;
    		ARCNode *p=(ARCNode*)malloc(sizeof(ARCNode));
    		p->vex=j;//假设编号和下标一致
    		//头插法插入 
    		p->next=G->list[i].first;
    		G->list[i].first=p;
    	}
    }
    

    4.2 图的遍历

    #include <iostream>
    #include<malloc.h>
    using namespace std;
    #define maxSize 150
    int visit[maxSize];
    /***********邻接表存储法***********/ 
    // 被指向的点 
    typedef struct ARCNode
    {
    	int vex;
    	struct ARCNode *next;
    	char info;
    }ARCNode;
    // 顶点
    typedef struct VNode
    {
    	char data;
    	ARCNode *first;
    }VNode;
    //邻接表
    typedef struct
    {
    	VNode list[maxSize];
    	int n,e; 
    }AGraph;
    //------- 深度优先遍历----------//
    void DFS(AGraph *G,int v)
    {
    	ARCNode *p;
    	visit[v]=1;
    	cout<<G->list[v].data<<" ";
    	p=G->list[v].first;
    	while(p!=NULL)
    	{
    		if(visit[p->vex]==0)
    		DFS(G,p->vex);
    		p=p->next;
    	}
    }
    /*广度优先遍历*/
    void BFS(AGraph *G,int v)
    {
    	ARCNode *p;
    	int que[maxSize];int front=0,rear=0;
    	int j;
    	cout<<G->list[v].data<<endl;
    	visit[v]=1;
    	rear=(rear+1)%maxSize;
    	que[rear]=1;
    	while(front!=rear)
    	{
    		front=(front+1)%maxSize;
    		int j = que[front];
    		p=G->list[j].first;
    		while(p!=NULL)
    		{
    			if(visit[p->vex]==0)
    			{
    				cout<<G->list[p->vex].data<<endl; //先访问,后入队 
    				visit[p->vex]=1;
    				rear=(rear+1)%maxSize;
    				que[rear]=p->vex;
    			}
    			p=p->next
    		}
    	}
    }
    int main()
    {
    	return 0;
    }
    

    4.3 最小生成树

    4.3.1 Prim算法

    //邻接矩阵
    typedef struct
    {
    	int edges[maxSize][maxSize];
    	int n,e;
    }MGraph;
    void Prim(MGraph g,int v0,int &sum)
    {
    	int lowcost[maxSize],vset[maxSize],v;
    	int i,j,k,min;
    	v=v0;
    	//初始化
    	for(i=0;i<g.n;i++)
    	{
    		lowcost[i]=g.edges[v0][i];
    		vset[i]=0;
    	}
    	vset[v0]=1;
    	sum=0;
    	for(i=0;i<g.n-1;i++)
    	{
    		min=INF;
    		//选择距离最小者(在lowcost数组中选取)
    		for(j=0;j<g.n;j++)
    		{
    			if(vset[j]==0 && lowcost[j]<min)
    			{
    				min=lowcost[j];
    				k=j;
    			} 
    		}
    		// 并入
    		vset[k]=1;  
    		v=k;//准备更新信息,k为这次的跳板 
    		sum+=min; //error 出错点 
    		for(j=0;j<g.n;j++)
    		{
    			if(vset[j]==0 && g.edges[v][j]<lowcost[j])
    			{
    				lowcost[j]=g.edges[v][j];
    			} 
    		} 
    	} 
    }
    

    4.3.2 Kruskal算法

    /*-------克鲁斯卡尔-------*/
    typedef struct
    {
    	int a,b;
    	int w;
    }Road;
    Road road[maxSize]; // 路径信息
    int v[maxSize]; //并查集使用 
    //获取根节点
    int getRoot(int a)
    {
    	while(a!=v[a]) a=v[a];
    	return a;
    }
    void Kruskal(MGraph g,int &sum,Road road[])
    {
    	//初始化 
    	int i;
    	int N,E,a,b;
    	N=g.n; 
    	E=g.e;
    	sum=0;
    	for(i=0;i<N;i++)
    	{
    		v[i]=i;
    	}
    	sort(road,E);//按照边的长度进行排序
    	for(i=0;i<E;i++)
    	{
    		a=getRoot(road[i].a);
    		b=getRoot(road[i].b);
    		if(a!=b)
    		{
    			v[a]=b;
    			sun+=road[i].w; //error出错点 
    		}
    	} 
    }
    

    4.4 最短路算法

    #include <iostream>
    using namespace std;
    #define INF 99999999
    typedef struct
    {
    	int edges[maxSize][maxSize];
    	int n,e;
    }MGraph;
    /**************Dijkstra算法********************/
    void Dijkstra(MGraph g,int v,int dist[],int path[])
    {
    	int set[maxSize];
    	int min,i,j,u;
    	for(i=0;i<g.n;++i)
    	{
    		dist[i]=g.edges[v][i];
    		set[i]=0;
    		if(g.edges[v][i]<INF)
    		{
    			path[i]=v;
    		}
    		else
    		path[i]=-1;
    	}
    	set[v]=1;path[v]=-1;
    	/*关键操作*/
    	for(i=0;i<g.n-1;i++)
    	{
    		min=INF;
    		//选取最小的点 
    		for(j=0;j<g.n;++j)
    		{
    			u=j;
    			min=dist[j];
    		}
    		set[u]=1;
    		//更新路径 
    		for(j=0;j<g.n;++j)
    		{
    			if(set[j]==0 && dist[j]>dist[u]+g.edges[u][j]) //忘记set为0 
    			{
    				dist[j]=dist[u]+g.edges[u][j];
    				path[j]=u; //更新前驱 
    			}
    			
    		}
    	}
    }
    // 打印路径
    void printPath(int path[],int a)
    {
    	int stack[maxSize];int top=-1;
    	while(path[a]!=-1)
    	{
    		stack[++top]=a;
    		a=path[a];
    	}
    	stack[++top]=a;
    	while(top!=-1)
    	cout<<stack[top--]<<" ";
    	cout<<endl;
    }
    /**************Flyod算法**********/
    void printpath(int u,int v,int path[][max])
    {
    	if(A[u][v]==INF) 
    	else
    	{
    		if(path[u][v]==-1)
    		cout<<u<<"--->"<<v;
    		else
    		{
    			int mid=path[u][v];
    			printpath(u,mid,path);
    			printpath(mid,v,path);
    		}
    	}
    }
    void Flyod(MGraph *g,int path[][maxSize],int A[][maxSize])
    {
    	int i,j,k;
    	for(i=0;i<g->n;i++)
    	for(j=0;j<g->n;j++)
    	{
    		A[i][j]=g->edges[i][j];
    		path[i][j]=-1;
    	}
    	for(k=0;k<g->n;++k)
    		for(i=0;i<g->n;i++)
    			for(j=0;j<g->n;j++)
    			{
    				if(A[i][j]>A[i][k]+A[k][j])
    				{
    					A[i][j]=A[i][k]+A[k][j];
    					path[i][j]=k;
    				}
    			}
    }
    int main()
    {
    	return 0;
    }
    

    五、查找

    4.1 顺序查找(带哨岗)

    #include <iostream>
    using namespace std;
    int SeqSearch(int A,int k,int len)
    {
    	A[0]=k;//存放岗哨
    	for(int i=len;A[i]!=k;i--);
    	return i;//如i为0,说明查找失败 
    }
    int main()
    {
    	return 0;
    }
    

    4.2 折半查找

    #include <iostream>
    using namespace std;
    int Bsearch(int R[],int low,int high,int k)
    {
    	int mid;
    	while(low<=high)
    	{
    		mid=(low+high)/2;
    		if(R[mid]==k)
    		return mid;
    		else if(R[mid]>k)
    		high=mid-1;
    		else
    		low=mid+1;
    	}
    	return -1; //查找失败则返回-1 
    }
    int main()
    {
    	int R[150];
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++)
    	cin>>R[i];
    	int flag = Bsearch(R,0,n-1,5);
    	cout<<R[flag]<<endl;
    	return 0;
    } 
    

    4.3 二叉排序树

    #include <iostream>
    using namespace std;
    typedef struct BTNode
    {
    	int key;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode;
    /**
    * 查找关键字 
    */
    BTNode* BSTSearch(BTNode *bt,int key)
    {
    	if(bt==NULL)
    	return NULL;
    	else
    	{
    		if(bt->key==key)
    			return bt;
    		else if(key<bt->key)
    			return BSTSearch(bt->lchild,key); //小于根节点,到左子树查找
    		else
    			return BSTSearch(bt->rchild,key); //查找右子树 
    	}
    }
    /**
    * 插入关键字 
    **/
    BTNode *(BTNode *&bt,int key)
    {
    	if(bt==NULL)
    	{
    		bt=(BTNode*)malloc(sizeof(BTNode));
    		bt->lchild=bt->rchild=NULL;
    		bt->key=key;
    		return 1;
    	}
    	else
    	{
    		if(bt->key==key)
    			return 0;
    		else if(key<bt->key)
    			return BSTInsert(bt->lchild,key);
    		else
    			return BSTInsert(bt->rchild,key);
    	}
    }
    /**
    * 构造二叉排序树 
    **/
    void CreatBST(BTNode *&bt,int key[],int n)
    {
    	int i;
    	bt=NULL;
    	for(i=0;i<n;i++)
    		BSTInsert(bt,key[i]);
    }
    int main()
    {
    	return 0;
    }
    

    六、排序

    6.1 直接插入排序

    #include <iostream>
    using namespace std;
    void InsertSort(int R[],int n)
    {
    	int i,j;
    	int temp;
    	for(i=1;i<n;i++) //i从1开始 
    	{
    		temp=R[i];
    		j=i-1; //key
    		while(j>=0 && temp<R[j])
    		{
    			R[j+1]=R[j]; //向后移动 
    			--j;
    		}
    		R[j+1]=temp;
    	}
    }
    int main()
    {
    	int R[15];
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{
    		cin>>R[i];
    	}
    	InsertSort(R,n);
    	for(int i=0;i<n;i++)
    	{
    		cout<<R[i]<<" ";
    	}
    	return 0;
    }
    

    6.2 折半插入排序

    #include <iostream>
    using namespace std;
    void BinsertSort(int A[],int len)
    {
    	int i,j,m,low,high;
    	for(i=2;i<=len;i++)
    	{
    		A[0]=A[i];//A[i]暂时存入A[0]中 
    		low=1;high=i-1;
    		while(low<=high)
    		{
    			m=(low+high)/2;
    			if(A[0]>R[m])
    				high=m-1;
    			else
    				low=m+1;
    		}
    		for(j=i-1;j>=high+1;--j)
    			A[j+1]=A[j];//元素后移
    		R[high+1]=R[0];//插入 
    	}
    }
     
    

    6.3 冒泡排序

    #include <iostream>
    using namespace std;
    void BubbleSort(int R[],int n)
    {
    	int i,j,flag;
    	int temp;
    	for(i=n-1;i>=1;i--)
    	{
    		flag=0;
    		for(j=1;j<=i;j++)
    		{
    			if(R[j-1]>R[j])
    			{
    				temp=R[j];
    				R[j]=R[j-1];
    				R[j-1]=temp;
    				flag=1;
    			}
    		}
    		if(flag==0)
    		return;
    	}
    }
    int main()
    {
    	int R[15];
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{
    		cin>>R[i];
    	}
    	BubbleSort(R,n);
    	for(int i=0;i<n;i++)
    	cout<<R[i]<<" ";
    	return 0;
    }
    

    6.4 快速排序

    #include <iostream>
    #include<stdlib.h>
    using namespace std;
    int sum;
    void QuickSort(int R[],int low,int high)
    {
    	sum++;
    	int temp;
    	int i=low,j=high;
    	if(low<high)
    	{
    		
    		temp=R[low]; //选出中间点
    		while(i<j)
    		{
    			while(j>i && R[j]>=temp) j--; //先从右往左 
    			if(i<j)
    			{
    				R[i]=R[j];
    				++i; //key 
    			}
    			
    			//从左往右扫描
    			while(i<j && R[i]<=temp) i++;
    			if(i<j)
    			{
    				R[j]=R[i];
    				j--; //key 
    			}
    			R[i]=temp;
    			QuickSort(R,low,i-1);
    			QuickSort(R,i+1,high);
    		}
    	}
    }
    

    6.5 二路归并排序

    #include <iostream>
    using namespace std;
    #define max 100
    void merge(int A[], int L1, int R1, int L2, int R2)
    {
         int i=L1,j=L2;
         int temp[max], index=0;
         while(i<=R1 && j<=R2)
    	 {
            if(A[i] <= A[j])
    		{
                temp[index++] = A[i++];
            }
    		else
    		{
                temp[index++] = A[j++];
            }
        }
        while(i <= R1) temp[index++] = A[i++];
        while(j <= R2) temp[index++] = A[j++];
        //将temp的值一一赋给A[L1~R2]
        for(int i=0; i<index; i++)
    	{
            A[L1+i] = temp[i];
        }
    }
    void mergeSort(int A[],int low,int high)
    {
    	if(low<high)
    	{
    		int mid=(low+high)/2;
    		mergeSort(A,low,mid); //归并前半段 
    		mergeSort(A,mid+1,high); //归并后半段 
    		merge(A,low,mid,mid+1,high); //将low->mid和mid+1->high两个有序序列合并成一个有序序列 
    	}
    }
    int main()
    {
    	int R[max];
    	for(int i=0;i<6;i++)
    	cin>>R[i];
    	mergeSort(R,0,5);
    	for(int i=0;i<6;i++)
    	cout<<R[i]<<" ";
    	return 0;
    } 
    
    展开全文
  • 数据结构考研知识点总结.pdf

    千次阅读 2021-06-28 12:26:49
    数据结构考研真题及知识点解析考察目标1. 掌握数据结构的基本概念、基本原理和基本方法。2. 掌握数据的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析。3. 能够运用数据...

    数据结构考研真题及知识点解析

    考察目标

    1. 掌握数据结构的基本概念、基本原理和基本方法。

    2. 掌握数据的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复

    杂度与空间复杂度的分析。

    3. 能够运用数据结构的基本原理和方法进行问题的分析与求解;具备采用C、C++或

    Java语言设计与实现算法的能力。

    第2章 线性表

    一、考研知识点

    (一)线性表的定义和基本操作

    (二)线性表的实现

    1.顺序存储

    2.链式存储

    3.线性表的应用

    二、考查重点

    1.线性结构的特点;

    2.线性表在顺序存储及链式存储方式下的基本操作及其应用;

    3.线性表的顺序存储及链式存储情况下,其不同和优缺点比较,及其各自适用的场合。

    单链表中设置头指针、循环链表中设置尾指针而不设置头指针的各自好处;

    4.能分析所写算法的时间和空间复杂度。

    分析:

    线性表是一种最简单的数据结构,在线性表方面,主要考查线性表的定义和基本操作、

    线性表的实现。在线性表实现方面,要掌握的是线性表的存储结构,包括顺序存储结构和链

    式存储结构,特别是链式存储结构,是考查的重点。另外,还要掌握线性表的基本应用。

    线性表一章在线性结构的学习乃至整个数据结构学科的学习中,其作用都是不可低估

    的。线性表一章小的知识点比较少,一般会出一个综合题,并且容易和第三章、第九章和第

    十章的内容结合来考,注意对基本知识的理解,能够利用书上的理论解决具体问题。学习过

    程中要注意多积累,多看、多写一些相关算法。

    三、考研真题

    (一)选择题

    近几年第2章没有考选择题,只有两个计算时间复杂度的题目,因为此章主要是线性表

    的操作,而且又是这门课的一个基础,考综合题的可能性比较大,可以和第3章、第9章和

    第10章的内容结合来出题。

    1.(11年)设n是描述问题规模的非负整数,下面程序片段的时间复杂度是 ( A )。

    x 2;

    while(x

    A.O(logn) B.O(n) C.O(nlogn) D.O(n)2

    2. (12年)求整数n (n> 0)的阶乘的算法如下,其时间复杂度是 ( B )。

    int fact(int n)

    {

    if(n< 1) return 1;

    return n*fact(n-1);

    }

    A. o(logn) B. O(n)2 C. O(nlogn)2 D. O(n)2

    分析:考查的是算法时间复杂度的计算。可以放在第二章,实际这内容贯穿每一章内容

    中算法的度量。

    (二)综合题

    1. (09年)已知一个带有表头结点的单链表结点结构为(data,link),假设该链表只给

    出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒

    数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;

    否则,只返回0。要求:

    (1)描述算法的基本设计思想;

    (2)描述算法的详细实现步骤;

    (3)根据设计思想和实现步骤,采用程序设计语言描述算法 (使用C或C++或JAVA语

    言实现),关键之处给出简要注释。

    分析:此题考查线性表的链式存储,主要是线性表的基本操作的应用。做此题时要把握

    算法的效率。

    (1)算法基本思想如下:从头到尾遍历单链表,并用指针p指向当前结点的前k个结

    点。当遍历到链表的最后一个结点时,指针p所指向的结点即为所查找的结点。

    (2)详细实现步骤:增加两个指针变量和一个整型变量,从链表头向后遍历,其中指

    针p1指向当前遍历的结点,指针p指向p1所指向结点的前k个结点,如果p1之前没有k

    个结点,那么p指向表头结点。用整型变量i表示当前遍历了多少结点,当i>k时,指针p

    随着每次遍历,也向前移动一个结点。当遍历完成时,p或者指向表头结点,或者指向链表

    中倒数第k个位置上的结点。

    (3)算法描述:

    int locate(Linklist list, int k)

    展开全文
  • 覆盖考研数据结构各章节经典题目代码 + 代码模板 图的内容依然丰富 适用于期末复习+考研数据结构背诵
  • 考研数据结构的知识点汇总

    千次阅读 多人点赞 2019-10-24 16:24:49
    第一章 1.数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被...5.数据结构:指互相之间存在着一种或多种特定关系的数据元素的集合。包括逻辑结构,存储结构和对数据的运算。(数据元素都不...
  • 本人是2021年应届考生,现已上岸,这是我在复习备考期间总结的计算机408中的数据结构选择题,一共有34页。
  • 王道考研数据结构代码总结

    万次阅读 多人点赞 2020-07-31 20:46:22
    6、先序线索化二叉树 7、后序线索化二叉树 8、先序,中序,后序线索二叉树总结 9、平衡二叉树 五、排序 1、插入排序 (1)直接插入排序 (2)折半插入排序 (3)希尔排序 2、交换排序 (1)冒泡排序 (2)快速排序 3...
  • //二叉树的顺序存储,用于堆排序(完全二叉树) ~ 数组 (+ 长度) //且数组第0位一般不放数据;用“0”表示树中不存在的空节点(因为不一定是完全二叉树) typedef struct BiTNode{ //二叉树的链式存储 ElemType ...
  • │ 清华计算机考研数据结构复习提要.pdf │ 算法与数据结构试题及分析.doc │ 考研《数据结构》必须掌握的知识点与算法.doc │ 考研数据结构,各种算法的经解分析.doc │ 考研用算法.doc │ 计算机数据结构考研讲义....
  • 华北电力大学计算机考研844 842 数据结构 名词解释整理
  • 考研数据结构代码整理

    万次阅读 多人点赞 2019-10-07 22:10:37
    顺序表的基本操作2.1)初始化顺序表2.2)求指定位置元素2.3)插入数据元素2.4)按元素值查找2.5)删除数据元素2.6)顺序表的元素逆置2.7)删除下标为i~j的数据元素2.8)Partition操作3. 单链表的基本操作3.1)初始...
  • 考研数据结构100天 Day1:在带头结点的单链表L中,删除所有值为X的节点,并释放其空间,假设值为的X节点不唯一,试编写算法以实现上述操作 void Del-X(LinkList &L,int x){ LNode *p=L->next; LNode *pre=L...
  • 计算机考研数据结构代码题总结 链表 题目1 在带头节点的单链表L中,删除所有值为X的结点,并释放其空间,假设值为X的节点不唯一,试编写算法实现。 .算法思路 1、图解 . 2、图解含义描述 实现带头节点的单链表的...
  • 基数排序主要解决的问题 数据元素的关键字可以方便地拆分为d组,且d较小 每组关键字的取值范围不大,即r较小 数据元素个数n较大 9 外部排序 概念:数据元素太多,无法一次性全部读入内存进行排序 实现方法:使用归并...
  • 数据结构习题集leetcode21PAT 6-1 单链表逆转 (20 分)leetcode 141. 环形链表PAT 6-2 顺序表操作集 (20 分) leetcode21 /* Created by salmon on 2021-9-14 21:27. */ /** * Definition for singly-linked list....
  • 数据结构总结及思维导图(王道考研

    千次阅读 多人点赞 2020-07-27 12:31:52
    数据结构 第一章:数据结构的 基本概念 定义 在任何问题中,数据元素都不是孤立存在的,而是在它们之间存在着某种关系,这种数据元素相互之间的关系称为结构(Structure)。数据结构是相互之间存在一种或多种特定...
  • 适用于考研、准备数据结构期末考的人群,一共100道题,以“习题+分析”形式解题,部分题目含知识拓展。
  • │ 清华计算机考研数据结构复习提要.pdf │ 算法与数据结构试题及分析.doc │ 考研《数据结构》必须掌握的知识点与算法.doc │ 考研数据结构,各种算法的经解分析.doc │ 考研用算法.doc │ 计算机数据结构考研讲义....
  • 1.设将 n(n>1)个整数存放在一维数组 R 中。试着设计一个在时间复杂度和空间复杂度都尽可能高效的算法,将 R 中保存...//先将 n 个数据 x 0 ,x 1, …,xn-2,xn-1 原地逆置,得到 x n-1 ,x n-2 ,…,x,x 0 ,然后再将 n-p
  • 2003年至2017年华中科技大学数据结构术语总结,个人总结归纳,并参于了2019年华科大考研大军,重复率极大,2019年考的术语里面都有。