动态顺序表的创建

时间：2021-12-07 01:26:22

建立头文件

头文件名   SeqList.h

1.构建一个结构体，结构体内的成员变量有，有效元素的个数size, 该数组的容量capacity,存放数据所开辟动态空间的地址a。（a是指向动态开辟空间的指针）代码10-15行。

动态顺序表的创建

2.创建接口

动态顺序表需要完成增删查改等功能

如图

动态顺序表的创建

完整代码如下，内部也已标有注释

SeqList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <assert.h>
#include<stdio.h>
#include <stdlib.h>

typedef int SLDataType;//int的重新定义
//结构体struct SeqList或者SL（类型）里面有，有效元素的个数size,
//该数组的容量capacity,存放数据所开辟空间的地址a
typedef struct SeqList
{
	SLDataType* a;
	int size;//有效元素的个数
	int capacity;//该数组的容量
}SL;
//下面的SL* ps是用来接收结构体的地址
void SeqListInit(SL* ps);//初始化
void SeqListPrint(SL* ps);//测试打印
void SeqListCheckCapacity(SL* ps);//检查容量，不够则加二倍

void SeqListPushBack(SL* ps, SLDataType x);//尾插
void SeqListPopBack(SL* ps);//尾删

void SeqListPushFront(SL* ps, SLDataType x);//头插
void SeqListPopFront(SL* ps);//头删
void SeqListInset(SL* ps, int pos,SLDataType x);//任意位置插入
void SeqListErase(SL* ps,int pos);//任意位置删除
int SeqListFind(SL* ps, SLDataType x);//查找
void SeqListFree(SL* ps);//释放空间

接口功能实现

先创建SeqList.c源文件

#include "SeqList.h"
void SeqListInit(SL* ps)//初始化
{
	ps->a =(SLDataType*) malloc(sizeof(SLDataType) * 4);
	if (ps->a == NULL)
	{
		printf("开辟内存失败\n");
		/*exit(-1);*/
	}
	ps->size = 0;//记录初始化后结构体里面的值
	ps->capacity = 4;
}
void SeqListPrint(SL* ps)//测试打印
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d  ", ps->a[i]);
	}
	printf("\n");
}
void SeqListCheckCapacity(SL* ps)//检查容量，不够则加二倍
{
	if (ps->size >= ps->capacity)
	{
		ps->capacity *= 2;
		ps->a = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity);
		if (ps->a == NULL)
		{
			printf("扩容失败\n");
			exit(-1);
		}
	}
}
//
void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
	assert(ps);
	SeqListCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
void SeqListPopBack(SL* ps)//尾删
{
	assert(ps);
	ps->size--;
}
void SeqListPushFront(SL* ps, SLDataType x)//头插
{
	assert(ps);
	SeqListCheckCapacity(ps);

	SLDataType end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->size++;
   ps->a[end+1] = x;
}
void SeqListPopFront(SL* ps)//头删
{
	assert(ps);
	int start = 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}
void SeqListInset(SL* ps, int pos, SLDataType x)//任意位置插入
{
	assert(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
void SeqListErase(SL* ps, int pos)//任意位置删除
{
	assert(ps);
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}
int SeqListFind(SL* ps, SLDataType x)//查找
{
	assert(ps);
	int i = 0;
	while (i < ps->size)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
		i++;
	}
}
void SeqListFree(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
}

创建工程测试test.c源文件

#include "SeqList.h"
//测试
void TestSeqList()
{
	SL s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 3);
	SeqListPrint(&s);//测试尾部插入打印
	SeqListPopBack(&s);
	SeqListPrint(&s);//测试尾部删除打印
	SeqListPushFront(&s, 9);
	SeqListPrint(&s);//测试头部插入打印
	SeqListPopFront(&s);
	SeqListPrint(&s);//测试头部删除打印
	SeqListInset(&s, 3, -1);
	SeqListPrint(&s);//测试任意位置插入打印
	SeqListErase(&s, 3);
	SeqListPrint(&s);//测试任意位置删除打印
	int ret=SeqListFind(&s, 1);//查找
	SeqListFree(&s);//释放动态开辟空间
}
int main()
{
	TestSeqList();
	return 0;
}

代码内部有详细的注释。

标签：

相关文章