順序表基本算法

順序表:
即線性表的順序存儲結(jié)構(gòu), 其邏輯結(jié)構(gòu)與物理存儲結(jié)構(gòu)一致.內(nèi)存分配連續(xù),需要考慮初始內(nèi)存分配和內(nèi)存追加的問題.

基礎(chǔ)算法:

1.類型定義&宏定義

#define C_TRUE 0
#define C_FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100 // 線性表存儲空間的初始分配量
#define LISTINCREMENT 10 // 線性表存儲空間的分配增量
typedef struct
{
    int *elem; // 首地址指針
    int length; // 長度
    int listsize; // 當前分配的存儲容量
}List;

2.創(chuàng)建空表

int ListInit(List *L) {
    L->elem = (int *)malloc(LIST_INIT_SIZE *sizeof(int));
    if (NULL == L->elem) exit(OVERFLOW);
    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
    return OK;
}

3.追加元素

int ListAdd(List *L, int e) {
    if (L->length >= L->listsize) {
        int *newbase = (int *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(int));
        if (!newbase) exit(OVERFLOW);
        L->elem = newbase;
        L->listsize += LISTINCREMENT;
    }
    L->elem[L->length] = e;
    L->length++;
    return OK;
}

4.插入元素

// 在第i個元素之前插入一個元素elem
int ListInsert(List *L, int i, int e) {
    // 保證i合法, i可以插到最后一個元素后面, 假定插入最后一個元素后面一個元素前面
    if (i<1 || i>L->length + 1) {
        printf("位置不合法");
        return ERROR;
    }
    
    if (L->length >= L->listsize) // 存儲空間滿, 增加分配
    {
        /* code */
        int *newbase = (int *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(int));
        if (!newbase) exit(OVERFLOW); // OVERFLOW 內(nèi)存溢出
        L->elem = newbase; // 新基址
        L->listsize += LISTINCREMENT;
    }
   
    // 插入的位置, 這里的位置不是數(shù)組元素下標, 而是實際物理地址,也可以用下標實現(xiàn) 
    int *q = &(L->elem[i - 1]);
    for (int *p = &(L->elem[L->length - 1]); p >= q; --p) {
        *(p + 1) = *p;
    }
    *q = e;
    L->length++;
    return OK;
}

5.遍歷

void ListTraversal(List L) {
    for (int i = 0; i<L.length; i++) {
        printf("長度為:%d, 下標為%d的元素: %d\n", L.length ,i,L.elem[i]);
    }
}

6.刪除

int ListDelete(List * L, int pos) {
    if (pos<0 || pos>L->length-1) {
        printf("刪除位置不合法\n");
        return ERROR;
    }
    int *q = L->elem + pos;
    int *p = L->elem + L->length - 1;
    for (++q; q<=p; ++q) *(q-1) = *q;
    --L->length;
    return OK;
}

7.取元素

// 取出第 i 個元素并賦值給*pE;
int ListGeteElem(List p, int i, int *pE) {
    if (i<1 || i>p.length) {
        printf("取元素位置不合法\n");
        return ERROR;
    }
    *pE = p.elem[i-1];
    printf("第%d個元素為: %d\n", i,*pE);
    return OK;
}

8.判斷是否為空

int ListIsEmpty(List L) {
    if (L.length==0) {
        printf("表為空\n");
        return C_TRUE;
    } else {
        printf("表不為空\n");
        return C_FALSE;
    }
}

9.歸并

// La Lb 都是遞增的, 歸并后 pC 也需要遞增
void ListMerge(List La, List Lb, List *pC) {
    ListInit(pC);
    int i, j;
    i = j = 1;
    int ai;
    int bj;
    while (i<=La.length && j<=Lb.length) { // 保證都不越界
        ListGeteElem(La, i, &ai); ListGeteElem(Lb, j, &bj);
        if (ai < bj) {
            ListAdd(pC, ai); // 如果ai小, 把ai放進pC, j不能加, 繼續(xù)與ai+1比較
            i++;
        } else {
            ListAdd(pC, bj); // 同理
            j++;
        }
    }
    while (i<=La.length) {
        ListGeteElem(La, i++, &ai);
        ListAdd(pC,ai);
    }
    while (i<=Lb.length) {
        ListGeteElem(Lb, i++, &ai);
        ListAdd(pC,ai);
    }
}

總結(jié):
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的過程考慮到內(nèi)存溢出, 數(shù)組越界等問題訓(xùn)練程序員所寫代碼的健壯性, 對比一些其他語言, C是直接操作內(nèi)存的, 有些語言如OC在內(nèi)存分配失敗(即alloc失敗)時一般不做任何處理, 雖然失敗的概率很小, 但就代碼的嚴謹性來說C語言更勝一籌.

在學(xué)習(xí)過程中, 值得注意的兩點, 一是什么時候參數(shù)傳遞指針, 什么時候直接傳值, 我的總結(jié)是: 使用時傳值, 修改時傳遞指針; 因為使用是使用值, 而改變則需要知道修改哪塊內(nèi)存對應(yīng)的值.

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市贬芥,隨后出現(xiàn)的幾起案子币喧,更是在濱河造成了極大的恐慌曹步,老刑警劉巖定庵,帶你破解...
    沈念sama閱讀 206,378評論 6 481
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件产弹,死亡現(xiàn)場離奇詭異,居然都是意外死亡,警方通過查閱死者的電腦和手機惑畴,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,356評論 2 382
  • 文/潘曉璐 我一進店門慈格,熙熙樓的掌柜王于貴愁眉苦臉地迎上來盯另,“玉大人,你說我怎么就攤上這事要出∽狡” “怎么了倒得?”我有些...
    開封第一講書人閱讀 152,702評論 0 342
  • 文/不壞的土叔 我叫張陵,是天一觀的道長夭禽。 經(jīng)常有香客問我霞掺,道長,這世上最難降的妖魔是什么讹躯? 我笑而不...
    開封第一講書人閱讀 55,259評論 1 279
  • 正文 為了忘掉前任菩彬,我火速辦了婚禮,結(jié)果婚禮上潮梯,老公的妹妹穿的比我還像新娘骗灶。我一直安慰自己,他們只是感情好秉馏,可當我...
    茶點故事閱讀 64,263評論 5 371
  • 文/花漫 我一把揭開白布耙旦。 她就那樣靜靜地躺著,像睡著了一般萝究。 火紅的嫁衣襯著肌膚如雪免都。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,036評論 1 285
  • 那天帆竹,我揣著相機與錄音绕娘,去河邊找鬼。 笑死栽连,一個胖子當著我的面吹牛险领,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播秒紧,決...
    沈念sama閱讀 38,349評論 3 400
  • 文/蒼蘭香墨 我猛地睜開眼舷暮,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了噩茄?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 36,979評論 0 259
  • 序言:老撾萬榮一對情侶失蹤复颈,失蹤者是張志新(化名)和其女友劉穎绩聘,沒想到半個月后沥割,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 43,469評論 1 300
  • 正文 獨居荒郊野嶺守林人離奇死亡凿菩,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 35,938評論 2 323
  • 正文 我和宋清朗相戀三年机杜,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片衅谷。...
    茶點故事閱讀 38,059評論 1 333
  • 序言:一個原本活蹦亂跳的男人離奇死亡椒拗,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出获黔,到底是詐尸還是另有隱情蚀苛,我是刑警寧澤,帶...
    沈念sama閱讀 33,703評論 4 323
  • 正文 年R本政府宣布玷氏,位于F島的核電站堵未,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏盏触。R本人自食惡果不足惜渗蟹,卻給世界環(huán)境...
    茶點故事閱讀 39,257評論 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望赞辩。 院中可真熱鬧雌芽,春花似錦、人聲如沸辨嗽。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,262評論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽召庞。三九已至岛心,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間篮灼,已是汗流浹背忘古。 一陣腳步聲響...
    開封第一講書人閱讀 31,485評論 1 262
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留诅诱,地道東北人髓堪。 一個月前我還...
    沈念sama閱讀 45,501評論 2 354
  • 正文 我出身青樓,卻偏偏與公主長得像娘荡,于是被迫代替她去往敵國和親干旁。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 42,792評論 2 345

推薦閱讀更多精彩內(nèi)容

  • 第一章 Nginx簡介 Nginx是什么 沒有聽過Nginx炮沐?那么一定聽過它的“同行”Apache吧争群!Ngi...
    JokerW閱讀 32,642評論 24 1,002
  • Java8張圖 11、字符串不變性 12大年、equals()方法换薄、hashCode()方法的區(qū)別 13玉雾、...
    Miley_MOJIE閱讀 3,693評論 0 11
  • 愛情是什么樣子复旬,似乎一直都不是我想象的樣子。就像我走近你很遠冲泥,因為你不了解我驹碍;但你走近我很近,因為我了解你凡恍。 一 ...
    三言兩二拍閱讀 761評論 2 0
  • 剛在看到簡書一篇文章叫做《畢業(yè)以后志秃,我們過著死魚一樣的生活》。我沒有點開看咳焚,我能想象到內(nèi)容是什么洽损。只是這個...
    顰眉閱讀 234評論 0 0
  • 認識的人越少越好 不要沾染不適合自己的圈子 知己那么一兩個就足夠 沉住氣 別去巴結(jié)誰 別人的奇跡和你無關(guān) 得不到的...
    泡泡糖味的小果凍閱讀 398評論 0 1