文章目錄
- 一.順序表的優缺點
- 二.鏈表
- 1.鏈表的概念和結構
- 2.鏈表的實作
- 三.完整代碼實作
一.順序表的優缺點
上一篇博客講解了順序表，我們來回顧一下順序表的優缺點
缺點:
(1). 中間/頭部的插入洗掉，時間復雜度為O(N)
(2). 增容需要申請新空間，拷貝資料，釋放舊空間，會有不小的消耗，
(3). 增容一般是呈2倍的增長，勢必會有一定的空間浪費，例如當前容量為100，滿了以后增容到200，我們再繼續插入了5個資料，后面沒有資料插入了，那么就浪費了95個資料空間，
優點:
(1). 可用下標進行隨機訪問
(2).快取命中率比較高
在訪問記憶體中的一個資料時，不會只加載一個資料到快取，而是從這個資料開始加載一段資料到快取，即預加載操作
由于陣列中的資料是連續存盤的，因此順序表快取的命中率相對于鏈表更高
二.鏈表
1.鏈表的概念和結構
概念：鏈表是一種物理存盤結構上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標連接實作的
2.鏈表的實作
SList.h 檔案中功能的宣告
// 無頭+單向+非回圈鏈表增刪查改實作
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// 動態申請一個節點
SListNode* CreateSListNode(SLTDateType x);
// 單鏈表列印
void SListPrint(SListNode* plist);
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist);
// 單鏈表頭刪
void SListPopFront(SListNode** pplist);
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 單鏈表洗掉pos位置之后的值
void SListEraseAfter(SListNode* pos);
說明:
pList為指向第一個結點的指標，ppList為指向 pList 的二級指標
在test.c進行測驗時，首先將 pList 置為了空指標
功能實作：
(1). 動態申請一個結點
使用malloc函式分配一個結構體型別大小的空間，放入資料，置空指標
// 動態申請一個結點
SListNode* CreateSListNode(SListDataType x)
{
// 分配空間
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
if (newNode == NULL)
{
printf("申請結點失敗\n");
exit(-1);
}
// 放入資料
newNode->data = x;
// 置空指標
newNode->next = NULL;
return newNode;
}
(2).單鏈表列印
// 單鏈表列印
void SListPrint(SListNode* pList)
{
SListNode* cur = pList;
while (cur != NULL)
{
// 列印結點資料
printf("%d->", cur->data);
// 不斷移動cur指標，直到cur指標指向為空
cur = cur->next;
}
printf("NULL\n");
}
(3).單鏈表尾插
首先動態申請一個結點，呼叫CreateSListNode函式即可，接著分兩種情況討論
1 . 未插入過資料，此時 pList為空指標，使pList指向我們新開辟的空間即可
2 . 插入過資料，pList不為空，找到尾節點，使尾結點的next指標指向我們新開辟的空間
// 單鏈表尾插
void SListPushBack(SListNode** ppList, SListDataType x)
{
// 開辟結點
SListNode* newNode = CreateSListNode(x);
// 第一次插入資料
if (*ppList == NULL)
{
*ppList = newNode;
}
// 插入過資料
else
{
SListNode* tail = *ppList;
while (tail->next != NULL)
{
// 找到尾結點
tail = tail->next;
}
// 尾結點的next指標指向新開辟的空間
tail->next = newNode;
}
}
(4).單鏈表尾刪
單鏈表尾刪分為三種情況:
1 . 鏈表為空，不需要進行操作，直接回傳
2 .鏈表有一個結點，釋放掉當前結點，將 pList 指標置為空
3 .鏈表有兩個及以上結點，找到尾結點，釋放掉尾結點，并將尾結點之前的結點的指標域置為空
// 單鏈表尾刪
void SListPopBack(SListNode** ppList)
{
// 1.空結點
if (*ppList == NULL)
{
return;
}
// 2.一個結點
else if ((*ppList)->next == NULL)
{
free(*ppList);
*ppList = NULL;
}
// 3.兩個及以上結點
else
{
SListNode* prev = NULL;
SListNode* tail = *ppList;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
(5). 單鏈表頭插
頭插和尾插同樣需要考慮兩種情況:
1 .未插入資料，pList指標為空指標，我們新開辟一塊結構體型別大小的空間，使其 next 域指向空，最后使 pList 指標指向這塊空間
2 .已插入資料，新開辟一塊結構體型別大小的空間，使其 next 域指向 pList 所指向的空間 , 最后使 pList 指標指向這塊空間
可以看出，這兩種情況操作都是一樣的，
// 單鏈表頭插
void SListPushFront(SListNode** ppList, SListDataType x)
{
// 鏈表為空和不為空操作一樣
SListNode* newNode = CreateSListNode(x);
newNode->next = *ppList;
*ppList = newNode;
}
(6).單鏈表頭刪
頭刪和尾刪同樣分為三種情況:
1 .鏈表為空，不需要進行操作，直接回傳即可
2 .鏈表有一個結點，釋放掉該結點，將 pList 指標置為空
3 .鏈表有兩個結點及以上，釋放第一個結點，使 pList 指標指向下一個結點
其中2，3情況的操作是一樣的
// 單鏈表頭刪
void SListPopFront(SListNode** ppList)
{
// 1. 鏈表為空
if (*ppList == NULL)
{
return;
}
// 2. 鏈表有一個及以上結點
else
{
SListNode* head = *ppList;
*ppList =(*ppList)->next;
free(head);
}
}
(7).單鏈表查找
原理很簡單 , 只需遍歷鏈表即可
// 單鏈表查找
SListNode* SListFind(SListNode* pList, SListDataType x)
{
SListNode* cur = pList;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
(8).單鏈表在pos位置后插入 x
// 單鏈表在pos位置后插入 x
void SListInsertAfter(SListNode* pos, SListDataType x)
{
assert(pos);
SListNode* newNode = CreateSListNode(x);
newNode->next = pos->next;
pos->next = newNode;
}
(9).單鏈表在pos位置后洗掉 x
// 單鏈表在pos位置后洗掉 x
void SListEraseAfter(SListNode* pos)
{
assert(pos);
if (pos->next != NULL)
{
SListNode* next = pos->next;
SListNode* nextnext = next->next;
pos->next = nextnext;
free(next);
}
}
三.完整代碼實作
SList.c檔案
#include"SList.h"
// 動態申請一個結點
SListNode* CreateSListNode(SListDataType x)
{
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
if (newNode == NULL)
{
printf("申請結點失敗\n");
exit(-1);
}
newNode->data = x;
newNode->next = NULL;
return newNode;
}
// 單鏈表列印
void SListPrint(SListNode* pList)
{
SListNode* cur = pList;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
// 單鏈表尾插
void SListPushBack(SListNode** ppList, SListDataType x)
{
SListNode* newNode = CreateSListNode(x);
if (*ppList == NULL)
{
*ppList = newNode;
}
else
{
SListNode* tail = *ppList;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newNode;
}
}
// 單鏈表尾刪
void SListPopBack(SListNode** ppList)
{
// 1.空結點
// 2.一個結點
// 3.兩個及以上結點
if (*ppList == NULL)
{
return;
}
else if ((*ppList)->next == NULL)
{
free(*ppList);
*ppList = NULL;
}
else
{
SListNode* prev = NULL;
SListNode* tail = *ppList;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
// 單鏈表頭插
void SListPushFront(SListNode** ppList, SListDataType x)
{
// 鏈表為空和不為空操作一樣
SListNode* newNode = CreateSListNode(x);
newNode->next = *ppList;
*ppList = newNode;
}
// 單鏈表頭刪
void SListPopFront(SListNode** ppList)
{
// 1. 鏈表為空
if (*ppList == NULL)
{
return;
}
// 2. 鏈表有一個及以上結點
else
{
SListNode* head = *ppList;
*ppList =(*ppList)->next;
free(head);
}
}
// 單鏈表查找
SListNode* SListFind(SListNode* pList, SListDataType x)
{
SListNode* cur = pList;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 單鏈表在pos位置后插入 x
void SListInsertAfter(SListNode* pos, SListDataType x)
{
assert(pos);
SListNode* newNode = CreateSListNode(x);
newNode->next = pos->next;
pos->next = newNode;
}
// 單鏈表在pos位置后洗掉 x
void SListEraseAfter(SListNode* pos)
{
assert(pos);
if (pos->next != NULL)
{
SListNode* next = pos->next;
SListNode* nextnext = next->next;
pos->next = nextnext;
free(next);
}
}
test.c檔案
#include"SList.h"
void TestSList()
{
SListNode* pList = NULL;
SListPushBack(&pList, 1);
SListPushBack(&pList, 2);
SListPushBack(&pList, 3);
SListPushBack(&pList, 4);
SListPrint(pList);
SListPopBack(&pList);
SListPopBack(&pList);
SListPopBack(&pList);
SListPopBack(&pList);
SListPopBack(&pList);
SListPrint(pList);
SListPushFront(&pList, 5);
SListPushFront(&pList, 4);
SListPushFront(&pList, 3);
SListPushFront(&pList, 2);
SListPushFront(&pList, 1);
SListPrint(pList);
SListPopFront(&pList);
SListPopFront(&pList);
SListPopFront(&pList);
SListPopFront(&pList);
SListPopFront(&pList);
SListPrint(pList);
}
int main()
{
TestSList();
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/262089.html
標籤：其他