数据结构c语言版：顺序表

顺序表的定义

? ?顺序表是一种线性数据结构，它由一组连续的存储单元组成，用来存储具有相同数据类型的元素。顺序表中的元素按照逻辑顺序依次存放，并且可以通过索引来访问和修改元素。

顺序表的实现方式

? ? ? ?两种：静态顺序表和动态顺序表。

• 静态顺序表：
  静态顺序表使用静态数组来实现，需要在创建顺序表时提前确定顺序表的大小。静态顺序表的大小是固定的，一旦分配了固定大小的存储空间，就不能动态地改变大小。因此，静态顺序表的容量是有限的，如果插入的元素超过了容量，就会导致溢出。
• ? ? ? ?优点：可以直接通过下标直接访问元素，访问元素速度快，时间复杂度是O（1）。
• ? ? ? ?缺点：插入与删除元素的操作比较耗时，需要移动其他元素，时间复杂度位O（n）。
• 动态顺序表：
• 动态顺序表使用动态数组来实现，可以根据需要动态调整顺序表的大小。动态顺序表的大小是可变的，当插入的元素超过当前容量时，会自动扩容，当删除元素后，如果剩余容量过多，可以缩小容量，以节省内存空间。
• ? ? ? ?优点：可以根据动态调整大小，灵活性较高。
• ? ? ? ?缺点：在插入和删除元素时，可能需要重新分配存储空间，导致一定的时间开销。

  ---

  静态顺序表的例子

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

// 定义静态顺序表的最大长度
#define MAX_SIZE 100

// 定义结构体，表示静态顺序表
struct SeqList 
{
    int data[MAX_SIZE];  // 数据数组
    int length;          // 当前表长
};

// 初始化顺序表
void initSeqList(struct SeqList* list) 
{
    list->length = 0;  // 初始化表长为0
}

// 插入元素到顺序表
int insertElement(struct SeqList* list, int position, int value) 
{
    // 检查插入位置的有效性
    if (position < 1 || position > list->length + 1 || list->length >= MAX_SIZE) 
    {
        printf("插入位置无效或表满，插入失败\n");
        return 0;  // 插入失败
    }

    // 将插入位置及之后的元素后移
    for (int i = list->length; i >= position; i--) 
    {
        list->data[i] = list->data[i - 1];
    }

    // 在插入位置处插入新元素
    list->data[position - 1] = value;

    // 表长加1
    list->length++;

    printf("插入成功\n");
    return 1;  // 插入成功
}

// 删除顺序表中指定位置的元素
int deleteElement(struct SeqList* list, int position) 
{
    // 检查删除位置的有效性
    if (position < 1 || position > list->length) 
    {
        printf("删除位置无效，删除失败\n");
        return 0;  // 删除失败
    }

    // 将删除位置之后的元素前移
    for (int i = position; i < list->length; i++) 
    {
        list->data[i - 1] = list->data[i];
    }

    // 表长减1
    list->length--;

    printf("删除成功\n");
    return 1;  // 删除成功
}

// 打印顺序表中的元素
void printSeqList(struct SeqList* list) 
{
    printf("顺序表元素：");
    for (int i = 0; i < list->length; i++) 
    {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

int main() 
{
    // 声明并初始化顺序表
    struct SeqList myList;
    initSeqList(&myList);

    // 在顺序表中插入元素
    insertElement(&myList, 1, 10);
    insertElement(&myList, 1, 20);
    insertElement(&myList, 1, 5);
    insertElement(&myList, 1, 6);
    // 打印顺序表
    printSeqList(&myList);

    // 删除顺序表中的元素
    deleteElement(&myList, 1);

    // 打印删除后的顺序表
    printSeqList(&myList);

    return 0;
}

上述程序实现了一个简单的静态顺序表，包括初始化、插入、删除和打印操作。大家可以自己修改插入，删除数据，体会其中的奥秘。

效果

动态顺序表的例子

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

// 定义动态顺序表的初始容量和增量
#define INIT_CAPACITY 10
#define INCREMENT 5

// 定义结构体，表示动态顺序表
struct SeqList 
{
    int* data;          // 数据指针
    int length;         // 当前表长
    int capacity;       // 当前容量
};

// 初始化顺序表
void initSeqList(struct SeqList* list) 
{
    list->data = (int*)malloc(INIT_CAPACITY * sizeof(int));  // 分配初始容量的内存
    list->length = 0;  // 初始化表长为0
    list->capacity = INIT_CAPACITY;  // 初始化容量为初始容量
}

// 销毁顺序表
void destroySeqList(struct SeqList* list) 
{
    free(list->data);  // 释放动态分配的内存
    list->data = NULL;  // 将指针置为空
    list->length = 0;  // 表长置为0
    list->capacity = 0;  // 容量置为0
}

// 打印顺序表中的元素
void printSeqList(struct SeqList* list) 
{
    printf("顺序表元素：");
    for (int i = 0; i < list->length; i++) 
    {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

// 自动增容
void increaseCapacity(struct SeqList* list) 
{
    int* newData = (int*)realloc(list->data, (list->capacity + INCREMENT) * sizeof(int));  // 重新分配内存
    if (newData != NULL) 
    {  // 分配成功
        list->data = newData;  // 将指针指向新的内存
        list->capacity += INCREMENT;  // 容量增加
        printf("自动增容成功，容量增加到%d\n", list->capacity);
    }
    else 
    {  // 分配失败
        printf("自动增容失败\n");
    }
}

// 插入元素到顺序表
int insertElement(struct SeqList* list, int position, int value) 
{
    // 检查插入位置的有效性
    if (position < 1 || position > list->length + 1) 
    {
        printf("插入位置无效，插入失败\n");
        return 0;  // 插入失败
    }

    // 如果表满，自动增容
    if (list->length >= list->capacity) 
    {
        increaseCapacity(list);
    }

    // 将插入位置及之后的元素后移
    for (int i = list->length; i >= position; i--) 
    {
        list->data[i] = list->data[i - 1];
    }

    // 在插入位置处插入新元素
    list->data[position - 1] = value;

    // 表长加1
    list->length++;

    printf("插入成功\n");
    return 1;  // 插入成功
}

// 删除顺序表中指定位置的元素
int deleteElement(struct SeqList* list, int position) 
{
    // 检查删除位置的有效性
    if (position < 1 || position > list->length) 
    {
        printf("删除位置无效，删除失败\n");
        return 0;  // 删除失败
    }

    // 将删除位置之后的元素前移
    for (int i = position; i < list->length; i++) 
    {
        list->data[i - 1] = list->data[i];
    }

    // 表长减1
    list->length--;

    printf("删除成功\n");
    return 1;  // 删除成功
}

// 查找元素在顺序表中的位置
int searchElement(struct SeqList* list, int value) 
{
    for (int i = 0; i < list->length; i++) 
    {
        if (list->data[i] == value) 
        {
            printf("元素%d在顺序表中的位置是%d\n", value, i + 1);
            return i + 1;  // 返回位置
        }
    }

    printf("元素%d不在顺序表中\n", value);
    return 0;  // 查找失败
}

int main() 
{
    // 声明并初始化顺序表
    struct SeqList myList;
    initSeqList(&myList);

    // 在顺序表中插入元素
    insertElement(&myList, 1, 10);
    insertElement(&myList, 2, 20);
    insertElement(&myList, 1, 5);

    // 打印顺序表
    printSeqList(&myList);

    // 删除顺序表中的元素
    deleteElement(&myList, 2);

    // 打印删除后的顺序表
    printSeqList(&myList);

    // 查找元素在顺序表中的位置
    searchElement(&myList, 20);
    searchElement(&myList, 30);

    // 销毁顺序表
    destroySeqList(&myList);

    return 0;
}

效果