数据结构C语言之线性表

发现更多计算机知识，欢迎访问Cr不是铬的个人网站

1.1线性表的定义

线性表是具有相同特性的数据元素的一个有限序列 对应的逻辑结构图形：

file

从线性表的定义中可以看出它的特性：

（1）有穷性：一个线性表中的元素个数是有限的

（2）一致性：一个线性表中所有元素的性质相同，即数据类型相同

（3）序列性：各个元素的相对位置是线性的

1.2线性表的抽象数据类型描述

（如下图所示）

file

那为什么要引进这个数据结构呢？那就不得不谈谈它的作用了。

线性表的作用体现在两个方面：

a. 当一个线性表实现后，程序员加油直接使用它来存放数据，即作为存放数据的容器

b.使用线性表的基本运算来完成更复杂的运算

2.1线性表的顺序存储结构——顺序表

线性表的顺序存储结构简称为顺序表

file

（如图为线性表到顺序表的映射）

需要注意的是顺序表采用数组进行实现，但是不是任意数组可以作为一个顺序表，二者运算是不同的

​ 下图为顺序表的存储示意图

file

2.2顺序表的基本运算实现

（1）结构体SqList定义

//数据元素
typedef int ElemType;
//结构体
typedef struct
{
    ElemType data[MaxSize];
    //数据长度
    int length;
}SqList;

（2）建立顺序表

//建立顺序表
void CreateList(SqList*& L, ElemType a[], int n)
{
    int i = 0, k = 0;
    //记得一定要分配内存空间 
    L = (SqList*)malloc(sizeof(SqList));
    while (i < n)
    {
        //将a[i]存储到L中
        L->data[k] = a[i];
        k++; i++;
    }
    L->length = k;
}

（3）初始化线性表

void InitList(SqList*& L)
{
    L = (SqList*)malloc(sizeof(SqList));
    L->length = 0; //置空线性表的长度为0
}

(4)销毁线性表

void DestroyList(SqList*& L)
{
    free(L);//释放L所指的顺序表空间
}

(5)判断是否为空

bool ListEmpty(SqList* L)
{
    return(L->length == 0);
}

(6)求线性表长度

int ListLength(SqList* L)
{
    return (L->length);
}

（7）求表中某个值

bool GetElem(SqList* L, int i, ElemType& e)
{
    if (i<1 || i > L->length)
        return false;
    e = L->data[i - 1];
    return true;    //成功找到元素返回true
}

（8）按照元素值查找

int LocateElem(SqList* L,ElemType e)
{
    int i = 0;
    while (i < L->length && L->data[i] != e)
        i++;
    if (i >= L->length)
        return 0;
    else
        return i + 1;        //返回逻辑序号
}

（9）输出线性表

void DisplayList(SqList* L)
{
    for (int i = 0; i < L->length; i++)
        printf("%d", L->data[i]);
    printf("\n");
}

(10)完整代码

#include<iostream>
using namespace std;
const int MaxSize = 1005;
typedef int ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int length;
}SqList;

//建立顺序表
void CreateList(SqList*& L, ElemType a[], int n)
{
    int i = 0, k = 0;
    //记得一定要分配内存空间 
    L = (SqList*)malloc(sizeof(SqList));
    while (i < n)
    {
        L->data[k] = a[i];
        k++; i++;
    }
    L->length = k;
}
//初始化线性表
void InitList(SqList*& L)
{
    L = (SqList*)malloc(sizeof(SqList));
    L->length = 0; //置空线性表的长度为0
}
void DestroyList(SqList*& L)
{
    free(L);//释放L所指的顺序表空间
}
bool ListEmpty(SqList* L)
{
    return(L->length == 0);
}

int ListLength(SqList* L)
{
    return (L->length);
}
void DisplayList(SqList* L)
{
    for (int i = 0; i < L->length; i++)
        printf("%d", L->data[i]);
    printf("\n");
}
bool GetElem(SqList* L, int i, ElemType& e)
{
    if (i<1 || i > L->length)
        return false;
    e = L->data[i - 1];
    return true;    //成功找到元素返回true
}
int LocateElem(SqList* L,ElemType e)
{
    int i = 0;
    while (i < L->length && L->data[i] != e)
        i++;
    if (i >= L->length)
        return 0;
    else
        return i + 1;        //返回逻辑序号
}
bool ListInsert(SqList*& L, int i, ElemType e)
{
    int j;
    if (i < 1 || i >L->length + 1 || L->length == MaxSize)
        return false;
    i--;
    for (j = L->length; j > i; j--)
        L->data[j] = L->data[j - 1];
    L->data[i] = e;
    L->length++;
    return true;
}
bool ListDelete(SqList*& L, int i, ElemType& e)
{
    int j;
    //特判是否符合 
    if (i < 1 || i>L->length)
        return false;
    i--;
    for (int j = i; j < L->length - 1; j++)
        L->data[j] = L->data[j + 1];
    L->length--;
    return true;
}
void delnodel(SqList*& L, ElemType x)
{
    int k = 0;
    for (int i = 0; i < L->length; i++)
        if (L->data[i] != x)
        {
            L->data[k] = L->data[i];
            k++;
        }
    L->length = k;
}

}
int main() {
    SqList* L;
    int a[10] = { 7,5,7,7,9,1,6,2,4,8 };
    CreateList(L, a, 10);

    DisplayList(L);
}

2.3线性表的链式存储结构——链表

线性表的链式存储就是链表，每个链表存储点不仅包括数据域，还有指针域。

链表示意图如下：

file

2.4 单链表算法实现

（1）数据结构声明

typedef int ElemType;
typedef struct LinkNode
{
    ElemType data;        //存放元素值
    struct LinkNode* next;    //指向后继结点

}LinkNode;

建立单链表有两种方法：头插法和尾插法

(2)头插法

//建立单链表
void CreatListF(LinkNode*& L, ElemType a[], int n)
{
    LinkNode* s;
    //创建头结点 
    L = (LinkNode*)malloc(sizeof(LinkNode));
    L->next = NULL;    //头结点指针域置NULL
    for (int i = 0; i < n; i++)
    {
        s = (LinkNode*)malloc(sizeof(LinkNode));//重新分配空间
        s->data = a[i];
        s->next = L->next;
        L->next = s;
    }
}

(3)尾插法

void CreatListR(LinkNode*& L, ElemType a[], int n)
{
    LinkNode* s, * r;
    //创建头结点
    L = (LinkNode*)malloc(sizeof(LinkNode));
    r = L;                        //r始终指向尾结点，初始时指向头结点
    for (int i = 0; i < n; i++)
    {
        s = (LinkNode*)malloc(sizeof(LinkNode));//重新分配空间
        s->data = a[i];
        r->next = s;
        r = s;
    }
    //尾结点的nextt域置为NULL
    r->next = NULL;            
}

(4)初始化

void InitList(LinkNode*& L)
{
    L = (LinkNode*)malloc(sizeof(LinkNode));
    L->next = NULL;
}

(5)销毁表

void DestroyList(LinkNode*& L)
{
    LinkNode* pre = L, * p = L->next;    //pre指向p的前驱结点
    while (p != NULL)
    {
        free(pre);
        pre = p;
        p = pre->next;
    }
    free(pre);        //循环结束时p为NULL，pre指向尾结点
}

(6)输出表

void DispList(LinkNode* L)
{
    LinkNode* p = L->next;//指向头结点
    while (p!=NULL)
    {
        printf("%d", p->data);
        p = p->next;
    }
    printf("\n");
}

重点！！！

（7）链表的插入

bool ListInsert(LinkNode*& L, int i, ElemType e)
{
    int j = 0;
    LinkNode* p = L, * s;
    if (i <= 0)return false;//首结点的次序是一
    while (j < i - 1 && p != NULL)//找到第i-1个结点
    {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false;
    else
    {
        s = (LinkNode*)malloc(sizeof(LinkNode));
        //典中典
        s->data = e;
        s->next = p->next;
        p->next = s;
        return true;
    }
}

(8)删除某个元素

bool ListDelete(LinkNode*& L, int i, ElemType& e)
{
    int j = 0;
    LinkNode* p = L, * q;
    if (i <= 0)return false;//头结点是不计入其中的
    while (j < i - 1 && p != NULL)
    {
        j++;
        p = p->next;
    }        
    if (p == NULL)
        return false;
    else {
        q = p->next;
        if (q == NULL)
            return false;
        e = q->data;
        p->next = q->next;
        free(q);
        return true;
    }
}

最后介绍一下双链表

2.5双链表

(1)建立双链表

typedef int ElemType;
// 定义DlinkNode结构体
struct DlinkNode {
    int data;           // 数据域
    DlinkNode* prior;   // 前驱指针
    DlinkNode* next;    // 后继指针
};

同样的，双链表的建立也有头插法和尾插法

（2）头插法

// 定义CreateListF函数
void CreateListF(DlinkNode*& L, ElemType a[], int n)
{
    DlinkNode* s;
    L = (DlinkNode*)malloc(sizeof(DlinkNode)); // 创建头结点
    L->prior = L->next = NULL; // 先后指针域置NULL
    for (int i = 0; i < n; i++) // 循环创建数据结点
    {
        s = (DlinkNode*)malloc(sizeof(DlinkNode)); // 创建数据结点s
        s->data = a[i];
        s->next = L->next; // 将S插到头结点之后
        if (L->next != NULL)
            L->next->prior = s;
        L->next = s;
        s->prior = L;
    }
}

(3)尾插法

void CreateListR(DlinkNode*& L, ElemType a[], int n)
{
    DlinkNode* s,*r;
    L = (DlinkNode*)malloc(sizeof(DlinkNode)); // 创建头结点
    r = L;          //r始终指向尾结点，开始时指向头结点
    for (int i = 0; i < n; i++) // 循环创建数据结点
    {
        s = (DlinkNode*)malloc(sizeof(DlinkNode)); // 创建数据结点s
        s->data = a[i];
        r->next = s; s->prior = r;      //将s结点插入到r结点之后
        r = s;                          //r指向尾结点
    }
    r->next = NULL;
}

2.6总结

线性表是一种基础且重要的数据结构,常见的线性表有三种实现方式:顺序表、单链表和双链表。

​ 本文对这三种线性表的实现方式及特点做一个简要总结:

一、顺序表顺序表是将逻辑顺序上相邻的数据元素存储在物理位置上也相邻的存储单元中,通常使用数组来实现。- 特点:定位直接,通过下标操作即可快速访问任一位置的节点;实现简单。

缺点:插入删除需要移动大量元素,效率低;存储空间固定,扩容不灵活。

二、单链表单链表通过链式存储结构实现,每个节点除存储数据外,还储存下一个节点的地址信息。

-特点:存储灵活,可动态扩展,插入删除简单,效率高。-

缺点:访问任一节点需要从头结点遍历,无法直接定位

三、双链表双链表相比单链表,每个节点增加一个指向前驱节点的指针,实现双向链表。-

特点:可双向遍历链表,操作更灵活。-

缺点:每个节点存储空间略大于单链表。

​ 综上,三种线性表各有特点,使用需根据具体场景需求选择合适的数据结构。顺序表操作简单,链表存储灵活,双链表可以双向访问。开发时需要权衡效率与实现难度,选择最优实现。

本文由博客一文多发平台 OpenWrite 发布！

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

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

相关文章

线程状态及线程之间通信

线程状态及线程之间通信

线程状态概述 当线程被创建并启动以后&#xff0c;它既不是一启动就进入了执行状态&#xff0c;也不是一直处于执行状态。在线程的生命周期中&#xff0c; 有几种状态呢&#xff1f;在 java.lang.Thread.State 这个枚举中给出了六种线程状态&#xff1a; 线程状态 导致状态发生…
阅读更多...
Objectarx 使用libcurl请求WebApi

Objectarx 使用libcurl请求WebApi

因为开发cad需要请求服务器的数据&#xff0c;再次之前我在服务器搭设了webapi用户传递数据&#xff0c;所以安装了libcurl在objectarx中使用数据。 Open VS2012 x64 Native Tools Command Prompt补充地址&#xff1a; 我在此将相关的引用配置图片&#xff0c;cad里面的应用和…
阅读更多...
Linux中的进程等待（超详细）

Linux中的进程等待（超详细）

Linux中的进程等待 1. 进程等待必要性2. 进程等待的方法2.1 wait方法2.2 waitpid方法 3. 获取子进程status4. 具体代码实现 1. 进程等待必要性 我们知道&#xff0c;子进程退出&#xff0c;父进程如果不管不顾&#xff0c;就可能造成‘僵尸进程’的问题&#xff0c;进而造成内…
阅读更多...
UE的PlayerController方法Convert Mouse Location To World Space

UE的PlayerController方法Convert Mouse Location To World Space

先上图&#xff1a; Convert Mouse Location To World这是PlayerController对象中很重要的方法。 需要说明的是两个输出值。 第一个是World Location&#xff0c;这是个基于世界空间的位置值&#xff0c;一开始我以为这个值和当前摄像机的位置是重叠的&#xff0c;但是打印出来…
阅读更多...
kaggle项目部署

kaggle项目部署

目录 流程详细步骤注意事项 流程 修改模块地址打包项目上传到kaggle Datasets创建code文件&#xff0c;导入数据与项目粘贴train.py文件&#xff0c;调整超参数&#xff0c;选择GPUsave version&#xff0c;后台训练查看训练结果 详细步骤 打开kaggle网站&#xff0c;点击da…
阅读更多...
号卡分销管理系统搭建

号卡分销管理系统搭建

随着移动互联网的发展&#xff0c;各种手机应用层出不穷&#xff0c;其中包括了很多用于企业管理的软件。号卡系统分销管理软件就是其中的一种。它是一种基于移动互联网的企业管理软件&#xff0c;能够帮助企业进行号卡的分销管理&#xff0c;从而提高企业的效率和竞争力。 …
阅读更多...
抖音快手判断性别、年龄自动关注脚本，按键精灵开源代码！

抖音快手判断性别、年龄自动关注脚本，按键精灵开源代码！

这个是支持抖音和快手两个平台的&#xff0c;可以进入对方主页然后判断对方年龄和性别&#xff0c;符合条件的关注&#xff0c;不符合条件的跳过下一个ID&#xff0c;所以比较精准&#xff0c;当然你可以二次开发加入更多的平台&#xff0c;小红书之类的&#xff0c;仅供学习&a…
阅读更多...
Linux（3）：Linux 的文件权限与目录配置

Linux（3）：Linux 的文件权限与目录配置

把具有相同的账户放入到一个组里面&#xff0c;这个组就是这两个账户的 群组 。在访问资源&#xff08;操作系统中计算机的资源&#xff09;时&#xff0c;可以让这个组里面的所有用户都具有访问权限。 每个账号都可以有多个群组的支持。 在我们Liux 系统当中&#xff0c;默认的…
阅读更多...
kibana8.10.4简单使用

kibana8.10.4简单使用

1.创建discovery里的日志项目 点击stack management 选择kibana里的数据视图&#xff0c;右上角创建数据视图&#xff0c;输入名称。索引范围。例子 example-* ,匹配以example-开头的所有index。 然后点击 保存数据视图到kibana&#xff0c; 2.Kibana多用户创建及角色权限控…
阅读更多...
macOS下如何使用Flask进行开发

macOS下如何使用Flask进行开发

&#x1f468;&#x1f3fb;‍&#x1f4bb; 热爱摄影的程序员 &#x1f468;&#x1f3fb;‍&#x1f3a8; 喜欢编码的设计师 &#x1f9d5;&#x1f3fb; 擅长设计的剪辑师 &#x1f9d1;&#x1f3fb;‍&#x1f3eb; 一位高冷无情的编码爱好者 大家好&#xff0c;我是全栈工…
阅读更多...
力扣栈与队列--总结篇

力扣栈与队列--总结篇

前言 八道题&#xff0c;没想到用了五天。当然需要时间的沉淀&#xff0c;但是一天不能啥也不干啊&#xff01; 内容 首先得熟悉特点和基本操作。 栈与队列在计算机底层中非常重要&#xff0c;这就是为什么要学好数据结构。 可视化的软件例如APP、网站之类的&#xff0c;都…
阅读更多...
Word中NoteExpress不显示的问题

Word中NoteExpress不显示的问题

首先确认我们以及安装了word插件 我们打开word却没有。此时我们打开&#xff1a;文件->选项->加载项 我们发现被禁用了 选择【禁用项目】&#xff08;如果没有&#xff0c;试一试【缓慢且禁用的加载项】&#xff09;&#xff0c;点击转到 选择启用 如果没有禁用且没有出…
阅读更多...
工具推荐-卸载小助手GeekUninstaller

工具推荐-卸载小助手GeekUninstaller

一.简介 1.1 GeekUninstalers是一款高效、快速、小巧、免费的软件卸载与清理工具&#xff0c;旨在帮助用户删除系统上安装的程序。 1.2 不同于其他的卸载程序&#xff0c;GeekUninstaller执行深入扫描进程&#xff0c;并清除软件卸载后留下的垃圾。 1.3 它是一款绿色软件&…
阅读更多...
有关编译器的科普

有关编译器的科普

Clang和GCC的主要区别如下所示&#xff1a; Clang比GCC编译用的时间更短&#xff0c;包括预处理、语法分析、解析、语义分析、抽象语法树生成的时间。Clang比GCC的内存占用更小。Clang生成的中间产物比GCC更小。Clang的错误提示比GCC更加友好。Clang有静态分析&#xff0c;GCC…
阅读更多...
合璧之光，共创辉煌｜明道云伙伴大会2023圆满结束

合璧之光，共创辉煌｜明道云伙伴大会2023圆满结束

2023年11月3日至11月4日&#xff0c;“合璧之光明道云伙伴大会2023”在上海星河湾酒店顺利举行&#xff0c;报名参会人数超过1800人。大会邀请到明道云标杆客户及合作伙伴分享组织落地零代码的经验及各行业领域解决方案&#xff0c;包括越秀集团、豫园股份、远大医药&#xff0…
阅读更多...
Springboot+vue的应急物资管理系统（有报告），Javaee项目，springboot vue前后端分离项目

Springboot+vue的应急物资管理系统（有报告），Javaee项目，springboot vue前后端分离项目

演示视频&#xff1a; Springbootvue的应急物资管理系统&#xff08;有报告&#xff09;&#xff0c;Javaee项目&#xff0c;springboot vue前后端分离项目 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。…
阅读更多...
极光笔记 | EngageLab Push的多数据中心接入指南

极光笔记 | EngageLab Push的多数据中心接入指南

01背景 作为一个面向全球的消息推送服务平台&#xff0c;我们一直致力于给全球用户提供安全、可靠、高效的消息推送服务&#xff0c;因此我们意识到在不同洲建立数据中心的重要性。这样做将有助于提高我们的服务可用性、降低延迟并保护用户数据的安全性。 第一&#xff0c;通过…
阅读更多...
redis数据结构

redis数据结构

1 string&#xff08;字符串&#xff09;->opsForValue 介绍 一个 string 类型的键最大可以存储 512 MB 的数据 应用场景 1 缓存数据&#xff0c;提高访问速度和降低数据库压力。 2 计数器&#xff0c;利用 incr 和 decr 命令实现原子性的加减操作。 3 分布式锁&#xff0c…
阅读更多...
Oracle 存储过程数据插入临时表慢以及SQL语句查询慢

Oracle 存储过程数据插入临时表慢以及SQL语句查询慢

/*parallel*/ 解释: 一般表数据量比较大&#xff08;超过100万&#xff09;时&#xff0c;可以使用parallel强制启动并行度来提升查询速度 用法&#xff1a;/*parallel(table_short_name,cash_number)*/ 可以加到insert、delete、update、select的后面来使用 比如&#xff…
阅读更多...
数字逻辑电路基础-组合逻辑电路之复用器

数字逻辑电路基础-组合逻辑电路之复用器

文章目录 一、复用器简介二、verilog源码三、综合及仿真结果一、复用器简介 本文介绍数字逻辑电路中一种常用的基础组合逻辑电路-两选一复用器，顾名思义，它的功能就是通过一个控制信号来选择两个输入中之一作为输出。 它的逻辑表达式为：out = ~sa + sb 它的逻辑真值表为：…
阅读更多...
最新文章

Copyright @ 2022~2023