C语言线性表顺序表示及实现

线性表的概念

线性表是一种数据结构，它是由n(n≥0)个数据元素a1,a2,...,an 组成的有限序列（元素个数为0时，称为空表），并且这些数据元素遵循一定的线性关系。

线性表的存储结构

线性表的存储结构有两种：顺序存储和链式存储。顺序存储指的是用一段连续的存储单元依次存储线性表的数据元素，线性表中的元素在物理位置上也是相邻的；而链式存储则是通过每个元素记录下一个元素的地址，以此将节点链接在一起。

顺序存储结构

顺序存储结构也叫数组存储结构，它通常是用一个一维数组来实现。当需要第i个元素时，直接使用数组的下标索引即可。如果数组的长度不够大，可以使用realloc函数来重新分配更大的存储空间。

下面是一个C语言实现的线性表的顺序存储结构示例代码：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE]; // 用来存储数据元素的数组
    int length; // 顺序表的当前长度
} SeqList;

void InitList(SeqList* L) { // 初始化一个空线性表
    for (int i = 0; i < MAXSIZE; i++) {
        L->data[i] = 0; // 将所有元素初始化为0
    }
    L->length = 0; // 初始化长度为0
}

void ListInsert(SeqList* L, int i, int e) { // 在第i个位置插入元素e
    if (i < 1 || i > L->length+1 || L->length >= MAXSIZE) { // 判断i的范围是否有效，以及当前表是否已满
        printf("插入失败\n");
        return;
    }
    for (int j = L->length; j >= i; j--) { // 将第i个位置后面的所有元素后移
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e; // 空出来的第i个位置插入新的元素
    L->length++; // 线性表长度加1
}

void ListPrint(SeqList L) { // 输出线性表中的所有元素
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
}

int main() {
    SeqList L;
    InitList(&L); // 初始化一个空的线性表
    ListInsert(&L, 1, 10); // 在第1个位置插入元素10
    ListInsert(&L, 2, 20); // 在第2个位置插入元素20
    ListInsert(&L, 3, 30); // 在第3个位置插入元素30
    ListPrint(L); // 输出线性表中的所有元素
    return 0;
}

链式存储结构

链式存储结构也叫链表，它由节点组成，每个节点中存储数据以及指向下一个节点的指针。链表的插入和删除操作十分方便，但是读取节点时需要从头节点开始依次遍历节点，效率比顺序存储结构要低。

下面是一个C语言实现的线性表的单链表示例代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { // 定义链表节点
    int data; // 数据域
    struct Node* next; // 指向下一个节点的指针
} Node;

typedef struct { // 定义链表头节点
    struct Node* head; // 指向链表首节点的指针
    int length; // 链表的长度
} LinkList;

void InitList(LinkList* L) { // 初始化一个空链表
    L->head = (Node*) malloc(sizeof(Node));
    L->head->next = NULL; // 头节点的指针指向NULL，表示它是最后一个节点
    L->length = 0; // 初始化长度为0
}

void ListInsert(LinkList* L, int i, int e) { // 在第i个位置插入元素e
    if (i < 1 || i > L->length+1) { // 判断i的范围是否有效
        printf("插入失败\n");
        return;
    }
    Node* p = L->head;
    for (int j = 1; j < i; j++) { // 移动指针到第i-1个节点
        p = p->next;
    }
    Node* newNode = (Node*) malloc(sizeof(Node));
    newNode->data = e; // 在第i-1个位置后面插入一个新的节点
    newNode->next = p->next;
    p->next = newNode;
    L->length++; // 链表长度加1
}

void ListPrint(LinkList L) { // 输出链表中的所有元素
    Node* p = L.head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    LinkList L;
    InitList(&L); // 初始化一个空的链表
    ListInsert(&L, 1, 10); // 在第1个位置插入元素10
    ListInsert(&L, 2, 20); // 在第2个位置插入元素20
    ListInsert(&L, 3, 30); // 在第3个位置插入元素30
    ListPrint(L); // 输出链表中的所有元素
    return 0;
}

总结

以上是C语言线性表顺序表示及实现的完整攻略，其中包括了顺序存储结构和链式存储结构的详细说明以及代码示例。顺序存储结构适合数据元素数量较少、频繁进行查找操作的情况；链式存储结构适合进行频繁插入、删除操作的情况。在实际应用中需要根据具体的情况选择合适的存储方式。