精华内容
下载资源
问答
  • 数组链表

    2019-11-26 11:17:09
    我们拿一个长度为10的数组来举例,在下面的图中,计算机给数组分配了一块连续的内存空间,其中内存的首地址为base_address=1000。 每次获取数据的时候,计算机都会根据下面的寻址公式计算出元素存储的内存...
    数组
    一、基本概念
    1、什么数组?
    数组是一种线性表的数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。
    2、数组是如何实现下标随机访问数组元素的?
    我们拿一个长度为10的数组来举例,在下面的图中,计算机给数组分配了一块连续的内存空间,其中内存的首地址为base_address=1000。
     
    每次获取数据的时候,计算机都会根据下面的寻址公式计算出元素的存储的内存地址
    a[i]_address = base_address + i * data_type_size

     

     
    3、数组和链表的区别是什么?
    • 数组支持随机访问,链表不可以
    • 数组需要连续内存空间,链表是一组零散的内存块。
     
     
    4、数组的插入操作
    (1)假设数组的长度为n,现在,如果我们需要将一个数据插入到数组中的第K个位置,为了把第K个位置腾出来,给新来的数据,我们需要将第k~n的位置往后挪。
     
    如果在数组的末尾插入元素,那就不需要移动数据,此时的时间复杂度为O(1),而如果在数组的第一个位置插入元素,那么就要移动后面的n个元素,此时的时间复杂度为o(n),因为在任何位置插入元素的概率都是一样的,所以平均时间复杂度为O((1+2+3+4+...+n)/n) = O(n+1/2) = O(n)
     
     
    但是,如果我们的数组不要求有序的话,那么我们插入的时候只需要将第k个位置的元素放到最后,然后在k处插入我们的元素。此时时间复杂度为O(1)
     
     
    5、数组的删除操作
    如果要求数组是有序的话,那么时间复杂度和插入一样。
    下面来说说数组是无序的情况下。
    如果无序的时候,为避免元素移动,我们可以只将要被删除的元素删除,而不去搬移数据(比如js数组,可以置为null),当数组没有更多空间存储了,我们再去真正的删除操作,并且移动数组。
     
    6、需要时刻警惕数组的访问越界的问题。
     
    7、二维数组的寻址公式
    对于m*n的数组:
    a[i]_address = base_address + (i*n+j)*byte

     

     
    8、利用链表来实现LRU缓存策略(最近最少使用策略)(使用次数是有序的)
    利用一个有序数组,当有数据需要缓存的时候遍历数组
    1. 如果数据已经存在数组中了,则将此数据插入到数组头部,并将头部至数据原来位置的数据往后移一个位置。
    2. 如果数据不存在数组中,
    • 如果此时缓存已满,则将数组最后一个元素删除掉,把数组中所有数据往后移动,把数据插入到数组头部。
    • 如果此时缓存未满,则将数据插入到头部,然后所有数据往后移
     
     
     
     
    链表
     
    1、链表与数组的区别
    首先从底层的存储结构来看
     
    数组需要的是一块连续的内存空间来进行存储,如果计算机没有连续的足够大小的存储空间就会申请失败。而链表并不需要连续的内存空间,它通过指针,将一组零散的内存块串联起来。
     
    2、链表的结构
    链表中最常见的三种结构分别是单链表,双链表,循环链表。
    (1)单链表
    链表通过指针将一组零散的内存块串联起来,这里的内存块就是链表的结点,为了将所有的链表串联起来,每个链表的结点除了存储数据意外,还需要记录链上的下一个结点的地址,称为后继指针next
     
    单链表有两个很重要的结点,头结点和尾结点,一般链表指向的变量的就是头结点的地址,它记录着链表的基地址。而尾结点的next指向的是一个null空地址,代表链表已经没有后续结点了。
     
    链表的插入和删除都比较简单,因为它不用搬移后面的结点,但是找到需要插入位置的前继结点,需要根据指针一个一个结点依次遍历,直到找到相应的结点,所以它的插入和删除时间复杂度都是O(n)。
     
     
     
    (2)循环链表
    循环链表就是在单链表的基础上,尾结点的next不再指向null,而是指向头结点。
     
    (3)双向链表
    双向链表是在单链表的基础上,每个结点多了一个前继指针prev,指向前一个结点。
    双向链表比单链表多了一个存储空间,为什么我们还要用它呢?
    虽然插入操作中,双向链表跟单链表时一样的时间复杂度,但是在删除操作中,双向链表还是比单链表有优势的:
    从链表中删除一个数据无非就两种情况:
    • 删除结点中指定给定值的结点
    • 删除指定指针指向的结点
    第一种情况,两种链表的操作都差不多,主要是第二种,
    删除一个结点需要它的前继结点,因为需要修改它next指针指向的结点,如果是单链表,则还是需要遍历链表,判断结点的next是否指向特定的结点。但是双向链表,拥有prev,只要修改prev指向结点的next和next结点的prev就可以了。此时单链表的时间复杂度是O(n),而双向链表的时间复杂度是O(1)。
     
     
    双向链表主要的思想就是用空间换时间,当内存足够的时候,为了加快代码的执行速度,那么就可以选择空间复杂度相对较高,但是时间复杂度相对较低的算法或数据结构,否则相反。
     
    缓存实际上就是利用了空间换时间的设计思想。
     
     
    3、利用链表来实现LRU缓存策略(最近最少使用策略)
    利用一个有序的单链表,越靠近链表尾部的就是越早访问的,每次有新的数据访问的时候,就遍历一次链表,
    1. 如果此数据之前已经存在链表中了,那么就把这个结点在原来的位置删除并移到链表头部。
    2. 如果此前没有存在链表中:
    • 如果缓存未满,则将其插入链表头部。
    • 如果缓存已满,则将链表尾部的结点删除,将数据插入到链表头部。
     
    链表与数组性能
     
     
     
     
    链表代码书写技巧
     
     
    1、一定要警惕指针丢失和内存泄漏!比如留意指针的指向问题,删除的时候要对删除结点释放内存空间。
    2、针对链表的插入、删除操作,需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。为了解决这个问题,链表可以加一个头结点,head指针总是指向这个结点,因此这样的链表叫做带头链表。
     
     
    3、重点留意边界条件处理。
    • 如果链表为空,代码是否能正常工作
    • 如果链表只包含一个结点的时候,代码是否能正常工作
    • 如果链表只包含两个结点的时候,代码是否能正常工作
    • 代码逻辑在处理头结点和尾结点的时候,是否能正常工作。
     
    4、用js实现链表
    (1)单链表
    //初始化结点
    class Node{
        constructor(key){
            this.next = null
            this.key = key
        }
    }
    //初始化单链表
    class List{
        constructor(){
            this.head = null
            this.length = 0
        }
    
    
        //创建结点
         static createNode(key){
            return new  Node(key)
         }
    
    
         //往头部插入数据
         insert(node){
            if (this.head){
                //此时head有指向的结点
                node.next = this.head
            } else {
                node.next = null
            }
            this.head = node
            this.length++
         }
         //删除结点
         delete(node){
            //删除的结点时头结点指向的结点
             //删除的结点是尾结点
             //删除的结点时列表中间的结点
             if (node == this.head){
                 this.head = node.next
                 this.length --;
                 return;
             }
             let prev = this.head
             while (prev.next!=node){
                 prev = prev.next
             }
    
             if (node.next == null){
                 prev.next = null
             }
             if (node.next){
                 prev.next = node.next
             }
             this.length --;
         }
    }

     

     
    (2)双向链表
    //初始化结点
    class Node{
        constructor(key){
            this.next = null
            this.prev = null
            this.key = key
        }
    }
    
    //初始化链表
    class List{
        constructor(){
            this.head = null
            this.length = 0
        }
    
        //创建结点
         static createNode(key){
            return new  Node(key)
         }
    
         //往头部插入数据
         insert(node){
             node.next = this.head
             node.prev = null
            if (this.head){
                //此时head有指向的结点
                this.head.prev = node
            } else {
                node.next = null
            }
            this.head = node
            this.length++
         }
         //删除结点
         delete(node){
            //删除的结点时头结点指向的结点
             //删除的结点是尾结点
             //删除的结点时列表中间的结点
             if (this.head == node){
                 node.next.prev = null
                 this.head = node.next
                 this.length --
                 return
             }
    
             if (node.next){
                 node.prev.next = node.next
                 node.next.prev = node.prev
             }else {
                 //最后一个结点
                 node.prev.next = null
             }
         }
    }

     

     
    5、常见链表操作
    (1)单链表反转
     
    var reverseList = function(head) {
        //如果空链表或者链表只有一个结点就返回原来的链表
        if (head == null || head.next == null) {
            return head
        }
        //遍历链表,将当前结点与上一个结点进行交换,prev用来存储当前结点
       let prev = null,cur = head
      while (cur){
          let temp = cur.next
          cur.next = prev
          prev = cur
          cur = temp
      }
        return prev
    
    
    };

     

     
     
     
    算法题练习
     
    字符回文数判断
    回文判断(函数)
    编写一个函数int isPalindrome(char s[]),判断参数表示的字符串是否是回文,如果是返回1,否则返回0。在主函数中调用它,判断输入的字符串是否是回文,如果是,输出“yes”,如果不是,输出”No”。
    回文的定义:“回文数”就是正读倒读都一样的字符串
    输入
    测试数据的个数 t
    第一个字符串
    第二个字符串
    …….
    输出
    如果是,输出“yes”,如果不是,输出”No”
    样例输入
    3
    abba
    abcba
    ab
    样例输出
    Yes
    Yes
    No
    function huiwen(str) {
         if(str<0){
           return false
         }
         str +=''
        let length = str.length
        let t = length/2
        let flag = true
        for (let i=0;i<t;i++){
            console.log(str[i],str[length-i-1])
            if (str[i] != str[length-i-1]){
                flag = false
                break
            }
        }
        if (flag){
            console.log(str,'yes')
        } else {
            console.log(str,'no')
        }
    }
    huiwen(10)
    huiwen('abcba')
    huiwen('ab')

     

     
     
    空间复杂度O(1),空间复杂度看额外的内存消耗,而不是看数组本身存储需要多少空间!!
    时间复杂度O(n)
     
     
    展开全文
  • 单链表有一个头节点head,指向链表在内存的首地址链表中的每一个节点的数据类型为结构体类型,节点有两个成员:整型成员(实际需要保存的数据)和指向下一个结构体类型节点的指针即下一个节点的地址(事实上,此...

    链表:由一系列结点(链表中每一个元素称为结点)组成,每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
    在这里插入图片描述

    单链表

    单向链表简介

    单链表有一个头节点head,指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型,节点有两个成员:整型成员(实际需要保存的数据)和指向下一个结构体类型节点的指针即下一个节点的地址(事实上,此单链表是用于存放整型数据的动态数组)。链表按此结构对各节点的访问需从链表的头找起,后续节点的地址由当前节点给出。无论在表中访问那一个节点,都需要从链表的头开始,顺序向后查找。链表的尾节点由于无后续节点,其指针域为空,写作为NULL。

    如图所示
    在这里插入图片描述

    上图还给出这样一层含义,链表中的各节点在内存的存储地址不是连续的,其各节点的地址是在需要时向系统申请分配的,系统根据内存的当前情况,既可以连续分配地址,也可以跳跃式分配地址。
    ————————————————
    原文链接:https://blog.csdn.net/qq_33835307/article/details/82683475

    本节的基本思想

    本节主要用数组模拟链表,速度更快,并且为静态存储
    e[N] 存储节点的值,ne[N]存储该节点下一节点的下标
    注意:下标从零开始,第k 个数对应数组e[k - 1];在删除节点时,要判断该节点是否为头节点,若为头节点,直接head指向该节点所指向的位置,即head = ne[head];

    在这里插入图片描述
    1、将链表初始化,head指向-1
    2、将x插到头结点
    在这里插入图片描述
    3、在第k个数后面 插入x
    在这里插入图片描述
    4、删除第k个节点后面的数
    在这里插入图片描述

    基本模板
    来自yxc

    // head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点
    int head, e[N], ne[N], idx;
    
    // 初始化
    void init()
    {
        head = -1;
        idx = 0;
    }
    
    // 在链表头插入一个数a
    void insert(int a)
    {
        e[idx] = a, ne[idx] = head, head = idx ++ ;
    }
    
    // 将头结点删除,需要保证头结点存在
    void remove()
    {
        head = ne[head];
    }
    

    经典例题
    AcWing 826. 单链表

    实现一个单链表,链表初始为空,支持三种操作:

    (1) 向链表头插入一个数;

    (2) 删除第k个插入的数后面的数;

    (3) 在第k个插入的数后插入一个数

    现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表。

    注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。

    输入格式
    第一行包含整数M,表示操作次数。

    接下来M行,每行包含一个操作命令,操作命令可能为以下几种:

    (1) “H x”,表示向链表头插入一个数x。

    (2) “D k”,表示删除第k个输入的数后面的数(当k为0时,表示删除头结点)。

    (3) “I k x”,表示在第k个输入的数后面插入一个数x(此操作中k均大于0)。

    输出格式
    共一行,将整个链表从头到尾输出。

    数据范围
    1≤M≤100000
    所有操作保证合法。

    输入样例:

    10
    H 9
    I 1 1
    D 1
    D 0
    H 6
    I 3 6
    I 4 5
    I 4 5
    I 3 4
    D 6
    

    输出样例:

    6 4 6 5
    

    解答
    在这里插入图片描述

    在这里插入图片描述

    #include <iostream>
    
    using namespace std;
    
    const int N = 100010;
    
    
    // head 表示头结点的下标
    // e[i] 表示节点i的值
    // ne[i] 表示节点i的next指针是多少
    // idx 存储当前已经用到了哪个点
    int head, e[N], ne[N], idx;
    
    // 初始化
    void init()
    {
        head = -1;
        idx = 0;
    }
    
    // 将x插到头结点
    void add_to_head(int x)
    {
        e[idx] = x, ne[idx] = head, head = idx ++ ;
    }
    
    // 将x插到下标是k的点后面
    void add(int k, int x)
    {
       e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
    }
    
    // 将下标是k的点后面的点删掉
    void remove(int k)
    {
        ne[k] = ne[ne[k]];
    }
    
    int main()
    {
        int m;
        cin >> m;
    
        init();
    
        while (m -- )
        {
            int k, x;
            char op;
    
            cin >> op;
            if (op == 'H')
            {
                cin >> x;
                add_to_head(x);
            }
            else if (op == 'D')
            {
                cin >> k;
                if (!k) head = ne[head];//注意判断是否为头节点
                else remove(k - 1);//注意下标从0开始,所以为k - 1
            }
            else
            {
                cin >> k >> x;
                add(k - 1, x);
            }
        }
    
        for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
        cout << endl;
    
        return 0;
    }
    

    双链表

    双链表:每个节点有两个指针,一个指向前面,另一个指向后面
    来自

    e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
    1、初始化
    2、在节点a的右边插入一个数x
    注意:先将要插入的数左右指针分别指向对应位置
    然后先将原来第k个数右指针所指的位置的左指针指向x,即l[r[k]] = idx;

    3、删除节点a
    在这里插入图片描述
    上图来自洛克家族

    基本模板

    // e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
    int e[N], l[N], r[N], idx;
    
    // 初始化
    void init()
    {
        //0是左端点,1是右端点
        r[0] = 1, l[1] = 0;
        idx = 2;
    }
    
    // 在节点a的右边插入一个数x
    void insert(int a, int x)
    {
        e[idx] = x;
        l[idx] = a, r[idx] = r[a];
        l[r[a]] = idx, r[a] = idx ++ ;
    }
    
    // 删除节点a
    void remove(int a)
    {
        l[r[a]] = l[a];
        r[l[a]] = r[a];
    }
    
    作者:yxc
    链接:https://www.acwing.com/blog/content/404/
    来源:AcWing
    

    经典例题
    ACWing827. 双链表

    实现一个双链表,双链表初始为空,支持5种操作:

    (1) 在最左侧插入一个数;

    (2) 在最右侧插入一个数;

    (3) 将第k个插入的数删除;

    (4) 在第k个插入的数左侧插入一个数;

    (5) 在第k个插入的数右侧插入一个数

    现在要对该链表进行M次操作,进行完所有操作后,从左到右输出整个链表。

    注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。

    输入格式
    第一行包含整数M,表示操作次数。

    接下来M行,每行包含一个操作命令,操作命令可能为以下几种:

    (1) “L x”,表示在链表的最左端插入数x。

    (2) “R x”,表示在链表的最右端插入数x。

    (3) “D k”,表示将第k个插入的数删除。

    (4) “IL k x”,表示在第k个插入的数左侧插入一个数。

    (5) “IR k x”,表示在第k个插入的数右侧插入一个数。

    输出格式
    共一行,将整个链表从左到右输出。

    数据范围
    1≤M≤100000
    所有操作保证合法。

    输入样例:

    10
    R 7
    D 1
    L 3
    IL 2 10
    D 3
    IL 2 7
    L 8
    R 9
    IL 4 7
    IR 2 2
    

    输出样例:

    8 7 7 3 2 9
    

    解答
    在这里插入图片描述

    #include <iostream>
    
    using namespace std;
    
    const int N = 100010;
    
    int m;
    int e[N], l[N], r[N], idx;
    
    // 在节点a的右边插入一个数x
    void insert(int a, int x)
    {
        e[idx] = x;//新节点的值为x
        l[idx] = a;//新节点左指针指向节点a
        r[idx] = r[a];//新节点右指针指向a节点的右节点
        l[r[a]] = idx;//a节点的右节点的左指针指向新节点
        r[a] = idx ++ ;//a节点右指针指向新节点
    }
    
    // 删除节点a
    void remove(int a)
    {
        l[r[a]] = l[a];//a节点的右节点的左指针指向k节点的左节点
        r[l[a]] = r[a];//a节点的左节点的右指针指向k节点的右节点
    }
    
    int main()
    {
        cin >> m;
    
        // 0是左端点,1是右端点,初始化,第一个点的右边是 1   第二个点的左边是 0
        r[0] = 1, l[1] = 0;
        idx = 2;//因为1,0,已被征用
    
        while (m -- )//询问
        {
            string op;
            cin >> op;
            int k, x;
            if (op == "L")
            {
                cin >> x;
                insert(0, x);// 最左边插入就是在指向0的数的左边插入就可以了也就是可以直接在 0的 有右边插入
                //注意:!!!出错:添加头结点时应该直接在0号点的右侧添加,而不应该在r[0]的右侧添加
            }
            else if (op == "R")
            {
                cin >> x;
                insert(l[1], x);//在链表的最右端插入数x,0和 1 只是代表 头和尾  所以最右边插入只要在指向 1的那个点的右边插入就可以了
            }
            else if (op == "D")
            {
                cin >> k;
                remove(k + 1);//将第k个插入的数删除,k + 1为第k个插入的数的下标
            }
            else if (op == "IL")
            {
                cin >> k >> x;
                insert(l[k + 1], x);//在第k个插入的数左侧插入一个数,l[k + 1]为第k个插入的数的左节点
            }
            else
            {
                cin >> k >> x;
                insert(k + 1, x);//在第k个插入的数右侧插入一个数,因为初始化加了两个节点,所以第k个数的下标为k+2-1
            }
        }
    
        for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';//从头开始,当i!=tail时输出
        cout << endl;
    
        return 0;
    }
    
    展开全文
  • 计算机通过地址来访问内存中的数据,数组在内存中存放的是它的首地址,一维数组的寻址公式为。数组的基本操作查找数据:上面提到了数组支持随机访问,数组根据下标访问的时间复杂度为O(1);但是如果是要查找满足特定...

    1df88561ed8b82890953e7c9f9d2104b.png

    (一)数组

    定义

    数组是一种用一片连续的内存空间来存储一组相同类型的数据的线性表结构。

    “连续的内存空间”这个特点,决定了数组支持随机访问的特性。计算机通过地址来访问内存中的数据,数组在内存中存放的是它的首地址,一维数组的寻址公式为。

    数组的基本操作

    查找数据:上面提到了数组支持随机访问,数组根据下标访问的时间复杂度为O(1);但是如果是要查找满足特定条件的元素,那么我们需要遍历数组,时间复杂度为O(n)。所以说数组的查找操作时间复杂度为O(1)的说法是不准确的,准确来说应该是根据下标随机访问的时间复杂度为O(1)。

    插入数据:数组的插入数据在前面我们分析过,如果插入的元素在数组末尾,时间复杂度为O(1);如果数据插入中间的位置,时间复杂度为O(n),因为需要移动数据。平均情况时间复杂度为O(n)。当然,如果数组本身不是有序的,那么在中间插入数据时,我们可以选择让要插入的位置对应的元素放到数组的末尾,然后用要插入的数据替换该位置的元素的值,这样在数组中间插入数据的时间复杂度就为O(1)了。

    删除数据:如果要删除的数据是数组的最后一个元素,那么直接删除,时间复杂度为O(1);如果删除中间的元素,那么要将中间位置后面的元素依次往前移动一个位置,时间复杂度为O(n)。平均情况时间复杂度为O(n)。同上,如果数组不是有序的,我们可以用数组最末尾元素的值代替要删除位置的值,再删除最后一个元素,这样的时间复杂度也是O(1)。

    # _*_ coding:utf8 _*_
    
    

    数组与容器

    在很多编程语言中,针对数组类型会提供一个容器类将数组的多种操作封装起来,比如Python的list,C++中的vector等。容器跟数组相比起来,它有一个优势就是容器支持动态扩容。我们都知道数组我们在定义数组时就规定了数组的大小,一旦数据量超过数组本身的大小,那么我们就要为数组申请一块更大的空间并且将原来数组中的数据全部搬移到新数组中去,对于日常操作来说很繁琐。而容器类,在我们的数据量超过现有的空间时,我们不用关心底层相关的扩容逻辑,因为容器已经帮我们实现了。

    但是由于数据的搬移比较耗时,所以我们如果能够事先确定数据量的话尽量事先指定数据大小,这样减少了对数据搬移的时间消耗。

    (二) 链表

    定义

    链表是一种线性表结构,相比较数组,链表稍微复杂一点,链表不需要一组连续的内存空间,它通过指针将一组零散的内存空间连起来使用。因此一组数据存储在链表中消耗的内存要比数组多,因为需要指针存储下一个数据的地址,会产生额外的空间。

    单链表

    6e702525c4be1d331ac42d27549455cd.png

    双向链表

    f26e5e991c736d4ab630e559fab7e59f.png

    循环链表

    65cde2cee05a2c571748f68e63f2dc0a.png

    双向循环链表

    f33c28360e76a82cd911b842f31ee7ea.png

    链表的基本操作

    查找数据:链表要查找数据只能通过遍历的方式查找满足指定条件的数据,所以时间复杂度为O(n)。

    插入数据:链表插入数据,需要知道要插入的位置的前一个节点,然后用要插入的节点指向该节点的下一个节点,再用该节点指向新的要插入的节点就完成了。

    49bda191cb2c9f7412cb63a5f8e6b3a4.png

    删除数据:链表删除指定数据,只需要将指定数据的前一个节点指向它的下下个节点即可。

    4bbb1dccb34bbdeeae3c4e9fb5895fa1.png
    #_*_ coding:utf8 _*_
    
    
    

    应用

    1、缓存清理

    (三) 数组与链表对比

    数组与链表同为线性表结构,那么数组与链表在使用上的区别在哪里呢?

    数组适合查找,数组支持随机访问,根据下标随机访问的时间复杂度为O(1);链表则适合插入以及删除操作,插入与删除本身的时间复杂度为O(1)。

    数组与链表基础操作的时间复杂度对比

    563d1ac8f36d64dee3f723eb74d8ef1e.png

    数组与链表在内存中的优缺点

    数组在内存中是一块连续的内存空间,简单易用,访问效率更高;但是由于数组的大小固定,一经声明,便在内存中占用了一块空间,如果声明的空间过大,会造成大量的内存浪费,反之声明空间太小会导致频繁需要搬移数据造成更多耗时。

    链表将零散的内存空间串起来使用,本身没有大小限制,天然的支持动态扩容;然而虽然链表有效利用了零散的内存碎片,但是由于每个节点多出了存储指向下一个节点地址的指针,所以存储相同的数据,链表比起数组消耗更多的内存。同时,如果频繁的对链表进行删除和插入操作,会导致频繁的内存申请和释放,很容易产生内存碎片。

    展开全文
  • 计算机通过地址来访问内存中的数据,数组在内存中存放的是它的首地址,一维数组的寻址公式为。数组的基本操作查找数据:上面提到了数组支持随机访问,数组根据下标访问的时间复杂度为O(1);但是如果是要查找满足特定...

    f7542d6017b34af729d5439cbfbf873b.png

    (一)数组

    定义

    数组是一种用一片连续的内存空间来存储一组相同类型的数据的线性表结构。

    “连续的内存空间”这个特点,决定了数组支持随机访问的特性。计算机通过地址来访问内存中的数据,数组在内存中存放的是它的首地址,一维数组的寻址公式为。

    数组的基本操作

    查找数据:上面提到了数组支持随机访问,数组根据下标访问的时间复杂度为O(1);但是如果是要查找满足特定条件的元素,那么我们需要遍历数组,时间复杂度为O(n)。所以说数组的查找操作时间复杂度为O(1)的说法是不准确的,准确来说应该是根据下标随机访问的时间复杂度为O(1)。

    插入数据:数组的插入数据在前面我们分析过,如果插入的元素在数组末尾,时间复杂度为O(1);如果数据插入中间的位置,时间复杂度为O(n),因为需要移动数据。平均情况时间复杂度为O(n)。当然,如果数组本身不是有序的,那么在中间插入数据时,我们可以选择让要插入的位置对应的元素放到数组的末尾,然后用要插入的数据替换该位置的元素的值,这样在数组中间插入数据的时间复杂度就为O(1)了。

    删除数据:如果要删除的数据是数组的最后一个元素,那么直接删除,时间复杂度为O(1);如果删除中间的元素,那么要将中间位置后面的元素依次往前移动一个位置,时间复杂度为O(n)。平均情况时间复杂度为O(n)。同上,如果数组不是有序的,我们可以用数组最末尾元素的值代替要删除位置的值,再删除最后一个元素,这样的时间复杂度也是O(1)。

    # _*_ coding:utf8 _*_
    
    """
    创建一个int类型数组类,在类中封装数组的插入、删除、按下标随机访问等方法
    """
    
    
    class Array():
        def __init__(self):
            '''数组类初始化方法.'''
            self.__data = []  # 数据存储List
    
        def find(self, index):
            '''数组的查找方法.
    
            参数:
                index:将要查找的数据的下标
    
            返回:
                如果查找成功,则返回找到的数据
                如果查找失败,则返回False
            '''
            if index < len(self.__data):
                return self.__data[index]
            return False
    
        def delete(self, index):
            '''数组的删除方法.
    
            参数:
                index:将要删除的数据的下标
    
            返回:
                如果删除成功,则返回True
                如果删除失败,则返回False
            '''
            length = len(self.__data)
            if index >= length or index < 0:
                return False
            elif index == length - 1:
                self.__data.pop(-1)
                return True
            else:
                for i in range(index + 1, length):
                    self.__data[i - 1] = self.__data[i]
                self.__data.pop(-1)
                return True
    
        def insert(self, index, value):
            '''数组插入数据操作.
    
            参数:
                index:将要插入的下标
                value:将要插入的数据
    
            返回:
                如果插入成功,则返回True
                如果插入失败,则返回False
            '''
            if index < 0 or index > len(self.__data):
                return False
            else:
                self.__data.insert(index, value)
                return True
    
        def insertToTail(self, value):
            '''直接在数组尾部插入数据.
    
            参数:
                value:将要插入的数据
            '''
            self.__data.append(value)
    
        def printAll(self):
            '''打印当前数组所有数据'''
            print(self.__data)
    

    数组与容器

    在很多编程语言中,针对数组类型会提供一个容器类将数组的多种操作封装起来,比如Python的list,C++中的vector等。容器跟数组相比起来,它有一个优势就是容器支持动态扩容。我们都知道数组我们在定义数组时就规定了数组的大小,一旦数据量超过数组本身的大小,那么我们就要为数组申请一块更大的空间并且将原来数组中的数据全部搬移到新数组中去,对于日常操作来说很繁琐。而容器类,在我们的数据量超过现有的空间时,我们不用关心底层相关的扩容逻辑,因为容器已经帮我们实现了。

    但是由于数据的搬移比较耗时,所以我们如果能够事先确定数据量的话尽量事先指定数据大小,这样减少了对数据搬移的时间消耗。

    (二) 链表

    定义

    链表是一种线性表结构,相比较数组,链表稍微复杂一点,链表不需要一组连续的内存空间,它通过指针将一组零散的内存空间连起来使用。因此一组数据存储在链表中消耗的内存要比数组多,因为需要指针存储下一个数据的地址,会产生额外的空间。

    单链表

    c77c704af5aa6933d8cfdfba4ea60afd.png

    双向链表

    0b4e35ea3401720032c17b07588c8666.png

    循环链表

    6f686cdc5edbba8b84d94fe3fd072e43.png

    双向循环链表

    ca8528b4bc2563309acccba07e5207a7.png

    链表的基本操作

    查找数据:链表要查找数据只能通过遍历的方式查找满足指定条件的数据,所以时间复杂度为O(n)。

    插入数据:链表插入数据,需要知道要插入的位置的前一个节点,然后用要插入的节点指向该节点的下一个节点,再用该节点指向新的要插入的节点就完成了。

    3f54bd80ac8c6b16c492a0ea1fd2cec3.png

    删除数据:链表删除指定数据,只需要将指定数据的前一个节点指向它的下下个节点即可。

    1cf60f71e9322cc9144351b1562fc389.png
    #_*_ coding:utf8 _*_
    
    
    """
    创建一个存储int类型数据的单链表并完成单链表的增删查等基础操作;
    实现反转链表、判断是否有环等操作
    """
    
    class Node():
        '''链表结构的Node节点'''
        def __init__(self, val, next = None):
            '''Node节点的初始化方法.
            参数:
                val:存储的数据
                next:下一个Node节点的引用地址
            '''
            self.val = val
            self.next = next
    
    class SinglyLinkedList():
        '''单向链表'''
        def __init__(self):
            '''单向列表的初始化方法.'''
            self.head = None
    
        def findByValue(self, value):
            '''按照数据值在单向列表中查找.
            参数:
                value:查找的数据
            返回:
                Node
            '''
            if not self.head:
                return
            flag = self.head
            while flag:
                if flag.val == value:
                    return flag
                flag = flag.next
            return
    
        def findByIndex(self, index):
            '''按照索引值在列表中查找.
            参数:
                index:索引值
            返回:
                Node
            '''
            if index < 0 or self.head == None:
                return
            i = 0
            node = self.head
            while i <= index:
                node = node.next
            return node
    
        def insertNodeInTail(self, value):
            '''在链表的末尾插入一个存储value数据的Node节点.
            参数:
                value:将要存储在新Node节点中的数据
            '''
            node = Node(value)
            if not self.head:
                self.head = node
                return
            temp = self.head
            while temp.next:
                temp = temp.next
            temp.next = node
            return
    
        def insertNodeInHead(self, value):
            '''在链表的头部插入一个存储value数据的Node节点.
            参数:
                value:将要存储在新的Node节点中的数据
            '''
            node = Node(value)
            if not self.head:
                self.head = node
                return
            node.next = self.head
            self.head = node
            return
    
        def deleteByValue(self, value):
            '''在链表中删除指定存储数据的Node节点.
            参数:
                value:指定的存储数据
            '''
            if not self.head:
                return
            prev = self.head
            curr = self.head
            while curr:
                if curr.val == value:
                    prev.next = curr.next
                    return
                prev = curr
                curr = curr.next
            return
    
        def deleteByIndex(self, index):
            '''在链表中删除指定位置的Node节点.
            参数:
                index:索引值
            '''
            if index < 0 or self.head == None:
                return
            i = 0
            prev = self.head
            curr = self.head
            while i < index:
                if not curr:
                    return
                prev = curr
                curr = curr.next
                i += 1
            prev.next = curr.next
            return
    
        def printAll(self):
            node = self.head
            if not node:
                return
            while node.next:
                print(node.val , '->', end=' ')
                node = node.next
            print(node.val)
    

    应用

    1、缓存清理

    (三) 数组与链表对比

    数组与链表同为线性表结构,那么数组与链表在使用上的区别在哪里呢?

    数组适合查找,数组支持随机访问,根据下标随机访问的时间复杂度为O(1);链表则适合插入以及删除操作,插入与删除本身的时间复杂度为O(1)。

    数组与链表基础操作的时间复杂度对比

    3ecc6bfdf2c882373a56d21e91c23d30.png

    数组与链表在内存中的优缺点

    数组在内存中是一块连续的内存空间,简单易用,访问效率更高;但是由于数组的大小固定,一经声明,便在内存中占用了一块空间,如果声明的空间过大,会造成大量的内存浪费,反之声明空间太小会导致频繁需要搬移数据造成更多耗时。

    链表将零散的内存空间串起来使用,本身没有大小限制,天然的支持动态扩容;然而虽然链表有效利用了零散的内存碎片,但是由于每个节点多出了存储指向下一个节点地址的指针,所以存储相同的数据,链表比起数组消耗更多的内存。同时,如果频繁的对链表进行删除和插入操作,会导致频繁的内存申请和释放,很容易产生内存碎片。

    展开全文
  • 数组数组是在内存中存储相同数据类型的连续的空间 -----声明一个数组就是在内存空间中划出一串连续的空间1、数组名代表的是连续空间的首地址2、通过首地址可以依次访问数组所有元素3、元素数组中的排序叫做下标...
  • 所以,指针可以进行增量运算,而数组名(指向该数组的地址,即数组首元素的地址)不可以进行增量运算; 但在函数传参时,情况有所变化,将一个数组传入函数,函数会将形参的数组名退化成一个指针,此时,在函数内,...
  • 前言 线性表就是数据排成像一条线一样结构。每个线性表上数据最多只有前和后两个方向。其实除了数组链表、队列、栈等也是线性表结构。而与它相对立概念是非线性表,...即下标为i的元素地址=数组首地址+下标 i
  • 从数组存储的内存模型来看,数组的下标实际上指的是内存地址的偏移,假设用a表示数组的首地址,将数组元素的类型所占字节数计为type_size,那么a[k]表示的含义就是存储在内存空间k*typesize+base_addr处的元素,如果...
  • 线性结构[把所有结点用一个线穿起来] 连续存储[线性表(数组)] 什么叫数组元素类型相同,大小相等 确定一个数组需要几个参数?...数组的大小 ...数组首地址 数组的优缺点(相对于链表)? ...
  • 首地址数组是按照连接顺序存储的首地址,再开辟另一个数组用来存储排好序的首地址。 我们利用这几个数组就可以开始折腾了,首先遍历整个首地址数组,取出首地址对数据进行索引,判断数据大小即可。 在这里需要注意...
  • 数组最大长度、数组当前长度、指向数组的第一个元素地址的指针变量(数组的首地址) #include #include /* 定义了一个数据类型,该数据类型的名字叫做struct Arr */ struct Arr{ int * pBase;/
  • 算法基础之数组

    2020-05-23 02:20:50
    算法基础之数组 一、数组定义 数组是一种线性数据结构,每一个元素至多只有一个前驱和一个一个...那么对于数组任意元素只要知道相对首地址的偏移量,就可以从内存中获取到这个元素。计算方法如下num[i]_add =b
  • 链表

    2020-06-04 20:27:38
    数组的存储地址 = 数组的起始地址+偏移量 需要一个连续很大内存 不需要一个连续很大内存 专业术语: 头结点 头结点数据类型和节点类型是一模一样 头结点是节点前面那个节点 头结点并不存放...
  • 1、概念 数组(Array)是一种线性表数据结构。它用一组连续内存空间,来存储一组具有相同类型数据。...当前元素地址=数组首地址+元素字节大小∗数组下标当前元素地址=数组首地址+元素字节大小...
  • 1. 数组 数组是一种线性数据结构... 计算机随机访问数组某个元素时,通过下面寻址公式计算元素存储的的内存地址;若下标以1开始,则要进行一次(i -1)操作。 // 元素内存地址 = 首地址 + 偏移量 * 数...
  • 数据结构按照逻辑分类可以分为线性结构和非线性结构。 今天复习线性结构。线性结构就是把所有结点用一根直线穿起来,常用线性结构有:...定义:元素类型相同,占用空间大小相等(数组传参,只要传进去首地址和长
  • 在计算机中数组存储元素的地址,即基地址数组存储的变量都是统统数据类型,所以占用空间大小相同。所以,在查询数组的某个元素时只需要按照(基地址+偏移地址)进行查找。这个计算时间复杂度为0(1)...
  • 链表学习:静态链表

    2020-12-19 14:08:29
    链表的概念: 链表由一系列节点组成,其中每个节点包括两个域,一个是数据域,用来存储数据,另一个是指针域,用来存储下一个节点的地址,链表在内存中是非连续的 例如: struct LinkNode { int age;//定义数据域 ...
  • 数组 数组(Array)是一种线性表数据结构,用连续内存空间,存储相同类型数据 线性表 线性表(Linear List)数据是线性排列,每个线性表中数据...当我们需要访问到数组的某个位置的元素时,可以根据首地址
  • 数组和广义表 2021-1-16

    2021-01-16 14:37:36
    1-1 ...设有数组A[i,j],数组的每个元素长度为3字节,i值为1 到8 ,j值为1 到10,数组从内存首地址BA开始顺序存放,当用以行为主存放时,元素A[5,8]的存储首地址为 A.BA+141 B.BA+180 C.BA+222
  • 的存储结构

    2020-11-10 21:09:05
    根据这一特性,可以用一维数组来存储各个结点(一般按照层序存储),数组中一个元素对应树中一个结点,数组元素包括树中结点数据信息以及该结点双亲在数组中下标。有①双亲表示法和②带有兄弟双亲...
  • 定义 数组(Array)是一种线性表数据结构。它用一组连续内存空间,来存储一组具有相同类型数据。 线性表 顾名思义,线性表就是数据排成像一条线一样结构。...当计算机需要随机访问数组某个元素时,它会...
  • 数据的存储结构

    2020-06-29 09:15:29
    数组:查询快,增删慢(数组的地址是连续的,我们通过数组的首地址找到数组,通过索引可以快速的找到某个元素数组的长度是固定的,想要增加/删除一个元素,必须创建一个新数组,把源数组复制过来)。 链表:查询慢...
  • 有C语言实现链表的专题学习过程

    千次阅读 2007-11-13 20:37:00
    链表的专题研究:链表是一种重要的,动态的,数据存储结构.数组的特点是元素个数固定,不适合相对元素个数不固定的时候.虽然它用起来比较简单直观....链表有一个”头指针”指向这个链表的首地址,用来表示
  • 单向链表漫谈

    2020-03-28 22:17:49
    数组,一段地址连续内存,可以通过首地址加偏移量方式快速读写任意一个元素。但缺点也很明显,增加容量,增删元素的成本很高,均为 O(n)。 增加数组容量需要先申请一块新内存,然后复制原有的元素。如果需要...
  • 链表的形式【F】

    2020-05-25 23:53:12
    符号,之前我们都是通过数组名来获取第一个元素的首地址,但是,动态分配内存不给你名字,只是给你一块空地,当你离开的时候就找不到了,就像是我们去一个餐厅吃饭,如果对方告诉我们名字,我们就可
  • C语言链表基础入门

    2020-08-25 16:57:15
    每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。,链表结构可以充分利用计算机内存空间,实现灵活内存动态管理。但是链表失去了数组随机读取优点,同时链表由于增加了...
  • 插入删除元素效率高计算机术语头指针:存放头结点地址的指针变量头结点:数据类型和节点数据类型一模一样头结点是节点前面那个节点头结点并不存放有效数据设置头结点目的是为了方便对链表操作节点:存放...
  • 链表(Linked List)是不同于数组的另一种数据结构,它的存储单元(即结点或元素)除了包含任意类型数据之外,还需要包含指向另一个结点引用,后文会用术语链接表示对结点引用。 下面会列出链表数组的具体...

空空如也

空空如也

1 2 3 4 5 6
收藏数 104
精华内容 41
关键字:

数组元素存储链表的首地址