数据结构之顺序表

顺序其实本质上就是一个数组，但是这个数组与结构体的空间不是连续在一起的。

（内有注释）

#define _CRT_SECURE_NO_WARNINGS 1
//函数实现
#include"SeqList.h"
void SLInit(SL* ps)
{
	//两种初始化方式
	//one
	//ps->a = NULL;
	//ps->size = 0;
	//ps->capacity = 0;
	
	//two
	assert(ps);
	ps->a = (SLDataType*)malloc(sizeof(SLDataType));//小小的扩容一下
    ps->size = 0;
	ps->capacity = 0;
}


void SLDestory(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
}


void SLPrint(SL* ps)
{
	assert(ps);
	int i = 0;
	while(i<ps->size)
	{
		printf("%d ", ps->a[i++]);
	}
}


void SLcheckcapacity(SL* ps)
{
	assert(ps);
	SLDataType* Nodeps = ps->a;
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
}
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLcheckcapacity(ps);
	ps->a[ps->size++]=x;
}

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

void SLPushFront(SL* ps,SLDataType x)
{
	assert(ps);
	SLcheckcapacity(ps);
	int end = ps->size;
	while (end)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

void SLPopFront(SL* ps)
{
	assert(ps);
	int pos = 0;
	while (pos < ps->size-1)
	{
		ps->a[pos] = ps->a[++pos];
	}
}

void SLInsert(SL* ps,int pos,SLDataType x)
{
	assert(ps);
	SLcheckcapacity(ps);
	int end = ps->size;
	while (end> pos)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	--ps->size;
}

void SLErase(SL* ps, int pos)
{
	assert(ps);
	while (pos < ps->size)
	{
		ps->a[pos] = ps->a[pos + 1];
		pos++;
	}
	--ps->size;
}

//找到了返回下标，没找到返回-1
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int start = 0;
	while (start < ps->size)
	{
		if (x == ps->a[start])
			return start;
		else
			start++;
	}
	return -1;
}


void SLModify(SL* ps, int pos, SLDataType x)
{
	ps->a[pos] = x;
}

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDataType;
typedef struct SeqList
{
	//实际上就是一个数组
	SLDataType* a;
	int size;//数据个数
	int capacity;//数据容量
}SL;
//初始化、销毁、打印
void SLInit(SL* ps);
void SLDestory(SL* ps);
void SLPrint(SL* ps);
//扩容
void SLcheckcapacity(SL* ps);
//头插尾插   头删尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);//返回长度
//随机插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//随机删除数据
void SLErase(SL* ps,int pos);
//寻找数据
int SLFind(SL* ps,SLDataType x);
//修改数据
void SLModify(SL* ps, int pos, SLDataType x);

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListtest()
{
	SL s = { 0 };
	SLInit(&s);
	SLPushBack(&s,6);
	SLPushBack(&s,5);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 4);
	SLPopBack(&s);
	SLPushFront(&s, 8);
	SLErase(&s, 3);
	SLPrint(&s);
	SLDestory(&s);
}
int main()
{
	SeqListtest();
}