数据结构_数据包结构 - 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+人生感悟+理财知识+互联网事件等)

    展开全文
  • 看的是——《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数据结构和算法》,补回之前没学和没弄懂的。

     

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

    展开全文
  • 数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第6部分“树和...
  • 数据结构、算法视频培训课程,该教程主要是介绍在游戏开发中经常使用的数据结构,例如数组,链表,栈,队列,二叉树,递归等重要知识点讲解以及将它们里灵活的运用到算法里面。
  • 目前,对数据结构的定义还没有得到真正的统一认同,我就先引用书本里的内容了:数据结构是相互之间存在的一种或多种特定关系的集合。可以说数据结构就是带着“结构”的数据元素的集合,这个“结构”就是数据元素之间...

        目前,对数据结构的定义还没有得到真正的统一认同,我就先引用书本里的内容了:数据结构是相互之间存在的一种或多种特定关系的集合。可以说数据结构就是带着“结构”的数据元素的集合,这个“结构”就是数据元素之间的关系。

        数据结构包括存储结构和逻辑结构两个层次。


    (图片转载于https://blog.csdn.net/balingybj/article/details/48293929)

        1、存储结构(也称:物理结构)

        数据对象在计算机中的存储表示就称为数据的存储结构。基本的存储结构主要分为顺序存储结构和链式存储结构两种。

        (1)、顺序存储结构

        顺序存储结构是借元素在存储器中的相对位置来表示数据元素之间的逻辑关系;在顺序存储结构中,逻辑相邻的两个元素之间在地址存储中也是相邻的。如下表,每个结点(学生记录)占用25个存储单元。数据便从0号单元从低地址向高地址方向存储,要求所有的元素一次存放在一片连续的存储空间中。通常借用程序设计语言的数组类型来描述。
    顺序存储结构
    地址学号姓名性别
    0060122201杨阳
    25060122202薛林
    50060122203王诗萌
        (2)、链式存储结构
        链式存储结构不需要占用一整块存储空间,但需要给每个结点附加指针字段存放后继元素的存储地址用以表示结点之间的关系,所以常借助于程序设计语言中的指针类型来描述。
    链式存储结构
    地址学号姓名性别指针(存后继结点首地址)
    0060122201杨阳25
        如此,每个相邻结点的存储地址便不必相邻,不过每个结点都需要多声明一个指针项。

        除了这两种主要的存储结构,还有索引存储和散列存储,不过课堂和书本上都没细讲,我也只在网上查了一点资料:
        (3)、索引存储:除了建立存储结点信息外,还建立附加的索引表来标识结点的地址。索引表由若干个索引项组成

        (4)、散列存储:散列存储,又称hash存储,是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。散列法存储的基本思想是:由结点的关键码值决定结点的存储地址。散列技术除了可以用于查找外,还可以用于存储。

    存储结构在这儿就讲一段落了,接下来开始总结一下逻辑结构

        1、逻辑结构

        数据的逻辑结构是在逻辑关系上描述问题,与数据的存储无关。数据的逻辑结构包括两个要素:数据元素和关系。其中关系指数据元素之间的逻辑关系。根据数据元素之间关系的不同特性,通常有四种基本结构。如下图


        集合结构除了集合关系外,任意结点之间无其他关系;

        线性结构数据元素间存在一对一的关系;

        树结构中数据元素间存在一对多的关系;

        图结构(网状结构)中数据元素间存在多对多的关系。

    其中集合结构、树结构、图结构都属于非线性结构

    (想搞清线性结构和非线性结构的同学请转到https://blog.csdn.net/balingybj/article/details/48293929)

    其中线性结构包括线性表、栈和队列、字符串、数组和广义表;非线性结构包括树和二叉树、有向图和无向图。


        数据结构的存储结构和逻辑结构的总体概述便先这样吧,后面会再详细讲各个知识点。

    展开全文
  • 排序就是将一个数据元素(或记录)的任意序列,通过一定的方法重新排列成一个按关键字有序的序列的过程。 2.排序的稳定性 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对...

    1.什么是排序

    排序就是将一个数据元素(或记录)的任意序列,通过一定的方法重新排列成一个按关键字有序的序列的过程。

    2.排序的稳定性

    假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。

    稳定的排序的优点是,从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。

    例如,假设一个班的学生已经按照学号大小排好序了,我现在要求按照年龄从小到大再排个序,如果年龄相同的,必须按照学号从小到大的顺序排列。
    那么问题来了,你选择的年龄排序方法如果是不稳定的,是不是排序完了后年龄相同的一组学生学号就乱了,你就得把这组年龄相同的学生再按照学号拍一遍。如果是稳定的排序算法,我就只需要按照年龄排一遍就好了。

    3.内部排序和外部排序

    根据在排序过程中待排序的记录是否全部被放置在内存中,排序分为内部排序和外部排序。

    • 内部排序:在整个排序过程中,待排序的所有记录全部被放置在内存中。

    • 外部排序:由于排序的记录个数太多,不能同时放置在内存中,整个排序过程需要在内外存之间多次交换数据才能进行。

    4.内部排序方法

    根据排序过程中借助的主要操作,我们把内部排序分为:插入排序、交换排序、分配排序、选择排序和归并排序等。

    4.1.插入排序

    插入排序的基本方法是:每步将一个待排序的记录按照其排序码的大小,插入到前面已经排序的文件中的适当位置,直到全部插入完为止。插入排序算法主要包括直接插入排序、二分插入排序、表插入排序和希尔排序等。

    4.1.1.直接插入排序

    直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。

    具体算法描述如下:

    1. 从第一个元素开始,该元素可以认为已经被排序

    2. 取出下一个元素,在已经排序的元素序列中从后向前扫描

    3. 如果该元素(已排序)大于新元素,将该元素移到下一位置

    4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

    5. 将新元素插入到该位置后

    6. 重复步骤2~5

    #include<stdio.h>
    #define MAXNUM 100
    typedef int KeyType;
    typedef int DataType;
    typedef struct {
        KeyType key;       /* 排序码字段 */
        /*DataType info;           记录的其它字段 */
    } RecordNode;
    typedef struct {
        int n;               /* n为文件中的记录个数,n<MAXNUM */
        RecordNode record[MAXNUM];
    } SortObject;
    void insertSort(SortObject * pvector) { /* 按递增序进行直接插入排序 */
        int i, j;
        RecordNode temp;
        RecordNode *data = pvector->record;
        for( i = 1; i < pvector->n; i++ ) { /* 依次插入记录R1, R2…Rn-1 */
            temp = data[i]; 
            for ( j = i-1; temp.key < data[j].key && j >= 0; j-- )
                /* 由后向前找插入位置 将排序码大于ki的记录后移 */
                data[j+1] = data[j];
            if( j != i-1 ) data[j+1] = temp;
        }
    }
    SortObject vector = {10, 
        49, 38, 65, 97, 76, 13, 27, 49, 50, 101};
    int main(){
        int i;
        insertSort(&vector);
        for(i = 0; i < vector.n; i++)
            printf("%d ", vector.record[i]);
        getchar();
        return 0;
    }

    4.1.2.二分插入排序

    直接插入排序的算法简洁,容易实现,n较小时是一种很好的排序算法。但是,因为如果文件中记录的数量很大,则此时直接插入排序方法不太适用。在直接插入排序的基础上,为了减少比较的次数,可以在插入第i个元素时改用二分比较法查找插入位置,便得到了二分插入排序。

    所谓的二分比较法是在插入第i+1个元素时(前i个元素已排序),取第i/2位置的排序码与要插入的元素比较,如果要插入的元素小于第i/2位置的排序码,则在第1到第i/2位置之间使用二分法,反之则在第i/2+1到第i位置之间使用二分法,直到确定插入位置为止。这种方法经过一次比较,便可排除一半记录,故称为二分法。

    #include<stdio.h>
    #define MAXNUM 100
    typedef int KeyType;
    typedef int DataType;
    typedef struct {
        KeyType key;       /* 排序码字段 */
        /*DataType info;   记录的其它字段 */
    } RecordNode;
    typedef struct {
        int n;               /* n为文件中的记录个数,n<MAXNUM */
        RecordNode record[MAXNUM];
    } SortObject;
    void binSort(SortObject * pvector) {      /* 按递增序进行二分法插入排序 */
        int i, j, left, mid, right;
        RecordNode temp;
        RecordNode *data = pvector->record;
        
        for( i = 1; i < pvector->n; i++ ) {
            temp = data[i];
            left = 0;  right = i-1;           /* 置已排序区间的下、上界初值 */
            while (left <= right) {
                mid = (left + right)/2;       /* mid指向已排序区间的中间位置 */
                if (temp.key < data[mid].key)
                    right = mid-1;            /* 插入元素应在左子区间 */
                else left = mid+1;            /* 插入元素应在右子区间 */
            }
            for (j = i-1;  j >= left;  j--)
                data[j+1] = data[j];          /* 将排序码大于ki的记录后移 */
            if (left != i) data[left] = temp;
        }
    }
    SortObject vector={10, 49,38,65,97,76,13,27,49,50,101};
    int main(){
        int i;
        binSort(&vector);
        for(i = 0; i < vector.n; i++)
            printf("%d ", vector.record[i]);
        getchar();
        return 0;
    }

    4.1.3.表插入排序

    表插入排序的目标是在直接插入排序的基础上减少记录移动的次数,其基本的思想是在每个记录中增加一个指针字段,指向下一个记录。整个被排序的文件表示成一个记录的单链表。插入记录i时,记录0到i-1已经排序了,为了确定插入的位置,可以先将记录i脱链,再采用顺序比较的方法找到i应当插入的位置,像单链表插入那样,将i插入链表。

    #include<stdio.h>
    struct Node;                    /* 单链表结点类型 */
    typedef int KeyType;
    typedef int DataType;
    typedef struct Node ListNode;
    struct Node {
        KeyType key;            /* 排序码字段 */
        /*DataType info;                记录的其它字段 */
        ListNode *next;              /* 记录的指针字段 */
    };
    typedef ListNode * LinkList;
    /* 对链表按递增序进行表插入排序,链表中第一个结点为表头结点。 */
    void listSort(LinkList * plist) {
        ListNode *now, *pre, *p, *q, *head; head=*plist;
        if (head->next == NULL || head->next->next == NULL)
            return;  /* 为空链表或链表中只有一个结点 */
        pre = head->next; now = pre->next;
        while (now != NULL) {
            q = head; p = head->next;
            while(p != now && p->key <= now->key) {
                q = p;  p = p->next;
            } /* 本循环结束时,已经找到了now的插入位置 */
            if (p == now) {                        /* now应放在原位置 */
                pre = pre->next; now = pre->next; continue;
            }
            /* 使now记录脱链,将now记录插入链表中 */
            pre->next = now->next; q->next = now;
            now->next = p; now = pre->next;
        }
    }
    ListNode element[9]={
        0, &element[1],
        49, &element[2],
        38, &element[3],
        65, &element[4],
        97, &element[5],
        76, &element[6],
        13, &element[7],
        27, &element[8],
        49, NULL
    };
    int main(){
        LinkList p = element;
        listSort(&p);
        p = p->next;
        while (p != NULL){
            printf("%d ",p->key);
            p = p->next;
        }
        getchar();
        return 0;
    }

    4.1.4.希尔排序

    希尔排序的方法又称缩小增量法,是对直接插入排序法的改进。它的做法是:先取一个整数d1<n,把全部记录分成d1个组,所有距离为d1倍数的记录放在一个组中,先在各组内排序;然后取d2<d1,重复上述分组和排序工作;直到di=1,即所有的记录放在一个组中为止。各组内的排序可以采用直接插入排序或其他排序。

    #include<stdio.h>
    #define MAXNUM 100
    typedef int KeyType;
    typedef int DataType;
    typedef struct {
        KeyType key;       /* 排序码字段 */
        /*DataType info;           记录的其它字段 */
    } RecordNode;
    typedef struct {
        int n;               /* n为文件中的记录个数,n<MAXNUM */
        RecordNode record[MAXNUM];
    } SortObject;
    void  shellSort(SortObject * pvector, int d) {    /* 按递增序进行Shell排序 */
        int i, j, inc; 
        RecordNode temp, *data = pvector->record;
        
        for (inc = d; inc > 0; inc /= 2) {
            /* inc 为本趟shell排序增量 */
            for (i = inc; i < pvector->n; i++) { 
                temp = data[i];              /* 保存待插入记录Ri*/ 
                for (j = i-inc; j >= 0 && temp.key < data[j].key; j -= inc)
                    data[j+inc] = data[j];    /* 查找插入位置,记录后移 */
                data[j+inc] = temp;            /* 插入记录Ri */
            }
        }
    }
    SortObject vector={8,49,38,65,97,76,13,27,49};
    int main(){
        int i;
        shellSort(&vector,4);
        for(i=0;i<8;i++)
            printf("%d ",vector.record[i]);
        getchar();
        return 0;
    }

    4.2.交换排序

    交换排序的基本方法是:两两比较待排序记录的排序码,交换不满足顺序要求的偶对,直到全部满足为止。

    交换排序主要包含冒泡排序和快速排序算法

    4.2.1.冒泡排序

    冒泡排序的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

    #include<stdio.h>
    #define MAXNUM 100
    #define TRUE 1
    #define FALSE 0
    typedef int KeyType;
    typedef int DataType;
    typedef struct {
        KeyType key;       /* 排序码字段 */
        /*DataType info;           记录的其它字段 */
    } RecordNode;
    typedef struct {
        int n;               /* n为文件中的记录个数,n<MAXNUM */
        RecordNode record[MAXNUM];
    } SortObject;
    void  bubbleSort(SortObject * pvector) {
        int i, j, noswap; 
        RecordNode temp, *data = pvector->record;
        for(i = 0; i < pvector->n-1; i++) {         /* 做n-1次起泡 */
            noswap = TRUE;                          /* 置交换标志 */
            for (j = 0; j < pvector->n-i-1; j++)    /* 从前向后扫描 */
                if (data[j+1].key < data[j].key) {  /* 交换记录 */
                    temp = data[j]; 
                    data[j] = data[j+1];
                    data[j+1] = temp;
                    noswap = FALSE;
                }
            if ( noswap ) break;    /* 本趟起泡未发生记录交换,算法结束 */
        }
    }
    SortObject vector={8, 49,38,65,97,76,13,27,49};
    int main(){
        int i;
        bubbleSort(&vector);
        for(i = 0; i < 8; i++)
            printf("%d ", vector.record[i]);
        getchar();
        return 0;
    }

    4.2.2.快速排序

    快速排序是一种十分重要的排序算法,它的基本思想是:通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

    #include<stdio.h>
    #define MAXNUM 100
    #define TRUE 1
    #define FALSE 0
    typedef int KeyType;
    typedef int DataType;
    typedef struct {
        KeyType key;         /* 排序码字段 */
        /*DataType info;        记录的其它字段 */
    } RecordNode;
    typedef struct {
        int n;               /* n为文件中的记录个数,n<MAXNUM */
        RecordNode record[MAXNUM];
    } SortObject;
    void quickSort(SortObject * pvector, int l, int r) {
        int i, j;
        RecordNode temp, *data = pvector->record;
        
        if (l >= r) return;   /* 只有一个记录或无记录,则无须排序 */
        i = l;  j = r;  temp = data[i];
        while (i != j) {        /* 寻找Rl的最终位置 */
            while( data[j].key >= temp.key && j > i )
                j--;         /* 从右向左扫描,查找第1个排序码小于temp.key的记录 */
            if (i < j) data[i++] = data[j];   
            while( data[i].key <= temp.key && j > i )
                i++;         /* 从左向右扫描,查找第1个排序码大于temp.key的记录 */
            if (i < j) data[j--] = data[i];
        }
        data[i] = temp;                 /* 找到Rl的最终位置 */
        quickSort(pvector, l, i-1);                 /* 递归处理左区间 */
        quickSort(pvector, i+1, r);            /* 递归处理右区间 */
    }
    SortObject vector = {8, 49,38,65,97,76,13,27,49};
    int main(){
        int i;
        quickSort(&vector, 0, 7);
        for(i = 0; i < 8; i++)
            printf("%d ", vector.record[i]);
        getchar();
        return 0;
    }

    4.3.分配排序

    分配排序的思想是把排序码分解成若干部分,然后通过对各个部分排序码的分别排序,最终达到整个排序码的排序。

    4.3.1.基数排序

    基数排序(英语:Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。

    它是这样实现的:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。

    这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

    #include<stdio.h>
    #define D 3                       /* D为排序码的最大位数 */
    #define R 10                      /* R为基数 */
    typedef int KeyType;
    typedef int DataType;
    struct Node;                      /* 单链表结点类型 */
    typedef struct Node RadixNode;
    struct Node {
        KeyType key[D]; 
        /* DataType info;*/
        RadixNode *next;
    };
    typedef RadixNode * RadixList;
    typedef struct QueueNode {
        RadixNode *f;                  /* 队列的头指针 */
        RadixNode *e;                  /* 队列的尾指针 */
    } Queue;
    Queue queue[R];
    void radixSort(RadixList * plist, int d, int r) {
        int i,j,k; 
        RadixNode *p, *head = (*plist)->next;
        for(j = d-1; j >= 0; j--) {         /* 进行d次分配和收集*/
            p = head;
            for(i = 0; i < r; i++) { 
                queue[i].f = NULL;  queue[i].e = NULL; /* 清队列 */
            }
            while (p != NULL) {
                k = p->key[j];              /* 按排序码的第j个分量进行分配*/
                if (queue[k].f == NULL) 
                    queue[k].f = p;         /* 若第k个队列为空,则当前记录为队头*/ 
                else (queue[k].e)->next = p;/* 否则当前记录链接到第k队的队尾*/
                queue[k].e = p;
                p = p->next;
            }
            for(i = 0; queue[i].f == NULL; i++) /* 找出第一个非空队列*/
                ;
            p = queue[i].e;  head = queue[i].f; /* head为收集链表的头指针*/
            for(i++; i < r; i++)
                if(queue[i].f != NULL) { /* 收集非空队列 */
                    p->next = queue[i].f;
                    p = queue[i].e;
                }       
            p->next = NULL;
        }
        (*plist)->next = head;
    }
    struct Node element[11]={
        0,0,0,NULL,/*表头*/
        0,3,6,NULL,/*36*/
        0,0,5,NULL,/*5*/
        0,1,6,NULL,/*16*/
        0,9,8,NULL,/*98*/
        0,9,5,NULL,/*95*/
        0,4,7,NULL,/*47*/
        0,3,2,NULL,/*32*/
        0,3,6,NULL,/*36*/
        0,4,8,NULL,/*48*/
        0,1,0,NULL /*10*/
    };
    int main(){
        int i;
        RadixList p = element;
        for (i = 0; i < 10; i++)
            element[i].next = &element[i+1];
        element[10].next = NULL;
        radixSort(&p, 3, 10);
        p = p->next;
        while (p != NULL){
            printf("%d ", p->key[1]*10+p->key[2]);
            p = p->next;
        }
        getchar();
        return 0;
    }

    4.4.选择排序

    选择排序的基本方法是:每步从待排序记录中选出排序码最小的记录,顺序放在已排序的记录序列的后面,直到全部排完。主要包括直接选择排序和堆排序等。

    4.4.1.直接选择排序

    直接选择排序的方法是:首先在所有记录中选出排序码最小的记录,与第一个记录交换,然后在其余的记录中再选出排序码最小的记录与第二个记录交换,以此类推,直到所有的记录排好序。

    #include<stdio.h>
    #define MAXNUM 100
    #define TRUE 1
    #define FALSE 0
    typedef int KeyType;
    typedef int DataType;
    typedef struct {
        KeyType key;         /* 排序码字段 */
        /*DataType info;     记录的其它字段 */
    } RecordNode;
    typedef struct {
        int n;               /* n为文件中的记录个数,n<MAXNUM */
        RecordNode record[MAXNUM];
    } SortObject;
    void  selectSort(SortObject * pvector) {   /* 按递增序进行直接选择排序 */
        int i, j, k;
        RecordNode temp, *data = pvector->record;
        for( i = 0; i < pvector->n-1; i++ ) {  /* 做n-1趟选择排序 */
            k = i;
            for (j = i+1; j < pvector->n; j++) /* 在无序区内找出排序码最小的记录Rk*/
                if (data[j].key < data[k].key) k = j;
            if (k != i) {                      /* 记录Rk与Ri互换 */
                temp = data[i];
                data[i] = data[k];
                data[k] = temp;
            }     
        }
    }
    SortObject vector={8, 49,38,65,97,76,13,27,49};
    int main(){
        int i;
        selectSort(&vector);
        for(i = 0; i < 8; i++)
            printf("%d ", vector.record[i]);
        getchar();
        return 0;
    }

    4.4.2.堆排序

    堆排序的方法是先把待排序的记录构造成堆,然后通过从堆中不断选出最小元素,从而达到排序的目的。

    #include<stdio.h>
    #define MAXNUM 100
    #define TRUE 1
    #define FALSE 0
    typedef int KeyType;
    typedef int DataType;
    typedef struct {
        KeyType key;         /* 排序码字段 */
        /*DataType info;     记录的其它字段 */
    } RecordNode;
    typedef struct {
        int n;               /* n为文件中的记录个数,n<MAXNUM */
        RecordNode record[MAXNUM];
    } SortObject;
    /* 定义宏是为了使程序清晰 */ 
    #define leftChild(i) (2*(i)+1)
    void  sift(SortObject * pvector, int i, int n) {
        int child; 
        RecordNode temp = pvector->record[i], *data = pvector->record;
        child = leftChild(i);      /* Rchild是R0的左子女 */
        while(child<n) {
            if (child < n-1 && data[child].key < data[child+1].key)
                child++;           /* child 指向Ri的左、右子女中排序码较大的结点 */
            if (temp.key < data[child].key) {
                data[i] = data[child]; 
                i = child;  child = leftChild(i);/* child换到父结点位置,继续调整*/
            }
            else break;            /* 调整结束 */
        }
        data[i] = temp;            /* 将记录Ri放入正确位置 */
    }
    void  heapSort(SortObject * pvector) {    /* 对记录R0到Rn-1进行堆排序 */
        int i, n = pvector->n;
        RecordNode temp, *data = pvector->record;
        
        for (i = n/2-1; i >= 0; i--)
            sift(pvector, i, n);              /* 建立初始堆 */
        for (i = n-1; i > 0; i--) {           /* 进行n-1趟堆排序 */
            temp = data[0];                   /* 当前堆顶记录和最后一个记录互换 */
            data[0] = data[i];
            data[i] = temp;
            sift(pvector, 0, i);              /* 从R0到Ri-1重建堆 */
        }
    }
    SortObject vector={8, 49,38,65,97,76,13,27,49};
    int main(){
        int i;
        heapSort(&vector);
        for(i = 0; i < 8; i++)
            printf("%d ", vector.record[i]);
        getchar(); 
        return 0;
    }

    4.5.归并排序

    归并排序的主要思想是:把待排序的文件分成若干个子文件,先将每个子文件内的记录排序,再将已排序的子文件合并,得到完全排序的文件。合并时开始只要比较各子文件第一个记录的排序码,排序码最小的记录为排序后的第一个记录,取出该记录,继续比较各子文件的第一个记录,找出排序后的第二个记录,如此反复,经过一次扫描,得到排序结果。

    归并排序的思想可以用于内排序,但更多的用于外排序。

    #include<stdio.h>
    #define D 3                       /* D为排序码的最大位数 */
    #define R 10                      /* R为基数 */
    typedef int KeyType;
    typedef int DataType;
    struct Node;                      /* 单链表结点类型 */
    typedef struct Node RadixNode;
    struct Node {
        KeyType key[D]; 
        /* DataType info;*/
        RadixNode *next;
    };
    typedef RadixNode * RadixList;
    typedef struct QueueNode {
        RadixNode *f;                  /* 队列的头指针 */
        RadixNode *e;                  /* 队列的尾指针 */
    } Queue;
    Queue queue[R];
    void radixSort(RadixList * plist, int d, int r) {
        int i,j,k; 
        RadixNode *p, *head = (*plist)->next;
        for(j = d-1; j >= 0; j--) {         /* 进行d次分配和收集*/
            p = head;
            for(i = 0; i < r; i++) { 
                queue[i].f = NULL;  queue[i].e = NULL; /* 清队列 */
            }
            while (p != NULL) {
                k = p->key[j];              /* 按排序码的第j个分量进行分配*/
                if (queue[k].f == NULL) 
                    queue[k].f = p;         /* 若第k个队列为空,则当前记录为队头*/ 
                else (queue[k].e)->next = p;/* 否则当前记录链接到第k队的队尾*/
                queue[k].e = p;
                p = p->next;
            }
            for(i = 0; queue[i].f == NULL; i++) /* 找出第一个非空队列*/
                ;
            p = queue[i].e;  head = queue[i].f; /* head为收集链表的头指针*/
            for(i++; i < r; i++)
                if(queue[i].f != NULL) { /* 收集非空队列 */
                    p->next = queue[i].f;
                    p = queue[i].e;
                }       
            p->next = NULL;
        }
        (*plist)->next = head;
    }
    struct Node element[11]={
        0,0,0,NULL,/*表头*/
        0,3,6,NULL,/*36*/
        0,0,5,NULL,/*5*/
        0,1,6,NULL,/*16*/
        0,9,8,NULL,/*98*/
        0,9,5,NULL,/*95*/
        0,4,7,NULL,/*47*/
        0,3,2,NULL,/*32*/
        0,3,6,NULL,/*36*/
        0,4,8,NULL,/*48*/
        0,1,0,NULL /*10*/
    };
    int main(){
        int i;
        RadixList p = element;
        for (i = 0; i < 10; i++)
            element[i].next = &element[i+1];
        element[10].next = NULL;
        radixSort(&p, 3, 10);
        p = p->next;
        while (p != NULL){
            printf("%d ", p->key[1]*10+p->key[2]);
            p = p->next;
        }
        getchar();
        return 0;
    }

     

    转载于:https://www.cnblogs.com/CoderTian/p/6719277.html

    展开全文
  • 数据结构算法(3)--排序 总结并记录常见的几种排序算法. 稳定排序算法 Note: 稳定性是指当数组中有两个相同值的元素p和q ,其排序完成后q依旧在p右边。 (1)插入排序 说明: 插入排序在n较小且原始数组基本有序的...
  • 选择排序的基本思想是:每一趟(如第i趟)在后面n-i+1个待排序元素中选择关键字最小的元素,作为有序子序列的第i个元素,执行n-1趟,最后那个不用选了。 主要包括:简单选择排序和堆排序。 ...
  • 数据量比较小,常见于小游戏中10个左右数据的排序场景 具体实现 /** * 冒泡排序算法 * * 适用于数据量比较小的场景 * * @param array */ public static void bubbleSort(int[] array)...
  • 数据结构分类 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都...
  • 数据结构基础概念篇

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

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

    2018-11-15 19:33:22
     数据结构主要研究非数值性程序设计中所出现的计算机操作对象以及他们之间的关系和运算等  术语   数据(Data):信息 对在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称;  例如 在结...
  • 小猪的数据结构辅助教程——1.数据结构与算法绪论标签(空格分隔): 数据结构本节学习路线图与学习要点学习要点: 1.了解数据结构的相关概念 2.了解算法的相关概念 3.熟悉时间复杂度的计算 4.了解空间复杂度...
  • ... 数据结构(C语言版 第2版)课后习题答案 严蔚敏 等 编著,仅供参考,还是自己认真做了再看 ...(1)在数据结构中,从逻辑上可以把数据结构分成( C )。 A.动态结构和静态结构 B.紧凑...
  • 面试给人上了一课,突然感觉数据结构很重要;还有,帮助后来者,刚接触数据结构的 童鞋们一点点方向,不至于学完什么都不知道!大部分学校采用的教程应该是严蔚敏老师的 《数据结构(C语言版)》吧,而讲数据结构课程...
  • 小猪的数据结构辅助教程——3.2 栈与队列中的链栈标签(空格分隔): 数据结构1.本节引言: 嗯,本节没有学习路线图哈,因为栈我们一般都用的是顺序栈,链栈还是顺带提一提吧, 栈因为只是栈顶来做插入和删除操作...
  • 程序=算法+数据结构 N.沃思(Niklaus Wirth)教授提出:  程序=算法+数据结构  以上公式说明了如下两个问题:  (1)算法决定如何构造和组织数据(算法→数据结构)。  (2)算法的选择依赖于作为基础的...
  • 数据结构与算法(java版)标签: java 数据结构 算法2017年12月28日 21:50:08102人阅读 评论(0) ...(1)数据结构与算法概念解析 (2)数据结构之数组 (3)数据结构之栈 (4)数据结构之队列 (5)数据结...
  • 数据结构(C语言版本) 第1章 绪论 1.常用的数据结构类型:集合、线性、树形、图状。 2.数据结构: - 逻辑结构:数据元素之间的关系 - 存储结构:数据结构在计算机中的表示。存储结构分为:顺序存储结构和...
1 2 3 4 5 ... 20
收藏数 3,654,691
精华内容 1,461,876
热门标签
关键字:

数据结构