数据结构_数据结构c语言 - CSDN
数据结构 订阅
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 [1] 展开全文
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 [1]
信息
外文名
data structure
具体指向
特定关系的数据元素的集合
有关技术
检索算法和索引技术
中文名
数据结构
解    释
计算机存储、组织数据的方式
数据结构定义
数据结构(data structure)是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之,数据结构是相互之间存在一种或多种特定关系的数据元素的集合,即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系,分为逻辑结构和存储结构。 [2]  数据的逻辑结构和物理结构是数据结构的两个密切相关的方面,同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构,而算法的实现依赖于指定的存储结构。 [2]  数据结构的研究内容是构造复杂软件系统的基础,它的核心技术是分解与抽象。通过分解可以划分出数据的3个层次;再通过抽象,舍弃数据元素的具体内容,就得到逻辑结构。类似地,通过分解将处理要求划分成各种功能,再通过抽象舍弃实现细节,就得到运算的定义。上述两个方面的结合可以将问题变换为数据结构。这是一个从具体(即具体问题)到抽象(即数据结构)的过程。然后,通过增加对实现细节的考虑进一步得到存储结构和实现运算,从而完成设计任务。这是一个从抽象(即数据结构)到具体(即具体实现)的过程。 [3] 
收起全文
精华内容
参与话题
  • 数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。 为什么要学数据结构? 首先,因为数据结构作为...

    系列文章

    第一章:基础知识

    第二章:线性表

    第三章:栈和队列 

    第四章:字符串和数组

    第五章:树和二叉树

    第六章:图

    第七章:排序算法


    前言

    数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分

    为什么要学数据结构?

    首先,因为数据结构作为计算机专业的专业基础课程,是计算机考研的必考科目之一,如果打算报考计算机专业的研究生,你必须学好它;其次,数据结构是计算机软考、计算机等级考试等相关考试的必考内容之一,想要顺利通过这些考试,你也必须学好它;最后,数据结构还是你打算今后学习计算专业其他课程的基础,如操作系统、编辑原理、数据库管理系统、软件工程、人工智能等。总而言之,你既然已经与计算机接轨就必须掌握好它。

    如何学习数据结构?

    对于初学者来说,数据结构是门概念上比较抽象的课程,不是太容易掌握,需要构思和理解。万事开头难,只要你掌握了学习这门课的方法和技巧,就会变得很容易了。不管学什么,首先应该做好充分的心理准备,建立好自信心,拥有一颗战胜困难的决心,才能不畏惧、不退缩,直至胜利归来。其次,就是最好有C语言基础,这样学起来事半功倍,当然没有C语言基础也行,可以一边学数据结构一边巩固C语言知识。最后,就是多动手!多动手!多动手!重要的事情说三遍!只有亲自动手上机操作或用笔在纸上画画写写才能加深映像,方便理解记忆。?


    第一章:基础知识

    第1节:数据结构概述

      1.1 概念术语

      1.2数据的逻辑结构

      1.3数据的存储(物理)结构

      1.4抽象数据类型

      1.5算法

    1.6时间复杂度

    1.7空间复杂度

    第2节:C语言基础

    2.1 开发环境

    2.2 递归与非递归(重点)

    2.3参数传递

    2.4 结构体和联合体

    2.5 链表

    2.6 内存的分配与释放


     

    第1节:数据结构概述

    数据结构的主要任务是通过分析数据对象的结构特征,包括逻辑结构及数据对象之间的关系,然后把逻辑结构表示成计算机课实现的物理结构,从而便于计算机处理。

     

      1.1 概念术语

    (1)数据(Data)是能被计算机处理的符号或符号集合,含义广泛,可理解为“原材料”。如字符、图片、音视频等。

    (2)数据元素(data element)是数据的基本单位。例如一张学生统计表。

    (3)数据项(data item)组成数据元素的最小单位。例如一张学生统计表,有编号、姓名、性别、籍贯等数据项。

    (4)数据对象(data object)是性质相同的数据元素的集合,是数据的一个子集。例如正整数N={1,2,3,····}。

    (5)数据结构(data structure)是数据的组织形式,数据元素之间存在的一种或多种特定关系的数据元素集合。

    (6)数据类型(data type)是按照数据值的不同进行划分的可操作性。在C语言中还可以分为原子类型和结构类型。原字类型是不可以再分解的基本类型,包括整型、实型、字符型等。结构类型是由若干个类型组合而成,是可以再分解的。

     

      1.2数据的逻辑结构

    逻辑结构(logical structure)是指在数据中数据元素之间的相互关系。数据元素之间存在不同的逻辑关系构成了以下4种结构类型。

    (1)集合结构:集合的数据元素没有其他关系,仅仅是因为他们挤在一个被称作“集合”的盒子里。

    (2)线性结构:线性的数据元素结构关系是一对一的,并且是一种先后的次序,就像a-b-c-d-e-f-g·····被一根线穿连起来。

    (3)树形结构:树形的数据元素结构关系是一对多的,这就像公司的部门级别,董事长-CEO\CTO-技术部\人事部\市场部.....。

    (4)图结构:图的数据元素结构关系是多对多的。就是我们常见的各大城市的铁路图,一个城市有很多线路连接不同城市。

     

      1.3数据的存储(物理)结构

    存储结构(storage structure)也称为物理结构(physical structure),指的是数据的逻辑结构在计算机中的存储形式。数据的存储结构一般可以反映数据元素之间的逻辑关系。分为顺序存储结构和链式存储结构。

    (1)顺序存储结构:是把数据元素存放在一组存储地址连续的存储单元里,其数据元素间的逻辑关系和物理关系是一致的。

    (2)链式存储结果:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的,数据元素的存储关系并不能反映其逻辑关系,因此需要借助指针来表示数据元素之间的逻辑关系。

     

    小结:数据的逻辑结构和物理结构是密切相关的,在学习数据的过程中会发现,任何一个算法的设计取决于选定的数据逻辑结构,而算法的实现依赖于所采用的存储结构。

     

      1.4抽象数据类型

    抽象数据类型(abstract data type,ADT)是描述具有某种逻辑关系的数据模型,并对在数学模型上进行的一组操作。抽象数据类型描述的是一组逻辑上的特性,与在计算机内部表示无关,计算机中的整数数据类型是一个抽象数据类型,不同处理器可能实现方法不同,但其逻辑特性相同,即加、减、乘、除等运算是一致的。“抽象”的意思是数据类型的数学抽象特性而不是指它们的实现方法。抽象数据类型体现了程序设计中的问题分解、抽象、信息隐藏等特性,可以把现实中的大问题分解为多个规模小且容易处理的小问题,然后建立起一个能被计算机处理的数据,并把每个功能模块的实现细节作为一个独立的单元,从而使具体实现过程隐藏起来。就类似建一栋房子,分成若干个小任务,如地皮规划、图纸设计、施工、装修等,整个过程与抽象数据类型中的问题分解类似。而搬砖人不需要了解图纸设计如何,设计图纸人员不需要了解施工的地基、砌墙的具体细节,装修工人不用关系图纸和搬砖过程,这就是抽象类型中的信息隐藏。

    抽象数据类型的概念可能让初学者不太容易理解。例如线性表的抽象数据类型的描述数据对象集合:线性表的数据对象集合为{a1,a2,a3,····,an},每个元素的类型均为DataType。其中,除了第一个元素a1外,每一个元素有且只有一个直接前驱元素;除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的。

     

      1.5算法

    算法(algorithm)是解决特定问题求解步骤的描述,在计算机中表现为有限的操作序列。在数据类型建立起来之后,就要对这些数据类型进行操作,建立起运算的集合即程序。运算的建立、方法好坏直接决定着计算机程序原型效率的高低。

    (1)数据结构和算法的关系

    两者基友联系又有区别。联系是程序=算法+数据结构。数据结构是算法实现的基础,算法总是要依赖某种数据结构来实现的。算法的操作对象是数据结构。区别是数据结构关注的是数据的逻辑结构、存储结构有一集基本操作,而算法更多的是关注如何在数据结构的基本上解决实际问题。算法是编程思想,数据结构则是这些思想的基础。

    (2)算法的五大特性

    有穷性,是指算法在执行有限的步骤之后,自动结束而不是出现无限循环,并且每一个步骤在可接受的时间内完成。

    确定性,是指算法执行的每一步骤在一定条件下只有一条执行路径,也就是相同输入只能有一个唯一的输出结果。

    可行性,是指算法每一步骤都必须可行,能够通过有限的执行次数完成。

    输入,是指算法具有零个或多个输入。

    输出,是指算法至少有一个或多个输出。

     

    1.6时间复杂度

    在进行算法分析时,语句总是执行次数 T(n) 是关于问题规模 n 的函数。进而分析次数T(n)随规模n的变化情况并确定T(n)的数量级。算法的时间复杂度就是算法的时间度量,记作T(n) = O(f(n))。它表示随问题规模n的增大,算法的执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中,f(n)是问题规模n的某个函数。

    算法的时间复杂度是衡量一个算法好坏的重要指标。一般情况下,随着规模n的增大,次数T(n)的增长较慢的算法为最优算法。常见时间复杂度从小到大依次排列:O(1) < O(log2n) < O(n) < O(n²)<O(n³) ····<O(n!)

    例如:

    (a) 1;      // 时间复杂度为O(1)

    (b)for(i =1 ; i<=n ;i++){  x= x+1;}    // 时间复杂度为O(n),称为线性阶

    (c)for(i =1 ; i<=n ; i++){for(j=1;j<=n;j++){  x=x+1 } }  // 时间复杂度为O(n²),称为平方阶

     

    1.7空间复杂度

    空间复杂度(space complexity)作为算法所需存储空间的量度,记做S(n) = O (f(n))。其中,n为问题的规模;f(n)为语句关于n的所占存储空间的函数。

    一般情况下,一个程序在机器上运行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单位。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常量,则称此算法为原地工作,空间复杂度为O(1)。

     

    第2节:C语言基础

    C语言作为数据结构的算法描述语言,广泛应用于系统软件和应用软件的开发。在真正开发学习数据结构知识之前,先复习一下C语言基础,为数据结构的学习扫清障碍。本节主要针对重点和难点部分详细讲解,包括开发环境、函数与递归、指针、参数传递、动态内存分配及结构体、联合体。

     

    2.1 开发环境

    C语言常见的开发环境有很多种,如LCC、Turbo C2.0、Visual C++、Borland C++,本章主要介绍使用最多的Turbo C 2.0和Visual C++ 6.0。

    (1)Turbo C 2.0 :1989年,美国Borland公司推出,简称TC。它集编辑、编译、连接和运行一体的C程序集成开发环境。界面简单、上手容易、使用方便,通过一个简单的主界面可以很容易编辑、编译和链接程序,也是初学者广发使用的开发工具。

    (2)Visual C++6.0:是强大的C/C++软件开发工具,使用非常广泛,已经成为首选的开发工具。利用它可以开发Windows SDK、MFC等应用程序。

     

    2.2 递归与非递归(重点)

    在数据结构与算法实践过程中,经常会遇到利用递归实现算法的情况。递归是一种分而治之、将复杂问题转换成简单问题的求解方法。使用递归可以使编写的程序简洁、结构清晰,程序的正确性很容易证明,不需要了解递归调用的具体细节。

    (1)函数的递归:就是函数自己调用自己,即一个函数在调用其他函数的过程中,又出现对自身的调用,这种函数称为递归函数。函数的递归调用就是自己调用自己,可以直接调用自己也可以间接调用。其中,在函数中直接调用自己称为函数的直接递归调用;如果函数f1调用了函数f2又再次调用了函数f1,这种调用的方式我们称之为间接递归调用。

    例1:利用递归求n! :有两种情况,当n=0递归结束,返回值为1 ;当n !=0时,继续递归。

    //递归求n!函数实现
    
    int factorial (int  n){
    
        if(n ==0 )
            return 1;
    
        else
            return n*factorial(n-1);
    }
    

      例2:已知有数组a[] ,要求利用递归实现求n个数中的最大值。

    a[] ={0,···,n-1};
    
    int findMax(int a[] ,int n){
    
        int  m ;
    
        if (n<=1)
            return a[0];
    
        else
        {
            m = findMax(a,n-1);
            return a[n-1] >= m ?a[n-1] : m ;//找到最大值
        }
    }

     

    (2)迭代与递归

    迭代与递归是程序设计中最常用的两种结构。任何能使用递归解决的问题都能使用迭代的方法解决。迭代和递归的区别是,迭代使用的是循环结构,递归使用的是选择结构。大量的递归会耗费大量的时间和内存,每次递归调用都会建立函数的一个备份,会占用大量的内存空间。迭代则不需要反复调用函数和占用额外的内存。对于较为简单的递归问题,可以利用简单的迭代将其转化为非递归。而对于较为复杂的递归问题,需要通过利用数据结构中的栈来消除递归。

    (3)指针

    是C语言中一个重要概念,也是最不容易掌握的内容。指针常常用在函数的参数传递和动态内存分配中。指针与数组相结合,使引用数组成分的形式更加多样化,访问数组元素的手段更加灵活;指针与结构体结合,利用系统提供的动态存储手段,能构造出各种复杂的动态数据结构;利用指针形参,使函数能实现传递地址形参和函数形参的要求。接下里会介绍指针变量的概念、指针与数组、函数指针与指针函数。

    指针是一种变量,也称之为指针变量,它的值不少整数、浮点数和字符,而是内存地址。指针的值就是变量的地址,而变量又拥有一个具体的值。因此,可以理解为变量名直接引用了一个值,指针间接地引用了一个值。

    指针可以与变量结合,也可以与数组结合使用。指针数组是一种存放一组变量的地址。数组指针是一个指针,表示该指针指向数组的指针。数组指针可以进行自增或自减运算,但是数组名则不能进行自增或自减运算,这是因为数组名是一个常量指针,它是一个常量,常量值是不能改变的。函数指针与指针函数同理。

     

    2.3参数传递

    (1)传值调用:分为实际参数和形式参数。例如:

    int GCD(int m ,int n);
    
    void main(){
        int a,b,v,
        v = GCD(a,b);  //实际参数
    }
    
    int GCD(int m ,int n){ //形式参数
        int r;
        r = m;
        do{
            m=n;
            n=r;
            r=m&n;
          }while(r);
    
        return n;
    }

    上面的函数参数传递属于参数的单向传递,即a和b可以把值传递给m和n,而不是可以把m和n传递给a和b。实际参数和形式参数的值的改变都不会互相收到影响。

    (2)传指针地址参数:略

     

    2.4 结构体和联合体

    也称共用体,是自定义的数据类型,用于构造非数值数据类型,在处理实际问题中应用非常广泛。数据结构中的链表、队列、树、图等结构都需要用到结构体。教师表结构体如下所示。

    //结构体类型
    struct teacher{
        //数据项
        int no;
        char name[20];
        char sex[4];
        char headship[8];
        char degree[6];
        long int phone;
    }

    与结构体一样,联合体也是一种派生的数据类型。但是与结构体不同的是,联合体的成员共享同一个存储空间。定义联合体一般形式如下所示。

    union 共用体名{
    
        成员列表;
    }
    变量列表;
    
    ——————————————————————————
    union data{
    
        int a ;
        float b;
        char c;
        double d;
    }abc;
    
    //或写成
    union data{
        int a;
        float b;
        char c;
        double d;
    };
    union data abc;
    
    

     

    2.5 链表

    在C语言中,处理已知数据可以使用数组。如果事先并不知道要处理的数据的个数,则需要使用链表结构。链表需要动态分配内存,链表的长度随时可以发生变化。链表有一个指针类型的成员指向自身,该指针指向与结构体一样的类型。例如如下语句:

    struct node{
        int data;
        struct data *next;
    }
    

    自引用结构体类型为struct node,该结构体类型有两个成员:整数成员data,指针成员next。成员next是指向结构体为struct node类型的指针。通过这种形式定义的结构体通过next指针把两个结构体变量连在一起。这种自引用结构体单元称为结点,结点之间通过箭头连接起来,构成一张表,称为链表。

    链表中第一个结点的指针称为头指针且可以访问链表的每一个结点。为了方便操作,在链表的第一个结点之前增加一个头结点。

    2.6 内存的分配与释放

    (1)malloc函数主要作用是分配一块长度为size的内存空间。void *malloc(unsigned int size);其中,size就是要分配的内存空间大小字节。使用时最好先检查一下是否分配成功,否则返回null,可以保证程序的正确运行。使用完分配后的空间要利用free函数及时释放。

    (2)free函数主要作用是将内存空间释放。void free (void *p); 其中,参数p指向要释放的内存空间。不能使用已经被free函数释放的内存空间。

     


    下一章:

    数据结构与算法——从零开始学习(二)线性表

     

     

    欢迎,😆大家关注公众号:(推送数据结构+算法+Java+人生感悟+理财知识+互联网事件等)

    展开全文
  • 数据结构知识整理

    万次阅读 多人点赞 2018-09-25 12:02:45
    1.数据结构:是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。 2.数据结构涵盖的内容: 3.基本概念和术语: 数据:对客观事物的符号表示,在计算机科学中是指所有能...

    基于严蔚敏及吴伟民编著的清华大学C语言版教材并结合网上相关资料整理(http://www.docin.com/p-2027739005.html)

    第一章:绪论

    1.数据结构:是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。

    2.数据结构涵盖的内容:

    3.基本概念和术语:

    数据:对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

    数据元素:数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。

    数据对象:性质相同的数据元素的集合,是数据的一个子集。

    数据结构:相互之间存在一种或多种特定关系的数据元素的集合。

    数据类型:一个值的集合和定义在这个值集上的一组操作的总称。

    4.算法和算法分析

    1)算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。

    算法五个特性:有穷性,确定性,可行性,输入,输出。

    2)算法设计要求:正确性,可读性,健壮性,效率与低存储量需求。

    3)算法分析:时间复杂度,空间复杂度,稳定性

     

    第二章:线性表

    1.线性结构特点:在数据元素的非空有限集合中,(1)存在唯一的一个被称做“第一个”的数据元素;(2)存在唯一的一个被称做“最后一个”的数据元素;(3)除第一个之外,集合中的每个数据元素均只有一个前驱;(4)除最后一个之外,集合中每个数据元素均只有一个后继。

    2.线性表定义:有限个性质相同的数据元素组成的序列。

    3.线性表的存储结构:顺序存储结构和链式存储结构

    顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

    通常用数组来描述数据结构中的顺序存储结构。

    链式存储结构: 其结点在存储器中的位置是随意的,即逻辑上相邻的数据元素在物理上不一定相邻。通过指针来实现。

    数据结构的基本运算:修改、插入、删除、查找、排序

    4.线性表的顺序表示和实现

    1)修改:通过数组的下标便可访问某个特定元素并修改。

    时间复杂度O(1)

    2) 插入:在线性表的第i个位置前插入一个元素

    实现步骤:

       ①将第n至第i 位的元素逐一向后移动一个位置;

       ②将要插入的元素写到第i个位置;

       ③表长加1。

       注意:事先应判断: 插入位置i 是否合法?表是否已满?

       应当符合条件: 1≤i≤n+1  或  i=[1, n+1]

       核心语句:

    for (j=n; j>=i; j--)

    a[j+1]=a[ j ]; 

    a[ i ]=x;   

    n++;

      插入时的平均移动次数为:n(n+1)/2÷(n+1)=n/2≈O(n)

    3)删除:删除线性表的第i个位置上的元素

      实现步骤:

      ①将第i+1 至第n 位的元素向前移动一个位置;

      ②表长减1。

      注意:事先需要判断,删除位置i 是否合法?

      应当符合条件:1≤i≤n  或  i=[1, n]

      核心语句:

    {

        for ( j=i+1; j<=n; j++ )

        a[j-1]=a[j]; 

        n--;

    }

      顺序表删除一元素的时间效率为:T(n)=(n-1)/2 O(n)

      顺序表插入、删除算法的平均空间复杂度为O(1)

    5.线性表的链式表示和实现

    线性链表:用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。

    一个数据元素称为一个结点,包括两个域:存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。

    由于链表的每个结点中只包含一个指针域,故线性链表又称为单链表。

    1)单链表的修改(或读取)

    思路:要修改第i个数据元素,必须从头指针起一直找到该结点的指针preturn p;  

    然后才能:p->data=new_value

    读取第i个数据元素的核心语句是:

    Linklist *find(Linklist *head ,int i)

    { 

       int j=1;

       Linklist *p;

       P=head->next;

       While((p!=NULL)&&(j<i))

       {

           p=p->next;

           j++;

        }

    }

    2)单链表的插入

    链表插入的核心语句:

    Step 1:s->next=p->next;

    Step 2:p->next=s;

    3)单链表的删除

    删除动作的核心语句(要借助辅助指针变量q):

    q = p->next;           //首先保存b的指针,靠它才能找到c;

    p->next=q->next;  //将a、c两结点相连,淘汰b结点;

    free(q) ;               //彻底释放b结点空间

    4)双向链表的插入操作

    设p已指向第i 元素,请在第 i 元素前插入元素 x:

    ① ai-1的后继从 ai ( 指针是p)变为 x(指针是s) :

                    s->next = p  ;   p->prior->next = s ;

    ② ai  的前驱从ai-1 ( 指针是p->prior)变为 x ( 指针是s);

                    s->prior = p ->prior ; p->prior = s ;

    5)双向链表的删除操作

    设p指向第i 个元素,删除第 i 个 元素

    后继方向:ai-1的后继由ai ( 指针p)变为ai+1(指针 p ->next );

                       p ->prior->next =  p->next  ;

    前驱方向:ai+1的前驱由ai ( 指针p)变为ai-1 (指针 p -> prior );

                     p->next->prior = p ->prior ;

    6.循环链表

    循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。

    循环链表的操作和线性链表基本一致,差别仅在于算法中的循环条件不是p或p->next是否为空,而是它们是否等于头指针。

    学习重点:

    • 线性表的逻辑结构,指线性表的数据元素间存在着线性关系。在顺序存储结构中,元素存储的先后位置反映出这种线性关系,而在链式存储结构中,是靠指针来反映这种关系的。

    • 顺序存储结构用一维数组表示,给定下标,可以存取相应元素,属于随机存取的存储结构。

    • 链表操作中应注意不要使链意外“断开”。因此,若在某结点前插入一个元素,或删除某元素,必须知道该元素的前驱结点的指针。

    • 掌握通过画出结点图来进行链表(单链表、循环链表等)的生成、插入、删除、遍历等操作。

    • 数组(主要是二维)在以行序/列序为主的存储中的地址计算方法。

    补充重点:

    • 每个存储结点都包含两部分:数据域和指针域(链域)

    • 在单链表中,除了首元结点外,任一结点的存储位置由 其直接前驱结点的链域的值 指示。

    • 在链表中设置头结点有什么好处?

        头结点即在链表的首元结点之前附设的一个结点,该结点的数据域可以为空,也可存放表长度等附加信息,其作用是为了对链表进行操作时,可以对空表、非空表的情况以及对首元结点进行统一处理,编程更方便。

    • 如何表示空表?

    (1)无头结点时,当头指针的值为空时表示空表;

    (2)有头结点时,当头结点的指针域为空时表示空表。

    • 链表的数据元素有两个域,不再是简单数据类型,编程时该如何表示?

     因每个结点至少有两个分量,且数据类型通常不一致,所以要采用结构数据类型。

    • sizeof(x)——  计算变量x的长度(字节数);

              malloc(m) —  开辟m字节长度的地址空间,并返回这段空间的首地址;

              free(p)   —— 释放指针p所指变量的存储空间,即彻底删除一个变量。

    • 链表的运算效率分析:

    (1)查找 

    因线性链表只能顺序存取,即在查找时要从头指针找起,查找的时间复杂度为 O(n)。

    (2) 插入和删除 

    因线性链表不需要移动元素,只要修改指针,一般情况下时间复杂度为 O(1)。

    但是,如果要在单链表中进行前插或删除操作,因为要从头查找前驱结点,所耗时间复杂度将是 O(n)。

    例:在n个结点的单链表中要删除已知结点*P,需找到它的前驱结点的地址,其时间复杂度为 O(n)

    • 顺序存储和链式存储的区别和优缺点?

        顺序存储时,逻辑上相邻的数据元素,其物理存放地址也相邻。顺序存储的优点是存储密度大,存储空间利用率高;缺点是插入或删除元素时不方便。

      链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便,使用灵活。缺点是存储密度小,存储空间利用率低。

    • 顺序表适宜于做查找这样的静态操作;

    • 链表宜于做插入、删除这样的动态操作。

    • 若线性表的长度变化不大,且其主要操作是查找,则采用顺序表;

    • 若线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。

    ① 数组中各元素具有统一的类型;

    ② 数组元素的下标一般具有固定的上界和下界,即数组一旦被定义,它的维数和维界就不再改变。

    ③数组的基本操作比较简单,除了结构的初始化和销毁之外,只有存取元素和修改元素值的操作。

    • 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素的 行下标  、列下标 和 元素值 。

    第三章:栈和队列

    1.栈:限定仅在表尾进行插入或删除操作的线性表。

    栈的基本操作:在栈顶进行插入或删除,栈的初始化、判空及取栈顶元素等。

    入栈口诀:堆栈指针top “先压后加”

    出栈口诀:堆栈指针top “先减后弹”

    top=0表示空栈。

     

    2.栈的表示和实现

         1)构造一个空栈S

        Status InitStack(SqStack &S)

        {

            S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType));

            if(!S.base) exit (OVERFLOW); //存储分配失败

                S.top = S.base;

                S.stacksize = STACK_INIT_SIZE;

                return OK;

        }

     

        2)返回栈顶元素

           Status GetTop(SqStack S, SElemType e) 

            {//若栈不空,则用e返回S的栈顶元素,并返回OK,否则返回ERROR

                if(S.top == S.base) return ERROR;

                e = *(S.top-1);

                return OK; 

            }//GetTop

     

        3)顺序栈入栈函数PUSH()

    Status Push(SqStack &S, SElemType e)

    { //插入元素e为新的栈顶元素

        if(S.top-S.base>=S.stacksize)//栈满,追加存储空间

       {

        s.base = (SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

        if(!S.base) exit(OVERFLOW);//存储分配失败

        S.top = S.base + S.stacksize;

        S.stacksize += STACKINCREMENT;

        }

        *S.top++ =e;

        return OK:

    }//PUSH

    4)顺序栈出栈函数POP()

    status Pop( SqStack &S,SElemType &e)

    { //若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK,否则返回ERROR

        if(S.top == S.base) return ERROR; 

        e=* —S.top;

        return OK;

            }

    3.栈的应用

    数制转换,括号匹配的检验,行编辑程序,迷宫求解,表达式求值,递归实现。

    4.队列:是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素。

    允许插入的一端叫做队尾,允许删除的一端叫做队头。

    除了栈和队列外,还有一种限定性数据结构是双端队列。双端队列是限定插入和删除操作在表的两端进行的线性表。

    5.链队列结点类型定义:

     typedef Struct QNode{

         QElemType        data;     //元素

         Struct   QNode   *next;  //指向下一结点的指针

       }Qnode , * QueuePtr ;

    链队列类型定义:

     typedef  struct {

      QueuePtr     front ; //队首指针

      QueuePtr     rear ; //队尾指针

      }  LinkQueue;

    链队示意图:

    ①  空链队的特征:front=rear

    ②  链队会满吗?一般不会,因为删除时有free动作。除非内存不足!

    ③  入队(尾部插入):rear->next=S; rear=S;

        出队(头部删除):front->next=p->next;

    6.顺序队

    顺序队类型定义:

    #define    QUEUE-MAXSIZE  100  //最大队列长度

         typedef    struct {

                QElemType     *base;    //队列的基址

                 int                    front;     //队首指针

                 int                     rear;    //队尾指针

           }SqQueue

    建队核心语句:

    q.base=(QElemType *)malloc(sizeof (QElemType)* QUEUE_MAXSIZE);       //分配空间

    顺序队示意图:

    7.循环队列:

    队空条件 :  front = rear       (初始化时:front = rear )

    队满条件: front = (rear+1) % N         (N=maxsize)

    队列长度(即数据元素个数):L=(N+rear-front)% N

    1)初始化一个空队列

    Status   InitQueue ( SqQueue  &q ) //初始化空循环队列 q

    {   

    q.base=(QElemType *)malloc(sizeof(QElemType)* QUEUE_MAXSIZE);   //分配空间

    if (!q.base)  exit(OVERFLOW);//内存分配失败,退出程序

       q.front =q.rear=0; //置空队列

        return OK;

     } //InitQueue;

     

    2)入队操作

    Status   EnQueue(SqQueue  &q,  QElemType e)

    {//向循环队列 q 的队尾加入一个元素 e

       if ( (q.rear+1) %  QUEUE_MAXSIZE ==  q.front)

                        return  ERROR ; //队满则上溢,无法再入队

            q.rear = ( q.rear + 1 ) %  QUEUE_MAXSIZE;

            q.base [q.rear] = e;    //新元素e入队

            return  OK;

     }// EnQueue;

     

    3)出队操作

    Status     DeQueue ( SqQueue  &q,    QElemType &e)

     {//若队列不空,删除循环队列q的队头元素,

            //由 e 返回其值,并返回OK

          if ( q.front = = q.rear )   return ERROR;//队列空

          q.front=(q.front+1) % QUEUE_MAXSIZE; 

          e = q.base [ q.front ] ;

         return OK;

        }// DeQueue

    • 链队列空的条件是首尾指针相等,而循环队列满的条件的判定,则有队尾加1等于队头和设标记两种方法。

    补充重点:

    1. 为什么要设计堆栈?它有什么独特用途?

    2. 什么叫“假溢出” ?如何解决?

     调用函数或子程序非它莫属;

     递归运算的有力工具;

     用于保护现场和恢复现场;

     简化了程序设计的问题。                         

    2.为什么要设计队列?它有什么独特用途?

     离散事件的模拟(模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列);

     操作系统中的作业调度(一个CPU执行多个作业);

     简化程序设计。

    答:在顺序队中,当尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。解决假溢出的途径———采用循环队列。

    4.在一个循环队列中,若约定队首指针指向队首元素的前一个位置。那么,从循环队列中删除一个元素时,其操作是先 移动队首位置 ,后 取出元素

    5.线性表、栈、队的异同点:

    相同点:逻辑结构相同,都是线性的;都可以用顺序存储或链表存储;栈和队列是两种特殊的线性表,即受限的线性表(只是对插入、删除运算加以限制)。

    不同点:① 运算规则不同:

    线性表为随机存取;

    而栈是只允许在一端进行插入和删除运算,因而是后进先出表LIFO

    队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO

     用途不同,线性表比较通用;堆栈用于函数调用、递归和简化设计等;队列用于离散事件模拟、OS作业调度和简化设计等。

     

    第四章:串

    1.串是数据元素为字符的线性表,串的定义及操作。

    串即字符串,是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表。

    串比较:int strcmp(char *s1,char *s2);            

    求串长:int strlen(char *s);                          

    串连接:char  strcat(char *to,char *from)   

    子串T定位:char strchr(char *s,char *c);

    2.串的存储结构,因串是数据元素为字符的线性表,所以存在“结点大小”的问题。

    模式匹配算法 

    串有三种机内表示方法:

     

    3.模式匹配算法 :

    算法目的:确定主串中所含子串第一次出现的位置(定位)

    定位问题称为串的模式匹配,典型函数为Index(S,T,pos)

    BF算法的实现—即编写Index(S, T, pos)函数

    BF算法设计思想:

    将主串S的第pos个字符和模式T的第1个字符比较,

    若相等,继续逐个比较后续字符;

    若不等,从主串S的下一字符(pos+1)起,重新与T第一个字符比较。 

    直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号,即匹配成功。

    否则,匹配失败,返回值 0。

    Int Index_BP(SString S, SString T, int pos)

    { //返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0.

     // 其中,T非空,1≤pos≤StrLength(S)

        i=pos;      j=1;

       while ( i<=S[0] && j<=T[0] ) //如果i,j二指针在正常长度范围,

         {  

           if (S[i] = = T[j] ) {++i, ++j; }   //则继续比较后续字符

           else {i=i-j+2; j=1;} //若不相等,指针后退重新开始匹配

          }

      if(j>T[0]) return i-T[0];  //T子串指针j正常到尾,说明匹配成功,  else return 0;        //否则属于i>S[0]情况,i先到尾就不正常

    } //Index_BP

    补充重点:

    1.空串和空白串有无区别?

    答:有区别。

    空串(Null String)是指长度为零的串;

    而空白串(Blank  String),是指包含一个或多个空白字符‘  ’(空格键)的字符串.

    2.“空串是任意串的子串;任意串S都是S本身的子串,除S本身外,S的其他子串称为S的真子串。”

     

    第五章:数组和广义表

    重点:二维数组的位置计算。

    矩阵的压缩存储:特殊矩阵(三角矩阵,对称矩阵),稀疏矩阵,

     

    第六章:树和二叉树

    1.树:是n(n≥0)个结点的有限集。(1)有且仅有一个特定的称为根(root)的结点;(2)当n>1时,其余的结点分为m(m≥0)个互不相交的有限集合T1,T2,…,Tm。每个集合本身又是棵树,被称作这个根的子树 。

    2.二叉树:是n(n≥0)个结点的有限集合,由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

    二叉树的性质,存储结构。

    性质1: 在二叉树的第i层上至多有2^(i-1)个结点(i>0)。

    性质2: 深度为k的二叉树至多有2^k-1个结点(k>0)。

    性质3: 对于任何一棵二叉树,如果其终端结点数为n0,度为2的结点数有n2个,则叶子数n0=n2+1

    性质4: 具有n个结点的完全二叉树的深度必为 [log2n]+1

    性质5: 对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号为2i+1;其双亲的编号必为i/2(i=1 时为根,除外)。

    二叉树的存储结构:

    1).顺序存储结构

    按二叉树的结点“自上而下、从左至右”编号,用一组连续的存储单元存储。

    若是完全/满二叉树则可以做到唯一复原。

    不是完全二叉树:一律转为完全二叉树!

    方法很简单,将各层空缺处统统补上“虚结点”,其内容为空。

    缺点:①浪费空间;②插入、删除不便 

    2).链式存储结构

    用二叉链表即可方便表示。一般从根结点开始存储。

    lchild

    data

    rchild

    优点:①不浪费空间;②插入、删除方便

    3.二叉树的遍历。

    指按照某种次序访问二叉树的所有结点,并且每个结点仅访问一次,得到一个线性序列。

    遍历规则:二叉树由根、左子树、右子树构成,定义为D、 L、R

    若限定先左后右,则有三种实现方案:

      DLR               LDR                   LRD

    先序遍历           中序遍历          后序遍历

    4.线索二叉树

    1)线索二叉树可以加快查找前驱与后继结点,实质就是将二叉链表中的空指针改为指向前驱或后继的线索,线索化就是在遍历中修改空指针。

    通常规定:对某一结点,若无左子树,将lchild指向前驱结点;若无右子树,将rchild指向后继结点。

    还需要设置左右两个tag,用来标记当前结点是否有子树。

    若ltag==1,lchild指向结点前驱;若rtag==1,rchild指向结点后继。

    2)线索二叉树的存储结构如下:

    typedef struct ThreadNode{

    ElemType data;

    struct ThreadNode *lchild, *rchild;

    int ltag, rtag;

    }ThreadNode, *ThreadTree;

    5.树和森林

    1)树有三种常用存储方式:

    ①双亲表示法     ②孩子表示法    ③孩子—兄弟表示法

    2)森林、树、二叉树的转换

    (1)将树转换为二叉树

    树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树:a.在所有兄弟结点之间加一连线

    b.对每个结点,除了保留与其长子的连线外,去掉该结点与其它孩子的连线。

    (2)将一个森林转换为二叉树:

    具体方法是:a.将森林中的每棵树变为二叉树;

    b.因为转换所得的二叉树的根结点的右子树均为空,故可将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。

    (3)二叉树转换为树

    是树转换为二叉树的逆过程。

    a.加线。若某结点X的左孩子结点存在,则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点,都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。

    b.去线。删除原二叉树中所有结点与其右孩子结点的连线。

     

    (4)二叉树转换为森林:

    假如一棵二叉树的根节点有右孩子,则这棵二叉树能够转换为森林,否则将转换为一棵树。

    a.从根节点开始,若右孩子存在,则把与右孩子结点的连线删除。再查看分离后的二叉树,若其根节点的右孩子存在,则连线删除。直到所有这些根节点与右孩子的连线都删除为止。

    b.将每棵分离后的二叉树转换为树。

    6.树和森林的遍历

    • 树的遍历

    ① 先根遍历:访问根结点;依次先根遍历根结点的每棵子树。

    ② 后根遍历:依次后根遍历根结点的每棵子树;访问根结点。

     

    • 森林的遍历

    ① 先序遍历

    若森林为空,返回;

    访问森林中第一棵树的根结点;

    先根遍历第一棵树的根结点的子树森林;

    先根遍历除去第一棵树之后剩余的树构成的森林。

    ② 中序遍历

    若森林为空,返回;

    中根遍历森林中第一棵树的根结点的子树森林;

    访问第一棵树的根结点;

    中根遍历除去第一棵树之后剩余的树构成的森林。

     

    7.哈夫曼树及其应用

    Huffman树:最优二叉树(带权路径长度最短的树)

    Huffman编码:不等长编码。

    树的带权路径长度:(树中所有叶子结点的带权路径长度之和)

    构造Huffman树的基本思想:权值大的结点用短路径,权值小的结点用长路径。

    构造Huffman树的步骤(即Huffman算法):

    (1) 由给定的 n 个权值{ w1, w2, …, wn }构成n棵二叉树的集合F = { T1, T2, …, Tn } (即森林) ,其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点,其左右子树均空。

    (2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树,且让新二叉树根结点的权值等于其左右子树的根结点权值之和。

    (3) 在F 中删去这两棵树,同时将新得到的二叉树加入 F中。

    (4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。

    具体操作步骤:

    应用:用于通信编码

      在通信及数据传输中多采用二进制编码。为了使电文尽可能的缩短,可以对电文中每个字符出现的次数进行统计。设法让出现次数多的字符的二进制码短些,而让那些很少出现的字符的二进制码长一些。假设有一段电文,其中用到 4 个不同字符A,C,S,T,它们在电文中出现的次数分别为 7 , 2 , 4 , 5 。把 7 , 2 , 4 , 5 当做 4 个叶子的权值构造哈夫曼树如图(a) 所示。在树中令所有左分支取编码为 0 ,令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列,就得这个叶子结点所代表的字符的二进制编码,如图(b) 所示。这些编码拼成的电文不会混淆,因为每个字符的编码均不是其他编码的前缀,这种编码称做前缀编码。

     

    第七章 图

    1.图的定义,概念、术语及基本操作(https://blog.csdn.net/eyishion/article/details/53234255)

    1)图的定义

    图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成;

    通常表示为:G(V,E),G表示一个图,V是图G中顶点的集合,E是图G中边的集合;

    注意:在图中数据元素称之为顶点(Vertex),而且顶点集合有穷非空;在图中任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示。

    2)图的分类

    • 按照有无方向,分为无向图有向图

    无向图:如果图中任意两个顶点之间的边都是无向边,则称该图为无向图。

    无向边:若顶点M到顶点N的边没有方向,称这条边为无向边,用无序偶对(M,N)或(N,M)表示。

    无向图是有顶点构成。如下图所示就是一个无向图G1:

    无向图G1= (V1,{E1}),其中顶点集合 V1={A,B,C,D};边集合E1={(A,B),(B,C),(C,D),(D,A)}

    有向图:如果图中任意两个顶点之间的边都是有向边,则称该图为有向图。

    有向边:若顶点M到顶点N的边有方向,称这条边为有向边,也称为弧,用偶序对 < M, N >表示;M表示弧尾,N表示弧头

    有向图是有顶点构成,如下图所示是一个有向图G2:

    有向图G2=(V2,{E2}),其中顶点集合 V2={A,B,C,D};弧集合E2={< A,D>,< B,A>,< C,A>,< B,C>}

    对于弧< A,D>来说, A是弧尾,D是弧头

    注意:无向边用 小括号 “()”表示,有向边用“<>”表示。

    无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。

    含有n个顶点的无向完全图有n * (n-1)/2条边。下面是一个无向完全图

    4个顶点,6条无向边,每个顶点对应3条边 ,一共4个顶点 总共 4*3,每个顶点对应的边都重复计算了一次,所以整体要除以2。

    对于n各 顶点和e条边的无向图满足:0<=e <= n(n-1)/2

    有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。

    含有n个顶点的无向完全图有n * (n-1)条边。下面是一个有向完全图

    4个顶点,12条弧,一共4个顶点 总共 4*3。

    2,按照弧或边的多少,分为稀疏图稠密图

    若边或弧的个数e<=NlogN(N是顶点的个数),称为系数图,否则称为稠密图;

    3,按照边或弧是否带权,其中带权的图统称为

    有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权。

    有向网中弧带权的图叫做有向网;

    无向网中边带权的图叫做无向网;

    比如下图就是一个无向图

     

    图的顶点和边间关系

    邻接点 度 入度 出度

    对于无向图,假若顶点v和顶点w之间存在一条边,则称顶点v和顶点w互为邻接点,边(v,w)和顶点v和w相关联。

    顶点v的是和v相关联的边的数目,记为TD(v);

    上面这个无向图G1,A和B互为邻接点,A和D互为邻接点,B和C互为邻接点,C和D互为邻接点;

    A的度是2,B的度是2,C的度是2,D的度是2;所有顶点度的和为8,而边的数目是4;

    图中边的数目e = 各个顶点度数和的一半。

    对于有向图来说,与某个顶点相关联的弧的数目称为度(TD);以某个顶点v为弧尾的弧的数目定义为顶点v的出度(OD);以顶点v为弧头的弧的数目定义为顶点的入度(ID)

    度(TD) = 出度(OD) + 入度(ID);

    比如上面有向图,

    A的度为3 ,A的入度 2,A的出度是1

    B的度为2 ,B的入度 0,B的出度是2

    C的度为2 ,C的入度 1,C的出度是1

    D的度为1 ,D的入度 1,D的出度是0

    所有顶点的入度和是4,出度和也是4,而这个图有4个弧

    所以 有向图的弧 e = 所有顶点入度的和 = 所有顶点出度的和

    路径 路径长度 简单路径 回路 (环) 简单回路(简单环)

    设图G=(V,{E})中的一个顶点序列{u=Fi0,Fi1,Fi2,….Fim=w}中,(Fi,j-1,Fi,j)∈E 1 ≤j ≤m,则称从顶点u到顶点w之间存在一条路径,路径上边或弧的数目称作路径长度

    若路径中的顶点不重复出现的路径称为简单路径

    若路径中第一个顶点到最后一个顶点相同的路径称为回路或环

    若路径中第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环

    比如下图 :

    从B 到 D 中顶点没有重复出现 ,所以是简单路径 ,边的数目是2,所以路径长度为 2。

    图1和图2都是一个回路(环),图1中出了第一个顶点和最后一个顶点相同之外,其余顶点不相同,所以是简单环(简单回路),图2,有与顶点C重复就不是一个简单环了;

    连通图相关术语

    连通图

    在无向图G(V,{E})中,如果从顶点V到顶点W有路径,则称V和W是连通的。如果对于图中任意两个顶点Vi、Vj∈V,Vi和Vj都是连通的,则称G是连通图。

    如下图所示:

    图1,顶点A到顶点E就无法连通,所以图1不是连通;图2,图3,图4属于连通图;

    连通分量

    若无向图为非连通图,则图中各个极大连通子图称作此图的连通分量;

    图1是无向非连通图,由两个连通分量,分别是图2和图3。图4尽管也是图1的子图,但是它不满足极大连通,也就说极大连通应当是包含ABCD四个顶点,比如图2那样;

    强连通图

    在有向图G(V,{E})中,如果对于每一对Vi ,Vj∈V,Vi≠Vj,从Vi到Vj和从Vj到Vi都存在有向路径,则称G是强连通图。

    图1不是强连通图因为D到A不存在路径,图2属于强连通图。

    强连通分量

    若有向图不是强连通图,则图中各个极大强连通子图称作此图的强连通分量;

    图1不是强连通图,但是图2是图1的强连通子图,也就是强连通分量;

    生成树和生成森林

    生成树

    假设一个连通图有n个顶点和e条边,其中n-1条边和n个顶点构成一个极小连通子图,称该极小连通子图为此连通图的生成树;

    图1是一个连通图含有4个顶点和4条边,图2,图3,图4含有3条边和4个顶点,构成了一个极小连通图子图,也称为生成树,为什么是极小连通子图,因为图2,图3,图4中少一条边都构不成一个连通图,多一条边就变成一个回路(环),所以是3条边和4个顶点构成的极小连通子图。图5尽管也是3个边4个顶点,但不是连通图。

    生成森林

    如果一个有向图恰有一个顶点的入度为0,其余顶点的入度为1,则是一颗有向树

    入度为0,相当于根节点,入度为1,相当于分支节点;,比如下面的有向图就是一个有向树

    顶点B的入度是0,其余顶点的入度是1;

    一个有向图的生成森林由若干颗有向树组成,含有图中全部顶点,但有足以构成若干颗不相交的有向树的弧;

    有向图1去掉一些弧后分解成2颗有向树,图2和图3,这两颗树就是有向图图1的生成森林;

    2.图的存储结构

    1).邻接矩阵(数组)表示法

    ① 建立一个顶点表和一个邻接矩阵

    ② 设图 A = (V, E) 有 n 个顶点,则图的邻接矩阵是一个二维数组 A.Edge[n][n]。

    注:在有向图的邻接矩阵中,

       第i行含义:以结点vi为尾的弧(即出度边);

       第i列含义:以结点vi为头的弧(即入度边)。

    邻接矩阵法优点:容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等等。

    邻接矩阵法缺点:n个顶点需要n*n个单元存储边(弧);空间效率为O(n^2)。

    2).邻接表(链式)表示法

    ① 对每个顶点vi 建立一个单链表,把与vi有关联的边的信息(即度或出度边)链接起来,表中每个结点都设为3个域:

    ② 每个单链表还应当附设一个头结点(设为2个域),存vi信息;

    ③ 每个单链表的头结点另外用顺序存储结构存储。

    邻接表的优点:空间效率高;容易寻找顶点的邻接点;

    邻接表的缺点:判断两顶点间是否有边或弧,需搜索两结点对应的单链表,没有邻接矩阵方便。

    3.图的遍历

    遍历定义:从已给的连通图中某一顶点出发,沿着一些边,访遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做图的遍历,它是图的基本运算。

    图的遍历算法求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

    图常用的遍历:一、深度优先搜索;二、广度优先搜索 

    深度优先搜索(遍历)步骤:(如下图)

    ① 访问起始点 v;

    ② 若v的第1个邻接点没访问过,深度遍历此邻接点;

    ③ 若当前邻接点已访问过,再找v的第2个邻接点重新遍历。

    基本思想:——仿树的先序遍历过程。

    遍历结果:v1->v2->v4->v8->v5-v3->v6->v7

    广度优先搜索(遍历)步骤:

    ① 在访问了起始点v之后,依次访问 v的邻接点;

    ② 然后再依次(顺序)访问这些点(下一层)中未被访问过的邻接点;

    ③ 直到所有顶点都被访问过为止。

    遍历结果:v1->v2->v3->v4->v5-v6->v7->v8

    4.图的连通性问题

    1)对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。

    2)最小生成树:在连通网的所有生成树中,所有边的代价和最小的生成树。

    构造最小生成树有很多算法,但是他们都是利用了最小生成树的同一种性质:MST性质(假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集,如果(u,v)是一条具有最小权值的边,其中u属于U,v属于V-U,则必定存在一颗包含边(u,v)的最小生成树),下面就介绍两种使用MST性质生成最小生成树的算法:普里姆算法和克鲁斯卡尔算法。

    Kruskal算法特点:将边归并,适于求稀疏网的最小生成树。

    Prime算法特点: 将顶点归并,与边数无关,适于稠密网。

    Prime算法构造最小生成树过程如下图:

    Kruskal算法构造最小生成树过程如下图:

    5.有向无环图及其应用

    有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。

    1)拓扑排序

    拓扑排序对应施工的流程图具有特别重要的作用,它可以决定哪些子工程必须要先执行,哪些子工程要在某些工程执行后才可以执行。

    我们把顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network),简称AOV网。

    一个AOV网应该是一个有向无环图,即不应该带有回路,因为若带有回路,则回路上的所有活动都无法进行(对于数据流来说就是死循环)。在AOV网中,若不存在回路,则所有活动可排列成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,我们把此序列叫做拓扑序列(Topological order),由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的,满足上述定义的任一线性序列都称作它的拓扑序列。

    拓扑排序的实现:

    a.在有向图中选一个没有前驱的顶点并且输出

    b.从图中删除该顶点和所有以它为尾的弧(白话就是:删除所有和它有关的边)

    c.重复上述两步,直至所有顶点输出,或者当前图中不存在无前驱的顶点为止,后者代表我们的有向图是有环的,因此,也可以通过拓扑排序来判断一个图是否有环。

    2)关键路径

    AOE-网是一个带权的有向无环图,其中,顶点表示事件,弧表示活动,权表示活动持续的时间。通常,AOE-网可用来估算工程的完成时间。

    关键路径:在AOE网中,从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径。

    关键活动:关键路径上的活动称为关键活动。关键活动:e[i]=l[i]的活动

    由于AOE网中的某些活动能够同时进行,故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。

    与关键活动有关的量

    (1)事件的最早发生时间ve[k]:ve[k]是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。 

    (2)事件的最迟发生时间vl[k]:vl[k]是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。

    (3)活动的最早开始时间e[i]:若活动ai是由弧<vk vj>表示,则活动ai的最早开始时间应等于事件vk的最早发生时间。因此,有:e[i]=ve[k]

    (4)活动的最晚开始时间l[i]:活动ai的最晚开始时间是指,在不推迟整个工期的前提下, ai必须开始的最晚时间。若ai由弧<vkvj>表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此,有:l[i]=vl[j]-len<vk,vj

    示例如下:

    6.最短路径

    从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径叫做最短路径。

    1)迪杰斯塔拉算法--单源最短路径

     

    所有顶点间的最短路径—用Floyd(弗洛伊德)算法

    第八章:查找

    查找表是称为集合的数据结构。是元素间约束力最差的数据结构:元素间的关系是元素仅共在同一个集合中。(同一类型的数据元素构成的集合)

    1.静态查找表

      1)顺序查找(线性查找)

      技巧:把待查关键字key存入表头或表尾(俗称“哨兵”),这样可以加快执行速度。

    int Search_Seq( SSTable  ST , KeyType  key ){

    ST.elem[0].key =key;

    for( i=ST.length; ST.elem[ i ].key!=key;  - - i  );

          return i;

    } // Search_Seq

    //ASL=(1+n)/2,时间效率为 O(n),这是查找成功的情况:

    顺序查找的特点:

    优点:算法简单,且对顺序结构或链表结构均适用。

           缺点: ASL 太大,时间效率太低。

      2)折半查找(二分查找)——只适用于有序表,且限于顺序存储结构。

      若关键字不在表中,怎样得知并及时停止查找?

      典型标志是:当查找范围的上界≤下界时停止查找。

      ASL的含义是“平均每个数据的查找时间”,而前式是n个数据查找时间的总和,所以:

     

    3)分块查找(索引顺序查找)

    思路:先让数据分块有序,即分成若干子表,要求每个子表中的数据元素值都比后一块中的数值小(但子表内部未必有序)。然后将各子表中的最大关键字构成一个索引表,表中还要包含每个子表的起始地址(即头指针)。

    特点:块间有序,块内无序。

    查找:块间折半,块内线性

    查找步骤分两步进行:

    ① 对索引表使用折半查找法(因为索引表是有序表);

    ② 确定了待查关键字所在的子表后,在子表内采用顺序查找法(因为各子表内部是无序表);

    查找效率ASL分析:

    2.动态查找表

    1)二叉排序树和平衡二叉树

    • 二叉排序树的定义----或是一棵空树;或者是具有如下性质的非空二叉树:

     (1)若它的左子树不空,则左子树上所有结点的值均小于根的值;

     (2)若它的右子树不空,则右子树的所有结点的值均大于根的值;

     (3)它的左右子树也分别为二叉排序树。

    二叉排序树又称二叉查找树。

    二叉排序树的查找过程:

    BiTree SearchBST(BiTree T, KeyType key)

    {

            //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素,

            //若查找成功,则返回指向该数据元素结点的指针,否则返回空指针

            if ((!T)||EQ(key, T->data.key))  return(T); //查找结束

            else if LT(key, T->data.key) return (SearchBST(T->lchild, key)); //在左子树中继续查找

            else return (SearchBST(T->rchild,key)); //在右子树中继续查找

    }

    • 二叉排序树的插入

            思路:查找不成功,生成一个新结点s,插入到二叉排序树中;查找成功则返回。

       SearchBST (K,  &t) { //K为待查关键字,t为根结点指针

       p=t;       //p为查找过程中进行扫描的指针

       while(p!=NULL)

    {

       case {

                   K= p->data:  {查找成功,return true;}

                   K< p->data :  {q=p;p=p->lchild }  //继续向左搜索

                   K> p->data :  {q=p;p=p->rchild } //继续向右搜索

                }

      }  //查找不成功则插入到二叉排序树中

    s =(BiTree)malloc(sizeof(BiTNode)); 

    s->data=K; s ->lchild=NULL; s ->rchild=NULL;

          //查找不成功,生成一个新结点s,插入到二叉排序树叶子处

    case {

                t=NULL:   t=s;   //若t为空,则插入的结点s作为根结点

                K < q->data: q->lchild=s;  //若K比叶子小,挂左边

                K > q->data: q->rchild=s; //若K比叶子大,挂右边

            }

    return OK;

    }

    • 二叉排序树的删除

    假设:*p表示被删结点的指针; PL和PR 分别表示*P的左、右孩子指针;

    *f表示*p的双亲结点指针;并假定*p是*f的左孩子;则可能有三种情况:

    *p有两颗子树,有两种解决方法:

    法1:令*p的左子树为 *f的左子树,*p的右子树接为*s的右子树;如下图(c)所示  //即 fL=PL  ;   SR=PR   ;

    法2:直接令*p的直接前驱(或直接后继)替代*p,然后再从二叉排序树中删去它的直接前驱(或直接后继) 。如图(d),当以直接前驱*s替代*p时,由于*s只有左子树SL,则在删去*s之后,只要令SL为*s的双亲*q的右子树即可。 // *s为*p左子树最右下方的结点

    删除算法如下:

    Status Delete(BiTree &p)

    {

        //从二叉排序树种删除结点p,并重接它的左或右子树

        if(!p->rchild) //右子树空,只需重接它的左子树

        {

            q=p;

            p=p->lchild;

            free(q);

        }

        else if(!p->lchild) //左子树空,只需重接它的右子树

        {

            q=p;

            p=p->rchild;

            free(q);

        }

        else //左右子树都不空

        {

            q=p; 

            s=p->lchild;

            while(s->rchild)  //转左,然后向右到尽头(找p的直接前驱) 图(b)

            {

                q=s;

                s=s->rchild;

            }

            p->data = s->data; //s指向被删结点的“前驱”

            if(q!=p)  //重接*q的右子树

            {

                q->rchild=s->lchild;

            }

            else  //q=p,说明s->rchild为空(即:p->lchild->rchild为空),重接*q的左子树

            {

                q->lchild=s->lchild;

            }

             delete s;

        }//end else 左右子树都不空

        return TRUE;

    }

    二叉排序树查找分析:和折半查找类似,与给定值比较的关键字个数不超过树的深度。然而,折半查找长度为n的表的判定树是惟一的,而含有n个结点的二叉排序树却不惟一。

    含有n个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树。树的深度为n,其平均查找长度为(n+1)/2(和顺序查找相同),这是最差的情况。最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和log2n成正比。

    (n>=2)

     

    • 平衡二叉树

    又称AVL树,即它或者是一颗空树,或者具有如下性质:它的左子树和右子树都是平衡二叉树,且左子树与右子树的深度之差的绝对值不超过1。

    平衡因子:该结点的左子树的深度减去它的右子树的深度。

    平衡二叉树的特点:任一结点的平衡因子只能取:-1、0 或 1。

    如果在一棵AVL树中插入一个新结点,就有可能造成失衡,此时必须重新调整树的结构,使之恢复平衡。我们称调整平衡过程为平衡旋转

    平衡旋转可以归纳为四类:单向右顺时针旋转(LL);单向左逆时针旋转(RR);双向旋转先左逆时针后右顺时针(LR);双向旋转先右顺时针后左逆时针(RL)

    平衡二叉树查找分析:

    时间复杂度为O(logn)

    3.B-树和B+树

    B+树是应文件系统所需而出的一种B树的变型树。一棵m阶的B+树和m阶的B-树的差异在于:

    1.有n棵子树的结点中含有n个关键字,每个关键字不保存数据,只用来索引,所有数据都保存在叶子节点。

    2.所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。

    3.所有的非终端结点可以看成是索引部分,结点中仅含其子树(根结点)中的最大(或最小)关键字。

    通常在B+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点。

    B-树:一棵m阶的B-树或者是一棵空树,或者是满足下列要求的m叉树:

    • 树中的每个结点至多有m棵子树;

    • 若根结点不是叶子结点,则至少有两棵子树;

    • 除根结点外,所有非终端结点至少有[ m/2 ] ( 向上取整 )棵子树。

    • 所有的非终端结点中包括如下信息的数据(n,A0,K1,A1,K2,A2,….,Kn,An)

    其中:Ki(i=1,2,…,n)为关键码,且Ki < K(i+1),

    Ai 为指向子树根结点的指针(i=0,1,…,n),且指针A(i-1) 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n),An 所指子树中所有结点的关键码均大于Kn。n 为关键码的个数。

    • 所有的叶子结点都出现在同一层次上,并且不带信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空)。

     

    4.哈希表

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表

     

    1)哈希函数构造方法

    • 直接定址法

    取关键字或关键字的某个线性函数值为散列地址。

    即 H(key) = key 或 H(key) = a*key + b,其中a和b为常数。

    • 除留余数法

    取关键字被某个不大于散列表长度 m 的数 p 求余,得到的作为散列地址。

    即 H(key) = key % p, p < m。

    • 数字分析法

    当关键字的位数大于地址的位数,对关键字的各位分布进行分析,选出分布均匀的任意几位作为散列地址。

    仅适用于所有关键字都已知的情况下,根据实际应用确定要选取的部分,尽量避免发生冲突。

    • 平方取中法

    先计算出关键字值的平方,然后取平方值中间几位作为散列地址。

    随机分布的关键字,得到的散列地址也是随机分布的。

    • 折叠法(叠加法)

    将关键字分为位数相同的几部分,然后取这几部分的叠加和(舍去进位)作为散列地址。

    用于关键字位数较多,并且关键字中每一位上数字分布大致均匀。

    • 随机数法

    选择一个随机函数,把关键字的随机函数值作为它的哈希值。

    通常当关键字的长度不等时用这种方法。

    构造哈希函数的方法很多,实际工作中要根据不同的情况选择合适的方法,总的原则是尽可能少的产生冲突

    通常考虑的因素有关键字的长度分布情况哈希值的范围等。

    如:当关键字是整数类型时就可以用除留余数法;如果关键字是小数类型,选择随机数法会比较好。

     

    2)哈希冲突的解决方法

     

    • 开放定址法

    Hi=(H(key) + di) MOD m i=1,2,…,k (k<=m)

    当冲突发生时,使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探测到开放的地址则表明表中无待查的关键字,即查找失败。

    当冲突发生时,使用某种探查(亦称探测)技术在散列表中寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到

    按照形成探查序列的方法不同,可将开放定址法区分为线性探查法、二次探查法、双重散列法等。

    a.线性探查法

    hi=(h(key)+i) % m ,0 ≤ i ≤ m-1

    基本思想是:探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+1],…,直到 T[m-1],此后又循环到 T[0],T[1],…,直到探查到 有空余地址 或者到 T[d-1]为止。

    b.二次探查法

    hi=(h(key)+i*i) % m,0 ≤ i ≤ m-1

    基本思想是:探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+1^2],T[d+2^2],T[d+3^2],…,等,直到探查到 有空余地址 或者到 T[d-1]为止。缺点是无法探查到整个散列空间。

    c.双重散列法

    hi=(h(key)+i*h1(key)) % m,0 ≤ i ≤ m-1

    基本思想是:探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+h1(d)], T[d + 2*h1(d)],…,等。

    该方法使用了两个散列函数 h(key) 和 h1(key),故也称为双散列函数探查法。

    定义 h1(key) 的方法较多,但无论采用什么方法定义,都必须使 h1(key) 的值和 m 互素,才能使发生冲突的同义词地址均匀地分布在整个表中,否则可能造成同义词地址的循环计算。

    该方法是开放定址法中最好的方法之一。

    • 链接法(拉链法)

    将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为 m,则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1] 。

    凡是散列地址为 i 的结点,均插入到以 T[i] 为头指针的单链表中。

    T 中各分量的初值均应为空指针。

    在拉链法中,装填因子 α 可以大于 1,但一般均取 α ≤ 1。

    3.哈希表的查找及其分析

    哈希表是实现关联数组(associative array)的一种数据结构,广泛应用于实现数据的快速查找。

    查找过程中,关键字的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。

    影响产生冲突多少有以下三个因素:

    1)哈希函数是否均匀;

    2)处理冲突的方法;

    3)哈希表的加载因子。

     

    第九章:内部排序

    排序:将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。

    稳定性——若两个记录A和B的关键字值相等,且排序后A、B的先后次序保持不变,则称这种排序算法是稳定的。

    1.插入排序

    思想:每步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。

    简言之,边插入边排序,保证子序列中随时都是排好序的。

    1)  直接插入排序

        在已形成的有序表中线性查找,并在适当位置插入,把原来位置上的元素向后顺移。

    时间效率: 因为在最坏情况下,所有元素的比较次数总和为(0+1+…+n-1)→O(n^2)。

    其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n^2)

    空间效率:仅占用1个缓冲单元——O(1)

    算法的稳定性:稳定

    直接插入排序算法的实现:

    void InsertSort ( SqList &L ) 

    { //对顺序表L作直接插入排序

     for ( i = 2;  i <=L.length; i++) //假定第一个记录有序

    {

         L.r[0]= L.r[i];

           j=i-1 ;                      //先将待插入的元素放入“哨兵”位置

         while(L[0] .key<L[j].key)

        {  

            L.r[j+1]= L.r[j];

            j--  ;                    

        }      //只要子表元素比哨兵大就不断后移

        L.r[j+1]= L.r[0];      //直到子表元素小于哨兵,将哨兵值送入

                                     //当前要插入的位置(包括插入到表首)

    }

    }

    2)折半插入排序

    子表有序且为顺序存储结构,则插入时采用折半查找定可加速。

    优点:比较次数大大减少,全部元素比较次数仅为O(nlog2n)。

    时间效率:虽然比较次数大大减少,可惜移动次数并未减少, 所以排序效率仍为O(n^2) 。

    空间效率:仍为 O(1)

    稳 定  性: 稳定

     

    3)希尔排序—不稳定

    基本思想:先将整个待排记录序列分割成若干子序列,分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。

    优点:让关键字值小的元素能很快前移,且序列若基本有序时,再用直接插入排序处理,时间效率会高很多。

    时间效率:当n在某个特定范围内,希尔排序所需的比较和移动次数约为n^1.3,当n->无穷,可减少到n(log2n)^2

    空间效率:O(1)

    4)快速排序

    基本思想:从待排序列中任取一个元素 (例如取第一个) 作为中心,所有比它小的元素一律前放,所有比它大的元素一律后放,形成左右两个子表;然后再对各子表重新选择中心元素并依此规则调整,直到每个子表的元素只剩一个。此时便为有序序列了。

    优点:因为每趟可以确定不止一个元素的位置,而且呈指数增加,所以特别快!

    前提:顺序存储结构

    时间效率:O(nlog2n) —因为每趟确定的元素呈指数增加

    空间效率:O(log2n)—因为递归要用栈(存每层low,high和pivot)

    稳 定 性: 不 稳 定 — —因为有跳跃式交换。

    算法:

    int partition(SqList &L,int low,int high)

    {

      L.r[0] = L.r[low];

      pivot key = L.r[low].key;

        while(low < high)

        {

         while(low<high&&L.r[high]>=pivot) high--;

         L.r[low] = L.r[high];

         while(low<high&&L.r[low]<=pivot) low++;

         L.r[high] = L.r[low];

        }

        L.r[low] = pivot;

        return low;

    }

     

    5)冒泡排序

    基本思路:每趟不断将记录两两比较,并按“前小后大”(或“前大后小”)规则交换。

    优点:每趟结束时,不仅能挤出一个最大值到最后面位置,还能同时部分理顺其他元素;一旦下趟没有交换发生,还可以提前结束排序。

    前提:顺序存储结构

    冒泡排序的算法分析:

    时间效率:O(n^2) —因为要考虑最坏情况

    空间效率:O(1) —只在交换时用到一个缓冲单元

    稳 定 性: 稳定  —25和25*在排序前后的次序未改变

    冒泡排序的优点:每一趟整理元素时,不仅可以完全确定一个元素的位置(挤出一个泡到表尾),还可以对前面的元素作一些整理,所以比一般的排序要快。

    选择排序:选择排序的基本思想是:每一趟在后面n-i 个待排记录中选取关键字最小的记录作为有序序列中的第i  个记录。

    6)简单选择排序

    思路异常简单:每经过一趟比较就找出一个最小值,与待排序列最前面的位置互换即可。

    ——首先,在n个记录中选择最小者放到r[1]位置;然后,从剩余的n-1个记录中选择最小者放到r[2]位置;…如此进行下去,直到全部有序为止。

    优点:实现简单

    缺点:每趟只能确定一个元素,表长为n时需要n-1趟

    前提:顺序存储结构

    时间效率:O(n^2)——虽移动次数较少,但比较次数较多

    空间效率:O(1)

    算法稳定性——不稳定

    Void SelectSort(SqList  &L ) 

    {

    for (i=1;  i<L.length; ++i)

    {

         j = SelectMinKey(L,i);  //在L.r[i..L.length]中选择key最小的记录

         if( i!=j )   r[i] <--> r[j]; //与第i个记录交换

          } //for

      }  //SelectSort

     

    7)堆排序

    设有n个元素的序列 k1,k2,…,kn,当且仅当满足下述关系之一时,称之为堆。

    如果让满足以上条件的元素序列 (k1,k2,…,kn)顺次排成一棵完全二叉树,则此树的特点是:树中所有结点的值均大于(或小于)其左右孩子,此树的根结点(即堆顶)必最大(或最小)。

    堆排序算法分析:

    时间效率:O(nlog2n)。因为整个排序过程中需要调用n-1次HeapAdjust( )算法,而算法本身耗时为log2n;

    空间效率:O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。

    稳定性: 不稳定。

    优点:对小文件效果不明显,但对大文件有效。

     

    8)归并排序----稳定

    将两个或两个以上有序表组合成一个新的有序表。

    时间复杂度:O(nlogn)

    空间复杂度:和待排记录等数量的辅助空间。

     

    9)基数排序

    时间复杂度:对于n各记录(每个记录含d个关键字,每个关键字取值范围为rd个值)进行链式基数排序的时间复杂度为O(d(n+rd)),其中每一趟分配的时间复杂度为O(n),每一趟收集的时间复杂度为O(rd)

    10)各种内部排序方法的比较讨论

    (1) 从平均时间性能看,快速排序最佳,其所需时间最省,但快速排序的最坏情况下的时间性能不如堆排序和快速排序。后两者相比较,在n较大时,归并排序所需时间较堆排序省,但它所需的辅助存储量最多。

    (2)基数排序的时间复杂度可写成O(dn)。因此,它最适用于n值很大而关键字较小的序列。

    (3)从方法的稳定性来比较,基数排序是稳定的内排方法,所需时间复杂度为O(n^2)的简单排序方法也是稳定的,然而,快速排序、堆排序和希尔排序等时间性能较好的排序方法是不稳定的。

    展开全文
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    数据结构分类 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都...

    本文目录:

    数据结构分类

    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。
    常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示:
    这里写图片描述
    每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。

    1、数组

    数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

    int[] data = new int[100];data[0]  = 1;
    

    优点:
    1、按照索引查询元素速度快
    2、按照索引遍历数组方便

    缺点:
    1、数组的大小固定后就无法扩容了
    2、数组只能存储一种类型的数据
    3、添加,删除的操作慢,因为要移动其他的元素。

    适用场景:
    频繁查询,对存储空间要求不大,很少增加和删除的情况。

    2、栈

    栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。
    这里写图片描述
    栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。

    3、队列

    队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队,示例图如下:
    这里写图片描述
    使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

    4、链表

    链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。
    这里写图片描述
    链表的优点:
    链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;
    添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

    缺点:
    因为含有大量的指针域,占用空间较大;
    查找元素需要遍历链表来查找,非常耗时。

    适用场景:
    数据量较小,需要频繁增加,删除操作的场景

    5、树

    是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

    • 每个节点有零个或多个子节点;
    • 没有父节点的节点称为根节点;
    • 每一个非根节点有且只有一个父节点;
    • 除了根节点外,每个子节点可以分为多个不相交的子树;

    在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树
    这里写图片描述
    二叉树是树的特殊一种,具有如下特点:

    1、每个结点最多有两颗子树,结点的度最大为2。
    2、左子树和右子树是有顺序的,次序不能颠倒。
    3、即使某结点只有一个子树,也要区分左右子树。

    二叉树是一种比较有用的折中方案,它添加,删除元素都很快,并且在查找方面也有很多的算法优化,所以,二叉树既有链表的好处,也有数组的好处,是两者的优化方案,在处理大批量的动态数据方面非常有用。

    扩展:
    二叉树有很多扩展的数据结构,包括平衡二叉树、红黑树、B+树等,这些数据结构二叉树的基础上衍生了很多的功能,在实际应用中广泛用到,例如mysql的数据库索引结构用的就是B+树,还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大,但算法上比较复杂,想学习的话还是需要花时间去深入的。

    6、散列表

    散列表,也叫哈希表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。

    记录的存储位置=f(key)

    这里的对应关系 f 成为散列函数,又称为哈希 (hash函数),而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,这种存储空间可以充分利用数组的查找优势来查找元素,所以查找的速度很快。

    哈希表在应用中也是比较常见的,就如Java中有些集合类就是借鉴了哈希原理构造的,例如HashMap,HashTable等,利用hash表的优势,对于集合的查找元素时非常方便的,然而,因为哈希表是基于数组衍生的数据结构,在添加删除元素方面是比较慢的,所以很多时候需要用到一种数组链表来做,也就是拉链法。拉链法是数组结合链表的一种结构,较早前的hashMap底层的存储就是采用这种结构,直到jdk1.8之后才换成了数组加红黑树的结构,其示例图如下:
    这里写图片描述
    从图中可以看出,左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

    哈希表的应用场景很多,当然也有很多问题要考虑,比如哈希冲突的问题,如果处理的不好会浪费大量的时间,导致应用崩溃。

    7、堆

    堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:

    • 堆中某个节点的值总是不大于或不小于其父节点的值;

    • 堆总是一棵完全二叉树。

    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

    堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
    (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2),满足前者的表达式的成为小顶堆,满足后者表达式的为大顶堆,这两者的结构图可以用完全二叉树排列出来,示例图如下:
    这里写图片描述
    因为堆有序的特点,一般用来做数组中的排序,称为堆排序。

    8、图

    图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

    按照顶点指向的方向可分为无向图和有向图:
    这里写图片描述
    这里写图片描述
    图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构,这里不做展开,读者有兴趣可以自己学习深入。

    展开全文
  • Java数据结构和算法(一)——开篇

    万次阅读 多人点赞 2019-09-18 12:31:42
    看的是——《Java数据结构和算法》一书,作者Robert Lafore。 目录 1)数据结构算法有什么用? 2)技术与通俗 3)驱动力学习 1)数据结构算法有什么用? 当你用着java里面的容器类很爽的时候,你有没有想过,怎么...

    这篇文章里面不讲技术,抽空讲讲技术和通俗之间有一种奇特的关系,还有驱动力学习的东西。看的是——《Java数据结构和算法》一书,作者Robert Lafore。

    目录

    1)数据结构算法有什么用?

    2)技术与通俗

    3)驱动力学习


    1)数据结构算法有什么用?

    当你用着java里面的容器类很爽的时候,你有没有想过,怎么ArrayList就像一个无限扩充的数组,也好像链表之类的。好用吗?好用,这就是数据结构的用处,只不过你在不知不觉中使用了。

     

    校招会发现大公司考的就是这类的题目,刚开始不会考你java的线程,容器,多态什么的特性,考的就是你的基础,你的这些基础扎实,学其他不是问题。

     

    正如作者所说,用于现实世界的存储,我们使用的工具和建模。每种数据结构有自己的优点和缺点,想想如果Google的数据用的是数组的存储,我们还能方便地查询到所需要的数据吗。

    而算法,在这么多的数据中如何做到最快的插入,查找,删除,也是在追求更快。

     

    第一章也把数据库,面向对象,软件工程(原来整个软件工程项目的生命周期包括分析、设计、验证编码、测试、生产和维护几个阶段)讲了个大概

     

     

     

    2)技术与通俗

    大学里面那本严蔚敏的数据结构不厚,内容丰富,但是复杂问题的讲解方面篇幅这样就少了,比较难理解,c也不是很擅长,但是基本的思路还是有的。

    简单的链表,数组,堆栈,队列,图,几个排序算法。

     

    后面看到知乎涛吴的回答,当时很震撼,这里引用一下他的回答:

     

    如果说 Java 是自动档轿车,C 就是手动档吉普。数据结构呢?是变速箱的工作原理。你完全可以不知道变速箱怎样工作,就把自动档的车子从 A 开到 B,而且未必就比懂得的人慢。写程序这件事,和开车一样,经验可以起到很大作用,但如果你不知道底层是怎么工作的,就永远只能开车,既不会修车,也不能造车。如果你对这两件事都不感兴趣也就罢了,数据结构懂得用就好。但若你此生在编程领域还有点更高的追求,数据结构是绕不开的课题。

    Java 替你做了太多事情,那么多动不动还支持范型的容器类,加上垃圾收集,会让你觉得编程很容易。但你有没有想过,那些容器类是怎么来的,以及它存在的意义是什么?最粗浅的,比如 ArrayList 这个类,你想过它的存在是多么大的福利吗——一个可以随机访问、自动增加容量的数组,这种东西 C 是没有的,要自己实现。但是,具体怎么实现呢?如果你对这种问题感兴趣,那数据结构是一定要看的。甚至,面向对象编程范式本身,就是个数据结构问题:怎么才能把数据和操作数据的方法封装到一起,来造出 class / prototype 这种东西?

    此外,很重要的一点是,数据结构也是通向各种实用算法的基石,所以学习数据结构都是提升内力的事情。

     

    反正我有醍醐灌顶的感觉,好比说,我有在编程上更厉害的追求,怎么能死在数据结构上的感觉。

     

    其实要将一门难懂的技术通俗地讲给不懂的人听,需要很大的功力,包括之前我写的那篇《C与指针》刚开始的时候,那个C语言有什么用回答也是他写的,我很佩服这样的人。

     

    所以当你能把一件东西清楚的讲解给别人听,类似前几篇文章提到的橡皮鸭调试法一样,你搞懂了,摸清楚了。跟一个技术人士用技术的语言讲解,非专业人士通俗语言讲解。

     

    当然了,前提需要积累。具体可以参见一下CSDN里面关于罗升阳的访谈——

    专访罗升阳:老罗的Android之旅

    当时吓了我一跳,之前以为和那个老罗同个级别的年龄,后面发现好年轻的小伙子,积累,慢慢积累。

     

     

    3)驱动力学习

    当你看到你自己玩过的马里奥可以自己写出来的时候是不是心动了?顿时学习的驱动力是不是有了——我要做一个这样的东西出来,然后开始学,直到自己动手完成。

     

    当时我在大学里就在推算,按照我这个学习速度,10年之后那也可以牛逼哄哄啊。有些人为什么技术没有提升,几年之后还是那样,因为驱动力的东西,有段时间我曾经停下来过,Java的差不多都学完了,干什么?

     

    因为从J2SE到EE的东西,大体的看完做过,然后就有一段迷茫期了,驱动力也没有了。后面意识到自己太肤浅了,还有其他一些热门的框架没用,最好的单例你写出来了吗,虚拟机你深入了吗,Java还有很多经典书籍没看呢?

    以学习新知识为驱动力也是可以的,期间不停地学到新知识是很有成就感和很兴奋的东西——原来是这样xx。

     

    还有一种——目标驱动,当时要做一个网络相关的东西——想到了爬虫,然后以做出这东西为目的,收集资料,看别人的代码,这样的驱动力学习也是可以的。工作的时候,如果目标只放在工作的项目,每次的项目都有新的东西在里面,那是可以学到东西的,一成不变的话,只能自己去发掘了。

    不然哪有那个学习到半夜的——专访雷果国:从1.5K到18K 一个程序员的5年成长之路。

     

    我要学Python,学了之后会发现,原来真的很牛逼,可以尝试用Python写个爬虫,GoAgent之类的。这便是进步。

     

     

    扯了那么多,就是不希望自己只懂的用Java做xx系统,只懂得用容器而永远不知道里面是怎样的。这些作为根基的懂了,其他也好学。

     

    说回数据结构这个,为什么很多学生听课听得想睡,xx链表,双向链表,我排序都有N种,学生的想法是这不知道有什么用,你讲链表给我,我把它实现一次,完事。

     

    但当你生活中的编程问题需要解决的时候,你会发现到处都是数据结构的使用,像基金买入买出不是队列吗,先进先出;像简单的一个班级学生的数据保存,用个数组不就可以解决了吗;再复杂的游戏路线问题,这不是图的问题吗;Java里面有Tree这字的,其实不也是用到树的原理吗?

     

    种种下来,你会发现,原来现实问题和语言里面的封装,都是和这些有联系的,每当你学会一种,就会恍然大悟,这不就是当年西湖河畔的夏雨荷,就是这种感觉。而学生在没有想过这些问题和没真正去使用这些语言的封装类之前,是不会考虑到上面所说的东西的。

     

    所以,一大群学生趴在那里睡觉玩手机是正常的。

     

    后面自己意识到之后,马上去买了《Java数据结构和算法》,补回之前没学和没弄懂的。

     

    不想学好基础的程序员不是好的程序员。

    展开全文
  • 数据结构: 一、数据结构概述

    千次阅读 多人点赞 2018-04-07 15:11:40
    目前,对数据结构的定义还没有得到真正的统一认同,我就先引用书本里的内容了:数据结构是相互之间存在的一种或多种特定关系的集合。可以说数据结构就是带着“结构”的数据元素的集合,这个“结构”就是数据元素之间...
  • #include #include #define ok 1 #define error 0 #define overflow -1 #define LIST_INIT_SIZE typedef int ElemType; typedef int Status; typedef struct LNode{ ElemType data; struct LNode *next;...
  • 数据结构基础概念篇

    万次阅读 多人点赞 2017-11-14 13:44:24
    数据结构一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据:所有能被输入到计算机中,且能...
  • 数据结构

    千次阅读 2018-11-15 19:33:22
     数据结构主要研究非数值性程序设计中所出现的计算机操作对象以及他们之间的关系和运算等  术语   数据(Data):信息 对在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称;  例如 在结...
  • 结构数据和非结构数据、半结构数据的区别

    万次阅读 多人点赞 2019-06-15 22:27:41
    计算机信息化系统中的数据分为结构数据和非结构数据、半结构数据结构数据 结构数据,是指由二维表结构来逻辑表达和实现的数据,严格地遵循数据格式与长度规范,主要通过关系型数据库进行存储和管理...
  • 结构数据、半结构数据和非结构数据

    万次阅读 多人点赞 2020-08-20 19:04:49
    结构化数据、半结构化数据和非结构化数据结构数据结构化的数据是指可以使用关系型数据库表示和存储,表现为二维形式的数据。一般特点是:数据以行为单位,一行数据表示一个实体的信息,每一行数据的属性是相同的。...
  • 数据结构和算法视频教程

    万人学习 2019-06-25 10:51:39
    数据结构、算法视频培训课程,该教程主要是介绍在游戏开发中经常使用的数据结构,例如数组,链表,栈,队列,二叉树,递归等重要知识点讲解以及将它们里灵活的运用到算法里面。
  • 数据结构与算法(java版)

    万次阅读 多人点赞 2018-04-22 17:18:08
    数据结构与算法(java版)标签: java 数据结构 算法2017年12月28日 21:50:08102人阅读 评论(0) ...(1)数据结构与算法概念解析 (2)数据结构之数组 (3)数据结构之栈 (4)数据结构之队列 (5)数据结...
  • 关于结构化、半结构化、非结构数据的理解

    万次阅读 多人点赞 2018-08-06 11:36:03
    记得在课上,老师说,结构数据就是我们关系数据库里的表,剩下的都是半结构化和非结构数据,好比XML文档就是半结构数据,WORD文档就是非结构数据,大数据就是半结构化和非结构数据。心中一直有一个疑问?...
  • 数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第1部分,介绍...
  • 以下数据结构中,()是非线性数据结构A:树(二叉树) B:字符串 C:队列 D:栈 E:线性表 F:二维数组 G:多维数组数据的逻辑结构分为线性结构和非线性结构。 常用的线性结构有:线性表,栈,队列,双队列,...
  • eMule资源 下面是用户共享的文件列表,安装eMule后,您可以点击这些文件名进行下载 数据结构(清华严蔚敏)_数据结构01.asf 详情 55.4MB 数据结构(清华严
  • 数据结构教程(第5版)李春葆 课后习题及答案(PDF版) 链接: https://pan.baidu.com/s/1IYmbv16hiZJVwR5EJY-mcQ 提取码: 6uwa   数据结构听不懂的同学看一下严蔚敏的数据结构:(经典中的经典) 链接: ...
  • 本书下载链接: https://download.csdn.net/download/u010752028/10575288
  • 写在前面: 恰逢期末复习,用了几天时间结合老师勾画的重点以及课件教材等,将全书重要内容做了个大整合。一方面便于自己复习记忆,另一方面po出来让更多需要的人也可以做个参考... 《数据结构》C语言版 (清华严...
  • 书本下载链接:链接:https://pan.baidu.com/s/1jgVnbBZoLgA8pshpxbapOQ 密码...虽说数据结构以美国人Mark Allen Weiss 写的《数据结构与算法分析——C语言实现》最好,但是我发现他的书让人很不容易理解,可能我们...
1 2 3 4 5 ... 20
收藏数 3,757,308
精华内容 1,502,923
关键字:

数据结构