第2章 数据的存储方式 课件 2023-2024学年粤教版（2019）高中信息技术选修1

2.1数据存储的顺序结构与链式结构2.1.1数据存储的顺序结构数据元素之间有一种常见的逻辑结构——线性结构，其数据元素中除第一个和最后一个数据元素之外，其他数据元素都是首尾相接的。就如生活中的一个队伍一样，队伍中的每个人可以看作一个数据元素，除了第一个人和最后一个人之外，其他人都是跟在某一个人之后，且其后面又跟着另外一个人。如某数据结构中，数据元素的集合K和K上二元关系的集合R如下：K＝{a1，a2，…，ai-1，ai，…，an-1，an}R={<a1，a2>，<a2，a3>，…，<ai-1，ai>，…，<an-1，an>}其中，i为整数且1＜i≤n。我们说ai-1是ai的前驱，ai是ai-1的后继。这种数据元素之间的线性关系指的是逻辑结构上的，而在物理存储上则不一定。2.2数据的顺序存储与组织数据在计算机中能够以顺序结构进行存储。用计算机程序来实现对数据元素的顺序存储与组织，可以使用数组这种数据结构。1．一维数组在计算机程序设计中，可以通过数组（Array）这种数据结构来实现对具有相同数据类型且按一定逻辑顺序排列的数据元素的存储与组织，定义了一个数组就是定义了一块可使用的连续存储空间，数组的基本类型就是数据元素的类型，数组的长度就是数组元素的最大个数。在C++语言中，数组的一般定义方式为：类型说明符数组名[数组长度];其中，“类型说明符”是任一种数据类型，“数组名”是用户定义的数组标识符，“数组长度”必须为常量表达式。例如：inta[6];一维数组inta[6]a[0]a[1]a[2]a[3]a[4]a[5]123456定义数组为整型，数组名为a，数组长度为6的一个数组。a=[1,2,3,4,5,6]2．二维数组数组的下标可以是一个，也可以是多个。当数组有两个下标时，就称为二维数组。二维数组可以看成一维数组的嵌套，即首先把它看作一个一维数组，这个数组的每个元素又是一个一维数组。如一个二维数组b，可看成为某个一维数组共有n个元素，分别是b[0]，b[1]，…，b[n-1]，其中每个元素b[i]（0≤i＜n）又是一个有m个元素的一维数组，分别是b[i][0]，b[i][1]，…，b[i][m-1]。从逻辑结构上，我们也可以把这个二维数组看成一个n行m列的矩阵，并把第一个下标称为行下标，第二个下标称为列下标。intb[4][3];intb[4]虽然二维数组在逻辑结构上具有行与列两个方向，但它作为一种顺序结构，所有元素在计算机内存空间中的物理存储地址仍是连续的。如在n行m列的二维数组b中，每个数据元素占用d个字节，假设b的第一个数据元素的计算机存储地址为Loc(b[0][0])，那么b的存储结构如图2-5所示。2.2.2数组的基本操作对于一维数组，通常有遍历（用于数组元素的赋值或查找）、插入元素、删除元素这几种操作。通过对数组的操作，我们可以实现以数组为数据结构的数据的各种管理功能。2.1.2数据存储的链式结构数据的链式结构与顺序结构不同，它的特点是存储各个数据元素的计算机存储单元的地址不一定是连续的。因此，为了表示每个数据元素ai与其后继数据元素ai+1之间的逻辑关系，对于数据元素ai来说，除了存储其本身的信息，还需要存储其后继数据元素的存储位置信息。比如，人们到银行、医院办理业务时，一般都是在叫号系统取号之后就在大厅中静坐等候。此时的人们看似无序，但叫号系统为每个人分配的号码无形中把等候的人们串成了一条链子。当以链式结构存储数据时，一种最简单也最常用的方法是分别用两个域存储数据元素的两部分信息：数据域存储数据元素自身信息，指针域存储后继数据元素的存储位置。链式结构存储学生信息表

指针不指向任何一个存储单元，这种指针称为空指针，最后一位同学由于没有后记数据，所以指针域没有指向任何一个存储单元，用符号表示指针域为空指针赋值为null。2.3.1指针与指针变量采用链式结构存储数据的特点是：每个数据元素除了要存储数据本身的信息外，还需要存储一个指示其后继数据元素的信息（即后继数据元素的存储位置）。在C++语言中，通常使用指针（Pointer）来实现这种存储位置的指示。所谓指针，就是指某个内存单元的地址。在C++语言中，指针也是一种数据类型。与普通数据类型不同的是，定义指针变量（PointerVariable）没有专门的关键字，而是利用“*”（星号）来进行定义。C++语言中定义指针变量的一般形式为：类型说明符*变量名;//指针变量的定义形式：类型说明符*变量名；int*pi;//定义一个整型指针float*pf;//定义一个浮点型指针string*ps;//定义一个字符串指针structWareInfo*pware;//定义一个结构类型指针定义一个变量，其实就代表分配计算机内存中的一个存储单元用于存储数据，变量名通常就代表所存储的数据。但是，如果我们在变量名前面使用“&”运算符（取地址运算符），则表示获取变量对应存储空间的地址。例如：inta=42;int*pi=&a;在计算机程序中，我们通过链表（LinkedLists）这种数据结构来实现链式结构的数据存储与组织，链表由一系列结点组成，结点可以动态生成。每个结点包括两个部分：一个是存储数据的数据域，另一个是存储下一个结点物理地址的指针域。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表有多种不同的类型，如单向链表、单向循环链表、双向链表、双向循环链表等，本节我们学习的是单向链表。因为链表是由若干个结点链接而成的，每个结点都具有相同的结构，因此我们定义链表的结构时只需要定义链表结点的结构即可。以下是链表结点的类型定义：typedef类型声明类型别名;因为链表就像铁链一样，一环扣一环，只要记住第一环，那整个链表就被记住了。所以，只需要定义一个LinkList类型的变量L（即LinkNode的指针变量），就可以记录和使用整个链表，L就称为链表的头指针，其定义如下：Link