線性表的定義和特點(diǎn)
線性結(jié)構(gòu)的基本特點(diǎn):除第一個(gè)元素?zé)o直接前驅(qū),最后一個(gè)元素?zé)o直接后繼,其他元素都有一個(gè)前驅(qū)和一個(gè)后繼。
說人話就是:第一個(gè)元素不能向前訪問,最后一個(gè)元素不能向后訪問,中間的元素都可以前后訪問其他元素。
例如:26個(gè)字母表{A,B,C,D,E,F…}就是一個(gè)線性表。
雖然該線性表中數(shù)據(jù)元素各不相同,但每個(gè)元素都具有相同的特性,都屬于同一數(shù)據(jù)對象。
線性表:由有限個(gè)數(shù)據(jù)特性相同的數(shù)據(jù)元素構(gòu)成的有限序列。
如果沒有數(shù)據(jù)元素,該線性表也叫空表。
線性結(jié)構(gòu)的特點(diǎn)
1,存在唯一 一個(gè)“第一個(gè)”與“最后一個(gè)”數(shù)據(jù)元素
2,出第一個(gè)和最后一個(gè)數(shù)據(jù)元素,其余元素都有一個(gè)前驅(qū)和一個(gè)后驅(qū)
解釋一下:前驅(qū)和后繼就是邏輯關(guān)系中的上一個(gè)元素和下一個(gè)元素
我原先以為是指針之類的。
線性表
線性表的長度可以根據(jù)需要增長或減小。還擁有任意位置的插入和刪除
線性表分為順序表和鏈表
順序存儲
線性表的順序存儲就是順序表,是指**一組地址連續(xù)的存儲單元依次存儲的數(shù)據(jù)元素。**實(shí)際就是每個(gè)元素都是依次儲存在地址連續(xù)的空間(簡稱:數(shù)組)。對于順序存儲而言,邏輯上是連續(xù)的,其物理次序上也是連續(xù)的
來看一張圖增強(qiáng)一下理解(這是我寫順序存儲的習(xí)慣,可能會(huì)存在差異)
對于線性表的順序存儲的而言,每個(gè)數(shù)據(jù)元素都可以通過下標(biāo)來快速訪問,讀取。正規(guī)來說就是隨機(jī)存取
順序表的元素類型定義
這是我對順序存儲的結(jié)構(gòu)體類型的定義
#define N 8 typedef struct elem { int element;//每個(gè)數(shù)據(jù)元素中的數(shù)據(jù)項(xiàng) }sel; typedef struct seq { sel* arr;//動(dòng)態(tài)開辟的線性表空間的首地址,通過這個(gè)指針訪問到線性表空間 int size;//當(dāng)前已經(jīng)使用了的空間的個(gè)數(shù) int capacity;//當(dāng)前的最大的數(shù)據(jù)元素容量 }sl;
這里我為了簡單一些描述,我直接使用了每個(gè)數(shù)據(jù)元素都相當(dāng)于只有int 類型的數(shù)據(jù)項(xiàng)。
其實(shí)就是跟通訊錄一樣,每個(gè)數(shù)據(jù)元素都是一個(gè)人的全部信息的集合(應(yīng)該可以這么說吧),而數(shù)據(jù)項(xiàng)就是每個(gè)元素中包含的一部分。
順序表的增刪查改
對于順序表來說,絕大部分可以當(dāng)成數(shù)組進(jìn)行操作,當(dāng)然,也就是要考慮順序的容量問題,是否需要擴(kuò)容的幾個(gè)動(dòng)態(tài)變化問題。
初始化順序表
void initsequence(sl* a)//初始化動(dòng)態(tài)順序表 { a->size = 0;//數(shù)組元素以0開始計(jì)算,size是最后一個(gè)元素的下標(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í)元素個(gè)數(shù)已經(jīng)達(dá)到最大容量時(shí),由于我們的size是下標(biāo),就要加一。因?yàn)槲覀儨?zhǔn)備擴(kuò)容,所以是不會(huì)允許size>=capacity。
同時(shí),擴(kuò)容不能一次性擴(kuò)太多,否則或?qū)е驴臻g浪費(fèi)。
又不能擴(kuò)太少,少了就要多次擴(kuò)容,會(huì)增加消耗。
所以,自己看情況吧。嘻嘻~
尾插法增加元素
void sequpushfront(sl* a,sel* ele)//尾插法 { checkcapacity(&a);//檢查是否需要擴(kuò)容 *(a->arr + a->size) =ele->element;//因?yàn)槲抑辉O(shè)置了一個(gè)int類型的如果數(shù)據(jù)元素中有多個(gè)數(shù)據(jù)項(xiàng)向下看 ++(a->size); }
void sequpushfront(sl* a,sel* ele)//尾插法 { checkcapacity(&a);//檢查是否需要擴(kuò)容 (a->arr + a->size)->n =ele->element;//假設(shè)是有多個(gè)數(shù)據(jù)項(xiàng)就這樣依次匹配(a->arr + a->size)已經(jīng)訪問到每個(gè)元素的地址再->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; }
頭插法就需要將放入位置后的元素全部向后移動(dòng)一個(gè)位置。
但是,怎么移又是要考慮一下的問題。
是從前向后開始移動(dòng),還是從最后一個(gè)元素開始移動(dòng)。
如果是從前向后移動(dòng)
會(huì)造成這個(gè)樣子,后面元素就一直是1,則,這種方法就是錯(cuò)誤的。
再來看看從后向前移動(dòng)
這種方法是可以行的通的。
先擴(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; }
任意位置刪除
刪除就不頭刪尾刪了,直接任意位置刪除。
找到那個(gè)元素的下標(biāo),再開始向前覆蓋
對于刪除而言,元素移動(dòng)又是一個(gè)麻煩事。
這次我們對于刪除而言,元素得從前向后開始移動(dòng)。
void sequpopmid(sl* a, int n)//中間刪除,n是要?jiǎng)h除的位置 { 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自減,防止越界。
任意位置添加
傳要添加的位置,再開始向后移動(dòng)。
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; }
其實(shí)就是頭插法的一種變形。
小總結(jié)
對于數(shù)組刪除元素,要從前向后開始移動(dòng)。
而對于數(shù)組增加元素,要從后向前開始移動(dòng)。
同時(shí)刪除添加的位置都要符合條件,不能越界。
線性表的鏈?zhǔn)酱鎯?/h2>
該存儲結(jié)構(gòu)的存儲特點(diǎn)是:用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。(這組存儲單元可以是連續(xù)的也可以是不連續(xù)的,簡稱:隨機(jī)分布的存儲單元)
數(shù)據(jù)域與指針域
而每個(gè)分配到存儲單元都要分為兩個(gè)部分:數(shù)據(jù)域與指針域。
這兩個(gè)域或者信息組成數(shù)據(jù)元素的存儲映像。是邏輯層次的元素在物理層次的投影。也叫結(jié)點(diǎn)。
- 數(shù)據(jù)域:儲存每個(gè)數(shù)據(jù)元素,包括各個(gè)數(shù)據(jù)項(xiàng)
- 指針域:儲存一個(gè)指針,也就是下一個(gè)結(jié)點(diǎn)的地址
注意,鏈?zhǔn)絻Υ嬉簿褪擎湵?,其每個(gè)結(jié)點(diǎn)的地址都是隨機(jī)的,并不是像順序表一樣,每個(gè)空間依次排列。
鏈表有超多種結(jié)構(gòu),如:單鏈表,單向/雙向循環(huán)鏈表,雙向鏈表,二叉鏈表,十字鏈表,鄰鏈表,鄰接多重表等。
本文主要分析單鏈表,循環(huán)鏈表,雙向鏈表。其余的暫時(shí)不分析(其實(shí)是我不會(huì),目前比較菜),以后會(huì)補(bǔ)充分析。
數(shù)據(jù)結(jié)構(gòu)最好先畫圖,這樣可以增強(qiáng)理解與分析。
大致了解一下鏈表的結(jié)構(gòu)。
由于鏈表中的每個(gè)結(jié)點(diǎn)的物理關(guān)系是不確定的,是隨機(jī)的,就需要靠指針域來表示,構(gòu)成邏輯關(guān)系。指針指向是十分重要的。
這個(gè)哨兵位的頭節(jié)點(diǎn)的可要可不要的。
#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就是哨兵位,而這個(gè)last,是要來定位最后一個(gè)結(jié)點(diǎn),當(dāng)last指向head時(shí),就代表是一個(gè)空表。
由于我是在測試函數(shù)中創(chuàng)建了哨兵結(jié)點(diǎn)和尾結(jié)點(diǎn)指針,所以要對指針進(jìn)行操作得傳一個(gè)二級指針,傳址調(diào)用才能才能對鏈表進(jìn)行影響。
當(dāng)尾結(jié)點(diǎn)指向哨兵結(jié)點(diǎn)時(shí),表示是一個(gè)空表。
尾插法增加鏈表結(jié)點(diǎn)
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é)點(diǎn),也就是last結(jié)點(diǎn)。
尾插結(jié)點(diǎn)圖解,就是這樣的。
同時(shí),當(dāng)last->next的指向newnode后,last也要再移向newnode,因?yàn)閚ewnode變成了尾結(jié)點(diǎn),下次插入會(huì)在這次newnode的后面進(jìn)行插入。
頭插法添加鏈表結(jié)點(diǎn)
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é)點(diǎn)后進(jìn)行。
而哨兵位結(jié)點(diǎn)是始終不變的,我們可以通過這樣的操作不斷頭插。
打印鏈表
void printlist(list** head)//打印 { list* p = (*head)->next; while (p) { printf("%d ", p->n); p = p->next; } }
從哨兵位結(jié)點(diǎn)進(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é)點(diǎn)的前一個(gè)結(jié)點(diǎn)地址,當(dāng)沒有哨兵位的時(shí)候就需要if判斷一下。其實(shí)也沒多麻煩。
任意位置插入和刪除是一樣的。
雙向鏈表
這是另一種鏈?zhǔn)浇Y(jié)構(gòu)。
每個(gè)結(jié)點(diǎn)都具有兩個(gè)指針,一個(gè)指向上一個(gè)邏輯關(guān)系結(jié)點(diǎn),一個(gè)指向下一個(gè)邏輯關(guān)系結(jié)點(diǎn)。
這一般使用一個(gè)哨兵位的結(jié)點(diǎn),可以創(chuàng)建使用雙向鏈表的步驟更簡單。
對于雙向鏈表與單鏈表而言,雙向鏈表在鏈表的插入,刪除以及多個(gè)操作上更具有優(yōu)勢。
如:尾插。
對于單鏈表,要指針遍歷找到尾結(jié)點(diǎn),再插入。時(shí)間復(fù)雜度為O(N).
而雙向鏈表,他的頭結(jié)點(diǎn)的prev指針指向了最后一個(gè)結(jié)點(diǎn),根本不需要依次遍歷。
像一些插入操作
如:前插
單鏈表都要準(zhǔn)備兩個(gè)指針。
而雙向鏈表直接訪問prev指針就可以找到上一個(gè)結(jié)點(diǎn)。
雖然,指針較多可能比單鏈表麻煩,但整體操作上,卻要簡單。
而且,在以后的很多結(jié)構(gòu)上,單鏈表都不會(huì)拿出來單獨(dú)使用,而是作為某個(gè)數(shù)據(jù)結(jié)構(gòu)的一部分。雙向鏈表才是會(huì)作為一個(gè)主體來使用。
測試雙向鏈表(主函數(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(); }
因?yàn)槲沂莿?chuàng)建了一個(gè)結(jié)構(gòu)體變量,要對其進(jìn)行操作,需要傳址調(diào)用,如果傳值調(diào)用會(huì),導(dǎo)致實(shí)際上哨兵并未改變,只是改變了函數(shù)中的形參。
初始化雙向鏈表
void initlinkedlist(doulink* head)//初始化雙向鏈表 { (*head).next = head; (*head).prev = head; }
因?yàn)殡p向鏈表要形成一個(gè)閉環(huán),初始化時(shí)也要形成閉環(huán)
頭插法插入元素
void LinkedlistFrontPush(doulink* head, lint n)//頭插法 { doulink* newnode = (doulink*)malloc(sizeof(doulink)); newnode->num = n; doulink*phead=(*head).next;//原頭節(jié)點(diǎn) newnode->next = phead;//新的后驅(qū)指針接入下一個(gè) (*head).next = newnode;//將哨兵鏈接新結(jié)點(diǎn) newnode->prev = head;//新結(jié)點(diǎn)的前驅(qū)指針指向哨兵 phead->prev = newnode;//原頭結(jié)點(diǎn)的前驅(qū)指針指向新的頭節(jié)點(diǎn) }
尾插法插入元素
void LinkedlistBackpush(doulink* head, lint n)//尾插法 { doulink* newnode = (doulink*)malloc(sizeof(doulink)); newnode->num = n; doulink* plast = (*head).prev;//找到尾結(jié)點(diǎn) newnode->prev = plast;//新的尾接入原尾結(jié)點(diǎn) newnode->next = plast->next;//新接入哨兵 plast->next = newnode;//原尾結(jié)點(diǎn)next指向新的尾 (*head).prev = newnode;//頭節(jié)點(diǎn)的prev指向新的尾結(jié)點(diǎn),形成閉環(huán) }
有鏈表中多個(gè)結(jié)點(diǎn)的情況
尾刪法刪除結(jié)點(diǎn)
void LinkedlistBackPop(doulink* head)//尾刪 { doulink* last = (*head).prev;//找到要?jiǎng)h除的尾結(jié)點(diǎn) doulink* llast = last->prev;//找到刪除后的新的尾結(jié)點(diǎn) if (last == head) { printf("Empty List\n"); return; } (*head).prev = llast;//改變哨兵結(jié)點(diǎn)prev指向 llast->next = last->next;//讓新的尾結(jié)點(diǎn)的next接入哨兵 free(last);//刪除內(nèi)存 }
頭刪法刪除結(jié)點(diǎ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; free(first); }
對于頭插尾插,尾刪頭刪,一定要注意順序,不然可能會(huì)導(dǎo)致指針指向錯(cuò)誤的地方。
而對于雙向鏈表的刪除插入,不需要多個(gè)指針,這樣要方便很多。
以下是代碼的全部主體
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é)點(diǎn) newnode->next = phead;//新的后驅(qū)指針接入下一個(gè) (*head).next = newnode;//將哨兵鏈接新結(jié)點(diǎn) newnode->prev = head;//新結(jié)點(diǎn)的前驅(qū)指針指向哨兵 phead->prev = newnode;//原頭結(jié)點(diǎn)的前驅(qū)指針指向新的頭節(jié)點(diǎn) } void LinkedlistBackpush(doulink* head, lint n)//尾插法 { doulink* newnode = (doulink*)malloc(sizeof(doulink)); newnode->num = n; doulink* plast = (*head).prev;//找到尾結(jié)點(diǎn) newnode->prev = plast;//新的尾接入原尾結(jié)點(diǎn) newnode->next = plast->next;//新接入哨兵 plast->next = newnode;//原尾結(jié)點(diǎn)next指向新的尾 (*head).prev = newnode;//頭節(jié)點(diǎn)的prev指向新的尾結(jié)點(diǎn),形成閉環(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ǎng)h除的尾結(jié)點(diǎn) doulink* llast = last->prev;//找到刪除后的新的尾結(jié)點(diǎn) if (last == head) { printf("Empty List\n"); return; } (*head).prev = llast;//改變哨兵結(jié)點(diǎn)prev指向 llast->next = last->next;//讓新的尾結(jié)點(diǎn)的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)注服務(wù)器之家其它相關(guān)文章!
感謝閱讀~
原文鏈接:https://blog.csdn.net/weixin_52199109/article/details/115240381