线性表的深度理解

  • 以下哪个选项对线性表的描述是正确的?a. 班级中同学的友谊关系b.
    公司中的上下级关系c. 冬天图书排队占座关系d. 花名册上名字之间的关系
  • 正确答案是

 

一、定义:

线性表是具有像线一样的性质的表,是一个序列,元素间是有顺序的,如果存在多个元素的话,第一个元素无前驱,后一个元素无后继,其他每个元素都有且只有一个前驱和后继,线性表强调有限性

线性表的元素个数n(n>=0)定义为线性表的长度,当n=0时,成为空表。

非空表中每个元素都有一个确定的位置,如果a1是第一个元素,a7是第七个元素,1成为a1元素在线性表中的位序。

线性表最典型的例子就是星座和生肖了。星座中都是白羊座第一,双鱼座收尾,当中的每个星座有且仅有一个前驱和后继,而且个数是有限的12个;生肖中以鼠开头以猪结尾。每个星座和生肖的位置(位序)是固定的,白羊座和鼠是1,金牛座和牛是2……

要成为线性表中的元素比较有相同的数据类型,不同的数据类型是不能组成线性表的。人和衣服就不能组成线性表。

复杂的线性表允许每个元素有若干个数据项组成,例如按照学号排序的学生组成了一个线性表,每个学生都可以有姓名,性别,出生年月等多个数据项。

线性表的定义

  • 线性表是零个或多个数据元素的集合
  • 线性表中的数据元素之间是有顺序的
  • 线性表中的数据元素个数是有限的
  • 线性表中的数据元素的类型必须相同

第五课:线性表的本质 

线性表(List)是零个或是多个数据元素的集合 

注意(这些要求有点儿类似于数组,但是和数组是有区别的,不要混淆): 

  1. 线性表中的数据元素之间是有序的 

  2. 线性表中的数据元素的个数是有限的 

  3. 线性表中的数据元素的类型必须相同
     
    线性表的专业定义:  

线性表是具有相同类型的n(n≥0)个数据元素的有限序列  (a1, a2, …. an)

an是表项, n表示长度
 
  线性表的性质: 

  1. a0是线性表的第一个元素,只有一个后继;

  2. an是线性表的最后一个元素,只有一个前驱; 

  3. 除了a0和an之外的其他元素ai,既有前驱,也有后继;

  4. 线性表能够逐项访问和顺序存取   

二、线性表的抽象数据类型

线性表的性质

  • a0为线性表的第一个元素,只有一个后继
  • an为线性表的最后一个元素,只有一个前驱
  • 除a0和an外的其他元素ai,既有前驱,又有后继
  • 线性表能够逐项访问和顺序存取

第六课:线性表的相关操作 

常用操作: 

  1. 创建线性表

  2. 销毁线性表

  3. 清空线性表

  4. 在线性表中插入元素 

  5. 从线性表中删除元素

  6. 获取线性表中某个元素的位置

  7. 获取线性表的长度
     
      问题:如何在程序中表达和使用线性表?
     
     
    线性表在程序中表现为一种特殊的数据类型,相应的操作,在程序中表现为一组函数
     
      示例:

    List List_Create();
    void List_Destory(List ist);
    void List_Clear(List list);
    int List_Insert(List list, ListNode node, int pos);
    ListNode List_Delete(List list, int pos);
    ListNode ListGet(List list, int pos);
    int List_Length(List list);

  问题:

  1. 线性表的各个函数是如何实现的?

  2. 有几种线性表的实现方式呢?

  3. 每种实现方式的优缺点是什么?     

2.1什么是线性表

线性表的数据对象元素为{a1,a2,a3,……,an},每个元素的类型均为DataType。其中,除了第一个元素a1外,每个元素都有前驱;除了最后一个元素an外,每个元素都有后继。数据元素间的关系是一对一的关系。

幼儿园的小朋友按照固定的顺序排队,并且长期使用这个顺序,每个小朋友就对应一个元素,所以小朋友组成的顺序队列就叫线性表。

小结

  • 线性表是数据元素的有序并且有限的集合
  • 线性表中的数据元素必须是类型相同
  • 线性表可用于描述“队列类型”关系的问题

第七课:线性表的顺序存储结构(数组的方式实现) 

顺序存储的定义: 
线性表的顺序存储结构,是用一段地址连续的存储单元依次存储线性表的数据元素
— 这有些类似于数组 

例如:从地址0xAABBCCDD开始存储线性表的n个元素: 

a1 。。。。ak 。。。。。。an

  所以,在C语言中,线性表的顺序存储结构可以用一维数组来实现

  需要厘清的要点:

  1. 存储空间的起始位置

  2. 线性表的最大容量:MAXSIZE

  3.线性表的当前长度:length

  示例:

  #define MAXSIZE 20
  typedef struct _tag_List
  {
   char node[MAXSIZE];
   int length; 
  } List;

  相关操作的具体实现: 

2.2线性表的操作

  • InitList(*L):

初始化操作,建立一个空的线性表。

老师让小朋友按照一定顺序排队的过程就是线性表的创建与初始化的过程。

  • ListEmpty(L):

若线性表为空,返回true,否则返回false。

  • ClearList(L):

将线性表清空。

没经验的小朋友排好队后,老师发现有高有矮很不整齐,队伍很难看,于是让小朋友解散重新排列,这就是一个线性表重置为空的操作。

  • GetElem(L,i,*e):

将线性表L中的第i个元素值返回给e。

  • LocateElem(L,e):

在线性表中查找与e相等的元素,如果查找成功返回该元素的序号,查找失败返回0;

  • ListInsert(*L,i,e):

在线性表第i个位置插入新元素e

  • ListDelete(*L,i,e):

删除线性表第i个位置,并用e返回

  • ListLength(L):

获取线性表元素个数

使用以上几个基本操作实现求
线性表A和线性表B的并集,思路大致为,查找B中的每个元素判断是否在A中,如果不在则插入。

void unionL(List *La,List Lb){
    int La_length,Lb_length,i;
    //声明相同的数据元素e
    ElemType e;
    La_length = ListLength(La);
    Lb_length = ListLength(Lb);
    //遍历Lb所以元素,在La中查找,没有就插入
    for(i=1; i<=Lb_length; i++){
        //取出Lb中第i个元素给e
        GetElem(Lb,i,e);
        //Lb中如果没找到e就插入
        if(!LocateElem(La,e)){
            ListInsert(La, ++La_length, e);
        }
    }
}

线性表的一些常用操作

  • 创建线性表
  • 销毁线性表
  • 清空线性表
  • 将元素插入线性表
  • 将元素从线性表中删除
  • 获取线性表中某个位置的元素
  • 获取线性表的长度

1. 获取线性表中的元素的操作 

1.1 判断线性表是否合法 

1.2 判断位置是否合法

1.3 直接通过数组下标的方式获取元素

示例代码:

  char Get(List list, int pos)
  {
   char ret = -1;
   //判断线性表和位置是否合法
   if((list != NULL) && (0 <= pos) && (pos < list->length))
   {
    //获取元素
    ret = list->node[pos];
   }
   return ret;
  }

三、线性表的物理结构—顺序存储结构

线性表操作的实现

  • 线性表在程序中表现为一种特殊的数据类型
  • 线性表的操作在程序中的表现为一组函数

2. 插入元素算法 

2.1 判断线性表时候合法 

2.2 判断插入位置是否合法 

2.3 把最后一个元素一直到插入位置的元素顺序后移一个位置 

2.4 将新元素插入 

2.5 线性表长度加1 

示例代码:

  int Insert(List list, char c, int pos)
  {
   // 1 判断线性表时候合法
   int i = 0;
   int ret = (list != NULL);

   // 2 判断插入位置是否合法
   ret = ret && (list->length + 1 <= MAXSIZE);
   ret = ret && (0 <= pos);

   if(ret)
   {
    if(pos >= list->length)
    {
     pos = list->length;
    }
    // 3 把最后一个元素一直到插入位置的元素顺序后移一个位置
    for(i=list->legth; i>pos; i--)
    {
     list->node[i] = list->node[i-1];
    }
    // 4 将新元素插入
    list->node[i] = c;
    // 5 线性表长度加1
    list->length++;
   }
   return ret;
  }

3.1 定义

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

发表评论

电子邮件地址不会被公开。 必填项已用*标注