前沿

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

线性构造

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

线性构造次要分为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++则不会，所以要手动开释，否则会引起内存泄露。

致谢

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