AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】——拿捏顺序表 ( 详细 )（下）

2022-05-11 141
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】——拿捏顺序表 ( 详细 )（下）

✨三、线性表的顺序表示和实现

数据元素相互之间的存储关系

【数据结构】——拿捏顺序表 ( 详细 )_顺序表_10

顺序表的类型定义：

#define  MAXSIZE 100     //最大长度
typedef  struct 
{
      ElemType  *elem;      //指向数据元素的基地址
      int  length;                 //线性表的当前长度                        
 }SqList；

1.初始化顺序表

首先，我们要创建一个顺序表类型，该顺序表类型包括了顺序表的起始位置、记录顺序表内已有元素个数的计数器(size)，以及记录当前顺序表的容量的变量(capacity)。

typedef int SLDataType;

typedef struct SeqList
{
    SLDataType* a;//声明了一个指向顺序表的指针，姑且称它为“顺序表指针”
    int size;//记录当前顺序表内元素个数
    int capacity;//记录当前顺序表的最大容量
}SeqList;

然后，我们需要一个初始化函数，对顺序表进行初始化。

//初始化顺序表
void SeqListInit(SeqList* ps)
{
    assert(ps);
    ps->a = NULL;//刚开始时顺序表为空，顺序表指针为NULL
    ps->size = 0;//起始时元素个数为0
    ps->capacity = 0;//容量为0
}

2.销毁顺序表

因为顺序表所用的内存空间是动态开辟在堆区的，所以我们在使用完后需要及时对其进行释放，避免造成内存泄漏。

//销毁顺序表
void SeqListDestory(SeqList* ps)
{
    assert(ps);
    free(ps->a);//释放顺序表指针指向的空间
    ps->a = NULL;//及时置空
    ps->size = 0;//元素个数置0
    ps->capacity = 0;//容量置0
}

若需要对数据进行保存，可以使用文件操作函数将数据保存到一个文件中，下次使用顺序表的时候先读取文件数据即可。

3.打印顺序表

打印就比较简单了，依次循环打印size个元素即可。

//打印顺序表
void SeqListPrint(SeqList* ps)
{
    assert(ps);
    int i = 0;
    //循环打印顺序表指针指向的数据
    for (i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

4.扩容实现

仔细想想，我们每次需要增加数据的时候，首先都应该先检查顺序表内元素个数是否已达顺序表容量上限。若已达上限，那么我们就需要先对顺序表进行扩容，然后才能增加数据。

//检查顺序表容量是否已满，若已满，则增容
void SeqCheckCapacity(SeqList* ps)
{
    if (ps->size == ps->capacity)//满了，需要增容
    {
        //判断顺序表容量是否为0，若为0，则先开辟用于存放4个元素的空间大小，若不为0，则扩容为原来容量的两倍
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDataType* newA = realloc(ps->a, newcapacity*sizeof(SLDataType));
        if (newA == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        ps->a = newA;//开辟成功，将顺序表指针更新
        ps->capacity = newcapacity;//容量更新
    }
}

注意：若传入realloc的指针为空指针(NULL)，则realloc函数的作用相当于malloc函数。

将顺序表原有的数据从后往前依次向后挪动一位，最后再将数据插入表头。

5.头插

要想在顺序表的表头插入数据，那么就需要先将顺序表原有的数据从后往前依次向后挪动一位，最后再将数据插入表头。

//头插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
    assert(ps);
    SeqCheckCapacity(ps);//检查容量
    int i = 0;
    for (i = ps->size; i > 0; i--)//将数据从后往前依次向后挪
    {
        ps->a[i] = ps->a[i - 1];
    }
    ps->a[0] = x;
    ps->size++;//顺序表元素个数加一
}

注意：挪动数据的时候应从后向前依次挪动，若从前向后挪动，会导致后一个数据被覆盖。

6.尾插

尾插相对于头插就比较简单了，直接在表尾插入数据即可。

//尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
    assert(ps);
    SeqCheckCapacity(ps);//检查容量
    ps->a[ps->size] = x;
    ps->size++;//顺序表元素个数加一
}

7.指定下标位置插入

要做到在指定下标位置插入数据，首先我们需要得到一个下标位置，然后从该下标位置开始（包括该位置），其后的数据从后往前依次向后挪动一位，最后将数据插入到该下标位置。

//指定下标位置插入
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);//检查输入下标的合法性
    SeqCheckCapacity(ps);//检查容量
    int i = 0;
    for (i = ps->size; i > pos; i--)//从pos下标位置开始，其后的数据从后往前依次向后挪
    {
        ps->a[i] = ps->a[i - 1];
    }
    ps->a[pos] = x;
    ps->size++;//顺序表元素个数加一
}

我们可以发现，头插和尾插实际上就是在下标为0的位置和下标为ps->size的位置插入数据，也就意味着我们可以统一使用该函数来实现头插和尾插。

//头插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
    SeqListInsert(ps, 0, x);//在下标为0的位置插入数据
}
//尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
    SeqListInsert(ps, ps->size, x);//在下标为ps->size的位置插入数据
}

删除数据，其实可以理解为：从某个位置开始，数据依次向前覆盖。这样一来，该位置的数据就相当于删除了。

8.头删

要删除表头的数据，我们可以从下标为1的位置开始，依次将数据向前覆盖即可。

//头删
void SeqListPopFront(SeqList* ps)
{
    assert(ps);
    assert(ps->size > 0);//保证顺序表不为空
    int i = 0;
    for (i = 0; i < ps->size - 1; i++)//将数据从前往后依次向前覆盖
    {
        ps->a[i] = ps->a[i + 1];
    }
    ps->size--;//顺序表元素个数减一
}

注意：数据覆盖的时候应从前向后依次覆盖，若从后向前覆盖，会导致前一个数据被覆盖。

9. 尾删

尾删就更简单了，直接将顺序表的元素个数减一即可。

//尾删
void SeqListPopBack(SeqList* ps)
{
    assert(ps);
    assert(ps->size > 0);//保证顺序表不为空
    ps->size--;//顺序表元素个数减一
}

10.指定下标位置删除

要删除指定下标位置的数据，我们只需要从下标位置开始，其后的数据从前向后依次覆盖即可

//指定下标位置删除
void SeqListErase(SeqList* ps, int pos)
{
    assert(ps);
    assert(ps->size > 0);//保证顺序表不为空
    assert(pos >= 0 && pos < ps->size);
    int i = 0;
    for (i = pos; i < ps->size - 1; i++)//从pos下标位置开始，其后的数据从前往后依次向前覆盖
    {
        ps->a[i] = ps->a[i + 1];
    }
    ps->size--;//顺序表元素个数减一
}

同样的道理，头删和尾删实际上也就是删除下标为0的位置和下标为ps->size - 1的位置的数据，也就意味着我们可以统一使用该函数来实现头删和尾删。

//头删
void SeqListPopFront(SeqList* ps)
{
    SeqListErase(ps, 0);//删除下标为0的位置的数据
}
//尾删
void SeqListPopBack(SeqList* ps)
{
    SeqListErase(ps, ps->size - 1);//删除下标为ps->size - 1的位置的数据
}

11.查找数据

查找数据也相对简单，直接遍历一次顺序表即可，若找到了目标数据，则停止遍历，并返回该数据的下标，否则返回-1

//查找元素，若有，返回下标，否则返回-1
int SeqListFind(SeqList* ps, SLDataType x)
{
    assert(ps);
    int i = 0;
    for (i = 0; i < ps->size; i++)//遍历顺序表进行查找
    {
        if (ps->a[i] == x)
            return i;//找到该数据，返回下标
    }
    return -1;//未找到，返回-1
}

12.修改数据

修改数据，就直接对该位置的数据进行再次赋值即可。

//修改指定下标位置元素
void SeqListModify(SeqList* ps, int pos, SLDataType x)
{
    assert(ps);
    assert(pos >= 0 && pos < ps->size);//检查输入下标的合法性
    ps->a[pos] = x;//修改数据
}

⌚四、顺序表实现源码

Sqlist.h 文件:

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include
#include 
#include 
// #define MAX_SIZE 100
typedef int SQDateType;

typedef struct SeqList
{
    SQDateType* a;
    int size; //有效数据个数
    int cacpcity;//容量
}SL;

//增删查改
void SeqListInit(SL* ps);
void SeqListDestory(SL* ps);
int SeqListFind(SL* ps, SQDateType x); 
int SeqListModity(SL* ps, int pos, SQDateType x);

//头插 尾插  头删  尾删  任意位置插入、删除  
void SeqListPushBack(SL* ps, SQDateType x);
void SeqListPushFront(SL* ps, SQDateType x);

void SeqListPopBack(SL* ps);
void SeqListPopFront(SL* ps);

void SeqListInsert(SL* ps, int pos, SQDateType x);
void SeqListErase(SL* ps, int pos);

//打印
void SeqListPrintf(SL* ps);
//扩容
void SeqLIstCheckCacpcity(SL* ps);

Sqlist.cpp文件;

#include "seqList.h"

void SeqLIstCheckCacpcity(SL* ps)
{
    //判断表满就扩容
    if (ps->size == ps->cacpcity)
    {
        int newcacpcity = ps->cacpcity == 0 ? 4 : ps->cacpcity * 2;

        SQDateType* tmp = (SQDateType*)realloc(ps->a, newcacpcity * 2 * sizeof(SQDateType));

        if (tmp == NULL)
        {
            printf("realloc is fail\n");
            exit(-1);
        }

        else
        {
            ps->a = tmp;
            ps->cacpcity = newcacpcity;
        }
    }
}

//初始化
void SeqListInit(SL* ps)
{
    ps->a = NULL;
    ps->size = 0;
    ps->cacpcity = 0;
}

//尾插
void SeqListPushBack(SL* ps, SQDateType x)
{
    SeqLIstCheckCacpcity(ps);

    ps->a[ps->size] = x;
    ps->size++;

}

void SeqListPrintf(SL* ps)
{
    for (int i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->a[i]);
    }
    printf("\n");

}

//头插
void SeqListPushFront(SL* ps, SQDateType x)
{

    SeqLIstCheckCacpcity(ps);

    int end = ps->size - 1;
    int start = 0;
    while (end>=start)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }

    ps->a[0] = x; 
    ps->size++;

}

//尾删
void SeqListPopBack(SL* ps)
{
    assert(ps->size > 0);//size不大于0就断言了

    // ps->a[ps->size - 1] = 0; 可有可无
    ps->size--;

}    

//头删
void SeqListPopFront(SL* ps)
{
    assert(ps->size > 0);

    int start = 1;
    while (start < ps->size)
    {
        ps->a[start-1] = ps->a[start];
        start++;
    }
    ps->size--;

}

//
void SeqListInsert(SL* ps, int pos, SQDateType x)
{
    assert(pos< ps->size );
    SeqLIstCheckCacpcity(ps);

    int end = ps->a[ps->size - 1];
    while (end <= pos)
    {
        ps->a[end + 1] = ps->a[end];
        end--;

    }

    ps->a[pos] = x;
    ps->size++;
}



void SeqListErase(SL* ps, int pos)
{
    assert(pos < ps->size);
    int start = pos+1;
    while (start <ps->size )
    {
        ps->a[start-1] = ps->a[start];
        start++;
    }

    ps->size--;
}



int SeqListFind(SL* ps, SQDateType x)
{
    for (int i = 0; i < ps->size; i++)
    {
        if (ps->a[i] == x)
        {
            return i;
        }
    }

    return -1;

}

int SeqListModity(SL* ps, int pos, SQDateType x)
{
    assert(pos < ps->size);

    ps->a[pos] = x;

    return 0;
}

Text.cpp文件（菜单+测试）

 #define _CRT_SECURE_NO_WARNINGS 1
#include "seqList.h"

void TestSeqList1()
{
    SL sl;
    SeqListInit(&sl);
    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);
    SeqListPushBack(&sl, 6);

    SeqListPrintf(&sl);
    
    SeqListPushFront(&sl,1);
    SeqListPushFront(&sl, 1);
    SeqListPushFront(&sl, 1);
    SeqListPushFront(&sl, 1);
    SeqListPushFront(&sl, 1);
    SeqListPushFront(&sl, 1);


    SeqListPrintf(&sl);
    
    SeqListPopBack(&sl);
    SeqListPopBack(&sl);

    SeqListPrintf(&sl);

    SeqListPopFront(&sl);
    SeqListPopFront(&sl);

    SeqListPrintf(&sl);

    SeqListInsert(&sl, 1, 20);
    SeqListInsert(&sl, 2, 30);

    SeqListPrintf(&sl);

    SeqListErase(&sl, 2);

    SeqListPrintf(&sl);

    SeqListModity(&sl, 2, 55);

    SeqListPrintf(&sl);

    int Findpos=SeqListFind(&sl , 55);
    
    printf("下标为%d\n", Findpos);

}


void meau()
{
    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("\n**请输入你的操作选项:>**\n");

}



int main()
{
    int option = 0;
    int x = 0;
    int y = 0;
    SL s;
    SeqListInit(&s);

    while (option !=-1)
    {
        meau();
        scanf("%d",&option);

        switch (option)
        {
        case 1:
            printf("请输入你要头插的数据，用-1结束\n");
            do
            {
                scanf("%d", &x);
                if (x != -1)
                {
                    SeqListPushFront(&s, x);
                }

            } while (x!=-1);
            break;

        case 2:
            printf("请输入你要尾插的数据，以-1结束\n");
            do
            {
                scanf("%d", &x);
                if (x != -1)
                {
                    SeqListPushBack(&s, x);
                }

            } while (x != -1);
            break;

        case 3:
            printf("头删数据，输入1确定，输入-1退出\n");
            do
            {
                scanf("%d", &x);
                if (x == 1)
                {
                    SeqListPopFront(&s);
                }

            } while (x == 1);
            break;

        case 4:
            printf("尾删数据，输入1确定，输入-1退出\n");
            do
            {
                scanf("%d", &x);
                if (x == 1)
                {
                    SeqListPopBack(&s);
                }

            } while (x == 1);
            break;

        case 5:
            SeqListPrintf(&s);
            break;

        case 6:
            printf("请输入你要查找的数据（返回输出下标，没找到输出-1），输入-1结束\n");
            do
            {
                scanf("%d", &x);
                int a = x;
                if (x != -1)
                {
                    int Findpos = SeqListFind(&s, a);
                    
                    if (Findpos == -1)
                    {
                        printf("没有找到\n");
                    }
                    else
                    {
                        printf("下标为%d", Findpos);
                    }

                }
            } while (x != -1);
            break;

        case 7:
            printf("请输入你 插入数据位置的下标 和 插入数据，输入-1结束\n");
            do
            {
                scanf("%d", &x);
                if (x != -1)
                {
                    scanf("%d", &y);
                    SeqListInsert(&s,x,y);
                }

            } while (x != -1);
            break;

        case 8:
            printf("请输入你要删除位置的下标，输入-1结束\n");
            do
            {
                scanf("%d", &x);
                if (x != -1)
                {
                    SeqListPushBack(&s, x);
                }

            } while (x != -1);
            break;

        case 9:
            printf("请输入你 修改数据位置的下标 和 修改的数据，输入-1结束\n");
            do
            {
                scanf("%d", &x);
                if (x != -1)
                {
                    scanf("%d", &y);
                    SeqListModity(&s, x, y);
                }

            } while (x != -1);
            break;


        case -1:
            printf("退出\n");
            return 0;
            break;

        default:
            printf("输入错误，请重新输入\n");
            break;
        }

    }

    //测试用例
    //TestSeqList1();


    return 0;
}

【数据结构】——拿捏顺序表 ( 详细 )_C语言_11

文章标签：
存储
关键词：
数据结构顺序表
数据结构拿捏顺序表
Perceus
目录
相关文章
禁默
|
3月前
|
存储 编译器 C语言
数据结构-顺序表详解（看这篇就足够了，哈哈哈）
数据结构-顺序表详解（看这篇就足够了，哈哈哈）
禁默
74 2
RossyYan
|
5天前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算（头歌实践教学平台习题）【合集】
本文档介绍了线性表的基本运算任务，涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法，并提供了测试说明和通关代码。 主要内容包括： - **任务描述**：实现顺序表的基本运算。 - **相关知识**：介绍线性表的基本概念及操作，如初始化、销毁、判定是否为空表等。 - **具体操作**：详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法，并附有代码示例。 - **测试说明**：提供测试输入和预期输出，确保代码正确性。 - **通关代码**：给出完整的C++代码实现，帮助完成任务。 文档
RossyYan
20 5
三三是该溜子
|
19天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
29 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
肾透侧视攻城狮
|
2月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找等具体详解步骤以及举例说明
肾透侧视攻城狮
36 3
ephemerals__
|
2月前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
95 3
肾透侧视攻城狮
|
2月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找习题精讲等具体详解步骤以及举例说明
肾透侧视攻城狮
31 1
小强在此
|
3月前
|
存储 Java
数据结构第二篇【关于java线性表（顺序表）的基本操作】
数据结构第二篇【关于java线性表（顺序表）的基本操作】
小强在此
52 6
星霜旅人
|
3月前
|
存储
数据结构（顺序表）
数据结构（顺序表）
星霜旅人
32 0
白子寰
|
3月前
|
存储 算法
【数据结构】新篇章 -- 顺序表
【数据结构】新篇章 -- 顺序表
白子寰
26 0
阿客不是客
|
3月前
|
存储 测试技术
探索数据结构：顺序表的实现与应用
探索数据结构：顺序表的实现与应用
阿客不是客
52 0