码农小屋 码农小屋
  • 首页
  • 文章
    • Python
    • 计算机基础
    • C语言
    • Java
    • 数据库
    • Linux
  • 资源
  • 随笔
  • 优秀软件
  • 24h新鲜事
  • 专题
  • 留言板
  • 注册 登录
立即登录
0文章
0评论
0获赞
  • 首页
  • 博客中心
    • 文章
    • 资源
  • 随笔
  • 优秀软件
  • 24h新鲜事
  • 专题
  • 留言板
主页 › 文章 › 计算机基础 › 数据结构——线性表
#计算机基础#

数据结构——线性表

3月前
94 0 0

线性表的定义

线性表:简称表,是n(n≥0)个具有相同类型数据元素的有限序列。

线性表的长度:线性表中数据元素的个数。

空表:长度等于零的线性表,记为:L=(  )。

非空表记为:L=(a1, a2 , …, ai-1, ai , …, an)。

其中,ai(1≤i≤n)称为数据元素;下角标 i 表示该元素在线性表中的位置或序号

线性表的特征

n个数据元素的有限序列

数据结构——线性表-码农小屋

线性结构的基本特征为:

  • 集合中必存在唯一的一个“第一元素”
  • 集合中必存在唯一的一个 “最后元素”
  • 除最后元素在外,均有 唯一的后继;
  • 除第一元素之外,均有 唯一的前驱
  • 元素个数n—表长度,n=0空表
  • 1<i<n时 –ai的直接前驱是ai-1,a1无直接前驱 –ai的直接后继是ai+1,an无直接后继
  • 元素同构,且不能出现缺项

线性表的抽象数据类型定义

ADT List

Data: D={ ai | ai ∈ElementSet, i=1, 2, …, n, n≥0}

Relation: R={ <ai-1, ai >| ai-1, ai∈D, i=2, …, n, }

Operation:

  • InitList(&L):初始化线性表,构造一一个空的线性表L。
  • DestroyList(&L):销毁线性表,释放线性表L占用的内存空间。
  • ListEmpty(L):判断线性表是否为空表,若L为空表,则返回真,否则返回假。
  • ListLength(L):求线性表的长度,返回L中元素的个数。
  • DispList(L):输出线性表,当线性表L不为空时顺序显示L中各结点的值域。
  • GetElem(L,i,&e):求线性表中某个数据元素值,用e返回L中第i(1≤i≤n)个元素的值。
  • LocateElem(L,e):按元素值查找,返回L中第一个值域与e相等的元素的序号,若这样的元素不存在,则返回值为0。
  • ListInsert(&L,i,e):插人数据元素,在L的第i(1≤i≤n+1)个位置插人-一个新的元素e,L的长度增1。
  • ListDelete(&L,i,&e):删除数据元素,删除L的第i(1≤i≤n)个元素,并用e返回其值,L的长度减1。

endADT

线性表的作用主要体现在两个方面,当个线性表实现后,程序员可以直接使用它来存放数据,即作为存放数据的容器,另外程序员可以直接使用它的基本运算来完成更复杂的功能。线性表基本运算是与求解问题相关的,上面列出的9个基本运算是线性表最常用的功能,在实际应用中大家可以根据需要进行增减。

实例

例题一

假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即:线性表中的数据元素即为集合中的成员。现要求一个新的集合A=A∪B。

上述问题可演绎为:

要求对线性表作如下操作:扩大线性表 LA,将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。

操作步骤:

1.从线性表LB中依次查看每个数据元素;

GetElem(LB, i)→e

2.依次在线性表LA中进行查访;

LocateElem(LA, e, equal( ))

3.若不存在,则插入之。

ListInsert(LA, n+1, e)

void union(List &La, List Lb)
{   
    La_len = ListLength(La);    //求线性表的长度
    Lb_len = ListLength(Lb);
    for (i = 1;  i <= Lb_len;  i++)
    {
        GetElem(Lb, i, e); //取Lb中第i个数据元素赋给e
        if(!LocateElem(La, e, equal())) 
            ListInsert(La, ++La_len, e);
            //La中不存在和 e 相同的数据元素,则插入之
    }
}

例题二

双表归并——试将非递减的有序表 La 和 Lb 归并为另一个有序表 Lc。

思路:

先设LC为空表,再按下法将LA或LB中的元素逐个插入到LC中:设置三个指针i、j和k分别指向LA、LB和LC中的当前元素a、b和c,LC中的当前元素c按如下方法确定:

数据结构——线性表-码农小屋
void MergeList(List La, List Lb, List &Lc)
{
    //本算法将非递减的有序表 La 和 Lb 归并为 Lc
    InitList(Lc);  // 构造空的线性表 Lc
    i = j = 1;    k = 0;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    while((i <= La_len) && (j <= Lb_len)) {
        //La 和 Lb 均非空,i = j = 1, k = 0
        GetElem(La, i, ai);    
        GetElem(Lb, j, bj);
        if (ai <= bj) {
            ListInsert(Lc, ++k, ai);  ++i; 
        } else {
            ListInsert(Lc, ++k, bj);  ++j; }
    }
    while (i <= La_len) { 
        // 当La不空时
        GetElem(La, i++, ai);   
        ListInsert(Lc, ++k, ai); }
    while (j <= Lb_len) { 
        // 当Lb不空时
        GetElem(Lb, j++, bj);
        ListInsert(Lc, ++k, bj); }
}      

0
独家记忆
相关文章
算法时间复杂度和空间复杂度简介
计算机的基本组成
HTTP协议报文结构
线性表的顺序和链式存储结构
数据结构——绪论
评论 (0)
再想想
独家记忆作者
一个爱学习的程序猿
28文章 2评论 29获赞
文章推荐
ZIP Pro 3 – 文件压缩分享加密管理套件
2月前
Uninstall Tool-专业的软件卸载工具
3月前
Speccy:优秀的硬件检测工具
4月前
CleanMyPC-专为 Windows打造的清理工具
4月前
Internet Downloader Manager-一款专业的Win下载工具
4月前
Wise Care 365-Windows 系统清理和加速工具
4月前
新鲜事
新Mac太牛:在电脑上运行iPhone、iPad的软件、游戏
2月前
自从苹果M1芯片发布之后,使用这颗芯片的Mac电脑,就被大家认为是有史以来最强的Mac,因为这颗小米的芯片,在性能上已经打败了苹果使用的最高端的i9芯 ...[阅读全文]
苹果发布会总结:一个芯片,三款产品!苹果这把棋下得可真深
2月前
北京时间11月11日凌晨2点,苹果在圣何塞召开了本年度最后一场发布会。在这次发布会上,苹果推出了基于ARM架构的全新M1自研处理器。 ...[阅读全文]
荣耀命运落定:救了自己,也救华为
2月前
华为出售荣耀一事终于落槌。 ...[阅读全文]
发布会停不下来,苹果下月发布新Mac
3月前
今年的苹果有些与众不同,往年只开一次秋季发布会,今年在九月十月连开两场。 ...[阅读全文]
iPhone 12 开启 5G 续航锐减,苹果回应
3月前
对于今年的 iPhone 12 来说,除了回归直角边框设计之外,最大的亮点就是 5G 了。 ...[阅读全文]
华为Mate40正式发布
3月前
定位高端旗舰的华为Mate40系列共发布四款新机:华为Mate40(6.5英寸)、华为Mate40 Pro(6.76英寸)、华为Mate40 Pro+ ...[阅读全文]
更多
  • 专题
  • 文章
  • 友情链接
  • 留言板
Copyright © 2020-2021 码农小屋. 苏ICP备20033168号