顺序表详解

迷南。 2024-03-26 13:23 38阅读 0赞

#### 顺序表详解 ####

*  一.基本概念
 *  二.功能实现
 *   *  1.初始化
     *  2.销毁
     *  3.尾插尾删
     *  4.头插头删
     *  5.任意位置插入和删除
     *  6.改进
     *  7.查找
 *  三.完整源代码

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

## 一.基本概念 ##

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

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

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

> **分别用于存放头文件声明，进行测试和顺序表的实现。**

> **由于该数据结构是以工程为目的，所以很多的定义和命名方式与写工程保持一致（注意与写算法里的顺序表是很不相同的）。**

> **顺序表分为静态和动态，由于静态顺序表很不方便并且在工程中很少使用，所以下面我们直接写动态顺序表。**

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

## 二.功能实现 ##

### 1.初始化 ###

> **特别注意要记得传地址不能直接传值。**

*首先在主函数里创建测试样例*

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

*创建顺序表声明*

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

*实现初始化*

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

### 2.销毁 ###

*测试文件里*  
![在这里插入图片描述][e351423a7e1f49dd954579fac377aa17.png]

*声明文件里*

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

*销毁的实现*

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

### 3.尾插尾删 ###

*首先声明*

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

*判断是否已经排满*

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

*尾插实现*

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

*尾删*

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

### 4.头插头删 ###

*声明*

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

*头插*

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

*头删*

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

### 5.任意位置插入和删除 ###

*声明*

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

*任意位置插入*

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

*任意位置删除*

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

### 6.改进 ###

> **根据上面的任意位置插入和删除，所以我们可以把头插头删尾插尾删**

*头插头删*

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

*尾插尾删*

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

### 7.查找 ###

*声明*

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

*实现查找*

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

*打印整个顺序表*

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

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

## 三.完整源代码 ##

*SeqList.h*

#pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    typedef int SLDateType;//sldatetype是顺序表类型以符合工程命名规则
    #define INIT_CAPACITY 4//初始容量
    
    typedef struct SeqList
    {
        
    	SLDateType* a;
    	int size;//有效数据个数
    	int capacity;//空间容量
    }SL;
    
    void SeqInit(SL*s);//初始化顺序表
    
    void Seqdestroy(SL* s);//销毁顺序表
    
    void SLCheckCapacity(SL* ps);//判断是否排满
    void SLPushBack(SL* ps, SLDateType x);//尾插
    void SLPopBack(SL* ps);//尾删
    
    
    void SLPushFront(SL* ps,SLDateType X);//头插
    void SLPopFront(SL* PS);//头删
    
    void SLInert(SL* ps, int pos, SLDateType x);//某个位置插入
    void SLErase(SL* ps, int pos);//某个位置删除
    
    
    int SLFind(SL* ps, SLDateType x);//查找
    void SeqPrintf(SL* ps);//打印整个顺序表

*SeqList.c*

#define _CRT_SECURE_NO_WARNINGS
    #include"SeqList.h"
    
    
    void SeqInit(SL*ps)
    {
        
    	ps->a = (SLDateType)malloc(sizeof(SLDateType) * INIT_CAPACITY);//开辟初始容量（SLDateType就是int类型）
    	if (ps->a == NULL)//如果开辟错误打印错误
    	{
        
    		perror("malloc fail");
    		return;
    	}
    	ps->size = 0;//当前没有存数据所以当前个数是0
    	ps->capacity = INIT_CAPACITY;//初始化容量大小（4个整形）
    }
    
    
    void Seqdestory(SL* ps)
    {
        
    	free(ps->a);//注意a数组是由malloc开辟的所以在程序结束时也要释放
    	ps->a = NULL;
    	ps->capacity = ps->size = 0;//容量归0
    }
    
    void SLCheckCapicity(SL* ps)
    {
        
    	//首先考虑是否需要扩容
    	if (ps->size == ps->capacity)
    	{
        
    		SLDateType* tmp = (SLDateType)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);
    		//判断是否开辟成功
    		if (tmp == NULL)
    		{
        
    			perror("realloc error");
    			return;
    		}
    		ps->capacity *= 2;//如果开辟成功，则将原来空间扩大一倍
    	}
    }
    
    void SLPushBack(SL* ps, SLDateType x)//尾插
    {
        
    	/*SLCheckCapacity(ps);
    	ps->a[ps->size++] = x;*/
    	SLInert(ps, ps->size - 1, x);
    }
    
    
    void SLPopBack(SL* ps)//尾删
    {
        
    	//assert(ps->size > 0);//如果size<=0时就报错(别忘了头文件assert.h哟)
    	//ps->size--;
    	SLErase(ps, ps->size - 1);
    }
    
    void SLPushFront(SL* ps,SLDateType x)//头插
    {
        
    	SLCheckCapacity(ps);//首先检查是否排满
    
    	/*int end = ps->size - 1;
    	while (end >= 0)
    	{
    		ps->a[end + 1] = ps->a[end];
    		end--;
    	}
    	ps->a[0] = x;
    	ps->size++;*/
    	SLInert(ps, 0, x);
    }
    
    
    void SLPopFront(SL* ps)//头删
    {
        
    	//assert(ps->size > 0);//判断是否为空
    
    	//int begin = 1;
    	//while (begin < ps->size)
    	//{
        
    	//	ps->a[begin - 1] = ps->a[begin];
    	//	begin++;
    	//}
    	//ps->size--;
    	SLErase(ps, 0);
    }
    
    void SLInert(SL* ps, int pos, SLDateType x)//任意插入
    {
        
    	assert(pos >= 0 && pos <= ps->size);//选择位置必须合法
    
    	SLCheckCapacity(ps);//判断是否需要扩容
    	int end = ps->size - 1;
    	while (end >= pos)
    	{
        
    		ps->a[end + 1] = ps->a[end];
    		end--;
    	}
    	ps->a[pos] = x;
    	ps->size++;
    }
    
    void SLErase(SL* ps, int pos)//任意删除
    {
        
    	assert(pos >= 0 && pos < ps->size);//判断位置是否合法
    
    	int begin = pos;
    	while (begin < ps->size-1)
    	{
        
    		ps->a[begin] = ps->a[begin + 1];
    		begin++;
    	}
    	ps->size--;
    }
    
    int SLFind(SL* ps, SLDateType x)//查找
    {
        
    	for (int i = 0; i < ps->size; i++)
    	{
        
    		if (ps->a[i] == x) return i;
    	}
    	return -1;
    }
    
    
    void SeqPrintf(SL* ps)
    {
        
    	for (int i = 0; i < ps->size; i++)
    	{
        
    		printf("%d ", ps->a[i]);
    	}
    }

*Test.c*

#define _CRT_SECURE_NO_WARNINGS
    #include"SeqList.h"
    
    void TestSeqList()
    {
        
    	SL s;
    	SeqInit(&s);//初始化顺序表
    
    	//任意插入或者删除操作
    	SeqPrintf(ps);
    	Seqdestroy(&s);//销毁顺序表
    }
    
    int main()
    {
        
    	TestSeqList();
    	return 0;
    }

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

[6dfee1ca0abe40a597bbf020de08d568.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/699b5e1fa2dd4e0da1c1ef549788fce7.png
[a5f49377ec8044bc9469a7223d853750.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1ba4e1b7bbea41c79ae645c482183cc2.png
[131074c66d0f46839f0802c10e83f232.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/bcab5915a9b44c0084c4eccc146fdb59.png
[46e0956f54ab4b1dbd66eecc81504bc6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/5601e43371fa4d3cb0f8bc71e9e8ee85.png
[a56123b178d04dd7a92de543fd961791.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/2f0428d1c6794f0ea9e2f917946fd5e8.png
[cb993c87c99b45faa798ea727b5677b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/dfdec17cd54f41448e792b3fce048129.png
[e137a5f73bbf4555a203c1d43e687825.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/3a43bd17de4244d7af0303e612309808.png
[4f3b4a37a8c541c09cfa502df3102388.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/18c024729f7b473f8914b2e286b1c1df.png
[e351423a7e1f49dd954579fac377aa17.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/f063137a41ac45f2a83eb7467ee127f1.png
[dfeb0103e2694d088042665c29e29968.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/82b0c71485454119b29b2d398cb80542.png
[d3e870963cf840ecb478ac2a1a7985a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d4a5503f88ef4cda9dfb352659af43d2.png
[12b6714ac194461a9abdf8cfa6ed169d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/50420396dd3c46f0a6c50c0e1770807b.png
[7de7f2134e474a6987436a5d7f91e6f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/5ce190f0b2154727bfa7f9ec22fa7d68.png
[bd584aca61654411a0b1df22878e27b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/8171e564b324423ebb3b59775182de9e.png
[eb629c6f3c4e43d5bb6b0547286672ef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e8f33a4394734707b962ec341259682a.png
[7973454286d74ba890ccb74908db3f19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/37f6c95d7ef24805b5fcebd63dd2d0be.png
[58a049e2c2604ac4a4f7706fec3f5ea1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/11f63b81552b4d079066556c757c7b77.png
[f76ddc76c6bf47d6bcb70bff1c76e45a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/23642d53786e4d288ce93f392d41e5bf.png
[386c521c14b3445da601f6548734734f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/b6405efbebfd44eb97f7e8f816e933b5.png
[31737134e831439d93418de348d66156.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ddfe573b43294a658abf77cfcb9942ff.png
[a9c2f2727b12433188e7ec8e83858e15.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/8c62aeeba40742c39c19bcc7d8853d1d.png
[9ce2ccaff407464ab4fb25b1686ecff2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/0a94aa965d834defb3f6529c372e69a4.png
[6022e068476044a48c1312cfcb2a0786.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/13e50232b6824374a9e33e9fec5efbb3.png
[2df993846a014790a0ff7bc90d7be194.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/5c68baa250784e9891b1014ed2f7830f.png
[48c4e3f6d5874e2c8b8d703e128bb5b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/72c941ce67f44f3192e1f5d03bc927d7.png
[526f071ae96542d69a98d1ce0d4009f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/73c5ce159e6d445faa2fe2bbbfe20f12.png
[eb139da675a94efba3c1552cfecadc27.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1d1d2ba7c06c4ca4a3f9697445d96ad3.png
[3e4598e82db14d09b434f914c6c9b9ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ab6c547bfd60409cb389cf8ed1c8a1d8.png