假如面试官让你手撕顺序表，该如何快速准确的交出一份让面试官满意的答卷？

目录

1.概念

2结构

3.顺序表的接口

4.与顺序表相关的面试题

5.顺序表的优缺点

1.概念

顺序表是一段物理上连续存储数据元素的线性结构，一般使用数组存储，在数组上完成数据的增删查改。

2结构

采用动态增长的方式实现顺序表

typedef int SeqListDatatype;
typedef struct SeqList
{
	SeqListDatatype* a;
	int capacity;
	int size;
}SeqList;

capacity:标识容量

size:标识数据个数

3.顺序表的接口

void SeqListInit(SeqList* psl);

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

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

void CheckCapacity(SeqList* psl)
{
	assert(psl);
	int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
	SeqListDatatype* tmp = (SeqListDatatype*)realloc(psl->a, sizeof(SeqList) * newCapacity);
	if (tmp == NULL)
	{
		perror("realloc fail:");
		exit(-1);
	}
	psl->a = tmp;
	psl->capacity = newCapacity;
}

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

void SeqListPushBack(SeqList* psl, SeqListDatatype x)
{
	assert(psl);
	if (psl->capacity == psl->size)
	{
		CheckCapacity(psl);
	}
	psl->a[psl->size] = x;
	psl->size++;
}

// 顺序表尾删
void SeqListPopBack(SeqList* psl);

void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	assert(psl->size > 0);
	psl->size--;
}

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

void SeqListPushFront(SeqList* psl, SeqListDatatype x)
{
	assert(psl);
	if (psl->capacity == psl->size)
	{
		CheckCapacity(psl);
	}
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}

// 顺序表头删
void SeqListPopFront(SeqList* psl);

void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	int begin = 0;
	while (begin < psl->size - 1)
	{
		psl->a[begin] = psl->a[begin + 1];
		begin++;
	}
	psl->size--;
}

// 顺序表查找
int SeqListFind(SeqList* psl, SeqListDatatype x);

int SeqListFind(SeqList* psl, SeqListDatatype x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SeqListDatatype x);

void SeqListInsert(SeqList* psl, size_t pos, SeqListDatatype x)
{
	assert(psl);
	assert((int)pos <= psl->size);
	if (psl->capacity == psl->size)
	{
		CheckCapacity(psl);
	}
	int end = psl->size - 1;
	while (end >= (int)pos)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[pos] = x;
	psl->size++;
}

// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);

void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	int begin = pos;
	while (begin < psl->size - 1)
	{
		psl->a[begin] = psl->a[begin + 1];
		++begin;
	}
	psl->size--;
}

// 顺序表销毁
void SeqListDestory(SeqList* psl);

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

// 顺序表打印
void SeqListPrint(SeqList* psl);

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

 4.与顺序表相关的面试题

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

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

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

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

3. 合并两个有序数组。OJ链接

 
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int end1 = m - 1;
    int end2 = n - 1;
    int end = nums1Size - 1;
    while(end1 >= 0 && end2 >= 0)
    {
        if(nums1[end1] >= nums2[end2])
            nums1[end--] = nums1[end1--];
        else
            nums1[end--] = nums2[end2--];
    }
    while(end2 >= 0)
    {
        nums1[end--] = nums2[end2--];
    }
}

5.顺序表的优缺点

顺序表的优点：

1.尾插和尾删效率高

2.可以通过下标进行随机访问

.顺序表的缺点：

1.头部和中部插入删除效率低

2.扩容可能会造成空间大量浪费