《数据结构》顺序线性表

《数据结构》顺序线性表 /******************************************************************* ************ /* <PRE> : - /* 版权所有 /* 模块名 : 线性表 /* 文件名 : sqlist.cpp : 线性表的顺序表示与实现 /* 功能描述 /* 作者 : <xxx> /* 版本 : 1.0 /* ----------------------------------------------------------------------------- /* 备 注 : - /* ----------------------------------------------------------------------------- /* 修改记 录 : /* 日 期 版本 修改人 修改 1.0 <xxx> 创建 /* </PRE> ******************************************************************* ************/ #include <stdio.h> #include <stdlib.h> /******************************************************************* *********** /* 数据类型和常量定义 /******************************************************************* ***********/ #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef int ElemType; /******************************************************************* *********** /* 数据结构声明 /******************************************************************* ***********/ /* 线性表的动态分配顺序存储结构 */ #define LIST_INIT_SIZE 2 /* 线性存储空间的初始分配量 */ #define LISTINCREMENT 1 /* 线性存储空间的分配增量 */ typedef struct { ElemType *elem; /* 存储空间基址 */ int length; /* 当前长度 */ int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ } SqList; /******************************************************************* ************ /* <FUNC> /* 函数名 : InitList_Sq /* 功能 : 构造空线性表 /* 参数 : - /* 返回值 : - : 构造一个空的线性表 /* 备注 /* 作者 : <xxx> /* </FUNC> ******************************************************************* ************/ Status InitList_Sq(SqList &L) { L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if (!L.elem) exit(OVERFLOW); L.length = 0; //空表长度为0 L.listsize = LIST_INIT_SIZE; //初始存储容量 return OK; } /******************************************************************* ************ /* <FUNC> /* 函数名 : ListInsert_Sq /* 功能 : 在线性表中插入元素 /* 参数 : - /* 返回值 : - /* 备注 : 在顺序线性表L中第i个位置之前插入新的元素e, i的合法值 为 1<= i <= ListLength_Sq(L) + 1 /* 作者 : <xxx> /* </FUNC> ******************************************************************* ************/ Status ListInsert_Sq(SqList &L, int i, ElemType e) { ElemType *newbase = NULL; ElemType *p = NULL; ElemType *q = NULL; if (i <1 || i >L.length + 1) return ERROR; if (L.length >= L.listsize) { newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType)); if (!newbase) exit(OVERFLOW); L.elem = newbase; L.listsize += LISTINCREMENT; } q = &(L.elem[i - 1]); for (p = &(L.elem[L.length - 1]); p >= q; --p) *(p + 1) = *p; *q = e; ++L.length; return OK; } /******************************************************************* ************ /* <FUNC> /* 函数名 : ListDelete_Sq /* 功能 : 删除线性表中的元素 /* 参数 : - /* 返回值 : - /* 备注 : 在顺序线性表L中删除第i个元素, 并用e返回其值, i的合法值 为 1<= i <= ListLength_Sq(L) /* 作者 : <xxx> /* </FUNC> ******************************************************************* ************/ Status ListDelete_Sq(SqList &L, int i, ElemType &e) { ElemType *p = NULL; ElemType *q = NULL; if ((i < 1) || (i > L.length)) return ERROR; p = &(L.elem[i - 1]); e = *p; q = L.elem + L.length - 1; //表尾元素位置 for (++p; p <= q; ++p) *(p - 1) = *p; //被删除元素之后的元素左移 --L.length; return OK; } /******************************************************************* ************ /* <FUNC> /* 函数名 : ListTraverse /* 功能 : 遍历线性表 /* 参数 : - /* 返回值 : - /* 备注 : - /* 作者 : <xxx> /* </FUNC> ******************************************************************* ************/ Status ListTraverse_Sq(SqList &L, Status (*Visit)(ElemType)) { ElemType *p = NULL; ElemType *q = NULL; if (L.length == 0) return ERROR; p = &(L.elem[0]); q = L.elem + L.length - 1; //表尾元素位置 for (; p <= q; ++p) Visit(*p); return OK; } /******************************************************************* ************ /* <FUNC> /* 函数名 : Visit /* 功能 : 访问线性表中的元素 /* 参数 : - /* 返回值 : - /* 备注 : - /* 作者 : <xxx> /* </FUNC> ******************************************************************* ************/ Status Visit(ElemType e) { printf("%d ", e); return OK; } /******************************************************************* ************ /* <FUNC> /* 函数名 : main /* 功能 : 测试函数 /* 参数 : - /* 返回值 : - /* 备注 : - /* 作者 : <xxx> /* </FUNC> *******************************************************************************/ void main() { SqList L; InitList_Sq(L); ElemType e; //遍历空表 if (OK == ListTraverse_Sq(L, Visit)) printf("visit succeed!\n" ); //插入元素 if (OK == ListInsert_Sq(L, 1, 10)) printf("insert succeed!\n"); if (OK == ListInsert_Sq(L, 2, 20)) printf("insert succeed!\n"); if (OK == ListInsert_Sq(L, 1, 30)) printf("insert succeed!\n"); if (OK == ListInsert_Sq(L, 2, 40)) printf("insert succeed!\n"); if (OK == ListInsert_Sq(L, 1, 50)) printf("insert succeed!\n"); //遍历非空表 if (OK == ListTraverse_Sq(L, Visit)) printf("visit succeed!\n"); //删除元素 if (OK == ListDelete_Sq(L, 1, e)) printf("delete %d succeed!\n", e); if (OK == ListDelete_Sq(L, 3, e)) printf("delete %d succeed!\n", e); if (OK == ListDelete_Sq(L, 2, e)) printf("delete %d succeed!\n", e); //遍历非空表 if (OK == ListTraverse_Sq(L, Visit)) printf("visit succeed!\n"); }