C语言数据结构之数组模拟实现顺序表流程详解

编辑: admin 分类: c#语言发布时间: 2021-12-12 来源:互联网

线性表和顺序表

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列，这是我们广泛使用的数据结构。

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

常见的线性表：顺序表、链表、栈、队列、字符串…

在这里插入图片描述

顺序表

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

一般可以分为：

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

静态顺序表

//定义静态数组的大小，方便后续修改
#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);

以下是这些接口的具体实现

//顺序表初始化
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上，需要的小伙伴可以去看看

到此这篇关于C语言数据结构之数组模拟实现顺序表流程详解的文章就介绍到这了,更多相关数组模拟实现顺序表内容请搜索海外IDC网以前的文章或继续浏览下面的相关文章希望大家以后多多支持海外IDC网！

【文章转自：http://www.1234xp.com/xjp.html 复制请保留原URL】

海外服务器

C语言数据结构之数组模拟实现顺序表流程详解

目录

线性表和顺序表

线性表

顺序表

静态顺序表

动态顺序表

C语言 数据结构之数组模拟实现顺序表流程详解

目录

线性表和顺序表

线性表

顺序表

静态顺序表

动态顺序表

C语言数据结构之数组模拟实现顺序表流程详解