线性表的链式存储结构

线性表的链式存储结构定义

结点

结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

线性表的线性存储结构(也叫单链表)

n个结点链成一个链表，即为线性表的链式存储结构。

头结点

在单链表的第一个结点前附设一个头结点，头结点的数据域可以不存储任何数据，头结点的指针域存储指向第一个结点的指针，链表可以没有头结点。

头指针

头指针是链表指向第一个结点的指针，如果链表有头结点，头指针指向头结点。

空表

• 有头结点的空表，头指针指向头结点，头结点的指针域为空。
• 没有头结点的空表，头指针为空。

数组与链表对比

• 数组是内存上一段连续的存储空间
• 链表是内存上非连续，非顺序的存储空间(结构)。
• 数组是线性表的顺序存储结构
• 链表是线性表的链式存储结构

单链表的读取

获得链表第i个数据的方法，定义一个指针，从链表第一个数据开始遍历，不断指向下一个结点，直到第i个。

单链表的插入

• 单链表第i个数据插入结点s
  遍历链表寻找i-1结点，记为p结点。让原p的后继结点改成s的后继结点，s结点变成p的后继结点。
  s->next=p->next;
p->next=s;
• 伪代码

/* LinkList是链表类，ElemType是一种数据类型，ListInsert是单链表第i个数据插入结点的算法*/
void ListInsert(LinkList L,int i,ElemType e){
       LinkList p,s; //结点p、s
       p=L;//p结点是指向链表L第一个结点的指针
      //寻找第i-1个结点
      int j=1；
     while(j<i){//遍历寻找i-1个结点，让指针p指向它。只要j<i,指针p就向后移动，指向下一个结点，直到j=i;跳出循环，此时p指向第i-1结点。
      p=p->next;
     ++j;           
}
    定义结点s的值和插入位置
    s->data=e;//结点s的值是e
    p->next=s->next;//将p的后继结点赋值给s的后继
    p->next=s;//将s赋值给p的后继
}

• 图

  
  1.jpg
  2.jpg

单链表的删除

• 删除链表的第i个结点。
  遍历链表，寻找第i-1个结点，把i-1结点的后继改成i+1结点。

• 图

  
  微信图片_20180912214450.jpg
• 伪代码

/* LinkList是链表，ElemType是数据类型，ListDelete是删除链表第i个结点的方法*/
void ListDelete(LinkList L,int i,ElemType e){
    LinkList p,s;//
    p=L;//结点p是指向链表L第一个元素的指针
    int j=1;
   //遍历寻找第i-1个结点，指针p指向i-1结点
  while(j<i){
  p=p->next
  ++j;
  }
  //p的后继的后继结点赋值给p的后继
  p->next=p->next-next;

}

线性表的顺序存储结构与线性表的链式存储结构(单链表)分析

• 第i个位置插入或删除结点
  1.对于线性表的顺序存储结构，每一次插入结点或者删除结点，都需要移动n-i个结点。时间复杂度O(n)
  2.对于单链表，只需要赋值移动指针而已。时间复杂度O(1)
• 读取第i个位置的数据
  1. 顺序表的顺序存储结构，支持下标来访问元素，可以直接获取第i个元素，时间复杂度O(1)。
  2. 链表的链式存储结构，想要获取第i个数据，只能从第一个结点开始遍历,每次指针往后移动一次，最多需要移动n次才能获取第i个数据(i=n)。时间复杂度O(n)