C語言編程數(shù)據(jù)結(jié)構(gòu)線性表之順序表和鏈表原理分析
線性表的定義和特點
線性結(jié)構(gòu)的基本特點：除第一個元素?zé)o直接前驅(qū)，最后一個元素?zé)o直接后繼，其他元素都有一個前驅(qū)和一個后繼。
說人話就是：第一個元素不能向前訪問，最后一個元素不能向后訪問，中間的元素都可以前后訪問其他元素。
例如：26個字母表{A,B,C,D,E,F…}就是一個線性表.
雖然該線性表中數(shù)據(jù)元素各不相同，但每個元素都具有相同的特性，都屬于同一數(shù)據(jù)對象
線性表：由有限個數(shù)據(jù)特性相同的數(shù)據(jù)元素構(gòu)成的有限序列
如果沒有數(shù)據(jù)元素，該線性表也叫空表。
線性結(jié)構(gòu)的特點
1，存在唯一 一個“第一個”與“最后一個”數(shù)據(jù)元素
2，出第一個和最后一個數(shù)據(jù)元素，其余元素都有一個前驅(qū)和一個后驅(qū)
解釋一下：前驅(qū)和后繼就是邏輯關(guān)系中的上一個元素和下一個元素
我原先以為是指針之類的。
線性表
線性表的長度可以根據(jù)需要增長或減小。還擁有任意位置的插入和刪除
線性表分為順序表和鏈表
順序存儲
線性表的順序存儲就是順序表，是指**一組地址連續(xù)的存儲單元依次存儲的數(shù)據(jù)元素。**實際就是每個元素都是依次儲存在地址連續(xù)的空間（簡稱：數(shù)組）。對于順序存儲而言，邏輯上是連續(xù)的，其物理次序上也是連續(xù)的
來看一張圖增強(qiáng)一下理解（這是我寫順序存儲的習(xí)慣，可能會存在差異）
對于線性表的順序存儲的而言，每個數(shù)據(jù)元素都可以通過下標(biāo)來快速訪問，讀取。正規(guī)來說就是隨機(jī)存取
順序表的元素類型定義
這是我對順序存儲的結(jié)構(gòu)體類型的定義
#define N 8
typedef struct elem
{
int element;//每個數(shù)據(jù)元素中的數(shù)據(jù)項
}sel;
typedef struct seq
{
sel* arr;//動態(tài)開辟的線性表空間的首地址，通過這個指針訪問到線性表空間
int size;//當(dāng)前已經(jīng)使用了的空間的個數(shù)
int capacity;//當(dāng)前的最大的數(shù)據(jù)元素容量
}sl;
這里我為了簡單一些描述，我直接使用了每個數(shù)據(jù)元素都相當(dāng)于只有int 類型的數(shù)據(jù)項。
其實就是跟通訊錄一樣，每個數(shù)據(jù)元素都是一個人的全部信息的集合（應(yīng)該可以這么說吧），而數(shù)據(jù)項就是每個元素中包含的一部分。
順序表的增刪查改
對于順序表來說，絕大部分可以當(dāng)成數(shù)組進(jìn)行操作，當(dāng)然，也就是要考慮順序的容量問題，是否需要擴(kuò)容的幾個動態(tài)變化問題。
初始化順序表
void initsequence(sl* a)//初始化動態(tài)順序表
{
a->size = 0;//數(shù)組元素以0開始計算,size是最后一個元素的下標(biāo)，不是元素總數(shù)量
a->capacity = N;//N在上面已經(jīng)define了
a->arr = (sel*)malloc(sizeof(int) * N);
}
擴(kuò)容順序表
void checkcapacity(sl* a)//檢查是否需要擴(kuò)容
{
if (a->size +1== a->capacity)
{
a->capacity *= 2;
a->arr =(sel*) realloc( a->arr,sizeof(int) * (a->capacity));
if (a->arr == NULL)
{
printf("realloc defect");
exit(-1);
}
}
}
擴(kuò)容是當(dāng)準(zhǔn)備對順序表的元素進(jìn)行操作時元素個數(shù)已經(jīng)達(dá)到最大容量時，由于我們的size是下標(biāo)，就要加一。因為我們準(zhǔn)備擴(kuò)容，所以是不會允許size>=capacity。
同時，擴(kuò)容不能一次性擴(kuò)太多，否則或?qū)е驴臻g浪費(fèi)。
又不能擴(kuò)太少，少了就要多次擴(kuò)容，會增加消耗。
所以，自己看情況吧。嘻嘻~
尾插法增加元素
void sequpushfront(sl* a,sel* ele)//尾插法
{
checkcapacity(&a);//檢查是否需要擴(kuò)容
*(a->arr + a->size) =ele->element;//因為我只設(shè)置了一個int類型的如果數(shù)據(jù)元素中有多個數(shù)據(jù)項向下看
++(a->size);
}
void sequpushfront(sl* a,sel* ele)//尾插法
{
checkcapacity(&a);//檢查是否需要擴(kuò)容
(a->arr + a->size)->n =ele->element;//假設(shè)是有多個數(shù)據(jù)項就這樣依次匹配（a->arr + a->size）已經(jīng)訪問到每個元素的地址再->n訪問到相應(yīng)元素的空間進(jìn)行存儲。
++(a->size);
}
尾插法沒那么復(fù)雜，檢查一下擴(kuò)容，直接在后面放入元素就行。
下面我就不再舉例了，舉一反三很容易的。
頭插法
void sequpushback(sl* a, int n)//頭插法
{
checkcapacity(&a);//檢查是否需要擴(kuò)容
int head = 0;
int end = a->size;
while (end>=head)
{
*(a->arr + end + 1) = *(a->arr + end);
--end;
}
++(a->size);
*(a->arr + head) = n;
}
頭插法就需要將放入位置后的元素全部向后移動一個位置。
但是，怎么移又是要考慮一下的問題。
是從前向后開始移動，還是從最后一個元素開始移動。
如果是從前向后移動
會造成這個樣子，后面元素就一直是1，則，這種方法就是錯誤的。
再來看看從后向前移動
這種方法是可以行的通的。
先擴(kuò)容
再元素向后移，再頭插。
void sequpushback(sl* a, sel* ele)//頭插法
{
checkcapacity(&a);//檢查是否需要擴(kuò)容
int head = 0;
int end = a->size;
while (end>=head)
{
*(a->arr + end + 1) = *(a->arr + end);
--end;
}
++(a->size);
*(a->arr + head) = ele->element;
}
任意位置刪除
刪除就不頭刪尾刪了，直接任意位置刪除。
找到那個元素的下標(biāo)，再開始向前覆蓋
對于刪除而言，元素移動又是一個麻煩事。
這次我們對于刪除而言，元素得從前向后開始移動。
void sequpopmid(sl* a, int n)//中間刪除，n是要刪除的位置
{
assert(n>=0&&n<=a->size);
for (int i = n ; i < a->size-1; i++)
{
*(a->arr + i) = *(a->arr + i + 1);
}
--(a->size);
}
刪除后要將邊界也就是size自減，防止越界。
任意位置添加
傳要添加的位置，再開始向后移動。
void sequpushmid(sl* a, int n,sel* ele)//中間添加
{
assert(n>=0&&n=<a->size+1);//要在有效位置添加
checkcapacity(&a);//檢查是否需要擴(kuò)容
int head = n;
int end = a->size;
while (end>=head)
{
*(a->arr + end + 1) = *(a->arr + end);
--end;
}
++(a->size);
*(a->arr + head) = ele->element;
}
其實就是頭插法的一種變形。
小總結(jié)
對于數(shù)組刪除元素，要從前向后開始移動。
而對于數(shù)組增加元素，要從后向前開始移動。
同時刪除添加的位置都要符合條件，不能越界。
線性表的鏈?zhǔn)酱鎯?/h2>
該存儲結(jié)構(gòu)的存儲特點是：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。（這組存儲單元可以是連續(xù)的也可以是不連續(xù)的，簡稱：隨機(jī)分布的存儲單元）
數(shù)據(jù)域與指針域
而每個分配到存儲單元都要分為兩個部分：數(shù)據(jù)域與指針域。
這兩個域或者信息組成數(shù)據(jù)元素的存儲映像。是邏輯層次的元素在物理層次的投影。也叫結(jié)點。
- 數(shù)據(jù)域：儲存每個數(shù)據(jù)元素，包括各個數(shù)據(jù)項
- 指針域：儲存一個指針，也就是下一個結(jié)點的地址
注意，鏈?zhǔn)絻Υ嬉簿褪擎湵恚涿總€結(jié)點的地址都是隨機(jī)的，并不是像順序表一樣，每個空間依次排列。
鏈表有超多種結(jié)構(gòu)，如：單鏈表，單向/雙向循環(huán)鏈表，雙向鏈表，二叉鏈表，十字鏈表，鄰鏈表，鄰接多重表等。
本文主要分析單鏈表，循環(huán)鏈表，雙向鏈表。其余的暫時不分析（其實是我不會，目前比較菜），以后會補(bǔ)充分析。
數(shù)據(jù)結(jié)構(gòu)最好先畫圖，這樣可以增強(qiáng)理解與分析。
大致了解一下鏈表的結(jié)構(gòu)。
由于鏈表中的每個結(jié)點的物理關(guān)系是不確定的，是隨機(jī)的，就需要靠指針域來表示，構(gòu)成邏輯關(guān)系。指針指向是十分重要的。
這個哨兵位的頭節(jié)點的可要可不要的。
#include "linkedlist.h"
void test()
{
list* head;
list* last;
initLinkedlist(&head,&last);
pushlast(&last, 1);//尾插法
pushlast(&last, 2);
pushlast(&last, 3);
pushlast(&last, 4);
pushfront(&head, 5);//頭插法
pushfront(&head, 8);//頭插法
pushfront(&head, 7);//頭插法
pushfront(&head, 6);//頭插法
popchoice(&head, 0);//任意位置刪除
//poshposition(&head, 3);//任意位置插入
printlist(&head);//打印
}
int main(void)
{
test();
return 0;
}
先分析哨兵位的鏈表，好理解
初始化鏈表
void initLinkedlist(list** head,list** last)//初始化鏈表
{
*head = (list*)malloc(sizeof(list));
(*head)->next = NULL;
*last=*head;
}
head就是哨兵位，而這個last，是要來定位最后一個結(jié)點，當(dāng)last指向head時，就代表是一個空表。
由于我是在測試函數(shù)中創(chuàng)建了哨兵結(jié)點和尾結(jié)點指針，所以要對指針進(jìn)行操作得傳一個二級指針，傳址調(diào)用才能才能對鏈表進(jìn)行影響。
當(dāng)尾結(jié)點指向哨兵結(jié)點時，表示是一個空表。
尾插法增加鏈表結(jié)點
void pushlast(list** last, int num)//尾插法
{
list* new = (list*)malloc(sizeof(list));
new->n = num;
new->next = (*last)->next;
(*last)->next = new;
(*last) = new;
}
要在尾結(jié)點，也就是last結(jié)點。
尾插結(jié)點圖解，就是這樣的。
同時，當(dāng)last->next的指向newnode后，last也要再移向newnode，因為newnode變成了尾結(jié)點，下次插入會在這次newnode的后面進(jìn)行插入。
頭插法添加鏈表結(jié)點
void pushfront(list** head, int num)//頭插法
{
list* new = (list*)malloc(sizeof(list));
new->n = num;
new->next = (*head)->next;
(*head)->next = new;
}
要在哨兵位后進(jìn)行插入，每次插入都要滿足在哨兵位節(jié)點后進(jìn)行。
而哨兵位結(jié)點是始終不變的，我們可以通過這樣的操作不斷頭插。
打印鏈表
void printlist(list** head)//打印
{
list* p = (*head)->next;
while (p)
{
printf("%d ", p->n);
p = p->next;
}
}
從哨兵位結(jié)點進(jìn)行遍歷，依次打印。
任意位置的刪除
void popchoice(list** head, int pos)//任意位置刪除
{
assert(pos<8&pos>=0);
int i = 0;
list* pre = *head;
list* cur = (*head)->next;
while (i < pos)
{
pre = cur;
cur = cur->next;
i++;
}
pre->next = cur->next;
free(cur);
}
由于是有哨兵位的鏈表，在任意位置刪除還好，但無哨兵位的鏈表，就有一些麻煩。
雖然差不多的變化。因位要保存結(jié)點的前一個結(jié)點地址，當(dāng)沒有哨兵位的時候就需要if判斷一下。其實也沒多麻煩。
任意位置插入和刪除是一樣的。
雙向鏈表
這是另一種鏈?zhǔn)浇Y(jié)構(gòu)。
每個結(jié)點都具有兩個指針，一個指向上一個邏輯關(guān)系結(jié)點，一個指向下一個邏輯關(guān)系結(jié)點。
這一般使用一個哨兵位的結(jié)點，可以創(chuàng)建使用雙向鏈表的步驟更簡單。
對于雙向鏈表與單鏈表而言，雙向鏈表在鏈表的插入，刪除以及多個操作上更具有優(yōu)勢。
如：尾插。
對于單鏈表，要指針遍歷找到尾結(jié)點，再插入。時間復(fù)雜度為O(N).
而雙向鏈表，他的頭結(jié)點的prev指針指向了最后一個結(jié)點，根本不需要依次遍歷。
像一些插入操作
如：前插
單鏈表都要準(zhǔn)備兩個指針。
而雙向鏈表直接訪問prev指針就可以找到上一個結(jié)點。
雖然，指針較多可能比單鏈表麻煩，但整體操作上，卻要簡單。
而且，在以后的很多結(jié)構(gòu)上，單鏈表都不會拿出來單獨(dú)使用，而是作為某個數(shù)據(jù)結(jié)構(gòu)的一部分。雙向鏈表才是會作為一個主體來使用。
測試雙向鏈表（主函數(shù)）
#include "doubly_Linkedlist.h"
void doublelinkedlist1()
{
doulink head;
initlinkedlist(&head);//初始化雙向鏈表
LinkedlistFrontPush(&head, 1);//頭插法
LinkedlistFrontPush(&head, 2);//頭插法
LinkedlistFrontPush(&head, 3);//頭插法
LinkedlistFrontPush(&head, 4);//頭插法
LinkedlistFrontPush(&head, 5);//頭插法
LinkedlistBackpush(&head, 6);//尾插法
LinkedlistBackpush(&head, 7);//尾插法
LinkedlistBackpush(&head, 8);//尾插法
LinkedlistBackpush(&head, 9);//尾插法
LinkedlistBackpush(&head, 10);//尾插法
LinkedlistFrontPop(&head);//頭刪
LinkedlistFrontPop(&head);//頭刪
LinkedlistFrontPop(&head);//頭刪
LinkedlistBackPop(&head);//尾刪
LinkedlistBackPop(&head);//尾刪
LinkedlistBackPop(&head);//尾刪
LinkedlistBackPop(&head);//尾刪
LinkedlistBackPop(&head);//尾刪
LinkedlistPrint(&head);//打印鏈表
}
int main(void)
{
doublelinkedlist1();
}
因為我是創(chuàng)建了一個結(jié)構(gòu)體變量，要對其進(jìn)行操作，需要傳址調(diào)用，如果傳值調(diào)用會，導(dǎo)致實際上哨兵并未改變，只是改變了函數(shù)中的形參。
初始化雙向鏈表
void initlinkedlist(doulink* head)//初始化雙向鏈表
{
(*head).next = head;
(*head).prev = head;
}
因為雙向鏈表要形成一個閉環(huán)，初始化時也要形成閉環(huán)
頭插法插入元素
void LinkedlistFrontPush(doulink* head, lint n)//頭插法
{
doulink* newnode = (doulink*)malloc(sizeof(doulink));
newnode->num = n;
doulink*phead=(*head).next;//原頭節(jié)點
newnode->next = phead;//新的后驅(qū)指針接入下一個
(*head).next = newnode;//將哨兵鏈接新結(jié)點
newnode->prev = head;//新結(jié)點的前驅(qū)指針指向哨兵
phead->prev = newnode;//原頭結(jié)點的前驅(qū)指針指向新的頭節(jié)點
}
尾插法插入元素
void LinkedlistBackpush(doulink* head, lint n)//尾插法
{
doulink* newnode = (doulink*)malloc(sizeof(doulink));
newnode->num = n;
doulink* plast = (*head).prev;//找到尾結(jié)點
newnode->prev = plast;//新的尾接入原尾結(jié)點
newnode->next = plast->next;//新接入哨兵
plast->next = newnode;//原尾結(jié)點next指向新的尾
(*head).prev = newnode;//頭節(jié)點的prev指向新的尾結(jié)點，形成閉環(huán)
}
有鏈表中多個結(jié)點的情況
尾刪法刪除結(jié)點
void LinkedlistBackPop(doulink* head)//尾刪
{
doulink* last = (*head).prev;//找到要刪除的尾結(jié)點
doulink* llast = last->prev;//找到刪除后的新的尾結(jié)點
if (last == head)
{
printf("Empty List\n");
return;
}
(*head).prev = llast;//改變哨兵結(jié)點prev指向
llast->next = last->next;//讓新的尾結(jié)點的next接入哨兵
free(last);//刪除內(nèi)存
}
頭刪法刪除結(jié)點
void LinkedlistFrontPop(doulink* head)//頭刪
{
doulink* phead = (*head).next;
doulink* second = phead->next;
if (phead == head)
{
printf("Empty List\n");
return;
}
second->prev = phead->prev;
(*head).next = second;
free(first);
}
對于頭插尾插，尾刪頭刪，一定要注意順序，不然可能會導(dǎo)致指針指向錯誤的地方。
而對于雙向鏈表的刪除插入，不需要多個指針，這樣要方便很多。
以下是代碼的全部主體
doubly-Linked list.c文件
#include "doubly_Linkedlist.h"
void initlinkedlist(doulink* head)//初始化雙向鏈表
{
(*head).next = head;
(*head).prev = head;
}
void LinkedlistFrontPush(doulink* head, lint n)//頭插法
{
doulink* newnode = (doulink*)malloc(sizeof(doulink));
newnode->num = n;
doulink*phead=(*head).next;//原頭節(jié)點
newnode->next = phead;//新的后驅(qū)指針接入下一個
(*head).next = newnode;//將哨兵鏈接新結(jié)點
newnode->prev = head;//新結(jié)點的前驅(qū)指針指向哨兵
phead->prev = newnode;//原頭結(jié)點的前驅(qū)指針指向新的頭節(jié)點
}
void LinkedlistBackpush(doulink* head, lint n)//尾插法
{
doulink* newnode = (doulink*)malloc(sizeof(doulink));
newnode->num = n;
doulink* plast = (*head).prev;//找到尾結(jié)點
newnode->prev = plast;//新的尾接入原尾結(jié)點
newnode->next = plast->next;//新接入哨兵
plast->next = newnode;//原尾結(jié)點next指向新的尾
(*head).prev = newnode;//頭節(jié)點的prev指向新的尾結(jié)點，形成閉環(huán)
}
void LinkedlistFrontPop(doulink* head)//頭刪
{
doulink* phead = (*head).next;
doulink* second = phead->next;
if (phead == head)
{
printf("Empty List\n");
return;
}
second->prev = phead->prev;
(*head).next = second;
}
void LinkedlistBackPop(doulink* head)//尾刪
{
doulink* last = (*head).prev;//找到要刪除的尾結(jié)點
doulink* llast = last->prev;//找到刪除后的新的尾結(jié)點
if (last == head)
{
printf("Empty List\n");
return;
}
(*head).prev = llast;//改變哨兵結(jié)點prev指向
llast->next = last->next;//讓新的尾結(jié)點的next接入哨兵
free(last);
}
void LinkedlistPrint(doulink* head)//打印鏈表
{
doulink* cur = (*head).next;
while (cur != head)
{
printf("%d ", cur->num);
cur = cur->next;
}
}
doubly-Linkedlist.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int lint;
typedef struct doulinked
{
lint num;
lint* prev;
lint* next;
}doulink;
void initlinkedlist(doulink* head);//初始化雙向鏈表
void LinkedlistFrontPush(doulink* head, lint n);//頭插法
void LinkedlistBackpush(doulink* head, lint n);//尾插法
void LinkedlistFrontPop(doulink* head);//頭刪
void LinkedlistBackPop(doulink* head);//尾刪
void LinkedlistPrint(doulink* head);//打印鏈表
以上就是C語言編程數(shù)據(jù)結(jié)構(gòu)線性表之順序表和鏈表原理分析的詳細(xì)內(nèi)容，更多關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)線性表順序表和鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！
感謝閱讀~
相關(guān)文章
隨便google一下,人家就可以跟你解釋的,一大堆的道理,我們沒怎么多時間,討論為何要對齊.直入主題,怎么判斷內(nèi)存對齊規(guī)則,sizeof的結(jié)果怎么來的,請牢記以下3條原則2013-09-09
這篇文章主要介紹了C++ STL中常見的算法使用方式,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09
這篇文章主要介紹了windows消息和消息隊列實例詳解,詳細(xì)講述了Windows的消息機(jī)制與原理,對于深入理解和學(xué)習(xí)Windows應(yīng)用程序設(shè)計有不錯的借鑒價值,需要的朋友可以參考下2014-10-10
這篇文章主要為大家詳細(xì)介紹了C/C++中高精度算法（加減乘除）的簡單實現(xiàn)，方便以后需要時拷貝使用。感興趣的小伙伴可以跟隨小編一起了解一下2022-12-12
C語言數(shù)據(jù)結(jié)構(gòu)之棧與隊列的相互實現(xiàn)
這篇文章主要為大家詳細(xì)介紹了如何利用C語言相互實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的棧與隊列，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2022-07-07
C/C++ 中const關(guān)鍵字的用法小結(jié)
C++中的const關(guān)鍵字的用法非常靈活，而使用const將大大改善程序的健壯性。這篇文章主要介紹了C/C++ 中const關(guān)鍵字的用法,需要的朋友可以參考下2020-02-02
C++超詳細(xì)分析講解內(nèi)聯(lián)函數(shù)
為了消除函數(shù)調(diào)用的時空開銷，C++ 提供一種提高效率的方法，即在編譯時將函數(shù)調(diào)用處用函數(shù)體替換，類似于C語言中的宏展開。這種在函數(shù)調(diào)用處直接嵌入函數(shù)體的函數(shù)稱為內(nèi)聯(lián)函數(shù)（Inline Function），又稱內(nèi)嵌函數(shù)或者內(nèi)置函數(shù)2022-06-06
C++類與對象深入之靜態(tài)成員與友元及內(nèi)部類詳解
朋友們好,這篇播客我們繼續(xù)C++的初階學(xué)習(xí)，現(xiàn)在對我們對C++的靜態(tài)成員，友元，內(nèi)部類知識點做出總結(jié)，整理出來一篇博客供我們一起復(fù)習(xí)和學(xué)習(xí),如果文章中有理解不當(dāng)?shù)牡胤?還希望朋友們在評論區(qū)指出,我們相互學(xué)習(xí),共同進(jìn)步2022-06-06
函數(shù)以及函數(shù)的遞歸調(diào)用是學(xué)習(xí)C語言必須要掌握的內(nèi)容,且遞歸作為經(jīng)典的算法思想被廣泛應(yīng)用于程序設(shè)計中,下面這篇文章主要給大家介紹了關(guān)于C語言中遞歸的實際應(yīng)用與經(jīng)典問題的相關(guān)資料,需要的朋友可以參考下2021-09-09
C++11這次的更新帶來了令很多C++程序員期待已久的for range循環(huán)，每次看到j(luò)avascript， lua里的for range，心想要是C++能有多好，心里別提多酸了。這次C++11不負(fù)眾望，再也不用羨慕別家人的for range了。下面看下C++11的for循環(huán)的新用法2021-11-11