数据布局(顺序表)

打印 上一主题 下一主题

主题 780|帖子 780|积分 2340

数据布局概述

什么是数据布局

数据布局: 数据布局就是计算机存储,构造,管理数据的方式方法;
数据布局的类型

① 根据数据的逻辑布局划分 (数据间关系)

  • 集合:数据布局中的元素之间除了"同属一个构造"之外,别无其他关系;
  • 线性数据布局: 数据之间 "一对一"的关系,数据具有唯一的前驱和后继, 典型代表是链表
  • 非线性数据布局:数据之间不具有唯一的前驱和后继。例如: 二维数组,二叉树., 典型代表 是二叉树

② 根据数据在内存中的存储方式划分

  • 顺序布局:各个元素存储在连续的内存空间 , 典型代表是数组
  • 链式布局:各个元素存储在不连续的内存空间 , 典型代表是链表
  • 索引布局:元素在存储时,不但存储元素数据,还建立元素附加的索引表来标识元素的地点
  • 哈希(散列)布局:元素在存储时,为元素提供关键字,在元素访问时,可根据关键字来访问数 据。
常见的数据布局

链表 顺序表 树 图 映射 栈 队列.
算法分析

算法分析是指算法在正确的情况下,对其优劣的分析。一个好的算法通常是指:

  • . 算法对应的程序所耗时间少
  • 算法对应的程序所耗存储空间少
  • 算法布局性好、易读、易移植和调试
数据布局与算法的本质任务,是进步程序的时间空间效率,简单讲就是让程序的执行速度越快越 好,所需内存空间越少越好。固然在很多情况下,程序的时空特性是相互制约的,就像鱼和熊掌不 可兼得,但我们可以根据程序现实解决题目标侧重点,去均衡时间和空间的对性能的斲丧。
2.1 时间复杂度

一样平常而言,时间复杂度并不观察一段代码运行所需要的绝对时间,因为不同的计算机的硬件参数不 同,观察绝对时间没有意义。 时间复杂度一样平常指的是代码的语句执行总次数,称为语句频度。比 如
  1. void counting(int n)
  2. {
  3. for(int i=0; i<n; i++)
  4. {
  5. printf("本行语句将会出现n次\n");
  6. }
  7. for(int j=0; j<n; j++)
  8. {
  9. printf("本行语句将会出现n*n次\n");
  10. }
  11. }
复制代码
在上述代码中,程序执行的语句频度理论是:

但一样平常情况下,我们只关心多项式的最高次幂,于是上述代码的时间复杂度我们表示为:

这意味着,该程序算法所需要的时间,与传进来的参数n的平方成正比。 不同算法的时间复杂度相差很大,如下图所示,随着所处理的题目规模的增大,不同时间复杂度的 程序所需要的时间有天壤之别。

2.2 空间复杂度

空间复杂度的概念更简单一点,就是一段程序运行时所需的内存字节量。
2.3 时空复杂度互换

一段程序的性能指标,既要运行快速,又要节省内存,而通常这两者又是相互制约的,很难兼得。 因此在现实解决题目时,会根据需要侧重一方,牺牲另一方。
线性表

概念

对于一组拥有n个数据元素的线性表,其严格数学界说是:此中任何一个数据元素 ,有且仅有一 个直接前驱 ,有且仅有一个直接后继 。首元素 无直接前驱,尾元素 无直接后继。 满足这种数学关系的一组数据,当中的数据是一个挨着一个的,常被称为一对一关系。反之,假如 数据之间的关系不是一对一的,就好坏线性的。
举例

生存中的线性表例子非常多,比如一个班级中的以学号编排的学生,一座图书馆中的以序号编排的 图书、一条正常排队等候的队列、一摞从上到下堆叠的餐盘,这些都是线性表。他们的特点都是: 除了首尾两个元素,其余任何一个元素前后都对应相邻的另一个元素。
   留意:
  线性表是一种数据内部的逻辑关系,与存储形式无关
  线性表既可以接纳连续的顺序存储(顺序表),也可以接纳离散的链式存储(链表)
  顺序表

基本概念


  • 顺序表:顺序存储的线性表。
  • 链式表:链式存储的线性表,简称链表。
顺序存储就是将数据存储到一片连续的内存中,在C语言情况下,可以是 具名的堆数组。 具名的栈数组,或者是匿
存储方式不但仅只是提供数据的存储空间,而是必须要能体现数据之间的逻辑关系。当接纳顺序存 储的方式来存放数据时,唯一能用来表达数据间本身的逻辑关系的就是存储位置。比如队列中的两 个人,小明和小花,假如小明在逻辑上排在相邻的小花的前面,那么在存储位置上也必须把小明存 放在相邻的小花的前面。

基本操作



  • 基本操作
    一样平常而言,为了方便操作顺序表,需要一个专门管理顺序表的”管理布局体“,管理布局体中一样平常 会包罗:

    • 顺序表总容量
    • 顺序表当前最末元素下标位置
    • 顺序表指针
    下面是管理布局体示例代码:
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <unistd.h>
    4. #include <string.h>
    5. typedef struct
    6. {
    7. int   capacity; // 顺序表容量
    8. int   last;     // 最末元素下标
    9. int * data;     
    10. }sequenceList;
    复制代码
      

    • 初始化
      所谓初始化就是建立一个不包罗任何元素的顺序表,设置好管理布局体中的表的总容量、末元 素下标,申请好顺序表内存空间等系列预备工作。
    下面是初始化顺序表的示例代码:
    1. sequenceList  *init_list(int cap)
    2. {
    3. sequenceList *list = malloc(sizeof(sequenceList));
    4. if(list != NULL)
    5. {
    6. list -> data = malloc(sizeof(int) *cap);
    7. if(list -> data == NULL)
    8. {
    9. free(list);
    10. return NULL;
    11. }
    12. list -> capacity = cap;
    13. list -> last = -1;
    14. }
    15.   return list;
    16. }
    复制代码
    测试
    1. int main()
    2. {
    3. sequenceList *list = init_list(10);
    4. if(list == NULL)
    5. {
    6.    perror("初始化顺序表失败!");
    7.         exit(0);
    8.     }
    9.     else
    10.     {
    11.         printf("初始化顺序表成功!\n");
    12.     }
    13. }
    复制代码
      

    • 增删节点
      在顺序表中增加一个数据,可以有多种方式,比如在原数组的末端增加,或者在原数组的头部 增加,或者在数组中间恣意一个位置增加。根据现实需要来定。
    下面以在顺序表头部增删数据为例,示例代码如下:
    1. // 判定顺序表是否为空
    2. bool isEmpty(sequenceList *s)
    3. {
    4.     return s->last == -1;
    5. }
    6. // 判定顺序表是否已满
    7. bool isFull(sequenceList *s)
    8. {
    9.     return s->last == s->capacity-1;
    10. }
    11. // 在顺序表表头插入一个新数据
    12. bool insert(sequenceList *s, int data)
    13. {
    14.     if(isFull(s))
    15.         return false;
    16.     // 将原有数据全部往后挪一位
    17.     for(int i=s->last; i>=0; i--)
    18.         s->data[i+1] = s->data[i];
    19.    
    20.     // 将新数据置入表头
    21.     s->data[0] = data;
    22.     s->last++;
    23.     return true;
    24. }
    25. // 将顺序表表头的数据删除掉
    26. bool removeNode(sequenceList *s)
    27. {
    28. if(isEmpty(s))
    29. return false;
    30. // 将所有数据全部往前挪一位
    31. for(int i=0; i<s->last; i++)
    32. s->data[i] = s->data[i+1];
    33.      s->last--;
    34. return true;
    35. }
    复制代码
      

    • 销毁顺序表
      一个顺序表最后不再需要,应当要开释其所占用的内存空间,这被称为顺序表的销毁。
      下面是销毁操作的示例代码:
      1. void destroy(sequenceList *s)
      2. {
      3. if(s == NULL)
      4. return;
      5. free(s->data);
      6. free(s);
      7. }
      复制代码

完整代码



  • seqlist.h
  1. #ifndef __SEQLIST_H
  2. #define __SEQLIST_H
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <unistd.h>
  6. #include <string.h>
  7. #include <stdbool.h>
  8. typedef struct
  9. {
  10. int capacity; // 顺序表容量
  11. int last;     
  12. // 最末元素下标
  13. int *data;   
  14. } sequenceList;
  15. // 初始化顺序表
  16. sequenceList *init_list(int cap);
  17. // 判断顺序表是否写满
  18. bool isFull(sequenceList *list);
  19. // 向顺序表插入数据
  20. bool insert(sequenceList *s, int data);
  21. // 非空校验
  22. bool isEmpty(sequenceList *list);
  23. // 遍历顺序表
  24. void show(sequenceList *list);
  25. // 删除顺序表数据
  26. bool removeNode(sequenceList *list, int data);
  27. // 释放内存
  28. void destroy(sequenceList *s);
  29. #endif
复制代码


  • seqlist.c
    1. #include "seqlist.h"
    2. sequenceList *init_list(int cap)
    3. {
    4.     sequenceList *list = malloc(sizeof(sequenceList));
    5.     if (list != NULL)
    6.     {
    7.         list->data = malloc(sizeof(int) * cap);
    8.         if (list->data == NULL)
    9.         {
    10.             free(list);
    11.             return NULL;
    12.         }
    13.         list->capacity = cap;
    14.         list->last = -1;
    15.     }
    16.     return list;
    17. }
    18. bool isFull(sequenceList *list)
    19. {
    20.     return list->last == list->capacity - 1;
    21. }
    22. // 在顺序表表头插入一个新数据
    23. bool insert(sequenceList *s, int data)
    24. {
    25.     if (isFull(s))
    26.         return false;
    27.      // 将原有数据全部往后挪一位
    28.     for (int i = s->last; i >= 0; i--)
    29.         s->data[i + 1] = s->data[i];
    30.     // 将新数据置入表头
    31.     s->data[0] = data;
    32.     s->last++;
    33.     return true;
    34. }
    35. // 判断是否为空
    36. bool isEmpty(sequenceList *list)
    37. {
    38.     return list->last == -1;
    39. }
    40. // 查看当前顺序表的元素
    41. void show(sequenceList *list)
    42. {
    43.     if (isEmpty(list))
    44.     {
    45.         return;
    46.     }
    47.     for (int i = 0; i <= list->last; i++)
    48.         printf("%d\t", list->data[i]);
    49.     printf("\n");
    50. }
    51. // 将顺序表中指定的某个元素删除掉
    52. bool removeNode(sequenceList *list, int data)
    53. {
    54.     if (isEmpty(list))
    55.         return false;
    56.     // 找到要删除的节点的位置
    57.     int i, pos = -1;
    58.     for (i = 0; i <= list->last; i++)
    59.     {
    60.         if (list->data[i] == data)
    61.         {
    62.             pos = i;
    63.             break;
    64.         }
    65.     }
    66.     // 找不到要删除的元素
    67.     if (i > list->last)
    68.     {
    69.                return false;
    70.     }
    71.     // 将所有数据全部往前挪一位
    72.     for (int i = pos; i < list->last; i++)
    73.         list->data[i] = list->data[i + 1];
    74.     list->last--;
    75.     return true;
    76. }
    77. // 释放内存
    78. void destroy(sequenceList *s)
    79. {
    80.     if(s == NULL)
    81.         return;
    82.     free(s->data);
    83.     free(s);
    84. }
    85. int main()
    86. {
    87.     // 创建顺序表
    88.     sequenceList *list = init_list(10);
    89.     if (list == NULL)
    90.     {
    91.         perror("初始化顺序表失败!");
    92.         exit(0);
    93.     }
    94.     else
    95.     {
    96.         printf("初始化顺序表成功!\n");
    97.     }
    98.     // 测试向顺序表插入/删除信息
    99.     int n;
    100.     while (true)
    101.     {
    102.         scanf("%d", &n);
    103.         if (n > 0)
    104.         {
    105.             // 插入
    106.             if (!insert(list, n))
    107.             {
    108.                 printf("容量已满,插入失败!\n");
    109.                 continue;
    110.             }
    111.              }
    112. else if(n < 0)
    113. {
    114. // 删除
    115. if(!removeNode(list,-n))
    116. {
    117. printf("查无此数,删除失败!\n");
    118. continue;
    119. }
    120. }
    121. // 遍历
    122. show(list);
    123. }
    124. // 释放
    125. destroy(list);
    126. }
    复制代码
训练 1

创建一个顺序表,并从键盘吸收数字输入,将输入的正整数按从小到大的顺序插入顺序表,并在输 入负整数的时间将其绝对值数据删除。每次输入后,将顺序表的内容打印到屏幕上。
剖析 : 此题考查顺序表的基本思绪,先要筹划好顺序表的逻辑表达,再通过对顺序表的插入和删除操作, 体会顺序存储中对于插入和删除的未便性。
参考代码 :
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3. #include <stdlib.h>
  4. typedef struct
  5. {
  6.        int total_size; // 顺序表总容量
  7.     int last;       // 顺序表最末元素的下标
  8.     int *data;      // 顺序表的存储空间
  9. }sqlist;
  10. // 初始化一个空的顺序表
  11. sqlist * init_list(int total_size)
  12. {
  13.     sqlist *sq = (sqlist *)malloc(sizeof(sqlist));
  14.     if(sq != NULL)
  15.     {
  16.         sq->total_size = total_size;
  17.         sq->last       = -1; // 用-1表征当前没有元素
  18.         sq->data = (int *)malloc(sizeof(int) * total_size);
  19.         if(sq->data == NULL)
  20.         {
  21.             free(sq);
  22.         }
  23.     }
  24.     return sq;
  25. }
  26. // 在递增的顺序表中找到x应插入的合适位置
  27. int get_pos(sqlist *sq, int x)
  28. {
  29.     int pos = 0;
  30.     while((pos<=sq->last) && (sq->data[pos]<x))
  31.         pos++;
  32.     // 当链表为空(即sq->last为-1时),返回0
  33.     return pos;
  34. }
  35. // 判断顺序表是否已满
  36. bool is_full(sqlist *sq)
  37. {
  38.     return sq->last >= sq->total_size-1;
  39. }
  40. // 将元素x插入顺序表sq中
  41. bool insert(sqlist *sq, int x)
  42. {
  43.     if(is_full(sq))
  44.         return false;
  45.     // 在顺序表中得到即将要插入的元素x的合适的位置
  46.     int pos = get_pos(sq, x);
  47.     // 将顺序表中pos往后的所有元素往后挪一位
  48.         for(int i=sq->last; i>=pos; i--)
  49.         sq->data[i+1] = sq->data[i];
  50.     sq->data[pos] = x;
  51.     sq->last++;
  52.     return true;
  53. }
  54. // 在顺序表sq中,定位元素x
  55. int locate(sqlist *sq, int x)
  56. {
  57.     int pos;
  58.     for(pos=0; pos<=sq->last; pos++)
  59.     {
  60.         if(sq->data[pos] == x)
  61.         {
  62.             printf("data[%d]=%d\n", pos, x);
  63.             return pos;
  64.         }
  65.     }
  66.     return -1;
  67. }
  68. // 从顺序表中将元素x剔除
  69. bool delete(sqlist *sq, int x)
  70. {
  71.     int pos;
  72.     pos = locate(sq, x);
  73.     // 元素x不存在
  74.     if(pos == -1)
  75.         return false;
  76.     // 将pos后续的元素全部往前挪一位
  77.     for(; pos<=sq->last; pos++)
  78.             sq->data[pos] = sq->data[pos+1];
  79.     sq->last--;
  80.     return true;
  81. }
  82. // 展示顺序表元素
  83. void show_data(sqlist *sq)
  84. {
  85.     for(int i=0; i<=sq->last; i++)
  86.         printf("\tsq->data[%d]=%d\n", i, sq->data[i]);
  87.     printf("=======================\n");
  88. }
  89. int main(int argc, char *argv[])
  90. {
  91.     // 初始化一条空的顺序表
  92.     sqlist *sq = init_list(10);
  93.     // 插入元素
  94.     int num;
  95.     while(1)
  96.     {
  97.         scanf("%d", &num);
  98.         if(num > 0)
  99.         {
  100.             if(insert(sq, num))
  101.                 show_data(sq);
  102.             else
  103.                 fprintf(stderr, "顺序表已满\n");
  104.         }
  105.         else if(num < 0)
  106.         {
  107.             if(delete(sq, -num))
  108.                 show_data(sq);
  109.             else
  110.                 fprintf(stderr, "元素不存在\n");
  111.         }
  112.         else
  113.         {
  114.             fprintf(stderr, "BYE\n");
  115.             break;
  116.         }
  117.     }
  118.     return 0;
  119. }
复制代码
顺序表优缺点总结

顺序存储中,由于逻辑关系是用物理位置来表达的,因此从上述示例代码可以很清楚看到,增删数 据都非常困难,需要成片地移动数据。顺序表对数据节点的增删操作是很不友好的。 总结其特点如下:


  • 优点

  • 不需要多余的信息来记录数据间的关系,存储密度高
  • 全部数据顺序存储在一片连续的内存中,支持立即访问恣意一个随机数据,比如上述顺序表中 第个节点是 s->data


  • 缺点

  • 插入、删除时需要保持数据的物理位置反映其逻辑关系,一样平常需要成片移动数据
  • 当数据节点数目较多时,需要一整片较大的连续内存空间
  • 当数据节点数目变化剧烈时,内存的开释和分配不机动

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

去皮卡多

金牌会员
这个人很懒什么都没写!

标签云

快速回复 返回顶部 返回列表