鏈表
陣列作為基本的資料結構被廣泛使用在各種程式中，其查找十分方便，使用也十分簡單，但要對其進行插入和洗掉操作，花費卻十分昂貴，比如，對一個長度為n的陣列在k位置進行插入操作，首先要把k到n-1位置的資料整體后移，而洗掉k則要把k+1到n-1 的位置整體前移，為了避免插入和洗掉的開銷，我們可以使用不連續存盤的鏈表，
鏈表的存盤形式如下圖所示：
對于鏈表的插入和洗掉操作我們可以直接修改next指標，對鏈表元素進行調整
程式實作
為了編程方便我們在鏈表開頭留出一個不使用的頭節點
下面列出鏈表的宣告型別:
typedef struct{
}Item; //鏈表的元素型別,由用戶自定義
typedef struct node {
Item elem; //節點的資料域
struct node * next; //節點的指標域
}Node;
typedef struct {
Node * head; //頭節點指標
//可保存其它資訊,如鏈表長度,指向鏈表末的指標等
}List;
/*
*創建一個鏈表
*并回傳指向鏈表的指標
*如果記憶體申請失敗，則回傳空指標
*/
List * ListCreate(void);
/*
*回傳一個bool值
*如果鏈表為空，則回傳true
*反之，則回傳false
*/
bool ListIsEmpty(List * pl);
/*
*回傳鏈表的大小
*回傳值為一個unsigned int
*/
unsigned ListSize(List * pl);
/*
*接受一個cmp函式，用于比較Item元素
*回傳第一個使cmp回傳0的節點，
*若該節點不存在，則回傳NULL
*/
Node * ListFind(List * pl, const Item * pi, int(*cmp)(const Item *, const Item *));
/*
*接受一個cmp函式，用于比較Item元素
*回傳第一個使cmp回傳0的前一個節點，
*若該節點不存在，則回傳NULL
*/
Node * ListFindPrevious(List * pl, const Item * pi, int(*cmp)(const Item *, const Item *));
/*
*將pi指向的資料插入鏈表
*插入的資料位于鏈表開始
*回傳一個指向新節點的指標
*/
Node * ListPushFront(List * pl, const Item * pi);
/*
*將pi指向的資料插入鏈表
*插入的資料位于pn指向的節點之后
*回傳一個指向新節點的指標
*/
Node * ListInsertAfter(List * pl, Node * pn, const Item * pi);
/*
*洗掉pl指向鏈表的第一個元素
*元素的值賦給pi指向的元素
*回傳一個指向被洗掉元素的下一個節點的指標
*/
Node * ListPopFront(List * pl);
/*
*洗掉pn指向節點的下一個元素
*元素的值賦給pi指向的元素
*回傳一個指向被洗掉元素的下一個節點的指標
*/
Node * ListEraseAfter(List * pl, Node * pn);
/*
*遍歷鏈表，使鏈表中每一個元素都被pfun作用
*/
void listTraverse(List * pl, void(*pfun)(Item *));
/*
*清空鏈表，使鏈表的size為0
*/
void ListClear(List * pl);
/*
*銷毀鏈表，并把pl賦為NULL
*/
void ListDestroy(List ** pl);
鏈表的創建
首先我們創建一個空表、使用malloc申請一個list空間和一個頭節點，由于元素數量不確定，所以我們在需要時再申請更多的空間，
List * ListCreate(void)
{
List * new_list = malloc(sizeof(List)); //獲得鏈表所需空間
if (new_list == NULL)
{
fprintf(stderr, "Out of memory in function: create_list()!\n");
return NULL;
}
new_list->head = make_node(NULL, NULL); //獲得一個頭節點
if (new_list->head == NULL)
{
fprintf(stderr, "Out of memory in function: create_list()!\n");
free(new_list);
return NULL;
}
return new_list;
}
在這里使用了一個輔助函式make_node()，make_node接受一個item指標和一個Node指標，把node指標作為其申請節點的next指標，如果item指標不為NULL的話，則將pi指向的值賦給申請的節點，其定義如下
Node * make_node(const Item * pi, Node * pn)
{
Node * new_node = malloc(sizeof(Node));
if(new_node!=NULL)
{
if (pi != NULL)
new_node->elem = *pi;
new_node->next = pn;
}
return new_node;
}
Node * ListFind(List * pl, const Item * pi, int(*cmp)(const Item *, const Item *))
{
Node * temp = pl->head->next;
while (temp != NULL && cmp(&temp->elem, pi) != 0)
temp = temp->next;
return temp;
}
###鏈表的洗掉
***************
如果我們要洗掉某個節點，我們通過呼叫ListFindPrevious找到符合條件節點的前一個節點
```cpp
Node * ListEraseAfter(List * pl, Node * pn)
{
Node * temp = pn->next; //洗掉pn->next指向的節點
pn->next = temp->next;
destroy_node(temp); //自定義函式，釋放temp的空間，行為與free相似
return pn->next;
}
ListFindPrevious類似于ListFind只不過回傳的是前一個節點
鏈表的插入
Node * ListInsertAfter(List * pl, Node * pn, const Item * pi)
{
Node * new_node = make_node(pi, pn->next);
if (new_node == NULL)
{
fprintf(stderr, "Out of memory in function: list_push_front()!\n");
return NULL;
}
pn->next = new_node;
return new_node;
}
其他操作
判斷鏈表為空
要判斷鏈表是否為空，只需要判斷鏈表頭節點的next指標是否為NULL就行了
bool ListIsEmpty(List * pl)
{
return pl->head->next == NULL;
}
清空鏈表
void ListClear(List * pl)
{
Node * temp = pl->head->next;
while (temp != NULL)
{
pl->head->next = temp->next;
destroy_node(temp);
temp = pl->head->next;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/67340.html
標籤：C
下一篇：互斥那點事兒（下）