【数据结构和算法】7 线性表2

爱被打了一巴掌 2022-04-14 05:42 183阅读 0赞

# 线性表的抽象数据类型 #

**抽象数据类型**：就是把数据类型和相关操作捆绑在一起。

**线性表的创建和性表初始化**

小甲鱼组织大家春游，鱼油们按照规律排成一对，并且是长期使用这样的顺序排队，大家只需要记住自己的前驱鱼油是谁就行了。那么这个考虑和安排的过程就是**线性表的创建和性表初始化**。

**线性表的重置**

一开始小加油没有经验，鱼油们按照名字的第一个字母就行排列，结果发现队伍里面有高有矮，不美观，于是就让鱼友们重新解散按照从矮到高的顺序排列。这就是线性表的重置为表的过程。

**线性表删除数据**

排好队后，发现黑夜同学由于闹肚子来不了春游，那么由原来排在黑夜后面的小生开始往前挪。

**线性表插入数据**

黑夜同学下午康复了，回来了，黑夜同学说记得是排在斜阳后面的，所以让斜阳后面的小生开始一个一个往后退，黑夜就可以插回到原来的位置上了。

**线性表的访问**

活动开始不久，隔壁来了美眉旅游团。导游说你们队伍里的第八个那个家伙总是调戏我们队里的小花，他叫什么名字？小甲鱼查看了一下名单，奥，他叫迷途。

--------------------

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

•ADT 线性表（List）

•Data

线性表的数据对象集合为\{a1,a2,…,an\}，每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

•Operation

InitList(\*L): 初始化操作，建立一个空的线性表L。

ListEmpty(L): 判断线性表是否为空表，若线性表为空，返回true，否则返回false。

ClearList(\*L): 将线性表清空。

GetElem(L,i,\*e): 将线性表L中的第i个位置元素值返回给e。

LocateElem(L,e): 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。

ListInsert(\*L,i,e): 在线性表L中第i个位置插入新元素e。

ListDelete(\*L,i,\*e): 删除线性表L中第i个位置元素，并用e返回其值。

ListLength(L): 返回线性表L的元素个数。

•endADT

--------------------

# 线性表应用 #

对于不同的应用，线性表的基本操作是不同的。上面的操作是最基本的操作，对于实际涉及到的问题，需要将上述的操作进行不同的组合来实现。

例如：实现并集操作。

A =A∪B

分析：完成并集操作需要遍历循环B中所有元素，判断当前的元素是否存在A中，若不存在，则插入A中即可。

需要用到下面的操作：

ListLength(L): 返回线性表L的元素个数。

LocateElem(L,e): 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。

GetElem(L,i,\*e): 将线性表L中的第i个位置元素值返回给e。

ListInsert(\*L,i,e): 在线性表L中第i个位置插入新元素e。

参考程序：

// La表示A集合，Lb表示B集合。
    void unionL(List *La, list Lb)
    {
        int La_len, Lb_len, i;
    
        ElemType e;
        La_len = ListLength(*La);//求线性表的长度
        Lb_len = ListLength(Lb);
    
        for( i=1; i <= Lb_len; i++ )
        {
            GetElem(Lb, i, &e);//获取第i个元素，赋值给e
            if( !LocateElem(*La, e) )//判断是否存在当前元素e
            {
                ListInsert(La, ++La_len, e);
            }
        }
    }

--------------------

★finished by songpl ,2018.11.25

发表评论取消回复

表情：

评论列表（有 0 条评论，183人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构与算法_01_线性表】线性表

数据结构与算法线性表定义 ● 线性表具有相同数据类型\\（同类型）\\的n个数据元素有限序列 ● 三方面 ● 定义 `逻辑结构` ●

素颜马尾好姑娘i/ 2024年03月17日 13:46/ 0 赞/ 16 阅读

相关数据结构——线性表（2）

上接数据结构——线性表（1）上文中介绍了线性表的顺序存储结构和单链表的介绍与代码实现，接下来，继续介绍线性表的链式存储循环链表在座的各位都很年轻，不

怼烎@/ 2023年10月08日 13:29/ 0 赞/ 10 阅读

相关 Java数据结构和算法：线性表

线性表的定义线性表(linear-list)是最常用最简单的一种数据结构。一个线性表是n (n≥0)个相同类型数据元素的有限序列。记为： L= (a1, a2 , …

不念不忘少年蓝@/ 2022年07月13日 09:38/ 0 赞/ 156 阅读

相关数据结构与算法线性表

数据结构与算法线性表一、简述记-线性表。线性表是具有相同特性的数据元素的一个有限序列。线性表的顺序存储结构--顺序表--把线性

骑猪看日落/ 2022年05月17日 22:13/ 0 赞/ 256 阅读

相关【数据结构和算法】8 线性表：线性表的顺序存储结构

线性表的顺序存储结构线性表有两种物理存储结构：顺序存储结构和链式存储结构。物理上的存储方式事实上就是在内存中找个初始地址，然后通过占位的形式，把一定的内存空

柔光的暖阳◎/ 2022年04月21日 14:34/ 0 赞/ 246 阅读

相关【数据结构和算法】7 线性表2

线性表的抽象数据类型抽象数据类型：就是把数据类型和相关操作捆绑在一起。线性表的创建和性表初始化小甲鱼组织大家春游，鱼油们按照规律排成一对，并且是长期使用这样的顺

爱被打了一巴掌/ 2022年04月14日 05:42/ 0 赞/ 184 阅读

相关【数据结构和算法】6 线性表1

线性表的定义线性表像是排队一样，具有像线一样的性质。官方定义：线性表（List），是有零个或多个数据元素组成的有限序列；关于线性表几个关键的地方：（1）首先

叁歲伎倆/ 2022年04月14日 04:07/ 0 赞/ 138 阅读

相关数据结构与算法-线性表

概要一图胜千言线性表基本概念线性表顺序存储顺序存储-查询

拼搏现实的明天。/ 2022年03月22日 13:48/ 0 赞/ 263 阅读

相关数据结构与算法——线性表—顺序表（顺序线性表）

线性表（linear list）是最简单，也是最基本的一种线性数据结构，它有两种存储表示方法：顺序表和链表。它的主要基本操作是插入，删除和查找。 3.1 顺序表（顺序线性表

喜欢ヅ旅行/ 2022年03月16日 12:54/ 0 赞/ 316 阅读

相关数据结构与算法---2（线性表）

线性表线性表：零个或多个数据元素的有限序列 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6L

﹏ヽ暗。殇╰゛Y/ 2022年03月09日 12:20/ 0 赞/ 274 阅读