顺序存储之顺序表

顺序表的创建与操作(顺序存储)

1.首先我们需要定义数据类型

//定义数据类型  这儿我们使用int
typedef int DATA;   //给int取别名为DATA

2.构建顺序表的排序准则

//定义顺序表以index为顺序升序或降序排序
struct Node
{
	int index;
	DATA data;
};

3.定义顺序表结构

typedef struct seqList
{
	int size;     //当前顺序表长度
	struct Node* memory;   //存储顺序表数据的内存
}SQL,*LPSQL;
//SQL为该结构体类型的别名
//LPSQL为该结构体指针类型的别名

4.顺序表的创建

LPSQL createSeqList()
{
	LPSQL sqlist = (LPSQL)malloc(sizeof(SQL));
	if (NULL == sqlist)
	{
		printf("顺序表创建失败!");
		return NULL;
	}
	sqlist->size = 0;
	sqlist->memory = (struct Node*)malloc(sizeof(struct Node) * MAX);
	return sqlist;
}

5.顺序表的扩容

//这里直接采用扩大两倍内存的方式
void reallocMemeory(LPSQL sqlist, int curSize, int newSize)
{
	int max = curSize > newSize ? curSize : newSize;
	(struct Data*)realloc(sqlist->memory, sizeof(struct Node) * max);
}

6.顺序表的数据插入

//插入,我们采用直接插入到表尾,然后(根据准则)移动元素
//采用准则升序排序
void insertData(LPSQL sqlist, struct Node data)
{
	if (sqlist->size == MAX)
	{
		reallocMemeory(sqlist, MAX, MAX * 2);
		printf("顺序表已扩容\n");
	}
	//直接插在表尾
	sqlist->memory[sqlist->size] = data;
	//调整位置
	for (int i = sqlist->size; i > 0; i--)   //注意此处下标越界问题
	{
		if (sqlist->memory[i - 1].index > sqlist->memory[i].index)
		{
			struct Node temp = sqlist->memory[i - 1];
			sqlist->memory[i - 1] = sqlist->memory[i];
			sqlist->memory[i] = temp;
		}
		else
		{
			break;
		}
	}
	sqlist->size++;
}

7.顺序表的数据删除

void deleteListData(LPSQL sqlist, int index)
{
	//找到位置  删除  移动后面的元素
	int pos = -1;
	for (int i = 0; i < sqlist->size; i++)
	{
		if (sqlist->memory[i].index == index)
		{
			pos = i;
			break;
		}
	}if (pos == -1)
	{
		printf("顺序表之中没有该元素!");
		return;
	}
	else  //移动元素
	{
		for (int i = pos; i < sqlist->size; i++)
		{
			sqlist->memory[i] = sqlist->memory[i + 1];
		}
	}
	sqlist->size--;
}

8.顺序表的遍历

void traverseList(LPSQL sqlist)
{
	for (int i = 0; i < sqlist->size; i++)
	{
		printf("index: %d\tDATA:%d\n", (sqlist->memory[i]).index,
			(sqlist->memory + i)->data);
	}
	printf("\n");
}

9.顺序表的销毁

//这里因为需要改变指针的指向,因此需要传入二级指针
void deleteList(LPSQL* psqlist)
{
	free(*psqlist);
	printf("销毁成功\n");
}

总体代码

#include<stdio.h>
#include<stdlib.h>   //system()函数头文件
#define MAX 2       //定义一个初始长度

//定义数据类型  这儿我们使用int
typedef int DATA;   
//构建准则 (构建顺序表以何种顺序排列)
struct Node
{
	int index;
	DATA data;
};
//定义顺序表结构
typedef struct seqList
{
	int size;     //当前顺序表长度
	struct Node* memory;   //存储顺序表数据的内存
}SQL,*LPSQL;
//创建顺序表
LPSQL createSeqList()
{
	LPSQL sqlist = (LPSQL)malloc(sizeof(SQL));
	if (NULL == sqlist)
	{
		printf("顺序表创建失败!");
		return NULL;
	}
	sqlist->size = 0;
	sqlist->memory = (struct Node*)malloc(sizeof(struct Node) * MAX);
	return sqlist;
}
//顺序表扩容
void reallocMemeory(LPSQL sqlist, int curSize, int newSize)
{
	int max = curSize > newSize ? curSize : newSize;
	(struct Data*)realloc(sqlist->memory, sizeof(struct Node) * max);
}
//数据插入
void insertData(LPSQL sqlist, struct Node data)
{
	if (sqlist->size == MAX)
	{
		reallocMemeory(sqlist, MAX, MAX * 2);
		printf("顺序表已扩容\n");
	}
	//直接插在表尾
	sqlist->memory[sqlist->size] = data;
	//调整位置
	for (int i = sqlist->size; i > 0; i--)   //注意此处下标越界问题
	{
		if (sqlist->memory[i - 1].index > sqlist->memory[i].index)
		{
			struct Node temp = sqlist->memory[i - 1];
			sqlist->memory[i - 1] = sqlist->memory[i];
			sqlist->memory[i] = temp;
		}
		else
		{
			break;
		}
	}
	sqlist->size++;
}
//数据删除
void deleteListData(LPSQL sqlist, int index)
{
	//找到位置  删除  移动后面的元素
	int pos = -1;
	for (int i = 0; i < sqlist->size; i++)
	{
		if (sqlist->memory[i].index == index)
		{
			pos = i;
			break;
		}
	}if (pos == -1)
	{
		printf("顺序表之中没有该元素!");
		return;
	}
	else  //移动元素
	{
		for (int i = pos; i < sqlist->size; i++)
		{
			sqlist->memory[i] = sqlist->memory[i + 1];
		}
	}
	sqlist->size--;
}
//顺序表遍历
void traverseList(LPSQL sqlist)
{
	for (int i = 0; i < sqlist->size; i++)
	{
		printf("index: %d\tDATA:%d\n", (sqlist->memory[i]).index,
			(sqlist->memory + i)->data);
	}
	printf("\n");
}
//销毁顺序表
void deleteList(LPSQL* psqlist)
{
	free(*psqlist);
	*psqlist = NULL;
	if (NULL == psqlist)
	printf("销毁成功\n");
}
int main()
{
	//创建顺序表
	LPSQL seqList = createSeqList();
	struct Node data[8] = { {2,522},{8,528},{1,521},{3,523},
					   {5,525},{7,527},{4,524},{6,526} };
	//数据插入
	for (int i = 0; i < 8; i++)
	{
		insertData(seqList,data[i]);
	}
	//打印数据
	traverseList(seqList);
	//数据删除
	deleteListData(seqList, 3);
	//打印数据
	traverseList(seqList);
	//销毁顺序表
	deleteList(&seqList);

	system("pause");
	return 0;
}

10.输出结果

到此就结束了-------------------------->