``` /************************************************************************ * * 程序名字： Sq_list.c * 作 者： sid_tapole * 版 本： 1.0.1 * 編寫時間： 2015年6月 * 功 能： 鏈表==>增刪改查、分支合并 * *************************************************************************/ #define INIT_SIZE_LIST 100 // 線性表初始空間分配量 #define INCREAMENT_LIST 10 // 線性表的分配增量 #define ELEM_TYPE int // 自定義類型 #define STATUS int // 自定義的類型 typedef struct { ELEM_TYPE *elem; // 線性表基址 int length; // 當前長度 int list_size; // 當前分配的存儲容量ELEM_TYPE } Sq_list; Sq_list L; /***************************************************** init_list_Sq BEGIN * * init_list_Sq 初始化鏈表 * * @param * &L 哨兵節點 * @return * STATUS 捕獲程序運行狀態 */ STATUS init_list_Sq(Sq_list &L) { // 構造一個空的線性表L L.elem = (ELEM_TYPE *)malloc(INIT_SIZE_LIST * sizeof(ELEM_TYPE)); if (!L.elem) { printf("分配空間失敗！程序異常退出！"); exit(-1); } L.length = 0; // 空表長度為0 L.list_size = INIT_SIZE_LIST; // 初始存儲容量 return 0; } //------------------------------------------------------ init_list_Sq END /**************************************************** insert_list_Sq BEGIN * * init_list_Sq 插入節點 * * @param * &L 哨兵節點 * @param * i 第i個節點 * @param * e 類型 * @return * STATUS 捕獲程序運行狀態 */ STATUS insert_list_Sq(Sq_list &L, int i, ELEM_TYPE e) { ELEM_TYPE *newbase = NULL; ELEM_TYPE *q, *p; /* ** 在順序線性表L中第i個位置之前插入新的元素e， ** i的合法值為 1<= i <=list_length_Sq(L) + 1 ** i 不合法，錯誤退出-1 */ if (i < 1 || i > L.length + 1) { return -1; } //當前存儲空間已滿，增加分配 if (L.length >= L.list_size) { newbase = (ELEM_TYPE *)realoc(L.elem, (L.list_size + INCREAMENT_LIST) * sizeof(ELEM_TYPE)); if (!newbase){ printf("分配空間失敗！程序異常退出！"); exit(-1); } L.elem = newbase; // 新基址 L.list_size += INCREAMENT_LIST; // 增加存儲容量 } q = &(L.elem[i -1]); // q為插入位置 for (p = &(L.elem[L.length -1]); p >= q; --p) { //插入位置及之后的元素右移 *(p + 1) = *p; } *q = e; // 插入e ++L.length; // 表長增1 return 0; } //----------------------------------------------------- insert_list_Sq end /**************************************************** delete_list_Sq BEGIN * * delete_list_Sq 刪除節點 * * @param * &L 哨兵節點 * @param * i 第i個節點 * @param * e 類型 * @return * STATUS 捕獲程序運行狀態 */ STATUS delete_list_Sq(Sq_list &L, int i, ELEM_TYPE &e) { ELEM_TYPE *p,*q; /* ** 在順序線性表L中刪除第i個元素，并用e返回其值 ** i的合法值為 1<= i <=list_length_Sq(L) ** i 不合法，錯誤退出-1 */ if (i < 1 || i > L.length) { exit (-1); } p = &(L.elem[i - 1]); // p為刪除元素的位置 e = *p; // 被刪除元素的值賦給e q = L.elem + L.length - 1; // 表尾元素的位置 for (++p; p <= q; ++p) { //被刪除元素之后的元素左移 *(p - 1) = *p; } --L.length; // 表長減1 return 0; } //----------------------------------------------------- delete_list_Sq end /***************************************************** local_list_Sq BEGIN * * local_list_Sq 查找 * * @param * &L 哨兵節點 * @param * e 類型 * @param * STATUS 常量 * @return * STATUS 捕獲程序運行狀態 */ STATUS local_list_Sq(Sq_list &L, ELEM_TYPE e, STATUS (*compare)(ELEM_TYPE,ELEM_TYPE)) { /* ** 在順序線性表L中查找第1個值與e滿足compare()的元素的位序 ** 若找到，則返回其在L中的位序，否則返回0 */ int i = 1; // i的初值為第一個元素的位序 ELEM_TYPE *p = L.elem; // p的初值為第一個元素的存儲位置 while (i <= L.length && !(*compare)(*p++, e)) { i++; } if (i <= L.length) { return i; } else { return 0; } } //----------------------------------------------------- local_list_Sq end /***************************************************** merge_list_Sq BEGIN * * local_list_Sq 合并分支鏈表 * * @param * La 鏈表A * @param * Lb 鏈表B * @param * &Lc 鏈表C哨兵 * @return * STATUS 捕獲程序運行狀態 */ STATUS merge_list_Sq(Sq_list La, Sq_list Lb, Sq_list &Lc) { /* ** 已知順序線性表La和Lb的元素按值非遞減排列 ** 歸并La和Lb得到新的線性表Lc，它的數據元素也按值非遞減排列。 */ ELEM_TYPE *pa_last, *pb_last, *pc, *pa, *pb; pa = La.elem; pb = Lb.elem; Lc.list_size = Lc.length = La.length + Lb.length; pc = Lc.elem = (ELEM_TYPE *)malloc(Lc.list_size*sizeof(ELEM_TYPE)); if (!Lc.elem) { printf("分配空間失敗！程序異常退出！"); exit(-1); } pa_last = La.elem + La.length - 1; pb_last = Lb.elem + Lb.length - 1; while (pa <= pa_last && pb <= pb_last) { // 歸并 if (*pa <= *pb) { *pc++ = *pa++; } else { *pc++ = *pb++; } } while (pa <= pa_last) { *pc++ = *pa++; // 插入La的剩余元素 } while (pb <= pb_last) { *pc++ = *pb++; // 插入La的剩余元素 } return 0; } //----------------------------------------------------- merge_list_Sq end ```