程序员经验分享-hwhale

线性表(C++实现)

2023-11-15

线性表的定义与基本操作

定义

具有相同数据类型的n个数据元素的有限序列，n是表长，当n为0的时候线性表是一个空表。如果用L命名线性表，那么其一般表示为
L = ( a 1 ， a 2 ， . . . ， a i ， a i + 1 ， . . . ， a n ) L=(a_1，a_2， ...，a_i，a_{i+1}，...，an) L=(a1​，a2​，...，ai​，ai+1​，...，an)
式中， a 1 a_1 a1​是唯一的"第一个"数据元素，称为表头元素，而 a n a_n an​是唯一的"最后一个元素"，称为表尾元素。

逻辑特性：除了第一个元素外，每个元素都有且只有一个直接前驱，除了最后一个元素外，每个元素都有且只有一个直接后继。

特点：

  • 表中元素个数有限
  • 表中元素具有逻辑上的顺序性，表中元素具有其先后次序。
  • 表中元素都是数据元素，每个元素都是单个元素
  • 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
  • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容

**注意：线性表是一个逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表指的是存储结构，两者之间没有任何关系，属于不同层面的问题。

线性表需要满足的基本操作(需要完成的接口)

  1. InitList(&L); 初始化表，构造一个空的线性表
  2. Length(L); 求表长。返回线性表L的长度，即L中元素的个数
  3. LocateElem(L,e); 按值查找操作。在表L中查找具有给定关键字值的元素
  4. GetElem(L,i); 按位查找操作，获取表L中第i个位置的元素
  5. ListInsert(&L, i, e); 插入操作，在表L中的第i个位置插入指定元素e
  6. ListDelete(&L, i, &e); 删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值
  7. PrintList(L); 输出操作，按前后顺序输出线性表L的所有元素值
  8. Empty(L); 判空操作。如果L为空表，就返回true，否则返回false
  9. Destroy(&L); 销毁操作，销毁线性表，并释放线性表L所占用的内存空间

***注意：***①基本操作的实现取决于采用哪种存储结构(顺序表或是链表),存储结构不同，实现的算法也不一样。②"&"表示C++语言中的引用调用，在C语言中采用指针也可达到同样的效果。

顺序表(数组)实现

  1. DeletSmallest(&L); 从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删除元素的值。空出的位置由最后一个元素填补，如果顺序表为空，则显示出错信息并推出运行
  2. Turn(&L); 设计一个高效的算法，将顺序表L的说有元素逆置，要求算法的空间复杂度为O(1)
  3. DeleteX(&L,x); 对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素
  4. inXAndY(&L,x,y); 从顺序表中删除其值在给定值s与t之间(包含s和t，要求s<t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行
  5. Unique(&L); 从有序顺序表中删除所有其值重复的元素，使表中所有的元素的值都不一样
  6. Merge(&L,&R); 将两个有序数组合并为一个新的有序顺序表，并由函数返回结果顺序表
  7. TurnInArray(&L,m); 已知一维数组A[m+n]中依次存放两个线性表， ( a 1 , a 2 , . . . , a m ) (a_1,a_2,...,a_m) (a1​,a2​,...,am​)和 ( b 1 , b 2 , . . . , b n ) (b_1,b_2,...,b_n) (b1​,b2​,...,bn​)。编写一个函数，将数组中两个顺序表的位置互换，即将 ( b 1 , b 2 , . . . , b n ) (b_1,b_2,...,b_n) (b1​,b2​,...,bn​)放在 ( a 1 , a 2 , . . . , a m ) (a_1,a_2,...,a_m) (a1​,a2​,...,am​)前面。
  8. SearchInDouble(&L,x); 线性表 ( a 1 , a 2 , a 3 , . . . , a n ) (a_1,a_2,a_3,...,a_n) (a1​,a2​,a3​,...,an​)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，完成用最少时间在表中查找值为x的元素，若找到，则将其于后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序
#include <iostream>
#include <cstring>

using namespace  std;

typedef struct {
    int * data;
    int MaxSize , length;
}SqList;

void Expand(SqList &L, int ex){
    int * p = L.data;
    L.data = new int [L.length+ex];
    for(int i = 0 ; i<L.length ; i++){
        p[i] = L.data[i];
    }
    delete[]p;
    cout<<"complete"<<endl;
}

void InitList( SqList &L , int initSize){
    L.data = new int [initSize];
    L.MaxSize = initSize;
    L.length = 0;
}

void Length(SqList L){
    cout<<L.length<<endl;
}

void LocateElem(SqList L, int e){
    for(int i = 0 ; i<L.length ; i++){
        if (L.data[i]==e) {
            cout << i;
            return;
        }
    }
    cout<<"not found"<<endl;
}

void GetElem(SqList L, int i ){
    if (i<1||i>L.length){
        cout<<"超出界限"<<endl;
        return;
    }
    cout<<L.data[i-1]<<endl;
}

void ListInsert(SqList &L, int i , int e){
    if(i<1||i>L.length+1){
        cout<<"超出界限"<<endl;
        return;
    }
    if(L.length>=L.MaxSize){
        Expand(L,5);
    }
    for(int j = L.length ; j>=i ; j--){
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;
    L.length++;
    cout<<"complete"<<endl;
}

bool Empty (SqList L){
    if (L.length==0){
        return true;
    }
    return false;
}

void ListDelete(SqList &L , int i , int &e){
    if(Empty(L)){
        cout<<"顺序表为空"<<endl;
        return;
    }
    e = L.data[i-1];
    for(int j = i ; j<=L.length ; j++){
        L.data[j-1] = L.data[j];
    }
    L.length--;
}

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

void Destroy (SqList &L){
    delete []L.data;
    L.length=0;
    L.MaxSize=0;
    cout<<"complete"<<endl;
}

void DeleteSmallest(SqList &L){
    if(Empty(L)){
        cout<<"SqList is NULL!"<<endl;
        return;
    }
    int a = L.data[0];
    int id = 0;
    int *pid = &id;
    for (int i = 0; i < L.length; ++i) {
        if (a>L.data[i]){
            *pid = i;
            a = L.data[i];
        }
    }
    L.data[id] = L.data[L.length-1];
    L.length--;
    cout<<a<<"delete"<<endl;
}

void Turn (SqList &L){
    if (Empty(L)){
        cout<<"SqList is NULL!"<<endl;
        return;
    }
    int i = 0 ;
    int j = L.length-1;
    while(i<j){
        swap(L.data[i],L.data[j]);
        i++;
        j--;
    }
}

void DeleteX(SqList &L, int x){
    if (Empty(L)){
        cout<<"SqList is NULL!"<<endl;
        return;
    }
    int k = 0;
    int *pk = &k;
    for(int i = 0 ; i<L.length ; i++){
        if (L.data[i]==x){
            *pk+=1;
        }
        else{
            L.data[i-*pk] = L.data[i];
        }
    }
    L.length = L.length-*pk;
}

void inXAndY(SqList &L, int x , int y){
    if(Empty(L)){
        cout<<"SqList is Empty!"<<endl;
        return;
    }
    if(x>y){
        swap(x,y);
    }
    int k = 0 ;
    int *pk = &k;
    for(int i = 0 ; i<L.length; i++){
        if (L.data[i]>=x&&L.data[i]<=y){
            *pk+=1;
        }
        else{
            L.data[i-k] = L.data[i];
        }
    }
    L.length = L.length-*pk;
}

void Unique(SqList &L){
    int *p = L.data;
    L.data =  new int [L.MaxSize];
    bool *flag = new bool [100];
    int j = 0;
    memset(flag,false,10);
    for(int i = 0 ; i<L.length ; i++){
        if (!flag[p[i]]){
            L.data[j] = p[i];
            flag[p[i]]= true;
            j++;
        }
    }
    L.length = j;
    delete[]p;
}

void Merge(SqList &L , SqList &R){
    while (L.MaxSize<R.length){
        Expand(L,R.length);
    }
    int *p = L.data;
    int i = 0 , j = 0 , id = 0;
    while(i<L.length&&j<R.length){
        if (p[i]<=R.data[j]){
            L.data[id] = p[i];
            i++;
        } else{
            L.data[id] = R.data[j];
            j++;
        }
        id++;
    }
    if (i<L.length){
        for (;  i<L.length ; i++,id++) {
            L.data[id]= p[i];
        }
    }
    if(j<R.length){
        for (;  j<R.length ; j++,id++) {
            L.data[id] = R.data[j];
        }
    }
    L.length = R.length+L.length;
}

void TurnInArray(SqList &L,int m ){
    int *p = L.data;
    L.data = new int [L.MaxSize];
    int j = 0;
    for (int i = m ; i <L.length ; ++i,j++) {
        L.data[j] = p[i];
    }
    for(int i = 0 ; i<m ; i++,j++){
        L.data[j] = p[i];
    }
}

void SearchInDouble (SqList &L, int x){
    int left = 0;
    int right = L.length-1;
    int m  ;
    while(left<right){
        m = (left+right)/2;
        if (L.data[m]<x){
            left = m+1;
        }
        else if(L.data[m]>x){
            right = m-1;
        } else{
            swap(L.data[m],L.data[m+1]);
            return;
        }
    }
    ListInsert(L,left+2,x);
}

int main() {
    SqList L ;
    int initSize = 10;
    int show = 0;
    InitList(L,initSize);
}

链表(指针)实现

//
// Created by PrimeChuJiang on 2022/11/12.
//
#include <iostream>

using namespace std;

typedef struct LNode{
    int data;
    struct LNode *ptr;
}LNode , *LinkList;

bool InitList(LinkList & L){
//    LNode a ;
    L = new LNode ;
    if (L== nullptr)return false;
    L->ptr = nullptr;
    return true;
}

int Length(LinkList L){
    LNode * p = L;
    int i = 0 ;
    for ( ; p->ptr != nullptr ; p = p->ptr) {
        i++;
    }
    return i;
}

LNode* LocateElem(LinkList L, int e){
    LNode *p = L;
    while(p->ptr != nullptr){
        if (p->data==e){
            return p;
        }
        else{ continue;}
    }
    return nullptr;
}

LNode * GetElem(LinkList L , int i){
    LNode *p = L->ptr;
    if (i==0){return L;}
    if (i<0)return nullptr;
    for (int j = 1; j < i && p ; ++j) {
        p = p->ptr;
    }
    return p;
}

void ListInsert (LinkList &L , int i , int e){
    LNode *p = GetElem(L , i);
    auto s = new LNode ;
    s->data = p->data;
    s->ptr = p->ptr;
    p->ptr = s;
    p->data = e;
}

bool ListDelete(LinkList &L , int i , int &e){
    LNode *p = GetElem(L,i-1);
    LNode *d = p->ptr;
    p->ptr = d->ptr;
    delete d;
    return true;
}

void PrintList(LinkList L){
//    LNode *p = L;
    for (LNode *p= L->ptr;  p!= nullptr ; p=p->ptr) {
        cout << p->data;
    }
}

bool Empty(LinkList L){
    return L->ptr == nullptr;
}

void DestroyList(LinkList &L){
    if (!L->ptr){
        delete L;
        return;
    }
    LNode *p = L->ptr;
    LNode *d = L;
    while(p->ptr){
        delete d;
        d = p;
        p = p->ptr;
    }
    delete d;
    delete p;
}

LinkList List_HeadInsert(LinkList &L, int e){
    auto *p = new LNode ;
    p->data = e;
    p->ptr = L->ptr;
    L->ptr = p;
    return L;
}

LinkList List_TailInsert(LinkList &L, int e){
    auto *p = new LNode ;
    for(;p->ptr!= nullptr;p=p->ptr){}
    auto *s = new LNode ;
    s->data = e;
    p->ptr = s;
    s->ptr = nullptr;
    return L;
}

int main(){
    LinkList L ;
    InitList(L);
    cout <<"a"<<endl;

}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

链表

考研

改行学it

线性表(C++实现) 的相关文章

随机推荐

  • 问题解决：记录一次Linux服务器根目录突然爆满

    一 出问题了 过了个双休来到公司 同时发现Linux终端的服务器状态中根目录空间直接爆满100 周五走之前根目录仅仅使用了59 同时项目服务的后台不停的有日志打印 而且测试的小伙伴说系统登录不上去了 下面记录一下个人排查并解决这个问题的全过

  • 解决电脑无法通过网线直连海康摄像机的问题

    一 现象 通过博主的另外一篇博客https blog csdn net u014552102 article details 86700057 配置完海康网络摄像机后 摄像机可以通过路由器wifi传输视频声音 并通过手机客户端和电脑客户端播

  • VUE项目本地运行调试遇到问题，npm run,install 报错

    IDE 随意选择 太多了 VSCode webstorm 一 安装node js npm vue cli 这三个东西教程挺多的 我这里就不详细说了 我之前开发的时候安装过 查看当前电脑上有没有安装 注意V的大小写 node v npm v

  • Vue.js怎么给文本域赋默认值,和获取输入的值

    Vue js怎么给文本域赋默认值 一般给文本域赋初值用于修改某个东西 需要获取默认值 可以用v model来完成

  • Sublime Text 3 文本编辑器软件

    为什么80 的码农都做不了架构师 gt gt gt http www xiazaiba com html 24343 html Sublime Text 2 设置文件详解 http linux cn article 799 1 html S

  • 45类商标分类表明细表

    商标注册分类采用的是尼斯分类 尼斯联盟成员国采用 商标注册用商品和服务国际分类 尼斯分类将商品和服务分成45个大类 其中商品为1 34类 服务为35 45类 商标局将尼斯分类的商品和服务项目划分类似群 并结合实际情况增加我国常用商品和服务项

  • SpringBoot使用多数据源时怎么解决事务不生效问题

    在使用多数据源时 如果不进行特殊处理 可能会出现事务不生效的问题 这是因为 Spring Boot 默认只会为一个数据源创建一个事务管理器 如果要使用多个数据源 就需要为每个数据源创建一个事务管理器 并在需要使用事务的方法或类上指定使用哪个

  • Istio Pilot源码学习（二）：ServiceController服务发现

    本文基于Istio 1 18 0版本进行源码学习 4 服务发现 ServiceController ServiceController是服务发现的核心模块 主要功能是监听底层平台的服务注册中心 将平台服务模型转换成Istio服务模型并缓存

  • linux环境下设置用户密码过期期限

    关于密码过期时间和用户过期时间的设置 通常使用chage命令和usermod命令 设置某个用户的过期时间 accountexpires 可以用usermod e来设置 查看某个用户的密码 passwordexpires 过期时间等信息 可以

  • Java里Controller层参数不必填

    public Result

  • KNN算法的一个回归应用分析

    介绍 在我所接触的机器学习算法中 KNN是一种相对来说较容易理解的算法 但是它在实际中仍有十分广泛的应用 KNN算法可以用于分类和回归问题 在分类问题中应用较多 虽然KNN很少用于回归问题 但对于连续的变量仍有很好的效果 下面我们来介绍KN

  • 一篇打通，pytest自动化测试框架详细，从0到1精通实战（一）

    前言 pytest单元测试框架 1 什么是单元测试框架 单元测试是指在软件开发当中针对软件的最小单位 函数 方法 进行正确性的检查测试 2 单元测试框架有哪些 Java junit 和 testing python unittest 和 p

  • 整理了一些常用的免费api接口，不限次数，收藏备用~（持续更新...）

    API Application Program Interface 被定义为应用程序可用以与计算机操作系统交换信息和命令的标准集 一个标准的应用程序界面为用户或软件开发商提供一个通用编程环境 以编写可交互运行于不同厂商计算机的应用程序 AP

  • ISP_matlab

    确定输入是否为结构体数组字段 MATLAB isfield MathWorks 中国 对话框打开文件 获取路径和文件名 file path uigetfile raw RAW fid fopen fullfile path file htt

  • 百度通用翻译api使用

    官方api文档 http api fanyi baidu com api trans product apidoc springboot demo地址 https github com Blankwhiter translate 第一步 注

  • python web界面模板_Python简单轻量级Web Server模块Bottle

    Bottle 提示 使用此WEB服务器模块需要有基本的HTTP知识 简单 轻量级指的是 上手不难 容易使用 模块不大还能完成一般Web服务器的功能 Bottle是Python平台的轻量级Web Server 准确的说是HTTP Server

  • node.js在idea里运行

    Node js 是一种运行在 Chrome V8 JavaScript 引擎上的基于 JavaScript 的客户端运行时 JavaScript runtime 它可以用于构建网络应用程序和服务 在 Node js 中 你可以使用多种构建工

  • 从数据库字符串中获取数字部分，用于数据分析

    目录 前言 一 思路 1 获取字符串中的小数及整数部分 代码 效果 解析 2 获取字符串中数字部分 代码 效果 解析 二 总结 前言 在大数据时代 我们经常要分析很多非结构化的数据 同时也要分析很多非标准的数据 如 0 78吨 CYJ23w

  • 【数据结构 001】 定义

    数据 能被计算机处理 能被计算机识别 能输入计算机 数据元素 有一定意义的基本单位 数据项 数据元素的组成单位 认为是数据结构中最小组成单位 数据对象 具有相同性质的数据元素的集合 数据结构 存在特定关系的数据的集合 数据之间特定的结构关系

  • 线性表(C++实现)

    线性表的定义与基本操作 定义 具有相同数据类型的n个数据元素的有限序列 n是表长 当n为0的时候线性表是一个空表 如果用L命名线性表 那么其一般表示为 L a 1

热门标签