线性表
博客专区 > Syzhen 的博客 > 博客详情
线性表
Syzhen 发表于1年前
线性表
  • 发表于 1年前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

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

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

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

    抽象数据类型定义:

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;

 

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 4
码字总数 9901
×
Syzhen
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: