线性表

发表于 | 分类于

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

概念

  1. 单链表：链表的每个结点只有一个指针域。

  2. 静态链表:

  3. 双向链表:

  4. 循环链表：首尾相接的链表。

  5. 循环单链表：单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点。

  6. 头指针：指向链表中第一个结点的指针。

  7. 头结点：链表的首元结点之前附近的一个结点；数据域内只放空表标志和表长等信息。作用:为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。

  8. 首元结点：指链表中存储线性表第一个数据元素a1的结点。

时间复杂度的分析

线性表类别 插入 删除 查找
顺序表 n/2-O(n) (n-1)/2-O(n)  
单链表 O(1) O(1) O(n)

顺序表操作

  1. 元素地址:

LOC(aj) = LOC(ai) + L*(j-i)

其中:LOC表示某个元素的地址，L表示每个元素占用的多少存储空间(字节)

单链表操作

  1. 删除核心代码:

     q = p->next;
 p->next = q->next;
 free(q);

  2. 插入核心代码:

     s->next = p->next;
 p->next = s;

  3. 头插法核心代码:

     L->next = NULL;
	
 while：
 {
 p->next = L->next;
 L->next = p;
 }

  4. 尾插法核心代码:

     L->next = NULL;
 r = L;
	
 while:
 {
 r->next = p;
 r = r->next;
 }