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

2024-01-07 17:57:54

顺序表的定义

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


顺序表的实现方式

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

  • 静态顺序表:
    静态顺序表使用
    静态数组来实现,需要在创建顺序表时提前确定顺序表的大小。静态顺序表的大小是固定的,一旦分配了固定大小的存储空间,就不能动态地改变大小。因此,静态顺序表的容量是有限的,如果插入的元素超过了容量,就会导致溢出。
  • ? ? ? ?优点:可以直接通过下标直接访问元素,访问元素速度快,时间复杂度是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;
}

效果

文章来源:https://blog.csdn.net/2303_80025768/article/details/135438524
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。