2.3線性表的鏈式表現與實現
2.3.1.1單鏈表
【特點：
*用一組任意的存儲單元存儲線性表的數據元素
*利用指針實現用不同相鄰的存儲單元存放邏輯上相鄰的元素
*每個元素ai，除存儲本身信息外，還存儲其直接后繼的元素（后一個元素的地址）
*結點：數據元素ai的存儲映像
{數據域：數據元素本身
指針域：指示直接后繼的存儲位置
【頭指針、頭結點、第一個元素結點
*頭指針：以線性表的第一個數據元素a1的存數地址作為線性表的地址，稱為線性表的頭指針
*頭結點：為了操作方便，在第一個結點前虛加一個“頭結點”，指向頭結點的指針為鏈表的頭指針（相當于第一個呀元素的結點）
代碼：
typedef struct LNode{ElemType data;struct LNode*next;
}LNode,*LinkList //LNode是結構體的別名，LinkList為指針變量
//相當于：typedef LNode *LinkList
2.3.1.2 單鏈表存儲結構實現
格式： data | next
【p指向數據域
(*p).data=10;
或：p->data=10; //表示p指向結點的數據域
（*p）.next=10
或 p->next //表示p指向結點的指針域
*生成一個LNode型新結點：
p=(LinkList)malloc(sizeof(LNode));
*系統回收p的結點
free（p）
*單鏈表特點：
1）是它是一種動態結構，整個存儲空間為多個鏈表共用
2）不需預先分配空間
3）指針占用額外存儲空間
4）不能隨機存取，查找速度慢
【基本操作：
1）GetElem（L,i,&e） //第i個元素用e帶回結果
2）ListInsert(&L,i,e) //插入
3）ListDelete(&L,i,e) //刪除
4）CreateList_L（&L,n） //創建線性表
2.3.1.3單鏈表的查找
【操作：
1）GetElem（L,i,&e）
【基本思想：
1）令p為指針變量，首先指向第一個結點，變量 j為計數器
2）依次向后查找，循環結束條件：p為空或j>=i；
3）找到用e返回第i個值
【代碼：
Status GetElem_L(LinkList L,int i,ElemType&e)
{ //L是鏈表的頭指針（對帶頭結點的鏈表），以e返回dii個值
p=L->next;
j=1;while (p&&j<i)
{p=p->next; ++j;if(!p||j>i)return ERROR;e=p->data; //取第i個值
return OK;
}2.3.1.4單鏈表的插入操作
2）ListInsert(&L,i,e)
在線性表第i個元素之前插入一個元素e
【思路：在第i項的前加一個接結點，i-1項的地址域和e的數據域連接
int ListInsert_L(LinkList&L,int i,int e)
{
LNode*p,*s;int j; //或：LinkList p,s; 等同
p=L;j=0; //計數器
while(p&&j<i-1)
{p=p->next;++j;}
if(!p||j>i-1)
return ERROR;
s=LinkList()malloc(sizeof(LNode)); //新結點
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
2.3.1.5 單鏈表的刪除
【思路：刪除第i個元素，并保存到元素e中
【代碼：
int ListDelete_L(LinkList&L,int i,ElemType&e)
{
LNode*p,*q;int j;
p=L;j=0;
while(p->next||j<i-1) //？？？？我覺得應該是(!p||j>i-1)
{p=p->next;++j}
if(p->next==NULL||j>i-1)
return ERROR; //刪除位置不合理
q=p->next; //q指向被刪除結點
p->next=q->next; //
e=q->data; //取出第i個結點的數據域
free(q); // 釋放dii個結點的內存
return OK;
} 2.3.1.6單鏈表的建立
【頭插法建立有頭結點的單鏈表
【圖】
L=(Linklist)malloc(sizeof(LNode)) //sizeof后面跟數據類型（LNode）
L->next=NULL
【圖】
p=(LinkList)malloc(sizeof(LNode))
scanf("%f",&(p->data)); //
【整個代碼：
void CreateList_L(LinkList &L,int n)
{
LNode*p;int i;
L=(LinkList)malloc(sizeof(Lnode));
L->next=NULL;
for(i=n;i>0;--i)
{ p=(Listlink)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next=L->next;
l->next=p //這里的=都可以理解為“給了，到，指向”
}
}2.3.1.7有序單鏈表的合并
例：線性表LA和LB中數據元素按照廢帝劍有序排列，將LA和LB合并為一個新的LC，且LC中的數據元素仍按照遞減有序排列
【代碼：
void MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)
{// 歸并La和Lb得到Lc，Lc也按照降序排列
LinkList pa,pb,pc;
pa=La->next;pb=Lb->next;
Lc=pc=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; //若a不為空則指向pa，否則指向pb
free(Lb);
}2.3.1.8靜態鏈表
定義：用數組描述的鏈表叫靜態鏈表
目的：為在不設指針類型的高級程序語言中使用鏈表結構
存儲結構：
#define MAXSIZE 100 //靜態鏈表最大長度
typedef struct{
ElemType data;
int cur; //游標，代替指針的結點，表示數組中的位置
}component,SLinkList[MAXSIZE]
2.3.2循環鏈表
循環鏈表是單鏈表的變形
循環鏈表最后一個結點link指針部位NULL，而是指向表的前端
為簡化操作，在循環鏈表往往插入頭結點
特點：
只要知道表中一結點的地址，就可以搜索到所有其他結點的地址
操作的時間復雜度：
表尾插入，時間復雜度：O(1)
表尾刪除：O(n)
表頭插入，同表尾
表頭刪除：O(1)
來處理算子)
