关于c:链表和数组的比较

前沿

咱们如何把事实中大量简单的数据保留到主存储器 (内存) 中呢？为了解决这个问题，咱们出了数据结构的学科，专门钻研 —-个体的存储 + 个体关系的存储。所以当咱们要解决问题时，首先要先解决的是如何把这些问题转换成数据，先保留到咱们的主存中。

线性构造

什么是线性构造呢？就是把所有的结点用一根直线穿起来

线性构造次要分为 2 种

• 间断存储【数组】

  1. 什么叫数组？

     元素类型雷同，大小相等(数组传参，只有传进去首地址和长度就行)

  2. 数组的优缺点

     • 长处

       存取速度快

     • 毛病

       当时必须晓得数组的长度

       插入删除元素很慢

       空间通常是有限度的

       须要大块间断的存储块

       插入删除元素的效率很低

• 离散存储【链表】

  1. 定义：

     • n 个节点离散调配
     • 彼此通过指针相连
     • 每个节点只有一个前驱节点，每个节点只有一个后续节点
     • 首节点没有前驱节点，尾节点没有后续节点

数组和链表的排序

咱们来看个数组和链表排序的伪代码

// 数组排序
void sort_arr(struct Arr * pArr)
{
    int i, j, t;
    int len = length_list(pArr);

    for (i=0; i<len-1; ++i)
    {for (j=i+1; j<len; ++j)
        {if (pArr->pBase[i] > pArr->pBase[j])
            {t = pArr->pBase[i];
                pArr->pBase[i] = pArr->pBase[j];
                pArr->pBase[j] = t;
            }
        }
    }
}

// 链表排序
void sort_list(struct Arr * pHead)
{
    int i, j, t;
    int len = length_list(pHead);
    struct Arr * p, q;
    
    for (i=0,p=pHead->pNext; i<len-1; ++i,p=p->pNext)
    {for (j=i+1,q=p->pNext; j<len; ++j,q=q->pNext)
        {if (p->data > q->data)  // 等价于  a[i] > a[j]
            {t = p->data;// 等价于:  t = a[i];
                p->data = q->data; // 等价于:  a[i] = a[j];
                q->data = t; // 等价于:  a[j] = t;
            }
        }
    }

    return;
}

在咱们看来数组和链表的存储形式是不同的

数组能够有 a[++i] 来指向下个元素

链表则是 p = p->next 来指向下个元素

但从狭义上来说 算法说与数据的存储形式无关的，咱们能够对链表进行一个封装也能够实现 a[++i]指向下个元素的操作。不同的存储形式，达到操作形式是雷同的。

动静分配内存

当咱们要创立一个节点的时候，就须要动静来分配内存

int main(void) 
{

    int p;
    int *m = (int*)malloc(100);
}

在代码中动态变量 p 是在栈中调配，有操作系统主动调配和开释，而 (int*)malloc(100)执行之后将在堆中调配 100 字节的内存。这个操作系统并不会开释，必须要手动应用 free() 来开释内存。java 中变成垃圾内存则会主动开释，然而 C 和 C ++ 则不会，所以要手动开释，否则会引起内存泄露。

致谢

感激你看完这篇文章，有什么不对的中央欢送指出，谢谢????