线性表是最简单的数据结构之一,
一个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储),但是把最后一个数据元素的尾指针指向了首位结点)。
线性表定义(sqList.h文件):
// // Created by tioncico on 19-4-25. // #ifndef TEST\_SQLIST\_H #define TEST\_SQLIST\_H #include <stdlib.h> #include <stdio.h> #include <string.h> #define LIST\_INIT\_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量(当存储空间不够时要用到,暂时未使用`1) typedef int listElemType; typedef struct { listElemType *elem; int length; int listSize; } sqList; int initList(sqList *); int destroyList(sqList *); int listEmpty(sqList); int listLength(sqList); int getElem(sqList ,int,listElemType *); int getElemLocation(sqList,listElemType); int getElemPrior(sqList,listElemType,listElemType *); int getElemNext(sqList,listElemType,listElemType *); int insertList(sqList *,int ,listElemType); int deletList(sqList *, int,listElemType *); void printList(sqList); #endif //TEST\_SQLIST\_H
线性表操作方法(sqList.c文件):
// // Created by tioncico on 19-4-24. // #include "sqList.h" /** * 初始化线性表 * @param list * @return */ int initList(sqList *list) { //给data分配内存空间 list->elem = (listElemType *) malloc(sizeof(listElemType) * LIST\_INIT\_SIZE); if (list->elem == NULL) { return -1; } list->length = 0; list->listSize = LIST\_INIT\_SIZE; return 0; } /** * 判断线性表是否不为空 * @param list * @return */ int listEmpty(sqList list) { if (list.length == 0) { return 0; } else { return -1; } } /** * 获取表长度 * @param list * @return */ int listLength(sqList list) { return list.length; } /** * 获取i位置的元素 * @param list * @param i * @param elemType * @return */ int getElem(sqList list, int i, listElemType *elemType) { if (i < 0 || i > list.length) { return -1; } *elemType = list.elem\[i\]; return 0; } /** * 获取某个元素的位置 * @param list * @param elemType * @return */ int getElemLocation(sqList list, listElemType elemType) { for (int i = 0; i < list.length; ++i) { if (list.elem\[i\] == elemType) { return i; } } return -1; } /** * 获取某个元素之前的元素 * @param list * @param elemType * @param priorElem * @return */ int getElemPrior(sqList list, listElemType elemType, listElemType *priorElem) { if (elemType == list.elem\[0\]) { return -1; } int i = getElemLocation(list, elemType); if (i == -1) { return -1; }else{ *priorElem = list.elem\[i-1\]; return 0; } return -1; } /** * 获取某个元素之后的元素 * @param list * @param elemType * @param priorElem * @return */ int getElemNext(sqList list, listElemType elemType, listElemType *priorElem) { if (elemType == list.elem\[list.length-1\]) { return -1; } int i = getElemLocation(list, elemType); if (i == -1) { return -1; }else{ *priorElem = list.elem\[i+1\]; return 0; } } /** * 删除该线性表 * @param list * @return */ int destroyList(sqList *list) { if (list->elem) { free(list->elem); } list->length = 0; return 0; } /** * 在位置i插入一条数据 * @param list * @param i * @param elemType * @return */ int insertList(sqList *list, int i, listElemType elemType) { if (i >= 0) { if (i > list->listSize) { return -1; } if (!list->elem) { return -1; } listElemType *q = NULL; q = &list->elem\[i\];//插入位置 listElemType *p = NULL; for (p = &list->elem\[list->length - 1\]; p >= q; p--) { *(p + 1) = *p; } *q = elemType; list->length++; // list->listSize += LISTINCREMENT; return 0; } else { i = list->length; return insertList(list, i, elemType); } } /** * 删除表 * @param list * @param i * @param e * @return */ int deletList(sqList \*list, int i, listElemType \*e) { if (i < 0 || i > list->listSize) { return -1; } listElemType *q = NULL; listElemType *p = NULL; q = &list->elem\[i\]; \*e = \*q;//获取到该元素 p = &list->elem\[list->length - 1\];//最后一个元素 for (; q <= p; q++) { \*q = \*(q - 1); } list->length--; return 0; } /** * 打印 * @param list */ void printList(sqList list) { printf("length:%d,size:%d \\n", list.length, list.listSize);; for (int i = 0; i < list.length; ++i) { if (i == 0) { printf("%d", list.elem\[i\]); } else { printf(",%d", list.elem\[i\]); } } printf("\\n"); }
调用方式:
#include <stdio.h> #include "sqList.h" int main() { sqList list; //初始化 int result = initList(&list); //指定位置插入数据 for (int i = 0; i < LIST\_INIT\_SIZE/2; ++i) { if (!insertList(&list,i,i*10)){ // printf("第%d个数%d插入列表\\n",list.length, list.elem\[list.length-1\]); } } //往后插入数据 insertList(&list,-1,666); printf("数据是否为空 %d\\n",listEmpty(list)); printf("数据长度 %d\\n",listLength(list)); listElemType elem1; getElem(list,13,&elem1); printf("获取13位置的值 %d\\n",elem1); printf("获取666值的位置 %d\\n",getElemLocation(list,666)); listElemType elem2; getElemPrior(list,666,&elem2); printf("获取666前面的值 %d\\n",elem2); listElemType elem3; getElemNext(list,666,&elem3); listElemType elem4; deletList(&list,15,&elem4); printf("获取15位置删除的值 %d\\n",elem4); printList(list); destroyList(&list); printList(list); return 0; }
输出:
/home/tioncico/CLionProjects/test/cmake-build-debug/test 数据是否为空 -1 数据长度 51 获取13位置的值 130 获取666值的位置 50 获取666前面的值 490 获取15位置删除的值 150 length:50,size:100 0,10,20,30,40,50,60,70,80,90,100,110,120,130,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,140 length:0,size:100