线性表 Linear List

线性表的基本概念

• 线性表是具有相同数据类型的n(n>=0)个数据元素组成的有序数列
• 线性表的第一个元素成为表头节点，最后一个元素称为表尾节点

线性表的存储结构

线性表的存储结构有两种表示方式:

• 顺序存储结构
• 链式存储结构

顺序存储结构

存储特点

用一段地址连续的存储单元

依次存储线性表中的数据元素

如何描述顺序表

• 存储空间的起始位置
• 顺序表的容量(最大长度)
• 顺序表的当前长度

Tips
存储结构和存取结构
- 存储结构是数据及其逻辑结构在计算机中的表示
- 存取结构是在一个数据结构上对查找操作的时间性能的一种描述

• 顺序表是一种随机存取的存储结构
  • 含义：在顺序表这种结构上进行的查找操作，时间性能为O(1)

顺序表的优缺点

• 顺序表的优点

  • 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；
  • 随机存取：可以快速地存取表中任一位置的数据元素 (Data Element)；

• 顺序表的缺点

  • 插入和删除操作需要移动大量元素；
  • 表的容量难以确定，表的容量难以扩充；
  • 造成存储空间的“碎片”；

方法	时间复杂度
查找	O(1)
插入/删除	O(n)

链式存储结构

链表分类

• 线性链表
  • 单链表 Single Linked List
• 循环链表Circular Linked List
• 双向链表Doubly Linked List

存储特点

逻辑次序和物理次序不一定相同

元素之间的逻辑关系用指针表示

链表Linked List图示

单链表的存储结构

• 单链表是由若干节点node构成的
• 单链表的节点只有一个指针域

单链表的操作算法

定义一个通用链表节点struct Node

• 能存放任意类型的数据 T，并且用 next 指针把节点连接成链表

template <typename T>
struct Node {
	T data;          // 节点里存储的数据，类型是 T
	Node<T>* next;   // 指针，指向下一个同类型节点
};

定义模板类LinkList

• 声明私有成员变量（private 表示只能在类内部访问）：

  • Node<T>* head; ：指向头节点的指针，用来管理整个链表
  • int length; ：记录链表长度（有多少个数据元素）

• 声明公有成员函数（外部可以访问）：

  • LinkList(); ：构造函数（无参），创建一个空链表
  • LinkList(T a[], int n); ：构造函数（带参数），用数组 a 和长度 n 来初始化链表

template <typename T>
class LinkList {     //定义模板类 LinkList
	private:   //私有成员变量
		Node<T>* head;    //定义指向头节点的指针
		int length;    //记录链表长度

	public:    //公有成员函数
		LinkList(); //构造函数（无参），创建一个空链表
		LinkList(T a[], int n); //构造函数（带参数），用数组 `a` 和长度 `n` 来初始化链表
		T  Get(int pos); //按位查找
		int Locate(T item); //按值查找
};

无参构造函数

• 操作接口: LinkList()
• 创建一个仅带一个头节点的空链表
• 算法描述:

template <typename T>
LinkList<T> ::LinkList() {
	head = new Node<T>;
	head->next = NULL; //创建一个带头节点的空链表
};

有参构造函数

• 操作接口: LinkList(T a[], int n)

• 操作方法:

  • 头插法: 将待插入节点插在头节点后面

    算法描述:

    s = new Node<T>;  //新建一个节点
    s->data = a[1];  //放入data
    s->next = head->next;  //连接后面节点(图1.)
    head->next = s;   //将头节点指向新节点(图2.)

    

  • 尾插法: 将待插入节点插在终端节点后面

    (1) 初始化

    算法描述:

    head = new Node<T>; 
    Node<T>* r = head; //定义一个尾指针r，初始时指向头结点

    

    (2) 插入

    算法描述:

    s = new Node<T>; 
    s->data = a[0];
    r->next = s; //将头节点的指针指向s
    r = s;  //将s定义为尾指针

    

• 算法描述:

  template <typename T>
  LinkList<T> ::LinkList(T a[], int n) {
  	head = new Node<T>;
  	head->next = NULL; //创建一个带头结点的空链表
  	Node<T>* r = head; //定义一个尾指针r，初始时指向头结点
  	for (int i = 0; i < n; i++) {
  		Node<T>* s = new Node<T>;
  		s->data = a[i];
  		r->next = s;
  		r = s;
  	} //运用尾插法建立单链表
  	r->next = NULL; //将最后一个节点的指针域设为空，表示链表结束
  };

按位查找

• 操作接口: T Get(int pos)
• 从头结点(或开始结点)出发，工作指针后移遍历整个单链表
• 算法描述:

template <typename T>
T LinkList<T> ::Get(int pos) {
	p = head->next; //p指向第一个结点
	int i = 1; //计数器
	while (p != NULL && i < pos) { //链表不为空且未到达指定位置
		p = p->next; 
		i++;
	};
	if (p == NULL || i > pos){
		cerr << "查找位置非法" << endl;
	}
	else {
		return p->data;
};

按值查找

• 操作接口: int Locate(T item)
• 算法描述:

template <typename T>
int LinkList<T> ::Locate(T item) {
	p = head->next; //p指向第一个结点
	int i = 1; //计数器
	while (p != NULL && p->data != item) { //链表不为空且未找到指定元素
		p = p->next;
		i++;
	};
	if (p == NULL) {
		return 0; //未找到，返回0
	}
	else {
		return i; //找到，返回位置
	};

链表的优缺点

方法	时间复杂度
插入/删除	O(1)
查找	O(n)