数据结构笔记--线性表(下)

2.2.3 链表(线性表的链式存储结构)

链表: 用一组任意的存储单元来存储线性表中的数据元素,并用指针域实现逻辑上相邻的关系
特点:

• 链表中的结点的逻辑顺序和物理顺序不一定相同.
• 每个结点$a_i$,除存储本身信息外,还需存储$a_{i+1}$的位置的信息
• 结点结构的组成:
  
  • 数据域: 元素本身信息
  • 指针域: 指示直接后继的存储位置
• 是一种动态结构,不需要预先分配空间
• 指针占用额外的存储空间
• 不能随机存取,查找速度慢

相关术语:

• 链表是由表头唯一确定,因此可以用头指针的名字来命名链表.
• 单链表 每个结点只包含一个指针域的链表
• 头结点(head) 在第一个结点之前附设一个结点(也即头指针,它指向第一个结点)

• 判断一个链表是否为空的条件有以下两种情况:

  • 若此链表 有 头结点,条件为 head->next==NULL
  • 若此链表 没有 头结点,条件为 firstNode==NULL

• 单链表的结点示意图

typedef int Type;
typedef struct node_s
{
   Type data;
   struct node_s* next;
};

• 结点的赋值

node_t* p = calloc(1,sizeof(node_t));    // p ──> ┌─────┬───┐
p->data=20;                              //       │ 20  │ ^ │
p->next = NULL;                          //       └─────┴───┘

• 常见的指针操作

操作前                                     操作后
//---------------------------------------------------------------------
(1) q=p;
//  p ──> ┌───┬─┐                |   p ──> ┌───┬─┐
//  ...──>│ a │ ┼──>...          |   ...──>│ a │ ┼──>...
//        └───┴─┘                |   q ──> └───┴─┘
//---------------------------------------------------------------------
(2) q=p->next;
//  p ──> ┌───┬─┐  ┌───┬─┐       |   p ──> ┌───┬─┐  q ──> ┌───┬─┐
//  ...──>│ a │ ┼─>│ b │ ┼──>... |   ...──>│ a │ ┼───────>│ b │ ┼──>...
//        └───┴─┘  └───┴─┘       |         └───┴─┘        └───┴─┘
//---------------------------------------------------------------------
(3) p=p->next;
//  p ──> ┌───┬─┐  ┌───┬─┐       |         ┌───┬─┐  p ──> ┌───┬─┐
//  ...──>│ a │ ┼─>│ b │ ┼──>... |   ...──>│ a │ ┼───────>│ b │ ┼──>...
//        └───┴─┘  └───┴─┘       |         └───┴─┘        └───┴─┘
//---------------------------------------------------------------------
(4) p->next=q;
//      q ──> ┌───┬─┐            |              q ──> ┌───┬─┐
//            │ c │ ┼─>...       |                 ┌─>│ c │ ┼─>...
//            └───┴─┘            |                 │  └───┴─┘
//  p ──> ┌───┬─┐  ┌───┬─┐       |   p ──> ┌───┬─┐ │  ┌───┬─┐
//  ...──>│ a │ ┼─>│ b │ ┼──>... |   ...──>│ a │ ┼─┘  │ b │ ┼──>...
//        └───┴─┘  └───┴─┘       |         └───┴─┘    └───┴─┘
//---------------------------------------------------------------------
(5) p->next=q->next;
//  q ──> ┌───┬─┐  ┌───┬─┐       |   q ──> ┌───┬─┐    ┌───┬─┐
//  ...──>│ x │ ┼─>│ y │ ┼──>... |   ...──>│ x │ ┼───>│ y │ ┼──>...
//        └───┴─┘  └───┴─┘       |         └───┴─┘ ┌─>└───┴─┘
//  p ──> ┌───┬─┐  ┌───┬─┐       |   p ──> ┌───┬─┐ │  ┌───┬─┐
//  ...──>│ a │ ┼─>│ b │ ┼──>... |   ...──>│ a │ ┼─┘  │ b │ ┼──>...
//        └───┴─┘  └───┴─┘       |         └───┴─┘    └───┴─┘
//---------------------------------------------------------------------

• 单链表的基本操作的描述
  
  1. 建立单链表
     
     • 头插法
       每次插入的结点都作为链表的第一个结点
     • 尾插法
       每次插入的结点都作为链表的最后一个结点

2.2.4 单链表的 C++ 实现

待写