线性表的概念、结构与基本操作

线性表概览
服务器君一共花费了266.648 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

什么是线性表?线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑结构简单,便于实现和操作。因此,线性表这种数据结构在实际应用中是广泛采用的一种数据结构。

结构

线性表是一种常用的数据结构,以下介绍线性表及其顺序存储,并对栈和队列及它们的顺序实现给出了详细的设计描述。

在实际应用中,线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性,因此,掌握这些特殊线性表的特性,对于数据运算的可靠性和提高操作效率都是至关重要的。

线性表是一个线性结构,它是一个含有n≥0个结点的有限序列,对于其中的结点,有且仅有一个开始结点没有前驱但有一个后继结点,有且仅有一个终端结点没有后继但有一个前驱结点,其它的结点都有且仅有一个前驱和一个后继结点。一般地,一个线性表可以表示成一个线性序列:k1,k2,…,kn,其中k1是开始结点,kn是终端结点。 

线性表是一个数据元素的有序(次序)集。

特征

线性结构的基本特征为:

  1. 集合中必存在唯一的一个“第一元素”;
  2. 集合中必存在唯一的一个 “最后元素” ;
  3. 除最后一个元素之外,均有 唯一的后继(后件);
  4. 除第一个元素之外,均有 唯一的前驱(前件)。

由n(n≥0)个数据元素(结点)a1,a2,…,an组成的有限序列。数据元素的个数n定义为表的长度。当n=0时称为空表。

 常常将非空的线性表(n>0)记作:(a1,a2,…an)。数据元素ai(1≦i≦n)只是一个抽象的符号,其具体含义在不同的情况下可以不同。

线性表的基本操作:

  1. MakeEmpty(L) 这是一个将L变为空表的方法
  2. Length(L) 返回表L的长度,即表中元素个数
  3. Get(L,i) 这是一个函数,函数值为L中位置i处的元素(1≤i≤n)
  4. Prev(L,i) 取i的前趋元素
  5. Next(L,i) 取i的后继元素
  6. Locate(L,x) 这是一个函数,函数值为元素x在L中的位置
  7. Insert(L,i,x)在表L的位置i处插入元素x,将原占据位置i的元素及后面的元素都向后推一个位置
  8. Delete(L,p) 从表L中删除位置p处的元素
  9. IsEmpty(L) 如果表L为空表(长度为0)则返回true,否则返回false
  10. Clear(L)清除所有元素
  11. Init(L)同第一个,初始化线性表为空
  12. Traverse(L)遍历输出所有元素
  13. Find(L,x)查找并返回元素
  14. Update(L,x)修改元素
  15. Sort(L)对所有元素重新按给定的条件排序
  16. strstr(string1,string2)用于字符数组的求string1中出现string2的首地址

结构特点

线性表具有如下的结构特点:

  1. 均匀性:虽然不同数据表的数据元素可以是各种各样的,但对于同一线性表的各数据元素必定具有相同的数据类型和长度。
  2. 有序性:各数据元素在线性表中的位置只取决于它们的序与,数据元素之前的相对位置是线性的,即存在唯一的“第一个“和“最后一个“的数据元素,除了第一个和最后一个外,其它元素前面均只有一个数据元素直接前驱和后面均只有一个数据元素(直接后继)。

在实现线性表数据元素的存储方面,一般可用顺序存储结构和链式存储结构两种方法。链式存储结构将在本网站线性链表中介绍,本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈.队列和串也是线性表的特殊情况,又称为受限的线性结构。

附一道选择题:

下列哪个不是线性表(d):A. 链表 B. 队列 C.栈 D.关联数组

线性表的推广

时间有序表、排序表、和频率有序表都可以看做是线性表的推广。如果按照结点到达结构的时间先后,作为确定结点之间关系的,这样一种线性结构称之为时间有序表。例如,在红灯前停下的一长串汽车,最先到达的为首结点,最后到达的为尾结点;在离开时最先到达的汽车将最先离开,最后到达的将最后离开。这些汽车构成理一个队列,实际上就是一个时间有序表。栈和队列都是时间有序表。频率有序表是按照结点的使用频率确定它们之间的相互关系的,而排序表是根据结点的关键字值来加以确定的。

本文地址:http://www.nowamagic.net/librarys/veda/detail/1793,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1793

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《JavaScript高级程序设计(第2版)》 尼古拉斯·泽卡斯(Nicholas C.Zakas) (作者), 李松峰 (译者), 曹力 (译者)

《JavaScript高级程序设计(第2版)》在上一版基础上进行了大幅度更新和修订,融入了近几年来JavaScript应用发展的最新成果,几乎涵盖了所有需要理解的重要概念和最新的JavaScript应用成果。从颇具深度的JavaScript语言基础到作用域(链),从引用类型到面向对象编程,从极其灵活的匿名函数到闭包的内部机制,从浏览器对象模型(BOM)、文档对象模型(DOM)到基于事件的Web脚本设计,从XML(E4X)到Ajax及JSON,从高级前端开发技术到前沿的客户端存储,从最佳编程实践到即将成为现实的API,直至JavaScript未来的发展,全景式地展示了JavaScript高级程序设计的方方面面。

更多计算机宝库...