【数据结构——顺序表三种数据结构差异】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构——顺序表三种数据结构差异】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构——顺序表的三种数据结构

数据结构：就是数据之间的关系。
数据结构的关系：一对多，多对多，集合，网络

顺序表的三种数据结构

第一种顺序表数据结构

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//第一种设计方式
#define SEQSIZE 100 //定义一个宏，后面调用SEQSIZE都可以替换成100
typedef int ElemType;//将int重命名为ElemType

typedef struct
{
	ElemType data[SEQSIZE];
	int cursize;
}SeqList;

//初始化
void InitList(SeqList *list)
{
	list->cursize = 0;
}
bool push_back(SeqList *list,ElemType value)
{
	//检查顺序表是否已满
	if(list->cursize == SEQSIZE)
	{
		printf("顺序表已满");
		return false;
	}
	list->data[list->cursize]= value;
	list->cursize += 1;
	return true;
}
//销毁
void DestroyList(SeqList *list)
{
//其实可以不进行销毁，因为此时的数组是临时变量，当SeqList实例销毁，list也会被销毁
	list->cursize = 0;
}
int main()
{
	int value = 0;
	SeqList mylist;
	InitList(&mylist);
	for(int i = 0;i<10;i++)
	{
		push_back(&mylist,i);
	}
	DestroyList(&mylist);
}

第二种顺序表数据结构

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

//第二种设计方式
#define SEQSIZE 100
#define INCSIZE 2 //顺序表空间不足时，每次增加的空间数量
typedef int ElemType;
typedef struct 
{
	ElemType* data;
	int cursize;//已存储的元素数量
	int maxsize;//能够存储的最大数量
}SeqList;
//初始化
void InitList(SeqList *list)
{
	list->data = (ElemType*)malloc(sizeof(ElemType)*(SEQSIZE));
	if (!list->data)
	{
		exit(EXIT_FAILURE);//如果分配失败则退出程序
	}
	list->cursize = 0;
	list->maxsize = SEQSIZE;
}
bool push_back(SeqList *list,ElemType value)
{
	if(list->cursize == list->maxsize)
	{
		printf("顺序表已满");
		return false;
	}
	list->data[list->cursize]=value;
	list->cursize ++;
	return true;
}
void DestroyList(SeqList *list)
{
	free(list->data);
	list->data = NULL;
	list->cursize =0;
	list->maxsize = 0;
}
int main()
{
	SeqList mylist;
	InitList(&mylist);
	for(int i = 0;i<10;i++)
	{
		push_back(&mylist,i);
	}
	DestroyList(&mylist);
}

第三种顺序表数据结构

//第三种设计方式
#include <stdio.h>
#include <stdlib.h>

#define SEQSIZE 100
#define INCSIZE 2
typedef int ElemType;
typedef struct
{
	ElemType* first;
	ElemType* last;
	ElemType* end;	
}SeqList;
void InitList(SeqList *list)
{
	list->first = (ElemType*)malloc(sizeof(ElemType)*SEQSIZE);
	if(!list->first)
	{
		exit(EXIT_FAILURE);
	}
	list->last = list->first;
	list->end = list->first + SEQSIZE;
}
bool push_back(SeqList *list,ElemType value)
{
	if(list->last == list->end)
	{
		printf("顺序表已满");
		return false;
	}
	*(list->last)=value;
	list->last ++;
	return true;
}
void DestroyList(SeqList *list)
{
	free(list->first);
	list->first = NULL;
	list->last = NULL;
	list->end = NULL;
}
int main()
{
	SeqList mylist;
	InitList(&mylist);
	for(int i = 0;i<10;i++)
	{
		push_back(&mylist,i);
	}
	 DestroyList(&mylist);
	 return 0；
}

顺序表的三种数据结构使用差异

从初始化InitList、摧毁DestroyList、尾插法Push_back来比较三者差异。文章来源地址https://www.toymoban.com/news/detail-831757.html

数据结构	InitList
第一种	只需要定义cursize
第二种	需要动态申请内存，还需要定义cursize
第三种	需要动态申请内存，需要定义last、end指向

数据结构	DestroyList
第一种	因为是变量，当调用结束，结构体直接释放内存，只需要将cursize置为空。
第二种	动态生成的空间，需要free内存，并且需要将指针置为空（防止空悬指针）。
第三种	动态生成的空间，需要free内存，并且需要将指针置为空（防止空悬指针）。需要将其他指针置为空（可选）。

数据结构	Push_back
第一种	因为是数组，直接存在末尾位置，当前元素数量+1
第二种	动态生成空间可以看成存在当前末尾位置，当前元素数量+1
第三种	动态生成空间，数据存储在当前元素指针指向的最后一个位置，指针位置+1

数据结构	优点	缺点
第一种	便捷简单，不需要动态内存管理	申请空间多了，占内存；申请空间少了，放不下，不能动态扩容
第二种	可以扩容，扩容只需要更改maxsize的数量，相比较第三种更好管理	需要动态管理内存
第三种	可以扩容	扩容时first、last、end指针都需要更改，比较麻烦