数据结构 线性表的定义和基本操作(以顺序表为例)

这篇具有很好参考价值的文章主要介绍了数据结构 线性表的定义和基本操作(以顺序表为例)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

名人说:一花独放不是春,百花齐放花满园。——《增广贤文》
作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊)

以下代码个人分享出来,仅供学习交流,且仅在CSDN平台发布,未经授权禁止二次转发。

〇、线性表是什么?

1、定义

线性表是具有相同数据类型n(n>=0)个数据元素的有限序列,其中n为表长,当n=0时线性表是一个空表。

L=(a1,a2,a3…,an) a1为表头元素,an为表尾元素,除第一个元素外,每个元素有且仅有一个直接前驱,除最后一个元素,每个元素有且仅有一个直接后继。
数据结构 线性表的定义和基本操作(以顺序表为例),# 数据结构,# C/C++提高篇,算法,c++,数据结构,线性表,基本操作

2、特点
  • ①同类型
  • ②有限
  • ③有序
3、基本操作

数据结构 线性表的定义和基本操作(以顺序表为例),# 数据结构,# C/C++提高篇,算法,c++,数据结构,线性表,基本操作

那么该怎么用代码实现基本操作呢?请往下看(以顺序表为例)

一、代码实现

#include <iostream>
using namespace std;

#define MaxSize 50
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int length;
}SqList;

// 初始化线性表
void InitList(SqList &L) {
    L.length = 0;
}

// 销毁线性表
void DestroyList(SqList &L) {
    L.length = 0;
}

// 在第i个位置插入元素e
bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return false;
    if (L.length >= MaxSize) return false;
    for (int j = L.length; j >= i; j--)
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;
    L.length++;
    return true;
}

// 删除第i个位置的元素,并用e返回其值
bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return false;
    e = L.data[i - 1];
    for (int j = i; j < L.length; j++)
        L.data[j - 1] = L.data[j];
    L.length--;
    return true;
}

// 按值查找,返回元素e的位序
int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e) return i + 1;
    return 0;
}

// 按位查找,返回第i个位置的元素值
bool GetElem(SqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return false;
    e = L.data[i - 1];
    return true;
}

// 返回线性表的长度
int Length(SqList L) {
    return L.length;
}

// 输出线性表
void PrintList(SqList L) {
    for (int i = 0; i < L.length; i++)
        cout << L.data[i] << " ";
    cout << endl;
}

// 判断线性表是否为空
bool Empty(SqList L) {
    return L.length == 0;
}

int main() {
    SqList L;
    InitList(L);
    ListInsert(L, 1, 3);
    ListInsert(L, 2, 4);
    ListInsert(L, 3, 5);
    PrintList(L);
    
    int e = -1;
    ListDelete(L, 2, e);
    cout << "删除的元素为:" << e << endl;
    
    PrintList(L);
    
    cout << "线性表长度为:" << Length(L) << endl;
    
    cout << "元素4的位置为:" << LocateElem(L,4) << endl;

}

十万个为什么:代码中为什么要传入参数的引用“&”?

因为想要将 对参数的修改结果 “带回来”

二、思路阐明

顺序表是一种线性表的存储结构。顺序表使用一段连续的存储单元来存储数据,每个数据元素占用一个存储单元。

在实现上述代码的过程中,首先使用了一个结构体来定义顺序表,其中又用了一个数组data存储数据元素,一个整型变量length用来记录线性表的长度

之后实现了多种对顺序表的操作,包括初始化、销毁、插入、删除、按值查找、按位查找、求长度、输出和判空。

  • InitList(&L)函数:初始化线性表,将长度设为0。
  • DestroyList(&L)函数:销毁线性表,将长度设为0。
  • ListInsert(&L,i,e)函数:在第i个位置插入元素e。首先判断插入位置是否合法,然后将第i个位置及之后的元素后移一位,腾出空间插入新元素,最后将线性表长度加1。
  • ListDelete(&L,i,&e)函数:删除第i个位置的元素,并用e返回其值。首先判断删除位置是否合法,然后将被删除元素的值赋给e,再将第i个位置之后的元素前移一位,最后将线性表长度减1。
  • LocateElem(L,e)函数:按值查找,返回元素e的位序。遍历线性表,找到第一个值等于e的元素并返回其位序。
  • GetElem(L,i)函数:按位查找,返回第i个位置的元素值。首先判断查找位置是否合法,然后返回第i个位置的元素值。
  • Length(L)函数:返回线性表的长度。
  • PrintList(L)函数:输出线性表。
  • Empty(L)函数:判断线性表是否为空。

最终按照顺序表的操作顺序,在main函数中进行调用测试即可,具体测试见下方样例测试,以上就是这段代码的简要实现思路。

三、样例测试

首先在1、2、3位置插入3、4、5的值,长度为3,之后删除值为4的元素,接着计算线性表的长度,由一开始的3变为了2,也表明了删除成功,在查找元素4的位置时,由于元素4已经被删除了,所以在查找函数中返回了0。

3 4 5
删除的元素为:4
3 5
线性表长度为:2
元素4的位置为:0

--------------------------------
Process exited after 0.06322 seconds with return value 0
请按任意键继续. . .

✔ 部分内容参考:王道数据结构(B站/MOOC 咸鱼学长主讲)
Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊)
如果对大家有帮助的话,希望大家能多多点赞+关注!这样我动力会更足哦! ღ( ´・ᴗ・` )比心文章来源地址https://www.toymoban.com/news/detail-520035.html

到了这里,关于数据结构 线性表的定义和基本操作(以顺序表为例)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】单链表——单链表的定义及基本操作的实现(头插、尾插、头删、尾删、任意位置的插入与删除)

    🧑‍💻作者: @情话0.0 📝专栏:《数据结构》 👦个人简介:一名双非编程菜鸟,在这里分享自己的编程学习笔记,欢迎大家的指正与点赞,谢谢!   顺序表可以随时存取表中的任意一个元素,它的存储位置可以用一个简单直观的公式表示,但是插入和删除操作需要移动

    2024年02月19日
    浏览(204)
  • 数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现,含注释

      头文件和源文件分开有很多好处:可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性,同时也可以使代码结构更清晰,方便代码的管理和维护。 LinkList.h test.cpp                  (下面所有函数都默认在类中实现)   我们以

    2024年02月07日
    浏览(57)
  • 数据结构---双向链表的基本操作

    头插法 遍历链表 尾插法 头删法 尾删法 按位置插入数据 按位置删除数据 dooublelinklist.c doublelinklist.h doublemain.c

    2024年02月22日
    浏览(53)
  • 【数据结构】——单链表的基本操作(带头结点)

            单链表解决了顺序表需要大量连续存储单元的缺点,但单链表附加指针域, 存储密度较顺序表低(考点!!) 。由于单链表的元素离散地分布在存储空间中,所以单链表是 非随机存取 的存储结构,即不能直接找到表中某个特定的结点。当查找某个特定结点时,需要

    2024年02月05日
    浏览(51)
  • 【数据结构】C语言实现双链表的基本操作

    大家好,很高兴又和大家见面啦!!! 经过前面几个篇章的内容分享,相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中,咱们将介绍双链表的创建以及一些基本操作,接下来跟我一起

    2024年02月04日
    浏览(62)
  • c语言数据结构——链表的实现及其基本操作

    顺序表的问题及思考 问题: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插

    2023年04月09日
    浏览(85)
  • 【数据结构】单链表的基本操作 (C语言版)

    目录 一、单链表 1、单链表的定义: 2、单链表的优缺点: 二、单链表的基本操作算法(C语言) 1、宏定义 2、创建结构体 3、初始化 4、插入 4、求长度 5、清空 6、销毁  7、取值 8、查找 9、删除 10、头插法创建单链表 11、尾插法创建单链表 三、单链表的全部代码(C语言)

    2024年01月22日
    浏览(59)
  • 【数据结构】C语言实现单链表的基本操作

    大家好,很高兴又和大家见面啦!!! 在上一篇中,我们详细介绍了单链表的两种创建方式——头插法与尾插法,相信大家现在对这两种方式都已经掌握了。今天咱们将继续介绍单链表的基本操作——查找、插入与删除。在开始今天的内容之前,我们先通过尾插法创建一个单

    2024年02月03日
    浏览(65)
  • 【数据结构】 循环双链表的基本操作 (C语言版)

    目录 一、循环双链表 1、循环双链表的定义: 2、循环双链表的优缺点: 二、循环双链表的基本操作算法(C语言)    1、宏定义  2、创建结构体 3、循环双链表的初始化  4、循环双链表按位查找 5、循环双链表插入 6、循环双链表查找 7、循环双链表删除 8、求循环双链表长

    2024年01月22日
    浏览(59)
  • 【数据结构】 循环单链表的基本操作 (C语言版)

    目录 一、循环单链表 1、循环单链表的定义: 2、循环单链表的优缺点: 二、循环单链表的基本操作算法(C语言)    1、宏定义  2、创建结构体 3、循环单链表的初始化  4、循环单链表的插入 5、求单链表长度 6、循环单链表的清空 7、循环单链表的销毁 8、循环单链表的取

    2024年01月22日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包