1. 首页
  2. 文章中心
  3. C语言

C语言动态顺序表实例代码

180 阅读 0 评论
我是靠谱客的博主 细腻毛巾，最近开发中收集的这篇文章主要介绍C语言动态顺序表实例代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

顺序表概念：

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

代码解析：

一.准备工作

1. 首先对一些头文件的引用和创建一个结构体，结构体包含一个数组，size表示该数组目前有多少个元素，capacity表示目前数组能存多少个元素。例如：

 

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
 
typedef int DataType;
typedef struct SeqList
{
	DataType* a;
	int size;
	int capacity;
}SL;

2.创建一个顺序表

SL sl;

二、顺序表的基本操作 

1.顺序表的初始化函数

         注意这里的参数得是指针，形参是实参的一份临时拷贝，所以得把地址传给函数才能改变值。

void SeqListInit(SL* sl)
{
	sl->a = NULL;
	sl->size = 0;
	sl->capacity = 0;
}

2.尾插函数（在尾部插入数据）

        写尾插函数之前我们得先判断一下数组空间是否够。例如下面的例子。

所以我们要先检查空间是否满了，满了就扩容

将这个判断空间函数命名为  void CheckSpace(SL* sl) （这是动态顺序表区别于静态顺序表最主要的部分） 

void CheckSpace(SL* sl)
{
	if (sl->size == sl->capacity)
	{
		//因为capacity一开始等于0，所以先给capacity一个值
		int newcapacity = sl->capacity == 0 ? 4 : sl->capacity * 2;
		DataType* tmp = (DataType*)realloc(sl->a, sizeof(DataType)*newcapacity);
		if (tmp == NULL)
		{
			printf("开辟失败n");
			exit(-1);
		}
		else
		{
			sl->capacity = newcapacity;
			sl->a = tmp;
		}
	}
}

尾插函数：

void SeqListPushBack(SL* sl, DataType x)
{
CheckSpace(sl);
	sl->a[sl->size] = x;
	sl->size++;
}

3.头插函数（在数组头部插入数据）

        

void SeqListPushFront(SL* sl, DataType x)
{
	//因为插入的时候都要检查空间是不是满了，满了就扩容
	CheckSpace(sl);
	for (int end = sl->size - 1; end >= 0; end--)
	{
		sl->a[end + 1] = sl->a[end];
	}
	sl->a[0] = x;
	sl->size++;
}

 挪数据对应着for循环的代码，最后再给数组的第一个位置赋值。别忘了对size+1.

 4.尾删函数

        如果size等于0了就说明顺序表中没有数据了，所以

void SeqListPopBack(SL* sl)
{
	assert(sl->size > 0);
	sl->size--;
}

5.头删函数

        从第二个数据开始整体往前挪以为就可以了。（要从前面开始挪）：

void SeqListPopFront(SL* sl)
{
	for (int i = 1; i < sl->size; i++)
	{
		sl->a[i - 1] = sl->a[i];
	}
	sl->size--;
}

6.在第pos的位置插入数据

        首先pos不能小于现有的数据个数。

        第二判断空间，满了就扩容。

        第三：从第pos个位置的数据开始（这里第pos个位置的数据在数组中的下标是pos-1） 将后面的数据整体往后挪一位。

        第四：再这个位置赋值，别忘了对size++；

void SeqListInsert(SL* sl, int pos, DataType x)
{
	//查看空间
	assert(pos <= sl->size);
	CheckSpace(sl);
	for (int end = sl->size-1; end >= pos-1; end--)//这里不能用sl->size--
	{
		sl->a[end+1] = sl->a[end];
	}
	sl->a[pos - 1] = x;
	sl->size++;
}

7.删除第pos个位置的数据

        首先pos不能小于现有数据个数

        第二：将从第pos个位置的数据开始到最后一个数据往前挪一位

        第三：对size-- 

void SeqListErase(SL* sl, int pos)
{
	assert(pos <=sl->size);
	for (int i = pos; i < sl->size; i++)
	{
		sl->a[i - 1] = sl->a[i];
	}
	sl->size--;
}

8.修改第pos个位置的数据

        一：pos不能小于现有数据个数

        二：赋值。第pos个位置的数据在数组中下标是pos-1。（因为数组下表从0开始）

void SeqListModify(SL* sl, int pos, DataType x)
{
	assert(pos <= sl->size);
	sl->a[pos - 1] = x;
}

9.查找函数。

        遍历一遍看是否有这个数据，有就返回数据是第几个元素。（这里我不是返回该数据在数组中的下标，我是返回 下标+1） 

        这里我没有考虑如果有两个一样的数据的情况。

int SeqListFind(SL* sl, DataType x)
{
	for (int i = 0; i < sl->size;i++)
	{
		if (sl->a[i] == x)
		{
			i++;
			printf("在第%d个位置n", i);
			return i;
		}
	}
	printf("没有此数据n");
	return -1;
}

10.销毁函数

        释放sl->a之后要对它置空，因为指针free之后,free函数只是把指针指向的内存空间释放了,即内存中存储的值,但是并没有将指针的值赋为NULL,指针仍然指向这块内存。 

void SeqListDestory(SL* sl)
{
	free(sl->a);
	sl->a = NULL;
	sl->size = 0;
	sl->capacity = 0;
}

11.打印函数

void SeqListPrint(SL* sl)
{
	for (int i = 0; i < sl->size;i++)
	{
		printf("%d ", sl->a[i]);
	}
	printf("n");
}

三、总代码：

        菜单写的比较简单。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
 
typedef int DataType;
typedef struct SeqList
{
	DataType* a;
	int size;
	int capacity;
}SL;
 
void SeqListInit(SL* sl)
{
	sl->a = NULL;
	sl->size = 0;
	sl->capacity = 0;
}
 
void SeqListPrint(SL* sl)
{
	for (int i = 0; i < sl->size; i++)
	{
		printf("%d ", sl->a[i]);
	}
	printf("n");
}
 
void CheckSpace(SL* sl)
{
	if (sl->size == sl->capacity)
	{
		//因为capacity一开始等于0，所以先给capacity一个值
		int newcapacity = sl->capacity == 0 ? 4 : sl->capacity * 2;
		DataType* tmp = (DataType*)realloc(sl->a, sizeof(DataType)*newcapacity);
		if (tmp == NULL)
		{
			printf("开辟失败n");
			exit(-1);
		}
		else
		{
			sl->capacity = newcapacity;
			sl->a = tmp;
		}
	}
}
 
void SeqListPushBack(SL* sl, DataType x)
{
	//看空间是不是满了，满了就扩容
	//if (sl->size == sl->capacity)
	//{
	//	//因为capacity一开始等于0，所以先给capacity一个值
	//	int newcapacity = sl->capacity == 0 ? 4 : sl->capacity * 2;
	//	DataType* tmp = (DataType*)realloc(sl->a, sizeof(DataType)*newcapacity);
	//	if (tmp == NULL)
	//	{
	//		printf("开辟失败n");
	//		exit(-1);
	//	}
	//	else
	//	{
	//		sl->a = tmp;
	//	}
	//}
	//封装成一个函数
	CheckSpace(sl);
	sl->a[sl->size] = x;
	sl->size++;
}
 
void SeqListPushFront(SL* sl, DataType x)
{
	//因为插入的时候都要检查空间是不是满了，满了就扩容
	CheckSpace(sl);
	for (int end = sl->size - 1; end >= 0; end--)
	{
		sl->a[end + 1] = sl->a[end];
	}
	sl->a[0] = x;
	sl->size++;
}
 
void SeqListPopBack(SL* sl)
{
	assert(sl->size > 0);
	sl->size--;
}
 
void SeqListPopFront(SL* sl)
{
	for (int i = 1; i < sl->size; i++)
	{
		sl->a[i - 1] = sl->a[i];
	}
	sl->size--;
}
 
void SeqListInsert(SL* sl, int pos, DataType x)
{
	//查看空间
	assert(pos <= sl->size);
	CheckSpace(sl);
	for (int end = sl->size - 1; end >= pos - 1; end--)//这里不能用sl->size--
	{
		sl->a[end + 1] = sl->a[end];
	}
	sl->a[pos - 1] = x;
	sl->size++;
}
 
void SeqListErase(SL* sl, int pos)
{
	assert(pos <= sl->size);
	for (int i = pos; i < sl->size; i++)
	{
		sl->a[i - 1] = sl->a[i];
	}
	sl->size--;
}
 
void SeqListModify(SL* sl, int pos, DataType x)
{
	assert(pos <= sl->size);
	sl->a[pos - 1] = x;
}
 
int SeqListFind(SL* sl, DataType x)
{
	for (int i = 0; i < sl->size; i++)
	{
		if (sl->a[i] == x)
		{
			i++;
			printf("在第%d个位置n", i);
			return i;
		}
	}
	printf("没有此数据n");
	return -1;
}
 
void SeqListDestory(SL* sl)
{
	free(sl->a);
	sl->a = NULL;
	sl->size = 0;
	sl->capacity = 0;
}
 
 
void menu()
{
	printf("******************************n");
	printf("*** 1.尾插数据  2.头插数据 ***n");
	printf("*** 3.在第pos个位置插入数据***n");
	printf("*** 4.尾删数据  5.头删数据 ***n");
	printf("*** 6.在第pos个位置删除数据***n");
	printf("*** 7.修改第pos个位置的数据***n");
	printf("*** 8.查找数据 9.打印数据  ***n");
	printf("********** -1.退出 ***********n");
	printf("******************************n");
}
int main()
{
	SL sl;
	SeqListInit(&sl);
	int option = 0;
	int x = 0;
	int pos = 1;
	while (option != -1)
	{
		menu();
		scanf("%d", &option);
		switch (option)
		{
		case 1:
			printf("请输入要插入的数据，以-1结束：n");
			do
			{
				scanf("%d", &x);
				if (x != -1)
				{
					SeqListPushBack(&sl, x);
				}
			} while (x != -1);
			break;
		case 2:
			printf("请输入要插入的数据，以-1结束：n");
			do
			{
				scanf("%d", &x);
				if (x != -1)
				{
					SeqListPushFront(&sl, x);
				}
			} while (x != -1);
			break;
		case 3:
			printf("请输入要插入的数据，要从第几个插入,以非正正数结束n");
			do
			{
				scanf("%d", &x);
				scanf("%d", &pos);
				if (pos >= 0)
				{
					SeqListInsert(&sl, pos, x);
				}
			} while (pos >= 0);
			break;
		case 4:
			SeqListPopBack(&sl);
			break;
		case 5:
			SeqListPopFront(&sl);
			break;
		case 6:
			printf("请输入要删除第几个位置的数据，以非正正数结束n");
			do
			{
				scanf("%d", &pos);
				if (pos>0)
				{
					SeqListErase(&sl, pos);
				}
			} while (pos>0);
			break;
		case 7:
			printf("请输入要修改的数据，要修改第几个数据,以非正整数结束n");
			do
			{
				scanf("%d", &x);
				scanf("%d", &pos);
				if (pos>0)
				{
					SeqListInsert(&sl, pos, x);
				}
			} while (pos>0);
			break;
		case 8:
			printf("请输入需要查找的数据n");
			scanf("%d", &x);
			SeqListFind(&sl, x);
			break;
		case 9:
			SeqListPrint(&sl);
			break;
		case -1:
			printf("退出n");
			break;
		default:
			printf("输入错误，请重新输入n");
		}
	}
	SeqListDestory(&sl);
	return 0;
}

到此这篇关于C语言动态顺序表实例代码的文章就介绍到这了,更多相关C语言顺序表内容请搜索靠谱客以前的文章或继续浏览下面的相关文章希望大家以后多多支持靠谱客！

最后

以上就是细腻毛巾为你收集整理的C语言动态顺序表实例代码的全部内容，希望文章能够帮你解决C语言动态顺序表实例代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(119)

相关文章

C语言数据结构与算法之排序总结(二)
C语言数据结构与算法之排序总结(二)
C语言之快速排序算法(递归Hoare版)介绍
C语言之快速排序算法(递归Hoare版)介绍
C语言圣诞树的实现示例
C语言圣诞树的实现示例
C语言函数栈帧的创建和销毁介绍
C语言函数栈帧的创建和销毁介绍
C语言动态顺序表实例代码
C语言动态顺序表实例代码
EasyC++单独编译
EasyC++单独编译
C语言实战之纸牌游戏
C语言实战之纸牌游戏
C语言switch语句详解
C语言switch语句详解

评论列表共有 0 条评论

立即
投稿
返回
顶部