数据结构之线性表（二）
线性表的链式表示和表现
单链表
线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素。
对于一个数据元素ai需要存储其本身信息和指示其直接后继的信息（即直接后继的存储位置），这两信息构成一个“结点”：数据域，指针域
链表的每个结点中只包含一个指针域，故又称单链表或线性链表
和顺序表类似，在链式存储结构中仍以第一个数据元素的存储地址作为线性表的基地址，通常称它为头指针，线性表中所有数据元素都可以从头指针出发找到。 因为线性表的最后一个数据元素没有后继，因此，在单链表中最后一个结点中的“指针”是一个特殊的值 “NULL” （在图上用∧表示），通常称它为“空指针”。
为了便于处理一些特殊情况，在第一个结点之前附加一个“头结点”，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头结点（带头结点情况）
链表结构
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
若设 LNode * p，* q； LinkList H； 则 p，q 和 H 均为以上定义的指针型变量。若 p 的值非空，则表明 p 指向某个结点，p->data 表示 p 所指结点中的数据域，p->next 表示 p 所指结点中的指针域，若非空，则指向其“后继”结点。
- 指针型变量只能作同类型的指针赋值与比较操作。并且，指针型变量的“值”除了由同类型的指针变量赋值得到外，都必须用 C 语言中的动态分配函数得到。 例如，p = new LNode; 表示在运行时刻系统动态生成了一个 LNode 类型的结点，并令指针 p “指向”该结点。 反之，当指针 p 所指结点不再使用，可用 delete p， 释放此结点空间。
- 链表是一个进行动态存储管理的结构，因此在初始化时不需要按照线性表实际所需最大容量进行预分配。
单链表中的基本操作
初始化操作
初始化建一个空的链表即为建立一个只有头结点的链表。
void InitLst(Linklist &L)
{//创建一个带头结点的空链表，L为指向头结点的指针
L=new LNode;
if(!L){//存储空间分配失败
exit(1);
}
L->next=NULL;
}//InitList
时间复杂度为O (1）
销毁结构操作
void DestroyList(Linlist &L)
{//销毁以L为头指针的单链表，释放链表中的所有结点空间
LinkList p=L;
while(p){
q=p;
p=p->next;
delete q;
}
L=NULL;//虽然头结点占有的空间已经释放，但指针变量L中的值没有改变，为安全起见，置L为 “空”，以防止对系统空间的访问。
}//DestroyList
时间复杂度为O (Listlength(L))
存取元素操作
单链表是一种“顺序存取”的结构，即：为取第 i 元素，首先必须先找到第 i-1 个元素。因此不论 i 值为多少，都必须从头结点开始起“点数”，直数到第 i 个为止。头结点可看成是第0个结点。
bool GetElem(LinkList L,int pos,ElemType &e)
{//若1≤pos≤LengthList(L)，则用 e 带回指针L指向头结点的单链表中第 pos 个元素的值且返回函数值为TRUE,否则返回函数值为FALSE
int j=1;
LNode *p=L->next;
while(p&&j<pos){
p=p-next;
j++
}
if(!p||j>pos){//链表不存在第pos个结点
return FALSE;
}
e=p->data;
return TURE;
}//GetElem
时间复杂度为O (ListLength(L))
插入元素操作
在线性表中“插入”一个元素时，使元素之间的关系<ai-1,ai>改变为 <ai-1,e>和<e,ai>，只要修改相应数据元素的指针即可。因为新的元素插入在线性表的第i个元素之前，使得ai不再是ai-1的后继，而是新的元素e的后继，因此需要修改元素e和元素ai-1所在结点的指针。 由此，算法的基本思想就是，首先找到第i-1个结点，然后修改相应指针。
bool ListLnsert(LinkList &L,int pos,Elemtype e)
{//若1≤pos≤LengthList(L)+1，则在指针L指向头结点的单链表的第 pos 个元素之前插入新的元素 e，且返回函数值为 TRUE，否则不进行插入且返回函数值为 FALSE
p=L;
j=0;
while(p&&j<pos-1){//找到目标位置的前一个位置
p=p->next;
j++;
}
if(!p||j>pos-1){//参数不合法
return FALSE;
}
s=new LNode;
if(!s){//存储空间分配失败
exit(1);
}
//创造元素结点并修改指针
s->next=p-next;
s->data=e;
p->next=s;
return TURE;
}//ListInsert
时间复杂度为O (ListLength(L))
删除元素
和插入类似，由于删除元素 a i 改变了元素之间的关系，使 a i+1 不再是 a i 的后继，而是 a i-1 的后继，因此需要修改 a i-1 元素所在结点的指针。 因此在单链表中删除元素操作的算法基本思想和插入相同，也是：首先找到第 i-1 个结点，然后修改相应指针
bool ListDelete(LinkList &L,int pos,ElemType &e)
{// 若1≤pos≤LengthList(L)，则删除指针L指向头结点的单链表中第 pos 个元素并以 e 带回其值，返回函数值为 TRUE，否则不进行删除操作且返回函数值为 FALSE
p=L;
j=0;
while(p->next&&j<pos-1){
p=p->next;
j++;
}
if(!(p->next)||j>pos-1){
return FALSE;
}
q=p->next;
p->next=q->next;
e=q->data;
delete(q);
return TURE;
}//ListDelete_L
时间复杂度为O (ListLength(L))
逆序创建链表
void CreateList_L(LinkList &L,int n,ElemType A[])
{//已知数组 A 中存有线性表的 n 个数据元素， 逆序建立带头结点的单链表。
L=new LNode;
if(!L){//存储空间分配失败
exit(1);
}
L->next=NULL;//先建立一个带头结点的空的单链表
for(i=n;i>0;i--){
p=new LNode;
if(!p){
exit(1);
}
p->data=A[i-1];//赋元素值
L->next=p;//插入头结点之后
}
}//CreateList_L
时间复杂度为O (ListLength(L))
前m个结点与后n个结点位置交换
void exchange_L(LinkList &L,int m)
{
if(M&&L->next){
LNode *p=L->next;
int k=1;
while(k<m&&p){//查找am
p=p->next;
k++；
}
if(p&&p->next){//n!=0是才需要修改指针
ha=L->next;//ha记录a1位置
L->next=p->next;//修改指针位置，将m位置后的第一个结点至于头结点后
p->next=NULL;//摄am后继为空
q=L->next;//另q指向b1
while(q->next){//找到原链表的最后一个元素
q=q->next;
}
q->next=ha;//将a1街道bn后面
}
}
}
时间复杂度为O (ListLength(L))
删除单链表中相同元素
void purge_L(LinkList &L){
//删除单链表L中的冗余元素，即使操作之后的单链表中只保留操作之前表中所有值都不相同的元素
p=L->next;
L->next=NULL;//设新表为空表
while(p){//顺序考察原表中每个元素
succ=p->next;//记下结点*p的后继
q=L->next;//q指向新表的第一个结点
while(q&&q->data!=q->data){
q=q->next
}
}
}
单链表的相关算法
单链表翻转
//递归算法 ???
ListNode* reverseList(ListNode* head)
{
if(head==null||head->next==null){
return head;
}
ListNode *p=reverswList(head->next);
head->next->next=head;
head->next=null;
return p;
}
//非递归算法实现
ListNode* reverseList(ListNode* head)
{
ListNode *curr=head;
if(curr==null){
return null;
}
ListNode *prev=null,*temp==null;
while(curr!=null){
temp=curr->next;
curr->next=prev;
prev=curr;
curr=temp;
}
return prev;
}
单链表判断是否有环
？？？
最容易想到的思路是存一个所有 Node 地址的 Hash 表，从头开始遍历，将 Node 存到 Hash 表中，如果出现了重复，则说明链表有环。
一个经典的方法是双指针（也叫快慢指针），使用两个指针遍历链表，一个指针一次走一步，另一个一次走两步，如果链表有环，两个指针必然相遇。
//双指针算法实现
bool hasCycle(ListNode *head){
if(head==nullptr){
return false;
}
ListNode *fast,*slow;
slow=head;
fast=head->next;
while(fast&&fast->next){
slow=slow->next;
fast=fast->next->next;
if(slow==fast){
return true;
}
}
return false;
}
//遍历hash表的算法实现
单链表找环入口
在快慢指针相遇的时候，此时慢指针没有遍历完链表，再设置一个指针从链表头部开始遍历，这两个指针相遇的点，就是链表环的入口。
单链表找交点
单链表找中间结点
用快慢指针法，当快指针走到链表结尾时，慢指针刚好走到链表的中间：
ListNode* middleNode(ListNode* head) {
ListNode *slow = head;
ListNode *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
单链表合并
两个链表本身都是排序过的，把两个链表从头节点开始，逐个节点开始进行比较，最后剩下的节点接到尾部：
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
if (l1 == nullptr) {
return l2;
}
if (l2 == nullptr) {
return l1;
}
ListNode dummy(-1);
ListNode *p = &dummy;
for (; l1 && l2; p = p->next) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
}
p->next = l1 != nullptr ? l1 : l2;
return dummy.next;
}
