Sq_list · 小白学电脑

``` /************************************************************************ * * 程序名字： 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 ```