提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

【数据结构】顺序表

数据结构 顺序
2023-06-13 09:18:27 时间

数据结构之顺序表：：

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;
	int size;存储数据的个数
	int capacity;存储空间的大小
}SL;
扩容:一次扩多了,存在空间浪费 一次扩少了,频繁扩容,效率损失
空间满了扩容2倍的原因:2倍比较合适
void SLInit(SL* ps1);
void SLDestory(SL* ps1);
void SLPrint(SL* ps1);
头插头删 尾插尾删
void SLPushBack(SL* ps1, SLDataType x);
void SLPushFront(SL* ps1, SLDataType x);
void SLPopBack(SL* ps1);
void SLPopFront(SL* ps1);
找到了返回下标 没有找到就返回-1
int SLFind(SL* ps1, SLDataType x);
顺序表在pos位置插入x
void SLInsert(SL* ps1, size_t pos, SLDataType x);
顺序表删除pos位置的值
void SLErase(SL* ps1, size_t pos);
void SLModify(SL* ps1, size_t pos, SLDataType x);

什么是线性表？

线性表是n个具有相同特性的数据元素的有限序列,线性表是一种在实际中广泛使用的数据结构. 常见的线性表有:顺序表 链表 栈 队列 字符串... 线性表在逻辑上是线性结构,也就是连续的一条直线,但是在物理结构上并不一定是连续的. 线性表在物理上存储时,通常以数组和链式结构的形式存储. 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储,在数组上完成数据的增删查改. 顺序表一般可以分为： 静态顺序表:使用定长数组存储元素. 

动态顺序表:使用动态开辟的数组存储. 

SeqList.c

1.顺序表初始化

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

2.顺序表扩容函数

void SLCheckCapacity(SL* ps1)
{
	检查容量
	if (ps1->size == ps1->capacity)
	{
		realloc没有开辟字节数 会在realloc(扩容时会对ps1所指向的空间进行检查)或free(释放了本身不属于你自己的空间)报错
		int newCapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps1->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps1->a = tmp;
		ps1->capacity = newCapacity;
	}
}

3.顺序表尾插

void SLPushBack(SL* ps1, SLDataType x)
{
	assert(ps1);
	SLCheckCapacity(ps1);
	ps1->a[ps1->size] = x;
	ps1->size++;
}

4.顺序表尾删

void SLPopBack(SL* ps1)
{
	assert(ps1);
	if (ps1->size == 0)
	{
		return;
	}
	//assert(ps1->size > 0);
	ps1->size--;
}

5.顺序表头插

void SLPushFront(SL* ps1, SLDataType x)
{
	assert(ps1);
	SLCheckCapacity(ps1);
	挪动数据
	int end = ps1->size - 1;
	while (end >= 0)
	{
		ps1->a[end + 1] = ps1->a[end];
		--end;
	}
	ps1->a[0] = x;
	ps1->size++;
}

6.顺序表头删

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

7.顺序表在pos位置插入x

void SLInsert(SL* ps1, size_t pos, SLDataType x)
{
	assert(ps1);
	assert(pos <= ps1->size);
	SLCheckCapacity(ps1);
	/*int end = ps1->size - 1;
	while (end >= (int)pos)// end即使改为int也会发生算术转换 头插依然失败
	{
		ps1->a[end + 1] = ps1->a[end];
		--end;
	}*/
	size_t end = ps1->size;
	while (end > pos)
	{
		ps1->a[end] = ps1->a[end-1];
		--end;
	}
	ps1->a[pos] = x;
	++ps1->size;
}

8.顺序表删除pos位置的值

void SLErase(SL* ps1, size_t pos)
{
	assert(ps1);
	assert(pos < ps1->size);
	size_t begin = pos;
	while (begin < pos->size - 1)
	{
		ps1->a[begin] = ps1->a[begin + 1];
		++begin;
	}
	ps1->size--;
}

9.顺序表销毁

void SLDestory(SL* ps1)
{
	assert(ps1);
	if (ps1->a)
	{
		free(ps1->a);
		ps1->a = NULL;
		ps1->capacity = ps1->size = 0;
	}
}

10.顺序表打印

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

11.顺序表的修改

void SLModify(SL* ps1, size_t pos, SLDataType x)
{
	assert(ps1);
	assert(pos < ps1->size);
	ps1->a[pos] = x;
}

12顺序表的查找

找到了返回下标 没有找到就返回-1
int SLFind(SL* ps1, SLDataType x)
{
	assert(ps1);
	for (int i = 0; i < ps1->size; ++i)
	{
		if (ps1->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

13.顺序表的问题及思考

问题：

1.中间/的头部的插入删除,时间复杂度为O(N)

2.增容需要申请空间,拷贝数据,释放旧空间会有不小的消耗

3.增容一般是呈二倍的增长,势必会有一定的空间浪费,例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间.

思考：

如何解决上述问题呢？下篇文章链表的结构来解答.

14.顺序表相关面试题

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

int remoteElement(int* nums, int numSize, int val)
{
	int src = 0, dst = 0;
	while (src < numSize)
	{
		if (nums[src] != val)
		{
			nums[dst] = nums[src];
			++src;
			++dst;
		}
		else
		{
			++src;
		}
	}
	return dst;
}

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

int removeDuplicates(int* nums, int numSize)
{
	int src = 0, dst = 0;
	while (src < numSize)
	{
		if (nums[src] == nums[dst])
		{
			++src;
		}
		else
		{
			++dst;
			nums[dst] = nums[src];
			++src;
		}
	}
	return dst + 1;
}

3. 合并两个有序数组。 

void merge(int* num1, int m, int* num2, int n)
{
	int end1 = m - 1, end2 = n - 1;
	int i = m + n - 1;
	while (end1 >= 0 && end2 >= 0)
	{
		if (nums1[end1] > nums2[end2])
		{
			nums1[i] = nums1[end1];
			--i;
			--end1;
		}
		else
		{
			nums1[i] = nums2[end2];
			--i;
			--end2;
		}
	}
	end2结束 nums2的数组都拷贝过去了 那么不用处理
	end1结束 nums1的数组都拷贝过去了 那么需要把nums2剩下的数据拷贝过去
	while (end2 >= 0)
	{
		nums1[i] = nums2[end2];
		--i;
		--end2;
	}
}

相关文章