数据结构 | 数组模拟实现顺序表

2021年11月20日 阅读数:2
这篇文章主要向大家介绍数据结构 | 数组模拟实现顺序表,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

代码已经放在Gitee上,须要能够小伙伴能够去看看git

用C语言数组模拟实现顺序表web

Giteeexpress

线性表和顺序表

线性表

线性表(linear list)是n个具备相同特性的数据元素的有限序列,这是咱们普遍使用的数据结构。数组

线性表在逻辑上是线性结构,也就说是连续的一条直线。可是在物理结构上并不必定是连续的,线性表在物理上存储时,一般以数组和链式结构的形式存储。数据结构

常见的线性表:顺序表、链表、栈、队列、字符串…
在这里插入图片描述svg

顺序表

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

通常能够分为:ui

  1. 静态顺序表:使用定长数组来存储元素
  2. 动态顺序表:使用动态开辟的数组来储存元素

静态顺序表


//定义静态数组的大小,方便后续修改
#define MAX_SIZE 50

//重命名数组的数据类型,方便后续修改
typedef int SLDataType;


//定义结构体
//成员变量为数组和记录当前数据个数的变量
//重命名结构体数据类型,方便书写
typedef struct SeqList {
   
   

	SLDataType arr[MAX_SIZE];
	int size;

}SL;


//-----------------------------------------------------------------------------
//如下是一些常见的接口的声明

//顺序表初始化
//利用结构体类型建立一个静态顺序表变量后,能够对其进行初始化
void SLInit(SL* psl);

//打印顺序表
//把顺序表的值按照前后顺序打印出来
void SLPrint(SL* psl);

//检查顺序表是否已满
//每次进行加入数据的操做的时候须要先检查是否已经满了,若是满了就不可以插入了
void SLCheck(SL* psl);

//顺序表的尾插
//在顺序表的尾部在插入一个元素
//因为是数组加入数据很方便,直接使用数组下标就能够访问到
void SLPushBack(SL* psl, SLDataType data);

//顺序表的尾删
//删除顺序表尾部的数据
void  SLPopBack(SL* psl);

//顺序表的头插
//在顺序表的开头加入一个数据
void SLPushFront(SL* psl, SLDataType data);

//顺序表的头删
//把顺序表第一位数据删除
void SLPopFront(SL* psl);

//顺序表查找某个数据
//查找顺序表中是否存在某个数据,若是有就返回对应的下标
//若是找不到就返回-1
int SLFind(SL* psl, SLDataType x);

//顺序表在pos位置插入x
//在指定下标位置插入数据x,原来x位置的数据以及后面的数据日后移动
void SLInsert(SL* psl, size_t pos, SLDataType x);

//顺序表删除在pos位置的数据
void SLErase(SL* psl, size_t pos);

//顺序表某一位置数据的修改
void SLModify(SL* psl, size_t pos, SLDataType x);

如下是这些接口的具体实现spa

//顺序表初始化
void SLInit(SL* psl) {
   
   

	psl->arr[0] = 0;//此处只能初始化一个元素
	psl->size = 0;
}

//打印顺序表
void SLPrint(SL* psl) {
   
   

	int i = 0;

	if (psl->size) {
   
   

		for (i = 0; i < psl->size; i++) {
   
   

			//输出格式,记得根据SLDataTyped的类型来修改
			printf("%d ", psl->arr[i]);
		}
		printf("\n");
	}
	else {
   
   
		printf("Null\n");
	}

}

/*
//检查顺序表是否已满
void SLCheck(SL* psl) {

	if (psl->size == MAX_SIZE) {
		printf("顺序表已满,没法进行后续操做");
	}

}
*/

//顺序表的尾插
void SLPushBack(SL* psl, SLDataType data) {
   
   

	//插入数据要先检查空间是否已满

	//实现方法一不够好
	/*
	if (psl->size == MAX_SIZE) {

		printf("空间已满\n");
		return;
	}
	else {

		psl->arr[psl->size] = data;
		psl->size++;

	}*/

	//实现方法二,简单明了
	assert(psl->size != MAX_SIZE);

	psl->arr[psl->size] = data;
	psl->size++;
}

//顺序表的尾删
void  SLPopBack(SL* psl) {
   
   

	//判断是否还有元素能够删除
	assert(psl->size);

	psl->size--;

}

//顺序表的头插
void SLPushFront(SL* psl, SLDataType data) {
   
   

	assert(psl->size != MAX_SIZE);

	//src用来后移数据
	int src = psl->size;

	while (src >= 1) {
   
   
		psl->arr[src] = psl->arr[src - 1];
		src--;
	}
	psl->arr[src] = data;
	psl->size++;

}

//顺序表的头删
void SLPopFront(SL* psl) {
   
   

	//判断是否还有数据能够删除
	assert(psl->size);

	int src = 0;
	while (src < psl->size - 1) {
   
   

		psl->arr[src] = psl->arr[src + 1];
		src++;
	}
	psl->size--;
}

//顺序表查找某个数据
int SLFind(SL* psl, SLDataType x) {
   
   

	int i = 0;
	for (i = 0; i < psl->size; i++) {
   
   
		
		if (psl->arr[i] == x) {
   
   

			//找到了就返回该数据在顺序表中的位置
			return  i;
		}
	}
	//找不到就返回-1
	return -1;

}

//顺序表在pos位置插入x
void SLInsert(SL* psl, size_t pos, SLDataType x) {
   
   

	assert(psl->size < MAX_SIZE);
	assert(pos >= 0 && pos <= psl->size);//pos=0或者pos=size的时候,至关于头插,尾插

	int end = psl->size;

	while (end > pos) {
   
   

		psl->arr[end] = psl->arr[end - 1];
		end--;
	}
	psl->arr[pos] = x;
	psl->size++;

}

//顺序表删除在pos位置的数据
void SLErase(SL* psl, size_t pos) {
   
   

	assert(psl->size);
	assert(pos >= 0 && pos < psl->size);

	int start = pos + 1;
	while (start < psl->size) {
   
   

		psl->arr[start - 1] = psl->arr[start];
		start++;

	}
	psl->size--;
}


//顺序表某一位置数据的修改
void SLModify(SL* psl, size_t pos, SLDataType x) {
   
   

	assert(psl->size);
	assert(pos >= 0 && pos < psl->size);

	psl->arr[pos] = x;
}

上面代码的测试,我放在了Gitee上,须要的小伙伴能够参考一下指针

动态顺序表

静态顺序表只适用于肯定知道须要存多少数据的场景。静态顺序表的定长数组致使N定大了,空间开多了浪费,开少了不够用。因此现实中基本都是使用动态顺序表,根据须要动态的分配空间大小,因此下面咱们实现动态顺序表。

//重命名SL的数据类型,方便后续修改
typedef int SLDataType;

//定义结构体
//成员变量为指向动态顺序表的指针,数据的个数,顺序表的容量
//capacity用来管理数组的总大小,若是size与capacity相等了,就表示数组已经满了须要扩容
//重定义结构体类型名称,方便操做
typedef struct SeqList {
   
   

	SLDataType* p;
	int size;
	int capacity;

}SL;



//----------------------------------------------------------------------
//一下是一些经常使用的接口,与静态顺序表差很少

//SL初始化
void SLInit(SL* ps);


//SL空间检查
//如若size与capacity相等表示数组已经满了,须要扩容
void SLCheckCapacity(SL* ps);


//SL打印
void SLPrint(SL* ps);


//SL销毁
//由于数组是动态开辟的,因此在最后不使用的数组的时候要释放空间
void SLDestory(SL* ps);


//SL尾插
void SLPushBack(SL* ps,SLDataType x);


//SL尾删
void SLPopBack(SL* ps);


//SL头插
void SLPushFront(SL* ps, SLDataType x);


//SL头删
void SLPopFront(SL* ps);


//SL查找某个数据
//若是能找到,返回该数据在顺序表中下标
int SLFind(SL* ps, SLDataType x);


//SL在pos位置插入x
void SLInsert(SL* ps, size_t pos, SLDataType x);


//SL删除pos位置的值
void SLErase(SL* ps, size_t pos);


//SL修改某一位置的数据
void SLModity(SL* ps, size_t pos, SLDataType x);

如下是具体的实现

//动态顺序表的实现

#include"DynamicSeqList.h"

//SL初始化
void SLInit(SL* ps) {
   
   

	ps->p = NULL;
	ps->capacity = 0;
	ps->size = 0;

}


//SL空间检查
void SLCheckCapacity(SL* ps) {
   
   

	if (ps->size == ps->capacity) {
   
   

		ps->capacity = (ps->capacity == 0) ? 5 : 2 * ps->capacity;

		SLDataType* tmp = (SLDataType*)realloc(ps->p, (ps->capacity) * sizeof(SLDataType));

		if (tmp == NULL) {
   
   

			printf("realloc fail\n");
			exit(-1);
		}

		ps->p = tmp;

	}

}


//SL打印
void SLPrint(SL* ps) {
   
   

	if (ps->size == 0) {
   
   

		printf("顺序表为空\n");

	}
	else {
   
   

		int i = 0;
		for (i = 0; i < ps->size; i++) {
   
   

			//打印格式记得根据SLDataType的类型来修改
			printf("%d ", ps->p[i]);

		}
		printf("\n");

	}

}


//SL销毁
//这里并无彻底销毁结构体s,只是把成员变量都赋值为0
void SLDestory(SL* ps) {
   
   

	free(ps->p);
	ps->p = NULL;
	ps->size = ps->capacity = 0;

}


//SL尾插
void SLPushBack(SL* ps, SLDataType x) {
   
   

	SLCheckCapacity(ps);

	ps->p[ps->size] = x;
	ps->size++;

}


//SL尾删
void SLPopBack(SL* ps) {
   
   

	//删除数据须要判断一下顺序表是否为空
	assert(ps->size > 0);
	ps->size--;

}


//SL头插
void SLPushFront(SL* ps, SLDataType x) {
   
   

	SLCheckCapacity(ps);

	int end = ps->size;
	while (end > 0) {
   
   

		ps->p[end] = ps->p[end - 1];
		end--;

	}
	ps->p[end] = x;
	ps->size++;
}


//SL头删
void SLPopFront(SL* ps) {
   
   

	//删除数据须要判断一下顺序表是否为空
	assert(ps->size > 0);

	int start = 0;
	while (start < ps->size - 1) {
   
   

		ps->p[start] = ps->p[start + 1];
		start++;

	}
	ps->size--;

}


//SL查找某个数据
int  SLFind(SL* ps, SLDataType x) {
   
   

	//须要判断顺序表是否为空,能够用assert,也能够用if判断
	assert(ps->size);

	int i = 0;
	for (i = 0; i < ps->size; i++) {
   
   

		if (x == ps->p[i]) {
   
   

			return i;
		}

	}
	return -1;

}


//SL在pos位置插入x
//当pos为0或者pos为size时,至关于头插、尾插
void SLInsert(SL* ps, size_t pos, SLDataType x) {
   
   

	SLCheckCapacity(ps);

	assert(pos >= 0 && pos <= ps->size);

	int end = ps->size;
	while (end > pos) {
   
   

		ps->p[end] = ps->p[end - 1];
		end--;
	}
	ps->p[end] = x;
	ps->size++;

}


//SL删除pos位置的值
void SLErase(SL* ps, size_t pos) {
   
   

	//判断要删除的位置是否在size以内
	assert(pos >= 0 && pos < ps->size);

	int start = pos + 1;
	while (start < ps->size) {
   
   

		ps->p[start - 1] = ps->p[start];
		start++;

	}
	ps->size--;

}


//SL修改某一位置的数据
void SLModity(SL* ps, size_t pos, SLDataType x) {
   
   

	//判断要修改的位置是否在size以内
	assert(pos >= 0 && pos < ps->size);

	ps->p[pos] = x;
}

一样的,我本身写的一些小测试也在Gitee上,须要的小伙伴能够去看看