将顺序表的接口进行详细的实现(干货!!!!!!!!!)详细!!!!!!!

小灰灰 2022-10-29 05:29 95阅读 0赞

![在这里插入图片描述][20210322173741109.png]

# 顺序表 #

顺序表就是用一段连续的物理地址**连续**的存储单元存放的线性结构.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]  
**动态顺序表:**

typedef struct seqList{ 
    	SLDataType* _data;		//需要进行动态开辟的一个数组
    	size_t _size;			//有效元素的个数
    	size_t _capacity;		//当前我们可以存放的最大元素个数
    }seqList;			//别名

如果你对这个使用动态存储的结构体,只能看到12个字节,但是对于下面的静态就不一样了,大家可以试一下(很简单,利用sizeof实现)

**静态顺序表:**

#define N 10
    
    struct seqList2{ 
    	SLDataType _data[N];		
    	size_t _size;			//有效元素的个数
    	size_t _capacity;		//当前我们可以存放的最大元素个数
    }seqList2;			//别名

## 接口声明 ##

//1.初始化
    void initSeqList(seqList * sl);
    //2.检查内存是否够用
    void checkCapacity(seqList* sl);
    //3.函数打印
    void printSeqList(seqList* ls);
    //4.头插
    void pushFront(seqList* sl, SLDataType val);
    //5.头删
    void popFront(seqList* sl);
    //6.尾插
    void pushBack(seqList* sl, SLDataType val);
    //7.尾删 
    void popBack(seqList* ls);
    //8.指定插入
    void insert(seqList* sl, int pos, SLDataType val);
    //9.指定删除
    void erase(seqList* sl, int pos);
    //10.查找对应的值
    int findIdx(seqList* sl, SLDataType val);
    //11.内存大小
    int size(seqList* sl);
    //12.销毁
    void destorySeqList(seqList* sl);

这里有12个对应头文件的声明,量比较多,但是都大体相似,希望能坚持看下去,一起加油!

## 接口实现 ##

**1.初始化**  
对于初始化这里没有什么要说的,就是将其进行0的赋值就行了.

void initSeqList(seqList * sl){ 
    	
    	sl->_data = NULL;		//指针指向空间变为0
    	sl->_size = sl->_capacity = 0;	//内存大小和最大容量也变为0,相当于int i=0;操作,很好理解
    }

**2.检查内存是否够用**

void checkCapacity(seqList* sl){ 
    
    	if (sl == NULL)		//基本的判断是否为空指针,是则直接返回
    		return;
    		
    	if (sl->_size == sl->_capacity){ 
    		//在所存储的size和最大的容量相等时,我们就需要扩大内存空间
    		
    		//当需要扩大内存时,我们的最大容量也需要变化,这里的条件运算符:如果这两个相等则+1,不等开辟二倍的内存
    		int newCapacity = sl->_capacity == 0 ? 1 : 2 * sl->_capacity;
    		//写入一个新的指针,进行动态内存的申请
    		SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType)* newCapacity);
    		//将原始的数据进行拷贝过来
    		memcpy(tmp, sl->_data, sizeof(SLDataType)*sl->_size);
    		//释放原有的内存,否则会造成内存泄漏
    		free(sl->_data);
    		//更新代码
    		sl->_data = tmp;
    		sl->_capacity = newCapacity;
    	}
    }

在这里唯一有点疑惑的可能就是为啥要申请二倍的内存,当两个内存相等的时候,我们只用申请一个,当不等的时候,我们并不能确定要申请多少个空间才能将其覆盖,所以我们直接申请二倍的内存,绝对够用,而且不用不停地进行申请,比较方便.  
**3.函数打印**

void printSeqList(seqList* ls){ 
    
    	for (int i = 0; i < ls->_size; ++i){ 	//for将内存进行循环
    		printf("%d ",ls->_data[i]);			//然后挨个打印
    	}
    	printf("\n");
    }

**4.头插**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]

void pushFront(seqList* sl, SLDataType val){ 
    
    	if (sl == NULL)
    		return;			//判断是否空指针
    	checkCapacity(sl);	//内存大小检查
    
    
    	int end = sl->_size;	//这里最后一个内存就应该是size的大小,直接利用
    	while (end > 0){ 
    		//在while里面从后往前循环依次将数据往后移一位
    		sl->_data[end] = sl->_data[end - 1];
    		--end;		
    	}
    	
    	sl->_data[0] = val;		//将要插入的数据放在最前面
    	sl->_size++;			//更新代码
    }

**5.头删**  
![在这里插入图片描述][20210209001816415.png]

void popFront(seqList* sl){ 
    	
    	if (sl == NULL||sl->_size==0)
    		return;
    	checkCapacity(sl);			//前三行基本操作,不过多解释,后面的话
    
    	int start = 1;				//第二个变量
    	while (start < sl->_size){ 	//循环[2,size)
    	
    		sl->_data[start-1]=sl->_data[start];  //依次向前一位
    		
    		++start;		//循环
    	}
    	--sl->_size;		//更新
    }

**6.尾插**

void pushBack(seqList* sl,SLDataType val){ 
    	
    	checkCapacity(sl);
    	
    	sl->_data[sl->_size] = val;				//直接将数据插入到最后
    	
    	++sl->_size;	//更新 
    }

**7.尾删**

void popBack(seqList* ls){ 
    
    	if (ls == NULL)
    		return;
    		
    	if (ls->_size > 0)	//对于尾删这里并不是真正的删除,而是将size直接-1,从而达到了尾删的效果
    		ls->_size--;
    }

**8.指定插入**  
![在这里插入图片描述][2021020900321373.png]

void insert(seqList* sl,int pos,SLDataType val){ 
    
    	if (sl == NULL)
    		return;
    
    	if (pos >= 0 && pos <= sl->_size){ 		//判断输入的位置是否在有效区域
    
    		checkCapacity(sl);
    
    		int end = sl->_size;	//定义最后一个数据
    		
    		while (end > pos){ 		//在插入数后面的数据进行循环!!!!!!
    			sl->_data[end] = sl->_data[end - 1];		//向后移一位
    			--end;		//依次循环
    		}
    
    		sl->_data[pos] = val;	//指定位置进行插入
    
    		sl->_size++;		//更新
    	}
    }

**9.指定删除**  
![在这里插入图片描述][20210209003719197.png]

void erase(seqList* sl, int pos){ 
    
    	if (sl == NULL || sl->_size == 0)
    		return;
    
    	if (pos >= 0 && pos < sl->_size){ 		//有效范围内
    		
    		int start = pos + 1;		//定义要插入后面一位的数开始
    		while (start < sl->_size){ 		//后面的范围内
    		
    			sl->_data[start - 1] = sl->_data[start];	//依次向前一格
    			++start;		//循环
    		}
    		--sl->_size;		//更新
    	}
    }

**10.查找对应的值**

int findIdx(seqList* sl, SLDataType val){ 
    	
    	int i = 0;
    	for (; i < sl->_size; ++i){ 		//内存内循环
    		if (sl->_data[i] == val)	//当值相等的时候
    			return i;				//输出位置
    	}
    	return -1;		//找不到,返回-1
    }

**11.内存大小**

int size(seqList* sl){ 
    	if (sl == NULL)
    		return 0;		//如果为空,返回0
    	else
    		return sl->_size;	//不为空,返回其长度
    }

**12.销毁**

void destorySeqList(seqList* sl){ 
    	if (sl){ 
    		if (sl->_data){ 		//指向空间
    			free(sl->_data);	//空间释放
    			sl->_data = NULL;	//指针变为空
    		}
    	}
    }

对于顺序表有下面几个特点:  
1.空间是连续的  
2.支持随机访问  
3.空间利用率高  
**关键**:我们一般使用顺序表主要用**尾插**和**尾删**,因为他们的复杂度低,提高效率,我们还是要多多注重对于内存的理解,这里是比较重要的,对于cpp而言,希望大家能坚持看下来,确实有点长,不积跬步,无以至千里嘛.一起加油!多敲代码!!!

[20210322173741109.png]: /images/20221024/30c9557318f447979943a9a8b1baaa5c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/39d98fba26334c698867559ba8d3338e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221024/cc29215abea64f628a9ae704bee4f568.png
[20210209001816415.png]: /images/20221024/08cfabb9ef3a4df48d779482bbf1c291.png
[2021020900321373.png]: /images/20221024/13b72efac68b4916ab970183d4a7faa9.png
[20210209003719197.png]: /images/20221024/b04dcbb843cc4bf09786c3ae8a6a7d1d.png