初识数据结构——顺序表

曾经终败给现在 2023-09-28 15:27 3阅读 0赞

## 【数据结构】之顺序表（C语言版） ##

#### 目录 ####

*  【数据结构】之顺序表（C语言版）
 *  1.线性表的定义
 *  2.什么是顺序表
 *   *  顺序表的定义
 *  3.顺序表的接口实现
 *   *  （1）初始化顺序表
     *  （2）顺序表检测增容问题
     *  （3）顺序表尾插
     *  （4）顺序表尾删
     *  （5）顺序表头插
     *  （6）顺序表头删
     *  （7）顺序表查找指定值
     *  （8）顺序表指定下标位置插入
     *  （9）删除指定位置的数据
     *  （10）打印数据表
     *  （11）顺序表修改指定数值
     *  （12）销毁顺序表

## 1.线性表的定义 ##

线性表是n个具有相同特性的数据元素的有限序列，线性表是一种在实际生活中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串…

## 2.什么是顺序表 ##

顺序表即是线性表的顺序存储，他是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。  
![在这里插入图片描述][7a6fd22d3dfa47a79b2f8955ae68c5cb.jpeg]

### 顺序表的定义 ###

typedef int SLDataType;//类型重命名
    //动态顺序表
    typedef struct SeqList
    {
        
    	SLDataType* a;//指向动态开辟的数组
    	int size;//表示数组中存储了多少个数据
    	int capacity;//数组实际能存储的空间是多大
    }SL;

## 3.顺序表的接口实现 ##

需要分装三个部分实现：Seqlist.h、Seqlist.c、test.c。  
【Seqlist.h】里面用来写相关头文件的引用、接口函数的声明和结构体的类型定义。  
【Seqlist.c】里面用来实现所有的接口函数。  
【test.c】里面用来测试接口函数以及功能菜单的实现  
【Seqlist.h】头文件以及相关代码如下：

#pragma once//防止头文件倍二次引用
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<assert.h>
    typedef int SLDataType;//类型重命名
    //动态顺序表
    typedef struct SeqList
    {
        
    	SLDataType* a;//指向动态开辟的数组
    	int size;//表示数组中存储了多少个数据
    	int capacity;//数组实际能存储的空间是多大
    }SL;
    //初始化顺序表
    void SeqListInit(SL* ps);
    
    //顺序表尾插入
    void SeqListPushBack(SL* ps);
    
    //顺序表尾删除
    void SeqListPopBack(SL* ps);
    
    //顺序表头插入
    void SeqListPusFront(SL* ps);
    
    //顺序表头删除
    void SeqListPopFront(SL* ps);
    
    //顺序表检测增容问题
    void SeqListCheckCapacity(SL* ps);
    
    //顺序表查找指定值
    int SeqListFind(SL* ps, SLDataType x);
    
    //顺序表指定下标位置插入
    void SeqListInsert(SL* ps);
    
    //删除pos位置的数据
    void SeqListErase(SL* ps);
    
    //打印顺序表
    void SeqListPrint(SL* ps);
    
    //销毁顺序表
    void SeqListDestory(SL* ps);
    
    //顺序表修改指定元素数值
    void SeqListModify(SL* ps);

【test.c】文件中菜单的实现如下：

#define _CRT_SECURE_NO_WARNINGS 1
    #include"Seqlist.h"
    void menu()
    {
        
    	printf("                      顺序表操作                    \n");
    	printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
    	printf("             1.尾插入           2.尾删除            \n");
    	printf("             3.头插入           4.头删除            \n");
    	printf("             5.指定下标位置插入 6.打印顺序表        \n");
    	printf("             7.删除指定位置数据 8.修改指定数值      \n");
    	printf("~~~~~~~~~~~~~~~~~~~~~0.退出程序~~~~~~~~~~~~~~~~~~~~~\n");
    }
    int main()
    {
        
    	int input = 0;
    	SL s1;
    	SeqListInit(&s1);//初始化顺序表
    	do
    	{
        
    		menu();
    		printf("请选择:");
    		scanf("%d", &input);
    		switch (input)
    		{
        
    		case 1:
    			SeqListPushBack(&s1);//尾插
    			break;
    		case 2:
    			SeqListPopBack(&s1);//尾删
    			break;
    		case 3:
    			SeqListPusFront(&s1);//头插
    			break;
    		case 4:
    			SeqListPopFront(&s1);//头删
    			break;
    		case 5:
    			SeqListInsert(&s1);//指定下标位置插入
    			break;
    		case 6:
    			SeqListPrint(&s1);//打印顺序表
    			break;
    		case 7:
    			SeqListErase(&s1);//删除指定位置数据
    			break;
    		case 8:
    			SeqListModify(&s1);//修改指定数值
    			break;
    		case 0:
    		SeqListDestory(&s1);//销毁顺序表
    		printf("退出程序\n");
    		break;
    		default:
    			printf("选择错误,请重新选择\n");
    			break;
    		}
    	} while (input);
    	return 0;
    }

### （1）初始化顺序表 ###

void SeqListInit(SL* ps)
    {
        
    	ps->a = NULL;//初始化顺序表为空
    	ps->capacity = ps->size = 0;//初始化数据个数和数组实际存储的空间为空
    }

### （2）顺序表检测增容问题 ###

为避免频繁增容，我们一次性去增容上一次空间大小的两倍，在这里需要注意的是当传给realloc的指针为空时，realloc的用法等同于malloc。

void SeqListCheckCapacity(SL* ps)
    {
        
    	if (ps->capacity == ps->size)
    	{
        
    	    //如果是第一次开辟空间，先开辟四个字节大小的存储空间
    	    //之后就以原空间二倍的大小去增加容量
    		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    		SLDataType* tmp = realloc(ps->a, 
    		newcapacity * sizeof(SLDataType));
    		if (tmp == NULL)
    		{
        
    			printf("realloc fail\n");
    			exit(-1);//如果内存开辟失败，直接退出程序
    		}
    		ps->a = tmp;//将数组指向新开辟的动态存储空间
    		ps->capacity = newcapacity;//将容量指向新开辟的大小
    	}
    }

### （3）顺序表尾插 ###

在这里我们使用while循环可以一次性插入多个数据。

void SeqListPushBack(SL* ps)
    {
        
    	SeqListCheckCapacity(ps);//插入数据之前，先检测容量是否已满
    	SLDataType x;
    	printf("请输入您要插入的元素:");
    	scanf("%d", &x);
    	while (x!= EOF)
    	{
        
    		ps->a[ps->size] = x;
    		ps->size++;//数据个数+1
    		SeqListCheckCapacity(ps);//检测容量是否已满
    		scanf("%d", &x);
    	}
    }

函数功能测试  
![在这里插入图片描述][14eb2391ffdd4537bbc3a10ed9d2b663.png]

### （4）顺序表尾删 ###

void SeqListPopBack(SL* ps)
    {
        
    	assert(ps->size);//先断言顺序表是否为空
    	if (ps->size > 0)
    	{
        
    		ps->size--;//只需将有效数据个数减一即可
    		printf("尾删成功\n");
    	}
    }

函数功能测试  
![在这里插入图片描述][59ce927908ad44429383983a483a640b.png]

### （5）顺序表头插 ###

和尾插一样，在这里我们可以使用循环一次性插入多个数据

void SeqListPusFront(SL* ps)
    {
        
    	SeqListCheckCapacity(ps);//头插之前先检测是否需要增容
    	SLDataType x;
    	printf("请输入您要头插的元素:");
    	scanf("%d", &x);
    	while (x != EOF)
    	{
        
    		int i = 0;
    		//遍历数组，使得头部数据到尾部数据依次向后挪动一位
    		for (i = ps->size - 1; i >= 0; i--)
    			ps->a[i + 1] = ps->a[i];
    		ps->a[0] = x;
    		ps->size++;
    		SeqListCheckCapacity(ps);//每插入一个元素，都需要检测容量
    		scanf("%d", &x);
    	}
    }

函数功能测试  
![在这里插入图片描述][34acf77157f843589a391ed366a1aa0e.png]

### （6）顺序表头删 ###

void SeqListPopFront(SL* ps)
    {
        
    	assert(ps->size);//先判断顺序表数据个数是否为空
    	if (ps->size > 0)
    	{
        
    		int i = 0;
    		//遍历数组，将头元素之后的元素依次向前挪动一位
    		for (i = 0; i < ps->size - 1; i++)
    			ps->a[i] = ps->a[i + 1];
    	}
    	ps->size--;//有效数据个数减一
    	printf("头删成功\n");
    }

函数功能测试  
![在这里插入图片描述][1823e2f922bf44a893f632560886b613.png]

### （7）顺序表查找指定值 ###

int SeqListFind(SL* ps, SLDataType x)
    {
        
    	assert(ps->size);//顺序表元素个数是不能为空
    	int i = 0;
    	//遍历数组，将所有元素与所需查找的指定元素一一对比
    	while (i < ps->size)
    	{
        
    	    //若能找到，返回元素下标
    		if (ps->a[i] == x)
    			return i;
    		i++;
    	}
    	return -1;//找不到，则返回-1
    }

### （8）顺序表指定下标位置插入 ###

void SeqListInsert(SL* ps)
    {
        
    	int pos = 0;
    	SLDataType x;
    	printf("请输入下标和需要插入的数据");
    	scanf("%d%d", &pos, &x);
    	//判断指定下标是否超出有效范围，超出范围，则重新输入
    	while (pos<0||pos > ps->size)
    	{
        
    		printf("下标位置超出范围,请重新输入:");
    		scanf("%d", &pos);
    	}
    	SeqListCheckCapacity(ps);//检测顺序表容量是否已满
    	for (size_t i = ps->size - 1; i >= pos; i--)
    		ps->a[i + 1] = ps->a[i];
    	ps->a[pos] = x;//插入数据
    	ps->size++;//有效数据个数+1
    	printf("插入成功\n");
    }

函数功能测试  
![在这里插入图片描述][9b0a44d333fb4429b40acb1781bdc7b3.png]

### （9）删除指定位置的数据 ###

在这里我们需要注意的是指定pos的范围是大于size-1，而上面的指定插入的pos的范围是大于size。这是因为数组的插入可以在最后一个元素的后面插入，而删除只能是删除最后一个元素。

void SeqListErase(SL * ps)
    {
        
    	assert(ps->size);
    	int pos = 0;
    	printf("请输入所需删除的数值下标");
    	scanf("%d", &pos);
    	//判断指定位置下表是否超出有效范围
    	while (pos<0 || pos>ps->size - 1)
    	{
        
    		printf("pos invalid,请重新输入下标:");//超出范围，重新输入
    		scanf("%d", &pos);
    	}
    	for (int i = pos; i < ps->size; i++)
    		ps->a[i] = ps->a[i + 1];
    	ps->size--;//有效数据个数-1
    	printf("删除成功\n");
    }

函数功能测试  
![在这里插入图片描述][8985b92312294fd191d59f630b870f3b.png]

### （10）打印数据表 ###

void SeqListPrint(SL* ps)
    {
        
    	assert(ps->size);//断言，元素个数不能为0
    	for (int i = 0; i < ps->size; i++)
    		printf("%d ", ps->a[i]);//遍历数组，打印出每一个元素
    	printf("\n");
    }

### （11）顺序表修改指定数值 ###

这里我们需要用到“顺序表查找指定值”这个函数，用一个整型变量来接收所需要修改元素的下标，最后再修改。

void SeqListModify(SL* ps)
    {
        
    	SLDataType value, x ;//x为所需要修改的元素，value为该元素修改后的值
    	printf("请输入所需要修改的元素:");
    	scanf("%d", &x);
    	int tmp = SeqListFind(ps, x);
    	while (tmp == -1)
    	{
        
    		printf("该元素不存在,请重新输入:");
    		scanf("%d", &x);//重新输入所需要修改的元素
    		tmp = SeqListFind(ps, x);//重新接受新输入元素的下标
    	}
    	if (tmp != -1)
    	{
        
    		printf("请输入修改后的值:");
    		scanf("%d", &value);
    		ps->a[tmp] = value;//将该元素修改为value
    		printf("修改成功\n");
    	}
    }

函数功能测试  
![在这里插入图片描述][705b104be27145e98556510381a5102e.png]

### （12）销毁顺序表 ###

void SeqListDestory(SL* ps)
    {
        
        assert(ps);
    	free(ps->a)//释放开辟的空间
    	ps->a=NULL;
    	ps->size = 0;//数据个数置为0
    	ps->capacity = 0;//空间容量置为0
    }

**总节**  
*好了，以上就是顺序表的详解了，各位小伙伴们如果觉得不错的话可以支持一下哦！*

[7a6fd22d3dfa47a79b2f8955ae68c5cb.jpeg]: https://img-blog.csdnimg.cn/7a6fd22d3dfa47a79b2f8955ae68c5cb.jpeg
[14eb2391ffdd4537bbc3a10ed9d2b663.png]: https://img-blog.csdnimg.cn/14eb2391ffdd4537bbc3a10ed9d2b663.png
[59ce927908ad44429383983a483a640b.png]: https://img-blog.csdnimg.cn/59ce927908ad44429383983a483a640b.png
[34acf77157f843589a391ed366a1aa0e.png]: https://img-blog.csdnimg.cn/34acf77157f843589a391ed366a1aa0e.png
[1823e2f922bf44a893f632560886b613.png]: https://img-blog.csdnimg.cn/1823e2f922bf44a893f632560886b613.png
[9b0a44d333fb4429b40acb1781bdc7b3.png]: https://img-blog.csdnimg.cn/9b0a44d333fb4429b40acb1781bdc7b3.png
[8985b92312294fd191d59f630b870f3b.png]: https://img-blog.csdnimg.cn/8985b92312294fd191d59f630b870f3b.png
[705b104be27145e98556510381a5102e.png]: https://img-blog.csdnimg.cn/705b104be27145e98556510381a5102e.png