数据布局概述
什么是数据布局
数据布局: 数据布局就是计算机存储,构造,管理数据的方式方法;
数据布局的类型
① 根据数据的逻辑布局划分 (数据间关系)
- 集合:数据布局中的元素之间除了"同属一个构造"之外,别无其他关系;
- 线性数据布局: 数据之间 "一对一"的关系,数据具有唯一的前驱和后继, 典型代表是链表
- 非线性数据布局:数据之间不具有唯一的前驱和后继。例如: 二维数组,二叉树., 典型代表 是二叉树
② 根据数据在内存中的存储方式划分
- 顺序布局:各个元素存储在连续的内存空间 , 典型代表是数组
- 链式布局:各个元素存储在不连续的内存空间 , 典型代表是链表
- 索引布局:元素在存储时,不但存储元素数据,还建立元素附加的索引表来标识元素的地点
- 哈希(散列)布局:元素在存储时,为元素提供关键字,在元素访问时,可根据关键字来访问数 据。
常见的数据布局
链表 顺序表 树 图 映射 栈 队列.
算法分析
算法分析是指算法在正确的情况下,对其优劣的分析。一个好的算法通常是指:
- . 算法对应的程序所耗时间少
- 算法对应的程序所耗存储空间少
- 算法布局性好、易读、易移植和调试
数据布局与算法的本质任务,是进步程序的时间空间效率,简单讲就是让程序的执行速度越快越 好,所需内存空间越少越好。固然在很多情况下,程序的时空特性是相互制约的,就像鱼和熊掌不 可兼得,但我们可以根据程序现实解决题目标侧重点,去均衡时间和空间的对性能的斲丧。
2.1 时间复杂度
一样平常而言,时间复杂度并不观察一段代码运行所需要的绝对时间,因为不同的计算机的硬件参数不 同,观察绝对时间没有意义。 时间复杂度一样平常指的是代码的语句执行总次数,称为语句频度。比 如
- void counting(int n)
- {
- for(int i=0; i<n; i++)
- {
- printf("本行语句将会出现n次\n");
- }
- for(int j=0; j<n; j++)
- {
- printf("本行语句将会出现n*n次\n");
- }
- }
复制代码 在上述代码中,程序执行的语句频度理论是:
但一样平常情况下,我们只关心多项式的最高次幂,于是上述代码的时间复杂度我们表示为:
这意味着,该程序算法所需要的时间,与传进来的参数n的平方成正比。 不同算法的时间复杂度相差很大,如下图所示,随着所处理的题目规模的增大,不同时间复杂度的 程序所需要的时间有天壤之别。
2.2 空间复杂度
空间复杂度的概念更简单一点,就是一段程序运行时所需的内存字节量。
2.3 时空复杂度互换
一段程序的性能指标,既要运行快速,又要节省内存,而通常这两者又是相互制约的,很难兼得。 因此在现实解决题目时,会根据需要侧重一方,牺牲另一方。
线性表
概念
对于一组拥有n个数据元素的线性表,其严格数学界说是:此中任何一个数据元素 ,有且仅有一 个直接前驱 ,有且仅有一个直接后继 。首元素 无直接前驱,尾元素 无直接后继。 满足这种数学关系的一组数据,当中的数据是一个挨着一个的,常被称为一对一关系。反之,假如 数据之间的关系不是一对一的,就好坏线性的。
举例
生存中的线性表例子非常多,比如一个班级中的以学号编排的学生,一座图书馆中的以序号编排的 图书、一条正常排队等候的队列、一摞从上到下堆叠的餐盘,这些都是线性表。他们的特点都是: 除了首尾两个元素,其余任何一个元素前后都对应相邻的另一个元素。
留意:
线性表是一种数据内部的逻辑关系,与存储形式无关
线性表既可以接纳连续的顺序存储(顺序表),也可以接纳离散的链式存储(链表)
顺序表
基本概念
- 顺序表:顺序存储的线性表。
- 链式表:链式存储的线性表,简称链表。
顺序存储就是将数据存储到一片连续的内存中,在C语言情况下,可以是 具名的堆数组。 具名的栈数组,或者是匿
存储方式不但仅只是提供数据的存储空间,而是必须要能体现数据之间的逻辑关系。当接纳顺序存 储的方式来存放数据时,唯一能用来表达数据间本身的逻辑关系的就是存储位置。比如队列中的两 个人,小明和小花,假如小明在逻辑上排在相邻的小花的前面,那么在存储位置上也必须把小明存 放在相邻的小花的前面。
基本操作
- 基本操作
一样平常而言,为了方便操作顺序表,需要一个专门管理顺序表的”管理布局体“,管理布局体中一样平常 会包罗:
- 顺序表总容量
- 顺序表当前最末元素下标位置
- 顺序表指针
下面是管理布局体示例代码:
- #include <stdio.h>
- #include <stdlib.h>
- #include <unistd.h>
- #include <string.h>
- typedef struct
- {
- int capacity; // 顺序表容量
- int last; // 最末元素下标
- int * data;
- }sequenceList;
复制代码
- 初始化
所谓初始化就是建立一个不包罗任何元素的顺序表,设置好管理布局体中的表的总容量、末元 素下标,申请好顺序表内存空间等系列预备工作。
下面是初始化顺序表的示例代码:
- sequenceList *init_list(int cap)
- {
- sequenceList *list = malloc(sizeof(sequenceList));
- if(list != NULL)
- {
- list -> data = malloc(sizeof(int) *cap);
- if(list -> data == NULL)
- {
- free(list);
- return NULL;
- }
- list -> capacity = cap;
- list -> last = -1;
- }
- return list;
- }
复制代码 测试
- int main()
- {
- sequenceList *list = init_list(10);
- if(list == NULL)
- {
- perror("初始化顺序表失败!");
- exit(0);
- }
- else
- {
- printf("初始化顺序表成功!\n");
- }
- }
-
复制代码
- 增删节点
在顺序表中增加一个数据,可以有多种方式,比如在原数组的末端增加,或者在原数组的头部 增加,或者在数组中间恣意一个位置增加。根据现实需要来定。
下面以在顺序表头部增删数据为例,示例代码如下:
- // 判定顺序表是否为空
- bool isEmpty(sequenceList *s)
- {
- return s->last == -1;
- }
- // 判定顺序表是否已满
- bool isFull(sequenceList *s)
- {
- return s->last == s->capacity-1;
- }
- // 在顺序表表头插入一个新数据
- bool insert(sequenceList *s, int data)
- {
- if(isFull(s))
- return false;
- // 将原有数据全部往后挪一位
- for(int i=s->last; i>=0; i--)
- s->data[i+1] = s->data[i];
-
- // 将新数据置入表头
- s->data[0] = data;
- s->last++;
- return true;
- }
- // 将顺序表表头的数据删除掉
- bool removeNode(sequenceList *s)
- {
- if(isEmpty(s))
- return false;
- // 将所有数据全部往前挪一位
- for(int i=0; i<s->last; i++)
- s->data[i] = s->data[i+1];
-
- s->last--;
- return true;
- }
复制代码
- 销毁顺序表
一个顺序表最后不再需要,应当要开释其所占用的内存空间,这被称为顺序表的销毁。
下面是销毁操作的示例代码:
- void destroy(sequenceList *s)
- {
- if(s == NULL)
- return;
- free(s->data);
- free(s);
- }
复制代码
完整代码
- #ifndef __SEQLIST_H
- #define __SEQLIST_H
- #include <stdio.h>
- #include <stdlib.h>
- #include <unistd.h>
- #include <string.h>
- #include <stdbool.h>
- typedef struct
- {
- int capacity; // 顺序表容量
- int last;
- // 最末元素下标
- int *data;
- } sequenceList;
- // 初始化顺序表
- sequenceList *init_list(int cap);
- // 判断顺序表是否写满
- bool isFull(sequenceList *list);
- // 向顺序表插入数据
- bool insert(sequenceList *s, int data);
- // 非空校验
- bool isEmpty(sequenceList *list);
- // 遍历顺序表
- void show(sequenceList *list);
- // 删除顺序表数据
- bool removeNode(sequenceList *list, int data);
- // 释放内存
- void destroy(sequenceList *s);
- #endif
复制代码
训练 1
创建一个顺序表,并从键盘吸收数字输入,将输入的正整数按从小到大的顺序插入顺序表,并在输 入负整数的时间将其绝对值数据删除。每次输入后,将顺序表的内容打印到屏幕上。
剖析 : 此题考查顺序表的基本思绪,先要筹划好顺序表的逻辑表达,再通过对顺序表的插入和删除操作, 体会顺序存储中对于插入和删除的未便性。
参考代码 :
- #include <stdio.h>
- #include <stdbool.h>
- #include <stdlib.h>
- typedef struct
- {
- int total_size; // 顺序表总容量
- int last; // 顺序表最末元素的下标
- int *data; // 顺序表的存储空间
- }sqlist;
- // 初始化一个空的顺序表
- sqlist * init_list(int total_size)
- {
- sqlist *sq = (sqlist *)malloc(sizeof(sqlist));
- if(sq != NULL)
- {
- sq->total_size = total_size;
- sq->last = -1; // 用-1表征当前没有元素
- sq->data = (int *)malloc(sizeof(int) * total_size);
- if(sq->data == NULL)
- {
- free(sq);
- }
- }
- return sq;
- }
- // 在递增的顺序表中找到x应插入的合适位置
- int get_pos(sqlist *sq, int x)
- {
- int pos = 0;
- while((pos<=sq->last) && (sq->data[pos]<x))
- pos++;
- // 当链表为空(即sq->last为-1时),返回0
- return pos;
- }
- // 判断顺序表是否已满
- bool is_full(sqlist *sq)
- {
- return sq->last >= sq->total_size-1;
- }
- // 将元素x插入顺序表sq中
- bool insert(sqlist *sq, int x)
- {
- if(is_full(sq))
- return false;
- // 在顺序表中得到即将要插入的元素x的合适的位置
- int pos = get_pos(sq, x);
- // 将顺序表中pos往后的所有元素往后挪一位
- for(int i=sq->last; i>=pos; i--)
- sq->data[i+1] = sq->data[i];
- sq->data[pos] = x;
- sq->last++;
- return true;
- }
- // 在顺序表sq中,定位元素x
- int locate(sqlist *sq, int x)
- {
- int pos;
- for(pos=0; pos<=sq->last; pos++)
- {
- if(sq->data[pos] == x)
- {
- printf("data[%d]=%d\n", pos, x);
- return pos;
- }
- }
- return -1;
- }
- // 从顺序表中将元素x剔除
- bool delete(sqlist *sq, int x)
- {
- int pos;
- pos = locate(sq, x);
- // 元素x不存在
- if(pos == -1)
- return false;
- // 将pos后续的元素全部往前挪一位
- for(; pos<=sq->last; pos++)
- sq->data[pos] = sq->data[pos+1];
- sq->last--;
- return true;
- }
- // 展示顺序表元素
- void show_data(sqlist *sq)
- {
- for(int i=0; i<=sq->last; i++)
- printf("\tsq->data[%d]=%d\n", i, sq->data[i]);
- printf("=======================\n");
- }
- int main(int argc, char *argv[])
- {
- // 初始化一条空的顺序表
- sqlist *sq = init_list(10);
- // 插入元素
- int num;
- while(1)
- {
- scanf("%d", &num);
- if(num > 0)
- {
- if(insert(sq, num))
- show_data(sq);
- else
- fprintf(stderr, "顺序表已满\n");
- }
- else if(num < 0)
- {
- if(delete(sq, -num))
- show_data(sq);
- else
- fprintf(stderr, "元素不存在\n");
- }
- else
- {
- fprintf(stderr, "BYE\n");
- break;
- }
- }
- return 0;
- }
复制代码 顺序表优缺点总结
顺序存储中,由于逻辑关系是用物理位置来表达的,因此从上述示例代码可以很清楚看到,增删数 据都非常困难,需要成片地移动数据。顺序表对数据节点的增删操作是很不友好的。 总结其特点如下:
- 不需要多余的信息来记录数据间的关系,存储密度高
- 全部数据顺序存储在一片连续的内存中,支持立即访问恣意一个随机数据,比如上述顺序表中 第个节点是 s->data
- 插入、删除时需要保持数据的物理位置反映其逻辑关系,一样平常需要成片移动数据
- 当数据节点数目较多时,需要一整片较大的连续内存空间
- 当数据节点数目变化剧烈时,内存的开释和分配不机动
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |