`
XiangdongLee
  • 浏览: 86928 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

【线性表】(List)

阅读更多
本文围绕以下三个部分展开:

一、线性表(List)
二、顺序存储结构
三、链式存储结构






一、线性表(List)

        1. 概念

        线性表:0个或多个数据元素的有限序列。(像线一样性质的表)

            线性表的每个数据元素的类型都是相同的。

            A. 是一个序列。(元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。)

            B. 元素个数是有限的。



            类比:幼儿园小朋友按次序排队。


        2. 线性表的抽象数据类型

        (1)基本操作:



        抽象数据类型定义如下:




        (2)复杂的个性化操作

        例题:union操作(实现两个线性表集合A和B的并集操作)

        思想:把存在在集合B中但不存在在A中的数据元素插入到A中即可。即:循环集合B中的每个元素,判断当前元素是否存在A中。若不存在,则插入到A中即可。





二、顺序存储结构

        1. 顺序存储

        指用一段地址连续的存储单元依次存储线性表的数据元素。




        2. 顺序存储方式

        在内存中找了块地儿,通过占位符的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。

        使用一维数组来实现顺序存储结构。即:把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。


        3. 顺序存储结构代码和三个属性






        4. 地址计算方法

        存储器中每个存储单元都有自己的编号,称为地址。

        (1)数据元素的序号和存放它的数组下标之间的对应关系:



        (2)假设一个数据元素占c个存储单元,则第i+1个数据元素的存储位置和第i个数据元素的存储位置的关系:



        第i个数据元素的存储位置和第1个数据元素的存储位置的关系:





        (3)随机存取结构:可以随时算出线性表中任意位置的地址,存取时间复杂度均为O(1),具有这样特点的存取结构称为随机存取结构。


        5. 获得元素的操作(GetElem):将线性表L中第i个位置元素值返回。





        6. 插入某个数据元素








        7. 删除某个数据元素









        8. 优缺点





三、链式存储结构



        1. 特点:

        用一组任意的存储单元存储线性表的数据元素。这组存储单元可以连续,也可以不连续。意味着,这些数据元素可以存放在内存中未被占用的任意位置。


        2. 数据域、指针域、指针/链、结点






        3. 头结点、头指针

        (1)头指针:链表中第一个结点的存储位置。

        链表最后一个结点的指针为空(NULL/"^")

        (2)头结点:为了更方便地对链表进行操作,在单链表的第一个结点前附设的一个结点。

        数据域可以不存储任何信息,也可以存储如线性表长度等附加信息。

        指针域存储指向第一个结点的指针。



        (3)二者的异同




        4. 分类

        链式存储结构又有不同形式,分为:单链表、静态链表、循环链表和双向链表。






整理时重点参考:《大话数据结构》程杰著
0
1
分享到:
评论

相关推荐

    通信电源蓄电池组容量性充放电试验三措一案.docx

    5G通信行业、网络优化、通信工程建设资料。

    铁塔维护检测手段.docx

    5G通信行业、网络优化、通信工程建设资料

    通信设备安装施工组织方案.doc

    5G通信、网络优化与通信建设

    299-教育行业信息化与数据平台建设分享.pptx

    299-教育行业信息化与数据平台建设分享.pptx

    手写数字和字母数据集binaryalphadigs.mat

    手写数字和字母数据集binaryalphadigs.mat

    变电站视频监控解决方案.doc

    5G通信行业、网络优化、通信工程建设资料

    PEMFC电堆输出电压模型,可计算效率、输出功率、电流、消耗功率以及等效内阻

    PEMFC电堆输出电压模型,可计算效率、输出功率、电流、消耗功率以及等效内阻

    创建型 结构型 设计型设计模式相关知识

    1、 设计思路 1、 创建型设计模式 创建型设计模式主要“关注对象的创建”。 1. 单例模式 单例模式:能不用就不用 ,他的目的就是为了让一个类只创建一个实例。 用法:把对象的创建权限关闭,提供一个人公开的静态方法,实现静态方法后将实例存放于静态的字段中,方法中返回。 单例模式会长期持有一个对象不会被释放,而普通实例不用就会被释放(当然必须是GC之后才会被释放)。 单例用途;数据临时存储的地方如静态字典,数据库连接池、线程池、IOC容器实例。   1.1懒汉式 设置构造函数为私有的,避免其他外部类可以对其实例化, 创建静态类来存储实例。 在静态方法中创建实例,避免多个线程同时调用方法,我们可以加线程锁, 在方法中使用双判断语句:最外层判断是为了提高运行速率,检查如果静态字段中已经存在实例了就可以直接return;第二层判断是避免创建多个对象实例。 1.2饿汉式1 静态构造函数:由CLR保证,静态构造函数只会在启动程序时候,由CLR自行创建。并且只会创建一次,相比较于懒汉式创建的更早,并且不需要担心会

    《通信工程概预算》模拟试题2.docx

    5G通信行业、网络优化、通信工程建设资料

    毕业设计:Java项目之jsp高校规章制度管理系统(源码 + 数据库 + 说明文档)

    论文目录: 第二章 需求分析与系统总体设计 - 5 - 2.1java的特点 - 5 - 2.2技术可行性 - 5 - 2.3可靠性和安全性特点 - 6 - 2.4系统总体设计 - 6 - 2.5JSP技术介绍 - 7 - 2.5.1 什么是JSP - 7 - 2.5.2 JSP技术特点 - 7 - 2.5.3 JSP开发WEB的几种方式 - 8 - 第三章 数据库的设计与实现 - 9 - 3.1数据库的需求分析 - 9 - 3.2数据库的逻辑设计 - 10 - 3.3 数据库的结构创建 - 10 - 第四章 后台系统和数据库的配置 - 13 - 4.1后台服务器配置 - 13 - 4.2后台数据库的配置 - 13 - 4.3后台全局配置文件 - 13 - 第五章 前端网络页面的开发与设计 - 14 - 5.1登录页面 - 14 - 5.2 管理员用户页面 - 15 - 5.3 注册用户页面 - 16 - 5.4主页面 - 17 - 5.5用户注册页面 - 18 - 5.6 规章制度管理页面 - 18 - 第六章 系统的安全性 - 19 - 6.1 session和cookie的安

    ONU、分光器验收规范.doc

    5G通信行业、网络优化、通信工程建设资料。

    99-煤矿安全生产标准化基本要求及评分方法.pdf

    99-煤矿安全生产标准化基本要求及评分方法.pdf

    node-v12.22.6-sunos-x64.tar.xz

    Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。

    475现场通讯器用户手册

    475现场通讯器用户手册

    node-v7.7.0.tar.xz

    Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。

    600A钳形电流表使用手册

    600A钳形电流表使用手册

    常见宏基站认识和设计讲解.pptx

    5G通信、网络优化与通信建设

    node-v12.16.3-sunos-x64.tar.xz

    Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。

    数据中心机房供电需求分析.pptx

    5G通信、网络优化与通信建设

    Binomial Self-compensation

    Binomial Self-compensation for Motion Error in Dynamic 3D Scanning

Global site tag (gtag.js) - Google Analytics