C/C++|【数据结构笔记】顺序表——动态数组 C

本文更好的排版方式：http://mp.weixin.qq.com/s?__biz=MzU5MzcyMjI4MA==&mid=100000721&idx=1&sn=d2ed514917c7dce244d1c78bba16eeb9&chksm=7e0d6d16497ae4002106e22ab6a8aba13a883f24402cd01717cd6af5035850e61bda71636c66#rd

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

1、顺序表的结构定义

文章图片

2、创建一个顺序表：（5，2，0，13，14）

文章图片

【C/C++|【数据结构笔记】顺序表——动态数组】
3、查找操作

文章图片

4、替换旧元素old_elem为新元素new_elem

文章图片

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

文章图片

6、插入操作

文章图片

7、删除操作

文章图片

8、销毁函数

文章图片

程序运行结果：

文章图片

完整程序：

/*---------------------------------------------------------------------------------------- 程序说明：顺序表（动态数组实现）创建日期：2018.12.09 by LiZhengNian----------------------------------------------------------------------------------------*/#include #include #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