精华内容
下载资源
问答
  • 上次我们介绍了图关键路径算法实现,这次介绍查找这一章一个程序:顺序表和有序表(静态查找表)查找算法实现。还是老规矩:程序码云上可以下载。 地址:...

    上次我们介绍了图的关键路径算法的实现,这次介绍查找这一章的第一个程序:顺序表和有序表(静态查找表)查找算法的实现。

    还是老规矩:

    程序在码云上可以下载。
    地址:https://git.oschina.net/601345138/DataStructureCLanguage.git

    图这一章的程序做完以后,后面的程序就明显好做多了。

    这次的程序没啥好说的,就是顺序表每个数据元素加了一个关键字。其他操作差不多,仅此而已。

    关于顺序表的实现,可以参考:《 数据结构编程笔记三:第二章 线性表 顺序表的实现》,我就是拿这个程序改造之后变成了第九章的程序。

    直接看代码吧:

    //*********************引入头文件**********************************
    #include <stdio.h>
    #include <stdlib.h>  //使用了malloc、free函数 
    
    //********************自定义符号常量******************************** 
    
    #define OVERFLOW -2         //内存溢出错误常量
    #define ILLEGAL -1          //非法操作错误常量 
    #define OK 1                //表示操作正确的常量 
    #define ERROR 0             //表示操作错误的常量
    #define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
    #define EQ(a,b) ((a)==(b))  //相等 
    #define LT(a,b) ((a)< (b))  //小与
    #define LQ(a,b) ((a)<= (b)) //小与等于 
    
    //*********************自定义数据类型*******************************
    
    typedef int Status;   //状态码类型为int  
    typedef int KeyType;  //关键字类型为int 
    typedef struct{       //元素类型 
    
        //关键字域 
        KeyType key;
    }ElemType; 
    
    //------------------静态查找表的顺序存储结构------------------- 
    typedef struct{
    
        //数据元素存储空间基址,建表时按实际长度分配,0号单元留空
        ElemType *elem; 
    
        //表长度,表中记录数 
        int length;
    }SSTable;
    
    //**************************顺序表的主要操作************************* 
    
    //1.--------------------静态查找表的初始化操作---------------------------- 
    
    /*
        函数:InitSSTable_Seq
        参数:SSTable &ST 静态查找表引用 
        返回值:状态码,操作成功返回OK 
        作用:初始化静态查找表,构造一个空静态查找表
    */
    Status InitSSTable_Seq(SSTable &ST){
    
        //申请查找表内存空间,0号单元留空。
        ST.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType) + 1); 
    
        //若内存分配失败,退出程序
        if(!ST.elem){  
            printf("内存申请失败!\n");   
            exit(OVERFLOW); 
        }//if
    
        //设置静态查找表ST的长度为0
        ST.length = 0;
    
        //操作成功 
        return OK;    
    }//InitSSTable_Seq
    
    //2.----------------------输入静态查找表元素的操作-------------------
    
    /*
        函数:SSTableInput_Seq
        参数:SSTable &ST 静态查找表引用 
        返回值:状态码,操作成功返回OK 
        作用:顺序表插入元素的函数
    */
    Status SSTableInput_Seq(SSTable &ST) {
    
        //n代表元素的个数,i用作循环变量 
        int n, i;
    
        //直到用户输入正确为止 
        while(1){
    
            //先确定元素的个数
            printf("->您想输入几个元素,请输入个数,最多不可以超过100  "); 
            scanf("%d", &n);
    
            //检查元素个数n是否合法 
            if(n < 1 || n > 100) { 
    
                //如果输入非法数据,就提醒用户重新输入
                printf("您的输入非法,请重新输入!!!\n");
            }//if
    
            //若输入合法则退出循环 
            break;
        }//while
    
        //输入静态查找表数据
        printf("请输入静态查找表ST的元素,中间用空格隔开,最多不可以超过100个元素\n");
        for(i = 1; i <= n; i++) { 
    
            //初始化每一个元素
            scanf("%d", &ST.elem[i].key); 
        }//for 
    
        //静态查找表个数为元素个数n 
        ST.length = n;
    
        //操作成功 
        return OK;
    }//SSTableInput_Seq
    
    //3.------------------判断静态查找表是否为空-------------------
    
    /*
        函数:SSTableEmpty_Seq
        参数:SSTable ST 静态查找表ST 
        返回值:状态码,若静态查找表为空表返回TRUE,否则返回FALSE 
        作用:判断静态查找表是否为空 
    */
    Status SSTableEmpty_Seq(SSTable ST){
    
        //查看表长是否为0 
        return ST.length == 0;
    }//SSTableEmpty_Seq
    
    //4.----------------------静态查找表的输出操作------------------
    
    /*
        函数:Print
        参数:KeyType e 关键字的值e 
        返回值:状态码,操作成功返回OK,否则返回ERROR 
        作用:元素访问函数
    */
    Status Print(KeyType e){
    
        //采用控制台输出方式打印关键字e 
        printf("%3d ", e);
    
        //操作成功 
        return OK;
    }//Print
    
    /*
        函数:SSTableTraverse_Seq
        参数:SSTable ST 静态查找表ST 
              Status(* Visit)(KeyType) 函数指针,指向元素访问函数 
        返回值:状态码,操作成功返回OK,否则返回ERROR 
        作用:遍历静态查找表函数
    */
    Status SSTableTraverse_Seq(SSTable ST, Status(* Visit)(KeyType)){
    
        //访问静态查找表中每一个元素一次且仅一次 
        for(int i = 1; i <= ST.length; ++i) { 
    
            //一旦访问失败则遍历失败
            //if(!Visit(ST.elem[i].key)) <=> if(Visit(ST.elem[i].key) == ERROR)
            if(!Visit(ST.elem[i].key)) {
                return ERROR;
            }//if 
        }//for 
    
        //输出换行使结果美观 
        printf("\n");
    
        //操作成功 
        return OK;
    }//SSTableTraverse_Seq
    
    
    
    //5.----------------------顺序表的顺序查找算法------------------ 
    
    /*
        函数:SSTableTraverse_Seq
        参数:SSTable ST 静态查找表ST 
              KeyType key 被查找的关键字 
        返回值:若找到,则函数值为该元素在表中的位置,否则为0
        作用:在顺序表ST中顺序查找其关键字等于key的数据元素。
    */
    int Search_Seq(SSTable ST, KeyType key){
    
        //i是循环变量,存储了关键字在表中的位置 
        int i; 
    
        //0号单元不放被查找数据元素,放关键字,作用相当于"哨兵",
        //好处在于不必时时提防数组越界问题 
        ST.elem[0].key = key;
    
        //从后向前查找,直至找到元素或遇到哨兵为止 
        for(i = ST.length; !EQ(ST.elem[i].key, key); --i);
    
        //返回关键字在表中的位置i 
        return i;  
    }//Search_Seq 
    
    //6.-----------------------静态查找表的排序操作-------------------
    
    /*
        函数:SortSSTable_Seq
        参数:SSTable &ST 静态查找表引用 
        返回值:若找到,则函数值为该元素在表中的位置,否则为0
        作用:排序顺序表中元素,使顺序表变为有序表,以便于对有序表进行查找 
    */
    Status SortSSTable_Seq(SSTable &ST) {
        //将线性表中的元素排序,使用冒泡法,
        /*传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,
          我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法
          一次可以得到两个最终值(最大者和最小者),从而使排序趟数几乎减少了一半*/ 
    
        //对空表做排序没意义 
        if(SSTableEmpty_Seq(ST)) { 
            return ERROR; 
        }//if 
    
        int low = 1, high = ST.length, tmp, j;    
    
        while (low < high) {
    
            //正向冒泡,找到最大者 
            for (j = low; j < high; ++j) { 
                if (ST.elem[j].key > ST.elem[j + 1].key){  
                    tmp = ST.elem[j].key; 
                    ST.elem[j].key = ST.elem[j + 1].key;
                    ST.elem[j + 1].key = tmp;  
                }//if   
            }//for 
    
            //修改high值, 前移一位
            --high;
    
            //反向冒泡,找到最小者
            for (j = high; j > low; --j) {
                if (ST.elem[j].key < ST.elem[j - 1].key) {  
                    tmp = ST.elem[j].key; 
                    ST.elem[j].key = ST.elem[j - 1].key;
                    ST.elem[j - 1].key = tmp;  
                }//if
            }//for
    
            //修改low值,后移一位 
            ++low; 
        }//while  
    } //SortSSTable_Seq
    
    //7.----------------------有序表的折半查找算法------------------
    
    /*
        函数:Search_Bin
        参数:SSTable ST 静态查找表ST 
        返回值:若找到,则函数值为该元素在表中的位置,否则为0 
        作用:在有序表ST中折半查找其关键字等于key的数据元素
    */
    int Search_Bin(SSTable ST, KeyType key){
    
        //置区间初值
        int low = 1, high = ST.length, mid;
    
        //当low > high时查找结束 
        while(low <= high){
    
            //计算出mid 
            mid = (low + high) / 2;
    
            //找到待查元素
            if(EQ(key, ST.elem[mid].key)) {
                return mid;
            }//if
            //继续在前半区间进行查找 
            else if(LT(key,ST.elem[mid].key)) {
                high = mid - 1;
            }//else if 
            //继续在后半区间进行查找
            else { 
                low = mid + 1;
            }//else 
        }//while 
    
        //顺序表中不存在待查元素
        return 0; 
    }//Search_Bin 
    
    //8.-----------------------静态查找表的销毁操作--------------------
    
    /*
        函数:DestorySSTable_Seq
        参数:SSTable &ST 静态查找表引用 
        返回值:无 
        作用:销毁静态查找表ST
    */
    void DestorySSTable_Seq(SSTable &ST){
    
        //释放静态查找表内存空间 
        free(ST.elem);
    
        //指针置空 
        ST.elem = NULL;
    
        printf("内存空间释放成功!\n");  
    } //DestorySSTable_Seq
    
    //***************************************主函数******************************************** 
    int main(int argc,char *argv[]){ 
    
        //声明顺序查找表ST 
        SSTable ST; 
    
        //关键字         
        KeyType key;
    
        //状态标志
        Status flag;
    
        printf("\n***************************顺序表及有序表查找算法测试***************************\n");
    
        printf("->创建一个静态查找(顺序)表,请按要求进行操作\n"); 
        InitSSTable_Seq(ST);
        SSTableInput_Seq(ST);
        printf("->您创建的静态查找表包含的所有元素如下:\n");
        SSTableTraverse_Seq(ST, Print);
    
        printf("->请输入您想在顺序表中查找的元素:\n");
        scanf("%d", &key);
        flag=Search_Seq(ST, key); 
        if(!flag) { 
           printf("查找失败!\n"); 
        }//if 
        else {
           printf("查找成功!该元素在表中的位置为%d,表中该位置元素值为%d。\n",
                flag, ST.elem[flag].key);
        }//else
    
        printf("对顺序表排序,准备进行有序表查找。\n");
        SortSSTable_Seq(ST);
        printf("->排序后顺序表变为有序表,表中所有元素依次是:\n");
        SSTableTraverse_Seq(ST, Print);
    
        printf("->请输入您想在有序表中查找的元素:\n");
        scanf("%d", &key);
        flag=Search_Bin(ST, key); 
        if(!flag) {
           printf("查找失败!\n"); 
        }//if 
        else {
           printf("查找成功!该元素在表中的位置为%d,表中该位置元素值为%d。\n",
                flag, ST.elem[flag].key);
        }//else
    
        printf("->销毁静态查找表ST:");
        DestorySSTable_Seq(ST); 
    
        return 0;   
    }//main 

    输入数据来自书上P219页。

    程序运行时输出:

    ->创建一个静态查找(顺序)表,请按要求进行操作
    ->您想输入几个元素,请输入个数,最多不可以超过100  11
    请输入静态查找表ST的元素,中间用空格隔开,最多不可以超过100个元素
    05 13 19 21 37 56 64 75 80 88 92
    ->您创建的静态查找表包含的所有元素如下:
      5  13  19  21  37  56  64  75  80  88  92
    ->请输入您想在顺序表中查找的元素:
    12
    查找失败!
    对顺序表排序,准备进行有序表查找。
    ->排序后顺序表变为有序表,表中所有元素依次是:
      5  13  19  21  37  56  64  75  80  88  92
    ->请输入您想在有序表中查找的元素:
    88
    查找成功!该元素在表中的位置为10,表中该位置元素值为88。
    ->销毁静态查找表ST:内存空间释放成功!
    
    --------------------------------
    Process exited with return value 0
    Press any key to continue . . .

    总结:顺序表排序后变为有序表,查找效率有所提升。

    下次的文章会介绍动态查找表也就是二叉排序树的实现。感谢大家一直以来的关注和支持。再见!

    展开全文
  • 二、跳跃详解

    2019-01-07 12:19:27
    由 William Pugh 论文《Skip lists: a probabilistic alternative to balanced trees》中提出, 跳跃有序的方式层次化链表中保存元素, 效率和平衡树媲美 —— 查找、删除、添加等操作都可以对...

    跳跃表

    跳跃表(skiplist)是一种随机化的数据,其实就是给顺序单链表加了多个索引,高层次的索引跳跃节点数大于等于低层的,在。 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出, 跳跃表以有序的方式在层次化的链表中保存元素, 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成, 并且比起平衡树来说, 跳跃表的实现要简单直观得多。

    以下是个典型的跳跃表例子(图片来自维基百科):

    ../_images/skiplist.png

    从图中可以看到, 跳跃表主要由以下部分构成:

    • 表头(head):负责维护跳跃表的节点指针。
    • 跳跃表节点:保存着元素值,以及多个层。
    • 层:保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针,为了提高查找的效率,程序总是从高层先开始访问,然后随着元素值范围的缩小,慢慢降低层次。
    • 表尾:全部由 NULL 组成,表示跳跃表的末尾。

    因为跳跃表的定义可以在任何一本算法或数据结构的书中找到, 所以本章不介绍跳跃表的具体实现方式或者具体的算法, 而只介绍跳跃表在 Redis 的应用、核心数据结构和 API 。

    跳跃表的实现

    为了满足自身的功能需要, Redis 基于 William Pugh 论文中描述的跳跃表进行了以下修改:

    1. 允许重复的 score 值:多个不同的 member 的 score 值可以相同。
    2. 进行对比操作时,不仅要检查 score 值,还要检查 member :当 score 值可以重复时,单靠 score 值无法判断一个元素的身份,所以需要连 member 域都一并检查才行。
    3. 每个节点都带有一个高度为 1 层的后退指针,用于从表尾方向向表头方向迭代:当执行 ZREVRANGE 或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时,就会用到这个属性。

    这个修改版的跳跃表由 redis.h/zskiplist 结构定义:

    typedef struct zskiplist {
    
        // 头节点,尾节点
        struct zskiplistNode *header, *tail;
    
        // 节点数量
        unsigned long length;
    
        // 目前表内节点的最大层数
        int level;
    
    } zskiplist;
    

    跳跃表的节点由 redis.h/zskiplistNode 定义:

    typedef struct zskiplistNode {
    
        // member 对象
        robj *obj;
    
        // 分值
        double score;
    
        // 后退指针
        struct zskiplistNode *backward;
    
        // 层
        struct zskiplistLevel {
    
            // 前进指针
            struct zskiplistNode *forward;
    
            // 这个层跨越的节点数量
            unsigned int span;
    
        } level[];
    
    } zskiplistNode;
    

    以下是操作这两个数据结构的 API ,API 的用途与相应的算法复杂度:

    函数 作用 复杂度
    zslCreateNode 创建并返回一个新的跳跃表节点 最坏 O(1)O(1)
    zslFreeNode 释放给定的跳跃表节点 最坏 O(1)O(1)
    zslCreate 创建并初始化一个新的跳跃表 最坏 O(1)O(1)
    zslFree 释放给定的跳跃表 最坏 O(N)O(N)
    zslInsert 将一个包含给定 score 和 member 的新节点添加到跳跃表中 最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
    zslDeleteNode 删除给定的跳跃表节点 最坏 O(N)O(N)
    zslDelete 删除匹配给定 member 和 score 的元素 最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
    zslFirstInRange 找到跳跃表中第一个符合给定范围的元素 最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
    zslLastInRange 找到跳跃表中最后一个符合给定范围的元素 最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
    zslDeleteRangeByScore 删除 score 值在给定范围内的所有节点 最坏 O(N2)O(N2)
    zslDeleteRangeByRank 删除给定排序范围内的所有节点 最坏 O(N2)O(N2)
    zslGetRank 返回目标元素在有序集中的排位 最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
    zslGetElementByRank 根据给定排位,返回该排位上的元素节点 最坏 O(N)O(N) 平均 O(logN)O(log⁡N)

    跳跃表的应用

    和字典、链表或者字符串这几种在 Redis 中大量使用的数据结构不同, 跳跃表在 Redis 的唯一作用, 就是实现有序集数据类型。

    跳跃表将指向有序集的 score 值和 member 域的指针作为元素, 并以 score 值为索引, 对有序集元素进行排序。

    举个例子, 以下代码创建了一个带有 3 个元素的有序集:

    redis> ZADD s 6 x 10 y 15 z
    (integer) 3
    
    redis> ZRANGE s 0 -1 WITHSCORES
    1) "x"
    2) "6"
    3) "y"
    4) "10"
    5) "z"
    6) "15"
    

    在底层实现中, Redis 为 x 、 y 和 z 三个 member 分别创建了三个字符串, 值分别为 double 类型的 6 、 10 和 15 , 然后用跳跃表将这些指针有序地保存起来, 形成这样一个跳跃表:

    digraph zset {     rankdir = LR;      node [shape = record, style = filled];          edge [style = bold];      skiplist [label ="<head>zskipNode\n(head) |<3> |<2> |<1> |<score>score\n NULL |<robj>robj\n NULL", fillcolor = "#F2F2F2"];     six [label = "<head>zskipNode |<3> |<2> |<1> |<score>score\n 6 |<robj>robj\n x", fillcolor = "#95BBE3"];     ten [label = "<head>zskipNode | <1> |<score>score\n 10 |<robj>robj\n y", fillcolor = "#95BBE3"];     fiften [label = "<head>zskipNode |<3> |<2> |<1> |<score>score\n 15 |<robj>robj\n z", fillcolor = "#95BBE3"];      skiplist:3 -> six:3;      skiplist:2 -> six:2;     skiplist:1 -> six:1;     six:1 -> ten:1;     six:2 -> fiften:2;     six:3 -> fiften:3;     ten:1 -> fiften:1;      null_1 [label = "NULL", shape=plaintext];     null_2 [label = "NULL", shape=plaintext];     null_3 [label = "NULL", shape=plaintext];      fiften:1 -> null_1;     fiften:2 -> null_2;     fiften:3 -> null_3;  }

    为了方便展示, 在图片中我们直接将 member 和 score 值包含在表节点中, 但是在实际的定义中, 因为跳跃表要和另一个实现有序集的结构(字典)分享 member 和 score 值, 所以跳跃表只保存指向 member 和 score 的指针。 更详细的信息,请参考《有序集》章节。

    小结

    • 跳跃表是一种随机化数据结构,查找、添加、删除操作都可以在对数期望时间下完成。
    • 跳跃表目前在 Redis 的唯一作用,就是作为有序集类型的底层数据结构(之一,另一个构成有序集的结构是字典)。
    • 为了满足自身的需求,Redis 基于 William Pugh 论文中描述的跳跃表进行了修改,包括:
      1. score 值可重复。
      2. 对比一个元素需要同时检查它的 score 和 memeber 。
      3. 每个节点带有高度为 1 层的后退指针,用于从表尾方向向表头方向迭代。
    展开全文
  • 本期训练营采用分类别练习模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级题目,共计三道题,利用三时间完成这组刻意练习。...

    背景

    本篇图文是LSGO软件技术团队组织的 第二期基础算法(Leetcode)刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级的题目,共计三十道题,利用三十天的时间完成这组刻意练习。

    本次任务的知识点:数组

    数组 是在程序设计中,为了处理方便,把具有相同类型的若干元素按有序的形式组织起来的一种形式。抽象地讲,数组即是有限个类型相同的元素的有序序列。若将此序列命名,那么这个名称即为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素。而用于区分数组的各个元素的数字编号则被称为下标,若为此定义一个变量,即为下标变量。


    题目

    给定一个数组nums和一个值val,你需要原地移除所有数值等于val的元素,返回移除后数组的新长度。

    不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

    元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

    示例 1:

    给定 nums = [3,2,2,3], val = 3,
    
    函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
    
    你不需要考虑数组中超出新长度后面的元素。
    

    示例 2:

    给定 nums = [0,1,2,2,3,0,4,2], val = 2,
    
    函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
    
    注意这五个元素可为任意顺序。
    
    你不需要考虑数组中超出新长度后面的元素。
    

    示例 3:

    输入:[] value = 0
    
    输出:0
    

    示例 4:

    输入:[1] value = 1
    
    输出:0
    

    示例 5:

    输入:[4,5] value = 5
    
    输出:1
    

    说明:

    为什么返回数值是整数,但输出的答案是数组呢?

    请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

    你可以想象内部操作如下:

    // nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
    int len = removeElement(nums, val);
    
    // 在函数里修改输入数组对于调用者是可见的。
    // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }
    

    实现

    第一种:双指针法

    思路 利用双指针iji为慢指针拖后,j为快指针向前冲。如果nums[j]!=val,将num[j]的值赋给num[i],循环结束后,i指针前面的元素,即为需要保留的元素,从而达到了移除元素的目的,时间复杂度为 O(n)。

    • 执行结果:通过
    • 执行用时:272 ms, 在所有 C# 提交中击败了 94.41% 的用户
    • 内存消耗:29.9 MB, 在所有 C# 提交中击败了 5.21% 的用户
    public class Solution 
    {
        public int RemoveElement(int[] nums, int val) 
        {
            int i = 0;
            for (int j = 0; j < nums.Length; j++)
            {
                if (nums[j] != val)
                {
                    nums[i] = nums[j];
                        i++;
                }
            }
            return i;  
        }
    }
    

    Python 语言

    思路 利用Python语言中列表本身的特性。

    • 执行结果:通过
    • 执行用时:28 ms, 在所有 Python3 提交中击败了 96.72% 的用户
    • 内存消耗:13.4 MB, 在所有 Python3 提交中击败了 27.52% 的用户
    class Solution:
        def removeElement(self, nums: List[int], val: int) -> int:
            for i in range(len(nums) - 1, -1, -1):
                if nums[i] == val:
                    nums.pop(i)
            return len(nums)
    

    来源

    • https://leetcode-cn.com/problems/remove-element

    往期活动

    LSGO软件技术团队会定期开展提升编程技能的刻意练习活动,希望大家能够参与进来一起刻意练习,一起学习进步!


    我是 终身学习者“老马”,一个长期践行“结伴式学习”理念的 中年大叔

    我崇尚分享,渴望成长,于2010年创立了“LSGO软件技术团队”,并加入了国内著名的开源组织“Datawhale”,也是“Dre@mtech”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

    愿我们一起学习,一起进步,相互陪伴,共同成长。

    后台回复「搜搜搜」,随机获取电子资源!
    欢迎关注,请扫描二维码:

    展开全文
  • 定义:是最常用的,也是最简单的数据结构,是长度为n个数据元素的有序的序列。 含有大量记录的线性表叫文件 记录:稍微复杂的线性表里,数据元素为若干个数据项组成,这时把一个数据元素叫记录 结构特点:非空...

    线性表

    定义:是最常用的,也是最简单的数据结构,是长度为n个数据元素的有序的序列。

    含有大量记录的线性表叫文件

    记录:稍微复杂的线性表里,数据元素为若干个数据项组成,这时把一个数据元素叫记录

    结构特点:在非空有限的条件下,存在唯一的一个表头结点,唯一的一个表尾结点,除去第一个元素之外,每个数据元素都只有一个前驱,除去最后一个元素之外,每一个数据元素都只有一个后继。

    注意:线性表中的数据元素可以是各种各样的,但同一线性表中的元素必定具有相同特性(属于同一数据对象,类似数组)。线性表的数据元素间有序偶关系。

     

    线性表的顺序表示和实现

    有一组地址连续的内存单元,在这些连续的内存单元里,顺次地存储线性表里的数据元素

    特点:逻辑地址和物理地址都是连续的,适合随机存取。假设&a1为线性表的基址,每个数据元素占据L个存储单位。那么表里第i个元素的存储地址:

    &a(i) = &a(1) + (i - 1)x L

    线性表的顺序表示结构(顺序映象)也叫顺序表,顺序表中元素的逻辑关系和物理位置一致,是一种随机存取的存储结构。

    (类似高级语言里的数组,通常用数组描述数据结构的顺序存储结构)。

     

    如果用数组表示顺序表,那很简单,也不实用,不能改变存储容量,下面是动态分配的顺序表的表示和操作

    ADT.h头文件

     1 /************************************************************************/
     2 /* 功    能:声明常量和函数原型的头文件,线性表的动态分配顺序存储结构
     3 /* 作    者:dashuai
     4 /************************************************************************/
     5 #include <stdio.h>
     6 #include <stdlib.h>
     7 #define LIST_INIT_SIZE 100//线性表初始化存储空间分配
     8 #define LISTINCREMENT 10//线性表存储空间的分配增量
     9 
    10 typedef struct{//此时可以省去结构标记
    11     int *elem;//线性表基址
    12     int length;//当前表长
    13     int listsize;//当前为线性表分配的存储容量
    14 } SqList;//为结构起的别名SqList
    15 
    16 //线性表常用的有13个操作,归为4类
    17 
    18 /************************************************************************/
    19 /*第一类:初始化操作,记住各种数据结构开始使用都要初始化                */
    20 /************************************************************************/
    21 
    22 //1、线性表的初始化,构造一个空的线性表
    23 int InitList(SqList *L);//因为要改变线性表,必须用指针做参数
    24 
    25 /************************************************************************/
    26 /*第二类:销毁操作,记住各种数据结构使用了都要有销毁的步骤              */
    27 /************************************************************************/
    28 
    29 //2、销毁,释放内存操作
    30 void Destory(SqList *L);//直接把内存释放的操作!类似与free()
    31 
    32 /************************************************************************/
    33 /* 第三类:引用型操作,操作不改变线性表里的数据元素,也不改变他们之间的关系*/
    34 /************************************************************************/
    35 
    36 //3、判空操作,若线性表已经存在,为空白则返回true,否则返回false
    37 void ListEmpty(SqList L);
    38 
    39 //4、求长度操作,若线性表已经存在,则返回表L中元素个数
    40 int ListLength(SqList L);
    41 
    42 //5、定位操作:线性表 L 已存在,返回 L 中第 1 个与 e 满足相等关系的元素的位序。
    43 //若这种元素不存在,则返回 0。 
    44 int LocateElem(SqList L, int e);
    45 
    46 //6、求元素后继,初始条件:线性表 L 已存在。若 cur_e是 L 中的元素,则打印它的后继
    47 //否则操作失败
    48 void NextElem(SqList L, int cur_e);
    49 
    50 //7、得到指定的元素值,线性表 L 已存在
    51 //1≤i≤表长。用 e 返回 L 中第 i 个元素的值。 
    52 int GetElem(SqList L, int i, int e);
    53 
    54 //8、求元素前驱,线性表L已经存在,若cur_e是L的数据元素,则返回前驱
    55 //否则操作失败
    56 void PriorElem(SqList L, int cur_e);
    57 
    58 //9、遍历表中元素,线性表 L 已存在,打印出表中每个元素
    59 //无法遍历,则操作失败。 
    60 void ListTraverse(SqList L);
    61 
    62 /************************************************************************/
    63 /* 第四类:加工型操作                                                   */
    64 /************************************************************************/
    65 
    66 //10、把表清空(不释放内存):线性表 L 已存在,将 L 重置为空表。 
    67 void ClearList(SqList *L);
    68 
    69 //11、给表某元素赋值,线性表 L 已存在
    70 //L 中第 i 个元素赋值为 e 的值。 
    71 void PutElem(SqList *L, int i, int e );
    72 
    73 //12、插入操作,线性表 L 已存在,在 L 的第 i 个元素之前插入新的元素 e,L 的长度增 1。 
    74 void ListInsert(SqList *L, int i, int e );
    75 
    76 //13、删除操作,表 L 已存在且非空,。删除 L 的第 i 个元素,并用 e 返回其值,长度减 1。 
    77 void ListDelete(SqList *L, int i, int *e );
    78 
    79 /************************************************************************/
    80 /* 额外的几个复杂操作                                                   */
    81 /************************************************************************/
    82 
    83 //1、合并线性表AB,把在线性表B里,但不存在于线性表A的元素插入到A中
    84 //只改变A,不修改B
    85 void Union(SqList *LA, SqList LB);
    86 
    87 //2、合并线性表AB,AB的元素按值非递减有序的排列,要把A和B归并为一个新表C,且C的元素依然是按照值非递减的有序排列
    88 void MergeList(SqList LA, SqList LB, SqList *LC);
    89 
    90 //
    头文件

    ADTList.c文件

     1 /************************************************************************/
     2 /*函数定义在此文件                                                    */
     3 /************************************************************************/
     4 #include "ADT.h"
     5 /************************************************************************/
     6 /*第一类:初始化操作,记住各种数据结构开始使用都要初始化                */
     7 /************************************************************************/
     8 
     9 //注意c数组下标从0开始,但是用户并不知道,一般都是选择从1到length的位置,以用户的角度看问题
    10 
    11 //1、线性表的初始化,构造一个空的线性表,因为要改变线性表,必须用指针做参数
    12 int InitList(SqList *L)
    13 {
    14     //在堆中为线性表分配内存,初始化elem为该内存空间的首地址(基址)
    15     L->elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int));//结构里只是存储了表的地址值,而表本身存储在其他地方
    16     //判断是否分配成功
    17     if (!L->elem)//如果 !L->elem 为真(为空),执行下面代码
    18     {
    19         printf("线性表内存分配失败!退出程序。\n");
    20         exit(1);//函数异常退出,返回给操作系统1
    21     }
    22     //表内存空间分配成功
    23     L->length = 0;//开始是空表,没有存储任何元素,故表长置为0
    24     //当前为线性表分配的存储容量
    25     L->listsize = LIST_INIT_SIZE;//初始化表的存储容量,这是当前表最大的存储量
    26     return 0;//分配成功返回0
    27 }

    虽然在堆开辟了一块内存空间给线性表,但是需要设置一个变量listsize,来显式的表明表的最大存储容量的数值,方便程序使用(分配的空间内存大小和表长是两回事,表长是表内当前的元素个数,也就是此时线性表当前的存储容量)

     1 /************************************************************************/
     2 /*第二类:销毁操作,记住各种数据结构使用了都要有销毁的步骤              */
     3 /************************************************************************/
     4 
     5 //2、释放内存,销毁表操作,直接把内存释放的操作!类似free()和c++的delete操作符
     6 //注意:用malloc函数分配的空间在释放时是连续释放的,即将物理地址相邻的若干空间全部释放
     7 //所以顺序表销毁可以只释放基址,就自动释放所有空间,而链表要一个一个的把节点删除
     8 void Destory(SqList *L)
     9 {
    10     if (L->elem)//如果当前表还存在
    11     {
    12         free(L->elem);//销毁之
    13         //内存都没了,整个表也就不存在了,别的不用管。
    14         printf("本线性表已销毁!\n");
    15     }
    16 }
    注意:用malloc函数分配的空间在释放时是连续释放的,即将物理地址相邻的若干空间全部释放,所以顺序表销毁可以只释放基址自动释放所有空间,而链表要一个一个的把节点删除
     1 /************************************************************************/
     2 /* 第三类:引用型操作,操作不改变线性表里的数据元素,也不改变他们之间的关系
     3 /************************************************************************/
     4 
     5 //3、判空操作
     6 void ListEmpty(SqList L)
     7 {
     8     //判断表是否存在
     9     if (L.elem)
    10     {
    11         //判断是否存储了内容
    12         if (0 == L.length)
    13         {
    14             puts("本表为空!");//自动换行
    15         }
    16         else
    17         {
    18             puts("表不为空!");
    19         }
    20     }
    21     else
    22     {
    23         puts("表不存在!");
    24     }
    25 }

    0 == L.length,个人喜欢这种写法,避免出错,如果一时疏忽,写=,则编译报错!常量不能作为左值出现,来提醒自己

     1 //4、求长度操作,若线性表已经存在,则返回表L中元素个数
     2 int ListLength(SqList L)
     3 {
     4     if (L.elem)
     5     {
     6         return L.length;
     7     }
     8     puts("表不存在,无法求长度!");
     9     return 0;
    10 }

     

     1 //5、定位操作:线性表 L 已存在,返回 L 中第 1 个与 e 满足相等关系的元素位置。
     2 int LocateElem(SqList L, int e)
     3 {
     4     int i;//定位
     5     for (i = 0; i < L.length; i++)
     6     {
     7         //数组名本身就是数组的首地址
     8         if (e == L.elem[i] && i < L.length)
     9         {
    10             printf("定位成功,该元素的位置 = %d\n", i + 1);
    11             return i + 1;
    12         }
    13     }
    14     puts("定位失败!没有找到该元素");
    15     return 0;
    16 }

    个人觉得因为已经有初始化操作和判空操作,则其余函数不用再写判断表存在否的语句

    c的数组下标从0开始,但是还是习惯1对应第一个数据元素,以此类推……

    1、定位算法的时间复杂度分析

    假设表长为n

    最好的情况,如果第一个元素就满足关系,那么时间复杂度为0(1)

    最坏的情况,如果最后一个元素满足关系或者没有满足关系的(依然还是比较了),时间复杂度为0(n)

    2、算法平均时间复杂度:

    显然是和表长成正比的,为0(n)

     1 //6、求元素后继,线性表 L 已存在。若 cur_e是 L 中的元素,返回后继
     2 void NextElem(SqList L, int cur_e)
     3 {
     4     int i = LocateElem(L, cur_e);//先定位参照元素的位置
     5 
     6     if (0 != i)
     7     {
     8         if (i == L.length)
     9         {
    10             puts("这是最后一个元素,没有后继!");
    11         }
    12         else
    13         {
    14             printf("%d的后继是%d\n", L.elem[i - 1], L.elem[i]);
    15         }
    16     }
    17     else
    18     {
    19         puts("表中没有这个元素!");
    20     }
    21 }

    注意:区分数组角度看问题和用户角度看问题,表长范围等不要混淆。

     1 //7、得到指定的元素值,线性表 L 已存在, e 返回 L 中第 i 个元素的值。 
     2 int GetElem(SqList L, int i, int e)
     3 {
     4     if (i < 1 || i > L.length)
     5     {
     6         puts("超出了查找范围,重新输入!");
     7         return 0;
     8     }
     9     e = L.elem[i - 1];
    10     return e;
    11 }

    这里没有打印,只是返回了值,不太好,因为出现了一个问题,函数内部的e是局部变量,且是值传递参数类型,函数执行完毕,e的内存消失,不再起作用,对实参没有影响。在函数外打印e的值得不到正确值

     1 int GetElem(SqList L, int i, int *e)
     2 {
     3     if (i < 1 || i > L.length)
     4     {
     5         puts("超出了查找范围,重新输入!");
     6         return 0;
     7     }
     8     *e = L.elem[i - 1];
     9     printf("%d\n", *e);
    10     return *e;
    11 }

    改进:或者增加函数内的打印语句,或者把e变为指针类型的变量,可以修改实参,相应的声明里也要修改!

     

     1 /8、求元素前驱,线性表L已经存在,若cur_e是L的数据,则返回前驱
     2 void PriorElem(SqList L, int cur_e)
     3 {
     4     int i = LocateElem(L, cur_e);//如果定位失败返回0
     5 
     6     if (0 != i)
     7     {
     8         if (1 == i)
     9         {
    10             puts("这是第一个元素,没有前驱!");
    11         }
    12         else
    13         {
    14             printf("找到了%d的前驱%d \n",  L.elem[i - 1], L.elem[i - 2]);
    15         }
    16     } 
    17     else
    18     {
    19         puts("找不到这个元素!");
    20     }
    21 }

    注意一下: L.elem[i - 1]和 L.elem[i - 2]与i的关系

     1 //9、遍历表中元素,线性表 L 已存在,打印出表中每个元素 
     2 void ListTraverse(SqList L)
     3 {
     4     int i;
     5 
     6     for (i = 0; i < L.length; i++)
     7     {
     8         printf("%5d", L.elem[i]);
     9     }
    10 
    11 }

    %5d,宽度为5打印输出

     1 /************************************************************************/
     2 /* 第四类:加工型操作                                                   */
     3 /************************************************************************/
     4 
     5 //10、把表清空(不释放内存),线性表 L 已存在,将 L 重置为空表。 
     6 void ClearList(SqList *L)
     7 {
     8     if (L->elem)
     9     {
    10         L->length = 0;//顺序表置空,表长为0即可
    11     }
    12 }

    和销毁内存区分

     1 //11、给表元素赋值,线性表 L 已存在,1≤i≤LengthList(L)
     2 //L 中第 i 个元素赋值为 e  
     3 void PutElem(SqList *L, int i, int e )
     4 {
     5     if (i < 1 || i > L->length)
     6     {
     7         puts("超出表范围!");
     8     }
     9     L->elem[i - 1] = e;
    10 }

    常用的,也是比较重要的插入和删除算法

     1 //12、插入操作,线性表 L 已存在,1≤i≤LengthList(L)+1。在 L 的第 i 个元素之前插入新的元素 e,L 的长度增 1。 
     2 void ListInsert(SqList *L, int i, int e )
     3 {
     4     SqList *NL;//声明一个额外的结构指针指向重新分配的表内存空间
     5     int *j;
     6     int *k;
     7     //注意c数组下标从0开始,但是用户并不知道,一般都是选择从1到length的位置,以用户的角度看问题
     8     //在元素i之前插入,则把i和i后面的全部元素顺次后移一位
     9     if (i < 1 || i > L->length + 1)//最后一个元素后一位插入合法,不用移动直接插即可
    10     {
    11         puts("超出表范围!");
    12     }
    13     //考虑问题要全,因为可能会不止一次插入操作,早晚会超出表的存储容量
    14     else if (L->length >= L->listsize)
    15     {
    16         //重新分配内存,增加存储空间
    17         NL->elem = (int *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(int));
    18         if (!NL->elem)//分配失败,返回NULL
    19         {
    20             exit(0);//退出
    21         }
    22         //分配成功
    23         L->elem = NL->elem;//得到扩大之后的新基址
    24     }
    25     //指示用户的实际插入位置
    26     j = &(L->elem[i - 1]);//数组下标从0开始
    27     //最后一个数据元素的实际位置是length-1
    28     for (k = &(L->elem[L->length - 1]); k >= j; k--)//这里k--不是1的减量!而是指针的减量操作,每次是int类型字节大小变化
    29     {
    30         *(k + 1) = *k;//从j到k的元素顺次后移一位
    31     }
    32     *j = e;//完成插入
    33     L->length++;//别忘表长加1
    34 }

    1、需要注意一下运算符优先级,箭头(间接运算符)的优先级很高,高于取地址&

    2、解析realloc函数

    它可以对给定的指针所指的空间进行扩大或者缩小,原有内存的中内容将保持不变。对于缩小,则被缩小的那一部分的内容会丢失 ,realloc 并不保证调整后的内存空间和原来的内存空间保持同一内存地址。realloc 返回的指针很可能指向一个新的地址。因为realloc是从堆上分配内存,当扩大内存空间,realloc直接从堆上现存的数据后面的那些字节中获得附加的字节,但如果数据后字节不够,就用堆上第一个有足够大小的自由块,现存的数据被拷贝至新的位置,而老块则放回到堆上。

    在代码中,如果我们采用i = (int*)realloc(i, 2*sizeof(int))的重新分配内存方式,有以下两种情况:

    分配成功:
    realloc函数完成后,i 曾经指向的旧内存自动free掉。

    分配失败,返回NULL值:
    此时,i 原来指向的内存还没有被free掉,而现在又找不到地址,这样就出现memory leak!

    解决办法:定义另一个指针j用于接收realloc返回值,判断是否成功,成功则将 j 赋给 i

    3、插入算法的时间复杂度分析:

    问题规模是表的长度,值为 n。 算法的时间主要花费,在向后移动元素的 for 循环语句上。该语句的循环次数为 (n– i +1),所需移动结点的次数不仅依赖于表的长度 n,而且还与插入位置 i 有关。

    当插入位置在表尾 (i=n +1) 时,不需要移动任何元素;这是最好情况,其时间复杂度 O(1)。
    当插入位置在表头 (i = 1) 时,所有元素都要向后移动,循环语句执行 n 次,这是最坏情况,其时间复杂度 O(n)。
     
    4、插入算法的平均时间复杂度:
    设 pi 为第 i 个元素之前插入一个元素的概率,则在长度为 n 的线性表中插入一个元素时所需移动元素次数的期望值为 
    假设在n+1个位置上,插入的概率一样,那么pi = 1/(n+1);
    E = pi【(n)+(n-1)+ ……+ 3 + 2 + 1】 =pi x( n(n+1)/ 2) = n / 2
    由此可见,在顺序表上做插入运算,平均要移动

    一半元素。当表长 n 较大时,算法的效率相当低。

     

    插入

    算法的

    平均时间复杂度为 O(n)。

     
     1 //13、删除操作,表 L 已存在且非空,1≤i≤LengthList(L)。删除 L 的第 i 个元素,并用 e 返回其值,长度减 1。 
     2 void ListDelete(SqList *L, int i, int *e )
     3 {
     4     int *p;
     5 
     6     if (i < 1 || i > L->length)
     7     {
     8         puts("i的值不合法!重新输入!");
     9     } 
    10     else
    11     {
    12         //找到被删除元素的实际位置
    13         p = &(L->elem[i - 1]);
    14         *e = L->elem[i - 1];
    15         //p(不包含p)后面的元素依次前移一位
    16         for (; p < &(L->elem[L->length - 1]); p++)
    17         {
    18             *p = *(p + 1);
    19         }
    20         L->length--;
    21     }
    22 }

    1、这里e使用指针变量,这样形参就可以修改实参!

    2、删除算法的时间复杂度分析

    算法的时间主要花费在向前移动元素的 for 循环语句上。该语句的循环次数为 (n – i)。由此可看出,所需移动结点的次数不仅依赖于表的长度 n,而且还与删除位置 i 有关。

    当删除位置在表尾 (i = n) 时,不需要移动任何元素;这是最好情况,其时间复杂度 O(1)。
    当删除位置在表头 (i = 1) 时,有 n -1 个元素要向前移动,循环语句执行 n -1 次,这是最坏情况其时间复杂度 O(n)。
     
    3、算法的平均时间复杂度:
    设 qi 为删除第 i 个元素的概率,则在长度为 n 的线性表中删除一个元素时所需移动元素次数的期望值为
     
    假设,每一个位置的元素被删除的概率都一样,那么qi = 1 / n
    E = qi【(n-1)+(n-2)+……+3+2+1】=1/n x ((n-1)n / 2)=(n - 1)/ 2
    可见,在顺序表上做删除运算,平均也要移动表上

    一半元素。当表长 n 较大时,算法的效率相当低。算法的平

    均时间复杂度为 O(n)。 

     

     

     1 /************************************************************************/
     2 /* 额外的几个复杂操作                                                   */
     3 /************************************************************************/
     4 
     5 //1、合并线性表AB,把在线性表B里,但不存在于线性表A的元素插入到A中
     6 //只改变A,不修改B
     7 void Union(SqList *LA, SqList LB)
     8 {
     9     int i;
    10     int e;
    11     int lengthA = LA->length;
    12     int lengthB = LB.length;
    13 
    14     //在B里依次取得每个数据元素,顺序在A里比较,若不存在则插入
    15     for (i = 1; i <= lengthB; i++)
    16     {
    17         GetElem(LB, i, &e);
    18         if (!LocateElem(*LA, e))//A里没有这个元素
    19         {
    20             //插入到A尾部
    21             /*lengthA++;
    22             ListInsert(LA, lengthA, e);*/
    23             ListInsert(LA, ++lengthA, e);
    24         }
    25     }
    26     Destory(&LB);
    27 }

    算法复杂度分析:

    GetElem函数执行和表长没有关系,插入函数每次都在最后一位插入,执行时间和表长也没有关系,而LocateElem函数执行时间和表长有关系,无序合并算法的时间复杂度主要取决于LocateElem的执行时间,前面分析过,LocateElem时间复杂度:0(lengthA),那么本算法的时间复杂度为:O(lengthA x lengthB)

     

     1 //2、合并线性表AB,AB的元素按值非递减有序的排列,要把A和B归并为一个新表C,且C的元素依然是按照值非递减的有序排列
     2 void MergeList(SqList LA, SqList LB, SqList *LC)
     3 {
     4     InitList(LC);//构造新表c
     5     int lengthA = LA.length;
     6     int lengthB = LB.length;
     7     int lengthC = LC->length;//C表初始化为空表,0
     8     int i = 1;//i标记LA
     9     int j = 1;//j标记LB
    10     int iLA;
    11     int jLB;
    12 
    13     while ((i <= lengthA) && (j <= lengthB))
    14     {
    15         //分别取得元素值,比较
    16         GetElem(LA, i, &iLA);
    17         GetElem(LB, j, &jLB);
    18         if (iLA <= jLB)//LA,LB都是非递减排列
    19         {
    20             lengthC++;//总在末尾插入
    21             ListInsert(LC, lengthC, iLA);
    22             i++;
    23         }
    24         else
    25         {
    26             ListInsert(LC, ++lengthC, jLB);
    27             j++;
    28         }
    29     }
    30     //AB不会同时比完,一定会有一个表完全插入到c之后,另一表剩余
    31     while (i <= lengthA)
    32     {
    33         GetElem(LA, i++, &iLA);
    34         ListInsert(LC, ++lengthC, iLA);//本来AB就有序,直接全部插入到C末尾即可
    35     }
    36     //or
    37     while (j <= lengthB)
    38     {
    39         GetElem(LB, j++, &jLB);
    40         ListInsert(LC, ++lengthB, jLB);
    41     }
    42 }

    算法时间复杂度分析:

    不论表AB,哪个表,肯定有一个表先完全比完,比如是LA,比较了lengthA次。之后,两个while语句,就执行一个,就是LB剩余的元素顺次插入C表剩余次数的过程,加上之前LB和LA的比较次数,那么综合得其时间复杂度为0(lengthA + lengthB)

     

    本算法的另一种思路,不依靠前面已经定义好,能拿来就用的函数,使用指针进行比较,赋值

     1 //2、合并线性表AB,AB的元素按值非递减有序的排列,要把A和B归并为一个新表C,且C的元素依然是按照值非递减的有序排列
     2 void MergeList(SqList LA, SqList LB, SqList *LC)
     3 {
     4     //还是先构造表C,不用下标,只能使用指针来操作
     5     LC->listsize = LA.length + LB.length;
     6     LC->length = LA.length + LB.length;
     7     int *c = (int *)malloc((LC->listsize) * sizeof(int));
     8     int *a = LA.elem;
     9     int *b = LB.elem;
    10     int *lastA = LA.elem + (LA.length - 1) * sizeof(int);
    11     int *lastB = LB.elem + (LB.length - 1) * sizeof(int);
    12     LC->elem = c;
    13     if (!LC->elem)
    14     {
    15         puts("c表构建失败!");
    16         exit(-1);
    17     }
    18     while (a <= lastA && b <= lastB)
    19     {
    20         if (*a <= *b)
    21         {
    22             *c++ = *a++;//从右到左运算,先计算*c = *a,后a++,c++
    23         }
    24         else
    25         {
    26             *c++ = *b++;
    27         }
    28     }
    29     while (a <= lastA)
    30     {
    31         *c++ = *a++;
    32     }
    33     while (b <= lastB)
    34     {
    35         *c++ = *b++;
    36     }
    37 }

    1、时间复杂度还是0(lengthA + lengthB)

    2、这里发现,当线性表的元素无序的时候,进行插入操作的时间复杂度比有序的时候的时间复杂度要大的多。

    因为,有序的线性表AB,比如依次递增(都不相等),则比较AB元素大小时,不用把B的每一个元素都和A比较!因为可以保证前面的元素肯定是小于后面的。这样大大节省了运行时间!

    3、还有发现如果是两表归并到新表里,那么新表开始就是空的,只需要依次插入即可(换句话说就是依次赋值即可),不用移动元素,而如果是A归并到B里(反之亦然),那么保持有序的话,就需要B的元素时不时的移动,耽误时间。

    故,当使用线性表表示数组或者集合等等吧,进行操作的时候,最好是先给表排序,或者有归并,则归并到新的空表。

     

    到此,关于线性表里的顺序表的概念和常用算法就算分析完毕,经常用的操作的是初始化,销毁,清空,判空,定位,插入,删除,遍历,前驱,后继,赋值,得到元素,求长度,接下来分析的是经常用到的链表。

     

     

    转载于:https://www.cnblogs.com/kubixuesheng/p/4052912.html

    展开全文
  • 抽象地讲,数组即是有限类型相同的元素的有序序列。若将此序列命名,那么这名称即为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素。而用于区分数组的各个元素的数字编号则被
  • 十一章 关联容器

    2020-09-20 20:15:55
    map 基于红黑树实现(红黑树是一种自平衡二叉树,保障了良好最坏情况运行时间,可以O(log n)时间内完成查找...基于hash_table实现,一般是由一个大vector,vector元素节点可以挂接链表来实解决冲突来实现。 ...
  • 每次从无序表中取出第一个元素,将它插入到有序表中,使之成为新的有序表,重复n-1次完成整个排序过程。 时间复杂度 O(n^2) 步骤 从第一个元素开始,该元素可以认为已经被排序; 取出下一个元素已经排序的...
  • 1.直接插入排序 ...【3】如果A小于当前进行比较的有序表元素B,则将B有序表中往后移动一个位置,否则直接将A插入B之后; 【4】重复步骤【2】【3】直到无序表中所有元素插入到有序表中。 我是黑体字 我是微软...
  • 列如高考前每个班级排队照准考证,这个队伍就可以看做一个线性表,大家都井然有序的排着队,是一个有限序列,一个班就那么几个人,而且每个人之间都是有顺序,站错了顺序就不好核对信息。相对于广场上一群人...
  • 问题描述:假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个集合。 算法步骤: 依次取出Lb中每个元素,执行以下操作: ①La中查找该元素。 ②如果找不到,则将其插入到La最后。 【算法...
  • 本期训练营采用分类别练习模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级题目,共计三道题,利用三时间完成这组刻意练习。...
  • 本期训练营采用分类别练习模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级题目,共计三道题,利用三时间完成这组刻意练习。...
  • 本期训练营采用分类别练习模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级题目,共计三道题,利用三时间完成这组刻意练习。...
  • 插入排序就是将要排序表分成有序表和无序表两个部分,无序表中取一个元素在有序表中找到其位置,然后将其插入到有序表中。这样排序算法就是插入排序 一、插入排序分类 直接插入排序 折半插入排序 2-路...
  • 在一个使用有序链表描述的具有 n 个元素的字典中进行搜索,至多需进行 n 次比较。如果在链中部节点加一个指针,则比较次数可以减少到 n/ 2 + 1。搜索时,首先将欲搜索元素与中间元素进行比较。如果欲搜索的元素较小...
  • 2、数据元素位置上是有序排列的 3、数据元素的个数是有限的 4、数据元素的类型必须相同 二、线性表(List)的抽象定义 1、线性表是具有相同类型的n(>=0)数据元素的有限序列 {a0,a1,a2,....an-1} ai是...
  • 链式存储方式分析 优点:一定程度上对数组存储方式有优化(比如:插入一个数值节点,只需要将插入节点,链接到链表中即可, 删除效率也很好)。 缺点:进行检索时,效率仍然较低,比如(检索某个值,需要从头节点...
  • 排序 排序分为内排序和外排序 内排序三个重要指标 ...升序的情况下,相邻的两个元素比较,较大的交换到前面 ...升序的情况下,每一次遍历都...将一个元素插入到已经排好序的有序表中 时间复杂度O(n²) 性...
  • 集合类似于高级语言中的列表或一维数组,主要用来存储具有相同类型的元素的有序集合,每一个元素都有唯一的下标来标识当前元素集合中的位置。 PL/SQL中提供了如下三种类型的集合: - 索引:也称为关联数组,...
  • Queue实际上是实现了一个先进先出(FIFO:First In First Out)的有序表。它和List的区别在于,List可以任意位置添加和删除元素,而Queue只有两个操作: 把元素添加到队列末尾; 从队列头部取出元素。 超市...
  • 插入式排序基本思想是:对于一组元素,建立一个有序表一个无序表,在有序表中放一个元素,然后无序表中随意拿出一个元素,与有序表对照,找个位置放入,形成从小到大一组数。 具体程序是: public class...
  • 本期训练营采用分类别练习模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级题目,共计三道题,利用三时间完成这组刻意练习。...
  • 本期训练营采用分类别练习模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级题目,共计三道题,利用三时间完成这组刻意练习。...
  • 稀疏矩阵压缩存储

    2021-01-31 19:58:23
    稀疏矩阵:设mn矩阵中有t个非零元素。 令ζ=t/(mn) 当ζ<=0.05时称为稀疏矩阵。表示方法:三元组,十字链 三元组 ...十字链表中,矩阵一个非零元素一个节点表示,该节点除了(row,c
  • ()1.2_快速排序

    2019-02-07 14:34:20
    一.相关概念   快速排序(Quicksort)是对冒泡排序一种改进。   快速排序由C. A. R. Hoare1962年提出。它基本思想是:通过一趟排序将要排序数据分割成独立两部分,...我们首先把一个元素作为...

空空如也

空空如也

1 2 3 4
收藏数 71
精华内容 28
关键字:

在一个十元素的有序表