? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
大家好，今天我們來學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中的順序表與鏈表！源碼在最后附上
首先我們先來認(rèn)識一下順序表：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
**如上圖所示：很多人會以為數(shù)組就是順序表，順序表就是數(shù)組，這種理解時錯誤的。
數(shù)組：
數(shù)組是相同數(shù)據(jù)類型的元素按一定順序排列的的集合。數(shù)組中的元素存儲在一個連續(xù)性的內(nèi)存塊中，并通過索引來訪問。
簡單的說，數(shù)組是在物理空間中連續(xù)存儲的相同數(shù)據(jù)類型的元素的集合。
而順序表：
順序表，全名順序存儲結(jié)構(gòu)，是線性表的一種。（線性表（linear list）是數(shù)據(jù)結(jié)構(gòu)的一種，一個線性表是?n 個具有相同特性的數(shù)據(jù)元素的有限序列。線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線，但是在物理結(jié)構(gòu)上并不一定是連續(xù)的。常見的線性表：順序表、鏈表、棧、隊列、字符串等。）
順序表不僅要求數(shù)據(jù)在邏輯上是連續(xù)的一條直線，還要求用一段物理地址連續(xù)的存儲單元以存儲表中數(shù)據(jù)元素，一般情況下采用數(shù)組存儲。
總結(jié)：
順序表是在計算機(jī)內(nèi)存中以數(shù)組的形式保存的線性表，只能從頭開始連續(xù)存儲。
此處將「數(shù)組」理解為物理結(jié)構(gòu)，「順序表」理解為邏輯結(jié)構(gòu)比較合理
我們可以用數(shù)組實現(xiàn)順序表，但我們同樣可以用數(shù)組實現(xiàn)二叉樹、隊列等結(jié)構(gòu)，因此不能直接認(rèn)為順序表就是數(shù)組
在順序表中我們可以定義表中元素個數(shù)、表空間大小等變量，在數(shù)組中是沒有的
? ??
? ? ? ? ? ? ? ? ?
首先我們來學(xué)習(xí)一下順序表的靜態(tài)存儲：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
而順序表的靜態(tài)存儲又存在明顯的缺陷和不足：
不知道需要給確定的多少個空間，N給小了不夠用，N給大了會浪費。
那么如何解決這個問題呢？
在這里我們使用malloc來動態(tài)開辟空間，再使用realloc來進(jìn)行空間的管理。
順序表的動態(tài)存儲：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
在這里我們要注意realloc擴(kuò)容存在異地擴(kuò)容和原地擴(kuò)容倆種情況；
注意地址，當(dāng)你realloc的空間沒有那么大時，這里就是原地擴(kuò)容：
? ? ? ? ? ? ? ? ? ? ? ?
??
注意地址，當(dāng)你realloc的空間很大的時候，就會異地擴(kuò)容：
? ? ? ? ??
這里先讓我們簡單的來實現(xiàn)順序表的幾個功能：（完整功能最后附上源碼）
實現(xiàn)順序表的頭插，即往前邊插進(jìn)去數(shù)據(jù)：
?
實現(xiàn)順序表中間插入數(shù)據(jù)：
實現(xiàn)順序表的刪除：
通過以上學(xué)習(xí)，我們大概了解了順序表的一些基礎(chǔ)知識，那么順序表是否存在一些缺點呢？
順序表的缺點：
1.尾部插入數(shù)據(jù)還不錯，但是頭部和中間插入刪除數(shù)據(jù)，效率低下，需要挪動數(shù)據(jù)。?
2.滿了之后只能擴(kuò)容，而擴(kuò)容是有一定的消耗的，擴(kuò)容一般是存在一定的空間浪費（假如空間100已經(jīng)滿了，擴(kuò)容到200，只需要插入120個數(shù)據(jù)，那么就有80個浪費掉了）
3.一次擴(kuò)的多了，可能浪費掉了；一次擴(kuò)的少了，有需要頻繁去擴(kuò)容。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
接下來讓我們來學(xué)習(xí)鏈表：?
鏈表：鏈表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，其內(nèi)存空間不連續(xù)
而鏈表分為單鏈表和雙鏈表，我們先來學(xué)習(xí)單鏈表：
? ? ? ? ??
? ? ? ? ? ? ? ? ? ? ? ? ??
它是由一個一個結(jié)點結(jié)合在一起的，而每個節(jié)點的地址沒有關(guān)聯(lián)，都是隨機(jī)的，東一個西一個。
注意單鏈表的最后一個結(jié)點指向NULL;
這里我們簡單的定義一個單鏈表：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
?
如何去訪問鏈表里的各個結(jié)點呢：我們定義一個cur指針指向單鏈表的頭節(jié)點，然后通過cur->next來依次訪問剩下的結(jié)點，如果cur==NULL，說明鏈表訪問完了。
接下來我們來實現(xiàn)單鏈表幾個基本的功能：（完整源碼結(jié)尾附上）
單鏈表的尾插：
? ? ? ? ? ??
? ? ? ? ? ? ??
這里需要額外注意：因為phead是plist的臨時拷貝，使用要注意二級指針與一級指針的使用，當(dāng)然不使用二級指針也是可以 ，也有不同的寫法，這里這樣寫是讓大家小心注意一下其中的大坑。
單鏈表的頭插：
?
單鏈表的尾刪：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
需要注意，這里需要區(qū)分一個結(jié)點和多個結(jié)點的不同情況。
單鏈表的頭刪：
? ? ? ? ? ? ? ? ? ? ? ? ? ??
這里需要注意：我們的思路是把頭節(jié)點的指向原本頭結(jié)點的下一個結(jié)點，然后還需要free掉原本的頭節(jié)點，這里會出現(xiàn)一種很常見的錯誤：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
先free掉tmp后，就沒辦法再進(jìn)行頭結(jié)點的鏈接，丟失了地址。
而正確的寫法：（大家注意區(qū)分）
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
關(guān)于鏈表還有一個知識點，就是哨兵位：
? ? ? ? ? ? ? ? ? ? ? ? ? ?
哨兵位就是在頭節(jié)點的前面給它再加一個結(jié)點，讓它充當(dāng)頭節(jié)點，但它不存儲具體的數(shù)據(jù)，只是更方便進(jìn)行頭插頭刪等操作，哨兵位的含金量不是很高，有時候方便用來刷OJ題，這里大家簡單了解下，有興趣的朋友自己敲敲代碼試一下把。
單鏈表我們就學(xué)到這里，接下來我們學(xué)習(xí)一下雙鏈表：
這里我們先再來了解下鏈表有哪些分類：
? ? ? ??
我們注意到，單鏈表和雙鏈表的區(qū)別是：單鏈表一個結(jié)點只能指向下一個結(jié)點，而雙邊表一個結(jié)點可以指向前一個結(jié)點也可以指向后一個結(jié)點。
而循環(huán)鏈表的特殊之處則是尾結(jié)點直接指向了頭節(jié)點，實現(xiàn)了一個循環(huán)。
接下來我們先來比較一下倆種鏈表：
我們主要學(xué)習(xí)一下帶頭雙向循環(huán)鏈表：?
根據(jù)上面單鏈表的學(xué)習(xí)，我們簡單寫幾個功能讓加強(qiáng)大家對雙向鏈表的理解：
帶頭雙向循環(huán)鏈表的尾插：
? ? ? ? ? ? ? ? ? ? ? ? ?
我們可以明顯感受到，雙向循環(huán)鏈表的數(shù)據(jù)處理只需要幾個簡單的指向就可以簡單完成；
帶頭雙向循環(huán)鏈表的尾刪：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
知識的分享就結(jié)束了，接下來附上順序表與鏈表的源碼：（因為內(nèi)容較多，所以不是很全，但有具體的框架，大家可以根據(jù)自己的需要進(jìn)行補(bǔ)全）
順序表：
SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size; // 有效數(shù)據(jù)
int capacity; // 空間容量
}SL;
void SLInit(SL* psl);
void SLDestroy(SL* psl);
void SLPrint(SL* psl);
void SLCheckCapacity(SL* psl);
// 頭尾插入刪除
void SLPushBack(SL* psl, SLDataType x);
void SLPushFront(SL* psl, SLDataType x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);
// 任意下標(biāo)位置的插入刪除
void SLInsert(SL* psl, int pos, SLDataType x);
void SLErase(SL* psl, int pos);
?SeqList.c
#include"SeqList.h"
void SLInit(SL* psl)
{
assert(psl);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
void SLDestroy(SL* psl)
{
assert(psl);
if (psl->a != NULL)
{
free(psl->a);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
}
void SLPrint(SL* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
void SLCheckCapacity(SL* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType)*newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
psl->a = tmp;
psl->capacity = newCapacity;
}
}
// 10：37
void SLPushBack(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
}
void SLPushFront(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
// 挪動數(shù)據(jù)
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[0] = x;
psl->size++;
}
void SLPopBack(SL* psl)
{
assert(psl);
// 空
// 溫柔的檢查
/*if (psl->size == 0)
{
return;
}*/
// 暴力檢查
assert(psl->size > 0);
//psl->a[psl->size - 1] = -1;
psl->size--;
}
// 10:47
void SLPopFront(SL* psl)
{
assert(psl);
// 暴力檢查
assert(psl->size > 0);
int begin = 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}
// 注意pos是下標(biāo)
// size是數(shù)據(jù)個數(shù)，看做下標(biāo)的話，他是最后一個數(shù)據(jù)的下一個位置
void SLInsert(SL* psl, int pos, SLDataType x)
{
assert(psl);
assert(pos >= 0 && pos <= psl->size);
SLCheckCapacity(psl);
// 挪動數(shù)據(jù)
int end = psl->size - 1;
while (end >= pos)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[pos] = x;
psl->size++;
}
void SLErase(SL* psl, int pos)
{
assert(psl);
assert(pos >= 0 && pos < psl->size);
// 挪動覆蓋
int begin = pos + 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}Test.c：
#include<stdio.h>
#include"SeqList.h"
void TestSL1()
{
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPushBack(&sl, 6);
SLPushBack(&sl, 7);
SLPushBack(&sl, 8);
SLPushBack(&sl, 9);
SLPrint(&sl);
SLPushFront(&sl, 10);
SLPushFront(&sl, 20);
SLPushFront(&sl, 30);
SLPushFront(&sl, 40);
SLPrint(&sl);
SLDestroy(&sl);
}
void TestSL2()
{
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPrint(&sl);
SLPopBack(&sl);
SLPrint(&sl);
SLPopBack(&sl);
SLPopBack(&sl);
SLPopBack(&sl);
SLPopBack(&sl);
SLPrint(&sl);
SLPushFront(&sl, 10);
SLPushFront(&sl, 20);
SLPushFront(&sl, 30);
SLPushFront(&sl, 40);
SLPrint(&sl);
SLDestroy(&sl);
}
void TestSL3()
{
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPrint(&sl);
SLPopFront(&sl);
SLPrint(&sl);
SLPopFront(&sl);
SLPrint(&sl);
SLPopFront(&sl);
SLPrint(&sl);
SLPopFront(&sl);
SLPrint(&sl);
SLPopFront(&sl);
SLPrint(&sl);
//SLPopFront(&sl);
//SLPrint(&sl);
}
void TestSL4()
{
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPrint(&sl);
SLInsert(&sl, 2, 20);
SLPrint(&sl);
SLInsert(&sl, 6, 20);
SLPrint(&sl);
SLInsert(&sl, 0, 20);
SLPrint(&sl);
SLInsert(&sl, 10, 20);
SLPrint(&sl);
SLDestroy(&sl);
}
void TestSL5()
{
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPrint(&sl);
SLErase(&sl, 3);
SLPrint(&sl);
SLErase(&sl, 3);
SLPrint(&sl);
//SLErase(&sl, 3);
//SLPrint(&sl);
}
int main()
{
TestSL5();
return 0;
}單鏈表：?
?SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLNDataType;
// Single List
typedef struct SListNode
{
SLNDataType val;
struct SListNode* next;
}SLNode;
void SLTPrint(SLNode* phead);
void SLTPushBack(SLNode** pphead, SLNDataType x);
void SLTPushFront(SLNode** pphead, SLNDataType x);
void SLTPopBack(SLNode** pphead);
void SLTPopFront(SLNode** pphead);
SLNode* SLTFind(SLNode* phead, SLNDataType x);
// pos?
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);
// ?posλ
void SLTErase(SLNode** pphead, SLNode* pos);
void SLTDestroy(SLNode** pphead);SList.c
#include"SList.h"
void SLTPrint(SLNode* phead)
{
SLNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->val);
cur = cur->next;
}
printf("NULL\n");
}
SLNode* CreateNode(SLNDataType x)
{
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->val = x;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SLNode** pphead, SLNDataType x)
{
SLNode* newnode = CreateNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾
SLNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SLTPushFront(SLNode** pphead, SLNDataType x)
{
SLNode* newnode = CreateNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLTPopBack(SLNode** pphead)
{
// 溫柔的檢查
//if (*pphead == NULL)
// return;
// 空
assert(*pphead);
// 1、一個節(jié)點
// 2、一個以上節(jié)點
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
// 找尾
/*SLNode* prev = NULL;
SLNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;*/
SLNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
void SLTPopFront(SLNode** pphead)
{
assert(*pphead);
SLNode* tmp = *pphead;
free(tmp);
*pphead = (*pphead)->next;
}Test.c文章來源：http://www.zghlxwxcb.cn/news/detail-833483.html
#include"SList.h"
void TestSLT1()
{
SLNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
}
void TestSLT2()
{
SLNode* plist = NULL;
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
//SLNode* pos = SLTFind(plist, 3);
//SLTInsert(&plist, pos, 30);
}
//int main()
//{
// TestSLT2();
//
// return 0;
//}
struct ListNode
{
struct ListNode* next;
int val;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* prev = NULL;
struct ListNode* cur = head;
//while(cur != NULL)
while (cur)
{
if (cur->val == val)
{
struct ListNode* next = cur->next;
free(cur);
if (prev)
prev->next = next;
cur = next;
}
else
{
prev = cur;
cur = cur->next;
}
}
return head;
}
int main()
{
struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
n1->val = 7;
n2->val = 7;
n3->val = 7;
n4->val = 7;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
struct ListNode* head = removeElements(n1, 7);
return 0;
}
?文章來源地址http://www.zghlxwxcb.cn/news/detail-833483.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】順序表與鏈表（單鏈表和雙鏈表）超詳解圖示與源碼。的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
