0
0

【数据结构】线性表之顺序表

一.线性表

线性表：全名线性存储结构

线性存储结构分为顺序存储结构和链式存储结构，前者称为顺序表，后者称为链表

1.顺序存储

顺序表就是把线性表中的所有元素按照某种逻辑顺序，依次存储到指定位置的一块连续的存储空间。

2.链式存储

用于存储逻辑关系为“一对一”的数据

用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），包括数据与和指针域。数据域存储数据，指针域存储后继的信息。

二.顺序表

分类：

  1. 静态顺序表：使用定长数组存储
  2. 动态顺序表：使用动态开辟的数组存储

静态顺序表

问题：

给少了不够用 ，给多了用不完，不能灵活控制

动态顺序表

问题：

  1. 如果空间不够，增容。增容会付出一定性能消耗，其次可能存在一定的空间浪费
  2. 头部或者中部左右的插入和删除效率低

如何解决问题：

  1. 空间上，按需给空间
  2. 不要求物理空间的连续
  • 这里我们使用动态顺序表

三.代码实现

初始化

//初始化
void SeqListInit(SL* psl)
{
    psl->a = NULL;
    psl->capacity = 0;
    psl->sizel = 0;
}

尾插入

//增容
void SeqListCheckCapacity(SL* psl)
{
    if (psl->capacity == psl->sizel)
    {
        int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
        SQDataType* temp = (SQDataType*)realloc(psl->a, newcapacity * sizeof(SQDataType));
        //realloc将第一个参数的值依次存入所申请的空间
        assert(temp);

        psl->a = temp;
        psl->capacity = newcapacity;
    }
}

//尾插
void SeqListPushBack(SL* psl, SQDataType x)
{
    SeqListCheckCapacity(psl);//判断capacity是否足够，若不够进行增容
    psl->a[psl->sizel] = x;
    psl->sizel++;
}

首插入

方法1：

使用常规的for循环进行增容。

void SeqListPushFront(SL* psl, SQDataType x)
{
    SeqListCheckCapacity(psl);//增容
    for (int i = psl->sizel-1; i >= 0; i--)
    {
        psl->a[i + 1] = psl->a[i];
    }
    psl->a[0] = x;
    psl->sizel++;
}

方法2：

使用memmove函数，以字节为单位，拷贝链表，使其每个元素的位置增加一个SQDataType的大小。

//头插——方法2
void SeqListPushFront(SL* psl, SQDataType x)
{
    SeqListCheckCapacity(psl);//增容
    memmove(&(psl->a[1]), psl->a, psl->sizel * sizeof(SQDataType));
    psl->a[0] = x;
    psl->sizel++;
}

头删

这里同样可以使用两种方法，这里我使用了最方便的memmove

//头删
void SeqListPopFront(SL* psl)
{
    assert(psl->sizel > 0);//判断顺序表中是否有数据
    memmove(psl->a, &(psl->a[1]), (psl->sizel - 1) * sizeof(SQDataType));
    psl->a[psl->sizel - 1] = 0;
    psl->sizel--;
}

尾删

//尾删
void SeqListPopBack(SL* psl)
{
    assert(psl->sizel > 0);//判断顺序表中是否有数据
    psl->a[psl->sizel - 1] = NULL;
    psl->sizel--;
}

选择插入

方法1：

使用memmove函数调整表中元素位置后插入

//选择插入
void SeqListInsert(SL* psl, int index, SQDataType x)
{
    assert(pos <= psl->sizel);
    SeqListCheckCapacity(psl);//增容
    memmove(&(psl->a[index + 1]), &(psl->a[index]), (psl->sizel - index) * sizeof(SQDataType));
    psl->a[index] = x;
    psl->sizel++;
}

方法2：

使用循环依次移动元素最终插入

//选择插入
void SeqListInsert(SL* psl, int index, SQDataType x)
{
    assert(index <= psl->sizel);//判断index范围是否合法
    SeqListCheckCapacity(psl);//增容
    int cou = psl->sizel;
    while (cou > index)
    {
        psl->a[cou] = psl->a[cou - 1];
        cou--;
    }
    psl->a[index] = x;
    psl->sizel++;
}

选择删除

使用memmove函数覆盖所要删除的位置

//选择删除
void SeqListErase(SL* psl, int index)
{
    assert(index < psl->sizel);
    memmove(&(psl->a[index]), &(psl->a[index + 1]), (psl->sizel - index - 1) * sizeof(SQDataType));
    psl->a[psl->sizel - 1] = NULL;
    psl->sizel--;
}

查找

在顺序表中查找x，若找到返回下标，找不到则说明顺序表中没有改值

//查找
void SeqListFind(SL* psl, SQDataType x)
{
    int num = 0;
    while (num < psl->sizel)
    {
        if (psl->a[num] == x)
        {
            printf("%d\n", num);
            return;
        }
        num++;
    }
    printf("表中没有%d\b", x);
    return;
}

修改

给出要修改元素的下标和替换的值，进行替换操作。

//修改
void SeqListModity(SL* psl, int pos, SQDataType x)
{
    assert(pos < psl->sizel);//判断给出的下标是否在范围内
    psl->a[pos] = x;
}

四.完整代码

SeqList.h文件

在头文件定义，存放函数、头文件和结构体的声明

#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>

#define N 10;
typedef int SQDataType;

typedef struct SeqList
{
    SQDataType* a;
    int sizel;     //有效数据个数
    int capacity;  //容量
}SL;

//初始化
void SeqListInit(SL* psl);

//尾插入
void SeqListPushBack(SL* psl, SQDataType x);

//头插入
void SeqListPushFront(SL* psl, SQDataType x);

//头删
void SeqListPopFront(SL* psl);

//尾删
void SeqListPopBack(SL* psl);

//选择插入
void SeqListInsert(SL* psl, int index, SQDataType x);

//选择删除
void SeqListErase(SL* psl, int index);

//查找
void SeqListFind(SL* psl, SQDataType x);

//修改
void SeqListModity(SL* psl, int pos, SQDataType x);

//打印
void SeqListPrint(SL* psl);

//销毁空间
void SeqListDestroy(SL* psl);

SeqList.c文件

函数的实现放在此文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

//初始化
void SeqListInit(SL* psl)
{
    psl->a = NULL;
    psl->capacity = 0;
    psl->sizel = 0;
}

//增容
void SeqListCheckCapacity(SL* psl)
{
    if (psl->capacity == psl->sizel)
    {
        int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
        SQDataType* temp = (SQDataType*)realloc(psl->a, newcapacity * sizeof(SQDataType));
        assert(temp);

        psl->a = temp;
        psl->capacity = newcapacity;
    }
}

//尾插
void SeqListPushBack(SL* psl, SQDataType x)
{
    SeqListCheckCapacity(psl);//判断capacity是否足够，若不够进行增容
    psl->a[psl->sizel] = x;
    psl->sizel++;
}

//头插——方法1
//void SeqListPushFront(SL* psl, SQDataType x)
//{
//    SeqListCheckCapacity(psl);//增容
//    for (int i = psl->sizel-1; i >= 0; i--)
//    {
//        psl->a[i + 1] = psl->a[i];
//    }
//    psl->a[0] = x;
//    psl->sizel++;
//}

//头插——方法2
void SeqListPushFront(SL* psl, SQDataType x)
{
    SeqListCheckCapacity(psl);//增容
    memmove(&(psl->a[1]), psl->a, psl->sizel * sizeof(SQDataType));
    psl->a[0] = x;
    psl->sizel++;
}

//头删
void SeqListPopFront(SL* psl)
{
    assert(psl->sizel > 0);//判断顺序表中是否有数据
    memmove(psl->a, &(psl->a[1]), (psl->sizel - 1) * sizeof(SQDataType));
    psl->a[psl->sizel - 1] = 0;
    psl->sizel--;
}

//尾删
void SeqListPopBack(SL* psl)
{
    assert(psl->sizel > 0);//判断顺序表中是否有数据
    psl->a[psl->sizel - 1] = NULL;
    psl->sizel--;
}

//选择插入
//void SeqListInsert(SL* psl, int index, SQDataType x)
//{
//    assert(index <= psl->sizel);
//    SeqListCheckCapacity(psl);//增容
//    memmove(&(psl->a[index + 1]), &(psl->a[index]), (psl->sizel - index) * sizeof(SQDataType));
//    psl->a[index] = x;
//    psl->sizel++;
//}

//选择插入
void SeqListInsert(SL* psl, int index, SQDataType x)
{
    assert(index <= psl->sizel);
    SeqListCheckCapacity(psl);//增容
    int cou = psl->sizel;
    while (cou > index)
    {
        psl->a[cou] = psl->a[cou - 1];
        cou--;
    }
    psl->a[index] = x;
    psl->sizel++;
}

//选择删除
void SeqListErase(SL* psl, int index)
{
    assert(index < psl->sizel);
    memmove(&(psl->a[index]), &(psl->a[index + 1]), (psl->sizel - index - 1) * sizeof(SQDataType));
    psl->a[psl->sizel - 1] = NULL;
    psl->sizel--;
}

//查找
void SeqListFind(SL* psl, SQDataType x)
{
    int num = 0;
    while (num < psl->sizel)
    {
        if (psl->a[num] == x)
        {
            printf("%d\n", num);
            return;
        }
        num++;
    }
    printf("表中没有%d\b", x);
    return;
}

//修改
void SeqListModity(SL* psl, int pos, SQDataType x)
{
    assert(pos < psl->sizel);
    psl->a[pos] = x;
}

//打印链表
void SeqListPrint(SL* psl)
{
    for (int i = 0; i < psl->sizel; i++)
    {
        printf("%d ", psl->a[i]);
    }
    printf("\n");
}

//销毁空间
void SeqListDestroy(SL* psl)
{
    free(psl->a);
    psl->a = NULL;
    psl->capacity = 0;
    psl->sizel = 0;
}

text.c文件

存放主函数，其它函数在此文件夹调用

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include "SeqList.h"

//菜单
void menu()
{
    printf("**********************\n");
    printf("1.尾插数据，2.头插数据\n");
    printf("3.尾删数据，4.头删数据\n");
    printf("5.选择插入，6.选择删除\n");
    printf("7.查找元素，8.修改链表\n");
    printf("9.打印数据，-1，退出\n");
    printf("**********************\n");
    printf("请输入你的选择:");
}

int main()
{
    SL slist;
    int choose = 0;
    SeqListInit(&slist);//初始化
    while (choose != -1)
    {
        int a = 0, b = 0;
        menu();
        scanf(" %d", &choose);
        switch (choose)
        {
        case 1://尾插
            printf("请输入你要插入的数据，以-1结束\n");
            while (a != -1)
            {
                scanf("%d", &a);
                if(a!=-1)
                    SeqListPushBack(&slist, a);
            }
            break;
        case 2://头插
            printf("请输入你要插入的数据，以-1结束\n");
            while (a != -1) 
            {
                scanf("%d", &a);
                if (a != -1)
                    SeqListPushFront(&slist, a);
            } 
            break;
        case 3://尾删
            SeqListPopBack(&slist);
            printf("尾删，删除成功！\n");
            break;
        case 4://头删
            SeqListPopFront(&slist);
            printf("头删，删除成功!\n");
            break;
        case 5://选择插入
            printf("请输入需要插入的下标和元素:");
            scanf("%d%d", &a, &b);
            SeqListInsert(&slist, a, b);
            break;
        case 6://选择删除
            printf("请输入需要删除的元素的下标:");
            scanf("%d", &a);
            SeqListErase(&slist, a);
            break;
        case 7://查找元素
            printf("请输入需要查找的元素的下标:");
            scanf("%d", &a);
            SeqListFind(&slist, a);
            break;
        case 8://修改链表
            printf("请输入需要修改的下标和元素:");
            scanf("%d%d", &a, &b);
            SeqListModity(&slist, a, b);
            break;
        case 9://打印
            SeqListPrint(&slist);
            break;
        case -1://退出
            SeqListDestroy(&slist);//销毁空间
            break;
        default:
            printf("输入错误，请重新输入！\n");
            break;
        }
        system("pause");
        system("cls");
    }

    return 0;
}
标签： 数据结构 链表
本文转载自: https://blog.csdn.net/m0_52094687/article/details/126881530
版权归原作者 榶曲 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【数据结构】线性表之顺序表”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

【Windows】如何关闭Windows11安全中心中的“病毒和威胁保护”？

CVE-2022-26201（二次注入+文件上传）

每日分享之-单元测试

【新鲜出炉】QNAP威联通container station docker拉取问题

.gitignore 不生效解决方案

Unity组件大全之 UI 组件 |（5）Input Field 组件

【kafka】生产者

文章导航