第二章 線性表
順序表：采用順序存盤結構的線性表稱為順序表
2.1 線性表的順序存盤表示和實作
2.1.1線性表的順序存盤表示
#順序表是線性表的順序存盤表示法，其資料元素用一段連續的地址空間，類似陣列，其特點為邏輯上相鄰，物理次序也是相鄰的，
#假設順序表中每個元素占用l個存盤單元，并且第一個元素所占地址為存盤單元的基地址，線性表中第i+1個元素的存盤位置LOC(ai+1)和第i個元素的存盤位置LOC(ai)有以下關系
LOC(ai+1)=LOC(ai)+l
LOC(ai+1)=LOC(a1)+(i-1)*l
#define MAXSIZE 100 //存盤空間分配大小
typedef int ElemType; //給int起別名ElemType
typedef struct
{
ElemType *elem; //存盤空間基地址，首地址.可以理解為順序表為一“動態陣列”,指標變數elem指向陣列的首地址，
int length; //當前長度,用于統計順序表的長度，元素個數，
}SqList;
Tip：①這里的SqList,相當于給該自定義結構類取了一個別名，定義該自定義型別變數時就可像這樣SqList List;
2.1.2 順序表的基本操作與實作
2.1.2.1順序表的初始化 int InitList(SqList *L)
演算法步驟：
①為順序表List分配一個預定義大小的陣列空間，elem指向這段空間的基地址，
②分配空間成功，將當前表長設定為0（未插入資料，表長為0）；
//1.初始化順序線性表
int InitList(SqList *L)
{
(*L).elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));//分配存盤空間
if(!(*L).elem)
{
printf("\n分配空間失敗！！！");
return -1;//空間分配失敗
}
(*L).length=0;//空表長度設定為0
printf("\n分配空間成功！！！");
return 0;
}
Tip：①該順序表初始化函式所傳的引數為指標型別，需創建個指標變數L指向List（上面的SqList List），再將該指標變數L傳入，
②這里用if( ! (*L).elem )判斷分配空間是否為空，c語言中，變數未賦值時其值是隨機的，因此我們再創建變數List后，將List.elem賦值為NULL；使該判斷有效，
③分配存盤空間后將List.length<==>(*L).length賦值為0，當前表為空表，
2.1.2.2 順序表的插入 int ListInsert(SqList *L,int i,ElemType e)
演算法步驟：
①首先判斷位置i是否合法（合法范圍是1 <= i <= n+1）n為元素個數即順序表長度，
②判斷順序表的存盤空間是否已滿（這里暫時不考慮擴展空間），
③將第i個到第n個位置的元素依次向后移動一個位置，
④將要插入的元素e賦值到第i個位置，
⑤表長+1，完成插入，
//2.線性表中插入元素
int ListInsert(SqList *L,int i,ElemType e)
{
if(i<1||i>(*L).length+1)
{
printf("\n插入位置違法！！！");
return -1;
}
if((*L).length==MAXSIZE)
{
printf("\n順序表的存盤空間已滿！！！");
return -1;
}
int j;
for(j=(*L).length-1;j>=i-1;j--)
{
(*L).elem[j+1]=(*L).elem[j];
}
(*L).elem[i-1]=e;
(*L).length++;
printf("\n插入成功！！！");
return 0;
}
Tip：①這里移動順序標中第i到第n個元素采用的是下標表示法，elem[i-1]對應于第i個元素，這里要注意，
2.1.2.3 順序表的取值 int GetElem(SqList List,int i,ElemType *e)
演算法步驟：
①首先判斷取值位置i是否合法（1<= i >=n）
②若取值位置合法，將第i個元素List.elem[i-1]賦值給e，
//3.取出第i個元素的值
int GetElem(SqList List,int i,ElemType *e)
{
if(i<1||i>List.length)
{
printf("\n所取位置違法!!!");
return -1;
}
*e=List.elem[i-1];
printf("\n取值成功！！！");
return 0;
}
Tip：①這里傳入的是ElemType *e,e是個指向ElemType型別變數的指標，接收該回傳值即*e=List.elem[i-1]，
②想要接收第i個元素的值，就事先定義一個ElemType型別的變數e，再定義個該型別的指標變數pe指向變數e（pe>>e），向函式傳入指標變數pe即可，
2.1.2.4 順序表的查找 int LocateElem(SqList List,ELemType e)
演算法步驟：
①從第一個元素開始，依次與查找的元素e進行比較，若有e==List.elem[i],回傳其位置i+1，
②未查到，查找失敗，
//4.查詢線性表中有無與e值相同的元素，有回傳其位置，無回傳0
int LocateElem(SqList List,ElemType e)
{
int i;
for(i=0;i<List.length;i++)
{
if(List.elem[i]==e)
{
printf("\n查找成功!!!");
return i+1;
}
}
printf("\n未找到");
return 0;
}
Tip：①若所查找的元素值在順序表中有多個，這里只回傳第一個的位置（從第一個元素開始比較），
2.1.2.5 順序表的洗掉 int ListDelete(SqList *L,int i)
演算法步驟：
①先判斷洗掉位置i的合法性（1<= i <=n），
②將第i+1個到第n個元素依次向前移動一個位置
③洗掉成功，表長-1，
//5.洗掉i位置的元素
int ListDelete(SqList *L,int i)
{
if(i<1||i>(*L).length)
{
printf("\n洗掉位置違法！！！");
return -1;
}
else
{
int j;
for(j=i-1;j<(*L).length-1;j++)
{
(*L).elem[j]=(*L).elem[j+1];
}
(*L).length--;
printf("\n洗掉成功！！！");
return 0;
}
}
2.1.2.6 順序表的列印 int ListAll(SqList List)
演算法步驟：
①首先判斷順序表是否為空表，
②若不為空表，從第一個元素List.elem[0]開始回圈列印所有元素，
//列印線性表的所有元素
int ListAll(SqList List)
{
if(List.length==0)
{
printf("\n該表為空表");
return -1;
}
int i;
printf("\n輸出表中所有元素：\n");
for(i=0;i<List.length;i++)
{
printf("%d ",List.elem[i]);
}
return 0;
}
2.1.2.7 主函式的實作
int main()
{
int num,i; //初始線性表元素個數num
SqList List;
SqList *L;
L=&List;
InitList(L); //初始化順序表,建立空表
printf("\n請輸入要輸入的線性表元素個數");
scanf("%d",&num);
for(i=0;i<num;i++)
{
printf("\n請輸入第%d個元素：",i+1);
scanf("%d",&List.elem[i]);//給順序表一些元素賦一些值得到一個不為空的初始表
List.length++;
}
printf("請輸入要插入的元素資料：");
ElemType e;
ElemType *pe;
pe=&e;//指標pe指向變數e
scanf("%d",&e);
printf("請輸入要插入的位置：");
scanf("%d",&i);
ListInsert(L,i,e);//在位置i插入元素e
ListAll(List);//順序表的列印
printf("\n請輸入想要取出元素的位置：");
scanf("%d",&i);
if(GetElem(List,i,pe)==0)//取位置為i的元素
{
printf("\n位置合法查詢成功：%d位置的元素為%d",i,e);
}else
{
printf("\n位置不合法查詢元素失敗");
}
printf("\n請輸入要查找其位置的元素：");
scanf("%d",&e);
int locat=LocateElem(List,e);//查找元素e的位置
if(locat==0)
{
printf("\n線性表中無此元素");
}
else
{
printf("\n元素%d的位置為：%d",e,locat);
}
printf("\n請輸入要洗掉元素的位置：");
scanf("%d",&i);
ListDelete(L,i);//洗掉位置i的元素
ListAll(List);//順序表的列印
free(List.elem);//釋放順序表的記憶體空間
return 0;
}
2.1.2.8 結果演示
注意：本文章所有代碼連起來，即可運行（當然開頭匯入兩個頭檔案），
#include<stdio.h>
#include<stdlib.h>
#線性表鏈式存盤結構的特點是：用一組任意的存盤單元存盤線性表的資料元素（這組存盤單元可以是連續的，也可以是不連續的）， 結點：可以理解為自定義的結構類，包括資料域和指標域兩個成員， 資料域：即存放保存的資料的地方， 指標域：存放指向結點的指標，通過指向下一結點來表示前后關系， 頭指標：指向頭結點的指標， 頭結點：是個結點，當一般頭結點資料域無意義，其指標域指向首元結點， 首元結點：真正存放資料的第一個結點
2.2 線性表的鏈式表示和實作
2.2.1 單鏈表的定義和表示
typedef int ElemType;
typedef struct LNode
{
ElemType data;//結點的資料域，這里存的是自定義學生型別資料
struct LNode *next; //結點的指標域，指向下一結點
}LNode,*LinkList;
Tip：①這里最后一行LNodex相當于給自定義結構型別struct LNode取別名，后面可直接用LNode型別定義新結點，
②這里的*LinkList定義了一個指向LNodel型別的指標型別，即指向結點的指標型別，如定義LinkList L，L就是一個LNode型別的指標變數，指向結點，是一級指標，
③鏈表和順序表的空間分配有些不同，順序表是預分配，類似陣列，事先分配一定大小的空間，不夠可以擴大，而鏈表是每次給加入的結點分配記憶體，所以他們的記憶體地址并不連續，
2.2.2 單鏈表的基本操作與實作
2.2.2.1 單鏈表的初始化 int InitList(LinkList *L)
演算法步驟：①讓頭指標作為分配空間的基地址來分配空間給頭結點，
②使頭結點的指標域指向為空，即為空表，
//1.單鏈表的初始化
int InitList(LinkList *L)//指標L為二級指標：指向頭指標的指標
{//構造一個空的單鏈表
(*L)=(LinkList)malloc(sizeof(LNode));//給頭指標作為空間的基地址，分配空間
(*L)->next=NULL;//頭結點的指標域為空
printf("空鏈表創建成功！！！");
return 0;
}
Tip：①L為二級指標，指向一個（指向結點的）指標，這里*L為頭指標，指向頭結點
②(*L)代表頭指標，頭指標是指向頭結點的，則(*L)->next代表頭結點的next不熟悉的可看本文底部，pi->data和i.data的理解，
2.2.2.2 頭插法創建（插入結點）單鏈表 int CreateListHead(LinkList *L,int n)
演算法步驟：
①定義一個新結點*p給其分配空間，
②給新結點*p的資料域賦值，
③將新結點*p插入到頭結點后面，
//2（1）創建一個單鏈表--向單鏈表（頭插法）插入一些結點（資料域有值）
int CreateListHead(LinkList *L,int n)
{
LinkList p;//定義一個用來指向新結點的指標
int i;
srand((int)time(0));//使每次運行亂數不同
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(LNode));//為新結點*p分配空間
p->data=https://www.cnblogs.com/qmstudy/p/rand()%10+1;
printf("testing:頭插法第%d次插入資料%d\n", i + 1, p->data);
p->next=(*L)->next;//新加入的*p結點的指標域指向末尾（NULL）
(*L)->next=p;//頭結點的指標域指向新結點*p
}
printf("鏈表（頭插法）插入結點成功\n");
return 0;
}
2.2.2.3 尾插法創建（插入結點）單鏈表 int CreateListTail(LinkList *L,int n)
演算法步驟：
①定義一個新結點*p給其分配空間，
②給新結點*p的資料域賦值，
③將新結點*p插入到尾結點后面，
//2（2）創建一個單鏈表--向單鏈表（尾插法）插入一些結點（資料域有值）
int CreateListTail(LinkList *L,int n)
{
LinkList p,t;//指標p指向新結點，指標t用來指向當前鏈表尾結點
t=(*L);
while(t->next)
{
t=t->next;
} //該回圈結束，指標t指向當前鏈表尾結點
int i;
srand((int)time(0));//每次亂數不同
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(LNode));//為新結點*p分配空間
p->data=https://www.cnblogs.com/qmstudy/p/rand()%100+1;
printf("testing:尾插法第%d次插入資料%d\n", i + 1, p->data);
p->next=NULL;//新結點*p加在鏈表尾部所以*p結點的指標域為空
t->next=p;//加入新結點*p前的尾結點的指標域指向加入的*p結點
t=p;//加入新結點后指標t繼續指向當前鏈表尾結點
}
printf("鏈表（尾插法）插入結點成功\n");
return 0;
}
Tip：①頭插法是將新結點插到頭結點后面，結果是倒序的，
②尾插法是將新結點插到尾結點后面，結果正序，
2.2.2.4 鏈表的長度獲取 int GetLength(LinkList *L)
演算法步驟：
①在函式內用length計結點個數，
②從首元結點開始判斷，若存在則length+1，
③回傳length值，
//3.獲取鏈表長度（結點個數）
int GetLength(LinkList *L)
{
LinkList p;
int length=0;
p=(*L);//指標p指向頭結點
while(p->next)//第一次是判斷有沒有首元結點
{
length+=1;
p=p->next;
}
return length;
}
Tip：①若鏈表為空表，則length為0，
2.2.2.5 單鏈表的取值 int GetElem(LinkList *L,int i,ElemType *e)
演算法步驟：
①指標p指向頭結點，j來計數j初始值為0（頭結點對應位置0），
②從頭結點開始依次順著指標域判斷，指標域不為空則，
1.p指向下一結點，
2.計數器j+1，
3.判斷j是否與i相等，相等則找到位置i的值賦值給*e，
③②無結果則i不合法，
//4.取鏈表第i個元素
int GetElem(LinkList *L,int i,ElemType *e)
{
LinkList p;
int j=0;
p=(*L);//指標p指向頭結點
while(p->next)
{
j+=1;
p=p->next;
if(j==i)
{
*e=p->data;
printf("\n查找成功!!!");
printf("\n%d位置的結點資料域值為：%d",i,*e);
return 0;
}
}
printf("\n輸入的位置i不合法！！！（大于鏈表長度或小于1）");
return -1;
}
Tip：①引數中e為指向ElemType型別變數的指標變數，所以取值結果不需回傳，只需將結果賦值給*e即可，
2.2.2.6 單鏈表的查找 LinkList LocateElem(LinkList *L,ElemType e,int *pi)
演算法步驟：
①指標p指向首元結點，
②從首元結點開始順著指標域判斷，若存且資料域不與e相同繼續往下查找，
③回傳p，查找成功p為該結點地址值，失敗則p為null（尾結點的指標域為空），
//5.查找鏈表中是否有元素e，如果有回傳其結點地址
LinkList LocateElem(LinkList *L,ElemType e,int *pi)
{
LinkList p=(*L)->next;//指標p指向首元結點·
*pi=1;//首元結點位置為1
while(p&&p->data!=e)
{
p=p->next;//沒找到回圈到鏈表末尾，指標p為NULL
(*pi)++;
}
return p;
}
2.2.2.7 單鏈表的插入 int ListInsert(LinkList *L,int i,ElemType e)
演算法步驟：
①查找結點ai-1并由p指向該結點，
②定義一個新結點*s，其資料域賦值為e，
③將新結點*s的指標域指向結點ai，
④將結點*p的指標域指向新結點*s，
//6.在位置i插入結點（即插入到a（i-1）與a（i）之間）；插入結點---》插入了一元素
int ListInsert(LinkList *L,int i,ElemType e)
{
LinkList p=(*L);//P指向頭結點
int j=0;//頭結點對應位置0
while(p&&j<i-1)//若插入位置合法---屬于[1,n+1]回圈結束，指標p指向第（i-1）個結點,
{
p=p->next;
j++;
}
if(!p||j>i-1)//位置i大于（鏈表長度n）+1，或i<1
{
printf("\n插入位置位置i=%d非法！！！",i);
return -1;
}
LinkList s=(LinkList)malloc(sizeof(LNode));//生成新的結點*s（即將插入元素所在的結點）
s->data=https://www.cnblogs.com/qmstudy/p/e;//將資料e賦值到結點*s的資料域
s->next=p->next;//*p代表a（i-1）結點，將結點*s的指標域指向結點a（i）
p->next=s;
printf("\n在位置：%d插入元素：%d成功",i,e);
return 0;
}
Tip：①實際上就是定一個新結點將其插入到結點ai-1和結點ai之間，
2.2.2.8 單鏈表的洗掉 int ListDelete(LinkList *L,int i)
原理步驟：
①找到結點a(i-1)由指標p指向該結點，
②臨時保存待洗掉的結點a(i)的地址于q中，以備釋放資源，
③將a(i-1)結點的指標域指向a(i+1)結點，
④釋放結點a(i)的空間，
//7.洗掉鏈表的第i個結點
int ListDelete(LinkList *L,int i)
{
LinkList p,q;//指標q用于保存待洗掉結點a(i)的地址，已備釋放資源
int j=0;
p=(*L);//指標p指向頭結點
while(p->next&&j<i-1)//若位置i合法回圈結束指標p指向結點a(i-1)
{
p=p->next;
j++;
}
if(!(p->next)||j>i-1)
{
printf("\n位置：%d非法！！！",i);
return -1;
}
q=p->next;
p->next=p->next->next;
free(q);//釋放洗掉的結點的空間
printf("\n洗掉位置為%d的結點成功",i);
return 0;
}
Tip：①插入和洗掉的差異性，
2.2.2.9 單鏈表的清空 int ListClear(LinkList *L)
//8.清空鏈表
int ListClear(LinkList *L)
{
LinkList p,temp;
p=(*L)->next;//指標p指向首元結點
if(p==NULL)
{
printf("\n該鏈表是空表無需清空！！！");
return -1;
}
while(p)
{
temp=p;
p=p->next;
free(temp);
}
(*L)->next=NULL;
printf("\n鏈表已清空");
return 0;
}
2.2.2.10 單鏈表的列印 void PrintfList(LinkList *L)
//列印鏈表所有結點的資料域的值
void PrintfList(LinkList *L)
{
printf("\n----------列印整個鏈表----------\n");
LinkList p;
int i=0;
p=(*L)->next;//p指向首元結點
if(p==NULL)
{
printf("\n這是一個空鏈表");
}
while(p)
{
i++;
printf("%d（%d）->",p->data,i);
p=p->next;
}
}
2.2.2.11 主函式的實作
int main()
{
LinkList HeadL;//頭指標
LinkList *L;//指向頭指標的指標（二級指標）
//LNode LNode;//頭結點
//HeadL=&LNode;//頭指標HeadL指向頭結點
L=&HeadL;//二級指標L指向一級指標HeadL
InitList(L);//初始化鏈表
int n;
printf("\n請輸入鏈表插入（頭插法）元素個數：");
scanf("%d",&n);
CreateListHead(L,n);//頭插法插入若干結點（資料域有值）
PrintfList(L);//列印鏈表
printf("\n鏈表長度（除頭結點結點個數）：%d",GetLength(L));
printf("\n請輸入鏈表插入（尾插法）元素個數：");
scanf("%d",&n);
CreateListTail(L,n);//尾插法插入若干結點（資料域有值）
PrintfList(L);//列印鏈表所有結點的資料域值
printf("\n鏈表長度（除頭結點結點個數）：%d",GetLength(L));
ElemType e;
ElemType *pe;
pe=&e;
printf("\n請輸入要查找元素位置i=");
int i;//變數i后面多次使用位置i
int *pi;
pi=&i;
scanf("%d",&i);
GetElem(L,i,pe);//取出位置為i的結點的資料域的值
printf("\n請輸入要查找的元素e：");
scanf("%d",&e);
if(LocateElem(L,e,pi)==NULL)
{
printf("\n未找到該元素");
}else
{
printf("\n%d位于第%d個結點中",e,i);
}
printf("\n請輸入要插入的資料：");
scanf("%d",&e);
printf("\n請輸入要插入的位置：");
scanf("%d",&i);
ListInsert(L,i,e);//在位置i插入資料域值為e的結點
PrintfList(L);//列印鏈表
printf("\n請輸入要洗掉結點的位置：");
scanf("%d",&i);
ListDelete(L,i);//洗掉鏈表第i個結點
PrintfList(L);//列印鏈表
ListClear(L);//清空鏈表
PrintfList(L);//列印鏈表
return 0;
}
2.2.2.12 結果演示
注意：代碼連起來，即可運行（當然開頭匯入兩個頭檔案），
#include<stdio.h>
#include<stdlib.h>
2.2.3 回圈鏈表
回圈鏈表(CircularLinked List)：是另一種形式的鏈式存盤結構，其特點是表中最后一個結點的指標域指向頭結點，整個鏈表形成一個環，由此，從表中任一結點出發均可找到表中其他結點，下圖所示為單鏈的回圈鏈表，類似地，還可以有多重鏈的回圈鏈表，
回圈單鏈表的操作和單鏈表的差別僅在于：當鏈表遍歷時，判別當前指標p是否指向表尾結點的終止條件不同， 如表：
| 鏈表型別 | 當前指標p是否指向表尾結點的終止條件 |
| 單鏈表 | p!=NULL或p->next!=NULL |
| 回圈鏈表 | p!=L或p->next!=L |
2.2.4 雙向鏈表
以上討論的鏈式存盤結構的結點中 只有一個指示 直接后繼的指標域， 由此， 從某個結點 出發只能順指標向后尋查其他結點， 若要尋查結點的直接前驅，則必須從表頭指標出發， 換句話說，在單鏈表中，查找直接后繼結點的執行時間為 0(1), 而查找直接前驅的執行時間為O(n)， 為克服單鏈表這種單向性的缺點，可利用雙向鏈表 (Double Linked List)，雙向鏈表：相比單鏈表，其有兩個指標域，一個指向直接前驅，一個指向直接后繼，
2.2.4.1 雙向鏈表的定義和表示
typedef int ElemType;
typedef struct DuLNode
{
struct DuLNode *prior;//用于指向直接前驅的指標域
ElemType data;//資料域
struct DuLNode *next;//用于指向直接后繼的指標域
}DuLNode,*DuLinkList;
#在雙向鏈表中， 有些操作（如 ListLength、GetElem 和 LocateElem 等）僅需涉及一個方向的指標，則它們的演算法描述和線性鏈表的操作相同，但在插入、洗掉時有很大的不同，
2.2.4.2 雙向鏈表的基本操作與實作
2.2.4.2.1 雙向鏈表的初始化
//雙向鏈表的初始化
int InitList_DuL(DuLinkList *L)
{
(*L)=(DuLinkList)malloc(sizeof(DuLNode));//以頭指標（*L）作為分配空間的基地址
(*L)->next=NULL;//頭結點的后繼指標域設為空
(*L)->prior=NULL;//頭結點的前驅指標設為空
printf("空的雙向鏈表創建成功！！！");
return 0;
}
Tip：①雙向鏈表的初始化和單鏈表基本一致，這里將頭結點的前驅指標域賦值為空，方便后面測驗前驅指標域是否兩兩相連
2.2.4.2.2 頭插法創建雙向鏈表
這里就先講一下雙向鏈表的插入，單鏈表只需改動后繼指標域next，而雙向鏈表還要改動前驅指標域prior，
值得注意的是是否在尾結點后面插入，其操作也有所不同，
尾部插入：
非尾部插入：
//頭插法創建雙鏈表
int CreateListHead_DuL(DuLinkList *L,int n)
{
DuLinkList p;//指向新結點的指標
int i;
srand((int)time(0));//使每次運行程式產生的亂數不同
for(i=0;i<n;i++)
{
p=(DuLinkList)malloc(sizeof(DuLNode));
p->data=https://www.cnblogs.com/qmstudy/p/rand()%100+1;
if((*L)->next!=NULL)//如果，存在首元結點
{
(*L)->next->prior=p;//首元結點的前驅指標域指向新結點*p
}
p->next=(*L)->next;//結點*p的后繼指向首元結點，第一次為空，
(*L)->next=p;//頭結點的后繼指標域指向新結點*p
p->prior=(*L);//新結點的前驅指標域指向頭結點
printf("testing:頭插法第%d次插入資料%d\n", i + 1, p->data);
}
printf("鏈表（頭插法）插入結點成功\n");
return 0;
}
Tip：①考慮到尾部插入和非尾部插入操作有些不同，演算法中進行了插入位置是否為尾部的判斷，
②當然這里是頭插法，只需判斷是否存在首元結點即可（在頭結點后插入結點），
2.2.4.2.3 雙向鏈表的插入
以上已經講述插入的方法，知曉其與單鏈表插入的異同，還需要注意尾部和非尾部插入的情況，
//雙向鏈表的插入(插入到末尾時有所不同)
int ListInsert_DuL(DuLinkList *L,int i,ElemType e)
{
DuLinkList p;
p=(*L);//指標p指向頭結點
int j=0;
while(p&&j<i-1)//回圈結束如果i位置合法，p指向第（i-1）個結點
{
j++;
p=p->next;
}
if(!p||j>i-1)
{
printf("\n插入位置位置i=%d非法！！！",i);
return -1;
}
DuLinkList s=(DuLinkList)malloc(sizeof(DuLNode));//定義個新結點*s
s->data=https://www.cnblogs.com/qmstudy/p/e;
s->next=p->next;//新結點*s的后繼指標域指向第i個結點(第i-1個結點為尾結點時指向空),
if(p->next)//如果第（i-1）個結點不是尾結點（在兩個結點中插入），
{
p->next->prior=s;//第i個結點的前驅指標域指向新結點*s
}
s->prior=p;//新結點*s的前驅指標域指向第i-1個結點
p->next=s;//第i-1個結點的后繼指標域指向新結點*s
printf("\n在位置：%d插入元素：%d成功",i,e);
return 0;
}
Tip：①考慮到尾部插入和非尾部插入操作有些不同，演算法中進行了插入位置是否為尾部的判斷，
2.2.4.2.4 雙向鏈表的洗掉
雙向鏈表的洗掉操作和單鏈表不同，和插入類似，尾部結點和非尾部結點的洗掉情況也不同，
尾部結點洗掉：
非尾部結點洗掉：
//雙向鏈表的洗掉（洗掉尾結點有所不同）
int ListDelete_DuL(DuLinkList *L,int i)
{
DuLinkList p,q;
p=(*L);//p指向頭結點
if(!p->next)
{
printf("\n該表為空！！！");
}
int j=0;
while(p->next&&j<i)//回圈結束指標p指向第i個結點
{
j++;
p=p->next;
}
if(!p||j>i)
{
printf("\n要洗掉的位置i非法！！！");
return -1;
}
q=p;//存放要洗掉的結點的地址
p->prior->next=p->next;//-------------------------------------------------①
if(p->next)//如果i位置的結點不是尾結點,后繼結點不為空，
{
p->next->prior=p->prior;//--------------------------------------------②
}
free(q);//洗掉結點后釋放其空間
printf("\n洗掉位置為%d的結點成功",i);
return 0;
}
Tip：①注意區分洗掉尾結點和非尾結點的情況，
1.為什么單鏈表的插入和洗掉沒有這種差別呢？
小明：這種差別其實是對雙鏈表的前驅指標域操作造成的
①插入：插入一個新結點，假如是在兩結點直接插入，所插入結點的直接后繼結點的前驅指標域需指向所插入結點，假如是在尾部插入，所插入結點無后繼（后繼指標域指向為空），則不存在對后面結點的前驅指標域的操作，因為所插入結點的直接后繼結點不存在，
②洗掉：洗掉一個結點，假如洗掉非尾部結點，所洗掉的結點有直接后繼結點，直接后繼結點的前驅指標域需指向所洗掉結點的直接前驅結點，假如是洗掉尾部結點，則所洗掉無直接后繼結點，無對直接后繼結點的前驅指標域的操作，
2.那為什么第一個結點和非第一個沒有這種差別呢？
小明：小編文章講的表都是帶頭結點的，第一個結點一定有一個直接前驅那就是頭結點，
2.2.4.2.5 雙向鏈表的列印
//雙向鏈表的列印
int PrintfDuList(DuLinkList *L)
{
printf("\n----------列印整個鏈表----------\n");
int i=0;
DuLinkList p;
p=(*L)->next;
if(p==NULL)
{
printf("\n這是一個空表！！！");
return -1;
}
while(p)
{
i++;
printf("%d（%d）->",p->data,i);
p=p->next;
}
return 0;
}
2.2.4.2.6 雙向鏈表前驅指標域連接的判斷
原理步驟：
①先找到尾結點，
②從尾結點開始順著前驅指標域依次將每個結點的資料域的值輸出，
//測驗前驅指標域是否兩兩相連，從尾結點順著前驅指標域依次列印各結點的資料域的值即可
int PriorTest(DuLinkList *L)
{
DuLinkList p;
p=(*L);
int i=0;
if(!p->next)
{
printf("\n這是一個空表！！！");
return -1;
}
while(p->next)//while回圈結束p指向尾結點
{
i++;
p=p->next;
}
printf("\n從尾結點順著前驅指標域依次列印各結點的資料域的值");
while(p)
{
printf("%d（%d） ",p->data,i);
i--;
p=p->prior;
}
return 0;
}
2.2.4.2.7 主函式的實作
int main()
{
DuLinkList *L;//指向頭指標的二級指標L
DuLinkList DuListHead;//頭指標DuList
L=&DuListHead;//L指向頭指標DuList
InitList_DuL(L);//初始化雙向鏈表
printf("\n請輸入鏈表插入（頭插法）元素個數：");
int n;
scanf("%d",&n);
CreateListHead_DuL(L,n);//頭插法創建雙向鏈表
PrintfDuList(L);//列印雙向鏈表
printf("\n請輸入要插入的位置：");
int i;
scanf("%d",&i);
printf("\n請輸入要插入到%d位置的結點的資料域的值：",i);
ElemType e;
scanf("%d",&e);
ListInsert_DuL(L,i,e);//在i位置插入資料域值為e的結點
PrintfDuList(L);//列印雙向鏈表
printf("\n請輸入要洗掉結點的位置：");
scanf("%d",&i);
ListDelete_DuL(L,i);//洗掉i位置的結點
PrintfDuList(L);//列印雙向鏈表
PriorTest(L);//前驅指標域測驗
return 0;
}
2.2.4.2.8 結果演示
注意：代碼連起來，即可運行（當然開頭匯入兩個頭檔案），
#include<stdio.h>
#include<stdlib.h>
2.3 順序表和鏈表的比較
2.3.1 空間性能的比較
(1)存盤空間的分配 順序表的存盤空間必須預先分配，元素個數擴充受一定限制，易造成存盤空間浪費或空間溢位現象；而鏈表不需要為其預先分配空間，只要記憶體空間允許，鏈表中的元素個數就沒有限制，基于此，當線性表的長度變化較大，難以預估存盤規模時，宜采用鏈表作為存盤結構， (2)存盤密度的大小 鏈表的每個結點除了設定資料域用來存盤資料元素外，還要額外設定指標域，用來存盤指示元素之間邏輯關系的指標，從存盤密度上來講，這是不經濟的， 所謂存盤密度是指資料元素本身所占用的存盤量和整個結點結構所占用的存盤量之比，即 存盤密度＝ 資料元素本身占用的存盤量/結點結構占用的存盤量 存盤密度越大，存盤空間的利用率就越高， 顯然，順序表的存盤密度為1' 而鏈表的存盤密度小于1， 如果每個元素資料域占據的空間較小，則指標的結構性開銷就占用了整個結點的大部分空間，這樣存盤密度較小， 例如， 若單鏈表的結點資料均為整數，指標所占用的空間和整型量相同，則單鏈表的存盤密度為 0.5，因此，如果不考慮順序表中的空閑區，則順序表的存盤空間利用率為100%, 而單鏈表的存盤空間利用率僅為 50%，基于此，當線性表的長度變化不大，易千事先確定其大小時，為了節約存盤空間，宜采用順序表作為存盤結構，2.3.2 時間性能的比較
(1)存取元素的效率 順序表是由陣列實作的，它是一種隨機存取結構，指定任意一個位置序號'i'都可以在0(1)時間內直接存取該位置上的元素，即取值操作的效率高；而鏈表是一種順序存取結構，按位置訪問鏈表中第i個元素時，只能從表頭開始依次向后遍歷鏈表，直到找到第i個位置上的元素，時間復雜度為 O(n), 即取值操作的效率低，基于此，若線性表的主要操作是和元素位置緊密相關的這類取值操作，很少做插入或洗掉時，宜采用順序表作為存盤結構， (2)插入和洗掉操作的效率 對于鏈表，在確定插入或洗掉的位置后，插入或洗掉操作無需移動資料，只需要修改指標，時間復雜度為0(1)，而對千順序表，進行插入或洗掉時，平均要移動表中近一半的結點，時間復雜度為 O(n)， 尤其是當每個結點的資訊量較大時，移動結點的時間開銷就相當可觀，基于此，對于頻繁進行插入或洗掉操作的線性表，宜采用鏈表作為存盤結構，
*2.4 線性表的應用
2.4.1 線性表的合并
求解一般集合的并集
已知集合A={0,6,1,2}，集合B={0,7,2,1}，求集合A,B的并集，易得他們的并集{0,6,1,2,7},下面通過運用線性表來進行操作，
演算法步驟：
①我們可以創建兩個順序表LA,LB,
②把集合A的成員插入表LA中，集合B的成員插入表LB中，
③從表LB第一個元素開始，每次與表LA所有元素進行比較，
④如果無相同的元素，則將其元素值賦值到LA中，否則不操作----這里可用查找函（LocateElem）數進行判斷，
void BinJi(List *LA,List *LB)
{//將所有在線性表 LB中但不在LA中的資料元素插入到LA中
int m=ListLength(LA); //求線性表的長度
int n=ListLength(LB); //求線性表的長度
ElemType e,*pe;
pe=&e;
for(i=l;i<=n;i++)
{
GetElem(LB,i,pe); //取 LB中第l.個資料元素賦給 e
if (! LocateElem (LA, e)) //LA中不存在和 e 相同的資料元素
Listinsert(LA,++m,e);//將 e 插在LA的最后
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298006.html
標籤：其他