面向云技术架构 - 痴者工良

  • 首页
  • 工良写的电子书
    • kubernetes 教程
    • 从 C# 入门 Kafka
    • 多线程和异步
    • 动态编程-反射、特性、AOP
    • 表达式树
  • 本站文章导航
  • 隐私政策
愿有人陪你颠沛流离
遇到能让你付出的事物或者人,都是一种运气。
能遇到,就该珍惜。或许你们最终没能在一起,但你会切实地感受到力量。
正因为这样,那段相遇才变得有价值,才没有辜负这世间的每一段相遇。
  1. 首页
  2. 计算机科学与软件工程
  3. 数据结构
  4. 正文

003线性表的定义和基本操作

2021年4月11日 1618点热度 0人点赞 0条评论
内容纲要

学习要求

在前面提到过,数据结构的逻辑结构有线性结构和非线性结构,线性结构的元素是具有前趋和后续的 1:1 的关系。非线性结构有集合、图、树。

本篇讨论的线性表是线性结构,要求掌握线性表的定义和基本操作。

线性表的定义和基本操作

【1】线性表的定义

线性表示例:

A、B、C、D ... Z 等26个字母组成的英文字母表。

线性表(Linear List)可以表示由 n(n≧0) 个数据元素(结点)组成的有限序列,其中元素个数 n 表示为表的长度。当 n = 0 时,称为空线性表。

【2】线性表的种类

线性表是数据结构中的一种逻辑结构,而在存储结构中,线性表有顺序存储结构和链式存储结构,前者称为顺序表,后者称为链表。

(1)顺序表

把线性表中的每个元素按照其逻辑顺序,依次存储到指定的存储位置开始的一块连续存储空间中。

顺序表具有两个特性,第一个是随机访问特性,只需要知道它的位置(结点序号)就可以马上找到它。第二个特性是顺序表要求占用连续的存储空间。

顺序表做插入操作时需要移动多个元素。

(2)链表

在链表存储结构中,每个结构不仅包含所存元素的信息,还包含元素之间的逻辑关系的信息。链表还有单链表、双链表、循环单链表、循环双链表、静态链表。

链表不支持随机访问,必须在从 HEAD 开始查找;并且链表个每个结点必须划出一些空间来存储指向下一个结点位置的指针,链表中的结点可以散落在内存的任何位置。

下图为单链表。

node-in-linked-list

[图:https://www.studytonight.com/data-structures/linear-linked-list]

测试

1.将l6个数据元素的线性表按顺序存储方式存储在数组中,若第一个元素的存储地

址是l000,第6个元素的存储地址是1040,则最后一个元素的存储地址是

A.1112 B.1120 C.1124 D.1128


2.线性表是一种由 n 个数据元素组成的数据结构,n 的取值是:

A.0或任意一个正整数

B.非负整数

C.任意一个正整数或∞

D.某个正整数


3.线性表的存储方式中,能够随机存取表中任一元素的存储结构是 ____ 。


4.下列选项中,属于顺序存储结构优点的是

A.插入运算方便 B.删除运算方便

C.存储密度大 D.方便存储各种逻辑结构


5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,

则下列存储结构中,最节省运算时间的是

A.单链表 B.仅有头指针的单循环链表

C.双向链表 D.仅有尾指针的单循环链表

注:后面文章介绍;


6.用不带头结点的单链表存储队列,在进行删除运算时

A.仅修改头指针 B.仅修改尾指针

C.头、尾指针一定都要修改 D.头、尾指针可能都要修改

注:后面文章介绍;


答案:1,B;2,A;3,顺序存储结构 ;4,C;5,D;6,D;

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: 分析 描述 算法
最后更新:2021年4月11日

痴者工良

高级程序员劝退师

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

文章目录
  • 学习要求
  • 线性表的定义和基本操作
  • 测试

COPYRIGHT © 2022 whuanle.cn. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

粤ICP备18051778号

粤公网安备 44030902003257号