【数据结构】 顺序表的基本操作 （C语言版）

一、顺序表

1、顺序表的定义：

线性表的顺序存储结构，即将表中的结点按逻辑顺序依次存放在一组地址连续的存储单元里。这种存储方式使得在逻辑结构上相邻的数据元素在物理存储上也是相邻的，可以通过数据元素的物理存储位置来反映其逻辑关系。

数据结构中的顺序表是一种线性表，它在计算机内存中以数组的形式保存。顺序表采用顺序存储结构，即将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。这种存储方式使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

2、顺序表的优缺点：

顺序表的优点是便于随机访问查找，时间复杂度为O(1)。缺点是不便于插入和删除操作，尤其是中间或头部的插入和删除操作，时间复杂度为O(n)。因此，顺序表适用于需要大量访问元素，尾部插入和删除较多的场景。

顺序表的优点：
  1. 存储密度大：数据元素在内存中紧密排列，空间利用率高。
  2. 存取速度快：可以通过下标直接访问任意位置的元素，时间复杂度为O(1)。
  3. 空间连续：一次性申请一定大小的存储空间，便于管理和控制。
顺序表的缺点：
  1. 插入和删除操作效率低下：需要移动大量数据元素，特别是当插入或删除的位置位于中间或头部时，时间复杂度为O(N)。
  2. 长度固定：无法自由扩展或收缩，当元素个数超过预先分配的空间时会导致溢出，而元素个数远少于预先分配的空间时则会造成空间浪费。
  3. 动态调整困难：顺序表的空间必须预先分配，无法根据实际需求动态调整。

二、顺序表的基本操作算法（C语言）

1、宏定义
typedef int Status;
typedef char ElemType;
2、创建结构体
//定义类型
typedef struct {
    char *elem;
    int length;
}SqList;
3、顺序表初始化
//初始化
Status InitList_sq(SqList &L){//引用型参数
//	L.elem=new char[10];
    L.elem=new ElemType[10];
    if(!L.elem){
        //exit (-1);
        exit (OVERFLOW);
    }
    L.length=0;
    return OK;
}
4、顺序表插入

在顺序表L的第 i 个元素之前插入新的元素e

1.找到第i-1个位置   

2.将元素e插入

时间复杂度T(n)=O(n)

顺序表的空间复杂度S(n)=O(1)    没有占用辅助空间

//插入
Status InsertList_sq(SqList &L,int i,ElemType e){
    if(i<1 || i>L.length+1){
        return ERROR;
    }
    if(L.length==MAXSIZE){
        return ERROR;
    }
    for (int j=L.length-1;j>=i-1;j--){
        L.elem[j+1]=L.elem[j];
    }
    L.elem[i-1] = e;
    L.length++;
    return OK;
}
4、顺序表取值 
//取值
Status GetElem(SqList L, int i, ElemType &e){
    if(i<1 || i>L.length) {
        return ERROR;
    }
    e = L.elem[i-1];
    return OK;
}
5、求顺序表的长度
//求长度
int GetLength(SqList L){
    return L.length;
}
6、顺序表查找

//查找
Status LocateElem(SqList L,ElemType e)
{
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i] == e)
            return i + 1;
    }
    return 0;
}
7、顺序表删除

插入i-1个位置，删除第i个位置的元素

//删除
Status ListDelete(SqList &L,int i,ElemType &e)
{
    if ((i<1) || (i>L.length+1)) return ERROR;
//    if (L.length==MAXSIZE) return 0;       //不用判空
    e = L.elem[i - 1];
    for (int j=i;j<=L.length-1;j++)             //for (j=i-1;j<=L.length-1;j++)
        L.elem[j-1]=L.elem[j];             // L.elem[j]=L.elem[j+1];
    --L.length;
    return  OK;
}

四、顺序表的全部代码（C语言）

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

#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXSIZE 10


typedef int Status;
typedef char ElemType;

//定义类型
typedef struct {
    char *elem;
    int length;
} SqList;

//顺序表初始化
//int InitList_sq(SqList &L){   //引用型参数
Status InitList_sq(SqList &L) {
//	L.elem=new char[10];
    L.elem = new ElemType[10];
    if (!L.elem) {
        //exit (-1);
        exit(OVERFLOW);
    }
    L.length = 0;
//	return 1;
    return OK;
}

//功能菜单
int choice() {
    printf("==================================\n");
    printf("         顺序表操作功能菜单        \n");
    printf("          1、插入元素            \n");
    printf("          2、查询表长            \n");
    printf("          3、按位查找            \n");
    printf("          4、按值查找            \n");
    printf("          6、批量插入            \n");
    printf("          7、退出程序            \n");
    printf("==================================\n");
    return 0;
}

//顺序表插入
Status InsertList_sq(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) {
        return ERROR;
    }
    if (L.length == MAXSIZE) {
        return ERROR;
    }
    for (int j = L.length - 1; j >= i - 1; j--) {
        L.elem[j + 1] = L.elem[j];
    }
    L.elem[i - 1] = e;
    L.length++;
    return OK;
}

//顺序表取值
Status GetElem(SqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length) {
        return ERROR;
    }
    e = L.elem[i - 1];
    return OK;
}

//求顺序表长度
int GetLength(SqList L) {
    return L.length;
}

//顺序表查找
Status LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        //printf("%c",L.elem[i]);
        if (L.elem[i] == e)
            return i + 1;
    }
    return 0;
}

//顺序表删除
Status ListDelete(SqList &L, int i, ElemType &e) {
    if ((i < 1) || (i > L.length + 1)) return ERROR;
    e = L.elem[i - 1];
    for (int j = i; j <= L.length - 1; j++)         //j=i-1
        L.elem[j - 1] = L.elem[j];             // L.elem[j]=L.elem[j+1];
    L.length--;
    return OK;
}


int main() {
    //printf("Hell Word");
    //struct List list;
    SqList sqList;

    printf("顺序表正在初始化....\n");
    Status returnStatus = InitList_sq(sqList);
    if (returnStatus == OK) {
        printf("顺序表初始化成功！\n");
    } else {
        printf("顺序表初始化失败！\n");
    }

    choice();

    while (1) {

        int flag;
        printf("请输入所需的功能编号：\n");
        scanf("%d", &flag);

        switch (flag) {
            case 1: {//插入
                // printf("length = %d \n", sqList.length);
                // int listLength = GetLength(sqList);
                // printf("%d ", listLength);
                int insertLocation;
                ElemType insertElem;
                printf("请输入插入元素位置及插入元素(请在英文状态下输入例如:1,a): \n");
                scanf("%d,%c", &insertLocation, &insertElem);
                Status insertStatus = InsertList_sq(sqList, insertLocation, insertElem);
                if (insertStatus == OK) {
                    printf("向顺序表中第%d个位置,插入元素%c成功！\n", insertLocation, insertElem);
                } else {
                    printf("向顺序表中插入元素失败！\n");
                }
                choice();
            }
                break;
            case 2: {//求顺序表的长度
                printf("顺序表的长度为：%d  。\n", GetLength(sqList));
                choice();
            }
                break;
            case 3: {//取值
                Status no;
                printf("请输入需要查询的元素的位置：\n");
                scanf("%d", &no);
                ElemType element;
                Status GetElemStatus = GetElem(sqList, no, element);
                //printf("element = %c ", element);
                printf("在顺序表中第%d个元素为：%c 。 \n", no, element);
                if (GetElemStatus = OK) {
                    printf("在顺序表中第%d个元素为：%c 。 \n", no, element);
                } else {
                    printf("查找顺序表中第%d个元素失败。 \n", no);
                }
                choice();
            }
                break;
            case 4: {//查找
                ElemType findElem;
                printf("请输入想要查找元素：\n");
                getchar();    //用于接收回车
                scanf("%c", &findElem);
                int locate = LocateElem(sqList, findElem);
                if (locate != 0) {
                    printf("所需查找的元素%c存在于顺序表中，它的在第%d位置。  \n", findElem, locate);
                } else {
                    printf("所需查找的元素%c不存在于顺序表中！  \n", findElem);
                }
                //printf("locate = %d ", locate);
                choice();
            }
                break;
            case 5: {//删除
                //ListDelete_DuL(list,1);
                Status delindex;
                ElemType delElem;
                printf("请输入想要删除元素的位置：\n");
                scanf("%d", &delindex);
                Status delreturn = ListDelete(sqList, delindex, delElem);
                if (delreturn == OK) {
                    printf("在顺序表中删除第%d个元素为：%c 。 \n", delindex, delElem);
                } else {
                    printf("在顺序表中删除第%d个元素失败! \n", delindex);
                }
                printf("顺序表的长度为：%d  \n", GetLength(sqList));
                //printf("delindex = %d ", delindex);
                choice();
            }
                break;
            case 6: {//批量插入
                int on;
                printf("请输入想要插入的元素个数：\n");
                scanf("%d", &on);
                ElemType array[on];
                for (int i = 1; i <= on; i++) {
                    getchar();
                    printf("向顺序表第%d个位置插入元素为:", (i));
                    scanf("%c", &array[i]);
                }

                for (int i = 1; i <= on; i++) {
                    Status insertStatus = InsertList_sq(sqList, i, array[i]);
                    if (insertStatus == OK) {
                        printf("向顺序表中第%d个位置,插入元素%c成功！\n", i, array[i]);
                    } else {
                        printf("向顺序表中第%d个位置插入元素失败！\n", i);
                    }
                }
                choice();
            }
                break;
            case 7: {//退出程序
                return 0;
            }
                break;
            default: {
                printf("输入错误，无此功能，请检查输入:\n\n");
            }
        }
    }
}

五、结果

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/345468.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

基于Springboot的大学生心理健康管理系统（有报告）。Javaee项目，springboot项目。

基于Springboot的大学生心理健康管理系统（有报告）。Javaee项目，springboot项目。

演示视频&#xff1a; 基于Springboot的大学生心理健康管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体…
阅读更多...
【吃灰开发板复活】DIY全志V3s随身终端屏幕适配，LVGL以及各种外设驱动移植教程

【吃灰开发板复活】DIY全志V3s随身终端屏幕适配，LVGL以及各种外设驱动移植教程

在上周的文章中介绍了一款因作者想要学习Linux而动手DIY的终端设备V3S-PI&#xff0c; 《梦回2004&#xff01;我用全志V3s做了个成本100元&#xff0c;功能媲美MP4的随身终端》&#xff1a;梦回2004&#xff01;我用全志V3s做了个成本100元&#xff0c;功能媲美MP4的随身终端…
阅读更多...
微信小程序如何获取当前日期时间

微信小程序如何获取当前日期时间

Hello大家好&#xff01;我是咕噜铁蛋&#xff0c;获取当前日期时间是小程序中经常会用到的一个功能。因此&#xff0c;在本文中&#xff0c;我通过科技手段给大家收集整理了下&#xff0c;今天我将向大家介绍如何在微信小程序中获取当前日期时间的方法&#xff0c;并分享一些实…
阅读更多...
HubSpot在线客户互动：建立强大数字连接的关键一步

HubSpot在线客户互动：建立强大数字连接的关键一步

HubSpot在线客户互动为企业带来了多方面的具体业务优势&#xff0c;其中一些关键点包括&#xff1a; 提高销售转化率&#xff1a; 通过实时在线聊天、个性化推荐等互动方式&#xff0c;HubSpot使企业能够更主动地接触潜在客户&#xff0c;解答其疑问&#xff0c;提供定制化的…
阅读更多...
RabbitMQ——高级篇

RabbitMQ——高级篇

目录 一、MQ的常见问题 二、消息可靠性问题 生产者消息确认 消息持久化 消费者消息确认 失败重试机制 三、死信交换机 简介死信交换机 TTL超时机制 延迟队列 四、惰性队列 消息堆积问题 惰性队列 一、MQ的常见问题 消息可靠性问题&#xff1a;如何确保发送的…
阅读更多...
解决 Git：ssh: connect to host github.com port 22: Connection timed out 问题的三种方案

解决 Git：ssh: connect to host github.com port 22: Connection timed out 问题的三种方案

1、问题描述&#xff1a; 其一、整体提示为&#xff1a; ssh: connect to host github.com port 22: Connection timed out fatal: Could not read from remote repository. 中文为&#xff1a; ssh&#xff1a;连接到主机 github.com 端口 22&#xff1a;连接超时 fatal&a…
阅读更多...
【设计模式】腾讯面经:原型模式怎么理解？

【设计模式】腾讯面经:原型模式怎么理解？

什么是原型模式&#xff1f; 设计模式是编程世界的基石&#xff0c;其中原型模式无疑是一种常用而又高效的创建对象的手段。那么&#xff0c;什么是原型模式呢&#xff1f;又该如何去实现它&#xff1f; 在软件工程中&#xff0c;原型模式是一种创建型设计模式。我们可以这样…
阅读更多...
「JavaSE」抽象类接口2

「JavaSE」抽象类接口2

&#x1f387;个人主页&#xff1a;Ice_Sugar_7 &#x1f387;所属专栏&#xff1a;快来卷Java啦 &#x1f387;欢迎点赞收藏加关注哦&#xff01; 抽象类&接口2 &#x1f349;接口间的继承&#x1f349;接口的应用&#x1f349;总结 &#x1f349;接口间的继承 和类的继承…
阅读更多...
Pyside6中QTableWidget使用

Pyside6中QTableWidget使用

目录 一&#xff1a;介绍&#xff1a; 二&#xff1a;演示 一&#xff1a;介绍&#xff1a; 在 PySide6 中&#xff0c;QTableWidget 是一个用于展示和编辑表格数据的控件。它提供了在窗口中创建和显示表格的功能&#xff0c;并允许用户通过单元格来编辑数据。 要使用 QTabl…
阅读更多...
黑马Java——面向对象进阶（static继承）

黑马Java——面向对象进阶（static继承）

1.static静态变量 静态变量是随着类的加载而加载的&#xff0c;优先与对象出现的
阅读更多...
Kotlin 开发环境配置指南

Kotlin 开发环境配置指南

一、下载与安装 Kotlin 编译器 步骤 1&#xff1a;获取最新版 Kotlin 编译器 要配置 Kotlin 开发环境&#xff0c;首先需要从 JetBrains 官方 GitHub 仓库下载最新的 Kotlin 编译器。访问以下链接以获取最新版本的编译器&#xff1a; [https://github.com/JetBrains/kotlin/…
阅读更多...
Severstal公司的汉语名字是什么，是一家什么样的公司？

Severstal公司的汉语名字是什么，是一家什么样的公司？

问题描述&#xff1a;Severstal公司的汉语名字是什么&#xff0c;是一家什么样的公司&#xff1f; 问题解答&#xff1a; Severstal 公司的中文名字通常被翻译为 "谢韦尔钢铁公司"。这家公司是俄罗斯的一家大型钢铁和矿业企业&#xff0c;总部位于莫斯科。Seversta…
阅读更多...
libtorch学习第六

libtorch学习第六

构建卷积网络 #include<torch/torch.h> #include<torch/script.h> #include<iostream>using std::cout; using std::endl;class LinearBnReluImpl : public torch::nn::Module { private:torch::nn::Linear ln{ nullptr };torch::nn::BatchNorm1d bn{ nullp…
阅读更多...
[Python] glob内置模块介绍和使用场景（案例）

[Python] glob内置模块介绍和使用场景（案例）

Unix glob是一种用于匹配文件路径的模式&#xff0c;它可以帮助我们快速地找到符合特定规则的文件。在本文中&#xff0c;我们将介绍glob的基本概念、使用方法以及一些实际应用案例。 glob介绍 Glob(Global Match)是Unix和类Unix系统中的一种文件名扩展功能&#xff0c;它可以…
阅读更多...
分布式锁的实现方式

分布式锁的实现方式

分布式锁是指分布式环境下&#xff0c;系统部署在多个机器中&#xff0c;实现多进程分布式互斥的一种锁。实现分布式锁有三种主流方式&#xff0c;接下来一一盘点。 盘点之前要说说选择时的优缺点 数据库实现的锁表完全不推荐。 Redis分布式锁性能优于ZooKeeper&#xff0c;因…
阅读更多...
01、领域驱动设计：微服务设计为什么要选择DDD总结

01、领域驱动设计：微服务设计为什么要选择DDD总结

目录 1、前言 2、软件架构模式的演进 3、微服务设计和拆分的困境 4、为什么 DDD适合微服务 5、DDD与微服务的关系 6、总结 1、前言 我们知道&#xff0c;微服务设计过程中往往会面临边界如何划定的问题&#xff0c;不同的人会根据自己对微服务的理 解而拆分出不同的微服…
阅读更多...
通过 GScan 工具自动排查后门

通过 GScan 工具自动排查后门

一、简介 GScan 是一款为安全应急响应提供便利的工具&#xff0c;自动化监测系统中常见位置。 工具运行环境&#xff1a;CentOS (6、7) python (2.x、3.x) 工具检查项目&#xff1a; 1、主机信息获取 2、系统初始化 alias 检查 3、文件类安全扫描 3.1、系统重要文件完整行…
阅读更多...
JS进阶-深入对象（二）

JS进阶-深入对象（二）

拓展&#xff1a;深入对象主要介绍的是Js的构造函数&#xff0c;实例成员&#xff0c;静态成员&#xff0c;其中构造函数和Java种的构造函数用法相似&#xff0c;思想是一样的&#xff0c;但静态成员和实例成员和java种的有比较大的差别&#xff0c;需要认真理解 • 创建对象三…
阅读更多...
Switch用法以及新特性-最全总结版

Switch用法以及新特性-最全总结版

本篇文章参考了大佬文章&#xff0c;感谢大佬无私分享&#xff1a; http://t.csdnimg.cn/MjZnX http://t.csdnimg.cn/QFg0x 目录 一、Switch用法&#xff1a;JDK7及以前 1.1、举例一&#xff1a; 1.2、举例二&#xff1a; 二、Switch穿透&#xff1a; 2.1、举例&#xf…
阅读更多...
三极管的奥秘：如何用小电流控制大电流

三极管的奥秘：如何用小电流控制大电流

双极性晶体管&#xff08;英语&#xff1a;bipolar transistor&#xff09;&#xff0c;全称双极性结型晶体管&#xff08;bipolar junction transistor, BJT&#xff09;&#xff0c;俗称三极管&#xff0c;是一种具有三个引脚的电子元器件。 本文是讲述的是三极管的基础知识…
阅读更多...
最新文章

Copyright @ 2022~2023