文档章节

线性表

Syzhen
 Syzhen
发布于 2016/11/18 16:22
字数 1059
阅读 2
收藏 0
点赞 0
评论 0

   一、线性结构的基本特征:

    线性结构是一个数据元素点有序 集合。

   二、   线性表的逻辑结构:拥有唯一的一个表头元素和唯一的一个表尾元素,表头元素没有前驱,表尾元素没有后继,其他元素有唯一的直接前驱与后继。

    抽象数据类型定义:

ADT List{
    数据对象: D={ ai | ai ∈ ElemSet, i =1, 2, … …, n, n≥0 }
    数据关系: R1 = { < ai-1 , ai > | ai-1 , ai ∈ D,  i =2, … …, n } 
    
    基本操作:
    InitList (&L )      操作结果:构造一个空的线性表L.

    DestoryList (&L)    初始条件:线性表L已存在。 
                        操作结果:销毁线性表L。
    ClearList (&L)      初始条件:线性表L已存在。
                        操作结果:将L重置为空表。
    ListEmpty (L)       初始条件:线性表L已存在。      
                        操作结果:若L 为空表,则返回TRUE,否则返回  FALSE。
    ListLength (L)      初始条件:线性表L已存在。    
                        操作结果:返回L中数据元素个数。
    GetElem ( L,i,&e)   初始条件:线性表L已存在,1≤i≤ListLength(L)+1。    
                        操作结果:用e返回L中第i个数据元素的值。
    LocateElem ( L,e, compare() )      初始条件:线性表L已存在,compare()是判定函数。 
                                       操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在,则返回值0。
    PriorElem ( L, cur_e, &pre_e )     初始条件:线性表L已存在。  
                                       操作结果:若cur_e是L的数据元素且不是第1个,则用pre_e返回它的前驱,否则操作失败。 
    NextElem ( L, cur_e, &next_e )     初始条件:线性表L已存在。  
                                       操作结果:若cur_e是L的数据元素且不是最后一个,则用next_e返回它的后继,否则操作失败
    ListInsert ( &L, i, e )            初始条件:线性表L已存在,1≤i≤ListLength(L)+1。 
                                       操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。
    ListDelete( &L, i, &e )            初始条件:线性表L已存在且非空,1≤i≤ ListLength(L)。 
                                       操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1。 
    ListTraverse ( L,visit())          初始条件:线性表L已存在。 
                                       操作结果:依次对L的每个数据元素调用函数 visit()。一旦visit()失败,则操作失败。
}ADT List

    三、线性表的存储结构

            线性表的存储结构有顺序存储结构和链式存储结构,前者称为顺序表,后者称为链表。

        (1):顺序表

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

        (2)链表

            在链表存储中,每个节点不仅包含所存元素本身的信息,还包含元素之间逻辑关系信息,即前驱节点包含后继结点的地址信息,这样可以通过前驱节点中的地址信息找到后继结点的位置。

        (3)两种结构的比较

            顺序表:1、能随机访问 2、占有连续的存储空间    3、存储空间分配为静态分配

            链表:   1、不能随机访问    2、存储空间利用率比顺序表低    3、各结点散落分布在存储器中

4、可以动态分配空间大小

            顺序表做插入操作要移动多个元素,而链表无需。

         链表的5种形式:1、单链表2、双链表 3、循环单链表、4循环双链表、5、静态链表

         

    四、线性表的基本操作

        

线性表的结构定义
#define maxSize 100     //定义线性表的大小

//顺序表的结构定义
typedef struct
{
   int data[maxSize];   //存放数据元素的数组
   int length;          //存放顺序表的长度
}SqlList;               //顺序表类型定义


//单链表结点定义

typedef struct LNode
{
   int data;            //结点的数据域
   struct LNode *next;  //指向后继结点的指针
}LNode;                 //定义单链表结点类型


//双链表的结点定义
typedef struct DLNode
{
   int data;
   struct DLNode *prior;//指向前驱结点的指针
   struct DLNode *next; //指向后继结点的指针
}DLNode;

 

© 著作权归作者所有

共有 人打赏支持
Syzhen
粉丝 0
博文 10
码字总数 9901
作品 0
海淀
程序员

暂无文章

大数据基础知识,大数据学习,涉及的知识点

一、什么是大数据 一种规模大到在获取、存储、管理、分析方面大大超出了传统数据库软件工具能力范围的数据集合,具有海量的数据规模、快速的数据流 转、多样的数据类型和价值密度低四大特征。...

董黎明
18分钟前
0
0
Linux CentOS 7上安装极点五笔

话说几天前在新买的惠普笔记本上成功地安装了Linux CentOS 7操作系统、Nvidia Quandro P600驱动程序及X Window,并在VMware下安装Red Hat教学环境,彻底跳出Windows的苦海,但仍然有一件事不...

大别阿郎
30分钟前
3
0
2018年7月20日集群课程

一、集群介绍 集群,简单地说是指一组(若干个)相互独立的计算机,利用高速通信网络组成一个较大的计算机服务系统,每个集群节点(即集群中的每台计算机)都是运行各自服务的独立服务器。 ...

人在艹木中
32分钟前
0
0
spark开发机中调试snappy

目的 在Idea中的点击运行,使spark可以直接读取snappy 自己编译hadoop,以支持snappy的压缩。 自己编译的目的就是要得到支持snappy文件读写的动态链接库。如果可以在网上下载,可以跳过自行编...

benny周
50分钟前
0
0
centos7 安装docker

1,查看系统版本 cat /etc/redhat-release 2,安装gcc yum -y install gccyum -y install gcc-c++ 3,卸载旧版本 yum remove docker \ docker-client \ ......

暗中观察
51分钟前
0
0
rabbitmq学习记录(七)交换机Exchange-topic

实现功能:一条消息发送给多个消费者 交换机模式:topic 相比于direct匹配模式,匹配routingKey时,topic模式下不仅支持完全匹配,还支持两种特殊的匹配方式 #:可以匹配一个或多个字符 *:可...

人觉非常君
51分钟前
0
0
[译]为什么(要使用)GNU Affero GPL?

#为什么(要使用)GNU Affero GPL? 作者信息:Copyright © 2010, 2013, 2014, 2015 Free Software Foundation, Inc. This page is licensed under a Creative Commons Attribution-NoDeriv......

ICE冰焰火灵X
52分钟前
0
0
apollox-lua 示例

这个项目是从openn2o里迁出的项目。 示例地址 apollox-lua.js 是把js翻译成lua的库。支持两种不同的模态, 在编译工程的时候使用 可以用作openresty的代码翻译, 即用js代替lua。在web模式可...

钟元OSS
今天
0
0
Ubuntu系统笔记 Linux系统

Ubuntu 16.04.3 Ubuntu系统,不适用yum, yum软件源都是RPM软件包,不是deb格式软件包,所以你即便是在Ubuntu上面安装了yum,也是完全用不了的。 不推荐 apt好于yum apt install screen...

阿锋zxf
今天
0
0
Java面试中,遇到这类面试题最吃亏!

从你接触 Java开发到现在,你对 Java最直观的印象是什么呢?是它宣传的 “Compile once, run anywhere”,还是目前看已经有些过于形式主义的语法呢?你对于 Java平台到底了解到什么程度?请你...

Java大蜗牛
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部