系列文章
第一章：基礎(chǔ)知識
第二章：線性表
第三章：棧和隊列
第四章：字符串和數(shù)組
第五章：樹和二叉樹
第六章：圖
目錄
第1節(jié)：線性表
1.1 概念
1.2 順序存儲結(jié)構(gòu)
1.3 線性表的鏈?zhǔn)酱鎯?br>
1.4 單鏈表與順序表的對比
1.5 循環(huán)單鏈表
1.6 雙向鏈表
1.7 靜態(tài)鏈表
1.8 小結(jié)
第1節(jié)：線性表
1.1 概念
線性表是一種簡單的線性結(jié)構(gòu)，特點是在非空的有限集合中，且第一個元素沒有直接前驅(qū)元素，最后一個元素沒有直接后繼元素，其他元素都有唯一的前驅(qū)和后繼元素。
線性表有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。
1.2 順序存儲結(jié)構(gòu)
是指將線性表中的各個元素依次存放在一組地址連續(xù)的存儲單元中，通常將這種方法存儲的線性表稱為順序表。
假設(shè)，線性表的每個元素需占用m個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個元素的存儲位置location(ai+1)和第i個元素的存儲位置location(ai)之間滿足關(guān)系location(ai+1)=location(ai) + m。線性表中第i個元素的存儲位置與第一個元素的a1的存儲位置滿足以下關(guān)系，location(ai) =location(a1)+(i-1)*m。其中，第一個元素的位置location(a1)稱為起始地址或基地址。
順序表邏輯上相鄰的元素在物理上也是相鄰的。每一個數(shù)據(jù)元素的存儲位置都和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的位序成正比的常數(shù)。只要確定了第一個元素的起始位置，線性表中的任一個元素都可以隨機存取，因此，線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。由于C語言的數(shù)組具有隨機存儲特別，因此采用數(shù)組來描述順序表。如下所示：
typedef struct{
DataType list[ListSize];
int length;
}SeqList;
其中，DateType表示數(shù)據(jù)元素類型，list用于存儲線性表中的數(shù)據(jù)元素，length用來表示線性表中數(shù)據(jù)元素的個數(shù)，SeqList是結(jié)構(gòu)體類型名。定義一個順序表代碼：SeqList L; 指向順序表的指針：SeqList *L;
順序表的基本運算如下：
（1）初始化線性表：
void InitList（SeqList *L）{
L ->length =0; // 把線性表的長度設(shè)為0
}
(2）線性表非空判斷:
int ListEmpty(SeqList L){
if(L.length ==0)
return 1;
else
return 0;
}
（3）按序號查找：
int GetElem(SeqList L, int i, DataType *e) {
//查找線性表中第i個元素，查找成功將該值返回給e，并返回1表示成功，反正返回-1表失敗。
if(i<1||i>L.length)
return -1;
*e = L.list[i-1];
return 1;
}
(4) 按內(nèi)容查找：
int LocateElem(SeqList L,DataType e){
//查找線性表中元素值為e的元素
int i;
for (i = 0 ; L.length ;i++)
if(L.list[i] == e)
return i+1;
return 0;//找不到返回0
}
（5）插入操作：
//在順序表的第i個位置插入元素e，成功返回1，失敗返回-1，順序表滿了返回0
int InsertList(SeqList *L,int i ,DataType e){
int j;
if(i<1|| i> L->length+1）{
return -1;
}
else if(L->length >= ListSize){
return 0;
}else{
for(j=L->length ; j >=i ;j--){
L->list[j] = L ->list[j-1];
}
L->list[i-1] =e ;//插入元素到i個位置
L->length =L->length+1;
return 1;
}
}
(6）刪除操作：
int DeleteList(SeqList *L,int i ,DataType *e){
int j;
if(L->length<=0){
return 0;
}
else if(i<1||i>L-length){
return -1;
}else{
*e = L ->list[i-1];
for(j=i;j<=L->length-1;j++){
L->list[j-1] =L->length[j];
}
L->length = L->length-1;
return 1;
}
}
小結(jié)：順序表的優(yōu)缺點。
（1）優(yōu)點：無須關(guān)心表中元素之間的關(guān)系，所以不用增加額外的存儲空間；可以快速地取表中任意位置的元素。
（2）缺點：插入和刪除操作需要移動大量元素。使用前需事先分配好內(nèi)存空間，當(dāng)線性表長度變化較大時，難以確定存儲空間的容量。分配空間過大會造成存儲空間的巨大浪費，分配的空間過小，難以適應(yīng)問題的需求。
1.3 線性表的鏈?zhǔn)酱鎯?/h4>
在解決實際問題時，有時并不適合采用線性表的順序存儲結(jié)構(gòu)，例如兩個一元多項式的相加、相乘，這就需要另一種存儲結(jié)構(gòu)——鏈?zhǔn)酱鎯ΑＫ遣捎靡唤M任意的連續(xù)或非連續(xù)存儲單元存儲線性表的元素。為了表示每個元素ai與其直接后繼ai+1的邏輯關(guān)系，鏈?zhǔn)酱鎯Σ粌H需要存儲元素本身，還要存儲一個指向其直接后繼元素的地址。這種存儲結(jié)構(gòu)被稱之為結(jié)點（node）。存儲元素的叫數(shù)據(jù)域，存儲地址的叫指針域。結(jié)點元素的邏輯順序稱之為線性鏈表或單鏈表。
因為第一個結(jié)點沒有直接前驅(qū)結(jié)點，因此需要一個頭指針指向它。為了方便操作放在第一個元素結(jié)點之前一個結(jié)點稱之為頭結(jié)點，頭指針變成指向頭結(jié)點，其數(shù)據(jù)域可以存放如線表長度等信息，而指針域則存放第一個元素結(jié)點的地址信息。若該鏈表為空，則頭結(jié)點指針域為空。
因為，最后一個元素沒有直接后繼元素，所以將其指針域設(shè)置為“Null”空。
單鏈表的存儲結(jié)構(gòu)用C語言描述：
typedef struct Node{
DataType data;
struct Node *next;
}ListNode,*LinkList;
其中，ListNode是鏈表的結(jié)點類型，LinkList是指向鏈表結(jié)點的指針類型。定義為：LinkList L = ListNode *L。
單鏈表的基本運算如下：
（1）初始化單鏈表：
void InitList(LinkList *head){
if((*head=(LinkList)malloc(sizeof(ListNode)))==NULL){
//為頭結(jié)點分配存儲空間
exit(-1);
}
(*head)->next = NULL; //將單鏈表的頭結(jié)點指針域置為空
}
（2）單鏈表非空判斷：
int ListEmpty(LinkList head){
if(head->next == NULL){ //單鏈表為空
return 1;
}
else
{
return 0;
}
}
（3）按序號查詢操作：
//按序號查找單鏈表中第i個結(jié)點
ListNode *Get(LinkList head,int i){
ListNode *p;
int j;
if(ListEmpty(head)){ //如果鏈表為空
return NULL;
}
if(i<1){
return NULL;
}
j =0;
p =head;
while(p->next !=NULL && j<i){//保證p的下個結(jié)點不為空
p = p->next;
j++;
}
if(j==i)//找到第i個結(jié)點
return p;
else
return NULL;
}
（4）按內(nèi)容查找操作：
//按內(nèi)容查找單鏈表中元素值為e的元素
ListNode *LocateElem(LinkList head,DataType e){
ListNode *p;
p = head->next; //指針p指向第一個結(jié)點
while(p){
if(p->data != e){
p=p->next;//繼續(xù)下一個
}else{
break;
}
}
return p;
}
（5）定位操作：
int LocatePos(LinkList head,DataType e){
ListNode *p;//定義一個指向單鏈表的結(jié)點的指針p
int i;
if(ListEmpty(head))//非空判斷
return 0;
p =head->next;//指針p指向一個結(jié)點
i =1;
wihle(p){
if(p->data==e)
return i;
else
{
p=p->next;//指向下一個結(jié)點
i++;
}
}
if(!p)//如果沒有找到與e相等的元素
return 0;
}
(6)插入新數(shù)據(jù)元素e：
int InsertList(LinkList head,int i,DataType e){
ListNode *pre,*p;//定義第i個元素的前驅(qū)結(jié)點指針pre，新生結(jié)點指針p
int j;
pre =head; //指針pre指向頭結(jié)點
j =0;
while(pre->next!=NULL && j<i-1){ //循環(huán)直到直到i元素前驅(qū)結(jié)點
pre = pre->next;
j++;
}
if(j!=i-1)//如果沒找到，插入位置出錯
return 0;
//新生一個結(jié)點
if((p=(ListNode*)malloc(sizeof(ListNode)))==NULL){
exit(-1);
}
p->data =e; //將e賦值給結(jié)點的數(shù)據(jù)域
p->next =pre->next;
pre->next =p;
return 1;
}
(7) 刪除第i個結(jié)點：
int DeleteList(LinkList head,int i,DataType *e){
ListNode *pre,*p;
int j;
pre = head;
j = 0;
while(pre->next!=NULL && pre->next->next != NULL && j<i-1){
pre = pre->next;
j++;
}
if(j!=i-1){
return 0;
}
//指針p指向單鏈表中的第i個結(jié)點,并將該結(jié)點數(shù)據(jù)域值賦值給e
p = pre->next;
*e =p->data;
//將前驅(qū)結(jié)點的指針域指向要刪除結(jié)點的下一個結(jié)點
pre->next =p->next;
free(p);//釋放p指向的結(jié)點
return 1；
}
1.4 單鏈表與順序表的對比
（1）存儲方式：順序表用一組連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素；而單鏈表用一組任意的存儲單元存放線性表的數(shù)據(jù)元素。
（2）時間性能：采用循序存儲結(jié)構(gòu)時查找的時間復(fù)雜度為O(1)，插入和刪除需要移動平均一半的數(shù)據(jù)元素，時間復(fù)雜度為O(n)。采用單鏈表存儲結(jié)構(gòu)的查找時間復(fù)雜度為O(n)，插入和刪除不需要移動元素，時間復(fù)雜度僅為O(1）。
（3）空間性能：采用順序存儲結(jié)構(gòu)時需要預(yù)先分配存儲空間，分配空間過大會造成浪費，過小會造成問題。采用單鏈表存儲結(jié)構(gòu)時，可根據(jù)需要進行臨時分配，不需要估計問題的規(guī)模大小，只要內(nèi)存夠就可以分配，還可以用于一些特殊情況，如一元多項的表示。
1.5 循環(huán)單鏈表
循環(huán)單鏈表（circular linkedlist）是首尾相連的一種單鏈表，即將最后一個結(jié)點的空指針改為指向頭結(jié)點或第一個結(jié)點的形成一個環(huán)型，最后一個結(jié)點稱為尾指針:rear。判斷單鏈表為空的條件是head->next==NULL，而判斷循環(huán)單鏈表為空的條件是head->next==head。訪問第一個結(jié)點即rear->next->next。
如果將兩個循環(huán)單鏈表（LA，LB）合成一個鏈表，只需將一個表的表尾和另一個表的表頭連接即可。具體步驟為：
1，將LA->next = LB->next->next; 第一個結(jié)點。
2，釋放LB的頭結(jié)點，free(LB->next);
3, 將LB的表尾與LA的表頭相連，LB->next = LA->next。
LinkList Link(LinkList head1,LinkList head2){
ListNode *p,*q;
p = head1;//p指向1頭結(jié)點
while(p->next !=head1){//循環(huán)使指針p指向鏈表的最后一個結(jié)點
p = p->next;
}
q = head2;
while(q->next != head2){//同上
q = q->next;
}
p->next = head2->next;//將第一個鏈表的尾端連接第二個鏈表的第一個結(jié)點
q->next = head1; // 將第二個鏈表的尾端連接到第一個連接的第一個結(jié)點
return head1;
}
說明：也可以把循環(huán)單鏈表中的頭結(jié)點成為哨兵結(jié)點。
1.6 雙向鏈表
雙向鏈表(double linked list)就是鏈表中的每個結(jié)點有兩個指針域，一個指向直接前驅(qū)結(jié)點，另一個指向直接后繼結(jié)點。雙向鏈表的每個結(jié)點有data域、prior域、next域，共三個域。其中，data域為數(shù)據(jù)域，存放數(shù)據(jù)元素；prior域為前驅(qū)結(jié)點指針域；next域為后繼結(jié)點指針域。雙向鏈表為了方便操作也可以增加一個頭結(jié)點，同時也像單鏈表一樣也具有循環(huán)結(jié)構(gòu)，稱為雙向循環(huán)鏈表。
判斷帶頭結(jié)點的雙向循環(huán)鏈表為空的條件是：head->prior ==head || head->next == head。C語言描述：p=p->prior->next = p->next->prior。
雙向鏈表的結(jié)點存儲結(jié)構(gòu)描述如下：
typedef struct Node{
DataType data;
struct Node *prior;
struct Node *next;
}DListNode,*DLinkList;
（1）在第i個位置插入元素值為e的結(jié)點：
分析：首先找到第i個結(jié)點；再申請一個新結(jié)點，由s指向該結(jié)點，將e放入數(shù)據(jù)域。然后修改p和s指向的結(jié)點的指針域，修改s的prior域，使其指向p的直接前驅(qū)結(jié)點；修改p的直接前驅(qū)結(jié)點的next域，使其指向s指向的結(jié)點；修改s的next域，使其指向p指向的結(jié)點；修改p的prior域，使其指向s指向的結(jié)點。
int InsertDList(DListLink head,int i,DataType e){
DListNode *p,*s;
int j;
p = head->next;
j =0 ;
while(p!=head&&j<i){
p = p->next;
j++;
}
if(j!=i){
return 0;
}
s = (DListNode*)malloc(sizeof(DListNode));//給s創(chuàng)建新結(jié)點
if(!s){
return -1;
}
s->data=e; //e 賦值給s
s->prior = p->prior; //把p的前驅(qū)指針賦值給s的前驅(qū)
p->prior->next = s;//把s即e，賦值給p的前驅(qū)的后繼指針
s->next =p;//把s的后繼為p
p->prior =s;//p的前驅(qū)為s
return 1;
}
（2）刪除第i個結(jié)點
int DeleteDList(DListLink head,int i ,DataType e ){
DListNode *p;
int j;
p = head->next;
j= 0;
while(p!=head&&j<i){
p =p->next;
j++;
}
if(j!=i)
return 0;
p->prior->next =p->next;
p->next->prior = p->prior;
free(p);
return 1;
}
1.7 靜態(tài)鏈表
上面各種鏈表結(jié)點的分配與釋放都是由函數(shù)malloc、free動態(tài)實現(xiàn)，因此稱為動態(tài)鏈表。但是有的高級程序沒有指針類型，就不能利用上述辦法動態(tài)創(chuàng)建鏈表，需要利用靜態(tài)鏈表實現(xiàn)動態(tài)鏈表的功能。
利用一維數(shù)組實現(xiàn)靜態(tài)鏈表，類型說明如下：
typedef struct
{
DataType data;
int cur;
}SListNode;
typedef struct
{
SListNode list[ListSize];//節(jié)點類型
int av; //備用鏈表指針
}SLinkList; //靜態(tài)鏈表類型
靜態(tài)循環(huán)鏈表：數(shù)組的一個分量表示一個結(jié)點，同時用游標(biāo)（指示器cur）代替指針指示結(jié)點在數(shù)組中的相對位置。頭結(jié)點是數(shù)組的第0分量，其指針域指示鏈表的第一個結(jié)點。表中的最后一個結(jié)點的指針域為0，指向頭結(jié)點。例：線性表如下：
設(shè)s為SlinkList類型的變量，則s[0].cur指示頭結(jié)點，如果令i=s[0].cur，則s[i].data表示表中的第1個元素“Yang”是 s[i].cur指示第2個元素在數(shù)組的位置。
靜態(tài)鏈表基本元素：
（1）初始化靜態(tài)鏈表：
void InitSList(SLink *L){
int i;
for(i=0;i<ListSize;i++){
(*L).list[i].cur =i+1;
(*L).list[ListSize-1].cur=0;
(*L).av=1;
}
(2）分配結(jié)點：
int AssignNode(SLinkList L){
int i;
i=L.av;
L.av=L.list[i].cur;
return i;
}
(3）回收結(jié)點：
void FreeNode(SLinkList ,int pos){
L.list[pos].cur = L.av;
L.av=pos;
}
(4）插入操作：
void InsertSLink(SLinkList *L,int i,DataType e){
int j,k,x;
k=(*L).av;//從備用鏈中取出空閑結(jié)點
(*L).av=(*L).list.cur;//使備用鏈表指向下一個有用結(jié)點
(*L).list[k].data = e ;//將新元素放入空閑結(jié)點中
//將新結(jié)點插入到對應(yīng)的位置上
j =(*L).list[0].cur;
for(x=1;x<i<i;x++){
j=(*L).list[j].cur;
}
(*L).list[k].cur=(*L).list[j].cur;
(*L).list[j].cur=k;
}
（5）刪除操作：
void DeleteSList(SLinkList *L,int i,DataType *e){
int j,k,x;
if(i == 1）{
k=(*L).list[0].cur;
(*L).list[0].cur = (*L).list[k].cur;
}
else
{
j=(*L).list[0].cur;
for(x=1);x<i-1;x++){
j=(*L).list[j].cur;
}
k=(*L).list[j].cur;
(*L).list[j].cur = (*L).list[k].cur;
}
(*L).list[k].cur = (*L).av;
*e = (*L).list[k].data;
(*L).av = k ;
}
1.8 小結(jié)
（1）線性表中的元素之間是一對一的關(guān)系，除了第一個元素外，其他元素只有唯一的直接前驅(qū)，除了最后一個元素外，其他元素只有唯一的直接后繼。
（2）線性表有順序存儲和鏈?zhǔn)酱鎯煞N方式。采用順序存儲結(jié)構(gòu)的線性表成為順序表，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表成為鏈表。
（3）順序表中數(shù)據(jù)元素的邏輯順序與物理順序一致，因此可以隨機存取。鏈表是靠指針域表示元素之間的邏輯關(guān)系。
（4）鏈表又分為單鏈表和雙向鏈表，這兩種鏈表又可構(gòu)成單循環(huán)鏈表、雙向循環(huán)鏈表。單鏈表只有一個指針域，指針域指向直接后繼結(jié)點。雙向鏈表的一個指針域指向直接前驅(qū)結(jié)點，另一個指針域指向直接后繼結(jié)點。
（5）順序表的優(yōu)點是可以隨機存取任意一個元素，算法實現(xiàn)較為簡單，存儲空間利用率高，缺點是需要預(yù)先分配存儲空間，存儲規(guī)模不好確定，插入和刪除操作需要移動大量元素。鏈表的優(yōu)點是不需要事先確定存儲空間的大小，插入和刪除元素不需要移動大量元素；缺點是只能從第一個結(jié)點開始順序存取元素，存儲單元利用率不高，算法實現(xiàn)較復(fù)雜，因涉及指針操作，操作不當(dāng)會產(chǎn)生無法預(yù)料的內(nèi)存錯誤。
原文鏈接：https://blog.csdn.net/csdn_aiyang/java/article/details/84863136
