线性表

线性表的定义和基本操作

InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。

DestroyList(&L)：销毁操作。销毁线性表，并释放线性表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的长度，即L中数据元素的个数。

PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。

Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

Tips：

①对数据的操作（记忆思路） —— 创销、增删改查

②C语言函数的定义 —— <返回值类型> 函数名 (<参数1类型> 参数1，<参数2类型> 参数2，……)

③实际开发中，可根据实际需求定义其他的基本操作

④函数名和参数的形式、命名都可改变（Reference：严蔚敏版《数据结构》）

⑤什么时候要传入引用“&” —— 对参数的修改结果需要“带回来”

线性表的顺序表示

逻辑上相邻的两个元素物理上也相邻

InitList(&L)的使用

静态分配

#include 
#define MaxSize 10

// 定义结构体
typedef struct {
    int data[MaxSize];
    int length;
} SqList;

// 顺序表初始化函数
void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;//将所有元素的初始值默认设置为0
        //这一步其实可以省略，但是省略之后，有可能受到内存中"脏数据"的影响
    }
    L.length = 0; //因为此时还没存入元素，所以是零，上面只是初始化，不算存入

}

// 主函数
int main() {
    SqList L;
 InitList(L);
 for (int i = 0; i < MaxSize; i++) {
  printf("data[%d]=%d\n", i, L.data[i]);
 }
    return 0;
}

动态分配

#include 
#include 
# define InitSize 10

// 定义结构体
typedef struct {
 // Elem Type *data;
 int *data;
 int MaxSize;
 int length;
}SeqList;

// 初始化函数
void InitList(SeqList &L) {
 L.data = (int *)malloc(InitSize*sizeof(int));
 L.MaxSize = InitSize;
 for (int i = 0; i < L.MaxSize; i++) {
  L.data[i] = i+1;//为了后续动态扩展操作效果，将所有元素存入值
 }
 L.length = 10;
}

// 增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
 int *p = L.data;
 L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
 for (int i = 0; i < L.length; i++) {
  L.data[i] = p[i];
 }
 L.MaxSize = InitSize + len;
 free(p);
}

// 主函数
int main(){
 SeqList L;
 InitList(L);
 IncreaseSize(L, 5);
 for (int i = 0; i < L.MaxSize; i++) {
  printf("data[%d]=%d\n", i, L.data[i]);
 }
 return 0;
}

顺序表的特点：

①随机访问，即可以在 O(1) 时间内找到第 i 个元素。②存储密度高，每个节点只存储数据元素 ③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高） ④插入、删除操作不方便，需要移动大量元素

顺序表的基本操作——插入

ListInsert(&L,i,e)的使用

#include 
#define MaxSize 10 //定义最大长度

//定义结构体
typedef struct{
 int data[MaxSize]; //用静态的数组存放数据元素
 int length; // 顺序表的当前长度
}SqList;  // 顺序表的类型定义

// 初始化函数
void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;//将所有元素的初始值默认设置为0
        //这一步其实可以省略，但是省略之后，有可能受到内存中"脏数据"的影响
    }
    L.length = 0; //因为此时还没存入元素，所以是零，上面只是初始化，不算存入
}

//插入元素函数
bool ListInsert(SqList &L, int i, int e){
 if(i<1||i>L.length+1){
  return false;  // 容错，判断i是否有效
 }
 if(L.length>=MaxSize){
  return false;  //容错，当前存储空间已满，不能插入
 }
 for(int j=L.length; j>=i; j--){
  L.data[j]=L.data[j-1]; // 将i之后的元素依次后移
 }
 L.data[i-1]=e;  //将位置i放入e
 L.length++; //长度+1
 return true;
}

// 主函数
int main(){
 SqList L; //声明一个顺序表
 InitList(L); //初始化顺序表
 for (int i = 0; i < 5; i++) {
  L.data[i] = i+1;//为了后续插入操作效果，将前5个元素存入值
  L.length++;
 }
 if (ListInsert(L, 100, 3)){
  printf("插入成功\n");
 }
 else {
  printf("插入失败\n");
 }
 for (int i = 0; i < L.length; i++) {
  printf("data[%d]=%d\n", i, L.data[i]);
 }
}

插入操作的时间复杂度

O(n)

顺序表的基本操作——删除

ListDelete(&L,i,&e)的使用

#include 
#define MaxSize 10 //定义最大长度

//定义结构体
typedef struct{
 int data[MaxSize]; //用静态的数组存放数据元素
 int length; // 顺序表的当前长度
}SqList;  // 顺序表的类型定义

// 初始化函数
void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;//将所有元素的初始值默认设置为0
        //这一步其实可以省略，但是省略之后，有可能受到内存中"脏数据"的影响
    }
    L.length = 0; //因为此时还没存入元素，所以是零，上面只是初始化，不算存入
}

//插入元素函数
bool ListDelete(SqList &L, int i, int &e){
 if(i<1||i>L.length+1){
  return false;  // 容错，判断i是否有效
 }
 e = L.data[i-1];
 for(int j=i; j  L.data[j-1]=L.data[j]; // 将i之后的元素依次前移
 }
 L.length--; //长度-1
 return true;
}

// 主函数
int main(){
 SqList L; //声明一个顺序表
 InitList(L); //初始化顺序表
 for (int i = 0; i < 5; i++) {
  L.data[i] = i+1;//为了后续插入操作效果，将前5个元素存入值
  L.length++;
 }
 int e = -1;
 if (ListDelete(L, 3, e)){
  printf("删除成功[%d]\n", e);
 }
 else {
  printf("删除失败\n");
 }
 for (int i = 0; i < L.length; i++) {
  printf("data[%d]=%d\n", i, L.data[i]);
 }
}

删除操作的时间复杂度

O(n)

顺序表的按位查找

GetElem(L,i)的使用

#include 
#include 
#define InitSize 10 //顺序表的初始长度
typedef struct{
 int *data; //指示动态分配数组的指针
 int MaxSize; //顺序表的最大容量
 int length; //顺序表的当前长度
} SeqList; //顺序表的类型定义（动态分配方式）

// 初始化函数
void InitList(SeqList &L) {
 L.data = (int *)malloc(InitSize*sizeof(int));
 L.MaxSize = InitSize;
 for (int i = 0; i < L.MaxSize; i++) {
  L.data[i] = i+1; //所有的值给定i+1
  L.length++;
 }
}

// 按位查找
int GetElem(SeqList L, int i){
 return L.data[i-1]; 
}

// 主函数
int main() {
    SeqList L;
 InitList(L);
 printf("get data[%d]\n", GetElem(L, 3));
 for (int i = 0; i < L.MaxSize; i++) {
  printf("data[%d]=%d\n", i, L.data[i]);
 }
 
    return 0;
}

按位查找的时间复杂度

O(1)

顺序表的按值查找

LocateElem(L,e)的使用

#include 
#include 
#define InitSize 10 //顺序表的初始长度
typedef struct{
 int *data; //指示动态分配数组的指针
 int MaxSize; //顺序表的最大容量
 int length; //顺序表的当前长度
} SeqList; //顺序表的类型定义（动态分配方式）

// 初始化函数
void InitList(SeqList &L) {
 L.data = (int *)malloc(InitSize*sizeof(int));
 L.MaxSize = InitSize;
 for (int i = 0; i < L.MaxSize; i++) {
  L.data[i] = i*i; //所有的值给定i+1
  L.length++;
 }
}

// 按位查找
int LocateElem(SeqList L, int e){
 for(int i=0;i  if(L.data[i]==e)
  return i+1; //数组下标为i的元素值等于e，返回其位序i+1
 }
 return 0; 
}

// 主函数
int main() {
    SeqList L;
 InitList(L);
 printf("e的位序[%d]\n", LocateElem(L, 9));
 for (int i = 0; i < L.MaxSize; i++) {
  printf("data[%d]=%d\n", i, L.data[i]);
 }
 
    return 0;
}

按值查找的时间复杂度

O(n)