精华内容
下载资源
问答
  • 指针排序

    2013-10-11 19:37:00
    小Q在课堂上学到利用指针指向数据,数据不交换指针交换就能达到把数据排序的目的。他觉得很神奇,也觉得在单个数据元素占有空间太大的情况下这样排序非常有效。他想知道,如果在事先不知道元素个数的情况下,能否用...

    http://acm.uestc.edu.cn/problem.php?pid=1042

    Description

     

    小Q在课堂上学到利用指针指向数据,数据不交换指针交换就能达到把数据排序的目的。他觉得很神奇,也觉得在单个数据元素占有空间太大的情况下这样排序非常有效。他想知道,如果在事先不知道元素个数的情况下,能否用这种方法对输入的元素排序,你能帮他吗?(数据的存储要求用动态分配内存实现)

     

    Input

     

    第一行是一个正整数T表示测试数据的组数。下面每一组的第一行是一个整数n,第二行有n个待排序的整数,每个数后有一个空格。每个数据的大小不会超过整型数据存储的范围。

     

    Output

     

    每组数据对应有一行排序后的数据输出,每个数据后应有一个空格。

     

    Sample Input

     

    1
    5
    2 9 7 4 3

     

    Sample Output

     

    2 3 4 7 9

    我的解答是:

     1 #include<stdio.h>
     2 
     3 int N,i,t,j,k,p;
     4 int data[2000][2000],n[2000];
     5 
     6 int main()
     7 {
     8     scanf("%d",&t);
     9     for (i=0;i<t;i++) 
    10     {
    11         scanf("%d",&n[i]);    
    12         for (j=0;j<n[i];j++) scanf("%d",&data[i][j]);    
    13     }
    14     for(k=0;k<t;k++)
    15         for(p=0;p<t;p++) 
    16     {
    17         for(i=0;i<n[k];i++)
    18          for(j=0;j<n[k]-1;j++)
    19             if(data[p][j]>data[p][j+1])
    20            {t=data[p][j];data[p][j]=data[p][j+1];data[p][j+1]=t;}
    21       }
    22       for(i=0;i<t;i++)
    23           {
    24           for(j=0;j<n[i];j++) printf("%d ",data[i][j]);
    25           printf("\n");
    26           }
    27     
    28 }

    好像不是指针排序,有待优化。

    转载于:https://www.cnblogs.com/uestc-msc/p/3364071.html

    展开全文
  • 二叉排序树与平衡二叉树的实现

    热门讨论 2010-12-26 15:25:31
    本次实验是利用二叉排序树和平衡二叉树达到以下目的:(1)以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T;(2)对二叉排序树T作中序遍历,输出结果;(3)计算二叉排序树T查找成功的平均查找长度,输出结果...
  • 10.8 有关指针数据类型和指针运算的小结 167 10.8.1 有关指针数据类型的小结 167 10.8.2 指针运算的小结 167 10.8.3 void 指针类型 168 11 结构体与共用体 11.1 定义一个结构的一般形式 170 11.2 结构类型变量的...
  •  新名词的认识,地址和指针,对内存单元进行标识编号利用指针实现储存空间的动态分配。对复杂数据进行处理,能对计算机的内存分配进行控制,在函数调用中指针还可以返回多个值,  "*"为指针声明符,在定义指针时...

    1,本次课学习到的知识点:

      新名词的认识,地址和指针,对内存单元进行标识编号利用指针实现储存空间的动态分配。对复杂数据进行处理,能对计算机的内存分配进行控制,在函数调用中指针还可以返回多个值,

      "*"为指针声明符,在定义指针时被使用,说明被定义的那个变量是指针。

      冒泡排序法,二分法。

    2. 实验过程中遇到的问题及解决方法:

      对于指针和地址的关系还是搞不太清楚,因为刚刚接触这个定义所以在编程时经常搞混,这个还有待多加练习,试验中并没有出现很大的错误,一般都是些小错,运行成功率也挺高。

    3. 实验心得体会及本章学习总结:

      指针的引入使得函数更复杂,可同时处理的东西更多,在编程之前要确定关系在编程。另外两个排序法比起之前的if else更有规律,更方便进行个别元素的提取。

    问题回答

    (1)在课上讲过,指针相当于房间号,指针变量的值所存放的时指向地址相加不能保证是有效的新地址。

    (2)字符数组名有固定的地址,不需要加&,若加上的话没有效果,因为本身已经有固定地址。

    (3)数组名是常量指针,不能对常量进行赋值。

    coding地址:https://coding.net/u/gdxx_160809107/p/TEXT11/git

    转载于:https://www.cnblogs.com/MarvelD160809107/p/6146149.html

    展开全文
  • 10.8 有关指针数据类型和指针运算的小结 167 10.8.1 有关指针数据类型的小结 167 10.8.2 指针运算的小结 167 10.8.3 void 指针类型 168 11 结构体与共用体 11.1 定义一个结构的一般形式 170 11.2 结构类型变量的...
  • 征服指针(C)

    2018-01-20 13:00:44
    2.6 利用malloc()来进行动态内存分配(堆) 84 2.6.1 malloc()的基础 84 2.6.2 malloc()是“系统调用”吗 88 2.6.3 malloc()中发生了什么 89 2.6.4 free()之后,对应的内存区域会怎样 91 2.6.5 碎片化 93 ...
  • 使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。堆...

    链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。

    使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

    堆是一种树,由它实现的优先级队列的插入和删除的时间复杂度都为O(logN),这样尽管删除的时间变慢了,但是插入的时间快了很多,当速度非常重要,而且有很多插入操作时,可以选择用堆来实现优先级队列。

    数组表示堆的一些要点。若数组中节点的索引为x,则:

    节点的左子节点是 2index+1,

    节点的右子节点是 2index+2,

    节点的父节点是 (index-1)/2。

    Hashmap

    是一个最常用的Map,它根据键的HashCode值存储数据,根据键可以直接获取它的值,具有很快的访问速度,遍历时,取得数据的顺序是完全随机的。 HashMap最多只允许一条记录的键为Null(如果建是null存在数组的第一个位置);允许多条记录的值为 Null;HashMap不支持线程的同步,即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步,可以用 Collections的synchronizedMap方法使HashMap具有同步的能力,或者使用ConcurrentHashMap。

    Hashtable

    与 HashMap类似,它继承自Dictionary类,不同的是:它不允许记录的键或者值为空;它支持线程的同步,即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。

    LinkedHashMap

    是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的.也可以在构造 时用带参数,按照应用次数排序。在遍历的时候会比HashMap慢,不过有种情况例外,当HashMap容量很大,实际数据较少时,遍历起来可能会比 LinkedHashMap慢,因为LinkedHashMap的遍历速度只和实际数据有关,和容量无关,而HashMap的遍历速度和他的容量有关。

    TreeMap

    实现SortMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator 遍历TreeMap时,得到的记录是排过序的。

    一 般情况下,我们用的最多的是HashMap,在Map 中插入、删除和定位元素,HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键,那么TreeMap会更好。如果需要输出的顺序和输入的相同,那么用LinkedHashMap 可以实现,它还可以按读取顺序来排列.

    主要算法:

    int count = 0;

    public int InversePairs(int [] array) {

    if(array==null)

    return 0;

    mergeSort(array,0,array.length-1);

    return count;

    }

    private void mergeSort(int[] data,int start,int end) {

    int mid = (start + end) / 2;

    if (start < end) {

    mergeSort(data, start, mid);

    mergeSort(data, mid + 1, end);

    merge(data, start, mid, end);

    }

    }

    public void merge(int[] data,int start,int mid,int end) {

    int arr[] = new int[end - start + 1];

    int c = 0;

    int s = start;

    int index = mid + 1;

    while (start <= mid && index <= end) {

    if (data[start] < data[index]) {

    arr[c++] = data[start++];

    } else {

    arr[c++] = data[index++];

    count += mid +1 - start;

    count %= 1000000007;

    }

    }

    while (start <= mid) {

    arr[c++] = data[start++];

    }

    while (index <= end) {

    arr[c++] = data[index++];

    }

    for (int d : arr) {

    data[s++] = d;

    }

    }

    展开全文
  • 数据结构笔记

    2020-06-15 10:54:02
    不同点有很多,主要的点包括:作为一个类,接口的使用很方便,有很多较为使用的函数(包括排序、查找等),其占用的内存空间可以动态变化,当当前大小的内存空间被利用完后仍需要增加数据时会自动扩容(当然自动指的...

     

    目录

    首先较常见的线性结构如下:

    向量(vector):

    列表(LIST):

    堆栈(Stack):

    队列(queue):

    下面介绍半线性结构——树:

    二叉树(二叉树-BinTree):

    二叉搜索树(Binary search tree-BST):

    平衡二叉搜索树(BBST):

    AVL:

    伸展树:

    B树(B-Tree): 

    红黑树(Red-Black Tree):

    词典-散列表(哈希表-Hash table):

    优先队列(priority queue):

    完全二叉堆(Complete Binary Heap):

    左式堆 :

    串:

    KMP算法:

    BM算法:

    Karp-Rabin(KR)算法:

    下面介绍非线性结构——图:

    图(Graph):

    排序算法:

    1、冒泡排序:

    2、插入排序:

    3、希尔排序(缩小增量排序):

    4、选择排序:

    5、快速排序

    6、堆排序:

    7、归并排序:

    8、计数排序:

    9、桶排序:


    首先较常见的线性结构如下:

    向量(vector):

    与常见的数组极为相似,申请的是连续地址下的一段内存空间。不同点有很多,主要的点包括:作为一个类,接口的使用很方便,有很多较为使用的函数(包括排序、查找等),其占用的内存空间可以动态变化,当当前大小的内存空间被利用完后仍需要增加数据时会自动扩容(当然自动指的也是类里面定义的扩容函数)。向量的查找(search)操作效率很高为O(logn)的时间复杂度(这是采用二分查找的优势)。常用的排序方法为起泡排序(时间复杂度为稳定的O(n^2))和归并排序(时间复杂度为稳定的O(nlogn))。数据的获取采用call by rank模式,为O(1)的时间复杂度。

    列表(LIST):

    通过链表实现,与向量的区别在于其不要求数据的地址空间连续,而是通过记录前驱和后驱指针来保持数据的连续性,与向量结构相比,其优点在于对数据的插入和删除操作时O(1)的时间复杂度,而向量是O(n),缺点是其对于数据的查找工作是O(n)的时间复杂度,而向量是O(logn)。常用的排序方法为选择排序(每次找到无序列表中最小的取出)和插入排序(向已排序序列中插入新数据以满足有序性,类似于摆扑克牌)。数据的获取采用call by position模式。

    堆栈(Stack):

    LIFO(后入先出)结构,通过vector结构实现(这是因为只需要再栈顶进行数据的添加和删除,而vector结构的最后一个数据的插入和删除操作时间复杂度均为O(1),且对应的接口基本满足堆栈的要求)。

    队列(queue):

    FIFO(先入先出)结构,通过List结构实现(这是因为队列要在数据的头部尾部分别进行插入和删除操作,而List结构的插入和删除擦欧总均为O(1),且对应的接口基本满足队列的要求)。

    上面提到的线性基础结构为vector和List都有其优缺点,但其都无法满足高查找效率和高插入删除效率的要求,即高效地兼顾静态操作和动态操作。

    下面介绍半线性结构——树:

    可以视为List<List>(列表的列表)结构,也可以看作是二维的列表,可以视为半线性结构,其更多的表示一种层次关系。

    二叉树(二叉树-BinTree):

    利用类似于链表的结构,不同的是每个二叉树节点-BinNode其带有的指针为一个父亲节点和两个孩子节点,其用于描述任意有根且有序的多叉树,其演绎的过程如下图。

     值得注意的是,在对二叉树遍历的时候有时需要用到其他数据结构,对于先序(根-左-右)、中序(左-根-右)、后序(左-右-根)遍历来说,其模式类似于DFS,因此在不采用递归调用的情况下需要使用堆栈结构;而对于层次遍历来说,其模式类似于BFS,因此其在不采用递归调用的情况下需要利用队列结构。

    二叉搜索树(Binary search tree-BST):

    数据的获取采用call by key模式,其数据获取和查找、插入、删除的操作时间复杂度均为O(h),其中h为树的高度。不同于基本的二叉树,BST的结构具有有序性,每个轴点都不小于其左子树并且不大于其右子树,这一特性就使得对其进行中序遍历后,得到的序列为非降序列(这里指的是key),示意图如下:

    其中,插入、删除、查找的操作都是从根节点出发依次与节点key值进行比较进而判断将要操作的值所在的位置以满足其有序性。

    平衡二叉搜索树(BBST):

    由于BST的O(h)的时间复杂度带有很大的不确定性,即树的高度h的范围为[logn,n]这样一个区间。而BBST在设计上保证了高度渐进的不超过logn,继而将时间复杂度降至O(logn),具体的方法是通过等价变换来调整树达到平衡。典型的实现类型包括AVL树和红黑树等。下面详细介绍:

    AVL:

    AVL树在判断树是否平衡时引入了平衡因子,即每一节点的左右子树的高度差,如果差值的绝对值大于1,说明不平衡需要恢复平衡。可以证明这样的一种结构要求使得其高度渐进为logn。

    这里失衡后的回复平衡操作对于插入和删除而言是有区别的,但都可以通过单旋和双旋来完成,区别在于插入操作无需要向上判断至根节点而删除操作需要判断以恢复由旋转而导的更高层的节点失衡(最坏的情况需要重新调整logn次)。通过旋转的方法比较复杂,一般采用3+4重构的方法直接进行恢复平衡,形象的来说,旋转对应于魔方的扭动,而3+4相当于打散重新组装。具体的3+4就是找到失衡节点的祖孙三代的三个节点以及致其下面的4个子树,进而进而重构。如下图所示,即为3+4重构的示意图(在g处失衡)。

                 

    伸展树:

    伸展树是在BST的基础上进行调整。考虑到局部性(即上一次被查找的数据,更有可能在这次中被查找),对每次查找的节点将其移至根节点,这样对于伸展树来说,search操作将会改变树的拓扑结构,将不再是静态操作。其中移至根节点可以通过旋转逐层向上,如下图,这种方法的时间复杂度为O(n),显然不能够让人满意。

    而根据Tarjan的双层伸展算法,这个移至根节点的均摊时间复杂度为O(logn),其采用的是每次对两层进行调整,这样使得每次调整后的树在该路径下深度减半,其操作示意图如下,注意的是,其不同是旋转次序不同,双层调整首先以祖父节点(g)为轴旋转,而单层调整先以父节点(p)为轴旋转。

     两种调整策略在坏的情况下的不同表现如下:

     

    B树(B-Tree): 

    B树与上述的树结构不同,其并不是二叉树的结构,而是一种多路平衡的搜索树。其设计是考虑到实际需要的数据越来越多而内存却并不够用的情况,更具体的是在I/O访问的情况,即内存与外存的数据交换需要大量的时间(不过这种消耗在1B和1KB的数据量上的时间花费是基本相当的)。其结构如下图所示,与AVL树的区别在于每个节点不仅只有一个关键码(key),而是具有多个(可称之为超级节点),这样每次访问时得到的数据即为多个(大小即为数据块的大小,常在200-300间,设256),这种方式使得单词查找所需的I/O操作为log(256,n)。同时其每个叶节点的深度都相等,同时外部节点的深度也都相等(外部节点即叶节点的孩子)。

    不同的B树,阶数不同,对于一m阶B树,其每个内部节点中关键码个数不超过m-1个,其分支数不超过m个,同时对于内存节点来说,其分支数不能小于m/2个,故亦可称之为([m/2],m)-树,例如m=5,则为(3,5)-树。其每个节点就可以有两个向量分别表示关键码和子分支的指针向量。

    B树一般都是存放在外存中,内存中仅为为常驻的根节点。在搜索时,首先判断根节点,找到应该继续搜索的子分支,进而通过一次I/O操作将这个分支节点读入内存继续判断,循环往复直至找到目标或外部节点(这里的外部节点可以连接至更低层次的存储结构,如SSD->机械)。注意的是虽然这种树结构的查找方法的渐进复杂度同为O(logn),但其在常数项要小很多。

    B树的插入会改变树某一节点的关键码数量,当其超过m-1,就会发生上溢,进而需要逐层向上分类,直至不再上溢后到达根节点,如果根节点页出现上溢,则继续分裂,这回导致树的高度+1。

    同样,B树的删除操作也会改变树某一节点的关键码数量,当其小于[m/2],就会发生下溢,进而需要进行调整。首先会查询其左右节点是否能够移动一个关键码至发生下溢的节点中,可以则进行旋转操作调整一个关键码进而修改节点使得其满足B树规则(旋转的操作不会导致下一步的下溢或上溢)。否则就与存在的左或右兄弟节点进行合并,但合并会导致他们的父节点减少一个关键码进而可能发生下溢,需要向上判断直至根节点(这最后有可能会使得树高度最终-1)。

    红黑树(Red-Black Tree):

    对应着C++中的map<key, value>结构。作为BBST中的一员,红黑树支持对历史版本的查找,其插入和删除的操作都为O(logn)的时间复杂度,其缺点是其构建时间较慢。其结构满足如下图所示的规则。这里的外部节点与B树中定义相似,实际是不存在的。

    从一定意义上将,红黑树可以视为(2,4)的B树,如下所示即对应不同情况的红黑树对应(2,4)-树。可以证明,红黑树对应的黑高度等于其转换为(2,4)-树时的树高度(<=log(n+1)),且红黑树的高度一定小于两倍的黑高度。在接口中定义的树高度即黑高度,而不是实际的树高度。

    红黑树的插入操作首先将插入的节点染为红的,之后判断是否产生双红缺陷(即父亲节点和子节点均为红色),继而进行修正,这种修正发生的拓扑结构的变化为 O(1),不过其染色的变化可能为O(logn)。

    红黑树的删除操作可能会产生双黑缺陷(即父亲节点和子节点均为黑色,对应B树中的下溢),需要进行调整,这种调整的细节可以参考B树面对下溢时采取的操作,不同的是在修复下溢导致更上的节点发生下溢循环时,其染色的变化可能为O(logn),但拓扑结构的变化为 O(1)。

    比较发现,红黑树优于AVL树之处在于其插入和删除操作对树的拓扑结构的影响为常数项,不会大幅度变化,这在对历史版本的查询过程将带来很大的好处。

    :由于该结构为树结构,因此key值应具备比较操作,进而才能够实现查找、插入、删除等操作,这也是map结构能够具有有序性的原因。

    词典-散列表(哈希表-Hash table):

    在C++中对应着unordered map,也可以称为桶数组(bucket array),其访问方式为call by value(寻数值访问),与上述所以方法不同在于,想要获取一个词条,我们呢可以根据一个固定的值进行索引,例如Array["hi"],即找到字符串“hi”对应的词条,那么首选将hi住那换为hash code,再转换为散列表中的索引。

    一种字符转hash code的方法如下所示,其近似于多项式计算,但比多项式运算要快:

    实际上这种索引的区别在于其非连续且似乎随机,即实际上我们会有100000的可能的hash code,但实际的只有100个不同词条,那么我们需要的空间应该时大于100就够,因此需要散列函数将hash code转换为散列表中的索引。常见的散列函数有整除取余(一般除树为素数),平方取中,折叠法,伪随机数法等。

    上述方法都无可避免的再转换过程中出现相同的索引冲突(即不同的value对应相同的散列表中的索引)。

    那么一种解决方案是多槽位法,类似于B-树,在每个索引对应的桶中,包含的不是一个词条,而是规定的多个。显然易见的,这种方法并不能从根本的解决这个问题。

    另一种方法是独立链法,即在每个索引下包含的是个词条列表,即封闭定址。这种方法虽然解决了冲突问题,但其需要动态调整内存,且空间不连续,很难利用到系统缓存。

    一种解决方法是开放定址,将每个桶的空间固定,当其中数据已经满了,就将其放置在备用桶中,如果仍满,继续(这里的备用桶是对应着其他的索引,这个查找链是一个固定的查找顺序),一种较优的方式是双向平方试探。

    在这种结构中常采用的排序方式为桶排序,对N个待排序元素的取值范围是[1, M]的情况,计数排序的时间复杂度为O(N+M)。

    :对应的unordered map结构map结构相比,其不具有有序性(因此其key值无需带有比较属性),但其在进行查找和插入删除操作的速度更快。

    优先队列(priority queue):

    采用的是call by priority,可以用看作是栈(stack-LIFO)和队列(queue-FIFO)的推广。其可以通过BBST实现,但相对来说没有必要,因为BBST的结构功能完全可以涵盖了PQ的功能,一般采用的是完全二叉堆结构来实现。

    完全二叉堆(Complete Binary Heap):

    对应C++中的priority_queue 。其在逻辑上等同于完全二叉树(平衡因子处处非负的AVL树,即平衡因子只能为0和+1,不能为-1),在物理上直接借助向量实现。结构对应关系如下图,注意这里的数字指的是数据的rank,不是其Value。CBH中,父节点的优先级应不小于其子节点,进而堆最大值的获取仅为O(1)(即直接输出rank=0出的数据即可)。指的注意的是,在这个结构中父与子之间不是通过指针相连,而是通过固定的计算得到其rank,进而获取,如图所示的parent(i)等。

    插入操作中,首先将数据直接存放在向量最末端,并更新整个堆的优先性,通过比较其与父节点的优先级进而判断是否需要调换,如果需要就将父亲节点和插入节点数据调换并继续向上判断。这个上滤操作最坏的时间复杂度为O(logn)。

    删除操作中(优先度最大的值),首先将根节点删除,并将最末尾的数据移至根节点,然后向下判断,更新以满足堆的有序性。这个下滤操作最坏的时间复杂度为O(logn)。

    这种结构可以通过自下而上进行下滤来批量构建完全二叉堆(不采用自上而下上滤来构建的原因是作为树结构,其底部的节点数要大于顶部,进而从底部向上可以显著减少过程中的滤操作的最大高度),具体的从最末尾的非根节点开始,依次进行下溢操作,直至根节点,这一构造方式的时间复杂度为O(n),也称为弗洛伊德(Floyd)建堆算法。

    堆排序:进而很容易想到的一种排序方式为,通过构建完全二叉堆再依次取出堆顶的元素并删除,这样即完成了堆所有数据的排序,这一排序方法的时间复杂度为O(nlogn)。更有效地方式是通过交换+下滤的操作可以极大的减少消耗的空间,如下图。

    左式堆 :

    完全二叉堆如果想将两个堆(规模分别为N和M)合并则至少需要花费O(N+M)的时间,而左式堆可以很快的将两个堆进行合并,这是其设计的主要目的。与完全二叉堆不同,其基础的结构并不是向量,而是二叉树。

    首先通过引入外部节点将堆中每个节点的度都转为偶数(0或2),进而定义空节点路径长度(Null Path  Length)。

    左式堆具有如下所示的一些性质,如图中例子也可看出左倾并不意味着左子堆规模一定大于右子堆。根据性质,从根节点沿右孩子向下查找到的即为最浅的外部节点,且存在以根节点为根的满二叉树(这个满二叉树的高度即为找到的外部节点的深度,对应图中即为3),可以证明这个右侧链的长度<=logn。

    对于两个堆的合并,只需要递归的将根节点较小的堆A与根节点较大的堆B中的右子堆合并(这将递归往复进行),合并之后比较新的堆的根节点的左右npl值是否满足要求(即左子堆的npl应不小于右子堆),如果不满足,则将左右调换(整个合并的过程将递归往复进行直至结束)。这一过程是围绕着左式堆的右侧链进行的,因此时间复杂度不会超过右侧链的长度O(logn)。

    左式堆的插入和删除操作都可以基于堆的合并来完成。其中插入操作将插入节点视为一个堆与原本的堆合并即可;删除操作将根节点删除,并将左右子堆合并即可。显然这两种操作的时间复杂度也为O(logn)。

    串:

    即常用的字符串,一般为线性结构,字符串匹配算法包括暴力匹配、KMP、BM、RK。

    KMP算法:

    KMP算法用于实现字符串匹配,与暴力匹配算法不同,KMP首先会根据模板串构建一个next数组,来表明对应位置的字符串所具有的最大相同前缀和后缀的长度,进而在匹配串逐字符比较时,如果失配,就利用next数组的记录来滑动比较窗口继续判断。这一方法的时间复杂度为O(N + M),具体实现如下(图中列出的是一种改进后的KMP算法,区别在于标红处,这样使得在比较时不会对重复判断)。

    BM算法:

    BM-BC:坏字符策略(Bad-Character)。如果说KMP算法更多的是总结经验(利用成功的匹配),那么BM算法更多的是总结教训(利用失败的匹配)。与KMP算法不同,这一算法的思想是在匹配时从后往前比对,在比对失配的情况考虑模式串是否含有该字符,如果没有则可直接将整个模式串跳过该字符,如果找到则将模式串移动使得该失配处匹配,进而继续从末尾开始比较,以此往复。与kmp相似,这里可以首先通过处理模板串来构建一个查找的数组bc,进而每次失配后可直接查询。这一方法最好的结果为O(N/M),然而最坏的结果为O(N×M)。

    BM-GS:好后缀策略(good-suffic)。这里在BC的基础上结合KMP的思想,即考虑到经验(成功匹配的字符),这将结合两者的优点,使得算法匹配更加快速,这一过程可以参考KMP算法构建gs表进而实现,其对应从后向前匹配中可以借鉴的经验。这样一种实现将时间复杂度的最坏情况缩减为O(N+M)。

    各种算法的性能对比如下:

    Karp-Rabin(KR)算法:

    这种方法基于一种串即为数的思想,将模式串转换为一个整数,进而与匹配串中的子串转换成的数比较。注意的是这个转换采用散列表的方式,通过哈希函数转换,这样虽然缩小了转换后的值的范围,但显然会带来冲突,解决方法即在数值比较成功后在逐字符比较以确定匹配正确。这一方法的最坏时间复杂度为O(N×M),但一般为O(N+M)。

    其中hash函数的实现需要特殊设计以保证冲突的概率尽量小,一种可行的方法是对字符串进行转换时将其对一个较大的素数取余,指的注意的是对匹配传中连续的字串进行hash是是有规律的,如下图所示,即可以在O(1)的时间计算出下一子字符串的hash值,实现代码如右图。

    下面介绍非线性结构——图:

    图(Graph):

    图的基本构成即为点和边的集合G=(V;E),其中V即为点的集合(Vertex),E即为边的集合(Edge)。其表示形式一般分为两种,即邻接矩阵和邻接链表。

    邻接矩阵,即通过构建N×N的数组来表示N个点之间的连接情况,1为连通,0为断开,显然对于无向图来说其邻接矩阵是对称的;值得注意的是,这里01对应的是无权图,当是有权图,其值可以代表边的权重。

    邻接链表,即对每个顶点构建一个链表,其中包含其能够连通的点的集合。对于每个顶点来说,其链表空间大小应是不同的,即其所连边越多,其链表越大。

    除上述外,还有一种表示方式为关联矩阵,但不太常用,不做过多了解。

    对图的遍历方法一般包括深度优先搜索(DFS)和广度优先搜索(BFS),和两种方法再算法中常会被用到,这里也不多做介绍。值得注意的是在遍历的过程中记录下每个顶点的搜索时间和退出时间可以在之后很快的判断其是否在该遍历树中具有从属关系。例如顶点A的stime=1,dtime=10,而顶点B的stime=3,dtime=6,那么区间的包含说明B在A的搜索路径下被找到。

    排序算法:

    排序算法有很多,包括插入排序冒泡排序堆排序归并排序,选择排序,计数排序基数排序桶排序快速排序等。插入排序,堆排序,选择排序,归并排序和快速排序,冒泡排序都是比较排序,它们通过对数组中的元素进行比较来实现排序,其他排序算法则是利用非比较的其他方法来获得有关输入数组的排序信息。

    对应实现参考:https://leetcode-cn.com/problems/sort-an-array/solution/shi-da-pai-xu-suan-fa-by-h_jd-cht3/

    1、冒泡排序:

    从数组中第一个数开始,依次遍历数组中的每一个数,通过相邻比较交换,每一轮循环下来找出剩余未排序数的中的最大数并“冒泡”至数列的顶端。

    稳定性:稳定

    平均时间复杂度:O(n ^ 2)

    2、插入排序:

    从待排序的n个记录中的第二个记录开始,依次与前面的记录比较并寻找插入的位置,每次外循环结束后,将当前的数插入到合适的位置。

    稳定性:稳定

    平均时间复杂度:O(n ^ 2)

    一个优化是在寻找插入位置时,采用二分法来减小比较次数,不过其仍需要移动同样次数,因此其时间复杂度仍为O(n ^ 2)

    3、希尔排序(缩小增量排序):

    希尔排序法是对相邻指定距离(称为增量)的元素进行比较,并不断把增量缩小至1,完成排序。

    希尔排序开始时增量较大,分组较多,每组的记录数目较少,故在各组内采用直接插入排序较快,后来增量di逐渐缩小,分组数减少,各组的记录数增多,但由于已经按di−1分组排序,文件叫接近于有序状态,所以新的一趟排序过程较快。因此希尔 排序在效率上比直接插入排序有较大的改进。

    在直接插入排序的基础上,将直接插入排序中的1全部改变成增量d即可,因为希尔排序最后一轮的增量d就为1。

    稳定性:不稳定

    平均时间复杂度:希尔排序算法的时间复杂度分析比较复杂,实际所需的时间取决于各次排序时增量的个数和增量的取值。时间复杂度在O(n ^ 1.3)到O(n ^ 2)之间。

    详情:希尔排序也称为递减增量法,可以视为是插入排序的优化。实现过程是将待排序列视为一个矩阵(在物理上仍是一维的向量,单纯的在逻辑上视为二维),逐列进行排序,并将其合并使其变窄,进而继续逐列排序,直至归为一列。

    其中在对每列进行排序时选择的排序方法应具有输入敏感性,即输入越有序,速度越快。而上面提到的插入排序正是这样一种排序算法。且需要注意的是相邻两次的矩阵宽度应互素,对宽度为g的矩阵希尔排序后即成为g-ordered(以g为间隔有序),在将其宽度减为h进行排序后,即为h--ordered(即对于h长度分割下,序列是分别有序的),有定理表明对于h-ordered的序列,其仍然具有g-ordered。进而序列也具有g+h-ordered,即对于以g+h为步长的序列仍具有有序性(更多的推广为g和h多项式步长)。进而对于希尔排序来说,每次宽度的缩减都会使得整体序列中的逆序对减少(这一原理类似于邮资问题,对面值为g和h的邮票,不能恰好凑齐的最大邮资为gh-g-h)。

    希尔排序的时间复杂度取决于增量的选取方法,较为良好的增量方式的希尔排序的时间复杂度介于O(n^1.2)到O(n^1.3)之间,对其的研究还未完结。

    4、选择排序:

    从所有记录中选出最小的一个数据元素与第一个位置的记录交换;然后在剩下的记录当中再找最小的与第二个位置的记录交换,循环到只剩下最后一个数据元素为止。

    稳定性:不稳定

    平均时间复杂度:O(n ^ 2)

    5、快速排序

    1)从待排序的n个记录中任意选取一个记录(通常选取第一个记录)为分区标准;

    2)把所有小于该排序列的记录移动到左边,把所有大于该排序码的记录移动到右边,中间放所选记录,称之为第一趟排序;

    3)然后对前后两个子序列分别重复上述过程,直到所有记录都排好序。

    稳定性:不稳定

    平均时间复杂度:O(nlogn)

    详情:通过选定一个轴点,将序列据轴点分为两部分,分别为大于轴点的和小于轴点的,这一过程递归进行,并最终将其合并,进而实现了快排。其中轴点的选取较为关键,通过linear Select可以在O(N)的时间复杂度选择一个中心得轴点,进而提高整个排序得效率,最坏的时间复杂度为O(nlogn),但这种方式不可行,因为线性时间的中位数选取算法实际效率非常低。

    而采用正常的轴点选取算法,其在最快的情况下会达到O(N^2)的较差效率。在C++的STL中是将快排与堆排序结合来弥补这一缺陷,并且其在递归过程中会判断数据量,当其小于某一阈值时其会变为插入排序以提高速度。其可以分为下属几个过程:

    1、  数据量大时采用快排,分段递归排序。

    2、  一旦分段后的数据量小于某个阈值,为避免快排的递归调用带来的额外负荷,就改用插入排序,这一过程是在整体快排结束后进行。

    3、  如果层次过深,还会改用堆排序

    4、  “三点中值”获取好的分割

    6、堆排序:

    堆:

    1、完全二叉树或者是近似完全二叉树。

    2、大顶堆:父节点不小于子节点键值,小顶堆:父节点不大于子节点键值。左右孩子没有大小的顺序。

    堆排序在选择排序的基础上提出的,步骤:

    1、建立堆

    2、删除堆顶元素,同时交换堆顶元素和最后一个元素,再重新调整堆结构,直至全部删除堆中元素。

    稳定性:不稳定

    平均时间复杂度:O(nlogn)

    7、归并排序:

    采用分治思想,现将序列分为一个个子序列,对子序列进行排序合并,直至整个序列有序。

    稳定性:稳定

    平均时间复杂度:O(nlogn)

    8、计数排序:

    思想:如果比元素x小的元素个数有n个,则元素x排序后位置为n+1。

    步骤:

    1)找出待排序的数组中最大的元素;

    2)统计数组中每个值为i的元素出现的次数,存入数组C的第i项;

    3)对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);

    4)反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

    稳定性:稳定

    时间复杂度:O(n+k),k是待排序数的范围。

    9、桶排序:

    步骤:

    1)设置一个定量的数组当作空桶子; 常见的排序算法及其复杂度:

    2)寻访序列,并且把记录一个一个放到对应的桶子去;

    3)对每个不是空的桶子进行排序。

    4)从不是空的桶子里把项目再放回原来的序列中。

    时间复杂度:O(n+C) ,C为桶内排序时间。

    10、稳定排序和不稳定排序

    排序算法的稳定性通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。

    选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,

    冒泡排序、插入排序、归并排序、基数排序是稳定的排序算法

    展开全文
  • 2、实现利用选择排序对存储10个数值的动态数组进行排序的通用模板。 #include using namespace std; 3. 算法事后统计分析方法,利用函数库time中clock_t类进行测试。 实例:统计5,000,000,00次空的for循环的时间...
  • 数据结构与算法.xmind

    2020-06-19 17:04:23
    当递归到规模足够小时,利用插入排序 归并前判断一下是否还有必要归并 只在排序前开辟一次空间 基数(桶)排序 思想 分配,回收(分配到不同的位置上,然后回收)..不断分配..回收来...
  • 数据库系统实现

    2013-05-12 13:09:11
    2.3.2 辅助存储器中的数据排序 2.3.3 归并排序 2.3.4 两阶段多路归并排序 2.3.5 扩展多路归并以排序更大的关系 习题 2.4 改善辅助存储器的访问时间 2.4.1 按柱面组织数据 2.4.2 使用多个磁盘 2.4.3...
  • 使用链表结构可以克服数组需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。 删除...
  • 列表 从向量到列表,是从静态到动态。 列表的基本组成单位叫做节点node。各节点通过指针或引用彼此联接,在逻辑上构成一个线性序列。...选择排序:依次在剩余数据中获得最大的那个。然后把最大的那个放到后缀有
  • 技巧99 超过3个条件的数据排序 技巧100 自定义序列排序 技巧101 按笔划排序 技巧102 按行方向排序 技巧103 按颜色排序 技巧104 排序字母与数字的混合内容 技巧105 返回排序前的状态 技巧106 排除常见...
  • 数据结构》实验

    2012-04-09 21:39:46
    内容:1、已知带头结点的动态单链表L中的结点是按整数值递增排序的,试写一算法将值为x的结点插入到表L中,使L仍然有序。 2、设计一算法,逆置带头结点的动态链表L。要求利用原表的结点空间,并要求用尽可能少的时间...
  • 顺序栈即栈的顺序存储结构是,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时设指针top指示栈顶元素的当前位置。 栈也可以用链表实现,链式存储结构的栈简称链栈。若同时需两个以上的栈,则最好...
  • 若一组记录的排序码为(46,79,56,38,40,84),则利用排序的方式建立的初始堆为() A.79,46,56,38,40,84 B.84,79,56,38,40,46 C.84,79,56,46,40,38 D.84,56,79,40,46,38 C 画出图...
  • 数据结构演示软件

    2013-06-02 21:32:36
    本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...
  • 数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    9. 数据结构的抽象操作的定义与具体实现有关。( )【华南理工大学 2002 一、1(1分)】 10. 在顺序存储结构中,有时也存储数据结构中元素之间的关系。( )【华南理工大学 2002 一、2 (1分)】 11. 顺序存储方式的...
  • 二:内容:1、已知带头结点的动态单链表L中的结点是按整数值递增排序的,试写一算法将值为x的结点插入到表L中,使L仍然有序。 2、设计一算法,逆置带头结点的动态链表L。要求利用原表的结点空间,并要求用尽可能少的...
  • 数据结构与面向对象程序设计(C++版)(第4版)》首先介绍了软件开发的各个阶段、C++面向对象程序设计思想,然后从软件开发的角度,利用面向对象设计的思想,系统阐述了指针动态数组、链表、模板类、迭代器、栈、...
  • 数据结构与面向对象程序设计(C++版)(第4版)》首先介绍了软件开发的各个阶段、C++面向对象程序设计思想,然后从软件开发的角度,利用面向对象设计的思想,系统阐述了指针动态数组、链表、模板类、迭代器、栈、...
  • 152 利用图形页实现动画 153 图形时钟 154 音乐动画 第五部分 系统篇 155 读取DOS系统中的国家信息 156 修改环境变量 157 显示系统文件表 158 显示目录内容 159 读取磁盘文件 160 删除目录树 161 定义...
  • 实例100使用指针实现数据交换, 实例101使用指针实现整数排序 实例102指向结构体变量的指针 实例103周指针实现逆序存放数组元素值 实例104输出二维数组的有关值 实例105输出二维数组任一行任一列值 实例106使用指针...
  • 本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...
  •  本书不仅可以作为计算机及相关专业本科生“数据结构”课程的教材,也可以作为研究生第一学年的“高等数据结构”课程的教材,同时,本书所介绍的各种算法的C语言实现,对有关专业人员也具有很好的参考价值。...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    9、 已知f为单链表的表头指针,链表中存储的都是整型数据,试写出实现下列运算的递归算法: a. 求链表中的最大整数; b. 求链表的结点个数; c. 求所有整数的平均数; 告要求: 写出能运行的完整...
  • 你们数据结构课有没有学动态规划? <p>B:可能有讲吧,但是我没什么印象了。 对话大概就是这样,虽然面试最终还是pass了,但这个问题确实让我很在意,因为我觉得,高度差...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 223
精华内容 89
关键字:

利用指针实现动态数据排序