本文共 9327 字，大约阅读时间需要 31 分钟。

顺序表

1、顺序表的定义

（1）相关定义以及解析

（2）代码实现定义

#include
   
    typedef struct{
   	int num;//号数 	int people;//人数 } Customer ;void main(){
   	printf("%d",sizeof(Customer));}
   

2、顺序表的实现

（1）顺序表的实现 一一静态分配

a、设置默认值

C++代码

#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;   //将所有数据元素设置为默认初始值 	L.length = 0;//顺序表初始长度为0 }int main(){
   	SqList L;   //声明一个顺序表 	InitList(L);//初始化顺序表 	//..未完待续 	return 0; }
   

注意在上面的程序当中的我们给SqList 当中的值赋予了10和0 并设置长度为10

这样做的目的是为了设置其初始值为0，在后面使用的时候我们只需要将其设置的覆盖掉即可

在后期使用的时候

#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;   //将所有数据元素设置为默认初始值 	L.length = 0; }int main(){
   	SqList L;   //声明一个顺序表 	InitList(L);//初始化顺序表 	for(int i = 0; i < MaxSize; i++){
   		printf("%d ",L.data[i]);	}	printf("\n");	for(int i = 0; i < MaxSize;i++){
   		L.data[i] = i;	} 	L.length = MaxSize;		for(int i = 0; i < MaxSize; i++){
   		printf("%d ",L.data[i]);	}			return 0; }
   

b、假设我们不设置默认值会怎么样

#include
   
    #define MaxSize 10         //定义最大长度 typedef struct {
   	   	int data[MaxSize];     //用静态的“数组 ” 存放数据元素 	int length;            //顺序表的当前长度 }SqList;                   //顺序表的类型定义（静态分配方式） //基本操作一初始化一个顺序表void InitList(SqList &L){
   	L.length = 0; }int main(){
   	SqList L;   //声明一个顺序表 	InitList(L);//初始化顺序表 	//尝试“违规”打印整个data数组 	for(int i = 0; i < MaxSize; i++){
   		printf("data[%d]=%d\n", i , L.data[i]);	}			return 0; }
   

Q：如果“数组”存满了怎么办？ A：可以放弃治疗，顺序表的长度刚刚开始确定后就无法改变更改（存储空间是静态的）

（2）顺序表的实现 一一动态分配

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

顺序表实现动态分配相关代码

#include
   
    #include 
    
     #define InitSize 10  //默认最大长度 typedef struct {
   	int *data;//指示动态分配数组的指针 	int maxSize;//顺序表的最大容量 	int length;//顺序表的当前最大长度 }SeqList;void InitList(SeqList &L){
   	//用malloc 函数申请一片连续的存储空间	L.data=(int *)malloc(InitSize*sizeof(int));	L.length = 0;	L.maxSize =  InitSize;}//增加动态数组的长度 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 = L.maxSize + len;//顺序表最大长度增加len 	free(p);//释放原来内存空间 }int main(){
   	SeqList L;//声明一个顺序表 	InitList(L);//初始化顺序表	//...往顺序表当中随便插入几个元素。。	IncreaseSize(L,5);	return 0;	}
    
   

（3）顺序表的特点

a、随机访问，既可在O(1)时间找到第i个元素。（代码实现：data[i-1]，静态分配，动态分配，都一样）

b、存储密度高，每个节点只存储数据元素 c、拓展容量不方便（既变采用动态分配的方式，拓展长度的时间复杂度也比较高） d、插入、删除操作不方便、需要移动大量元素。

顺序表就是用顺序存储的方式实现的线性表

3、顺序表的插入和删除

（1）插入

ListInsert(&L,i,e):插入操作。

在表L中的第i个位置上插入指定元素e。

第i个位置指的是位序

顺序表用于存储位置的相邻来体现数据元素之间的逻辑关系

#define MaxSize 10	//定义最大长度typedef struct{
   	ElemType data[MaxSize ];//用静态的“数组”存储数据元素（用静态分配的方式实现顺序表）	int length;	//顺序表的当前长度}SqList; //顺序表的类型定义

#include
   
    #define MaxSize 10         //定义最大长度 typedef struct {
   	   	int data[MaxSize];     //用静态的“数组 ” 存放数据元素 	int length;            //顺序表的当前长度 }SqList;                   //顺序表的类型定义（静态分配方式） //基本操作一初始化一个顺序表void InitList(SqList &L){
   	L.length = 0; }void ListInsert(SqList &L,int i,int e){
   //基本操作：在L位序i处插入	for(int j = L.length; j >= i;j--){
   //在第i个元素之后的元素后移		L.data[j] = L.data[j-1];	}	L.data[i-1] = e;//在位置i处放入e	L.length++;}int main(){
   	SqList L;   //声明一个顺序表 	InitList(L);//初始化顺序表 	//...此处省略一些代码，插入几个元素	L.data[0] = 1;	L.data[1] = 2;	L.data[2] = 4;	L.data[3] = 5;	L.data[4] = 6;	L.length =  5;	printf("插入前\n");	for(int i = 0; i < L.length;i++){
   		printf("%d\n",L.data[i]);	}	printf("插入后\n");	ListInsert(L,3,3);	for(int i = 0; i < L.length;i++){
   		printf("%d\n",L.data[i]);	}	return 0;}
   

（2）插入二：在9的位置插入对应的数据

a、直接在上述的顺序表当中插入数据

#include
   
    #define MaxSize 10         //定义最大长度 typedef struct {
   	   	int data[MaxSize];     //用静态的“数组 ” 存放数据元素 	int length;            //顺序表的当前长度 }SqList;                   //顺序表的类型定义（静态分配方式） //基本操作一初始化一个顺序表void InitList(SqList &L){
   	L.length = 0; }void ListInsert(SqList &L,int i,int e){
   //基本操作：在L位序i处插入	for(int j = L.length; j >= i;j--){
   //在第i个元素之后的元素后移		L.data[j] = L.data[j-1];	}	L.data[i-1] = e;//在位置i处放入e	L.length++;}int main(){
   	SqList L;   //声明一个顺序表 	InitList(L);//初始化顺序表 	//...此处省略一些代码，插入几个元素	L.data[0] = 1;	L.data[1] = 2;	L.data[2] = 4;	L.data[3] = 5;	L.data[4] = 6;	L.length =  5;	printf("插入前\n");	for(int i = 0; i < L.length;i++){
   		printf("%d\n",L.data[i]);	}	printf("插入后\n");	ListInsert(L,3,3);	ListInsert(L,9,3);	for(int i = 0; i < L.length;i++){
   		printf("%d\n",L.data[i]);	}	return 0;}
   

直击在上述代码当中插入数据显然是不合法的

因为顺序表必须的数据必须是相邻的

b、需要通过i判断一下，插入的数据是否合法，而且需要判断当前顺序表是否存满，如果存满就不应该往内部插入数据。

完善上述算法

情况一：插入非法数据

#include
   
    #define MaxSize 10         //定义最大长度 typedef struct {
   	   	int data[MaxSize];     //用静态的“数组 ” 存放数据元素 	int length;            //顺序表的当前长度 }SqList;                   //顺序表的类型定义（静态分配方式） //基本操作一初始化一个顺序表void InitList(SqList &L){
   	L.length = 0; }bool ListInsert(SqList &L,int i,int e){
   //基本操作：在L位序i处插入	if(i < 1 || i > L.length +1){
      //判断i的范围是否有效 		printf("插入数据无效\n"); 		return false;	}	if(L.length >= MaxSize){
   	//判断存储空间是否已经满，不能插入 		printf("插入数据已满\n"); 		return false;	}	for(int j = L.length; j >= i;j--){
   //在第i个元素之后的元素后移		L.data[j] = L.data[j-1];	}	L.data[i-1] = e;//在位置i处放入e	L.length++;	return true;}int main(){
   	SqList L;   //声明一个顺序表 	InitList(L);//初始化顺序表 	//...此处省略一些代码，插入几个元素	L.data[0] = 1;	L.data[1] = 2;	L.data[2] = 4;	L.data[3] = 5;	L.data[4] = 6;	L.length =  5;	printf("插入前\n");	for(int i = 0; i < L.length;i++){
   		printf("%d\n",L.data[i]);	}	printf("插入后\n");	ListInsert(L,3,3);	ListInsert(L,9,3);	for(int i = 0; i < L.length;i++){
   		printf("%d\n",L.data[i]);	}	return 0;}
   

情况二：顺序表已满

#include
   
    #define MaxSize 10         //定义最大长度 typedef struct {
   	   	int data[MaxSize];     //用静态的“数组 ” 存放数据元素 	int length;            //顺序表的当前长度 }SqList;                   //顺序表的类型定义（静态分配方式） //基本操作一初始化一个顺序表void InitList(SqList &L){
   	L.length = 0; }bool ListInsert(SqList &L,int i,int e){
   //基本操作：在L位序i处插入	if(i < 1 || i > L.length +1){
      //判断i的范围是否有效 		printf("插入数据无效\n"); 		return false;	}	if(L.length >= MaxSize){
   	//判断存储空间是否已经满，不能插入 		printf("插入数据已满\n"); 		return false;	}	for(int j = L.length; j >= i;j--){
   //在第i个元素之后的元素后移		L.data[j] = L.data[j-1];	}	L.data[i-1] = e;//在位置i处放入e	L.length++;	return true;}int main(){
   	SqList L;   //声明一个顺序表 	InitList(L);//初始化顺序表 	//...此处省略一些代码，插入几个元素	L.data[0] = 1;	L.data[1] = 2;	L.data[2] = 4;	L.data[3] = 5;	L.data[4] = 6;	L.length =  5;	printf("插入前\n");	for(int i = 0; i < L.length;i++){
   		printf("%d\n",L.data[i]);	}	printf("插入后\n");	for(int i = 0; i < 6;i++){
   		ListInsert(L,3,3);	}	for(int i = 0; i < L.length;i++){
   		printf("%d\n",L.data[i]);	}	return 0;}
   

（3）插入操作的时间复杂度

a、最好的情况：新元素插入到表尾，不需要移动

i = n + 1，循环0次；最好的时间复杂度=O(1)

b、最坏的情况：在新元素插入表头，需要将原有的n个元素全部向后移动

i = 1,循环n次；最坏的时间复杂度=O(n)

c、平均的情况

假设新元素插入到任何一个位置的概率相同,既i=1,2,3,…,length+1的概率都是,p=1/n+1

i = 1,循环n次；i=2时，循环n-1次，i=3，循环n-2次… i = n + 1时，循环0次

平均循环次数

平均时间复杂度O(n)

4、顺序表的查找

GetElem(L,i):安位查找操作。获取表L中第i个位置的元素的值。

#define MaxSize 10    //定义最大长度 typedef struct {
   	ElemType data[MaxSize];	//用静态的“数组”存放数据元素 (静态分配)	int length; 			// 顺序表的当前长度 }SeqList;					//顺序表的类型定义（静态分配的方式） EmemType GetElem(SeqList L,int i) {
    //和访问普通数组的方法一样 	return L.data[i-1];}

ElemType *data 如果一个ElemType 占 6B ，即sizeof(ElemType)==6

1）顺序表的查找

再次理解，为何malloc函数返回的存储空间起始地址要转换为与数据空间的数据类型相对应的指针

2）按位查找的时间复杂度

由于顺序表的各个元素在内存中连续存放，因此可以根据起始地址和数据元素的

LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字的元素。

#define InitSize 10    //顺序表的初始长度typedef struct {
   	ElemType *data;    //指示动态分配数组的指针	int MaxSize;       //顺序表的最大容量	int length;			//顺序表的当前长度}SeqList;				//顺序表的类型定义（动态分配方式）//在顺序表L中查找第一个元素值等于e的元素，并返回其位序int LocateElem(SeqList L,EmemType e){
   	for(int i = 0; i < L.length;i++){
   		if(L.data[i] == e)			return i+1;	return;	}}

基本数据类型：int char double

float 等可以直接用运算符"=="比较

调用：LocateElem(L,9);

3）结构类型的比较

typedef struct {
   	int num;	int people;}Customer;

void test(){
   	Customer a;	a.num = 1;	a.people = 1;	Customer b;	b.num = 1;	b.people = 1;	if ( a == b ){
   //注意：C语言当中，结构体的比较不能直接用==		printf("相等");	}else{
   		printf("不相等");	}}bool isCustomerEqual(Customer a,Customer b){
   	if(a.num == b.num && a.people == b.people){
   		return;	}else{
   		return false;	}}

4）顺序表的按值查找

LocateElem(L,e) :按值查找操作。

在表当中查找具有给定关键词字值的元素。

//在顺序表L中查找第一个元素的值等于e的元素，并返回其位序int LocateElem(SeqList L,ElemType e){
   	for(int i = 0; i < L.length;i++){
   		if(L.data[i] == e)			return i+1;	//数组下标位i的元素值等于e，返回其位序i+1		return 0;		//退出循环，说明查找失败	}}

Tips：

《数据结构》考研初试中

手写代码可以直接用“==”

无论ElemType是基本数据类型还是结构类型

手写代码主要考察学生是否理解算法思想，不会严格要求代码完全可运行

有的学校考《C语言程序设计》

那么…也行就要语法严格一些

5）按值查找的时间复杂度

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序int LocateElem(SeqList L,ElemType e){
   	for(int i = 0; i < L.length;i++){
   		if(L.data[i] == 0)//关注最深层次循环语句的执行			return i + 1;//次数于问题规模的n的关系  返回其位序 i + 1		return 0;		//问题规模n = L.length (表长)	}}

最好情况：目标元素在表头

循环一次：最好的时间复杂度 = O(1)

最坏情况：目标元素在表尾

循环n次：最坏时间复杂度 = O(n)

平均情况：假设目标元素出现在任何一个位置上的概率相同，都是1/n

目标元素在第1位，循环1次；在第2位，循环2次；…；在n位，循环n次

平均时间复杂度=O(n)

转载地址：https://code100.blog.csdn.net/article/details/117932477 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！