乐趣区

关于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 ++ 则不会,所以要手动开释,否则会引起内存泄露。

致谢

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

退出移动版