第03话:线性表的顺序存储结构

线性表的结构体设计
服务器君一共花费了115.145 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议
  • 昨天贴了张线性表的知识路线图,线性表的顺序存储结构是比较简单的,从这里开始吧。

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

  • 线性表的顺序存储结构,说白了,就是在内存中找了块地方,通过占位的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。

既然线性表的毎个数据元素的类型都相同,所以可以用C语言(其他语言也相同)的一维数组来实现顺序存储结构,即把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。

  • 记得大学时,我们同宿舍有一个同学,人特别老实、热心,我们时常会让他帮我 们去图书馆占座,他总是答应,你想想,我们一个宿舍连他共有九个人,这其实明摆 着是欺负人的事。他每次一吃完早饭就冲去图书馆,挑一个好地儿,把他书包里的 书,一本一本地按座位放好,若书包里的书不够,他会把他的饭盒、水杯、水笔都用 上,长长一排,九个座硬是被他占了。

那同学占座时,如果图书馆里空座很多,他当然不必一定要选择第一排第一个位子,而是可以选择风水不错、美女较多的地儿。找到后,放一个书包在第一个位置,就表示从这开始,这地方暂时归我了。为了建立一个线性表,要在内存中找一块地,于是这块地的第一个位置就非常关键,它是存储空间的起始位置。

接着,因为我们一共九个人,所以他需要占九个座。线性表中,我们估算这个线性表的最大存储容量,建立一个数组,数组的长度就是这个最大存储容量。

可现实中,我们宿舍总有那么几个不是很好学的人,为了游戏,为了恋爱,就不去图书馆自习了。假设我们九个人,去了六个,真正被使用的座位也就只是六个,另三个是空的。同样的,我们已经有了起始的位置,也有了最大的容量,于是我们可以在里面增加数据了。随着数据的插入,我们线性表的长度开始变大,不过线性表的当前长度不能超过存储容量,即数组的长度。想想也是,如果我们有十个人,只占了九个座,自然是坐不下的。

线性表的顺序存储的结构体定义为:

#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType;   /* ElemType类型根据实际情况而定,这里假设为int */

typedef struct
{
	ElemType data[MAXSIZE]; /* 数组,存储数据元素 */
	int length;             /* 线性表当前长度 */
}SqList;

描述顺序存储结构需要三个属性:

  • 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置。
  • 线性表的最大存储容量:数组长度MaxSize。
  • 线性表的当前长度:length。
  • 数组的长度是存放线性表的存储空间的长度,存储分配后这个量是一般是不变的。线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行, 这个量是变化的。在任意时刻,线性表的长度应该小于等于数组的长度。

延伸阅读

此文章所在专题列表如下:

  1. 第01话:线性表的概念与定义
  2. 第02话:线性表的抽象数据类型ADT定义
  3. 第03话:线性表的顺序存储结构
  4. 第04话:线性表的初始化
  5. 第05话:线性表的遍历、插入操作
  6. 第06话:判断线性表是否为空与置空操作
  7. 第07话:线性表的查找操作
  8. 第08话:线性表删除某个元素
  9. 线性表顺序存储的优缺点
  10. 线性表链式存储结构的由来与基本概念
  11. 单链表的头指针、头结点与首元结点
  12. 单链表的结构体定义与声明
  13. 单链表的初始化
  14. 单链表的插入与遍历操作
  15. 单链表的删除某个元素的操作
  16. 获取单链表中的指定位置的元素
  17. 查找某数在单链表中的位置
  18. 用头插法实现单链表整表创建
  19. 用尾插法实现单链表整表创建
  20. 将单链表重置为空表
  21. 单链表反转/逆序的两种方法
  22. 单链表反转/逆序的第三种方法
  23. 求单链表倒数第N个数
  24. 用标尺法快速找到单链表的中间结点
  25. 如何判断链表是否有环的存在
  26. 单链表建环,无环链表变有环
  27. 删除单链表中的重复元素

本文地址:http://www.nowamagic.net/librarys/veda/detail/2200,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2200

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《JavaScript高级程序设计(第2版)》 尼古拉斯·泽卡斯(Nicholas C.Zakas) (作者), 李松峰 (译者), 曹力 (译者)

《JavaScript高级程序设计(第2版)》在上一版基础上进行了大幅度更新和修订,融入了近几年来JavaScript应用发展的最新成果,几乎涵盖了所有需要理解的重要概念和最新的JavaScript应用成果。从颇具深度的JavaScript语言基础到作用域(链),从引用类型到面向对象编程,从极其灵活的匿名函数到闭包的内部机制,从浏览器对象模型(BOM)、文档对象模型(DOM)到基于事件的Web脚本设计,从XML(E4X)到Ajax及JSON,从高级前端开发技术到前沿的客户端存储,从最佳编程实践到即将成为现实的API,直至JavaScript未来的发展,全景式地展示了JavaScript高级程序设计的方方面面。

更多计算机宝库...