线性表

2.5.1 单链表的定义和表示

存储结构（物理位置）可以不连续。（非顺序映像/链式映像）

typedef struct LNode {
	ElemType data; // 数据域
	struct LNode *next; // 指针域
} LNode, *LinkList; // （同一结构体指针类型起了两个名称）
// LinkList是指向结构体LNode的指针类型
// 如果定义LinkList L 则L就是单链表的头指针
// 如果定义LNode *p 则p就是指向单链表中某个结点的指针

每个结点的指针域指向其直接后继结点。

单链表由表头指针唯一确定，所以可以用表头指针的名字为单链表命名。

加入头结点的好处：

1. 首元结点可以和其他结点同样处理。

2. 判定空表：L == NULL

头指针始终是指向头结点的非空指针。

单链表是顺序存取 意思是只能从头开始遍历

2.5.2 单链表基本操作的实现

1. 初始化

   Status IntList(LinkList &L) {
   	L = new LNode;
       L -> next = NULL; // 头结点指针域置空
       return OK;
   }
   

2. 取值

   只能从头到尾遍历。

   平均时间复杂度为O(n).

   Status GetElem(LinkList L, int i, ElemType &e) {
   	p = L-> next; 
   	j = 1; // 计数器
   	while(p && j < i) {
   		p = p -> next;
   		++j;
   	}
   	if(!p || j > i) return ERROR;
   	e = p -> data;
   	return OK;
   }
   

3. 查找

   从头到尾查找。

   平均时间复杂度为O(n).

4. 插入

   Status ListInsert(LinkList &L, int i, ElemType e) {
   	// 在带头结点的链表L中第i个位置插入值为e的结点
   	p = L;
   	j = 0;
   	while(p && j < i - 1) {
   		p = p -> next;
   		++j;
   	}
   	if(!p || j > i - 1) return ERROR;
   	s = new LNode;
   	s -> data = e;
   	s -> next = p -> next;
   	p -> next = s;
   	return OK;
   }
   

   注意指针域赋值的顺序。

   要插入到第i个位置，要找到第i - 1个位置。

   时间复杂度是O(n)，因为要先遍历找到插入位置

5. 删除

   和插入一样，需要先找到待删除元素的前驱结点。

   然后修改指针域，并释放待删结点的空间。

   Status ListDelete(LinkList &L, int i) {
   	p = L;
   	j = 0;
   	while(p -> next && j < i - 1) {
   		p = p -> next;
   		++j;
   	}
   	if(!p || j > i - 1) return ERROR;
   	q = p -> next; // 储存被删结点地址 以备释放
   	p -> next = q -> next;
   	delete q;
   	return OK;
   }
   

   时间复杂度是O(n)。

6. 创建

   （1） 前插法

   ​ 每次生成的新结点插入头结点之后（也就是作为新的首元结点）。

   void CreateList_H(LinkList &L, int n) {
   	L = new LNode;
   	L -> next = NULL;
   	for(int i = 0; i < n; i++) {
   		 p = new LNode;
   		 cin >> p -> data;
   		 p -> next = L -> next;
   		 L -> next = p; // 注意顺序
   	}
   }
   

   ​ 时间复杂度是O(n)。

   （2） 后插法

   ​ 为了便于每次将新结点插入表尾， 需要一个尾指针指向尾结点。

   void CreateList_R(LinkList &L, int n) {
   	L = new LNode;
   	L -> next = NULL;
   	r = L;
   	for(int i = 0; i < n; i++) {
   		p = new LNode;
   		cin >> p -> data;
   		p -> next = NULL;
   		r -> next = p;
   		r = p;
   	}
   }
   

   ​ 时间复杂度是O(n)。