大綱：

1. 理解線性表的邏輯結(jié)構(gòu)
2. 掌握線性表的順序存貯結(jié)構(gòu)和鏈?zhǔn)酱尜A結(jié)構(gòu)航瞭；掌握線性表基本操作的實(shí)現(xiàn)佑菩。
3. 了解線性表的應(yīng)用汪诉。

線性表的定義和基本操作

1. 線性表的定義

   具有相同數(shù)據(jù)類型的n（n>=0）個(gè)數(shù)據(jù)元素的有限序列

   線性表的特點(diǎn)：

   • 除第一個(gè)元素外谅年，每個(gè)元素有且僅有一個(gè)直接前驅(qū)稼病；除最后一個(gè)元素外纽甘，每個(gè)元素有且僅有一個(gè)直接后繼
   • 表中元素的個(gè)數(shù)有限
   • 表中元素具有邏輯上的順序性
   • 表中每個(gè)元素都是數(shù)據(jù)元素良蛮，每個(gè)元素都是單個(gè)元素
   • 表中元素的數(shù)據(jù)類型都相同，即每一個(gè)元素占有相同大小的存儲(chǔ)空間
   • 表中元素具有抽象性悍赢，即只關(guān)注于邏輯結(jié)構(gòu)决瞳，不關(guān)注于元素表示什么內(nèi)容

• 線性表示一種邏輯結(jié)構(gòu)，表示元素之間一對(duì)一的相鄰關(guān)系左权；順序表和鏈表是存儲(chǔ)結(jié)構(gòu)皮胡，表示物理結(jié)構(gòu)

2. 線性表的基本操作

   InitList(&L)：初始化表
   Length(L)：求表長
   LocateElem(L,e)：按值查找操作
   GetElem(L,i)：按位查找操作
   ListInsert(&L,e)：插入操作
   ListDelete(&L,i,&e)：刪除操作
   PrintList(L)：輸出操作
   Empty(L)：判空操作
   DestroyList(&L)：銷毀操作

線性表的順序表示

1. 順序表的定義

   用一組連續(xù)的存儲(chǔ)單元，依次存儲(chǔ)線性表中的數(shù)據(jù)元素赏迟，使得邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰屡贺。

   結(jié)構(gòu)體描述：

   //數(shù)組空間靜態(tài)分配
   #define MaxSize 50  //數(shù)組最大長度
   typedef struct{
     ElemType data[MaxSize];  //順序表的元素  
     int length;  //順序表當(dāng)前長度
   }SqList;  //靜態(tài)分配數(shù)組順序表的類型定義
   
   //數(shù)組空間動(dòng)態(tài)分配
   #define InitSize 100  //表長度的初始定義
   typedef struct{
     ElemType *data;
     int MaxSize,length;
   }SeqList;  //動(dòng)態(tài)分配數(shù)組順序表的類型定義
   

   • C的初始動(dòng)態(tài)分配語句
     L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
   • 順序表的特點(diǎn)是隨機(jī)訪問，并且存儲(chǔ)密度高。但是增刪操作需要移動(dòng)大量元素

2. 基本操作相關(guān)代碼
   2.1 插入操作

   bool ListInsert(SqList &L,int i,ElemType e){
     if(i<1 || i>L.length)  //判斷插入范圍是否有效
       return false;
     if(i.length>=MaxSize)  //判斷存儲(chǔ)空間是否已滿
       return false;
     for(int j=L.lengt;j>=i;j--)  //將i之后的元素依次向后移動(dòng)
       L.data[j]=L.data[j-1];
     L.data[i-1]=e;  //在i位置上賦值甩栈，注意裳扯，i是位置序號(hào)，i-1是數(shù)組下標(biāo)
     L.length++;  // 長度加一
     return true;
   }
   

   • 移動(dòng)節(jié)點(diǎn)平均次數(shù)為n/2谤职，時(shí)間復(fù)雜度為O(n)

   2.2 刪除操作

   bool ListDelete(SqList &L,int i,ElemType &e){
     if(i<0 || i>L.length)  //判斷刪除范圍是否有效
       return false;
     for(int j=i;j<L.length;j++)  //將i之后的值依次前移
       L.data[j-1]=L,data[j];
     L.length--;  //長度減一
     return false;
   }
   

   • 移動(dòng)節(jié)點(diǎn)平均次數(shù)(n-1)/2饰豺，時(shí)間復(fù)雜度為O(n)

   2.3 按值查找

   int LocateElem(SqList L,ElemType e){
     //實(shí)現(xiàn)查找順序表中值為e的元素，查找成功則返回元素位序允蜈，否則返回0
     int i;
     for(i=0;i<L>length;i++)
       if(L.data[i]==e)
         return i+1;  //下標(biāo)為i的元素值為e冤吨，其位置為i+1
     return 0;
   }
   

   • 移動(dòng)節(jié)點(diǎn)平均次數(shù)為(n+1)/2，時(shí)間復(fù)雜度為O(n)

線性表的鏈?zhǔn)奖硎?/h2>

單鏈表

1. 單鏈表的定義

   通過一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中的數(shù)據(jù)元素饶套，每個(gè)鏈表節(jié)點(diǎn)除了存放自身的信息之外漩蟆，還要存放一個(gè)指向后繼的指針。其中data為數(shù)據(jù)域妓蛮，next為指針域怠李。

   結(jié)點(diǎn)類型定義

   typedef struct LNode{
     ElemType data;
     struct LNode *next;
   }LNode,*LinkList;
   

   • LinkList L==LNode *L
   • 單鏈表中的元素是離散地分布在存儲(chǔ)空間中的，所以是非隨機(jī)存取存儲(chǔ)結(jié)構(gòu)蛤克，想找到某個(gè)元素必須從頭遍歷
   • 通常用頭指針標(biāo)識(shí)一個(gè)單鏈表捺癞，此外，在單鏈表的第一個(gè)結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)构挤，稱為頭結(jié)點(diǎn)髓介。頭結(jié)點(diǎn)中可以不加任何信息，也可以記錄表長等信息筋现。
   • 引入頭結(jié)點(diǎn)的優(yōu)點(diǎn)：
     • 開始結(jié)點(diǎn)放在頭結(jié)點(diǎn)的指針域中唐础，所以鏈表的第一個(gè)位置上的操作與其他位置上的操作一致，不需要特殊處理
     • 若鏈表為空矾飞，頭指針是指向頭結(jié)點(diǎn)的非空指針（頭結(jié)點(diǎn)的指針域?yàn)榭眨┮慌颍钥毡砼c非空表的處理統(tǒng)一
   • 單鏈表解決了順序表需要大量連續(xù)存儲(chǔ)空間的缺點(diǎn)，但是單鏈表附加指針域洒沦，也存在浪費(fèi)存儲(chǔ)空間的缺點(diǎn)

2. 基本操作相關(guān)代碼
   2.1 建立單鏈表

   //頭插法
   LinkList CreatList1(LinkList &L){
     //從表尾到表頭逆向建立單鏈表L豹绪，每次均在頭結(jié)點(diǎn)之后插入元素
     LNode *s;
     int x;
     L=(LinkList)malloc(sizeof(LNode));  //創(chuàng)建頭結(jié)點(diǎn)
     L->next=NULL;  //初始空鏈表
     scanf("%d",&x);  //輸入結(jié)點(diǎn)中的元素
     while(x!=999){
       s=(LNode*)malloc(sizeof(LNode));  //創(chuàng)建新的結(jié)點(diǎn)
       //下面三條代碼為頭插法的插入細(xì)則
       s->data=s;
       s->next=L->next;
       L->next=s;
       scanf("%d",&x);
     }
     return L;
   }
   
   //尾插法
   LinkList CreatList2(LinkList &L){
     //從表頭到表尾正向建立單鏈表L，每次均在表尾插入元素
     LNode *s,*r=L;  //除了s這個(gè)新結(jié)點(diǎn)的指針微谓，還建立了一個(gè)指向尾結(jié)點(diǎn)的r指針
     int x;
     L=(LinkList)malloc(sizeof(LNode));
     L->next=NULL;
     scanf("%d",&x);
     while(x!=999){
       s=(LNode*)malloc(sizeof(LNode));
       //以下三條代碼為尾插法的插入細(xì)則
       s->data=s;
       r->next=s;
       r=s;  //r指向新的尾結(jié)點(diǎn)
       scanf("%d",&x);
     }
     r->next=NULL;
     return L;
   }
   

   • 頭插法建立單鏈表森篷，讀入數(shù)據(jù)的順序與生成的鏈表中的元素的順序是相反的；尾插法建立單鏈表豺型，讀入數(shù)據(jù)的順序與生成的鏈表中的元素的順序是相同的
   • 兩種方法的時(shí)間復(fù)雜度都為O(n)

   2.2 按序號(hào)查找結(jié)點(diǎn)值

   LNode *GetElem(LinkList L,int i){
     int j=1;  //計(jì)數(shù)器
     LNode *p=L->next;  //p指向頭結(jié)點(diǎn)指針
     if(i==0)
       return L;
     if(i<1)
       return NULL;
     while(p&&j<i){  //從第一個(gè)結(jié)點(diǎn)開始找仲智，查找第i-1個(gè)結(jié)點(diǎn)
       p=p->next;
       j++;
     }
     return p;  //返回第i個(gè)結(jié)點(diǎn)的指針，如果i大于表長姻氨，p=NULL钓辆，直接返回p即可
   }
   

   • 時(shí)間復(fù)雜度為O(n)

   2.3 按值查找

   LNode *LocateElem(LinkList L,ElemType e){
     LNode *p=L->next;
     while(p!=NULL&&p->data!=e)
       p=p->next;
     return p;
   }
   

   • 時(shí)間復(fù)雜度為O(n)

   2.4 插入結(jié)點(diǎn)主要代碼片段

   p=GetElem(L,i-1);  //查找插入位置的前驅(qū)結(jié)點(diǎn)
   s->next=p->next;
   p->next=s;
   

   • 時(shí)間復(fù)雜度為O(1)
   • 單鏈表一般都是后插操作，但可以通過如下方式將前插操作轉(zhuǎn)化為后插操作

     //將s結(jié)點(diǎn)插入到p結(jié)點(diǎn)之前的主要代碼片段
     s->next=p->next;
     p->next=s;
     temp=p->data;  //交換數(shù)據(jù)域
     p->data=s->data;
     s->data=temp;
     

   2.5 刪除結(jié)點(diǎn)操作

   //刪除當(dāng)前指針下一個(gè)結(jié)點(diǎn)
   p=GetElem(L,i-1);
   q=p->next;
   p->next=q->next;
   free(p);
   
   //刪除當(dāng)前指針?biāo)诮Y(jié)點(diǎn)
   q=p->next;
   p->data=p->next->data;
   p->next=q->next;
   free(q);
   

   • 第一個(gè)刪除操作時(shí)間復(fù)雜度為O(n)；第二個(gè)刪除操作時(shí)間復(fù)雜度為O(1)

雙鏈表

雙鏈表是在單鏈表只有一個(gè)指向后繼結(jié)點(diǎn)的指針next的基礎(chǔ)上前联，增加了一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針prior

• 單鏈表想訪問某個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)時(shí)功戚，只能從頭遍歷，訪問后繼結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)似嗤，訪問前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度O(n)

結(jié)點(diǎn)類型定義

typedef struct DNode{
  ElemType data;
  struct DNode *prior,*next;
}DNode,*LinkList;

• 插入操作主要代碼片段

s->next=p->next;
p->next-prior=s;
s->prior=p;
p->next=s;

• 刪除操作主要代碼片段

p->next=q->next;
q->next->prior=p;
free(p);

循環(huán)鏈表

循環(huán)單鏈表： 在單鏈表的基礎(chǔ)上啸臀，表中最后一個(gè)結(jié)點(diǎn)的指針不是NULL，而是改為指向頭結(jié)點(diǎn)烁落，整個(gè)鏈表形成一個(gè)環(huán)

• 因?yàn)闆]有指針域?yàn)镹ULL的結(jié)點(diǎn)乘粒，所以，循環(huán)單鏈表的判空條件不是頭結(jié)點(diǎn)的指針是否為空伤塌，而是它是否等于頭指針灯萍。
• 插入，刪除操作算法與單鏈表一致每聪，只是在表尾操作有所不同旦棉，需維持環(huán)的狀態(tài)。且药薯，任何位置插入绑洛，刪除操作都是等價(jià)的，所以不需要判斷表尾

循環(huán)雙鏈表：在雙鏈表的基礎(chǔ)上果善，表中最后一個(gè)結(jié)點(diǎn)的指針不是NULL诊笤，而是改為指向頭結(jié)點(diǎn)系谐，整個(gè)鏈表形成一個(gè)環(huán)

• 判空條件為頭結(jié)點(diǎn)的prior域和next域都等于頭結(jié)點(diǎn)

靜態(tài)鏈表

靜態(tài)鏈表是借助數(shù)組來描述線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)巾陕，結(jié)點(diǎn)也有數(shù)據(jù)域data和指針域next，不過這里的指針域指的是數(shù)組下標(biāo)（游標(biāo)）

結(jié)點(diǎn)類型定義

#define MaxSize  //靜態(tài)鏈表的最大長度
typedef struct{
  ElemType data;
  int next;   //下一個(gè)元素的數(shù)組下標(biāo)
}SLinkList[MaxSize];

• 同順序表一樣纪他，需要預(yù)先分配一塊連續(xù)的內(nèi)存空間
• 靜態(tài)鏈表以next=-1作為其結(jié)束的標(biāo)志

順序表和單鏈表的比較

1. 存取方式
   順序表可以順序存取鄙煤，也可以隨機(jī)存取茶袒；鏈表只能順序存取
2. 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)
   順序表梯刚，邏輯上相鄰的元素，物理位置上也相鄰薪寓；鏈表亡资，邏輯上相鄰的元素，物理位置上不一定相鄰
3. 查找向叉，插入和刪除操作時(shí)間復(fù)雜度
   按值查找：順序表無序時(shí)锥腻，兩者時(shí)間復(fù)雜度都是O(n)；當(dāng)順序表有序時(shí)母谎，可以采用折半查找瘦黑，時(shí)間復(fù)雜度為O(log?n)
   按位查找：順序表支持隨機(jī)訪問，時(shí)間復(fù)雜度為O(1)；鏈表平均時(shí)間復(fù)雜度為O(n)
   插入幸斥，刪除的時(shí)間內(nèi)復(fù)雜度見上
4. 空間分配
   順序表易造成空間浪費(fèi)匹摇，鏈表則不會(huì)

• 實(shí)際中，應(yīng)基于存儲(chǔ)甲葬，運(yùn)算廊勃，環(huán)境的多方面考慮，恰當(dāng)?shù)剡x擇存儲(chǔ)結(jié)構(gòu)