文档章节

线性表

Syzhen
 Syzhen
发布于 2016/11/18 16:22
字数 1059
阅读 2
收藏 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
海淀
程序员
私信 提问

暂无文章

使用正则表达式实现网页爬虫的思路详解

网页爬虫:就是一个程序用于在互联网中获取指定规则的数据。这篇文章主要介绍了使用正则表达式实现网页爬虫的思路详解,需要的朋友可以参考下 网页爬虫:就是一个程序用于在互联网中获取指定规...

前端小攻略
15分钟前
0
0
vue中锚点的三种方法

第一种: router.js中添加 mode: 'history', srcollBehavior(to,from,savedPosition){ if(to.hash){ return {selector:to.hash } } } 组件: <template><div><ul class="li......

peakedness丶
16分钟前
0
0
记一次面试最常见的10个Redis"刁难"问题

导读:在程序员面试过程中Redis相关的知识是常被问到的话题。作为一名在互联网技术行业打击过成百上千名的资深技术面试官,本文作者总结了面试过程中经常问到的问题。十分值得一读。 Redis在...

小刀爱编程
今天
20
0
TiDB Lab 诞生记 | TiDB Hackathon 优秀项目分享

本文由红凤凰粉凤凰粉红凤凰队的成员主笔,他们的项目 TiDB Lab 在本届 TiDB Hackathon 2018 中获得了二等奖。TiDB Lab 为 TiDB 培训体系增加了一个可以动态观测 TiDB / TiKV / PD 细节的动画...

TiDB
今天
5
0
当区块链遇到零知识证明

本文由云+社区发表 当区块链遇到零知识证明 什么是零知识证明 零知识证明的官方定义是能够在不向验证者任何有用的信息的情况下,使验证者相信某个论断是正确的。这个定义有点抽象,下面笔者举...

腾讯云加社区
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部