文档章节

线性表

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
海淀
程序员

暂无文章

GO冒泡,二分查找

package mainimport("fmt")func main() {var arr [5]int = [5]int{11,13,9,2,25}maopao(&arr)fmt.Println("arr = ", arr) //[2 9 11 13 25]findIndex := binaryFind(&arr, 0......

汤汤圆圆
26分钟前
1
0
工作2年半跳槽面试阿里,成功拿到offer,凭什么?

2015年刚毕业的我,进入了一家小小的公司实习工作,在学校学了三年软件开发的我,还是想去寻找一份互联网行业的工作,这样更能学以致用发挥自己的特长。一直到18年三月份,我辞掉已有的工作,...

java知识分子
31分钟前
1
0
讲述下:Linux的10个最危险的命令

导读 Linux命令行佷有用、很高效,也很有趣,但有时候也很危险,尤其是在你不确定你自己在正在做什么时候。这篇文章将会向你介绍十条命令,但你最好不要尝试着去使用。 当然,以下命令通常都...

问题终结者
35分钟前
1
0
分库分表后如何部署上线?

引言 我们先来讲一个段子 面试官:“有并发的经验没?” 应聘者:“有一点。” 面试官:“那你们为了处理并发,做了哪些优化?” 应聘者:“前后端分离啊,限流啊,分库分表啊。。” 面试官:...

Java烂猪皮
40分钟前
1
0
Redis源码阅读笔记-快速列表

快速列表 快速列表(quicklist)是由压缩列表(ziplist)组成的一个双向链表,链表中,每一个节点都是以压缩列表(ziplist)的结构保存。 在 Redis3.2 后加入的新数据结构,在列表键中取代了双向链...

Jian_Ming
58分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部