C语言实现线性表

线性表是最简单的数据结构之一,

一个线性表是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