数据结构与算法 | 顺序表的动态分配

2021年09月15日 阅读数:1
这篇文章主要向大家介绍数据结构与算法 | 顺序表的动态分配,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

1024G 嵌入式资源大放送!包括但不限于C/C++、单片机、Linux等。关注微信公众号【嵌入式大杂烩】,回复1024,便可免费获取!html

这篇写的是顺序表——动态数组。关于顺序表的具体描述可看上一篇文章写的是顺序表——静态分配算法

 

一、顺序表的结构定义数组

数据结构与算法 | 顺序表的动态分配_算法

 

二、建立一个顺序表:(5,2,0,13,14)微信

数据结构与算法 | 顺序表的动态分配_数据结构_02

 

三、查找操做数据结构

数据结构与算法 | 顺序表的动态分配_数据结构_03

 

 

四、替换旧元素old_elem为新元素new_elemide

数据结构与算法 | 顺序表的动态分配_数据结构_04

 

五、替换位置pos上的数据为elem函数

数据结构与算法 | 顺序表的动态分配_算法_05

 

六、插入操做spa

数据结构与算法 | 顺序表的动态分配_算法_06

 

七、删除操做.net

数据结构与算法 | 顺序表的动态分配_算法_07

 

八、销毁函数指针

数据结构与算法 | 顺序表的动态分配_算法_08

 

 

程序运行结果:

数据结构与算法 | 顺序表的动态分配_算法_09

 

完整程序:
/*----------------------------------------------------------------------------------------
	
	程序说明:顺序表(动态数组实现)
    建立日期:2018.12.09 by LiZhengNian

----------------------------------------------------------------------------------------*/

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

#define SIZE 5

/* 数据元素类型 */
typedef int SqType;

/* 顺序表的结构定义 */
typedef struct Sqlist
{
	SqType *elem;  // 定义一个动态数组elem
	int length;    // 顺序表的长度
	int size;      // 顺序表的存储容量
}Sqlist;

/* 函数的声明 */
Sqlist init_list(void);                                			// 初始化顺序表
void printf_list(Sqlist l);                            			// 打印顺序表
int serch(Sqlist l, SqType elem);								// 查找元素位置	
Sqlist replace_elem(Sqlist l, SqType old_elem, SqType new_elem);// 替换旧元素old_elem为新元素new_elem
Sqlist replace_pos(Sqlist l, int pos, SqType elem);				// 替换位置pos上的元素为elem
Sqlist insert(Sqlist l, int pos, SqType elem);					// 插入新元素
Sqlist delete(Sqlist l, int pos);								// 删除元素
void destroy_list(Sqlist l);										// 销毁顺序表


int list[SIZE] = {5, 2, 0, 13, 14};	// 用于初始化顺序表
/*******************************************************************************************************
** 函数: main,主函数
**------------------------------------------------------------------------------------------------------
** 参数: void
** 返回: 无
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
int main(void)
{
	Sqlist l;
	int pos = 0;
	int serch_elem = 13;
	
	/* 建立一个顺序表:(5, 2, 0, 13, 14) */
	l = init_list();
	printf("建立的顺序表为:");
	printf_list(l);
	
	/* 把旧元素0替换为新元素1 */
	l = replace_elem(l, 0, 1);
	printf("把0替换为1获得的新顺序表为:");
	printf_list(l);	
	
	/* 把第1个位置上的元素改成10 */
	l = replace_pos(l, 1, 10);
	printf("第一个位置改成10获得的新顺序表为:");
	printf_list(l);		
	
	/* 往第二个位置插入新元素99 */
	l = insert(l, 2, 99);
	printf("第二个位置插入99获得的新顺序表为:");
	printf_list(l);		
	
	/* 删除第二个位置上的元素 */
	l = delete(l, 2);
	printf("删除第二个位置元素获得的新顺序表为:");
	printf_list(l);		
	
	/* 查找serch_elem在该顺序表l中的第几个位置 */
	pos = serch(l, serch_elem); 
	printf("元素%d在顺序表的第%d个位置\n", serch_elem, pos);
	
	/* 销毁顺序表 */
	printf("\n销毁顺序表\n");
	destroy_list(l);
	
	return 0;
}

/*******************************************************************************************************
** 函数: create_list,建立一个顺序表
**------------------------------------------------------------------------------------------------------
** 参数: void
** 返回: 建立成功的顺序表
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
Sqlist init_list(void)
{
	Sqlist l;
	int i;
	
	l.elem = (SqType*)malloc(SIZE*sizeof(SqType)); // 动态申请空间
	if(!l.elem) //若是申请失败,做出提示并直接退出程序
	{
		printf("%s:申请动态内存失败!\n",__FUNCTION__);
		exit(0);	// 退出程序
	}
	
	for (i = 0; i < SIZE; i++)
	{
		l.elem[i] = list[i];
	}
	l.length = SIZE;  // 此时顺序表表长为SIZE
	l.size = SIZE;    // 此时顺序表占的的存储单元个数为SIZE
	
	return l;
	
}

/*******************************************************************************************************
** 函数: serch,查找元素elem在顺序表l的第几个位置
**------------------------------------------------------------------------------------------------------
** 参数: l:顺序表   elem:要查找的元素
** 返回: pos:元素elem的位置  -1:查找失败
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
int serch(Sqlist l, SqType elem)
{
	int i;
	int pos = 0;
	
	for (i = 0; i < l.length; i++)
	{
		if (elem == l.elem[i])
		{
			pos = i + 1;
			return pos;	// 查找成功
		}
	}
	
	return -1;	// 查找失败
}

/*******************************************************************************************************
** 函数: replace_elem,把旧元素old_elem替换为新元素new_elem
**------------------------------------------------------------------------------------------------------
** 参数: l:顺序表  old_elem:旧元素  new_elem:新元素
** 返回: 替换完成后的新的顺序表l
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
Sqlist replace_elem(Sqlist l, SqType old_elem, SqType new_elem)
{
	int old_elem_pos;
	
	old_elem_pos = serch(l, old_elem);	// 首先查找旧元素所在的位置
	l.elem[old_elem_pos - 1] = new_elem;
	
	return l;   // 返回新生成的顺序表
}

/*******************************************************************************************************
** 函数: replace_pos,把第pos个位置上的元素替换为elem
**------------------------------------------------------------------------------------------------------
** 参数: l:顺序表  pos:位置  elem:元素
** 返回: 替换完成后的新的顺序表l
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
Sqlist replace_pos(Sqlist l, int pos, SqType elem)
{
	l.elem[pos - 1] = elem;
	
	return l; // 返回新生成的顺序表
}

/*******************************************************************************************************
** 函数: insert,把元素elem插入到顺序表l的第pos个位置
**------------------------------------------------------------------------------------------------------
** 参数: l:顺序表  pos:位置  elem:元素
** 返回: 插入元素后获得的新的顺序表l
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
Sqlist insert(Sqlist l, int pos, SqType elem)
{
	int i;
	/* 判断插入的位置是否存在、是否是超过了表的长度 */
	if (pos < 1 || pos > l.length)
	{
		printf("%s:插入错误!\n", __FUNCTION__);
		return l;
	}
	/* 插入新元素,所以须要从新申请内存 */
	if (l.length >= l.size)
	{
		l.elem = (SqType*)realloc(l.elem, (l.size+1)*sizeof(SqType));
		if (!l.elem)
		{
			printf("%s:从新申请动态内存失败!\n",__FUNCTION__);
			exit(0);	// 退出程序
		}
		l.size += 1;
	}
	l.length += 1;	// 插入一个新元素,表长加一
	/* 从第pos个位置开始全部元素日后移一个元素长度 */ 
	for (i = l.length - 1; i >= pos-1; i--)
	{
		l.elem[i+1] = l.elem[i];
	}
	
	l.elem[pos-1] = elem; // 插入的新元素
	
	return l;  // 返回新生成的顺序表
}

/*******************************************************************************************************
** 函数: delete,把第pos个位置的元素删除
**------------------------------------------------------------------------------------------------------
** 参数: l:顺序表  pos:位置 
** 返回: 删除元素后获得的新的顺序表l
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
Sqlist delete(Sqlist l, int pos)
{
	int i;
	/* 判断要删除的位置是否存在、是否是超过了表的长度 */
	if (pos < 1 || pos > l.length)
	{
		printf("%s:删除位置错误!\n", __FUNCTION__);
		return l;
	}
	
	/* 从第pos个位置开始全部元素前移一个元素长度 */
	for (i = pos-1; i < l.length; i++)
	{
		l.elem[i] = l.elem[i+1];
	}
	
	l.length -= 1;	// 删除一个元素后表长减一
	
	return l;  // 返回新生成的顺序表
}

/*******************************************************************************************************
** 函数: destroy_list,销毁顺序表
**------------------------------------------------------------------------------------------------------
** 参数: l:要销毁的顺序表
** 返回: void
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
void destroy_list(Sqlist l)
{
	free(l.elem);	// 释放动态内存,防止内存泄漏
	l.elem = NULL;  // 防止出现野指针
}

/*******************************************************************************************************
** 函数: printf_list,打印输出顺序表
**------------------------------------------------------------------------------------------------------
** 参数: l:顺序表  pos:位置 
** 返回: 删除元素后获得的新的顺序表l
** 日期: 2018.12.09 by LiZhengNian
********************************************************************************************************/
void printf_list(Sqlist l)
{
	int i;
	for(i = 0; i < l.length; i++)
	{
		printf("%d ",l.elem[i]);
	}
	printf("(表长为%d)", l.length);
	printf("\n\n");
}

 

相关资料:

(1)http://blog.csdn.net/flueky/article/details/52711668