Skip to content

Chapter 02 线性表

1. 顺序表-向量

  • 采用定长的一维数组存储结构
  • 存储在连续空间, 读写方便
  • 使用常数作为向量长度, 程序运行时保持不变.

2.链表

  • 指针指向保持前驱关系，节点不必物理相邻
  • 动态申请/释放空间，长度动态变化（插入/删除）

分类:
- 单链表
- 双链表
- 循环链表

2.1 单链表

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
struct  ListNode

{

  ELEM  data；      //存放线性表结点的数据;

  ListNode * next;    //存放指向后继结点的指针；

 };

typedef  ListNode *  ListPtr;

ListPtr head, tail;     // head是分别指向单链表头、尾结点的指针；

Warning

单链表中的头节点(head指向的节点)不作为表中的实际元素, 值忽略.

访问时必须从 head 开始查找链表中的元素.

访问下标为 -1 则定位到头结点

Tips

1.由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上操作一致，无须进行特殊处理;

2.无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
//无头结点，须对i为0的插入位置作特殊处理

ListNode * Insert(int i, T value){

     if ( i==0){

         s = new ListNode;                               //生成新结点

         s->data = value; s->next = head;  // 插入到链表L中

         head = s;               // 修改链头指针L

    }else{

         ……（见27页）                              //同有头结点算法的处理;

    }

    return true;

}

单链表的不足: 仅有后继节点, 不能有效查找前驱.

2.2 双链表

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
struct  DblListNode

{

  T    data;

  DblListNode *prev;

  DblListNode *next;

};

注意插删时的操作顺序.

2.3 循环链表

将单链表或者双链表的头尾结点链接起来，就是一个循环链表。