数据结构之C语言实现线性表

• 定义
• 基本操作
• 代码实现

数据结构三要素—逻辑结构、数据的运算、存储结构(物理结构)【存储结构不同，运算的实现方式就不同】

线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线
性表是一个空表。若用命名线性表，则其一般表示为

L = ( a 1 , a 2 , … , a i … , a n L=(a_1,a_2,…,a_i…,a_n L=(a1​,a2​,…,ai​…,an​

1. a i a_i ai​是线性表中的“第i个”元素线性表中的位序
2. a 1 a_1 a1​是表头元素； a n a_n an​是表尾元素
3. 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且只有一个直接后继。

InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。
DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
其他常用操作：
Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

#include
#include




#define INIT_SIZE 10 //初试长度
typedef struct {
    int length;//顺序表的长度
    int *data;//顺序表的内容
    int maxsize;//顺序表的最大长度
} SeqList;


int initList(SeqList *l) {
    //用malloc函数申请一片连续的存储空间
    //重点掌握为什么需要强转malloc()类型为int*类型
    //指针在移动是会根据sizeof(type)去进行移动，如果你不指定指针的类型，那么在指针移动检索的操作时，指针只会一个一个字节的去移动
    l->data = (int *) malloc(INIT_SIZE * sizeof(int));
    l->length = 0;
    l->maxsize = INIT_SIZE;
    return 1;
}


int increaseSize(SeqList *l, int len) {
    int *pInt = l->data;
    l->data = (int *) malloc(l->maxsize + len * sizeof(int));
    //复制
    for (int i = 0; i < l->length; ++i) {
        l->data[i] = pInt[i];//将数据复制到新区域
    }
    l->maxsize = l->maxsize + len;//顺序表的最大长度增加len
    free(pInt);//释放空间
    return 1;
}


int listInsert(SeqList *l, int i, int e) {
    for (int j = l->length; j >= i; --j) {
        l->data[j] = l->data[j - 1];
    }
    l->data[i] = e;
    l->length++;
    return 1;
}


int listDelete(SeqList *l, int i, int *e) {
    if (i < 1 || i > l->length) {
        return 0;
    }
    *e = l->data[i - 1];
    for (int j = i; j < l->length; j++) {
        l->data[j - 1] = l->data[j];
    }
    l->length--;
    return 1;

}


int getElem(SeqList l, int i) {
    return l.data[i - 1];
}


int locateElem(SeqList l, int e) {
    for (int i = 0; i < l.length; ++i) {
        if (e == l.data[i]) {
            return i + 1;
        }
    }
    return -1;
}

int main() {
    SeqList seqList;
    initList(&seqList);
    increaseSize(&seqList, 100);
    printf("%l", sizeof(seqList));
}