前言
數(shù)據(jù)結(jié)構(gòu)就是將大量而復(fù)雜的數(shù)據(jù)類(lèi)型和特定的存儲(chǔ)結(jié)構(gòu)保存到主存儲(chǔ)器宵呛，并在此基礎(chǔ)上為了實(shí)現(xiàn)某個(gè)功能而執(zhí)行的相應(yīng)操作论笔。 -- by 郝斌視頻
今天研究并實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中線(xiàn)性結(jié)構(gòu)之一的數(shù)組實(shí)現(xiàn)汹押。
數(shù)組就是一組連續(xù)存儲(chǔ)的數(shù)據(jù)或链。
要實(shí)現(xiàn)的功能:
- 拼接 append
- 添加 insert
- 刪除 delete
- 排序 sort
- 獲取數(shù)組長(zhǎng)度 len
- 判斷數(shù)組是否為空 isempty
- 判斷數(shù)組是否已滿(mǎn) isfull
- 打印顯示數(shù)組數(shù)據(jù) show
// 1. 創(chuàng)建數(shù)組
void init_arr(PARRAYLIST pArray, int len);
// 2. 獲取數(shù)組長(zhǎng)度
int len_arr(PARRAYLIST pArray);
// 3. 判斷數(shù)組是否為空
bool isempty_arr(PARRAYLIST pArray);
// 4. 判斷數(shù)組是否已滿(mǎn)
bool isfull_arr(PARRAYLIST pArray);
// 5. 拼接數(shù)據(jù)
bool append_arr(PARRAYLIST pArray, int val);
// 6. 插入數(shù)據(jù)
bool insert_arr(PARRAYLIST pArray, int pos, int val);
// 7. 刪除數(shù)據(jù)
bool delete_arr(PARRAYLIST pArray, int pos, int * pVal);
// 8. 數(shù)組排序
void sort_arr(PARRAYLIST pArray);
// 9. 打印顯示
void show_arr(PARRAYLIST pArray);
首先我們要?jiǎng)?chuàng)建一個(gè)數(shù)組，那么數(shù)組在代碼中怎么體現(xiàn)的呢理澎？面向?qū)ο笳Z(yǔ)言中，數(shù)組就是一個(gè)對(duì)象曙寡，C 語(yǔ)言是面向過(guò)程語(yǔ)言糠爬，并不存在對(duì)象一說(shuō)，因此可以考慮使用結(jié)構(gòu)举庶。
數(shù)組的結(jié)構(gòu)执隧，數(shù)組我們需要了解哪些東西
- 肯定是數(shù)據(jù)，而且是保存一長(zhǎng)串?dāng)?shù)據(jù)就會(huì)用到數(shù)組户侥，我們這里使用指針保存數(shù)據(jù)镀琉；
- 既然是一個(gè)不可變數(shù)組，需要給數(shù)組指定一個(gè)總長(zhǎng)度蕊唐；
- 然后在指定一個(gè)有效長(zhǎng)度屋摔，來(lái)保存數(shù)組中真實(shí)存儲(chǔ)的數(shù)據(jù)個(gè)數(shù)。
// 數(shù)據(jù)結(jié)構(gòu)：數(shù)組實(shí)現(xiàn)
typedef struct ArrayList {
int * pbase; // 保存數(shù)據(jù)的第一個(gè)指針
int len; // 數(shù)組長(zhǎng)度
int cnt; // 數(shù)組有效長(zhǎng)度
}ARRAYLIST, *PARRAYLIST;
OK,現(xiàn)在有數(shù)組了替梨，我們要操作一個(gè)對(duì)象是不是需要有這個(gè)對(duì)象吶凡壤，現(xiàn)在要?jiǎng)?chuàng)建一個(gè)數(shù)組，C 語(yǔ)言中結(jié)構(gòu)體并不會(huì)像面向?qū)ο笳Z(yǔ)言中的對(duì)象可以跨函數(shù)調(diào)用耙替。
C 語(yǔ)言中跨函數(shù)調(diào)用必須是動(dòng)態(tài)分配內(nèi)存亚侠，因此我們這個(gè)數(shù)組就需要我們動(dòng)態(tài)分配內(nèi)存。
接下來(lái)使用 malloc 函數(shù)俗扇，也就是 C 語(yǔ)言中動(dòng)態(tài)分配內(nèi)存的方法硝烂，創(chuàng)建數(shù)組并為其分配內(nèi)存。
/**
創(chuàng)建數(shù)組
@param pArray 操作數(shù)組
@param len 創(chuàng)建數(shù)組長(zhǎng)度
*/
void init_arr(PARRAYLIST pArray, int len)
{
// 1. 為指針域分配空間
pArray->pbase = (int *)malloc(sizeof(int)*len);
if (NULL == pArray->pbase) {
printf("內(nèi)存分配失敗!\n");
exit(-1);
}
// 初始化數(shù)組其他參數(shù)
pArray->len = len;
pArray->cnt = 0;
return;
}
現(xiàn)在有了數(shù)組铜幽，我們就應(yīng)該實(shí)現(xiàn)數(shù)組的方法了滞谢。
首先串稀，我們先實(shí)現(xiàn)獲取長(zhǎng)度的方法，也很簡(jiǎn)單狮杨，在結(jié)構(gòu)體 ArrayList 中我們保存了一個(gè) cnt 字段來(lái)表示有效長(zhǎng)度母截，所有我們數(shù)組的長(zhǎng)度就是這個(gè) cnt 字段的值。
/**
獲取數(shù)組長(zhǎng)度
@param pArray 操作數(shù)組
@return 數(shù)組長(zhǎng)度
*/
int len_arr(PARRAYLIST pArray)
{
return pArray->cnt;
}
然后橄教，判斷數(shù)組是否為空, 那么數(shù)組什么時(shí)候?yàn)榭漳厍蹇埽慨?dāng)然是數(shù)組中沒(méi)有數(shù)據(jù)，也就是數(shù)組有效長(zhǎng)度為 0 的時(shí)候护蝶。
/**
判斷數(shù)組是否為空
@param pArray 操作數(shù)組
@return 是否為空
*/
bool isempty_arr(PARRAYLIST pArray)
{
return pArray->cnt == 0;
}
接下來(lái)华烟，判斷數(shù)組是否已滿(mǎn)，那么數(shù)組什么時(shí)候已滿(mǎn)呢持灰？當(dāng)然是當(dāng)數(shù)組中的個(gè)數(shù)等于數(shù)組總長(zhǎng)度的時(shí)候盔夜。
/**
判斷數(shù)組是否已滿(mǎn)
@param pArray 操作數(shù)組
@return 數(shù)組是否已滿(mǎn)
*/
bool isfull_arr(PARRAYLIST pArray)
{
return pArray->cnt == pArray->len;
}
再然后，我們來(lái)實(shí)現(xiàn)拼接堤魁、插入和刪除的邏輯喂链。
拼接就是在數(shù)組最后插入一條數(shù)據(jù)，那么只要知道當(dāng)前數(shù)組的個(gè)數(shù) count妥泉，并將拼接數(shù)據(jù)插入到 count+1 的位置椭微，當(dāng)然不要忘記把我們有效數(shù)據(jù)的表示為 +1涛漂。
/**
拼接數(shù)據(jù)
@param pArray 操作數(shù)組
@param val 拼接數(shù)據(jù)
@return 拼接是否成功
*/
bool append_arr(PARRAYLIST pArray, int val)
{
if (isfull_arr(pArray)) {
printf("數(shù)組已滿(mǎn), 拼接操作失敗\n");
return false;
}
pArray->pbase[pArray->cnt] = val;
pArray->cnt ++;
return true;
}
插入操作需要接受三個(gè)參數(shù)赏表，一個(gè)是數(shù)組地址，一個(gè)
插入位置匈仗，最后是數(shù)值瓢剿。
其實(shí)拼接操作可以看做插入操作的一個(gè)特例，因?yàn)槲覀兛梢宰约河?jì)算出了悠轩，省略了插入位置间狂，由拼接操作可以推算出插入操作執(zhí)行步驟。
第一步火架，需要定位到要插入的位置鉴象。
第二步，插數(shù)據(jù)到這個(gè)位置何鸡。
咦纺弊，貌似不對(duì)，數(shù)據(jù)是插進(jìn)去骡男，位置也對(duì)淆游，但是數(shù)組的長(zhǎng)度怎么沒(méi)有變，好像少了一個(gè)數(shù)吧。
每次犹菱，我們是插入數(shù)據(jù)拾稳，但是我們把原來(lái)位置數(shù)據(jù)替換成了我們要插的數(shù)據(jù)，但是原來(lái)數(shù)據(jù)卻丟了腊脱！因此访得，我們需要在插數(shù)據(jù)前在執(zhí)行一個(gè)步驟。
將當(dāng)前位置數(shù)據(jù)以及其后所有數(shù)據(jù)都往后移動(dòng)一個(gè)位置陕凹，當(dāng)然不要忘記把我們有效數(shù)據(jù)的表示為 +1悍抑。
/**
插入數(shù)據(jù)
@param pArray 操作數(shù)組
@param pos 插入位置
@param val 插入值
@return 插入是否成功
*/
bool insert_arr(PARRAYLIST pArray, int pos, int val)
{
if (isfull_arr(pArray)) {
printf("數(shù)組已滿(mǎn), 拼接操作失敗\n");
return false;
}
if (0 > pos - 1 || pos > pArray->cnt + 1) {
printf("插入位置不合法!\n");
return false;
}
if (pos == pArray->cnt + 1) {
pArray->pbase[pos - 1] = val;
pArray->cnt ++;
return true;
}
int i ;
for (i = pArray->cnt; i >= pos - 1; -- i) {
pArray->pbase[i] = pArray->pbase[i - 1];
}
pArray->pbase[pos - 1] = val;
pArray->cnt ++;
return true;
}
刪除操作跟插入操作是反向操作。
既然插入操作要將插入位置以及之后的數(shù)據(jù)后移一位捆姜，那么作為死對(duì)頭传趾，刪除肯定就是將刪除位置之后的數(shù)據(jù)前移一位迎膜，然后修改有效數(shù)據(jù)的標(biāo)識(shí) -1泥技。
/**
刪除數(shù)據(jù)
@param pArray 操作數(shù)組
@param pos 刪除位置
@param pVal 刪除值
@return 是否刪除成功
*/
bool delete_arr(PARRAYLIST pArray, int pos, int * pVal)
{
if (isempty_arr(pArray)) {
printf("數(shù)組為空,不能執(zhí)行刪除操作!\n");
exit(-1);
}
if (0 > pos - 1 || pos > pArray->cnt) {
printf("刪除位置不合法!\n");
return false;
}
*pVal = pArray->pbase[pos - 1];
if (pos == pArray->cnt + 1) {
pArray->cnt --;
return true;
}
int i ;
for (i = pos - 1; i < pArray->cnt; ++ i) {
pArray->pbase[i] = pArray->pbase[i + 1];
}
pArray->cnt --;
return true;
}
最后就是數(shù)組排序和顯示了，對(duì)于接觸過(guò)面向?qū)ο笳Z(yǔ)言的各位磕仅，排序應(yīng)該是成罕客了，較為常見(jiàn)的排序有順序和冒泡兩種榕订，在這里就不啰嗦了店茶，直接上代碼
/**
數(shù)組排序
@param pArray 操作數(shù)組
*/
void sort_arr(PARRAYLIST pArray)
{
int i, j, t;
for (i = 0; i < pArray->cnt - 1; ++ i) {
for (j = i; j < pArray->cnt; ++ j) {
if (pArray->pbase[i] > pArray->pbase[j]) {
t = pArray->pbase[j];
pArray->pbase[j] = pArray->pbase[i];
pArray->pbase[i] = t;
}
}
}
}
/**
打印顯示
@param pArray 操作數(shù)組
*/
void show_arr(PARRAYLIST pArray)
{
int i ;
for (i = 0; i < pArray->cnt; ++ i) {
printf("%d ", pArray->pbase[i]);
}
printf("\n");
return;
}
到目前為止，C 語(yǔ)言實(shí)現(xiàn)數(shù)組的任務(wù)基本完工劫恒，剩下的就是測(cè)試和拓展新功能了贩幻。
如果各位客官有興趣可以在此基礎(chǔ)上完善，或者有什么需求也可以提出两嘴，如果我能完成也可以分享出來(lái)丛楚。
各路大牛輕噴，新手練手憔辫，有錯(cuò)請(qǐng)指出趣些。
下面放出完整代碼供大家學(xué)習(xí)，喜歡請(qǐng) star 謝謝贰您！
