c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之順序表的定義實(shí)現(xiàn)詳解
順序表的定義
順序表 —— 用順序存儲(chǔ)的方式實(shí)現(xiàn)線性表順序存儲(chǔ)。
把邏輯上相鄰的元素存儲(chǔ)在物理位置上也相鄰的存儲(chǔ)單元中,元素之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)
線性表是具有相同數(shù)據(jù)類(lèi)型的 n (n≥0) 個(gè)數(shù)據(jù)元素的有限序列,數(shù)據(jù)類(lèi)型相同說(shuō)明每個(gè)數(shù)據(jù)元素所占的空間是一樣大的
我們假設(shè)線性表第一個(gè)元素的存放位置(即首地址)是 LOC(L) ,LOC 是 location 的縮寫(xiě)
那么第二個(gè)元素的存放位置就是 LOC(L)+數(shù)據(jù)元素的大小
第三個(gè)元素的存放位置就是 LOC(L)+2*數(shù)據(jù)元素的大小,依此類(lèi)推…
那么,我們又怎么知道所存放的數(shù)據(jù)元素的大小呢?
學(xué)過(guò) C語(yǔ)言 的小伙伴肯定知道,C語(yǔ)言 中有一個(gè)函數(shù) sizeof() 可以幫上我們的忙,我們用 sizeof(ElemType)
這樣調(diào)用的方式就能得到對(duì)應(yīng)數(shù)據(jù)元素的大小,其中的 ElemType 就是你的順序表中存放的數(shù)據(jù)元素類(lèi)型,比如 sizeof(int) = 4B
,一個(gè)整型一般是 4 個(gè)字節(jié);此外,我們還可以傳自己定義的類(lèi)型進(jìn)去,比如,我們定義一個(gè) Customer 類(lèi)型
typedef struct { int num; //號(hào)數(shù) int people; //人數(shù) } Customer;
相應(yīng)地,我們使用 sizeof(Customer)
就可以得到這個(gè)數(shù)據(jù)類(lèi)型的大小為 8B
順序表的實(shí)現(xiàn) —— 靜態(tài)分配
#define MaxSize 10 //定義最大長(zhǎng)度 typedef struct { ElemType data[MaxSize]; //用靜態(tài)的 “數(shù)組” 存放數(shù)據(jù)元素 int length; //順序表的當(dāng)前長(zhǎng)度 } SqList; //順序表的類(lèi)型定義(靜態(tài)分配方式)
ElemType data[MaxSize];
會(huì)給各個(gè)數(shù)據(jù)元素分配連續(xù)的存儲(chǔ)空間,大小為 MaxSize*sizeof(ElemType)
Sq:sequence —— 順序,序列
#include <stdio.h> #define MaxSize 10 //定義最大長(zhǎng)度 typedef int ElemType; typedef struct { ElemType data[MaxSize]; //用靜態(tài)的 “數(shù)組” 存放數(shù)據(jù)元素 int length; //順序表的當(dāng)前長(zhǎng)度 } SqList; //順序表的類(lèi)型定義 //基礎(chǔ)操作 —— 初始化一個(gè)順序表 void InitList(SqList &L) { for(int i = 0; i < MaxSize; i++) { L.data[i] = 0; //將所有數(shù)據(jù)元素設(shè)置為默認(rèn)初始值 } L.length = 0; } //主函數(shù) int main() { SqList L; //聲明一個(gè)順序表 InitList(L); //初始化順序表 //其他操作 return 0; }
如果在初始化順序表中不給 data 數(shù)組賦值為 0,會(huì)怎么樣呢?
#include <stdio.h> #define MaxSize 10 //定義最大長(zhǎng)度 typedef int ElemType; typedef struct { ElemType data[MaxSize]; //用靜態(tài)的 “數(shù)組” 存放數(shù)據(jù)元素 int length; //順序表的當(dāng)前長(zhǎng)度 } SqList; //順序表的類(lèi)型定義 //基礎(chǔ)操作 —— 初始化一個(gè)順序表 void InitList(SqList &L) { L.length = 0; } //主函數(shù) int main() { SqList L; //聲明一個(gè)順序表 InitList(L); //初始化順序表 //嘗試“違規(guī)”打印整個(gè)數(shù)組 for(int i = 0; i < MaxSize; i++) { printf("data[%d]=%d\n", i, L.data[i]); } return 0; }
運(yùn)行這段代碼,你會(huì)看到很奇怪的數(shù)據(jù),或許和我的運(yùn)行結(jié)果不太一樣,這是正常的
為什么會(huì)顯示這些奇怪的數(shù)據(jù)呢?
其實(shí)啊,程序在給我們這個(gè)數(shù)組分配內(nèi)存的時(shí)候,我們并不知道這塊內(nèi)存里面之前存儲(chǔ)過(guò)什么,如果我們不設(shè)置數(shù)據(jù)元素的默認(rèn)值,就會(huì)出現(xiàn)這樣的結(jié)果
其實(shí),我們這樣訪問(wèn)也是違規(guī)的,因?yàn)槌跏蓟樞虮淼臅r(shí)候 length 是為 0 的,我們要遍歷的條件應(yīng)該是 i < L.length;
才對(duì),所以數(shù)據(jù)元素的初始化是可以省略的,不過(guò) length 的初始化這一步驟就不能省略了
如果我們定義的 “數(shù)組” 存滿了,怎么辦呢?
建議直接放棄治療,順序表的表長(zhǎng)剛開(kāi)始確定后就無(wú)法更改了,因?yàn)槲覀兪庆o態(tài)分配空間
有小伙伴就說(shuō),那我一開(kāi)始就聲明一個(gè)很長(zhǎng)的順序表不就行了,但這樣的后果是會(huì)浪費(fèi)我們的內(nèi)存空間,從這里我們就可以看出來(lái)靜態(tài)分配的局限性了
順序表的實(shí)現(xiàn) —— 動(dòng)態(tài)分配
#define InitSize 10 //順序表的初始長(zhǎng)度 typedef struct { ElemType *data; //指示動(dòng)態(tài)分配數(shù)組的指針 int MaxSize; //順序表的最大容量 int length; //順序表的當(dāng)前長(zhǎng)度 } SqList; //順序表的類(lèi)型定義
C語(yǔ)言 中提供了 malloc 和 free 這兩個(gè)函數(shù)來(lái)讓我們動(dòng)態(tài)申請(qǐng)和釋放內(nèi)存空間
malloc 會(huì)申請(qǐng)一整片連續(xù)的存儲(chǔ)空間,然后返回一個(gè)指向這一片存儲(chǔ)空間開(kāi)始地址的指針,同時(shí)需要我們強(qiáng)制轉(zhuǎn)型為定義的數(shù)據(jù)元素類(lèi)型指針
malloc 函數(shù)的參數(shù),指明了要分配多大的連續(xù)內(nèi)存空間
L.data = (ElemType *) malloc(sizeof(ElemType) * InitSize);
如果你學(xué)習(xí)過(guò) C++,那你也可以使用 new 和 delete 這兩個(gè)函數(shù)來(lái)實(shí)現(xiàn)同樣的功能
#include <stdio.h> #include <stdlib.h> //使用 malloc 和 free 函數(shù)所需的頭文件 #define InitSize 10 //默認(rèn)最大長(zhǎng)度 typedef int ElemType; //方便我們改變類(lèi)型 typedef struct { ElemType *data; //指示動(dòng)態(tài)分配數(shù)組的指針 int MaxSize; //順序表的最大容量 int length; //順序表的當(dāng)前長(zhǎng)度 } SqList; //順序表的類(lèi)型定義 //初始化順序表 void InitList(SqList &L); //增加動(dòng)態(tài)數(shù)組的長(zhǎng)度 void IncreaseSize(SqList &L, int len); //主函數(shù) int main() { SqList L; //聲明一個(gè)順序表 InitList(L); //初始化順序表 IncreaseSize(L, 5); return 0; } //初始化順序表 void InitList(SqList &L) { //用 malloc 函數(shù)申請(qǐng)一片連續(xù)的存儲(chǔ)空間 L.data = (ElemType *)malloc(sizeof(ElemType)* InitSize); L.length = 0; L.MaxSize = InitSize; } //增加動(dòng)態(tài)數(shù)組的長(zhǎng)度 void IncreaseSize(SqList &L, int len) { ElemType *p = L.data; //將L數(shù)據(jù)存儲(chǔ)起來(lái) L.data = (ElemType *)malloc(sizeof(ElemType)* (L.MaxSize + len)); for (int i = 0; i < L.length; i++) { L.data[i] = p[i]; //將數(shù)據(jù)復(fù)制到新區(qū)域 } L.MaxSize = L.MaxSize + len; //順序表最大長(zhǎng)度增加 len free(p); //釋放臨時(shí)的內(nèi)存空間 }
注意:realloc 函數(shù)也可以實(shí)現(xiàn),但建議初學(xué)者使用 malloc 和 free 更能理解背后的過(guò)程
順序表的特點(diǎn):
- 隨機(jī)訪問(wèn),既可以在 O(1) 時(shí)間內(nèi)找到第 i 個(gè)元素,代碼實(shí)現(xiàn)為
data[i - 1]
- 存儲(chǔ)密度高,每個(gè)節(jié)點(diǎn)只存儲(chǔ)數(shù)據(jù)元素
- 拓展容量不方便,即便采用動(dòng)態(tài)分配的方式實(shí)現(xiàn),拓展長(zhǎng)度的時(shí)間復(fù)雜度也比較高
- 插入、刪除操作不方便,需要移動(dòng)大量元素
到此這篇關(guān)于c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之順序表的定義實(shí)現(xiàn)詳解的文章就介紹到這了,更多相關(guān)c語(yǔ)言順序表的定義內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語(yǔ)言項(xiàng)目小學(xué)生數(shù)學(xué)考試系統(tǒng)參考
今天小編就為大家分享一篇關(guān)于C語(yǔ)言項(xiàng)目小學(xué)生數(shù)學(xué)考試系統(tǒng)參考,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧2019-02-02C語(yǔ)言實(shí)現(xiàn)求最大公約數(shù)的三種方法
最大公因數(shù),也稱最大公約數(shù)、最大公因子,指兩個(gè)或多個(gè)整數(shù)共有約數(shù)中最大的一個(gè)。本文將為大家介紹三種方法來(lái)實(shí)現(xiàn)求解兩個(gè)正整數(shù)的最大公約數(shù),需要的可以參考一下2021-12-12VSCode遠(yuǎn)程開(kāi)發(fā)調(diào)試服務(wù)器c/c++代碼
語(yǔ)音相關(guān)的好多項(xiàng)目要在linux上跑,但代碼開(kāi)發(fā)大多是在PC機(jī)上,本篇簡(jiǎn)單介紹一下怎么在個(gè)人電腦上用VSCode遠(yuǎn)程開(kāi)發(fā)調(diào)試服務(wù)器上的c/c++代碼。感興趣的朋友跟隨小編一起看看吧2020-04-04C++中為何推薦要把基類(lèi)析構(gòu)函數(shù)設(shè)置成虛函數(shù)
這篇文章主要介紹了C++中為何推薦要把基類(lèi)析構(gòu)函數(shù)設(shè)置成虛函數(shù)問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-12-12C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)順序表的進(jìn)階講解
程序中經(jīng)常需要將一組數(shù)據(jù)元素作為整體管理和使用,需要?jiǎng)?chuàng)建這種元素組,用變量記錄它們,傳進(jìn)傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個(gè)數(shù)可能發(fā)生變化,順序表則是將元素順序地存放在一塊連續(xù)的存儲(chǔ)區(qū)里,元素間的順序關(guān)系由它們的存儲(chǔ)順序自然表示2022-04-04