顺序表 数据结构 顺序表基本 *** 作 C语言实现 顺序表详解

顺序表就是数组，但是数据必须从第一个位置开始连续存储

使用定长数组存储元素

#define N 200
typedef int SLDataType;
struct SeqList
{
    SLDataType a[N];//定义一个数组
    int size;//数据个数
};

 N太小可能不够用，N太大可能浪费空间

#define SEQ_INIT_SIZE 10//初始容量
#define SEQ_INC_SIZE 2//每次增容的倍数
typedef struct SeqList
{
    SLDataType* a;//指向动态数组指针
    int sz;//数据个数
    int capacity;//容量 -空间大小
}SeqList;

空间不够则增容

#include
#include
#include
#include
#define SEQ_INIT_SIZE 10//初始容量
#define SEQ_INC_SIZE 2//每次增容的倍数
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define NULLPTR -3
typedef int status;//状态
typedef int SLDataType;//元素类型

void SeqListInit(SeqList* ps)
{
	assert(ps != NULL);
	ps->capacity = SEQ_INIT_SIZE;
	ps->sz = 0;
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * ps->capacity);
	if (ps->a == NULL)exit(-1);
}

void SeqListPrint(const SeqList* ps)
{
	assert(ps != NULL);
	for (int i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

int SeqListFind(const SeqList* ps, SLDataType x)
{
	assert(ps != NULL);
	for (int i = 0; i < ps->sz; i++)
	{
		if (ps->a[i] == x)return i;
	}
	return -1;
}

bool IncCapacity(SeqList* ps)
{
	assert(ps != NULL);
	int newcapacity = ps->capacity * SEQ_INC_SIZE;
	SLDataType* newdata = (SLDataType*)malloc(sizeof(SLDataType) * newcapacity);
	if (newdata == NULL)return false;
	for (int i = 0; i < ps->capacity; i++)
	{
		newdata[i] = ps->a[i];
	}
	free(ps->a);
	ps->a = newdata;
	ps->capacity = newcapacity;
	return true;
}

bool IncCapacity(SeqList* ps)
{
	assert(ps != NULL);
	int newcapacity = ps->capacity * SEQ_INC_SIZE;
	SLDataType* newdata = (SLDataType*)realloc(ps->a,sizeof(SLDataType) * newcapacity);
	if (newdata == NULL)return false;
	ps->a = newdata;
	ps->capacity = newcapacity;
	return true;
}

bool IsFull(const SeqList* ps)
{
	assert(ps != NULL);
	return ps->sz == ps->capacity;
}

status SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps != NULL);
	if (pos<0 || pos>ps->sz)return INFEASIBLE;
	if (IsFull(ps) && !IncCapacity(ps))return OVERFLOW;//没满和满了但增容成功都不return，满了但增容失败return
	for (int i = ps->sz - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[pos] = x;
	ps->sz++;
	return OK;
}

void SeqListPushBack(SeqList* ps, SLDataType x)
{
	assert(ps != NULL);
	SeqListInsert(ps, ps->sz, x);
}

void SeqListPushFront(SeqList* ps, SLDataType x)
{
	assert(ps != NULL);
	SeqListInsert(ps, 0, x);
}

status SeqListErase(SeqList* ps,int pos)
{
	assert(ps != NULL);
	if (pos<0 || ps>ps->sz - 1)return INFEASIBLE;
	for (int i = pos; i < ps->sz-1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->sz--;
	return OK;
}

void SeqListPopBack(SeqList* ps)
{
	assert(ps != NULL);
	SeqListErase(ps,ps->sz-1);
}

void SeqListPopFront(SeqList* ps)
{
	assert(ps != NULL);
	SeqListErase(ps,0);
}

void SeqListClear(SeqList* ps)
{
    assert(ps != NULL);
    ps->sz = 0;
}

void SeqListDestory(SeqList* ps)
{
    assert(ps != NULL);
    ps->capacity = 0;
    ps->sz = 0;
    free(ps->a);
} 

int removeElement(int* nums, int numsSize, int val){
       int j=-1;
       for(int i=0;i

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

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
      int i=m-1;
      int j=n-1;
      int k=m+n-1;
      while(i>=0&&j>=0)
      {
          nums1[k--]=nums1[i]>=nums2[j]?nums1[i--]:nums2[j--];
      }
      while(j>=0)
      {
          nums1[k--]=nums2[j--];
      }
}