页数：45页文件大小：608.9 KB来源： 数据结构-C#语言描述ppt课件
本课件系统讲解线性表这一最基础的线性结构：先给出线性表的定义，再讲顺序存储结构下数组与动态数组的特点、地址计算公式与类型安全问题，随后展开链式存储结构，逐一图解单向链表的添加插入删除、循环链表在约瑟夫问题中的应用，以及双向链表中结点的指针修改顺序，最后对比顺序表与链表的性能优劣。
本页为第二章线性表封面。本章先讲线性表的定义，再分别展开顺序存储结构（顺序表）与链式存储结构（链表）两类实现。
线性表（Linear List）是具有相同特性的数据元素的一个有限序列，记为 a1、a2、…、an-1、an。序列中元素的个数即线性表的长度，元素之间存在严格的一对一先后关系。
线性表的顺序存储结构是指用一块地址连续的存储空间依次存储线性表的数据元素。这种实现称为顺序表，它在 C# 中最直接的表现形式就是数组。
顺序表的第一个特点是容量固定：空间必须一次性申请，占用的是一整块连续区域。
课件以宿舍安排为例：A 班 40 人住入 101～104 等连续宿舍，B 班 50 人住入 105～109 等连续宿舍，各班学生必须住在连续的宿舍区间内，一旦申请完成，区间长度便无法随意改变。
由于线性表中每个元素所占用的空间是相同的，只需按照公式计算便可以快速地访问指定元素。假设顺序表中第一个元素的位置是 Loc，每个数据元素所占用的存储空间为 n：
| 元素 | 下标位置 | 存储地址 |
|---|---|---|
| a1 | 0 | Loc |
| a2 | 1 | Loc+n |
| ai | i-1 | Loc+(i-1)×n |
因此顺序表支持按索引随机访问，时间复杂度为 O(1)。
线性表的顺序存储结构在 C# 中的最直接表现形式就是数组。它存在于 System 命名空间之中，是一种内置数据类型，数组是最基础也是存取速度最快的一种集合类型。
当数组元素为值类型时，数组变量存放在栈上，元素本身存放在托管堆中的连续区域。
以 int[] arrInt = new int[5]; 为例，创建后 5 个元素全部初始化为 0；执行 arrInt[2] = 5; 与 arrInt[4] = 3; 后，这两个位置的值被就地改写，其余元素保持不变。
当数组元素为引用类型时，数组空间中存放的是引用而非对象本身。
以 Control[] arrCtrl = new Control[5]; 为例，创建后 5 个位置全部为 null；arrCtrl[0] = new Button(); 与 arrCtrl[3] = new Label(); 之后，这两个位置分别指向托管堆中的 Button 与 Label 对象。
如果一个班级的宿舍必须是连续的，A 班补录 10 人，该如何安排宿舍？
做法是先将 A 班所有学生搬入连续的空宿舍（201～205），再把补录的 10 个学生安排到 205 内，并把 206、207、208 三间宿舍作为 A 班的备用宿舍留空。
这正对应 ArrayList 的扩容策略：容量不足时申请一块更大的连续空间，把原有元素整体搬过去，并预留一部分冗余容量。
例 2-1 ArrayList.cs 代码讲解——添加操作：在空集合上执行 Add(50)，元素 50 被写入内部数组 _items 的索引 0 处，表示实际元素个数的 _size 由 0 变为 1。
例 2-1 添加操作：继续执行 Add(200)，元素 200 被写入内部数组 _items 的索引 1 处，_size 由 1 变为 2。
例 2-1 添加操作：继续执行 Add(6)，元素 6 被写入内部数组 _items 的索引 2 处，_size 由 2 变为 3。
例 2-1 插入操作：执行 Insert(0,12) 后，12 被放入索引 0 的位置，原有的 50、200、6 依次向后移动一个位置，_size 加 1。这说明顺序表在表头插入需要移动全部后续元素。
例 2-1 插入操作：执行 Insert(2,73) 后，73 落在索引 2 的位置，该位置及其后的元素整体后移一位，_size 加 1。
例 2-1 删除操作：执行 RemoveAt(0) 删除索引 0 处的元素后，其后的所有元素依次向前移动一个位置，_size 减 1。
例 2-1 删除操作：执行 RemoveAt(2) 删除索引 2 处的元素后，位于其后的元素依次前移填补空位，_size 减 1。页面同时给出运行虚拟线性表演示程序的入口。
数组和 ArrayList 的本质区别在于前者是类型安全的，而后者不是类型安全的。ArrayList 为了兼容所有类型的对象，使用了 object 数组，这给使用带来了一些麻烦。
.NET 2.0 版本的泛型的出现完美地解决了集合类的安全问题，新版本使用 System.Collections.Generic 命名空间下的 List<T> 类取代了原来的 ArrayList 类。
在实际编程中，应使用 List<T> 代替 ArrayList。
线性表的另一种常见存在形式——链式存储结构，又称链表（Linked List）。顺序表必须占用一整块事先分配的存储空间，而链表则不需要。链表在逻辑上相邻的元素在物理位置上可以不相邻。
在链式存储中，每个存储点不仅包含所存元素本身的信息，而且包含元素之间逻辑关系的信息。链表又分为单链表和双链表。
单向链表的元素间的表面物理关系如同一盘散沙。如果每个元素只包含元素的有用数据内容，则这些元素之间将毫无任何内在逻辑关系。
单向链表的结点由数据域和指针域组成，头指针 head 指向开始结点，终端结点的指针域为空，表示链表的结束。
例 2-3 LinkedList.cs 代码讲解——添加操作：在空链表上执行 Add(6)，新建结点 6 并让 head 指向它，该结点的索引号为 0。
例 2-3 添加操作：继续执行 Add(12)，新结点 12 被挂到尾结点 6 之后，链表中元素索引号依次为 0、1。
例 2-3 添加操作：继续执行 Add(7)，新结点 7 追加到链表尾部，链表中元素索引号依次为 0、1、2。
例 2-3 插入操作：执行 Insert(1,32)，新结点 32 被插入到索引 1 的位置。与顺序表不同，链表插入只需修改相关结点的指针地址，不需要移动已有元素。
例 2-3 插入操作：执行 Insert(0,19) 在表头插入，新结点 19 的指针域指向原来的开始结点，并更新 head 指向 19。
例 2-3 删除操作：执行 RemoveAt(2) 删除索引 2 处的结点，只需把其前驱结点的指针域改指向它的后继结点，并把被删结点释放即可。页面同时给出运行虚拟线性表演示程序的入口。
循环链表是另一种形式的链式存储结构。循环链表的最后一个结点的指针指向第一个结点，从而使整个链表成为一个环，这种形式的链表就叫做单向循环链表。
单向循环链表有两种表示形式：
加斯帕·蒙日（1746～1818 年）是法国数学家，画法几何的创始人。他在《数学的游戏问题》中讲了一个故事：15 个教徒和 15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30 个人围成一圆圈，从第一个人开始依次报数，每数到第九个人（用数字 M 表示）就将他扔入大海，如此循环进行直到仅余 15 个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
为解决约瑟夫问题而设计的单向循环链表应实现如下功能：
例 2-4 CircularLinkedList.cs 代码讲解——添加操作：向空循环链表执行 Add(1)，新建结点后 tail 指向该结点，游标 current 指向当前选中元素，prev 指向其前驱。
例 2-4 添加操作：继续执行 Add(2)，新结点挂入环中，各结点指针首尾相接形成封闭的环，游标 current 与前驱指针 prev 同步更新。
例 2-4 添加操作：继续执行 Add(3)，环中共有三个元素，游标 current 指向当前选中元素，前驱指针 prev 指向它的前一个结点。
例 2-4 元素的删除：调用 RemoveCurrentMode() 删除游标 current 所指的元素后，前驱结点的指针改指向被删结点的后继，整个链表仍然保持首尾相接的环状结构。
例 2-4 游标的移动：调用 Move(2) 后，游标 current 沿环向前移动两个位置，前驱指针 prev 同步跟进，移动过程中若越过尾结点则自动绕回环的首部。
例 2-4 游标的移动：调用 Move(3) 后，游标 current 继续沿环前进三个位置。由于是循环链表，游标到达尾结点后会绕回第一个结点继续计数，这正是求解约瑟夫问题所需要的循环访问能力。
带密码的约瑟夫问题：编号为 1，2，……，n 的 n 个人按照顺时针方向围坐一圈，每个人有且只有一个密码（正整数）。一开始任选一个正整数作为报数上限值，从第一个人开始顺时针方向自 1 开始报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向的下一个人开始重新报数，如此下去，直到所有人全部出队为止。
思考：设计一个程序来求出出队顺序，应如何修改单向循环链表以求解这个问题。
单链表的各结点只有指向其后继结点的指针域 next，只能顺着一个方向寻找。如果希望很方便地查找前驱，可以给每个结点再加一个指向前驱的指针域，使链表可以进行双方向查找。
用这种结点结构组成的链表称为双向链表，简称双链表。
双向链表的结点由三个部分组成：prev（指向前驱结点）、data（数据域）和 next（指向后继结点）。
头指针 head 指向开始结点，开始结点的 prev 为空，终端结点的 next 为空，链表由此支持从两个方向遍历。
在结点 n 之前插入结点 s 的代码如下，请注意代码执行顺序：
四条语句的先后顺序不能随意调换，否则会丢失原前驱结点的地址。
在结点 p 之后插入结点 s 的代码如下，请注意代码执行顺序：
同样必须按此顺序执行，才能在不断链的前提下完成插入。
删除双向链表中的结点 s 时，需要把 s 的前驱结点与后继结点直接勾连起来，再摘除结点 s。与前插、后插一样，删除操作同样只需修改若干指针，不必移动元素。
C# 中实现了双向链表的数据结构是泛型集合 System.Collections.Generic.LinkedList<T>。它是一个通用链表类，不支持随机访问（使用索引访问）。它实现了很多添加元素的方法：
本章所学线性表的分类如下：
顺序表性能小结。
链表性能小结。
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}