鏈?zhǔn)奖硎?/h5>
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的得存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素（這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）。因此，為了表示ai和ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來(lái)說，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼存儲(chǔ)位置的信息。這兩部分信息組成ai的存儲(chǔ)映像，稱為結(jié)點(diǎn)（node）。
結(jié)點(diǎn)包括兩個(gè)域：其中存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域。指針域中存儲(chǔ)的信息稱作指針或鏈。n個(gè)結(jié)點(diǎn)鏈組成一個(gè)鏈表，即為線性表的鏈式存儲(chǔ)結(jié)構(gòu)。由于每個(gè)節(jié)點(diǎn)中只包含一個(gè)指針域，故又稱線性鏈表或單鏈表。
元素定義
typedef int ElemType;
單鏈表定義
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList; // 帶頭結(jié)點(diǎn)線性鏈表
我們?cè)趩捂湵淼牡谝粋€(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)如線性表長(zhǎng)度等類的附加信息，頭結(jié)點(diǎn)的指針指向第一個(gè)元素結(jié)點(diǎn)的存儲(chǔ)位置。
鏈?zhǔn)酱鎯?chǔ)
在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間沒有固定的聯(lián)系。然后，每個(gè)元素的存儲(chǔ)位置都包含在其直接前驅(qū)結(jié)點(diǎn)的信息之中，由此在單鏈表中，去得第i個(gè)數(shù)據(jù)元素必須從頭指針出發(fā)尋找。因此單鏈表是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，這種存儲(chǔ)結(jié)構(gòu)相對(duì)于順序存儲(chǔ)結(jié)構(gòu)，具有空間利用合理，插入和刪除時(shí)不需要移動(dòng)等優(yōu)點(diǎn)，因此在很多場(chǎng)合下，鏈?zhǔn)酱鎯?chǔ)是線性表的首選存儲(chǔ)結(jié)構(gòu)。
基本操作
#include <stdio.h>
#include <stdlib.h>
#define FAILURE -1
#define SUCCESS 1
typedef int ElemType; // 元素定義
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList; // 帶頭結(jié)點(diǎn)
int compare(ElemType e1, ElemType e2){
// 比較e1和e2元素是否相同，具體實(shí)現(xiàn)和ElemType類型有關(guān)
if(e1 == e2)
return SUCCESS;
else
return FAILURE;
}
int visit(ElemType e){
// 訪問e元素，具體實(shí)現(xiàn)和ElemType類型有關(guān)
printf("%d ", e);
return SUCCESS;
}
void InitList_L(LinkList *L){
// 初始化線性鏈表，L指向data為空的頭結(jié)點(diǎn)
*L = (LinkList)malloc(sizeof(LNode));
if (!*L) exit(-1); //創(chuàng)建頭結(jié)點(diǎn)失敗
(*L)->next = NULL;
}
void DestroyList_L(LinkList *L){
// 銷毀單鏈表, 不僅釋放數(shù)據(jù)節(jié)點(diǎn)，也銷毀頭結(jié)點(diǎn)
LinkList p = *L; //頭結(jié)點(diǎn)
LinkList np;
while(p){
np = p->next;
free(p);
p = np;
}
*L = NULL;
}
void ClearList_L(LinkList *L){
// 帶頭結(jié)點(diǎn)的鏈表,僅清除數(shù)據(jù)節(jié)點(diǎn)
LinkList p = (*L)->next;
LinkList np;
while(p){
np = p->next;
free(p);
p = np;
}
(*L)->next = NULL;
}
int ListEmpty_L(LinkList L){
if(L->next == NULL)
return SUCCESS;
else
return FAILURE;
}
int ListLength_L(LinkList L){
// 返回單鏈表的長(zhǎng)度
int i = 0;
while(L->next){
i++;
L = L->next;
}
return i;
}
int GetElem_L(LinkList L, int i, ElemType *e){
// 用e返回線性表L中第i位置元素
// 其中1<=i<=L.length
int p = 1;
L = L->next;
while(L && p < i){
p++;
L = L->next;
}
if(!L || p > i) return FAILURE;
*e = L->data;
return SUCCESS;
}
int LocateElem_L(LinkList L, ElemType e, int (*compare)(ElemType, ElemType)){
// 從L中查找第一個(gè)與e元素滿足compare函數(shù)關(guān)系的元素
// 如果不存在則返回0
int p = 1;
L = L->next;
while(L){
if(compare(L->data, e) > 0){ // 找到
return p;
} else{
L = L->next;
p++;
}
}
return FAILURE;
}
int PriorElem_L(LinkList L, ElemType cur_e, ElemType *pre_e){
// 若cur_e是L中元素且不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則失敗
LinkList pre, cur;
pre = L;
cur = L->next;
if(cur->data == cur_e) return FAILURE; //第一個(gè)位置
while(cur && cur->data != cur_e){
pre = cur;
cur = cur->next;
}
if(!cur) return FAILURE;
*pre_e = pre->data;
return SUCCESS;
}
int NextElem_L(LinkList L, ElemType cur_e, ElemType *next_e){
// cur_e是L中元素且不是最后一個(gè)，則用next_e返回它的后繼元素
LinkList cur, next;
cur = L;
next = cur->next;
while(next && cur->data != cur_e){
cur = next;
next = next->next;
}
if(!next) return FAILURE;
*next_e = next->data;
return SUCCESS;
}
int InsertList_L(LinkList L, int i, ElemType e){
// 在帶頭結(jié)點(diǎn)的L中第i位置之前插入e
LNode *p = L; // p指向L頭結(jié)點(diǎn)
int j=0;
while(p && j<i-1){
p = p->next;
j++;
}
if(!p || j > i-1) return FAILURE; // i值不合理
LNode *s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return SUCCESS;
}
int DeleteList_L(LinkList L, int i, ElemType *e){
// 刪除線性鏈表L中第i位置節(jié)點(diǎn)，并由e返回
LNode *p = L;
int j = 0;
while(p && j<i-1){
p = p->next;
j++;
}
if(!p || j>i-1) return FAILURE;
// 此時(shí)p指向第i-1位置節(jié)點(diǎn)
// q指向待刪除節(jié)點(diǎn)
LNode *q = p->next;
// 移除節(jié)點(diǎn)
p->next = p->next->next;
// 將值返回
*e = q->data;
free(q);
return SUCCESS;
}
int ListTraverse_L(LinkList L, int (*visit)(ElemType)){
// 對(duì)L中每一個(gè)元素調(diào)用visit函數(shù)，一旦visit失敗，則操作失敗
L = L->next;
while(L){
if(visit(L->data) < 0) return FAILURE;
L = L->next;
}
return SUCCESS;
}
void MergeList_L(LinkList La, LinkList Lb, LinkList *Lc){
// 歸并兩個(gè)有序線性鏈表，要求結(jié)果也有序排列
LNode *pa = La->next, *pb = Lb->next;
LNode *pc;
*Lc = pc = La; // Lc以La頭結(jié)點(diǎn)為頭結(jié)點(diǎn)
while(pa && pb){
if(pa->data <= pb->data){
pc->next = pa;
pa = pa->next;
} else{
pc->next = pb;
pb = pb->next;
}
pc = pc->next;
}
// 歸并剩余結(jié)點(diǎn)
pc->next = pa ? pa:pb;
free(Lb); // 釋放Lb頭結(jié)點(diǎn)
}
void difference(LinkList La, LinkList Lb){
// 計(jì)算帶頭結(jié)點(diǎn)的線性鏈表La和Lb的差集，并將結(jié)果保存在La鏈表中
LinkList pa = La;
while(pa->next){
LinkList pb = Lb->next;
while(pb && pb->data != pa->next->data) pb = pb->next;
if(!pb) pa = pa->next; // 沒有在pb中找到
else { // 在pb中找到
LinkList tem = pa->next;
pa->next = pa->next->next;
free(tem);
}
}
}
void main(){
// 聲明線性列表L
LinkList L;
// 初始化線性列表，令L指向頭結(jié)點(diǎn)
printf("****************** init list *************\n");
InitList_L(&L);
// 頭結(jié)點(diǎn)位置
printf("L position is: %p\n", L);
// 頭結(jié)點(diǎn)中data值
printf("L data is: %d\n", L->data);
// 插入值
printf("*********** insert value ************\n");
int a[] = {1, 3, 4, 5, 10, 5, 7};
int i;
for(i=0;i<7;i++){
InsertList_L(L, i+1, a[i]);
}
printf("插入值后：\n");
ListTraverse_L(L, visit);
// get elem
printf("\n****************** get elem from L*************\n");
ElemType e1, e2;
if(GetElem_L(L, 0, &e1) > 0){
printf("get elem at index 0 success, reutrn value: %d\n", e1);
} else {
printf("get elem at index 0 failure\n");
}
if(GetElem_L(L, 4, &e2) > 0){
printf("get elem at index 4 success, return value: %d\n", e2);
} else {
printf("get elem at index 4 failure\n");
}
if(GetElem_L(L, 20, &e2) >0){
printf("get elem at index 20 success, return value: %d\n", e2);
} else {
printf("get elem at index 20 failure.\n");
}
// locate elem
printf("\n***************** locate elem *************** \n");
int index1, index2;
index1 = LocateElem_L(L, -10, compare);
index2 = LocateElem_L(L, 7, compare);
if(index1 > 0){
printf("locate -10 in L success, index at: %d\n", index1);
} else {
printf("locate -10 in L failure!\n");
}
if(index2 > 0){
printf("locate 7 in L success, index at: %d\n", index2);
} else {
printf("locate 7 in L failure!\n");
}
// prior elem
printf("\n*********** prior elem *************\n");
ElemType pre_e1, pre_e2;
if(PriorElem_L(L, 1, &pre_e1) > 0){
printf("find prior elem of 1 in L success, value is: %d\n",
pre_e1);
} else {
printf("find prior elem of 1 in L failure!\n");
}
if(PriorElem_L(L, 7, &pre_e2) > 0){
printf("find prior elem of 7 in L success, value is: %d\n",
pre_e2);
} else {
printf("find prior elem of 7 in L failure!\n");
}
// next elem
printf("\n************ next elem ************\n");
ElemType next_e1, next_e2;
if(NextElem_L(L, 1, &next_e1) > 0){
printf("find next elem of 1 in L success, valueu is: %d\n",
next_e1);
} else {
printf("find next elem of 1 in L failure!\n");
}
if(NextElem_L(L, 7, &next_e2) > 0){
printf("find next elem of 7 in L success, value is: %d\n",
next_e2);
} else {
printf("find next elem of 7 failure!\n");
}
// traverse
printf("\n***********traverse************\n");
if(ListTraverse_L(L, visit) > 0){
printf("traverse L success!\n");
} else {
printf("traverse L failure!\n");
}
// 刪除一個(gè)元素
ElemType e;
printf("\n**************delete elem******************\n");
if(DeleteList_L(L, 1, &e)>0){
printf("delete success at index 1, deleted value is: %d\n", e);
} else {
printf("delete failure at index 1\n");
}
printf("now elem: ");
ListTraverse_L(L, visit);
printf("\n");
if(DeleteList_L(L, 0, &e)>0){
printf("delete success at index 0, deleted value is: %d\n", e);
} else {
printf("delete failure at index 0\n");
}
if(DeleteList_L(L, 6, &e)>0){
printf("delete success at index 6, deleted value is: %d\n", e);
} else {
printf("delete failure at index 6\n");
}
// 銷毀
printf("********** destroy **************\n");
DestroyList_L(&L);
printf("L position is: %p\n", L);
// 歸并兩個(gè)順序表
printf("\n********* start Merge ****************\n");
LinkList La, Lb, Lc;
InitList_L(&La);
InitList_L(&Lb);
InitList_L(&Lc);
int la[] = {2, 4, 5, 10, 22};
int lb[] = {1, 3, 8, 10, 12, 22, 34};
for(i=0;i<5;i++){
InsertList_L(La, i+1, la[i]);
}
for(i=0;i<7;i++){
InsertList_L(Lb, i+1, lb[i]);
}
printf("La is: ");
ListTraverse_L(La, visit);
printf("\nLb is: ");
ListTraverse_L(Lb, visit);
MergeList_L(La, Lb, &Lc);
printf("\nthe merge result Lc is: ");
ListTraverse_L(Lc, visit);
printf("\n");
// 求差集
LinkList Ld, Le;
InitList_L(&Ld);
InitList_L(&Le);
int ld[] = {5, 10, 20, 15, 25, 30};
int le[] = {5, 15, 35, 25, 30};
for(i=0;i<6;i++){
InsertList_L(Ld, i+1, ld[i]);
}
for(i=0;i<5;i++){
InsertList_L(Le, i+1, le[i]);
}
printf("\n************** compute difference*****\n");
printf("Ld is: ");
ListTraverse_L(Ld, visit);
printf("\n");
printf("Le is: ");
ListTraverse_L(Le, visit);
printf("\nthe result that value in Ld and not in Le is: ");
difference(Ld, Le);
ListTraverse_L(Ld, visit);
printf("\n");
}
運(yùn)行結(jié)果
****************** init list *************
L position is: 0x24e6010
L data is: 0
*********** insert value ************
插入值后：
1 3 4 5 10 5 7
****************** get elem from L*************
get elem at index 0 failure
get elem at index 4 success, return value: 5
get elem at index 20 failure.
***************** locate elem ***************
locate -10 in L failure!
locate 7 in L success, index at: 7
*********** prior elem *************
find prior elem of 1 in L failure!
find prior elem of 7 in L success, value is: 5
************ next elem ************
find next elem of 1 in L success, valueu is: 3
find next elem of 7 failure!
***********traverse************
1 3 4 5 10 5 7 traverse L success!
**************delete elem******************
delete success at index 1, deleted value is: 1
now elem: 3 4 5 10 5 7
delete failure at index 0
delete success at index 6, deleted value is: 7
********** destroy **************
L position is: 0x7ffe356bc5f8
********* start Merge ****************
La is: 2 4 5 10 22
Lb is: 1 3 8 10 12 22 34
the merge result Lc is: 1 2 3 4 5 8 10 10 12 22 22 34
************** compute difference*****
Ld is: 5 10 20 15 25 30
Le is: 5 15 35 25 30
the result that value in Ld and not in Le is: 10 20
