順序表主要操作集的實(shí)現(xiàn)

  • 相關(guān)宏定義及數(shù)據(jù)類型的別名定義

    #define LIST_INIT_SIZE 10   // 初始化順序表的空間分配量
    #define LIST_INCREMENT 10   // 順序表空間用完后的分配增量
    
    #define OK 1    // 函數(shù)正常返回
    #define ERROR -1    // 函數(shù)異常返回
    
    #define EMPTY 0 // 表空
    #define NOT_EMPTY 1 // 表不空
    
    typedef int ElemType;   // 元素類型
    typedef int Status; // 狀態(tài)(用作返回值類型)
    typedef int Length; // 長(zhǎng)度
    typedef int Position; // 位序
    
    
  • 結(jié)構(gòu)定義

    typedef struct {
        ElemType *elem; //  存儲(chǔ)空間基址(首地址)
        int length;     //  已存儲(chǔ)的元素個(gè)數(shù)
        int list_size;  //  當(dāng)前分配的存儲(chǔ)量(目前可存儲(chǔ)元素的個(gè)數(shù))
    } SqList;
    
  • InitList():構(gòu)造一個(gè)空表

    Status InitList_Sq(SqList *L) {
    
        // 動(dòng)態(tài)分配存儲(chǔ)空間猛蔽,返回已分配空間的首地址
        L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    
        // 如果分配后返回地址為空 說(shuō)明分配失敗
        if (!L->elem)   
            exit(ERROR);
    
        L->length = 0; // 空表長(zhǎng)度為0
        L->list_size = LIST_INIT_SIZE; // 當(dāng)前分配量即為初始分配量
    
        return OK;
    }
    
  • DestroyList(): 銷毀線性表

    Status DestroyList_Sq(SqList *L) {
    
        // 如果傳入的線性表空間首地址為空 說(shuō)明初始化時(shí)空間分配異常 
        // 則直接異常終止進(jìn)程 之后的代碼將不被執(zhí)行
        if (!L->elem)   
            exit(EXIT_FAILURE);
        
        // 釋放 L->elem 指向的內(nèi)存
        free(L->elem);
    
        L->elem = NULL;
        L->length = 0;
        L->list_size = 0;
    
        return OK;
    }
    
  • ClearList():重置為空表

    Status ClearList_Sq(SqList *L) {
        if (!L->elem)   
            return ERROR;
    
        L->length = 0;
        return OK;
    }
    
  • ListEmpty(): 檢測(cè)該表是否為空

    Status ListEmpty_Sq(SqList *L) {
        return (L->length > 0) ? NOT_EMPTY : EMPTY;
    }
    
  • GetLength(): 獲取順序表中元素的個(gè)數(shù)

    Length GetLength_Sq(SqList *L) {
        return L->length;
    }
    
  • GetElem(): 用 e 返回 L 中下標(biāo)為 i 的元素的值

    Status GetElem_Sq(SqList *L, int i, ElemType *e) {
        // 若空間分配異常或表中無(wú)元素 異常返回
        if (!L->elem || L->length < 1)
            return ERROR;
    
        *e = L->elem[i];
        return OK;
    }
    
  • LocateElem(): 返回表中第一個(gè)與 e 值滿足關(guān)系 compare() 的元素的位序(非下標(biāo))

Position LocateElem_Sq(SqList *L, ElemType e, Status((*compare)(ElemType e1, ElemType e2))) {
    // 若順序表為空 返回錯(cuò)誤狀態(tài)
    if (ListEmpty_Sq(L) == EMPTY)   
        return ERROR;

    for (int i = 0; i < L->length; ++i) {
        // 將第 i 個(gè)元素與 e 值作為參數(shù)傳入 compare()仁堪,根據(jù)返回值判斷是否滿足該關(guān)系陨囊,若是墨微,則返回位序坞靶,否則繼續(xù)往下遍歷
        if ((*compare)(e, L->elem[i]) == OK)
            return i + 1;
        else
            continue;
    }
    
    return 0;
}
  • compare(): 這里使用相等關(guān)系表示 compare() 函數(shù)

    Status Equal(ElemType e1, ElemType e2) {
        return (e1 == e2) ? OK : ERROR;
    }
    
    • 調(diào)用舉例
    int main() {
        ...
        // 返回表中第一個(gè)值為 8 的元素的位序
        int pos = LocateElem_Sq(&L, 8,  Equal);
        
        // 例如對(duì)于順序表:{3, 8, 6, 0, 9, 7, 4, 11}辽剧,此時(shí) pos 的值應(yīng)為 2
        printf("%d", pos);
        ...
    }
    
  • GetKth(): 獲取第 k(位序排截,非下標(biāo)) 個(gè)元素

    Status GetKth(SqList *L, int k, ElemType *e) {
        // 1<=k<=length
        if (k < 1 || k > L->length) {
            return ERROR;
        } else {
            *e = L->elem[k - 1];
            return OK;
        }
    }
    
  • PriorElem(): 獲取 curElem 的前驅(qū)

    ElemType PriorElem_Sq(SqList *L, ElemType curElem, ElemType *pre_e) {
        // 先找到當(dāng)前元素的位序
        int locateRes = LocateElem_Sq(L, curElem, Equal);
    
        // ERROR:表空; 1: 位序?yàn)?,第1個(gè)元素?zé)o前驅(qū); 0: 表中未找到當(dāng)前元素
        if (locateRes == ERROR || locateRes == 1 || locateRes == 0) {
            if (locateRes == 1) {
                printf("\nERROR: 第一個(gè)元素?zé)o前驅(qū)挠蛉!");
            }
            else if (locateRes == 0) {
                printf("\nERROR: 目標(biāo)元素: %d 不存在祭示!", curElem);
            }
    
            return ERROR;
        }
    
        // 成功找到存在前驅(qū)的 curElem
        else {
            //  將位序?yàn)?locateRes - 1 的元素(即curElem的前驅(qū))值寫入 pre_e
            if (GetKth(L, locateRes - 1, pre_e) != ERROR) {
                return OK;
            }
            else {
                printf("\nERROR: 未找到指定元素: %d 的前驅(qū)!", curElem);
                return ERROR;
            }
        }
    }
    
  • NextElem(): 獲取 curElem 的后繼

    ElemType NextElem_Sq(SqList *L, ElemType curElem, ElemType *next_e) {
        int locateRes = LocateElem_Sq(L, curElem, Equal);
    
        // ERROR:表空; 1: 位序?yàn)閘ength谴古,最后1個(gè)元素?zé)o后繼; 0: 表中未找到當(dāng)前元素
        if (locateRes == ERROR || locateRes == L->length || locateRes == 0) {
            if (locateRes == L->length) {
                printf("\nERROR: 最后一個(gè)元素?zé)o后繼质涛!");
            }
            else if (locateRes == 0) {
                printf("\nERROR: 目標(biāo)元素: %d 不存在!", curElem);
            }
            return ERROR;
        }
        else {
            // 將位序?yàn)?locateRes + 1 的元素(即curElem的后繼)值寫入 next_e
            if (GetKth(L, locateRes + 1, next_e) != ERROR) {
                return OK;
            }
            else {
                printf("\nERROR: 未找到指定元素: %d 的前驅(qū)掰担!", curElem);
                return ERROR;
            }
        }
    }
    
  • 調(diào)用舉例:查看表中所有元素的前驅(qū)與后繼

    int main () {
        ...
        
        for (int i = 0; i < L.length; i++) {
            // cur_e 為當(dāng)前遍歷的元素
            ElemType cur_e = L.elem[i];
            
            // pre_e, next_e 分別表示指向前驅(qū)和后繼元素所占內(nèi)存空間的地址汇陆,均為臨時(shí)量,用完需要釋放
            ElemType *pre_e = (ElemType *)malloc(sizeof(ElemType));
            ElemType *next_e = (ElemType *)malloc(sizeof(ElemType));
            
            // 將 cur_e 的前驅(qū)元素的值寫入 pre_e
            if (PriorElem_Sq(&L, cur_e, pre_e) == ERROR) {
                *pre_e = -1;
            }
            
            // 將 cur_e 的后繼元素的值寫入 next_e
            if (NextElem_Sq(&L, cur_e, next_e) == ERROR) {
                *next_e = -1;
            }
            
            // 輸出 cur_e, pre_e, next_e
            printf("\npreElem: %d\ncurElem: %d\nnextElem: %d\n", *pre_e, cur_e, *next_e);
            
            // 釋放動(dòng)態(tài)空間
            free(pre_e);
            free(next_e);
        }
        
        ...
    }
    
    
  • ListInsert(): 在表中第 i 個(gè)元素之前插入元素 e

    Status ListInsert_Sq(SqList *L, int i, ElemType e) {
        //  i = 0: 在表頭插入元素带饱, i = length: 在表尾插入元素毡代,均合法,除此之外的都不合法
        if (i < 0 || i > L->length) {
            return ERROR;
        }
    
        //  若空間不足勺疼,需增大空間分配量
        if (L->length >= L->list_size) {
            ElemType *newbase;
            newbase = (ElemType*)realloc(L->elem, (LIST_INIT_SIZE + LIST_INCREMENT) * sizeof(ElemType));
            if (!newbase)   
                exit(EXIT_FAILURE);
                
            L->elem = newbase;
            L->list_size += LIST_INCREMENT;
        }
    
        //  從被插入的元素位置起教寂,至表尾元素止,整體移動(dòng)
        ElemType *q = &L->elem[i];
        ElemType *p = &L->elem[L->length - 1];
    
        // 從后向前逐個(gè)進(jìn)行值的遷移 為新值的插入騰出一個(gè)元素所需的空間
        while (p >= q) {
            *(p + 1) = *p;
            --p;
        }
        
        *q = e; // 給目標(biāo)插入位置賦值
        ++L->length;
    
        return OK;
    }
    
  • ListDelete(): 刪除指定下標(biāo)的元素执庐,并返回它的值

    Status ListDelete_Sq(SqList *L, int i, ElemType *e) {
        if (ListEmpty_Sq(L) == EMPTY)   return ERROR;
        if (i < 0 || i > L->length - 1) return ERROR;
    
        *e = L->elem[i];    // 目標(biāo)刪除元素的值
        
        ElemType *q = &L->elem[i + 1];  // 目標(biāo)刪除位置的后一個(gè)
        ElemType *p = &L->elem[L->length - 1];  // 表尾位置
    
        // 從前往后進(jìn)行元素的逐個(gè)遷移
        while (q <= p) {
            *(q - 1) = *q;
            q++;
        }
        --L->length;
        
        return *e;
    }
    
  • ListTraverse(): 對(duì)表中每個(gè)元素進(jìn)行遍歷

    Status ListTraverse_Sq(SqList *L, Status((*visit)(ElemType *curElem))) {
        if (ListEmpty_Sq(L) == EMPTY)
            return ERROR;
    
        for (int i = 0; i < L->length; ++i) {
            if ((*visit)(&L->elem[i]) == ERROR) {
                exit(EXIT_FAILURE);
            }
        }
        printf("\n");
        return OK;
    }
    
  • visit(): 這里使用打印輸出元素的值表示對(duì)單個(gè)元素的訪問(wèn)

    Status PrintElem(ElemType *curElem) {
        if (!curElem)
            return ERROR;
    
        printf("%d ", *curElem);
        return OK;
    }
    
    • 調(diào)用舉例
    int main() {
        ...
        // 以 PrintElem 作為 Visit 方法遍歷順序表 L酪耕,程序?qū)⒋蛴≥敵?L 中每個(gè)元素的值
        ListTraverse_Sq(&L, PrintElem);
        ...
    }
    
  • AssignElem(): 自定義表長(zhǎng)并為各元素賦值

    Status AssignElem_Sq(SqList *L, int *assign_size) {
        // 傳入的表還未分配內(nèi)存空間,錯(cuò)誤
        if (!L->elem)   
            exit(EXIT_FAILURE);
    
        printf("Input the assignment size: ");
    
        // 欲賦值的個(gè)數(shù)轨淌,即表長(zhǎng)
        scanf_s("%d", assign_size, 1); 
    
        // 欲賦值的個(gè)數(shù)大于當(dāng)前已有的空間迂烁,錯(cuò)誤
        if (*assign_size > L->list_size)    
            exit(EXIT_FAILURE);     
    
        // 依次為各元素賦值
        for (int i = 0; i < *assign_size; ++i) {
            scanf_s("%d", &L->elem[i], 1);
            L->length++;
        }
    
        return OK;
    }
    
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市递鹉,隨后出現(xiàn)的幾起案子盟步,更是在濱河造成了極大的恐慌,老刑警劉巖梳虽,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件址芯,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡窜觉,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門北专,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)禀挫,“玉大人,你說(shuō)我怎么就攤上這事拓颓∮镉ぃ” “怎么了?”我有些...
    開封第一講書人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)砰左。 經(jīng)常有香客問(wèn)我匿醒,道長(zhǎng),這世上最難降的妖魔是什么缠导? 我笑而不...
    開封第一講書人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任唐责,我火速辦了婚禮懦傍,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘。我一直安慰自己呆贿,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開白布微服。 她就那樣靜靜地躺著葡兑,像睡著了一般。 火紅的嫁衣襯著肌膚如雪立膛。 梳的紋絲不亂的頭發(fā)上揪罕,一...
    開封第一講書人閱讀 52,821評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音宝泵,去河邊找鬼耸序。 笑死,一個(gè)胖子當(dāng)著我的面吹牛鲁猩,可吹牛的內(nèi)容都是我干的坎怪。 我是一名探鬼主播,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼廓握,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼搅窿!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起隙券,我...
    開封第一講書人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤男应,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后娱仔,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體沐飘,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年牲迫,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了耐朴。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡盹憎,死狀恐怖筛峭,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情陪每,我是刑警寧澤影晓,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布镰吵,位于F島的核電站,受9級(jí)特大地震影響挂签,放射性物質(zhì)發(fā)生泄漏疤祭。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一饵婆、第九天 我趴在偏房一處隱蔽的房頂上張望勺馆。 院中可真熱鬧,春花似錦啦辐、人聲如沸谓传。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)续挟。三九已至,卻和暖如春侥衬,著一層夾襖步出監(jiān)牢的瞬間诗祸,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工轴总, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留直颅,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓怀樟,卻偏偏與公主長(zhǎng)得像功偿,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子往堡,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361