数据结构考研复习第二章线性表

Posted on   |   更新于 | In |

复习要点

  1. 熟练掌握线性表的各种基本操作（基于两种存储结构），注重积累和培养动手能力。
  2. 考场上应尽力表达出算法的思想和步骤，不必拘泥于细节。

线性表的定义和基本操作

线性表的定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时，该线性表是一个空表。若用L命名线性表，则其一般表示为：

L=(a1,a2,···,ai,ai+1,···,an)
  • a1是表头元素，唯一
  • an是表尾元素，唯一
  • 除第一个元素外，每个元素有且只有一个直接前驱
  • 除最后一个元素外，每个元素有且仅有一个直接后继

线性表的特性：

  1. 表中的元素个数有限
  2. 表中元素具有逻辑上的顺序性，在序列中各元素的排序有先后顺序
  3. 表中元素都是数据元素，每个元素都是单个元素
  4. 表中元素的数据类型都相同，每个元素占有相同大小的存储空间
  5. 表中元素具有抽象性，即仅讨论元素之间的逻辑关系，而不考虑元素究竟表示什么内容

注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。

线性表的基本操作

InitList(&L)：初始化表。构造一个空的线性表。
Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i)：按位查找操作。获取表中第i个位置的元素的值。
ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
PrintList(L)：输出操作。按前后顺序输出表L中的所有顺序。
Empty(L)：判空操作。若L为空表，则返回True，否则返回False。
DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

注意：

  1. 基本操纵的实现取决于采用哪种存储结构，存储结构不同，算法的实现也不同。
  2. “&”表示C++中的引用。若传入的变量是指针变量，且在函数体内要对传入的指针进行改变，则会用到指针变量的引用型。在C中采用指针的指针也可以达到相同的效果。

线性表的顺序表示

顺序表的定义

线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元依次存储性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

注意：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。

数组的分配方式：

  1. 静态分配，数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序崩溃。
1
2
3
4
5
6
//静态分配
#define MaxSize 50
typeddf struct{
    ElemType data[MaxSize];
    int length;
}SqList;
  1. 动态分配，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。
1
2
3
4
5
6
7
8
9
10
//动态分配
#define InitSize 100
typedef struct{
    ElemType *data;
    int Maxsize,length;
}SeqList;
//C的初始动态分配语句
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
//C++的初始动态分配语句
L.data=new ElemType[InitSize];

注意：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。

顺序表特点：

  1. 最主要是：随机访问，通过首地址和元素序号可在时间O(1)内找到指定的元素。
  2. 存储密度高，每个结点只存储数据元素。
  3. 逻辑上相邻的元素物理上相邻，所以插入和删除操作需要移动大量元素。

顺序表上基本操作的实现

  1. 插入操作
1
2
3
4
5
6
7
8
9
10
11
bool ListInsert(SqList &L, int i, ElemType e){
    //实现将元素e插入到顺序表L中第i个位置
    if(i<1||i>L.length+1) return false; //判断i的范围是否有效
    if(L.length>=MaxSize) return false; //当前存储空间已满，不能插入
    for (int j=L.length;j>=i;j--){ //将第i个元素及之后的元素后移
        L.data[i]=L.data[j-1];
    }
    L.data[i-1]=e; //在位置i处放入e
    L.length++; //线性表长度加1
    return true;
}

时间复杂度：

最好情况是：表尾插入，O(1)；
最坏情况是：表头插入，O(n)；
平均情况是：中间任意位置插入的平均值，O(n)；
  1. 删除操作
1
2
3
4
5
6
7
8
9
10
bool ListDelete(SqList &L, int i,Elemtype &e){
    // 本算法实现删除顺序表L中第i个位置的元素
    if(i<1||i>L.length) return false; //判断i的范围是否有效
    e=L.data[i-1]; //将被删除的元素赋值给e
    for(int j=i;j<L.length;j++){ //将第i个位置后的元素前移
        L.data[j-1]=L.data[j]; //线性表长度减1
    }
    L.length--;
    return true;
}

时间复杂度：

最好情况：删除表尾元素，O(1)；
最坏情况：删除表头元素，O(n);
平均情况：任意位置插入，平均情况是O(n);
  1. 按值查找
1
2
3
4
5
6
7
8
int LocateElem(SqList L,ElemType e){
    //本算法实现查找顺序表值为e的元素，如果查找成功，返回元素位序，否则返回0
    int i;
    for(i=0;i<L.length;i++){
        if(L.data[i]==e) return i+1; //下标为i的元素值等于e，返回其位序i+1
    }
    return 0; //退出循环，说明查找失败
}

时间复杂度：

最好情况：元素在表头，O(1);
最坏情况：元素在表尾，O(n);
平均情况：O(n);