C语言数据结构之顺序表

概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改

顺序表一般分为两种

静态：使用定长数组存储元素
动态：使用动态开辟的数组存储

#include <stdio.h>
#define N 10000
int main()
{
	typedef int SLdatetype;

	struct Seqlist 
	{
		int a[N];
		int size;
	};
	return 0;
}

静态顺序表缺点：开多了用不了，开少了又不够

接口实现

头文件

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <iostream>

typedef int SLdatetype;
#define int_capacity 4

typedef	struct Seqlist
	{
		SLdatetype* array;
		size_t size;
		size_t capacity;
    }SL;

void SLInit(SL* ps);//顺序表初始化
void checkcapacity(SL* ps);//检查空间大小，扩容

void seqlistpushback(SL* ps,SLdatetype x);//尾插
void seqlistpopback(SL* ps);//尾割

void seqlistpushfront(SL* ps,SLdatetype x);//头插
void seqlistpopfront(SL* ps);//头割

SLdatetype seqlistfind(SL* ps, SLdatetype x);//查找x

void seqlistinsert(SL* ps, SLdatetype pop,SLdatetype x);//在pop位置插入x
void seqlistrelease(SL* ps, SLdatetype pop);//在pop位置删除x

void destory(SL* ps);//摧毁顺序表
void seqlistprint(SL* ps);//打印顺序表

函数实现

#include "seqlist.h"
void SLInit(SL* pch)
{
	pch->array = (SLdatetype*)malloc(sizeof(SLdatetype) * int_capacity);
	assert(pch);
	pch->size = 0;
	pch->capacity = int_capacity;
}
void destroy(SL* pch)
{
	free(pch->array);
	pch->array = NULL;
	pch->size = pch->capacity = 0;
}
void checkcapacity(SL* pch)
{
	if (pch->size == pch->capacity)
	{
		SLdatetype* tmp = (SLdatetype*)malloc(sizeof(SLdatetype) * pch->capacity * 2);
		assert(tmp);
		pch->array = tmp;

	}
	pch->capacity *= 2;
}
void seqlistpushback(SL* pch, SLdatetype x)

{
	checkcapacity(pch);
	pch->array[pch->size++] = x;
}

void seqlistpopback(SL* pch)
{
	assert(pch->size>0);
	pch->size--;
}
void seqlistprint(SL* pch)
{
	assert(pch);
	for (int i = 0;i < pch->size;i++)
	{
		printf("%d ", pch->array[i]);
	}
	printf("\n");
}
void seqlistpushfront(SL* pch, SLdatetype x)
{
	assert(pch);
	checkcapacity(pch);
	int end = pch->size - 1;
	while (end>=0)
	{
		pch->array[end+1] = pch->array[end];
		end--;
	}
	pch->array[0] = x;
	pch->size++;
}
void seqlistinsert(SL* pch, int pop, SLdatetype x)
{
	assert(pch);
	checkcapacity(pch);
	int end = pch->size - 1;
	while (end>=pop)
	{
		pch->array[end + 1] = pch->array[end];
			end--;
	}
	pch->array[pop] = x;
	pch->size++;
}
void seqlistpopfront(SL* pch)
{
	assert(pch);
	int end = 0;
	while (end < pch->size-1)
	{   
		pch->array[end] = pch->array[end+1];
	}
	pch->size--;
}
SLdatetype seqlistfind(SL* pch, SLdatetype x)
{
	assert(pch);
	for (int i = 0;i < pch->size;i++)
	{
		if (pch->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void seqlistrelease(SL* pch, SLdatetype pos)
{
	assert(pch);
	int end = pch->size - 1;
	int j = pos;
	while (j<end)
	{
		pch->array[j] = pch->array[j + 1];
		j++;
	}
	pch->size--;
}

测试

#include "seqlist.h"
int main()
{

	SL s;
	SLInit(&s);
	seqlistpushback(&s, 1);
	seqlistpushback(&s, 2);
	seqlistpushback(&s, 3);
	seqlistpushback(&s, 4);
	seqlistpushback(&s, 5);
	seqlistpushback(&s, 6);
	seqlistpushback(&s, 7);
	seqlistprint(&s);
	

	seqlistpopback(&s);
	seqlistpopback(&s);
	seqlistpopback(&s);
	seqlistpopback(&s);
	seqlistprint(&s);
	
	seqlistpopback(&s);
	seqlistpushback(&s, 10);
	seqlistpushback(&s, 20);
	seqlistprint(&s);

	seqlistinsert(&s,2,9);
	seqlistprint(&s);

	seqlistpushfront(&s, 10);
	seqlistprint(&s);

	seqlistrelease(&s, 0);
	seqlistprint(&s);
	int c = seqlistfind(&s, 9);
	printf("%d", c);
	return 0;
}

生死有命富贵在天，能不能悟就看自己了