C语言数据结构之顺序表的增删改查

傷城~ 2022-11-28 13:34 267阅读 0赞

## C语言数据结构之顺序表的增删改查 ##

tips：前些天学习了链表的操作以及相关的数据结构，今天我们来学习一下c语言数据结构之顺序表的增删改查。

--------------------

**顺序表采用顺序存储，即把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间关系由存储单元的邻接关系来体现。**

--------------------

**首先创建一个顺序表的结构体，采用动态数组的方式来实现顺序表**

#define InitSize 10//动态分配顺序表的默认最大长度
    
    //定义顺序表的结构体(动态顺序表)
    typedef struct student {
        
    
    	int *data;//用于动态分配数组的指针
    	int MaxSize;//顺序表的最大容量
    	int length;//顺序表当前长度
    
    }Stu,*pStu;

准备顺序表的打印输出测试函数：

//打印顺序表中的元素
    void print_LinkList(pStu p)
    {
        
    	//循环遍历输出
    	int i;
    	for (i = 0; i < p->length; i++)
    	{
        
    		printf("%d\n", p->data[i]);
    	}
    	printf("----------------------------------------\n");
    }

--------------------

**1、顺序表的初始化**

思路：

*  为顺序表申请连续的存储空间，并初始化；
 *  初始化的MaxSize=InitSize ；length=0；

具体实现：

//顺序表的初始化
    void InitList(pStu p)
    {
        
    	//首先先申请一片连续的存储空间，并将其初始化
    	p->data = (int *)calloc(1, InitSize * sizeof(int));
    
    	//将初始化的最大值记录在MaxSize
    	p->length = 0;
    	p->MaxSize = InitSize;
    }

--------------------

**2、向顺序表中顺序插入值**

思路：

*  当length>=MaxSize时，表满，不予插入；
 *  当表未满时，插值，并使顺序表的length+1；

具体实现：

//插入操作,向表顺序插入值
    void ListInsert(pStu p, int e)
    {
        
    	if (p->length >= p->MaxSize)
    	{
        
    		//表满
    		printf("当前表已经插满！\n");
    	}
    	else
    	{
        
    		//在data[length]位置插入新值
    		p->data[p->length] = e;
    
    		//将length+1
    		p->length++;
    	}
    }

--------------------

**3、在顺序表的指定位置插入值（插入的位置对应数组下标是 插入位置-1）**

思路：

*  判断插入位置是否合法，并且表是否已满，不合法或者表已满不予插入；
 *  判定合法后，将要插入位置的元素及后面的元素整体后移，然后在指定位置插入值；
 *  插值成功后，将顺序表的length+1；

具体实现：

//插入操作，在表p的第i个位置
    void ListInsertLoc(pStu p, int i, int e)
    {
        
    	if (i <= p->length + 1 && i >= 1 && p->length < p->MaxSize)//合法位置
    	{
        
    		//将第i个位置及之后的位置整体后移一位
    		for (int j = p->length; j >= i; j--)
    		{
        
    			p->data[j] = p->data[j - 1];
    		}
    
    		p->data[i-1] = e;//在原来位置i处插入e
    
    		p->length = p->length + 1;//将顺序表现有长度加1
    
    	}
    	else
    	{
        
    		printf("插入位置不合理!\n");
    	}
    	
    }

--------------------

**4、给原顺序表扩容，动态增加顺序表的长度**

思路：

*  重新为顺序表开辟MaxSize + len大小的空间，不需要初始化，保留原数据；
 *  将原数据复制到新开辟的存储空间，并更改顺序表的最大存储空间MaxSize ；
 *  释放原来已经分配的存储空间；

具体实现：

//增加动态数组的长度,新增的长度为len
    void IncreaseSize(pStu p, int len)
    {
        
    	int *pformer = p->data;//工具人，用来记录原来数据域的数据
    
    	//重新为data开辟MaxSize+len长度的存储空间,
    	p->data = (int *)malloc((p->MaxSize + len) * sizeof(int));
    
    	//将原来data中的数据复制到新data中
    	for (int i = 0; i < p->length; i++)
    	{
        
    		p->data[i] = pformer[i];
    	}
    
    	//将顺序表的最大长度+len
    	p->MaxSize = p->MaxSize + len;
    
    	//释放原来分配的存储空间
    	free(pformer);
    }

--------------------

**5、删除指定位置的元素**

思路：

*  判断删除位置是否合理，不合理不予删除；
 *  当删除位置合理时，将要删除位置的后面的元素整体前移，实现删除的效果；
 *  删除完成后，将顺序表的length-1；

具体实现：

//删除第i个位置的元素
    void ListDelete(pStu p, int i)
    {
        
    	if (i > p->length&&i < 1)
    	{
        
    		//删除位置不存在
    		printf("删除位置不合理!\n");
    	}
    	else
    	{
        
    		if (p->length > 0)
    		{
        
    			//将i位置后面的元素整体前移,覆盖掉i，（前移是从小到大遍历）
    			for (int j = i; j < p->length; j++)
    			{
        
    				p->data[j - 1] = p->data[j];
    			}
    
    			p->length--;//将线性表长度-1
    		}
    		else
    		{
        
    			printf("顺序表已空！\n");
    		}		
    	}
    }

--------------------

**6、查找第i个位置的元素**

思路：

*  判断查找位置是否合法，不合法返回0；
 *  查找位置合法时，返回数组下标为i-1的元素；

具体实现：

//查找第i个位置的元素
    int GetElem(pStu p, int i)
    {
        
    	if (i > p->length&&i < 1)
    	{
        
    		//查找位置不存在
    		return 0;
    	}
    	else
    	{
        
    		return p->data[i - 1];
    	}
    }

--------------------

**7、查找第一个元素值等于e的元素，并返回其位序**

思路：

*  遍历表，若找到有元素等于e，返回其位序（数组下标+1）；
 *  表中没有元素等于e，返回0；

具体实现：

//在顺序表中查找第一个元素值等于e的元素，并返回其位序
    int LocateElem(pStu p, int e)
    {
        
    	int i;
    	for (i = 0; i < p->length; i++)
    	{
        
    		if (p->data[i] == e)
    		{
        
    			return i + 1;
    		}
    	}
    
    	if (i >= p->length)//位置没找到
    	{
        
    		return 0;
    	}
    }

--------------------

修改顺序表的操作跟查找相同，这里就不写了。

至此，顺序表的基本操作已经完成，我们可以在main()函数中测试一下，测试结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]

--------------------

通过以上的学习，希望对大家有所帮助。

--------------------

tips：人生是很累的，你现在不累，以后就会更累。人生是很苦的，你现在不苦，以后就会更苦。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/efd4cae414df4bfd80c084f37062d6be.png