【C/C++】动态顺序表详解（附完整源码）

admin • • C/C++

本章内容

写在前面

1.静态与动态是指什么？

2.动态顺序表结构的定义

3.动态顺序表的函数接口实现

4.动态顺序表的问题及思考

5.关于顺序表的OJ题

6.OJ答案及解析

1.移除元素

2.删除有序数组中的重复项

​3.合并两个有序数组

7.动态顺序表完整源码

1.SeqList.h

2.SeqList.c

写在前面

上一章我们学习了静态顺序表的增删查改，并认识了静态顺序表的存储结构与静态顺序表的在不同场景下的优劣。静态顺序表与动态顺序表都叫做顺序表，只不过我们平时口头所提的顺序表指的是动态顺序表。静态顺序表的局限性太高，无法应对各种复杂的情况所以我们几乎不用它。本章我们就来学习动态顺序表的实现。

1.静态与动态是指什么？

静态顺序表：顺序表的大小固定，存储的数据个数有限。

#define N 5
typedef int SLDataType;

//静态顺序表
typedef struct SeqList
{
	SLDataType a[N];//定长数组
	int size;//记录存储多少个有效数据
}SeqList;

动态顺序表：运用动态内存管理，可按需调整顺序表的大小。

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int size;//记录有多少个有效数据
	int capacity;//记录顺序表的容量大小
}SeqList;

2.动态顺序表结构的定义

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int size;//记录有多少个有效数据
	int capacity;//记录顺序表的容量大小
}SeqList;

3.动态顺序表的函数接口实现

//初始化顺序表
void SLInit(SeqList* ps);
//释放空间
void SLDestroy(SeqList* ps);
//检查顺序表是否已满
void CheakCapacity(SeqList* ps);
//动态顺序表的尾插
void SLPushBack(SeqList* ps, SLDataType data);
//动态顺序表的尾删
void SLPopBack(SeqList* ps);
//动态顺序表的头插
void SLPushFront(SeqList* ps, SLDataType data);
//动态顺序表的头删
void SLPopFront(SeqList* ps);
//pos位置插入数据
void SLInsert(SeqList* ps, int pos, SLDataType data);
//pos位置删除数据
void SLErase(SeqList* ps, int pos);
//查找数据
int SLFind(SeqList* ps, SLDataType data, int begin);
//判断数组是否已满
bool IsFull(SeqList* ps);
//打印存储的数据
void SLPrint(SeqList* ps);

以下是各个接口的实现：

void SLInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
void SLDestroy(SeqList* ps)
{
	assert(ps);
	//若ps->a不为NULL，则释放空间
	if (ps->a)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = ps->size = 0;
	}
}
void CheakCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		//若是第一次扩容，则大小为4；
		//若不是第一次，则每次扩容为之前容量的2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//检查是否做到扩容
	printf("扩容成功,现在的容量为:%dn", ps->capacity);
}
void SLPushBack(SeqList* ps, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//插入数据
	ps->a[ps->size] = data;
	ps->size++;
}
void SLPopBack(SeqList* ps)
{
	assert(ps);
	ps->size--;
}

void SLPushFront(SeqList* ps, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//挪动数据
	for (int i = ps->size - 1; i >= 0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	//插入数据
	ps->a[0] = data;
	ps->size++;
}
void SLPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//挪动数据
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

void SLInsert(SeqList* ps, int pos, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//挪动数据
	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	//插入数据
	ps->a[pos] = data;
	ps->size++;
}
void SLErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);
	//挪动数据
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
int SLFind(SeqList* ps, SLDataType data, int begin)
{
	assert(ps);
	assert(begin < ps->size);
	for (int i = begin; i < ps->size; i++)
	{
		if (ps->a[i] == data)
		{
			return i;
		}
	}
	return -1;
}

void SLPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("n");
}

4.动态顺序表的问题及思考

动态顺序表与静态顺序表的差别仅仅在与一个容量是固定的，一个可以按需扩容。

动态顺序表看似灵活性有所提高但仍存在着空间浪费，特别是扩容次数越多，越容易造成空间浪费。那么有没有其他的数据结构可以解决这个问题呢？答案是肯定的。这个神奇的数据结构叫做链表，它是一种基于节点的数据结构。下一章我们就会见到它。

动态顺序表和静态顺序表都称为顺序表，它们的性能是相同的。关于顺序表的性能优劣我已经在上一章介绍过了，点击小卡片即可跳转。

静态顺序表详解icon-default.png?t=MBR7http://t.csdn.cn/zwU7I

5.关于顺序表的OJ题

1.移除元素

原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。 

移除元素icon-default.png?t=MBR7https://leetcode.cn/problems/remove-element/

2.删除有序数组中的重复项

删除有序数组中的重复项icon-default.png?t=MBR7https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

3.合并两个有序数组

合并两个有序数组icon-default.png?t=MBR7https://leetcode.cn/problems/merge-sorted-array/

6.OJ答案及解析

1.移除元素

题目要求不能开辟新的数组，所以我们的做法是遇到等于val的元素时，将数组末尾的元素依次倒着覆盖掉等于val的元素。

代码实现;

int removeElement(int* nums, int numsSize, int val){
    int i=0;
    while(i<numsSize)
    {
        while(val==nums[i]&&i<numsSize)
        {
           nums[i]=nums[numsSize-1];
           numsSize--;
        }
        i++;
    }
    return numsSize;

}

以数组nums={3,2,5,6,3,5},val=3为例。

第一步，检查索引为0处的值是否等于val；

 第二步，将索引为5处的值拷贝到索引为0处；

 第三步，检查索引为1处的值；

第四步，检查索引为2处的值；

 第五步，检查索引为3处的值；

 第六步，检查索引为4处的值；

 第七步，将索引为4处的值拷贝到索引为4处；

此时i已经大于numsSize，循环结束。 

2.删除有序数组中的重复项

本题我采用的是双指针的方式，p1来记录当前位置，p2来寻找与p1处的值不相同的元素。

代码实现：

int removeDuplicates(int* nums, int numsSize){
    int* p1=nums;
    int* p2=nums+1;
    int i=0;
    int returnSize=1;//至少有一个元素
    for(i=0;i<numsSize-1;i++)
    {
        if(*p1!=*(p2+i))
        {
            *(++p1)=*(p2+i);
            returnSize++;
        }
    }
    return returnSize;
}

以数组nums={0,0,1,1,1,2,2,3,3,4}为例。

 

3.合并两个有序数组

这道题目我采用的是双指针的方式。p1指向nums1，p2指向nums2。另外需要额外开辟一个数组arr，当合并完成之后再将arr里的内容拷贝到nums1中。

代码实现：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i=0;
    int j=0;
    int arr[200]={0};
    int* p1=nums1;
    int* p2=nums2;
    int k=0;//记录arr数组里元素的个数
    //检查数组是否为空
    if(nums2Size==0)
        return;
    //将nums1或nums2任何一个数组拷贝完成之后就结束
    while(i<nums1Size-nums2Size&&j<nums2Size)
    {
        if(p1[i]<p2[j])
        {
            arr[k]=p1[i];
            i++;
        }
        else
        {
            arr[k]=p2[j];
            j++;
        }
        k++;
    }
    //如果nums1先结束，将nums2中剩余的元素全部拷贝到arr
    if(i==nums1Size-nums2Size)
    {
        for(;j<nums2Size;j++)
        {
            arr[k++]=p2[j];
        }
    }
    //如果nums2先结束，将nums1中剩余的元素全部拷贝到arr
    if(j==nums2Size)
    {
        for(;i<nums1Size-nums2Size;i++)
        {
            arr[k++]=p1[i];
        }
    }
    //将arr中的元素拷贝回nums1
    for(k=0;k<nums1Size;k++)
    {
        nums1[k]=arr[k];
    }
}

7.动态顺序表完整源码

1.SeqList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int size;//记录有多少个有效数据
	int capacity;//记录顺序表的容量大小
}SeqList;

//初始化顺序表
void SLInit(SeqList* ps);
//释放空间
void SLDestroy(SeqList* ps);
//检查顺序表是否已满
void CheakCapacity(SeqList* ps);
//动态顺序表的尾插
void SLPushBack(SeqList* ps, SLDataType data);
//动态顺序表的尾删
void SLPopBack(SeqList* ps);
//动态顺序表的头插
void SLPushFront(SeqList* ps, SLDataType data);
//动态顺序表的头删
void SLPopFront(SeqList* ps);
//pos位置插入数据
void SLInsert(SeqList* ps, int pos, SLDataType data);
//pos位置删除数据
void SLErase(SeqList* ps, int pos);
//查找数据
int SLFind(SeqList* ps, SLDataType data, int begin);
//判断数组是否已满
bool IsFull(SeqList* ps);
//打印存储的数据
void SLPrint(SeqList* ps);

2.SeqList.c

#define _CRT_SECURE_NO_DEPRECATE 1
#include"SeqList.h"

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

void SLDestroy(SeqList* ps)
{
	assert(ps);
	//若ps->a不为NULL，则释放空间
	if (ps->a)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = ps->size = 0;
	}
}

void CheakCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		//若是第一次扩容，则大小为4；
		//若不是第一次，则每次扩容为之前容量的2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//检查是否做到扩容
	printf("扩容成功,现在的容量为:%dn", ps->capacity);
}

void SLPushBack(SeqList* ps, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//插入数据
	ps->a[ps->size] = data;
	ps->size++;
}

void SLPopBack(SeqList* ps)
{
	assert(ps);
	ps->size--;
}

void SLPushFront(SeqList* ps, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//挪动数据
	for (int i = ps->size - 1; i >= 0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	//插入数据
	ps->a[0] = data;
	ps->size++;
}

void SLPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//挪动数据
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

void SLInsert(SeqList* ps, int pos, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//挪动数据
	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	//插入数据
	ps->a[pos] = data;
	ps->size++;
}

void SLErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);
	//挪动数据
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

int SLFind(SeqList* ps, SLDataType data, int begin)
{
	assert(ps);
	assert(begin < ps->size);
	for (int i = begin; i < ps->size; i++)
	{
		if (ps->a[i] == data)
		{
			return i;
		}
	}
	return -1;
}

void SLPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("n");
}

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>