顺序表的增删改查

SeqList.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
//顺序表,有效数组在数组中必须是连续的
//静态顺序表设计(固定大小)
typedef int SLDataType;
#define N 10
//vector c++里的顺序表

typedef struct SeqList
{
	SLDataType* a;
	int size;//有效数据的个数
	int capacity; //容量
}SL, SeqList;

//尾插尾删  头插头删
void SeqListInit(SL* ps);
void SeqListPushBack(struct SeqList* ps, SLDataType x);
void SeqListPopBack(struct SeqList* ps);
void SeqListPushFront(SL* ps, SLDataType x);//头插法
void SeqListPopFront(SL* ps);//头删

//任意位置的插入删除
void SeqListInsert(SL* ps, int pos, SLDataType x);
void SeqListErase(struct SeqList* ps, int pos);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"

void SeqListInit(SL* ps)
{
	/*s.size = 0;
	s.a = NULL;
	s.capacity = 0;*/
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (ps->a == NULL)
	{
		printf("申请内存失败\n");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;
}

void SeqListPushBack(struct SeqList* ps, SLDataType x);
void SeqListPopBack(struct SeqList* ps);
void SeqListPushFront(struct SeqList* ps, SLDataType x);//头插法
void SeqListPopFront(struct SeqList* ps);//头删

//任意位置的插入删除
void SeqListInsert(SL* ps, int pos, SLDataType x);
void SeqListErase(struct SeqList* ps, int pos);

顺序表的增删改查

按个调试

先调试初始化SeqListInit 

扩容

void SeqListPushBack(struct SeqList* ps, SLDataType x)//尾插
{
	assert(ps);
	//如果满了需要增容
	if (ps->size >= ps->capacity)
	{
		ps->capacity *= 2;
		ps->a = realloc(ps->a, sizeof(SLDataType) * ps->capacity);//从ps->a开始扩容
		if (ps->a == NULL)
		{
			printf("扩容失败\n");
			exit(-1);
		}
	}
	ps->a[ps->size] = x;
	ps->size++;
 }

顺序表的增删改查

 

尾删

void SeqListPopBack(struct SeqList* ps)//尾删
{
	assert(ps);
	/*ps->a[ps->size - 1] = 0;*/
	ps->size--;//一般删数据就是减一下
}

顺序表的增删改查

没什么意义,尾删法

通常的一些电脑数据恢复软件就是恢复size,不是真的删除了内存中的数据,除非改写

头插法

void SeqListPushFront(struct SeqList* ps, SLDataType x);//头插法
{
	int end = ps->size - 1;
	while (end>=0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

顺序表的增删改查

 


出现问题:头插法插入个数超过capacity时:

顺序表的增删改查


解决办法:

void SeqListCheckCapacity(SL* ps)
{
	//如果满了需要增容
	if (ps->size >= ps->capacity)
	{
		ps->capacity *= 2;
		ps->a = realloc(ps->a, sizeof(SLDataType) * ps->capacity);//从ps->a开始扩容
		if (ps->a == NULL)
		{
			printf("扩容失败\n");
			exit(-1);
		}
	}

}

调用 SeqListCheckCapacity 扩容函数--在进行插入之前

void SeqListPushFront(struct SeqList* ps, SLDataType x)//头插法
{
	assert(ps);
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end>=0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

顺序表的增删改查

头删法

void SeqListPopFront(struct SeqList* ps)//头删
{
	int start = 0;
	while (start < ps->size-1)
	{
		ps->a[start] = ps->a[start + 1];
		++start;
	}
	ps->size--;
}

顺序表的增删改查

 

 

上一篇:顺序表L中的所有元素逆置


下一篇:排序