數據結構基礎篇(4)

十六.循環鏈表

概念
- 循環鏈表是一種頭尾相接的鏈表（最后一個結點的指針域指向頭結點，整個鏈表形成一個環）
優點
- 從表任一結點出發均可找到表中其他結點
判斷終止
- 由于循環鏈表中沒有NULL指針，所以涉及遍歷操作時，終止條件不像非循環鏈表那樣判斷p或p->next是否為空，而是是否等于頭指針
- 循環條件從p！=NULL到p！=L，p->next！=NULL到p->next！=L（單循環鏈表）
時間復雜度
- 頭指針表示單循環鏈表
  - 找a~1的時間復雜度：O（1）
  - 找a~n的時間復雜度：O（n）
    - 注意
      - 表的操作常常在表的首尾位置上進行
- 尾指針表示單循環鏈表
  - a~1的存儲位置是：R->next->next
  - a~n的存儲位置是：R
  - 時間復雜度均為O（1）

LinkList Connect(LinkList Ta,LinkList Tb)    //假設Ta.Tb都是非空的單循環鏈表
{vp=Ta->next;    //p存表頭結點Ta->next=Tb->next->next;    //Tb表頭連接Ta表尾delete Tb->next;    //釋放Tb表頭結點Tb->next=p;    //修改指針return Tb;
}

十七.雙向鏈表

雙向鏈表的由來
- 查找某結點的后續結點的執行時間=O(1)
  - 單鏈表結點->有指示后繼的指針域->后繼結點
- 查找某結點的前驅結點的執行時間=O（n）
  - - ->無指示前驅的指針域->依次尋找前驅結點
雙向鏈表的概念
- 在單鏈表的每個結點里再增加一個指向其直接前驅的指針域prior，這樣鏈表就形成了有兩個方向不同的鏈。
雙向鏈表的特點
- 雙向鏈表也有循環表
  - 讓頭結點的前驅指針指向鏈表的最后一個節點
  - 讓最后一個節點的后繼指針指向頭結點
雙向鏈表結構的對稱性
- p->prior->next=p=p->next->prior
在雙向鏈表中有些操作（如：ListLength、GetElem等），因僅涉及一個方向的指針，所以它們的算法與線性鏈表的相同。
在插入、刪除時，則需同事修改兩個方向上的指針，兩個的操作的時間復雜度都為O（n）。

雙向鏈表的插入

void ListInsert_DuL(DuLinkList &L,Init i,ElemType e)    //在帶頭結點的雙向循環鏈表L中第i個位置之前插入元素e
{if(!(p=GetElemP_DuL(L,i)))return ERROR;s=new DuLNOde;s->date=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;return OK;
}//ListInsert_Dul

雙向鏈表的刪除

void ListDelete_DuL(DuLinkList &L,Init i,ElemType &e)    //刪除帶頭節點的雙向循環鏈表L的第i個元素，并返回e
{if(!(p=GetElemP_DuL(L,i)))return ERROR;e=p->data;p->prior->next=p->next;p->next->prio=p->prior;free(p)return OK;
}//ListDelete_Dul

十八.單鏈表，循環鏈表和雙向鏈表的時間效率比較

時間效率的比較	查找表頭結點（首元結點）	查找表尾結點	查找結點*P的前驅結點
帶頭結點的單鏈表L	L->next 時間復雜度O(1)	從L->next依次向后遍歷時間復雜度O(n)	通過p->next無法找到其前驅
帶頭結點僅設頭指針L的循環單鏈表	L->next 時間復雜度O(1)	從L->next依次向后遍歷時間復雜度O(n)	通過p->next可以找到其前驅時間復雜度O(n)
帶頭結點僅設尾指針R的循環單鏈表	R->next\| 時間復雜度O(1)	R 時間復雜度O(1)	通過p->next可以找到其前驅時間復雜度O(n)
帶頭結點的雙向循環鏈表L	L->next 時間復雜度O(1)	L->prior 時間復雜度O(1)	p->prior 時間復雜度O(1)

十九.順序表和鏈表的比較

鏈式存儲結構的優點
- 節點空間可以動態申請和釋放
- 數據元素的邏輯次序靠節點的指針來指示，插入和刪除時不需要移動數據元素
鏈式存儲結構的缺點
- 存儲密度小，每個結點的指針域需額外占用存儲空間。當每個節點的數據域所占字節不多時，指針域所占存儲空間的比重閑得很大。
  - 存儲密度
    - 概念
      - 結點數據本身所占的存儲量和整個節點結構所占的存儲量之比
    - 公式
      - 存儲密度=結點數據本身占用的空間/結點占用的空間總量
    - 比較
      - 順序表存儲密度1，鏈式小于1。
- 鏈式存儲結構是非隨機存儲結構。對任一結點的操作都要從頭指針依指針鏈查找到該結點，增加了算法的復雜度。
順序表和鏈表比較圖

比較項目\存儲結構	順序表	鏈表
空間-存儲空間	預先分配，導致空間閑置或溢出現象	動態分配，不會出現存儲空間閑置或溢出現象
空間-存儲密度	不用為表示結點間的邏輯關系而增加額外的存儲開銷，存儲密度等于1	需要借助指針來體現元素間的邏輯關系，存儲密度小于1.
時間-存取元素	隨機存儲，按位置訪問元素的時間復雜度O(1)	順序存儲，按位置訪問元素時間復雜度O(n)
時間-插入、刪除	平均移動約表中一半元素，時間復雜度O(n)	不需要移動元素，確定插入，刪除位置后，時間復雜度O
適用情況	表長變化不大，能事先確定變化的范圍。很少進行插入或刪除操作，經常按元素位置序號訪問數據元素。	長度變化較大頻繁進行插入或刪除操作

二十.線性表的應用

線性表的合并
- 問題
  - 假設利用兩個線性表La和Lb分別表示兩個集合A和B,現要求一個新的集合A=AUB
- 解決

void union(List &La,List Lb)
{La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e))ListInsert(&La,++La_len,e);    }
}    //算法的時間復雜度是：O(ListLength(La)*ListLength(Lb))

有序表的合并
- 問題
  - 已知線性表La和Lb中的數據元素按值非遞減有序排列，現要求LA和Lb歸并為一個新的線性表Lc，Lc中的數據元素扔按值非遞減有序排列。
- 解決
  - 創建一個空表Lc
  - 依次從La或Lb中“摘取”元素值較小的節點插入到Lc表的最后，直到其中一個表邊空為止
  - 繼續將La或Lb其中一個表的剩余節點插入在Lc表的最后

用順序表來實現

void MergeList_Sq(SqList LA,SqList Lb,SqList &LC)
{pa=LA.elem;pb=LB.elem;    //指針pa和pb的初值分別指向兩個表的第一個元素LC.length=LA.length+LB.length;    //新表長度為待合并量表的長度之和LC.elem=new ElemType[LC.length];    //為合并后的新表分配一個數組空間pc=LC.elem;    //指針pc指向新表的第一個元素pa_last=LA.elem+LA.length-1;    //指針pa_last指向LA表的最后一個元素pb_last=LB.elem+LB.length-1;     //指針pa_last指向LB表的最后一個元素while(pa<=pa_last && pb<=pb_last)    //兩個表都非空{if(*pa<=*pb)*pc++=*pa++;    //依次“摘取”兩表中的最小值else *pc++=*pb++;                                                          }while(pa<=pa_last)*pc++=*pa++;     //LB表已到達表尾，將LA中剩余元素加入LCwhile(pb<=pb_last)*pc=++=*pb++;    //LA表已到達表尾，將LB中剩余元素加入LC
}    //MergeList_Sq//算法的時間復雜度是：O(ListLength(La)*ListLength(Lb))

用鏈表來實現

void MergeList_L(SqList &La,SqList &Lb,SqList &Lc)
{pa=La->next;pb=Lb->next;pc=Lc=La;    //用La的頭結點作為Lc的頭結點while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;        }               else{pc->next=pb;pc=pb;pb=pb->next;        }     }pc->next=pa?pa:pb；  //插入剩余段delete Lb;    //釋放Lb的頭結點
}    //算法的時間復雜度是：O(ListLength(La)*ListLength(Lb))

一元多項式的運算
- 多項式創建
- 創建一個只有頭結點的空鏈表
- 根據多項式的項的個數n，循環n次執行以下操作
  - 生成一個新結點*s
  - 輸入多項式當前項的系數和指數賦給新節點*s的數據域
  - 設置一前驅指針pre，用于指向待找到的第一個大于輸入項指數的結點的前驅，pre初值指向頭結點。
  - 指針q初始化，指向首元結點
  - 循鏈向下逐個比較鏈表中當前結點與輸入項指數，找到第一個大與輸入項指數的節點*q
  - 將輸入項結點*s插入到結點*q之前

void CreatePolyn(Polynomial &P,int n)    //輸入m項的系數和指數，建立表示多項式的有序鏈表P
{P=new PNode;p->next=NULL;    //先建立一個帶頭結點的單鏈表for(i=1;i<=n;i++)    //依次輸入n個非零項{s=new PNode;    //生成新節點cin>>s->coef>>s->expn;    //輸入系數和指數pre=P;    //pre用于保存q的前驅，初值為頭結點q=P->next;    //q初始化，指向首元結點while(q&&q->expn<s->expn)    //找到第一個大于輸入項指數的項*q{pre=q;q=q->next;        }    s->next=q;    //將輸入項s插入到q和其前驅結點pre之間pre->next=s;}
}