【数据结构与算法】第2课—数据结构之顺序表

1. 线性表

• 线性表：n个具有相同特性的数据元素的有限序列，常见的线性表有：顺序表、链表、栈、队列和字符串等
• 线性表在逻辑结构上是一条连续的直线，在物理结构上不一定是连续的
• 线性表在物理上存储时，通常以数组和链式结构的形式进行存储

2. 顺序表

• 顺序表是用一段物理地址连续的存储单元依次存储数据数据元素的线性结构，一般情况下采用数组存储
• 顺序表的底层结构是数组，对数组进行封装，实现常用的增删改查等接口
• 顺序表又分为静态顺序表和动态顺序表
• 由于静态顺序表的内存大小固定，因此常常使用的是动态顺序表

2.1 动态顺序表初始化

2.2 尾插

2.3 头插

2.4 尾删

2.5 头删

2.6 查找数

2.7 指定位置插入数据

2.8 指定位置删除数据

2.9 销毁

3. 练习

3.1 练习1—移除元素

• 举个简单的例子

//练习1
//给定数组，移除等于val的数
//例如:nums[]={ 2, 2, 3, 3},val = 3;
//移除后:nums[]={ 2, 2};
int removeElement(int* nums, int numsSize, int val)
{
	int src = 0;
	int dst = 0;
	while (src < numsSize)
	{
		if (nums[src] != val)
		{
			nums[dst] = nums[src];
			dst++;
		}
		src++;
	}
	return dst;
}

3.2 练习2—删除有序数组中的重复项

• 举个简单的例子

//练习2
//删除有序数组的重复项
int removeDuplicates(int* nums, int numsSize)
{
	int dst = 0;
	int src = dst + 1;
	while (src < numsSize)
	{
		if (nums[src] != nums[dst])
		{
			dst++;
			nums[dst] = nums[src];
			src++；
		}
		else
			src++;
	}
	return dst + 1;
}

//优化
int removeDuplicates(int* nums, int numsSize)
{
	int dst = 0;
	int src = dst + 1;
	while (src < numsSize)
	{
		if (nums[src] != nums[dst])
		{
			dst++;
			if (src != dst)
			{
				nums[dst] = nums[src];
			}
		}
		src++;
	}
	return dst + 1;
}

3.3 练习3—合并有序数组

• 拿思路2举个简单的例子

• 另外还需要考虑一个问题

//练习3:合并有序数组
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
	int src = m - 1;
	int dst = n - 1;
	int index = m + n - 1;
	while (src >= 0 && dst >= 0)
	{
		if (nums1[src] > nums2[dst])
			nums1[index--] = nums1[src--];
		else
			nums1[index--] = nums2[dst--];
	}
	//若nums2数组元素在src越界后还未全部放入
	while (dst >= 0)  
		nums1[index--] = nums2[dst--];
}