精华内容
下载资源
问答
  • 线性表

    2019-06-16 14:13:47
    常见线性表包括: 线性表在逻辑上是线性结构,但在物理结构上不一定是连续的,线性表在物理存储时,通常以数组或链式结构进行存储 一.顺序表 顺序表:用数组存储数据的物理地址连续的线性结构,在数组上完成数据的增...

    线性表:n个具有相同特性的数据元素的有限队列

    常见线性表包括:

                                 

    线性表在逻辑上是线性结构,但在物理结构上不一定是连续的,线性表在物理存储时,通常以数组或链式结构进行存储

    一.顺序表

     顺序表:用数组存储数据的物理地址连续的线性结构,在数组上完成数据的增删改查

    接口实现:

    //在pos位置插入val
    boolean add(int pos,Object data);
    //查找关键字key 找到返回key的下标,没有返回null;
    int search(Object key);
    //查找是否包含关键字key是否在顺序表当中(这个和search有点冲突)
    boolean contains(Object key);
    //得到pos位置的值
    Object getPos(int pos);
    //删除第一次出现的关键字key
    Object remove(Object key);
    //得到顺序表的长度
    int size();
    //打印顺序表
    void display();
    //清空顺序表以防内存泄漏
    void clear();

    总结:

    • 中间/尾部插入的时间复杂度为O(n)
    • 增容需要申请空间,拷贝数据,释放旧空间,会与不小的消耗
    • 增容一般呈2倍增长,会浪费一定的空间

    二.链表

    链表:物理存储结构上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表的引用链接次序实现的 

    常用的的三种结构:

    1. 无头单向非循环链表:哈希桶,图的邻接表的子结构
    2. 带头循环单链表
    3. 不带头双向循环链表:LinkedList底层实现的就是这种结构

    接口实现:

    无头单向废循环链表实现

    // 1、无头单向非循环链表实现
    public interface ILinked {
    //头插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
    boolean addindex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);
    //删除第一次出现关键字为key的节点
    int remove(int key);
    //删除所有值为key的节点
    void removeAllKey(int key);
    //得到单链表的长度
    int getLength();
    void display();
    void clear();
    }

    带头循环链表实现

    //2、带头循环单链表实现
    public interface ICLinked {
    //头插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
    boolean addindex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);
    //删除第一次出现关键字为key的节点
    int remove(int key);
    //删除所有值为key的节点
    void removeAllKey(int key);
    //得到单链表的长度
    int getLength();
    void display();
    void clear();
    }

    不带头双向链表实现 

    // 3、不带头双向链表实现
    public interface IDoubleLinked {
    //头插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
    boolean addindex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);
    //删除第一次出现关键字为key的节点
    int remove(int key);
    //删除所有值为key的节点
    void removeAllKey(int key);
    //得到单链表的长度
    int getLength();
    void display();
    void clear();
    }

    三.顺序表和链表的区别与联系

    顺序表:一白遮全丑

    白:空间连续,支持随机访问

    丑:中间或前面部分的插入删除的时间复杂度为O(n),增容的代价大

    链表一胖毁所有

    胖:以结点为单位存储,不支持随机访问

    所有:任意位置插入或删除的时间复杂度为O(1),没有增容问题,插入一个开辟一个空间

    顺序表随机访问元素快,链表添加删除元素快 

    四.栈

    栈:一种特殊的线性表,只允许在表的一端进行插入和删除操作,进行数据插入和删除操作的一端叫栈顶,另一端叫栈底(先进后出)

     栈的实现:一般用数组或者链表实现,相对而言数组的结构更优一些,因为数组在尾插的代价比较小

    接口实现:

    interface MyStack {
    // 判断这个栈是否为空栈
    boolean empty();
    // 返回栈顶元素,但不出栈
    int peek();
    // 返回栈顶元素,并且出栈
    int pop();
    // 将 item 压入栈中
    void push(int item);
    // 返回元素个数
    int size();
    }

    五.队列 

    队列:一种特殊的线性表,只允许在一端进行数据的插入操作,另一端进行数据的删除操作,进行插入操作的一端叫队尾,进行删除操作的一端叫对头,(先进先出)

    队列的实现:队列也可以用数组或链表实现,使用链表的结构更优一些,因为如果使用数组结构,出队列在数组头上出数据,效率会比较低

    插入操作

     删除操作

    接口实现:

    interface IMyQueue {
    // 判断这个队列是否为空
    boolean empty();
    // 返回队首元素,但不出队列
    int peek();
    // 返回队首元素,并且出队列
    int poll();
    // 将 item 放入队列中
    void add(int item);
    // 返回元素个数
    int size();
    }

     

    展开全文
  • 线性表 什么是线性表?就是一种连续或间断存储的数组,这里的连续和间断是针对物理内存空间中线性表元素之间是否连续,其中连续数组对应内置数组的实现方式,间断数组对应的是指针的实现方式,这种方式也称为链表...
        
    原文是在我自己博客中,小伙伴也可以点阅读原文进行跳转查看,还有好听的背景音乐噢背景音乐已取消~ 2333333

    线性表

    什么是线性表?就是一种连续或间断存储的数组,这里的连续和间断是针对物理内存空间中线性表元素之间是否连续,其中连续数组对应内置数组的实现方式,间断数组对应的是指针的实现方式,这种方式也称为链表实现。

    也就是说,线性表有两种实现方式,一种是内置数组实现,另一种是链表实现。
    下面来看一下,有哪些数据结构属于线性表吧!

    栈(stack)

    特性

    • 先进后出
    • 只有唯一的一个出入口

    介绍

    栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

    通过上面的话语表达,相信不难理解栈的概念。下面我们上图感受一下栈和入栈出栈情况:

    栈

    上图中我们可以看到入栈、出栈的实际情况。只有一个入口(缺口),在这个缺口处,进行入栈和出栈操作。在现实生活中更形象的比喻就是垒砖。
    砖一次一次往上叠加,取的时候也是从最上部取,一直取到底部的最后一块。

    php实现

    php也可以实现简单的栈,由于php中没有提供很好的操作指针的方式,所以只能通过数组的方式实现。使用连个函数就可以,它们分别是 array_pusharray_pop

    1. array_push 将一个或多个单元压入数组的末尾(入栈);
    2. array_pop 弹出数组最后一个单元(出栈)

    简单代码示例:

    $arr = [];
    
    array_push($arr, 1); // $arr[] = 1;
    print_r($arr);
    sleep(1);
    
    array_push($arr, 2); // $arr[] = 2;
    print_r($arr);
    sleep(1);
    
    array_push($arr, 3); // $arr[] = 3;
    print_r($arr);
    sleep(1);
    
    $val = array_pop($arr);
    echo $val . "\n\n";
    print_r($arr);
    sleep(1);
    
    $val = array_pop($arr);
    echo $val . "\n\n";
    print_r($arr);

    把这段代码放在cli下跑,就能看到效果了,看一下运行gif图:

    入栈.gif

    从命令行的执行结果来看,我们先依次入栈1、2、3三个值,后来取出的时候,也是按照栈的先进后出,后进先出的特性出栈的。

    队列(queue)

    特性

    • 先进先出
    • 两个缺口,一入口,一个出口

    介绍

    队列(queue)是一种采用先进先出(FIFO)策略的抽象数据结构,它的想法来自于生活中排队的策略。在生活中比较形象的比喻就是排队了。

    队列

    php实现

    同样的,php中也可以以数组的形式实现队列,两个函数array_pusharray_shift

    • array_push 将一个或多个单元压入数组的末尾(入队);
    • array_shift 将数组开头的单元移出数组(出队)

    可以发现array_push和上面的栈入栈是同一个函数,其实两个函数的作用一样。用在这里就表示为入队了。

    简单代码示例:

    header("Content-type:text/html;charset=utf-8");  
    
    $arr = [];
    echo '入队-1 array_push($arr, 1)' . "\n";
    array_push($arr, 1); // $arr[] = 1;
    print_r($arr);
    sleep(1);
    echo '入队-2 array_push($arr, 2)' . "\n";
    array_push($arr, 2); // $arr[] = 2;
    print_r($arr);
    sleep(1);
    echo '入队-3 array_push($arr, 2)' . "\n";
    array_push($arr, 3); // $arr[] = 3;
    print_r($arr);
    sleep(1);
    
    echo '出队-3 array_shift($arr)' . "\n";
    $val = array_shift($arr);
    echo $val . "\n\n";
    print_r($arr);
    sleep(1);
    
    echo '出队-2 array_shift($arr)' . "\n";
    $val = array_shift($arr);
    echo $val . "\n\n";
    print_r($arr);

    图示:

    队列.gif

    从命令行的执行结果我们可以看到,我们依次入队 1、2、3三个值,出队的时候先出1,再出2.符合我们队列的特性,先进先出,后进后出。

    单链表

    特性

    • 由每一个节点组成
    • 每个节点中包含下一个节点的指针(*next)

    介绍

    单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据

    链表有两个比较重要的部分组成:

    1. 指针 指向下一个节点的地址,(即内存位置的直接地址)
    2. 节点 链表中的组成部分,对于单链表,一个节点里面包含节点数据和下一个节点的指针

    单向链表

    图中我们可以看到,单向链表由一个头指针、头节点、n个元素节点和尾节点组成。
    其中头指针代表,我们根据这个指针可以找到对应的链表
    头节点,用来存储链表的一些信息,比如链表长度,头节点指针指向第一个元素节点
    每个节点中又包括,节点数据(data)和指针(*next指向下一个元素节点)、
    一直到尾节点为null

    双向链表

    特性

    1. 同单链表类似由一个一个的节点组成
    2. 与单向链表不同的是,每个节点中包含了除数据(data)之外的上一个节点的指针(*prev)和下一个节点的指针(*next)

    介绍

    双向链表又叫做双链表;跟单向链表不同的是,他的每个节点都有两个指针,一个指向前面的一个节点,一个指向后面的节点。通过这两个指针我们可以很方便的通过某一个节点,访问到相(前)邻(后)的两个节点。

    我们来看一下,双向链表的图示:

    双向链表

    图中我们可以看到,除了头节点和尾节点之外,每个中间节点与节点之间都是首尾相连,每个节点保存了上一个节点的指针和下一个节点的指针,这就是与单链表的不同之处。

    注:我们也可以构造双向循环链表;尾节点的下一个指针*next指向头节点,而头节点的*prev指向尾节点;这样就构成了一个双向循环链表;下图所示,我们只需把双向链表简单改造一下即可:

    双向循环链表

    总结

    以上,就是本篇文章介绍的内容了。
    数据结构很多,也很高深,其中的算法知识,也让人回味无穷。

    展开全文
  • 数据结构——四种最常见线性表

    千次阅读 2017-12-14 18:59:18
    数组、链表、栈、队列是四种最常见线性表

    数据之间常见的逻辑结构包括线性结构、关联结构(集合、映射)、树形结构、图形结构.
    线性表是数据结构中最简单的基本数据结构.
    数组、链表、栈、队列是四种最常见的线性表.

    1.数组
    对数组的基本操作有查找、插入、删除. 数组元素的直接访问几乎没有开销,但是插入和删除操作需要移动数组元素,开销比较大,因此在插入和删除操作比较频繁的场合下,不适合用数组.
    在数组中查找一个元素的时间复杂度为O(n) 如果数组元素是有序存储的,则使用二分查找可以将时间复杂度降到O(lgn)

    例子:有若干个数存放在value数组中,这些数的取值范围是[1-100],请设计一个算法统计一下这些数中相同的数出现的次数.
    解析:虽然value中数字的个数很多,但是范围并不大,所以可以设计一个有100个元素的数组,数组元素的下标对应数字,数组元素的值就是对应数字出现的次数. 虽然哪些没有出现过的数字也需要占用数组中的一个位置,但是这点空间开销是可以接受的.

    2.链表
    链表结构的每个节点数据都由两个域组成,一个是存放实际数据元素的数据域,另一个就是构成链式结构的指针域.
    单向链表:指针域只有一个后向指针
    双向链表:指针域由一个后向指针和一个前向指针组成
    链表访问数据元素的效率比较低,需要从链表头部向后搜索,查找操作的时间复杂度为O(n).
    在某些应用场合,可以将链表尾部节点的后向指针指向链表头部节点,构成一个环形链表
    对环形链表来说,无论从哪个节点开始都可以遍历整个链表
    表头节点的作用域中放置一些与链表有关的状态信息. 比如当前链中的数据元素节点个数。表头结点的指针域始终指向第一个实际链表节点,如果表头节点的指针域是null,则表示这个链表是空表.
    使用表头节点的好处:
    1.无论链表是否为空表,始终有一个能表示链表的头结点
    2.对链表进行插入、删除、遍历操作时,不需要对数据元素的首节点和中间节点做差异处理

    3.栈
    站的数据存储方式可以采用数组或链表.分别被称为”顺序栈”和”链式栈”. 利用栈的一些特性,可以将某算法的递归实现转换成非递归实现. 有时,广度优先搜索和深度优先搜索的差异仅仅是使用栈还是使用队列.
    判断表达式的括号是否匹配算法,可以使用栈这种数据结构

    4.队列
    队列和栈一样,都不是数据存储方式,而是一种逻辑管理方式.
    队列的数据存储方式可以采用数组,也可以使用链表
    队列有多种形式:环形队列、双端队列、优先级队列.
    队列在算法中的应用:图的广度优先搜索算法、操作系统中的线程调度算法、管理数据报文的发送和接收

    展开全文
  • 1.线性表的的动态分配顺序存储结构#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 100 //线性表存储空间的分配增量 typedef struct { ElemType *elem; //存储空间基址 int ...

    1.线性表的的动态分配顺序存储结构

    #define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
    #define LISTINCREMENT 100   //线性表存储空间的分配增量
    typedef struct {
        ElemType *elem;     //存储空间基址
        int length;         //当前长度
        int size;           //当前分配的存储容量
    }SqList;    

    2.线性表的单链表存储结构

    typedef struct LNode{   //结点类型
        ElemType data;      //数据域
        struct LNode *next; //指针域
    }*Link;
    typedef struct {        //链表类型
        Link head, tail;    //分别指向线性链表的头结点和最后一个结点
        int len;            //指示线性链表中数据元素的个数
    }LinkList;

    头指针:指示链表中第一个结点的存储位置(LNode *类型)
    头结点:单链表的第一个结点前附设一个结点(数据域可存长度 LNode类型)
    首元结点:第一个结点

    3.线性表的静态单链表存储结构

    #define MAXSIZE 1000    //链表的最大长度
    typedef struct{
        ElemType data;
        int cur;
    }Component, SLinkList[MAXSIZE];

    需要用户自己实现malloc和free函数,将所有未使用过的和被删除的结点用游标链成一个备用链表

    4.线性表的双向链表存储结构

    typedef struct DulNode{
        ElemType data;
        struct DulNode *prior;
        struct DulNode *next;
    }*Dulink;
    typedef struct {        //链表类型
        Link head, tail;    //分别指向线性链表的头结点和最后一个结点
        int len;            //指示线性链表中数据元素的个数
    }DulinkList;
    展开全文
  • 线性表常见算法实现

    2019-09-07 20:25:00
    常见算法实现线性表 线性表 设计一个算法,将顺序表中所有的元素逆置。 设计一个算法,从一给定的顺序表L中删除下标i~j(i<=j,包括i,j)的所有元素,假定i,j都是合法的。 有一个顺序表L,其元素为整型...
  • 线性表之顺序表常见操作 增删改查,逆转等

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,054
精华内容 5,621
关键字:

常见的线性表