数据的存储方式
一、数据存储的顺序结构与链式结构
1.数据存储的顺序结构
线性结构：K＝｛a_1， a_2，…，a_（i-1），a_i，…a_（n-1），a_n｝
在以上数据结构中，第一个元素仅有一个后继元素，最后一个元素仅有一个前驱元素，其他元素仅有一个前驱和一个后继元素。a_（i-1）是a_i的前驱，a_i是a_（i-1）的后继。存储空间为sizeof（a_1）*d字节。
2.数据存储的链式结构
一个数据元素有两个域：数据域和指针域。数据域存储数据，指针域存放后继元素的存储位置，最后一个数据元素的指针域为空。由于每个数据元素的存储位置是保存在它的前驱元素的指针域中，只有当访问到其前驱元素后才能沿着前驱元素的指针域访问到该数据元素。
二、数据的顺序存储与组织
1.数组
由具有相同名称、相同类数据类型、所占空间连续的数据元素构成的序列，称为数组。
定义数组的基本格式：类型说明符 数组名［数组长度］；
类型说明符可以是任意合法的数据类型；数组名是由字母、数字和下画线组成，开头只能是字母或下画线；数组长度必须是常量或常数。
数组元素的引用是通过下标来确定的，下标是从0到数组长度-1。数组名是一个特别的量，它的值是数组的第一个元素的地址，即指向第一个元素。例如，下面是一个长度为4的一维数组： int a［4］。
由此可以看出，a指向第一个元素，a+1指向第二个元素，a+2指向第三个元素，a+3指向第四个元素，a+4指向一个不确定的元素的地址（发生溢出）。a［0］至a［3］分别是对应内存的名称，它相应于一个单变量，代表对应内存空间存储的值。
在Python的基本数据类型中，没有哪一种类型与这种标准数组对应，这是因为Python是一种动态语言，不需要事先声明一个量就可以直接使用这个量，而且在Python的基本数据类型中，列表、元组、集合、字典等中每一个元素的类型都不相同。数组有点像一个特殊的列表，因此，在Python中，常用列表来替代数组，只是在使用时要注意遵循数组运算规则即可。
多维数组：可以把每一行看作一组数组来处理的数组。下面以二维数组为例。
基本格式：类型说明符 数组名［常量表达式1］［常量表达式2］；
例如，int a［3］［4］；
其实质：
a→a［0］ →a［0］［0］ a［0］［1］ a［0］［2］ a［0］［3］
a［1］ →a［1］［0］ a［1］［1］ a［1］［2］ a［1］［3］
a［2］ →a［2］［0］ a［2］［1］ a［2］［2］ a［0］［3］
由上可以看出，数组名a是整个数组的起始地址，指向第一行元素地址，即量a与a［0］是指向整个数组的第一个元素a［0］［0］的地址，a+1与a［1］是指向第二行元素的第一个元素a［1］［0］的地址，a+2与a［2］是指向第三行的第一个元素a［2］［0］的地址。在Python中，可以用列表来临时表示二维数组，如要表示一个3行4列的数组，用列表可表示为：L＝［［，，，］，［，，，］，［，，，］］（在给列表L的元素赋值时一定遵循数组的规则）。
2.数组基本操作（以Python为例）
遍历：将列表L中的所有元素输出。
for i in L：
print（i）
查找：在列表L中查找x，若有输出True，否则输出False。
if x in L：
print（“True”）
else：
print（“False”）
插入：将x插入到列表L的第i个位置。
L.insert（i，x）
删除：删除位置i上的元素。
del L［i］
提示：在其他语言中，对数组的遍历、查找、插入、删除等操作要使用循环结构。
三、数据的链式存储与组织（以Python语言为例）
1.指针
指针就是某个内存单元的地址。
2.链表
简单链表的节点有两个域，一个是指针域，用于保存下一个节点的地址，另一个是数据域，用于保存需要存储的数据，由此构成一个数据序列。
由于在Python语言中没有指针类型，且变量的类型由其值来决定，因此，在Python中使用类来替代其他语言中的结构体。下面是用Python语言定义的节点。
class Node（object）：
def __init__ （self，data，next = None）：
self.data = data
self.next = next
在上面节点中，data是保存当前节点数据的量，next是指向下一个节点的地址，如果没有下一个节点，则其值为None。
3.链表操作
（1）链表的初始化
def Create_List（lt）： #lt为要建立的链表的各节点的数据
head = Node（lt［0］）
p = head
for i in lt［1：］：
new_node = Node（i）
p.next = new_node
p=new_node
return head
（2）链表元素的遍历
def print_List（link）： #link为指向链表的头节点的指针
while link：
print（link.data，end=
）
link = link.next
（3）链表节点元素的插入
下面是链表插入操作的示意图和Python语言程序。
def Insert_Link（head，index，item）：
p=head
if index==None：#如果要把节点插入在第一个位置
q=Node（item）
q.next=self.head
self.head=q
else：
post=head
j=0
while p.next！= None and j < index： #查找插入的位置
post=p
p=p.next
j=j+1
if index==j：
q=Node（item，p）
post.next=q
q.next=p
（4）链表的节点删除操作
下面是链表删除操作的示意图和Python语言程序。
def Delete_Link（head，index）：
p=head
if index == None：
q=head
head=q.next
p=head
else：
post=head
j=0
while p.next！= None and j < index：
post=p
p=p.next
j=j+1
if index==j：
post.next = p.next
（5）获取链表的节点数
def get_length（head）：
p=head
length = 0
while p！= None：
length=length + 1
p=p.next
return length
（6）获取链表中子节点的值
def GetElement（head，i）：
L=get_length（head）
if i>=L：
print（"元素位置范围为：0-%d"%（L-1））
return
p=head
n=0
while True：
if i==n：
return p.data
p=p.next
n=n+1
return
四、数组与链表及其应用
在逻辑上都是属于线性关系，区别是数组是连续的存储，而链表并非连续存储，数组的长度是固定的，链表是动态申请内存。
对于确定长度的、需要连续使用内存单元，并且不需要频繁进行增加、删除操作的就用数组，反之使用链表。
随堂练习
一、单项选择题
1.线性结构的数据在存储时，数据元素之间的位置是（ ）。
A.随机的 B.相邻的 C.不确定的 D.以上都可能
2.链式存储结构所占存储空间（ ）。
A.分两部分：一部分存放节点的值，另一个部分存放下一节点的地址
B.只有一部分，存放节点的值
C.只有一部分，存储表示节点间关系的指针
D.分两部分：一部分存放节点的值，另一部分存放节点所占单个元素
3.当以链式结构存储数据时，数据元素至少包含（ ）部分信息。
A.1 B.2 C.3 D.4
4.在Python语言中，定义一个链表的节点使用的关键字是（ ）。
A.def B.import C.class D.from
5.在数据的链式存储结构中，数据元素αi的存储位置保存在（ ）。
A.αi的指针域中 B.αi+1的指针域中 C.αi-1的指针域中 D.无法确定
6.指针即内存单元地址，在C++语言中指针也是一种数据类型，但其没有专门的关键字来定义，而是在其数据类型符后用（ ）来表示后面的变量是一个指针。
A.// B.& C.# D.*
7.要在单向链表中将数据e放入到链L的i-1处与i处之间，首先应该（ ）
A.将i-１处的指针指向数据e
B.将数据e放入i处的节点的值域中
C.将i-1和i处的指针同时指向数据e
D.生成新节点，并把数据e放入到其值域中
8.执行int a=3；int *pi；pi=&a；*pi+=1；后，a的值为（ ）。
A.2 B.3 C.4 D.5
9.有一组数：1，1，2，3，5，8，…，55，保存在数组a中。这组数有这样一个特点：a［i+2］=a［i+1］+a［i］，则a［7］等于（ ）。
A.11 B.13 C.21 D.33
10.在长度为n的数组中插入数据，最多和最少移动数据的次数分别是（ ）。
A.n和0 B.n和1 C.n-1和0 D.n-1和1
11.在数组的第i个位置（0<i<n-1，数组最大长度n）插入一个元素e，首先要（ ）。
A.将位置为i的元素向后移一个位置 B.将位置为n的元素向后移一个位置
C.将位置为n-1的元素向后移一个位置 D.将新数据e保存到数组的第i个位置
12.结构体是一种复合型的数据类型，即由多个简单数据类型的量通过特定结构组合成一个复合体，这个复合体可作为简单类型的方式来使用，如果要引用其成员变量则结构体与成员之间通常用（ ）符号来连接。
A.. B.， C.； D.！
13.设指针变量P指向单链表中节点A，若删除单链表中节点A，则需要修改指针的操作序列为（ ）。
q=p->next；
p->data=q->data；
p->next=q->next；
delete q；
A.
q=p->next；
q->data=p->data；
p->next=q->next；
delete q；
B.
q=p->next；
p->next=q->next；
delete q；
C.
q=p->next；
p->data=q->data；
delete q；
D.
14.以下的程序片段是实现从具有n个元素的数组a中删除第t个元素的功能，横线处缺少的代码应该是（ ）。
for （i=t； i<n； i++）
｛
｝
A.a［t］=a［i］； B.a［i］=a［i+1］； C.a［i］=a［i-1］； D.a［i-1］=a［i］；
15.下列关于数组的说法，不正确的是（ ）。
A.所有元素的数据类型都相同
B.占用连续的内存空间
C.可以根据下标确定数组中的元素，下标从1开始
D.元素的类型可以是简单数据类型，也可以是结构类型
16.单向链表与数组都属于线性表，它们都是用于存储具有相同属性的数据，下列说法不正确的是（ ）。
A.数组适合用于最大元素个数容易确定的情况
B.存储相同的元素，单向链表比数组占用的存储空间要多
C.查找特定元素，使用单向链表比使用数组方便
D.对于需要频繁添加、删除元素的情况，使用单向链表比使用数组合适
二、判断题
17.顺序结构存储方式的优点是查找方便，插入、删除效率高。（ ）
18.在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（ ）
19.链表的每个节点都包含一个指针域。（ ）
20.数组会造成存储空间的浪费，而链表不会，所以链表的空间利用率比数组高。（ ）
21.需要频繁插入、删除数据时，应选择顺序存储结构。（ ）
22.定义一个二维数组float a［3］［4］；表示这是一个3行4列的矩阵，共有12个元素，其中最后一个元素为a［3］［4］。（ ）
23.链表、队列、字符串的数据模型都是线性表。（ ）
24.链表中各元素之间只能有一个“链”相连。（ ）
三、填空题
25.定义一个数组int a［n］；要访问该数组中第i个元素（0≤i≤n-1），则查找下标为 的元素。
26.定义一个二维数组，int a=［［1，2，3］，［4，5，6］，［7，8，9］，［10，11，12］］；那么a［2］［2］的值是 。
27. 是用来实现链式结构的数据存储与组织，它是由节点组成的。
28.为了链表操作的方便，一般会在链表的第一个节点前面增加一个节点，这个节点的data域不保存数据，将这个特殊的节点称为 。
29.在链表中，节点之间是通过节点中的 联系到一起的，将多块不连续的内存空间连接，在逻辑上形成一片连续的数据存储空间。
四、应用题
30.下图是使用单链表来存储数据元素a1、a2、a3、a4、a5，其中next指向下一节点的地址。请根据要求回答问题。
（1）在该链表中，L指向的下一个节点称为 。
（2）在最后一个节点中的指针域，符号“∧”表示指针域为 。
（3）在单链表中查询数据a3，要在数据元素 的指针域中查找其存储地址。
（4）若要在该单链表中数据元素a2、a3之间插入一个新的数据元素x，相关步骤如下：
①使用关键词 创建一个新的节点p，用来存放数据x。
②将数据x存入节点p的数据域。
③将节点p的指针域指向数据元素 所在的节点。
④将a2节点的next指向节点p。