数据结构--线性表&顺序表示（上）

1. 线性表

1.1线性表的定义

线性表是一种具有相同数据类型的n（n>=0）个数据元素的有限序列，若用L命名线性表，则其一般表示为：L = (a1, a2, … , ai, ai+1, … , an)
特点：数据元素同类型、有限、有序

Q:所有整数按递增次序排序是线性表吗？
A：不是，因为整数的数量是无限的

• 表长: 线性表中数据元素的数量n。
• 空表: 表长为零的线性表。
• 位序: 数据元素在线性表中的位置，从1开始
  • 注意： 位序是从1开始的，而程序中的数组下标是从0开始的。
• 表头元素: 线性表中的第一个元素。
• 表尾元素: 线性表中的最后一个元素。
• 直接前驱: 除了第一个元素外，每个元素有且只有一个直接前驱。
• 直接后继: 除了最后一个元素外，每个元素有且只有一个直接后继。

1.2. 线性表的基本操作

操作类型: 对数据结构的操作一般包括创建、销毁、增、删、改、查

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

参数的引用(&)注意点
如果需要对参数的修改结果带回，需传入引用类型的参数（C++特性）。

Q:为什么要实现对数据结构的基本操作?
A: 1.团队合作: 定义的数据结构需方便他人使用， 通过封装基本操作实现。
2.避免重复工作: 将常用操作封装成函数，降低出错风险。

• 无引用类型: 修改结果不带回，main函数中的变量x值不变。

#include <stdio.h>

void test(int x){//无引用
    x=1024;
    printf("Inside the test function x=%d\n",x);
}

int main() {
    int x=5;
    printf("Before calling the test function x=%d\n",x);
    test(x);
    printf("After calling the test function x=%d\n",x);
    return 0;
}

• 引用类型: 修改结果带回，main函数中的变量x值改变

#include <stdio.h>

void test(int &x){//加了引用符合&
    x=1024;
    printf("Inside the test function x=%d\n",x);
}

int main() {
    int x=5;
    printf("Before calling the test function x=%d\n",x);
    test(x);
    printf("After calling the test function x=%d\n",x);
    return 0;
}

2. 顺序表

2.1 顺序表的定义

顺序存储: 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。
顺序表: 用顺序存储的方式实现的线性表。元素的逻辑顺序与其存储的物理顺序相同，因此可通过起始地址和元素大小（sizeof）计算出任意元素的存放地址。

1.静态分配的顺序表结构：

# define Maxsize 10 //定义最大长度
typedef int ElemType;//重命名int
typedef struct {
    ElemType data[Maxsize];//用静态数组存放元素
    int length;//顺序表的当前长度
}Sqlist;//顺序表的类型定义

• 静态分配: 使用数组的定义方式实现顺序表，数组长度固定，一旦确定就不可改变。
• 数据类型: 数据元素的类型用ElemType表示，可以是int型或自定义的struct类型，具有通用性。

初始化顺序表

#include <stdio.h>
#include <stdlib.h>
# define Maxsize 5 //定义最大长度
typedef int ElemType;//重命名int
typedef struct {
    ElemType data[Maxsize];//用静态数组存放元素
    int length;//顺序表的当前长度
}Sqlist;//顺序表的类型定义

//初始化顺序表
void InistLsit(Sqlist &l){
    for(int i=0;i<Maxsize;i++){
        l.data[i]=0;//将所有元素都设置成为初始值
    }
    l.length=0;//顺序表长度设置成为0
}
int main(){
    Sqlist l;//声明一个顺序表
    InistLsit(l);//初始化
    return 0;
}

注意：顺序表初始化时，必须将length设为0，以确保访问有效数据元素。设置数据元素默认初始值可省略。
2.动态分配的顺序表结构：

• 动态分配方式: 采用动态分配来实现顺序表，需要定义一个指针指向顺序表的第一个数据元素，并增加变量MaxSize表示顺序表的最大容量，以及变量length记录顺序表的当前长度。

# define InitSize 10 //默认最大长度
typedef int ElemType;//重命名int
typedef struct {
    ElemType *data;//指示动态分配的指针
    int Maxsize;//顺序表的最大容量
    int length;//顺序表的当前长度
}Seqlist;

• 内存管理: 使用C语言中的malloc和free函数来动态申请和释放内存空间。malloc函数会申请一整片连续的内存空间，并返回一个指向这片空间起始地址的指针，需要将其强制转换为定义的数据元素类型指针。

//申请空间
void InitList(Seqlist &l){
    l.data=(ElemType*) malloc(InitSize*sizeof (ElemType));
    l.length=0;
    l.Maxsize=InitSize;
}

• 扩展: 当顺序表需要扩展时，可以定义一个新的指针p指向原数据空间，使用malloc函数申请更大的内存空间，将原数据复制到新空间，并更新data指针和Max Size值，最后使用free函数释放原内存空间。

//增加动态数组的长度
void IncreaseSize(Seqlist &l,int len){
    int *p=l.data;
    l.data=(ElemType*) malloc((l.Maxsize+len)*sizeof (ElemType));
    for(int i=0;i<l.length;i++){
        l.data[i]=p[i];//将数据赋值到新区域
    }
    l.Maxsize=l.Maxsize+len;
    free(p);
}

注意事项

• 指针转换: malloc函数返回的指针需要强制转换为定义的数据元素类型指针。
• 内存管理: 动态分配的内存空间在使用完毕后需要使用free函数释放，以避免内存泄漏。
• 性能考虑: 动态分配虽然灵活，但涉及数据复制，时间开销较大。在性能敏感的场景下需要权衡使用。

顺序表的特点：

• 随机访问: 顺序表支持随机访问，即可以在O(1)时间内找到第i个元素。原因在于顺序表中数据元素连续存放，只需知道首个元素地址，即可计算出其他元素地址。
• 存储密度高: 每个节点只存储数据元素本身，无需额外的存储空间来存储指针或链接信息。
• 拓展容量不方便: 顺序表的拓展容量不方便。静态分配方式无法拓展容量；动态分配方式虽然可以拓展，但需要复制数据到新区域，时间复杂度较高。
• 插入、删除不方便: 顺序表进行插入和删除操作时，需要移动大量的元素，效率较低。