线性表

基础

一个线性表示n个数据元素的有限集合。

顺序表

线性表的顺序表示,是用一组地址连续的存储单元依次存储线性表的数据元素。以元素在计算机内的“物理位置相邻”来表示线性表中数据元素之间的关系。 线性表中任一数据元素都可随机存取,所以线性表的顺序存储结构是一种随机存取的存储结构。一般使用数组描述数据结构。

创建

  1. 使用数组描述数据结构中的顺序存储结构,定义初始存储空间分配量和分配增量,结构体中定义基地址、长度、当前分配的存储空间。
  2. 申请内存空间,构造一个空的线性表。
  3. 定义空表长度为0.
  4. 定义初始存储空间。

插入

  1. 判断当前存储空间是否已满,满则增加分配。
  2. 在插入一个元素时,需要将插入位置后的所有元素向后移动一个位置。
  3. 表长+1。

删除

  1. 删除元素。
  2. 将被删除元素后的所有元素左移一个位置。
  3. 表长-1。

获取元素位置

找到返回元素的位序,若没有返回0。

合并

  1. 增加分配
  2. 插入元素
  3. 更改表长

缺点

在做插入或删除时,需要移动大量元素。

链表

线性表的链式表示。它不要求逻辑上相邻的两个元素在物理位置上也相邻,因此它没有顺序表的缺点,但是,它也失去了顺序表可随机存储的优点。

单向链表

单向链表需要一个头结点来表示开始。

头结点:在单向链表的第一个结点之前附设一个结点,它的数据域可以不存储任何信息,指针域指向第一个结点位置的指针。

单向链表的结点由数据域和指针域组成:

双向链表

双向链表的结点中有两个指针域,一个在前,另一个在后,中间的是数据域。它与单向链表不同的是,在一个结点中,它的一个指针域指向直接前驱,另一个指向直接后继。

循环链表

循环链表分有单循环链表和双循环链表。

单循环链表

单循环链表是由单向链表实现,它的特点是最后一个几点的指针域指向头结点,整个链表形成一个环。

单循环链表的操作和单向链表基本一致,差别仅在于算法中的循环条件不是P或P->next是否为空,而是他们是否等于头指针。

双循环链表

单循环链表是由双向链表实现,即最后一个结点的指针域指向第一个结点,其它操作基本与双向链表一致,判断条件与单循环链表一样。

Last Updated: 9/25/2019, 10:43:46 PM