《【初阶数据结构】从 0 到 1 速通顺序表：C 语言实现 + 手撕算法（附完整代码）》

//宏定义常量
#define N 7
//类型别名声明，方便后续代码维护
typedef int SLDataType
typedef struct SeqList
{
    SLDataType a[N];//定长数组
    int size;//有效数据个数
}SeqList;

typedef int SLdataType;
typedef struct Seqlist
{
   SLdataType* array
   ;//指向动态开辟的数组
   int size;//有效数据个数
   int capacity;//容量空间大小
}SL;

//顺序表的初始化
void SLInit(SL*ps)
{
	ps->arr = NULL;//顺序表初始化为空
	ps->size = ps->capacity = 0;//有效数据个数和空间容量均置为0
}

void SLCheckCapacity(SL*ps)
{
	if (ps->size == ps->capacity)
	{
		//capacity可能初始为0，所以要把他存放到临时的newcapacity中
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//如果realloc扩容失败，则返回null，如果直接赋值给arr，则会丢失之前存储的数据，所以用临时变量来存储
		SLdataType* temp = (SLdataType*)realloc(ps->arr, newcapacity * 2 * sizeof(SLdataType));//??????
		if (temp == NULL)
		{
			perror("realloc faile!");
			exit(1);//直接退出程序
		}
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
}

//顺序表的尾插
void SLPushBack(SL* ps, SLdataType x)
{ 
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
} 

void SLPushFront(SL* ps, SLdataType x) 
{
	assert(ps);
	SLCheckCapacity(ps);`在这里插入代码片`
	//先让顺序表已有的数据往后移动
	for (int i = ps->size; i>0 ; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	--ps->size;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

void SLInsert(SL* ps, int pos, SLdataType x)
{
	assert(ps);
    assert(pos >= 0 && pos <=ps->size);
	//插入数据要判断空间是否够
	SLCheckCapacity(ps);
	//让pos及之后的数据往后移动
	for (int i = ps->size;i>pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos;i<ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//顺序表的查找
int SLFind(SL* ps, SLdataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)	{
		if (ps->arr[i] == x)
	{
			//找到了
			return i;
		}
	}
	return -1;
}

void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"Contact.h"

//typedef int SLdataType;
typedef peoInfo SLdataType;

typedef struct Seqlist
{
	SLdataType* arr;
	int size;
	int capacity;
}SL;
void SLInit(SL* ps);

void SLDestroy(SL* ps);

void SLPrint(SL ps);
void SLPushBack(SL* ps,SLdataType x);

void SLPushFront(SL* ps, SLdataType X);

void SLPopBack(SL* ps);

void SLPopFront(SL* ps);
//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLdataType x);
//删除指定位置的数据
void SLErase(SL* ps, int pos);
//顺序表的查找
int SLFind(SL* ps, SLdataType x);

#include"Seqlist.h"
//顺序表的打印
//void SLPrint(SL s)
//{
//	for (int i = 0; i < s.size; i++)
//	{
//		printf("%d ", s.arr[i]);
//	}
//	printf("\n");
//}

//顺序表的初始化
void SLInit(SL*ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}


void SLCheckCapacity(SL*ps)
{
	if (ps->size == ps->capacity)
	{
		//capacity可能初始为0，所以要把他存放到临时的newcapacity中
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//如果realloc扩容失败，则返回null，如果直接赋值给arr，则会丢失之前存储的数据，所以用临时变量来存储
		SLdataType* temp = (SLdataType*)realloc(ps->arr, newcapacity * 2 * sizeof(SLdataType));//??????
		if (temp == NULL)
		{
			perror("realloc faile!");
			exit(1);//直接退出程序
		}
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
}

//顺序表的尾插
void SLPushBack(SL* ps, SLdataType x)
{ 
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
} 


void SLPushFront(SL* ps, SLdataType x) 
{
	assert(ps);
	SLCheckCapacity(ps);
	//先让顺序表已有的数据往后移动
	for (int i = ps->size; i>0 ; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}


//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	--ps->size;
}


//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}


//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLdataType x)
{
	assert(ps);
    assert(pos >= 0 && pos <=ps->size);
	//插入数据要判断空间是否够
	SLCheckCapacity(ps);
	//让posj及之后的数据往后移动
	for (int i = ps->size;i>pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}


//删除指定位置的顺序
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos;i<ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//顺序表的查找
int SLFind(SL* ps, SLdataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			//找到了
			return i;
		}
	}
	return -1;
}

#include"SeqList.h"
 
void test()
{
	SL s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPrint(&s);
	int find = SeqListFind(&s, 2);
	if (find < 0)
	{
		printf("所查找的数据不存在！\n");
	}
	else
	{
		printf("所查找的数据存在，该数据所在位置下标为%d\n", find);
	}
	SeqListInsert(&s, find, 100);
	SeqListPrint(&s);
	SeqListErase(&s, find);
	SeqListPrint(&s);
}
 
int main()
{
	test();
	return 0;
}

int removeElement(int* nums, int numsSize, int val) {
  //思路：双指针  ：创建两个变量指向数组的起始位置
  //nums[src]==val;src++
  //nums[src]!=val,赋值给dst，src和dst都++
  int dst=0,src=0;
  while(src<numsSize)
  {
     if(nums[src]!=val)
     {
        nums[dst++]=nums[src];
       // src++,dst++;
     }
     /*else
     {
        src++;
     }*/
     src++;
  } 
  //此时dst的值刚好就是新数组的有效长度
  return dst;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
     //从后往前找：比谁大，谁大谁往后放
    int l1=m-1;//放在第一个数组最后一个有效元素对应的下标
    int l2=n-1;//放在第二个数组最后一个有效元素对应的下标
    int l3=m+n-1;//放在第一个数组下标为第一个数组加第二个数组有效元素的下标处
    // 比较l1和l2对应元素的大小，谁大,l3放谁，然后l3和大的元素对应的下标--
    while(l1>=0&&l2>=0)//只要有一个为假就跳出循环
    {
        if(nums1[l1]>nums2[l2])
        {
            nums1[l3--]=nums1[l1--];
        }
        else
        {
            nums1[l3--]=nums2[l2--];
        }
    }
//l1已经越界，nums2中还有数据没有放到nums1中
while(l2>=0)
{
    nums1[l3--]=nums2[l2--];
}

}