【数据结构】线性表--顺序表（二）

1、什么是线性表

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

​ L = （a₁，a₂，…，a_i，a_i+1，…，a_n）

如图所示：

每个数据类型都相同，也意味着每个数据元素所占空间一样大

重要概念：

1. a_i是线性表中的“第i个”元素线性表中的位序
2. a₁是表头元素；a_n是表尾元素
3. 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

2、线性表的基本操作

常用操作：

• InitList(&L):初始化表。构造一个空的线性表L，分配内存空间
• DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
• ListInsert(&Li,e):插入操作。在表L中的第i个位置上插入指定元素e。
• ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
• LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素
• GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

其他常用操作：

• Length(L):求表长。返回线性表L的长度，即L中数据元素的个数
• PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。
• Empty(L):判空操作。若L为空表，则返回true，否则返回false。

Tips:

1. 数据元素的位序是从1开始，而程序数组下标是0开始
2. 在实际开发中，可根据实际需求定义其他的基本操作

3、顺序表

3.1、顺序表的定义

​ 顺序表指的是用顺序存储的方式来实现线性表的顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

3.2、顺序表的实现方式：静态分配

#define MaxSize 10		//定义最长长度
typedef struct{
    ElemType data[MaxSize];	//用静态的数组存放数据
    int length;				//顺序表当前长度
}SqList;		//顺序表的类型定义(静态分配方式)
1
2
3
4
5

**问题：**如果数组数组存满了呢？

• 直接放弃治疗，顺序表的表长刚开始就确定后，无法更改（存储空间是静态的）

**思考：**如果刚开始就声明一个很大的内存空间呢？存在什么问题？

• 过于浪费

3.3、顺序表的实现方式：动态分配

#define InitSize 10		//顺序表的初始长度
typedef struct{
    ElemType *data;	//指示动态分配数组的指针
    int MaxSize;	//顺序表的最大容量
    int length;		//顺序表的当前长度
}SeqList;		//顺序表的类型定义(动态分配方式)
1
2
3
4
5
6

3.4、顺序表的特点

1. 随机访问，即可以在o(1)时间内找到第i个元素
2. 存储密度高，每个节点只存储数据元素
3. 拓展容量不方便(即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高)

3.5、顺序表的初始化与插入操作

初始化顺序表

#define MaxSize 50
typedef int ElemType; //让顺序表存储其他类型元素时，可以快速改变代码
//静态分配
typedef struct {
    ElemType data[MaxSize];
    int length; //顺序表长度
}SqList;
1
2
3
4
5
6
7

顺序表插入

//顺序表插入，因为L会改变，所以要引用
bool ListInsert(SqList &L,int pos,ElemType elemType){
    //判断pos是否合法
    if(pos <= 1 || pos >= L.length + 1){
        return false;
    }
    //如果顺序表满了，也不能进行插入
    if(L.length == MaxSize){
        return false;
    }

    //将元素依次往后面移动
    for (int i = L.length; i >= pos; i--) {
        L.data[i] = L.data[i-1];
    }

    L.data[pos-1] = elemType; //存入数据
    L.length++;       //顺序表长度+1

    return true;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

打印顺序表

//打印顺序表
void PrintList(SqList L){
    for (int i = 0; i < L.length; ++i) {
        printf("%3d",L.data[i]);
    }
}
1
2
3
4
5
6

在主函数中调用

//顺序表的初始化与插入
int main() {
    SqList L;  //定义一个顺序表
    bool result;

    L.data[0] = 1;  //放置元素
    L.data[1] = 2;
    L.data[2] = 3;

    L.length = 3; //设置顺序表元素为3

    result = ListInsert(L,2,2);

    if(true == result){
        printf("success");
    } else{
        printf("error");
    }

    PrintList(L);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.6、顺序表的删除与查询

删除元素

//删除顺序表中的元素
bool ListDelete(SqList &L,int pos,ElemType &del){

   //判断删除元素位置是否合法
   if(pos < 1 || pos > L.length ){
       return false;
   }

   del = L.data[pos-1];  //保存删除元素的值

   //从当前下标开始，往前移动
   for (int i = pos;  i < L.length; i++) {
       L.data[i - 1] = L.data[i];
   }

   L.length--;
   
   return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

查询元素

//查询元素位置
int LocateElem(SqList L,ElemType elemType){
    //遍历顺序表
    for (int i = 0; i < L.length; ++i) {
        if(L.data[i] == elemType){  //如果元素相同
            return i+1; //返回下标+1
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10