ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据布局(顺序表) [打印本页]

---

作者: 去皮卡多    时间: 前天 16:22
标题: 数据布局(顺序表)
数据布局概述

什么是数据布局

数据布局： 数据布局就是计算机存储，构造，管理数据的方式方法；
数据布局的类型

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

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

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

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

常见的数据布局

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

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

• . 算法对应的程序所耗时间少
  
• 算法对应的程序所耗存储空间少
  
• 算法布局性好、易读、易移植和调试
  

数据布局与算法的本质任务，是进步程序的时间空间效率，简单讲就是让程序的执行速度越快越 好，所需内存空间越少越好。固然在很多情况下，程序的时空特性是相互制约的，就像鱼和熊掌不 可兼得，但我们可以根据程序现实解决题目标侧重点，去均衡时间和空间的对性能的斲丧。
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. // 将顺序表表头的数据删除掉
  27. bool removeNode(sequenceList *s)
  28. {
  29. if(isEmpty(s))
  30. return false;
  31. // 将所有数据全部往前挪一位
  32. for(int i=0; i<s->last; i++)
  33. s->data[i] = s->data[i+1];
  35.      s->last--;
  36. return true;
  37. }

  复制代码
    
  
  
  
  • 销毁顺序表
    一个顺序表最后不再需要，应当要开释其所占用的内存空间，这被称为顺序表的销毁。
    下面是销毁操作的示例代码：
    
    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企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4