您好,登錄后才能下訂單哦!
這篇文章主要講解了“C語(yǔ)言順序表如何實(shí)現(xiàn)”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來(lái)研究和學(xué)習(xí)“C語(yǔ)言順序表如何實(shí)現(xiàn)”吧!
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu),一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組 上完成數(shù)據(jù)的增刪查改。
順序表一般可以分為:
靜態(tài)順序表:使用定長(zhǎng)數(shù)組存儲(chǔ)元素,元素的數(shù)目無(wú)法進(jìn)行修改。
//順序表的靜態(tài)存儲(chǔ) #define N 7 typedef int SLDataType; typedef struct SeqList { SLDataType array[N];//定長(zhǎng)數(shù)組 size_t size;//有效數(shù)據(jù)的個(gè)數(shù) }SeqList;
動(dòng)態(tài)順序表
//順序表的動(dòng)態(tài)存儲(chǔ) typedef struct SeqList { SLDataType* array;//指向動(dòng)態(tài)開(kāi)辟的數(shù)組,空間不夠可以增容 size_t size;//有效數(shù)據(jù)的個(gè)數(shù) size_t capacity;//容量空間的大小 };
靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場(chǎng)景。靜態(tài)順序表的定長(zhǎng)數(shù)組導(dǎo)致N定大了,空間開(kāi)多了浪 費(fèi),開(kāi)少了不夠用。所以現(xiàn)實(shí)中基本都是使用動(dòng)態(tài)順序表,根據(jù)需要?jiǎng)討B(tài)的分配空間大小,所以下面我們實(shí)現(xiàn)動(dòng)態(tài)順序表。
typedef int SLDataType;//順序表中存儲(chǔ)的數(shù)據(jù),此處假設(shè)是int型 typedef struct SeqList { int* a;//指向動(dòng)態(tài)開(kāi)辟的數(shù)組空間,空間可以隨時(shí)增容 int size;//存儲(chǔ)數(shù)據(jù)個(gè)數(shù) int capacity;//存儲(chǔ)空間大小 }SL,SeqList;
void SeqListInit(SeqList* psl);//聲明 void SeqListInit(SeqList* psl) { assert(psl);//進(jìn)行斷言是因?yàn)楫?dāng)psl為NULL時(shí),下面的操作將無(wú)法進(jìn)行,因?yàn)榭罩羔樖菬o(wú)法進(jìn)行解引用的。 psl->a = NULL; psl->size = 0; psl->capacity = 0; }//函數(shù)實(shí)現(xiàn)
注意:進(jìn)行斷言是因?yàn)楫?dāng)psl為NULL時(shí),下面的操作將無(wú)法進(jìn)行,因?yàn)榭罩羔樖菬o(wú)法進(jìn)行解引用的,后面也是如此。
void SeqListDestroy(SeqList* psl); void SeqListDestroy(SeqList* psl) { assert(psl); free(psl->a); psl->a = NULL; psl->capacity = psl->size = 0; }
注意:free后面括號(hào)中的指針必須是malloc開(kāi)辟出來(lái)的那塊空間,且不能有任何的偏差(即指針不能發(fā)生移動(dòng))。
下面進(jìn)行舉例:
像上面這樣使用是完全沒(méi)有問(wèn)題的,但是像下面這樣進(jìn)行使用就出現(xiàn)了問(wèn)題:
tmp進(jìn)行自增操作后,就指向了下圖所示位置:
free的位置是tmp++后的位置,這不符合C語(yǔ)言的規(guī)定,且即使正常的釋放掉了,前面的那一塊int空間也將引起內(nèi)存泄漏問(wèn)題,即動(dòng)態(tài)開(kāi)辟的內(nèi)存忘記釋放。
void SeqListPushBack(SeqList* psl,SLDataType x);//聲明 void SeqListPushBack(SeqList* psl, SLDataType x) { assert(psl); //如果滿了,就進(jìn)行擴(kuò)容 SeqListCheckCapacity(psl); psl->a[psl->size] = x; psl->size++; }
void SeqListPopBack(SeqList* psl); void SeqListPopBack(SeqList* psl) { assert(psl); if(psl->size > 0) { psl->size -= 1; } }
void SeqListPushFront(SeqList* psl, SLDataType x); void SeqListPushFront(SeqList* psl, SLDataType x) { assert(psl); SeqListCheckCapacity(psl); int end = psl->size - 1; while (end >= 0) { psl->a[end+1] = psl->a[end]; --end; } psl->a[0] = x; psl->size++; }
順序表的頭插會(huì)涉及到后續(xù)元素的移動(dòng),頭插時(shí)要將順序表中的元素從后面開(kāi)始進(jìn)行移動(dòng),因?yàn)閺那懊骈_(kāi)始移動(dòng)的話會(huì)出現(xiàn)覆蓋現(xiàn)象。下面是圖示:
同理,如果想要元素不被覆蓋,就只能從前向后進(jìn)行移動(dòng)。
void SeqListPopFront(SeqList* psl); void SeqListPopFront(SeqList* psl) { //挪出數(shù)據(jù),騰出頭部空間 //方法一:從1開(kāi)始移動(dòng) /*assert(psl); if (psl->size > 0) { int begin = 1; while (begin < psl->size) { psl->a[begin - 1] = psl->a[begin]; begin++; } psl->size--; }*/ //方法二:從0開(kāi)始移動(dòng) assert(psl); if (psl->size > 0) { int begin = 0; while (begin < psl->size - 1) { psl->a[begin] = psl->a[begin + 1]; begin++; } psl->size--; } }
下圖是兩種移動(dòng)方式的區(qū)別:
問(wèn):為什么不可以直接將指針進(jìn)行加1操作?
free釋放空間時(shí)的指針和malloc開(kāi)辟空間的指針必須相同
mallo開(kāi)辟的空間存在浪費(fèi),即0的那塊空間被浪費(fèi),無(wú)法進(jìn)行使用,因?yàn)槟菈K空間是被合法申請(qǐng)的。
void SeqListCheckCapacity(SeqList* psl); void SeqListCheckCapacity(SeqList* psl) { assert(psl); if (psl->capacity == psl->size) { size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { psl->a = tmp; psl->capacity *= 2; } } }
注意點(diǎn)1:此處考慮使用的是如果容量不夠,就將容量擴(kuò)容為原容量的兩倍,但是最開(kāi)始的容量是0,所以要考慮到最開(kāi)始為0的情況。
注意點(diǎn)2:要對(duì)擴(kuò)容是否成功進(jìn)行檢測(cè),即判斷剛申請(qǐng)的空間是否為空。
void SeqListInsert(SeqList* psl,size_t pos,SLDataType x); void SeqListInsert(SeqList* psl, size_t pos, SLDataType x) { assert(psl); //較為溫和的檢查方式 /*if (pos > psl->size) { exit(-1); }*/ assert(pos <= psl->size);//較為暴力的檢查方式 SeqListCheckCapacity(psl); size_t end = psl->size; while (end > pos) { psl->a[end] = psl->a[end-1]; --end; } psl->a[pos] = x; psl->size++; }
注意:
問(wèn):為什么end從psl->size開(kāi)始?
答:此處需要注意的是pos和end的類型,為什么呢?因?yàn)閮烧叨际菬o(wú)符號(hào)類型,所以尤其注意當(dāng)end到了-1的時(shí)候,就會(huì)變成一個(gè)很大的數(shù)字,此時(shí)如果以此作為下標(biāo)進(jìn)行訪問(wèn),一定會(huì)出現(xiàn)越界訪問(wèn)內(nèi)存的情況,考慮一種極端情況,當(dāng)pos為0的時(shí)候,end最小的時(shí)候就是為0,所以此時(shí)不會(huì)出現(xiàn)越界的情況,但是如果end是從psl->size - 1開(kāi)始的話,那么while循環(huán)體內(nèi)的語(yǔ)句就變成下面這樣:
while(end > pos) { psl->a[end+1] = psl->a[end]; --end; }
最后end的最小值會(huì)變成-1,但是因?yàn)閑nd是size_t類型,所以會(huì)變成一個(gè)很大的數(shù)字,在whle()循環(huán)條件判定時(shí)條件始終是滿足的,同時(shí)在進(jìn)入循環(huán)體內(nèi)之后,會(huì)出現(xiàn)越界訪問(wèn)內(nèi)存的操作。
void SeqListErase(SeqList* psl, size_t pos); void SeqListErase(SeqList* psl, size_t pos) { assert(psl); assert(pos <= psl->size); size_t begin = pos+1; while (begin < psl->size) { psl->a[begin-1] = psl->a[begin]; ++begin; } psl->size--; }
void SeqListPrint(SeqList* psl); void SeqListPrint(SeqList* psl) { assert(psl); for (int i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } printf("\n"); }
int SeqListFind(SeqList* psl,SLDataType x); int SeqListFind(SeqList* psl, SLDataType x) { assert(psl); for (int i = 0; i < psl->size; i++) { if (psl->a[i] == x) return i;//找到了對(duì)應(yīng)元素,返回相應(yīng)的下標(biāo) } return -1;//說(shuō)明沒(méi)有找到對(duì)應(yīng)的元素 }
void SeqListModify(SeqList* psl, size_t pos, SLDataType x); void SeqListModify(SeqList* psl, size_t pos, SLDataType x) { assert(psl); assert(pos < psl->size); psl->a[pos] = x; }
感謝各位的閱讀,以上就是“C語(yǔ)言順序表如何實(shí)現(xiàn)”的內(nèi)容了,經(jīng)過(guò)本文的學(xué)習(xí)后,相信大家對(duì)C語(yǔ)言順序表如何實(shí)現(xiàn)這一問(wèn)題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。