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

zl程序教程

您现在的位置是：首页 >  数据库

当前栏目

【数据结构初阶】顺序表

存储 数组 数据 数据结构
2023-04-18 16:07:53 时间

【数据结构——调试+思考+画图+写代码】

【重在梳理代码逻辑，标记数组元素下标】

目录

前言

顺序表 

静态顺序表

动态顺序表

实现一个顺序表

梳理顺序表逻辑

代码实现

SeqList.h文件

SeqList.c文件

test.c文件

编程题——顺序表的变相考察

移除元素

删除有序数组中的重复项

合并两个有序数组

前言

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表的数据在存储的时候是成一条线性相互紧邻存放的。

线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，是连续的一条直线。但是在物理结构上（内存）并不一定是连续的。线性表在物理上存储时，通常以数组和链式结构的形式存储。顺序表是在物理上是线性连续的，链表是不连续的。

顺序表 

顺序表就是数组。管理数组、存储数据的结构就是线性表。把数据管理起来，管理就是增删查改，即完成各个函数的实现。

数组的缺陷：在支持C99之前，数组的长度是固定的。即使是变长数组，也会面临不知道所存数据的多少。

顺序表是一段连续的物理空间，就像（是）数组。

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组 上完成数据的增删查改。

顺序表相比数组还有一些额外的要求，要求存储的数据必须从0开始，必须从前向后依次连续存储，不能跳跃存储。比如数组有100个字节的空间就可以随便访问任意一个位置；而顺序表不能在任意位置存储数据，只能从第一个位置连续存储，若存2个数据则必须第0个位置存1个，第1个位置存1个。顺序表的优势：因为空间连续，所以在其空间内可以任意访问；缺点是空间释放要整体释放。

顺序表一般可以分为：静态顺序表和动态顺序表。

静态顺序表

静态顺序表使用定长数组（静态数组）存储元素——不太实用。

//1.结构的定义
#define N 100
struct SeqList//顺序表的结构体
{
	int a[N];
	int size;//记录存储了多少个数据
};

//2、拿这个结构定义一个变量，是对这个变量进行初始化

N是固定大小的，存在的问题是：开小了不够用；开大了存在空间浪费，不够灵活满足需求。

动态顺序表

动态顺序表使用动态开辟的数组存储——在实际中更实用

struct SeqList
{
	SLDataType* a;//用数组的指针
	int size;//记录存储数据个数
	int capacity;//存储空间大小
};

通常对数据结构首先进行操作的是在增删查改之前需要的初始化函数。

顺序表常见的几个操作是在尾部的插入和删除、头部的插入和删除。

实现一个顺序表

梳理顺序表逻辑

顺序表的头部插入：扩容——移动数据

头部插入，需要保证数据是连续的，并且保证从头到尾存储，则从头部插入数据就需要把原有数据向后移动，这里必须从后向前移动。
把4向后移一个，把3向后移一个，把2向后移一个，把1向后移一个，把0向后移一个，然后在头部放入这个数据。
这里每向后移一个，为了防止越界需要检查空间是否需要扩容。

使用realloc扩容的图解：

realloc有两种可能性：
1. 原地扩容——效率高，返回原有空间地址;
2. 异地扩容——拷贝原有数据，释放原有空间，返回新空间起始地址。

移动数据：
从后向前移，最后一个数据的下标是size-1。

顺序表的头部删除：

需要保证顺序表的数据必须从0开始存放，并且是连续的。

所以有两种写法——begin的起始位置不同，导致结束位置不同。

(1) 把数据从前向后移，把后一个位置向前覆盖。

(2) 把数据从前向后移，把当前位置向前移。

头插和头删的时间复杂度是O(N)；

尾插和尾删的时间复杂度是O(1)。

所以顺序表尽量不要用头插和头删，头插和头删的效率相对低，需要移动数据和覆盖数据；而尾插和尾删的效率相对高。

顺序表还提供了2个接口：在某个位置插入数据和删除数据，这个位置是下标。

在pos位置插入数据：

当在pos=0位置插入数据时的第三种解决方法图解：

可以避开发生整型提升造成死循环，既还可以用size_t定义下标的数据类型，也可以不强转就实现不越界访问。——这种方法相对方法1的改变数据类型和方法2的强制转换更好。

删除pos位置数据：

需要从前向后移，把后一个位置的数据向前移从而覆盖要删除的数据。

也有两种写法：

代码实现

SeqList.h文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//动态的顺序表:

//为了不能只满足存储int的类型数据，
//所以为了存储各种类型的数据,对int进行typedef

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//记录存储的数据个数
	int capacity;//存储空间大小
}SeqList;

//初始化函数
void SeqListInit(SeqList* psl);
//销毁动态开辟的空间
void SeqListDestroy(SeqList* psl);

//检查空间，如果满了，进行增容
void SeqListCheckCapacity(SeqList* psl);

//顺序表打印
void SeqListPrint(SeqList* psl);//这里是为了减少拷贝，结构体相对指针大，所以传的是地址

//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
//顺序表尾删
void SeqListPopBack(SeqList* psl);

//顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//顺序表头删
void SeqListPopFront(SeqList* psl);

//在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
//删除pos位置数据
void SeqListErase(SeqList* psl, size_t pos);

//顺序表查找
int SeqListFind(SeqList* Psl, SLDataType x);

//顺序表修改
void SeqListModify(SeqList* Psl, size_t pos, SLDataType x);//查找下标也可以进行

SeqList.c文件

#include "SeqList.h"
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

void SeqListDestroy(SeqList* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->capacity = psl->size = 0;
}


void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);
	//如果满了，扩容：
	if (psl->size == psl->capacity)
	{
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);//传个原来的空间和新的空间大小
		if (tmp == NULL)
		{
			printf("realloc fail
");
			exit(-1);//终止程序
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;
		}
	}

}


//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);

	//SeqListCheckCapacity(psl);
	//psl->a[psl->size] = x;
	size是有效数据个数，下标是从0开始的，则size作为下标是最后一个数据的下一个
	位置，而尾插插入的位置就是最后一个数据的下一个位置，再让size++，需要扩容检查

	//psl->size++;

	//复用SeqListInsert:
	SeqListInsert(psl, psl->size, x);

}


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

//顺序表尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	psl->a[psl->size - 1] = 0;
	//if (psl->size > 0)//保证没有数据时不需要删了
	//{
	//	psl->size--;
	//}
	size是指向最后一个数据的下一个位置，尾删就是把size-1这个位置删掉，即只需要size--就可以达到效果。
	因为size标识有效数据的个数，要删除的位置还在，向前移动size的位置就是减少有效数据，相当于尾删。

	//复用SeqListErase：
	SeqListErase(psl, psl->size - 1);//尾删，就是删除下标为size-1的数据

}

//顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	/*SeqListCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;*/

	//复用SeqListInsert:
	SeqListInsert(psl, 0, x);//在下标为0位置处插入数据就是头插

}
//顺序表头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	//if (psl->size > 0)
	//{
	//	int begin = 1;//用第2种写法写
	//	while (begin < psl->size)
	//	{
	//		psl->a[begin - 1] = psl->a[begin];
	//		++begin;
	//	}
	//	--psl->size;
	//}
	SeqListErase(psl, 0);
}

//1、第一种方法：void SeqListInsert(SeqList* psl, int pos, SLDataType x)然后在温和检查时要检查pos大于0
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
//暴力检查
	assert(psl);
	//这里pos的类型是size_t;
//温和检查
	if (pos > psl->size)
	{
		printf("pos 越界：%d
", pos);
		return;
		//exit(-1);
	}
//暴力检查
	//assert(pos <= psl->size);
	
	SeqListCheckCapacity(psl);//若这里没有扩容，直接向后移数据、插入（增加一个数据）是检查不出越界的！
	//size_t end = psl->size - 1;//当size是0时，在0位置插入，0-1是-1，-1赋
//值给end，end是无符号，则end就变成了42亿之多，是整形的最大值，就不会跳出循插入值，会一直在循环中，所以end应该用有符号的数据类型
	
//	int end = psl->size - 1;
//	//while (end >= pos)//此时end与pos比较，end会被提升为无符号。又会访问越界
//第2种方法：强转
//	while (end >= (int)pos)
//	{
//		psl->a[end + 1] = psl->a[end];
//		--end;
//	}

//第3种方法：
	size_t end = psl->size;
	//当必须在pos=0位置插入，又要保证end>=pos,则end就必须小于0，而又要避开无符号，
	//为避免这种互相矛盾的情况，那么让end的位置在size处
	while (end > pos)//等于时就终止了，所以end就不需要到-1,end也不能到-1,因为end是无符号
	{
		psl->a[end] = psl->a[end-1];
		--end;
	}
	

	psl->a[pos] = x;
	psl->size++;

}
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);//pos是无符号，一定大于0，注意不能pos等于size，没有意义

	size_t begin = pos + 1;//此时没有有无符号的问题，begin最少是1
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}
	psl->size--;
}


int SeqListFind(SeqList* psl, SLDataType x)//按值查找
{
	assert(psl);
	for (int i = 0; i < psl->size; ++i)
	{
		if (psl->a[i] == x)
		{
			return i;//查找的返回值是下标，是大于等于0的
		}
	}

	return -1;
}


void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos <= psl->size);//检查pos位置的合法性
	psl->a[pos] = x;
}

test.c文件

#include "SeqList.h"
void TestSeqList1()
{
	SeqList s;//定义结构体变量
	//初始化这个变量：
	SeqListInit(&s);//形参指向实参，传地址可以通过改变形参影响实参

	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPushBack(&s, 0);
	SeqListPrint(&s);//1 2 3 4 5 0

	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPrint(&s);//1 2 3 4

	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPrint(&s);

	SeqListPushBack(&s, 10);
	SeqListPushBack(&s, 20);
	SeqListPrint(&s);

	//SeqListPrint(NULL);
	//int a[10];
	//a[10] = 1;
	//a[10] = 1;
	//a[10] = 1;
	//a[10] = 1;
	//a[10] = 1;
}

void TestSeqList2()
{
	/*int* p = (int*)malloc(sizeof(int) * 10);
	printf("%p
", p);

	int* p1 = (int*)realloc(p, sizeof(int) * 100);
	printf("%p
", p1);*/

	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, -1);
	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, -1);
	SeqListPrint(&s);
}

void TestSeqList3()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPrint(&s);

	SeqListInsert(&s, 10, 100);//异常插入
	SeqListInsert(&s, 1, 20);//正常插入
	SeqListInsert(&s, 5, 50);//pos == size，相当于尾插
	SeqListInsert(&s, 0, 50);//在0位置插入，相当于头插
							 
    //SeqListPushBack(&s, 5);
	SeqListPrint(&s);

	SeqListDestroy(&s);
}

void TestSeqList4()
{
	//测试：
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);//下标是0
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);//下标是4
	SeqListPrint(&s);

	SeqListErase(&s, 4);//删尾，这个4是下标是为4的数据
	SeqListPrint(&s);

	SeqListErase(&s, 0);//删头，是下标为0的数据
	SeqListPrint(&s);

	SeqListErase(&s, 1);//删中间的数据，删下标是1的数据
	SeqListPrint(&s);

}


void TestSeqList5()
{
	SeqList s;
	SeqListInit(&s);
	
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPushFront(&s, -1);//头插
	SeqListPushFront(&s, -2);//头插
	SeqListPrint(&s);

	SeqListPopFront(&s);//头删
	SeqListPopFront(&s);//头删
	SeqListPopBack(&s);//尾删
	SeqListPopBack(&s);//尾删
	SeqListPrint(&s);

}


void TestSeqList6()
{
	SeqList s;
	SeqListInit(&s);

	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPushFront(&s, -1);
	SeqListPushFront(&s, -2); 
	SeqListPrint(&s);
	SeqListModify(&s, 3, 100000);//把下标为3的位置（第4个数据）修改成100000
	SeqListPrint(&s);

	int pos = SeqListFind(&s, 4);//查找数字4
	if (pos != -1)
	{
		SeqListModify(&s, pos, 40);
	}

	SeqListPrint(&s);

}


int main()
{
	TestSeqList6();

	return 0;
}

//参考：
//void menu()
//{
//	printf("************************************
");
//	printf("*******1.尾插数据  2.头插数据*******
");
//	printf("*******3.尾删数据  4.头删数据*******
");
//	printf("*******5.打印数据  6.查找数据*******
");
//	printf("**************-1.退出***************
");
//	printf("************************************
");
//}
//
//int main()
//{
//	/*TestSeqList5();*/
//	SeqList s;
//	SeqListInit(&s);
//
//	int option = -1;
//	/*scanf("%d
", &option);*///两处错误！
//	
//	do
//	{
//		menu();
//		printf("请选择你的操作:>
");
//		scanf("%d", &option);
//		if (option == 1)
//		{
//			printf("请输入你要尾插的数据:>");
//			int val = 0;
//			scanf("%d", &val);
//			SeqListPushBack(&s, val);
//		}
//		else if (option == 2)
//		{
//			printf("请输入你要头插的数据:>");
//			int val = 0;
//			scanf("%d", &val);
//			SeqListPushFront(&s, val);
//		}
//		else if (option == 3)
//		{
//			SeqListPopBack(&s);
//		}
//		else if (option == 4)
//		{
//			SeqListPopFront(&s);
//		}
//		else if (option == 5)
//		{
//			SeqListPrint(&s);
//		}
//		else if (option == 6)
//		{
//			printf("请输入你要查找的数据:>");
//			int val = 0;
//			scanf("%d", &val);
//			SeqListFind(&s, val);
//		}
//
//	} while (option != -1);
//
//	SeqListDestroy(&s);
//	return 0;
//}

 重在梳理逻辑，全面测试。

编程题——顺序表的变相考察

移除元素

27. 移除元素 - 力扣（LeetCode）

给你一个数组nums和一个值 val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。

（原地是指）不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]

解题：

思路1——
        遍历数组找到val，依次移动数据进行覆盖；遍历数组查找val，依次移动数据进行覆盖……
        时间复杂度：O(N^2)，最坏的情况是在不知道数组中全是val或大部分是val，如｛22222222222｝需要移动：N-1、N-2、N-3等是个等差数列，其和就是时间复杂度N^2。没有val是相对较好的情况，只需要遍历一遍数组，时间复杂度是O(N)。
        空间复杂度：O(1)

思路2——

        把不是val的值拷贝到新数组。若是对原数组删除，则把新数组拷贝回去。

这种方式是双指针，是两个下标在走。        

        时间复杂度：O(N)

        空间复杂度：O(N) ，不符合要求。

思路3——

        优化思路2，采用双指针。

        在原数组中进行：不开dst指向的新数组，src指向原数组的内容，dst是目标要放的数组（还是原数组）。不是val，把str指向的位置放到dst中，自己位置放到自己位置，str++、dst++，把是val的值放到“新”数组中；是val，即是要删除的数字，则只需要src++即可。

原数组直接充当了目标数组，被删除的位置可以直接被覆盖。要返回的新长度就是dst。

实现代码：

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

}

删除有序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（LeetCode）

给你一个 升序排列 的数组nums，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持 一致 。

不要使用额外的空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

示例：

输入：nums = [1,1,2]
输出：2, nums = [1,2]

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]

解题：去重，可以采用双指针。

若是使用额外空间，多个重复出现的数字，就只放一个到新数组中。

不用额外的数组，则就在原数组中处理数据：在同一个数组中有原数组和目标数组。

思路1：

一种实现方式：依次找区间，在一个相同数的区间中只放一个数字到dst目标数组中。

另一种实现方式，src在1位置处：

走完一个相等的区间，就把前一个区间中最后一个值给dst。

这里src走到最后，没有src指向的内容，也就不能和nums[src-1]进行比较，也就不能放最后一个值。

当src结束的时候，一定把src-1指向的内容放进去。

若最后一个区间是几个相同的数字：

发现无论最后是一串连续相等的值，还是最后的值只出现一次，最后一个值都没有放进去。因为要把一个值放过去一定是把一段区间走完，走到下一个位置和上一个位置的值不相等的时候才会放值到目标数组。

所以最后一个值是一定要放进去的。（无论最后是一串连续相等的值，还是最后的值只出现一次）

本质是：

src和src-1位置的值不相等时，前一段重复值区间已经走完了，那么把最后一个值保留放到dst位置。

实现代码：

int removeDuplicates(int* nums, int numsSize){
    int src = 1, dst = 0;
    while(src < numsSize)
    {
        if(nums[src] == nums[src-1])
        {
            src++;
        }
        else
        {
            nums[dst] = nums[src-1];
            src++;
            dst++;
        }
    }
    nums[dst] = nums[numsSize-1];
    dst++;//像上面一样，保证dst是在每次当前最后一个数据的下一个位置（的下标），所以dst就是数据个数
    return dst;

}

        时间复杂度是：O(N)

思路3——三指针

i和j去找区间，把一段区间走完，再把区间的第一个值放过去。

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

        时间复杂度是：O(N)

或另一种代码实现：

 cur和next去找一段一段的区间，把一段连续的区间走完，再把区间的第一个值放过去。

int removeDuplicates(int* nums, int numsSize)
{
    if (numsSize == 0)
    {
        return 0;
    }
    int dst = 0;
    int cur = 0, next = 1;
    while (next < numsSize)
    {
        if (nums[cur] != nums[next])
        {
            nums[dst++] = nums[cur++];
            ++next;
        }
        else
        {
            while (next < numsSize && nums[cur] == nums[next])
            {
                ++next;
            }

            nums[dst] = nums[cur];
            ++dst;
            cur = next;
            ++next;
        }
    }
    if (cur < numsSize)
    {
        nums[dst++] = nums[cur];
    }

    return dst;
}

        时间复杂度是：O(N)

注意若两层循环判断的是一个变量，如这一个代码片，两层循环都是next判断结束，时间复杂度是O(N)，都是next在往后走。若是：

while (j < n)
{
	//……
    j = i; 
	while (……j < n; ……)
	{
		//……
	}
}

这种一般是等差数列，时间复杂度是O(N^2)

合并两个有序数组

88. 合并两个有序数组 - 力扣（LeetCode）

给你两个按非递减顺序排列的整数数组nums1和 nums2，另有两个整数m和n ，分别表示nums1 和nums2中的元素数目。

请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1中。为了应对这种情况，nums1的初始长度为m + n，其中前m个元素表示应合并的元素，后n个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 ：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]

设计实现一个时间复杂度为O(m + n)的算法。

解题：

非递减顺序，不完全增序，但后一个数据一定不小于前一个数据。

题目中的时间复杂度是O(m+n)是不知道m和n谁大。

思路1——
memmove + sort
                  （冒泡——O(N^2)）
                  （qsort——O(N*logN)

思路2——
归并：
归并的核心思想：两个有序序列合并成（归并）有序的序列就是：依次比较，每次把小的数据放到归并数组中。（无序要变成有序后才能用归并实现）
本题是非递减序列说明是有序的。
若开一个额外的数组a：

        空间复杂度是O(N)
        时间复杂度是：O(m+n)

思路3——
不开额外数组，则空间复杂度为O(1)：
优化思路2：
正取小，倒取大。谁大谁--，

另一种情况：

发现：

nums1和nums2有一个结束就结束了。

如果nums2数组先结束，说明nums2数组的元素都拷贝放到nums1数组中了，则nums1剩下的数据就不用处理了，就放在原数组的原位置；

如果nums1数组先结束，说明nums1数组的元素拷贝放到nums1后面了，则nums2数组剩下的数据就需要拷贝放到nums1数组中。

实现代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
	//这里nums1Size是6，m是3, nums2Size是3，n是3
	//nums1Size和nums2Size这个参数没什么用，是废参数，因为nums1Size就是m+n

	int i = m - 1, j = n - 1;
	int dst = m + n - 1;//或写成int dst = nums1Size1-1;

	while (i >= 0 && j >= 0)
	{
		//反向思维：（有一个结束就结束了）有一个不满足条件就不进入循环，循环写的是继续的操作

		if (nums1[i] > nums2[j])
		{
			nums1[dst--] = nums1[i--];
		}
		else
		{
			nums1[dst--] = nums2[j--];
		}

	}

	while (j >= 0)
	{
		nums1[dst--] = nums2[j--];
	}

}

注意：

while (i >= 0 && j >= 0)

平常写while语句时，写的是继续的操作，判断的是结束的条件，而这里是判断的是继续的操作。

杂七杂八的知识碎片：

一般情况下很少使用柔型数组。使用柔型数组空间不够了则还需要malloc开辟空间，柔型数组和普通动态的区别是开整个数组空间的时候是把额外的数据也开到一块空间上还是分开来开。

C++是兼容C的，可以在C++中写C语言，void SeqListInit（SeqList* psl);也可以写成：void SeqListInit（SeqList& psl);这是C++中的语法，表示引用，不是取地址。有些地方可以替代指针。

当原有空间是空为0时（realloc的第一个参数是NULL，即0），用realloc对原有空间扩容就相当于mealloc。

断言的方式较暴力，是一定不要出现这种情况下才会去断言，比较温和的方式加 if 条件加return判断。

不是所有的越界都能被检查出来，所有的编译器对越界的检查都是一种抽查，并且对越界的检查都是在程序结束的时候进行检查的。通常越界是在数组结束附近的位置检查，其他远距离的越界行为是检查不到的。

动态开辟的内存是在free释放的时候检查越界的。

数据结构各有优缺点，没有一个能包揽各种操作，不同的场景需要用不同的数据结构。

当判断得出malloc、realloc返回值失败时通常用exit(-1)使程序结束。（操作系统已经没有内存可以使用）这是一种暴力的检查方式。

温和检查方式：if语句、return；——为假不会出现很严重的问题。

暴力检查方式：断言、exit(-1)。——是一定不能为假，为假造成的后果相对严重。

程序正常终止都是返回0的，在调试控制台界面会看到“代码为 0”，若是其他值就表示是异常退出的。

静态数组是在函数结束的时候检查越界，动态开辟的数组就会在free的时候检查。所以在free的时候报错了，很有可能就是程序越界了。

一个操作符进行运算的时候，如果两个操作数的类型不一样，就会有一个被提升成二者一样类型，才会进行比较，通常是向范围大的提升，当有符号和无符号比较的时候，会向无符号提升。

OJ题很少有时间复杂度的限制。

相关文章