数据结构——顺序表【C】

顺序表

• 1. 顺序表的概念以及结构
• • 1.1概念
  • 1.2静态顺序表和动态顺序表
  • 2. 顺序表接口模拟实现
  • 接口总览
  • • 2.1 初始化数据和销毁容器
    • 2.2 顺序表的尾插和尾删
    • • 2.3 头插和头删
      • 2.4 任意位置插入和删除数据
      • 2.5 查找数据
      • 3. 顺序表的问题 ：

        1. 顺序表的概念以及结构

        1.1概念

        顺序表就是用一段物理地址连续空间储存元素的线性结构，在正常情况下采用数组存储，在数组上完成增删查改等操作。

        1.2静态顺序表和动态顺序表

        1. 静态顺序表： 使用长数组存储数据（数组的长度是固定的）
        2. 动态顺序表： 动态开辟数组存储（根据需求来设定数组长度）

        2. 顺序表接口模拟实现

        接口总览

        typedef int SLDatatype;
        typedef struct SeqList
        {
        	SLDatatype* a; //指向动态开辟的数组
        	int size;//数组中有效数据的个数
        	int capacity;//容器空间大小
        }SL;
        void SLInit(SL* psl); //顺序表初始化
        void SLDestory(SL* psl);//顺序表的销毁
        void SLPrint(SL* psl);//打印顺序表中的元素
        void SLPushBack(SL* psl, SLDatatype num);//尾插
        void SLPushFront(SL* psl, SLDatatype num);//头插
        void SLPopBack(SL* psl);//尾删
        void SLPopFront(SL* psl);//头删
        void SLInsert(SL* psl, int pos, SLDatatype num);//从任意位置插入数据
        int SLFind(SL* psl, SLDatatype num);//查找顺序表中的元素
        void SLErase(SL* psl, int pos);//删除任意位置的元素
        

        2.1 初始化数据和销毁容器

        初始化数据:

        设置指向数组的指针为空，有效数据个数和容器空间大小设置为0。

        void SLInit(SL* psl)
        {
        	assert(psl);
        	psl->a = NULL;
        	psl->size = psl->capacity = 0;
        }
        

        销毁容器：

        所释放动态开辟数组的空间，并设置指向的指针为空指针，有效数据个数和容器空间大小设置为0。

        void SLDestory(SL* psl)
        {
        	assert(psl); //判断psl是否为空
        	free(psl->a);
        	psl->a = NULL;
        	psl->size = psl->capacity = 0;
        }
        

        2.2 顺序表的尾插和尾删

        在尾插只前我们还要考虑容器是否有足够的空间，若是足够直接插入数据，若是不够则需要动态开辟数组。

        注意我们这里默认开辟两倍的空间，在实际中要需要根据需求来开辟容器空间。

        void SLCheckCapacity(SL* psl)
        {
        	assert(psl);
        	if (psl->size == psl->capacity)//若是容器中的有效元素等于容器间就要扩容
        	{
        		int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity;
        		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * newcapacity);
        		if (tmp == NULL)
        		{
        			perror("realloc");
        			return;
        		}
        		psl->a = tmp;
        		psl->capacity = newcapacity;
        	}
        }
        

        尾插：

        首先我们要判断容器空间大小，不足则扩容，足够则插入数据。尾插十分容易直接在数组末尾插入数据即可，有效数据加一。

        

        void SLPushBack(SL* psl, SLDatatype num)
        {
        	assert(psl);
        	SLCheckCapacity(psl);
        	psl->a[psl->size++] = num;
        }
        

        尾删：

        同样的尾删也很容易，只需要将有效数据size-1即可。

        void SLPopBack(SL* psl)
        {
        	assert(psl);
        	assert(psl->size > 0);
        	psl->size--;
        }
        

        2.3 头插和头删

        头插：

        首先还是容器大小的老问题，不足则扩容，足够则插入数据。头插与尾插不同的是，需要挪动数据将数组中的每一个元素向后移动一位，然后我们在空出的头位置插入数据。

        

        void SLPushFront(SL* psl, SLDatatype num)
        {
        	assert(psl);
        	 
        	SLCheckCapacity(psl);
        	int end = psl->size - 1;
        	while (end >= 0)
        	{
        		psl->a[end + 1] = psl->a[end];
        		end--;
        	}
        	psl->a[0] = num;
        	psl->size++;
        }
        

        头删：

        头删也是同样的，让开始位置的后一个数据向前覆盖，将有效数据size-1即可。

        

        void SLPopFront(SL* psl)
        {
        	assert(psl);
        	int begin = 1;
        	while (begin size)
        	{
        		psl->a[begin - 1] = psl->a[begin];
        		begin++;
        	}
        	psl->size--;
        }
        

        2.4 任意位置插入和删除数据

        任意位置插入数据：

        这里任意位置的数据就是容器中任意元素下标位置，同样的插入数据还使用挪动数据，将末尾到pos位置的数据向后挪动一位，在空出的pos位置插入数据。

        void SLInsert(SL* psl,int pos, SLDatatype num)
        {
        	assert(psl);
        	SLCheckCapacity(psl);
        	int end = psl->size;
        	while (end >= pos)
        	{
        		psl->a[end] = psl->a[end - 1];
        		end--;
        	}
        	psl->a[pos] = num;
        	psl->size++; 
        }
        

        任意位置删除数据：

        删除pos位置的数据，还是一样挪动覆盖。

        void SLErase(SL* psl,int pos)
        {
        	assert(psl);
        	int end = pos;
        	while (end size - 1)
        	{
        		psl->a[end] = psl->a[end + 1];
        		end++;
        	}
        	psl->size--;
        }
        

        2.5 查找数据

        通过遍历容器中的元素，若是查到则返回元素下标，若是没有找到则返回-1。

        int SLFind(SL* psl,SLDatatype num)
        {
        	assert(psl);
        	
        	for (int i = 0; i size; i++)
        	{
        		if (psl->a[i] == num)
        		{
        			return i;
        		}
        	}
        	return -1;
        }
        

        3. 顺序表的问题 ：

        1. 尾部插入的效率还行，头部或者中间插入删除（时间复杂度尾O(N)）、需要挪动数据、效率低下。
        2. 满了以后只能扩容。扩容式有一定的消耗的，扩容一般是存在一定的空间浪费。

           （假设空间是100满了，扩容到200，但是只需要插入120个数据，因此有80个空间就浪费掉了，一次扩的越多，可能浪费的越多，一次扩少了，那么有可能就会频繁的扩容）