第11章数据结构

第11章数据结构

本章内容安排数组记录链表2数据结构的概念在程序设计中，我们可以使用变量来存储单个实体，变量的使用非常广泛，但变量不能解决复杂问题。数据结构是相关变量的集合，这些变量能够单独或作为整体被访问。数据结构代表了有特殊关系的数据的集合。3初步方案：定义100个变量，每个使用不同的名字。逐个变量读入数据，逐个变量进行处理。引入问题有100个分数，需要读入这些数，处理并打印，同时将这些数据保存在内存中？4独立变量的处理5数组的概念数组是固定大小，相同数据类型元素的顺序集合。每个元素在数组中有一个固定的位置。将100个数放入数组中，假设数组的名称为scores，可以称数组中第一个元素为scores[1]，第二个元素为scores[2]……索引表明元素在数组中的顺序号。现代语言（C、Java等）从0开始索引。6数组元素7循环的方式访问数组元素8独立变量和数组实现的比较编写语句数量比较独立变量：100条语句读，100语句写，100条语句处理，共需要编写300条语句数组配合循环：每个循环体2条语句，加上初始化索引，总共需要编写12条语句执行的机器周期数使用数组和循环，所需要执行的机器周期数没有减少，反而有所增加，需要初始化、递增循环变量和测试循环条件等负担更应该关心所编写的程序行数。91、数组名与元素名数组名是整个结构的名字，代表整个结构；元素名是对某个特定元素的标识。如数组的名称为scores，元素名为数组名加索引，如scores[1]。102、二维数组在程序中二维数组的需求也非常多，如表格包括行和列，需要二维数组表示。二维数组需要两个索引下标，前面的下标表示元素所在行，后面的下标表示元素所在的列。假设二维数组名为scores，有5行4列，则a[1][2]表示第1行第2列的元素；a[2][3]表示第2行第3列的元素。11二维数组123、存储配置一维数组以线性方式进行存储，数组中第一个元素存储在内存的低地址处，后面的元素依次连续存储。二维数组采用多数情况下采用行主序存储，“逐行”存储，先存储第一行元素(第一行的首个元素在低地址处，后面的元素依次存储)，存完第一行之后，接着存储第二行元素……13行主序存储和列主序存储14例题Students是一个100×4的二维数组（100行和4列），假定元素students[1][1]存储地址为1000，每个元素占用1个存储地址，求元素students[5][3]的地址，假定使用行主序存储，索引下标从1开始解答

y=1000+4*(5-1)+(3-1)=1018154、数组操作查找元素：查找匹配元素值的对应元素的序号。对未排序的数组采用顺序查找，对有序的数组采用折半查找。元素的插入尾部插入：新数据直接插入原数组的尾部开始或中间插入：需要将插入位置之后的所有元素向后移动，最后插入指定元素。16数组操作元素的删除：删除某个元素后，后续的元素需要向前移动。检索元素：随机存取一个元素，直接通过下标索引的方式进行访问，如scores[9]数组的遍历：应用与数组中每个元素的操作。17求数组元素的平均值185、数组应用数组适合于插入和删除操作较少，而需要大量的查找和检索操作的场合。在需要大量插入和删除操作情况下，不适宜使用数组。19本章内容安排数组记录链表20记录记录(结构体)是一组相关元素的集合，它们可能是不同的类型，整个记录有一个名称。记录中的每个元素称为域。域是具有含义的命名数据的最小元素。数组中所有元素必须是同一种类型，记录中的元素可以是相同或不同类型。211、记录的示例22记录记录中多个元素可以是相同或不同类型，但记录中的所有元素必须是相关的。记录中的数据往往和一个对象关联，如第二个例子中的数据都与一个学生关联；不要将不相关的数据组合到一起。注意:23记录名与域名记录的名称是整个结构的名字，域的名字允许我们存取特定的域。右图中，记录的名字为student，域名字分别为：

student.id student.grade242、记录与数组数组定义了相同类型元素的集合，常用于描述多个同类对象的信息，如定义一个班级的学生成绩（40个同学）。记录常用于定义同一个对象的属性集合，如描述某个学生的学号、姓名、成绩等，域的数据类型往往不同。253、记录数组一种特殊的数组，本身是数组，包含多个元素。数组中的每个元素是一个记录。记录数组往往用于定义多个对象的属性信息。如班级中有30名同学，可以定义一个记录的数组，每个记录描述一位学生的信息。26记录数组访问第2个学生的姓名：(student[2]).name27示例：访问记录数组中的每个记录域28示例：循环访问记录数组29本章内容安排数组记录链表30链表链表也是一个有序数据的集合，但每个元素包含下一个元素的地址。每个元素包含两部分：数据和链(链是存储下一个元素地址的指针)。此处只讨论单链表，每个节点仅有一个指向后继节点的链。通常使用一个指针变量指向第一个元素，称为链表的头指针。链表的最后一个元素包含一个空指针，标识链表的结束。31链表示意32节点链表中的元素习惯上被称为节点，节点是至少包含两个域的记录。一个域用于保存数据部分，另一个域包含指向下一个节点的地址。33数组与列表数组元素在内存中连续存储，通过索引下标可对某个元素直接存取。链表中的节点在内存中是分散存储的，通过节点中的指针域链在一起。在链表中插入、删除节点方便高效，但需要额外的域存储地址；此外链表查询需要遍历链表。34数组与链表35链表名与节点名链表通常有一个头指针，指向第一个元素，头指针标识整个链表，做为链表的名字。节点在链表中没有明显的名字，存在隐含的名字。以C语言为例，某个节点的名字通过指向它的指针间接获得。如p指向某个节点，则节点名字为(*p)。36节点名字37链表的操作对链表的操作很多，在此我们只给出几种基本操作：搜索链表插入节点删除节点检索链表遍历链表381、搜索链表链表的搜索只能是顺序搜索，链表中节点没有特定的名字。搜索链表时，通过一个标识变量表示是否搜索到目标。当搜索到时，将该标识变量置为true，同时用指针变量指向含有目标值的节点。39链表搜索示意图4041链表搜索算法422、插入节点链表通常按照关键字有序排列，不允许插入重复值。插入新节点前，先搜索链表，只有当插入的目标值不存在时才允许执行插入操作要考虑几种不同的情况向空表插入节点向表的开始处插入节点向表尾插入节点在表中插入节点43表头插入节点44表尾插入节点45表中插入节点46插入节点的算法473、删除节点删除节点之前，先搜索链表，只有当搜索的目标存在时才能删除。删除节点要考虑两种情况删除首节点删除其他节点（中间或尾节点）48删除首节点49删除中间或尾节点50删除节点的算法514、检索链表检索是为了检查或复制节点中所含数据，而随机访问节点，检索之前，首先需要通过搜索链表定位目标节点。找到目标节点后，通常会返回目标节点的数据。52检索链表的算法535、遍历链表从第一个节点开始，依次检查并处理每个节点直到最后一个节点。遍历在各种算法中被广泛使用，如修改节点的值、打印列表、计算某个域的和、计算平均值等。遍历链表需要一个步进指针，配合循环结构，指针从一个节点移动到另一个节点，直到处理完最后一个节