文档章节

线性表

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

暂无文章

数据库

数据库架构 数据库架构可以分为存储文件系统和程序实例两大块,而程序实例根据不同的功能又可以分为如下小模块。 1550644570798 索引模块 常见的问题有: 为什么要使用索引 什么样的信息能成...

一只小青蛙
今天
4
0
PHP常用经典算法实现

<? //-------------------- // 基本数据结构算法 //-------------------- //二分查找(数组里查找某个元素) function bin_sch($array, $low, $high, $k){ if ( $low <= $high){ $mid = int......

半缘修道半缘君丶
昨天
5
0
GIL 已经被杀死了么?

本文原创并首发于公众号【Python猫】,未经授权,请勿转载。 原文地址:https://mp.weixin.qq.com/s/8KvQemz0SWq2hw-2aBPv2Q 花下猫语: Python 中最广为人诟病的一点,大概就是它的 GIL 了。...

豌豆花下猫
昨天
5
0
git commit message form

commit message一般包括3部分:Header、Body、Footer。 <type>(<scope>):<subject>blank line<body>blank line<footer> header是必需的,body、footer可以省略。 header中type、subject......

ninjaFrog
昨天
5
0
聊聊Elasticsearch的CircuitBreakerService

序 本文主要研究一下Elasticsearch的CircuitBreakerService CircuitBreakerService elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/indices/breaker/CircuitBreakerService.ja......

go4it
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部