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");
}
``````

1.移除元素

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

3.合并两个有序数组

# 6.OJ答案及解析

## 1.移除元素

``````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;

}``````

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

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

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

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

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

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

``````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;
}``````

## 3.合并两个有序数组

``````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