2.1顺序表

第二章 线性表

1. 线性表的定义和基本操作

1.1 定义

​ 具有相同类型数据类型的n&＃xff08;n>&＃61;0&＃xff09;个数据元素的有限序列&＃xff0c;其中n为表长&＃xff0c;当n &＃61; 0时线性表是一个空表。若用L命名线性表&＃xff0c;表示为&＃xff1a;L &＃61; &＃xff08;a₁,a₂…&＃xff0c;a_n&＃xff09;

C语言中如何确定一个数据元素的大小

sizeof(ElemType)

1.2 线性表的特点

• 表中个数有限
• 表中元素具有逻辑上的顺序性&＃xff0c;表中元素有其先后次序
• 表中元素都是数据元素&＃xff0c;每个元素都是单个元素
• 表中元素的数据类型都相同&＃xff0c;每个元素占有相同大小的存储空间
• 表中元素具有抽象性&＃xff0c;只考虑元素间逻辑关系&＃xff0c;不考虑元素表示什么内容

1.3 若需要直接改变x的值要用到&

#include
void test(int x){x &＃61; 1024;printf("test函数内部x &＃61; %d\n",x);
}int main(){int x &＃61; 1;printf("调用test前x &＃61; %d\n",x); //调用test前x &＃61; 1test(x); //test函数内部x &＃61; 1024printf("调用test后x &＃61; %d\n",x); //调用test后x &＃61; 1
}


造成未赋值却有值是因为&＃xff0c;在调用test时&＃xff0c;在内存中复制了一个x使得test函数中的x值给到复制的x的位置&＃xff0c;x的数值未发生改变

#include
//使用&直接对内存中的x的值进行改变&＃xff0c;C&＃43;&＃43;支持&＃xff0c;C语言不支持
void test(int & x){x &＃61; 1024;printf("test函数内部x &＃61; %d\n",x);
}int main(){int x &＃61; 1;printf("调用test前x &＃61; %d\n",x); //调用test前x &＃61; 1test(x); //test函数内部x &＃61; 1024printf("调用test后x &＃61; %d\n",x); //调用test后x &＃61; 1024
}


1.4 线性表的基本操作

InitList(&L)&＃xff1a;初始化表&＃xff08;构造一个空的线性表&＃xff09;

Length(L)&＃xff1a;求表长&＃xff08;返回线性表L的长度&＃xff09;

LocateElem(L,e)&＃xff1a;按值查找操作&＃xff08;在表L中查找特定关键字值的元素&＃xff09;

GetElem(L,i)&＃xff1a;按位查找操作&＃xff08;获取表中第i个位置的元素的值&＃xff09;

ListInsert(&L,i,e)&＃xff1a;插入操作&＃xff08;在表L中的第i个位置上插入指定元素e&＃xff09;

ListDelete(&L,i,&e)&＃xff1a;删除操作&＃xff08;删除表L中第i个位置的元素&＃xff0c;并用e返回删除元素的值&＃xff09;

PrintList(L)&＃xff1a;输出操作&＃xff08;按照先后顺序输出线性表L的所有元素值&＃xff09;

Empty(L)&＃xff1a;判空操作

DestroyList(&L)&＃xff1a;销毁操作&＃xff08;销毁线性表&＃xff0c;并释放线性表L所占用的内存空间&＃xff09;

2. 顺序表的实现

2.1 静态分配

#include //定义线性表的最大长度
#define MaxSize 10typedef struct {//用静态数组存放数据元素int data[MaxSize];//顺序表的长度int length;
}SqList;//基本操作——初始化一个顺序表
void InitList(SqList &L){for (int i &＃61; 0;i}int main() {//声明一个顺序表SqList L;//初始化顺序表InitList(L);//打印顺序表&＃xff0c;这里最好使用顺序表的基本操作来访问各个数据GetElem(L,i)for(int i&＃61;0;i<10;i&＃43;&＃43;){printf("data[%d]&＃61;%d\n",i,L.data[i]);}
}


由于内存中会有遗留数据&＃xff0c;所以使得顺序表中会出现非0数据

2.2 动态分配

#include
#include
//顺序表的初始长度
#define InitSize 10typedef struct {//指示动态分配数组的指针int *data;//顺序表的最大容量int MaxSize;//顺序表的当前长度int length;
}SqList;void InitList(SqList &L){//用malloc函数申请存储空间L.data &＃61; (int *)malloc(InitSize*sizeof(int));L.length &＃61; 0;L.MaxSize &＃61; InitSize;
}//增加动态数组的长度
void IncreaseSize(SqList L,int len){int *p &＃61; L.data;L.data &＃61; (int *)malloc((L.MaxSize&＃43;len)*sizeof(int));for (int i &＃61; 0; i < L.length; &＃43;&＃43;i) {//将数据复制到新区域L.data[i] &＃61; p[i];}//顺序表最大长度增加lenL.MaxSize &＃61; L.MaxSize&＃43;len;//释放原来存储空间free(p);
}int main(){//声明一个顺序表SqList L;//初始化顺序表InitList(L);IncreaseSize(L,5);return 0;
}


• 动态申请内存空间&＃xff08;malloc函数&＃xff09;

​ malloc函数返回一个指针&＃xff0c;需要强制转换数据类型

​ malloc函数会在内存中创建一整片连续的空间

//malloc函数的参数需要指明分配多大的内存空间
L.data &＃61; (ElemType *)malloc(siazeof(ElemType)*InitSize);


• 释放内存空间&＃xff08;free函数&＃xff09;

free();


2.3 顺序表的特点

• 随机访问&＃xff0c;可以在O(1)时间内找到第i个元素
• 存储密度高&＃xff0c;每个节点只存储数据元素

• 拓展容量不方便&＃xff08;即便采用动态分配的方式实现&＃xff0c;拓展长度的时间复杂度也比较高&＃xff09;
• 插入删除不方便&＃xff0c;需要移动大量元素

2.4 顺序表的基本操作

2.4.1 插入

• ListInsert(&L,i,e)&＃xff1a;插入操作&＃xff0c;在表L中的第i个位置上插入指定元素e

#define MaxSize 10
typedef struct{ElemType data[10];int length;
}SqList;bool ListInsert(SqList &L,int i,ElemType e){//确定i是否在有效范围内if (i<1||i>L.length&＃43;1){return false;}//判断存储空间是否满if (L.length>&＃61;MaxSize){return false;}//将第i个元素及之后的元素后移for (int j &＃61; L.length; j >&＃61;i ; j--) {L.data[j] &＃61; L.data[j-1];}//在i的位置处放入eL.data[i-1] &＃61; e;L.length&＃43;&＃43;;return true;
}int main(){SqList L;InitList(L);ListInsert(&L,3,3);
}


• 最深层次循环语句的执行次数与问题规模n的关系[问题规模n &＃61; L.leng

  • 最好情况&＃xff1a;数据插入到表尾&＃xff0c;不需要移动元素 i &＃61; n&＃43;1; 时间复杂度 &＃61; O&＃xff08;1&＃xff09;

  • 最坏情况&＃xff1a;新元素插入到表头&＃xff0c;需要将原有的n个元素全部向后移动 i &＃61; 1&＃xff0c;循环n次&＃xff1b;时间复杂度O(n)

  • 平均情况&＃xff1a;假设新元素插入到任何一个位置的概率相同&＃xff0c;即i &＃61; 1,2,……,length&＃43;1的概率都是p &＃61; 1/n&＃43;1,当i&＃61;1时&＃xff0c;循环n次&＃xff0c;i&＃61;2时&＃xff0c;循环n-1次……i&＃61;n&＃43;1时&＃xff0c;循环0次

    平均循环次数 &＃61; np&＃43;(n-1)p&＃43;(n-2)p&＃43;……1*p &＃61; n/2,所以平均时间复杂度&＃61;O&＃xff08;n&＃xff09;

2.4.2 删除

• ListDelete(&L,i&e)&＃xff1a;删除操作&＃xff0c;删除表中第i个位置的元素&＃xff0c;并用e返回删除元素的值

  #include
#include
#include #define MaxSize 20typedef struct{int *data;int length;
}SqList;void InitList(){L.data &＃61; (int *)malloc(MaxSize*sizeof(int));L.length &＃61; 0;
};//e为此次删除的数据元素返回
bool ListDelete(SqList &L,int i,ElemType &e){if (i<1||i>L.length){return false;}e &＃61; L.data[i-1];for (int j&＃61;i;j}int main(){SqList L;InitList(L);if (ListDelete(L,3,e)){printf("已经删除第三个元素&＃xff0c;删除元素值为&＃61;%d\n",e);} else{printf("位序i不合法&＃xff0c;删除失败\n");}
}


  2.4.3 查找

  2.4.3.1 按位查找

  GetElem(L,i)&＃xff1a;获取表中第i个位置的元素的值

  #include
#include #define MaxSize 10
typedef struct{//用静态“数组”存放数据元素ElemType data[MaxSize];int length;
}SqList;//按位查找
ElemType GetElem(SqList L,int i){return L.data[i-1];
}


  2.4.3.2 按值查找

  //顺序表的初始长度
#define InitSize 10
//按值查找
typedef struct{ElemType *data;//顺序表最大容量int MaxSize;//顺序表当前长度int length;
}SeqList;//在顺序表L中查找第一个元素值等于e的元素&＃xff0c;并返回其位序
int LocateElem(SeqList L,ElemType e){for (int i &＃61; 0; i < L.length; i&＃43;&＃43;) {if (L.data[i]&＃61;&＃61;e){//返回位序return i&＃43;1;}}return 0;
}


  顺序表按值查找平均时间复杂度&＃xff1a;O(n)

  最好情况&＃xff1a;目标元素在表头 时间复杂度为O(1)

  最坏情况&＃xff1a;目标元素在表尾 时间复杂度为O(n)