首页 > 代码库 > 数据结构线性存储之连续存储数组的实现
数据结构线性存储之连续存储数组的实现
归纳：
线性
连续存储【数组】
优点：存取速度快（元素可以直接定位到）
缺点：插入删除元素慢（因为要移动其他元素），空间通常有限制
离散存储【链表】
优点：空间没有限制，插入删除元素很快
缺点：存取速度很慢（要一个一个遍历，一个一个找）
线性结构的应用：
1. 栈
2. 队列
非线性
树
图
#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define bool int#define false 0#define true 1/*连续存储数组的算法表示这个程序，用数据结构实现了数组的初始化（开辟内存，确定数组长度）、追加、在某一位置插入元素、删除元素、得到元素、判断是否为空、是否已满、排序数组、遍历展示数组元素、倒序数组的功能。*/// 定义了一个数据类型，该数据类型的名字叫做struct Arr，该数据类型含有三个成员struct Arr{ int *pBase; // 存储的是数组的首地址 int len; // 数组所能容纳的最大元素的个数 int cnt; // 当前数组的有效元素的个数};void init_arr(struct Arr *pArr, int length);bool append_arr(struct Arr *pArr, int val); // 追加bool insert_arr(struct Arr *pArr, int pos, int val); // pos的值从1开始bool delete_arr(struct Arr *pArr, int pos, int *pVal);//int get();bool is_empty(struct Arr *pArr);bool is_full(struct Arr *pArr);void sort_arr(struct Arr *pArr);void show_arr(struct Arr *pArr);void inverse_arr(struct Arr *pArr);int main(void){ struct Arr arr; int val; init_arr(&arr, 6); if(append_arr(&arr, 7)) { printf("追加成功！\n"); } append_arr(&arr, -5); append_arr(&arr, 2); append_arr(&arr, 8); append_arr(&arr, 11); //insert_arr(&arr, 3, 384); /* if(delete_arr(&arr, 1, &val)) { printf("删除成功！\n"); printf("您删除的元素是：%d\n", val); } else { printf("删除失败！"); } */ //inverse_arr(&arr); sort_arr(&arr); show_arr(&arr); printf("数组的长度为：%d\n", arr.len); printf("数组里有效的元素个数为：%d\n", arr.cnt); return 0;}void init_arr(struct Arr *pArr, int length){ //(*pArr).len = 99; //pArr->len = 99; pArr->pBase = (int *)malloc(sizeof(int)*length); if(pArr->pBase == NULL) { printf("动态内存分配失败！\n"); exit(-1); // 终止整个程序，需要头文件stdlib.h } else { pArr->len = length; pArr->cnt = 0; } return; // 代表程序终止了}bool is_empty(struct Arr *pArr){ if(pArr->cnt == 0) return true; else return false;}bool is_full(struct Arr *pArr){ if(pArr->len == pArr->cnt) return true; else return false;}void show_arr(struct Arr *pArr){ if(is_empty(pArr)) { printf("数组为空！\n"); } else { // 输出数组的有效内容 int i; for(i = 0;i < pArr->cnt;i++) { printf("%d\n", pArr->pBase[i]); } }}bool append_arr(struct Arr *pArr, int val){ if(is_full(pArr)) { return false; } else { pArr->pBase[pArr->cnt] = val; (pArr->cnt)++; return true; }}bool insert_arr(struct Arr *pArr, int pos, int val){ int i; // 保证程序的合理性，写出健壮性的代码： if(is_full(pArr)) return false; if(pos < 1 || pos > (pArr->cnt + 1)) return false; for(i = (pArr->cnt) - 1;i >= (pos - 1);i--) { //printf("%d\n", i); pArr->pBase[i + 1] = pArr->pBase[i]; } pArr->pBase[pos - 1] = val; (pArr->cnt)++; return true;}bool delete_arr(struct Arr *pArr, int pos, int *pVal){ int i; // 把不合法的排去 if(is_empty(pArr)) return false; if(pos < 1 || pos > pArr->cnt) return false; *pVal = pArr->pBase[pos - 1]; for(i = pos; i < pArr->cnt; i++) { pArr->pBase[i - 1] = pArr->pBase[i]; } (pArr->cnt)--; return true;}void inverse_arr(struct Arr *pArr){ int i = 0; int j = (pArr->cnt)-1; int t; while (i < j) { t = pArr->pBase[i]; pArr->pBase[i] = pArr->pBase[j]; pArr->pBase[j] = t; i++; j--; } return;}// 冒泡排序void sort_arr(struct Arr *pArr){ int i, j; int t; for(i = 0;i < pArr->cnt;i++) { for(j = i + 1; j < pArr->cnt;j++) { if(pArr->pBase[i] > pArr->pBase[j]) { t = pArr->pBase[i]; pArr->pBase[i] = pArr->pBase[j]; pArr->pBase[j] = t; } } }}
数据结构线性存储之连续存储数组的实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。