下载文档原格式
数据结构之线性结构和⾮线性结构线性结构：⼀、概念1. 线性结构作为最常⽤的数据结构，其特点是数据元素之间存在⼀对⼀的线性关系。
2. 线性结构拥有两种不同的存储结构，即顺序存储结构和链式存储结构。
顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的，链式存储的线性表称为链表，链表中的存储元素不⼀定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
3. 线性结构中存在两种操作受限的使⽤场景，即队列和栈。
栈的操作只能在线性表的⼀端进⾏，就是我们常说的先进后出（FILO），队列的插⼊操作在线性表的⼀端进⾏⽽其他操作在线性表的另⼀端进⾏，先进先出（FIFO），由于线性结构存在两种存储结构，因此队列和栈各存在两个实现⽅式。
⼆、部分实现1. 顺序表（顺序存储） 按照我们的习惯，存放东西时，⼀般是找⼀块空间，然后将需要存放的东西依次摆放，这就是顺序存储。
计算机中的顺序存储是指在内存中⽤⼀块地址连续的空间依次存放数据元素，⽤这种⽅式存储的线性表叫顺序表其特点是表中相邻的数据元素在内存中存储位置也相邻，如下图：1 // 倒置线性表2 public void Reverse()3 {4 T tmp = default(T);56 int len = GetLength() - 1;7 for (int i = 0; i <= len / 2; i++)8 {9 if (i.Equals(len - i))10 {11 break;12 }1314 tmp = data[i];15 data[i] = data[len - i];16 data[len - i] = tmp;17 }18 }2. 链表（链式存储） 假如我们现在要存放⼀些物品，但是没有⾜够⼤的空间将所有的物品⼀次性放下（电脑中使⽤链式存储不是因为内存不够先事先说明⼀下...，具体原因后续会说到），同时设定我们因为脑容量很⼩，为了节省空间，只能记住⼀件物品位置。
教学单元一：线性结构一、知识点总结知识点我的总结（可以对课堂相对应的知识点进行总结）（建议图文并茂，标识重难点）掌握程度自评（1-5分）5分表示掌握的非常最好线性表的顺序存储●线性表的顺序存储：线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
●通常用数组来描述数据结构中的顺序存储结构重点：线性表的顺序存储示意图难点：结构体定义●顺序存储的优点与缺点：线性表的顺序存储结构，在存、读数据时，不管哪个位置，时间复杂都是O(1)；而插入和删除时，时间复杂度都是O(n)优点：可以快速的存取任一位置的元素。
缺点：插入和删除元素时将移动大量元素。
5分线性表的链式存储●线性表的链式存储：线性表的链式存储：是用一组任意的存储单元存储线性表的数据元素，这组数据元素可以是连续的，也可以是不连续的。
●单链表与顺序表优缺点对比：(1)若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。
若需要频繁插入和删除时，宜采用单链表结构。
(2)当线性表中的元素个数变化较大或者根本不知道多大时，最好采用单链表结构，这样可以不用考虑存储空间大小问题。
而如果事先知道线性表的大致长度，例如一年2个月这种用顺序存储结构效率会高很多。
重点：线性表的链式存储示意图●结构体定义●链表的初始化1.首先为头节点开辟空间使用malloc(sizeof())结构;也可采用无头结点的链表2.采用头插法或者尾插法，此处示例尾插法难点：插入节点和删除节点插入：删除：5分●双向列表●循环链表顺序查找和折半查找●顺序查找的概念：顺序查找也称为线性查找，属于无序查找算法。
从数据结构线性表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
重点：顺序查找的示意图（请点击播放）●顺序查找时间复杂度：查找成功时的平均查找长度为：（假设每个数据元素的概率相等）ASL=(1/n)∗(1+2+3+…+n)=(n+1)/2ASL=(1/n)∗(1+2+3+…+n)=(n+1)/2 ；当查找不成功时，需要n+1次比较，时间复杂度为O(n)；所以，顺序查找的时间复杂度为O(n)●二分查找的概念：二分查找也称为是折半查找，属于有序查找算法。
名词解释线性结构线性结构是指一种平衡系统的结构，其特点是各组成要素和子系统之间保持严格的比例关系。
如果该点上具有行政权利的人数少于可容纳的最大人数，则称该结构为线性结构；而反之，则为非线性结构。
其实，很多事物都属于线性结构，它们通过简单的叠加便能产生复杂的功能。
比如说，运动中的个人，整个团队，乃至国家和地区，也可以看作是一个典型的线性结构。
这就是非线性科学最本质的概念，只不过在中国历史上被长期忽略罢了。
有一句谚语是这么说的：铁打的衙门流水的官。
意思是一个衙门前的官员是会换的，但只要有需要就一定会有新的官员来充实这个衙门的人员配置。
为什么呢？因为官员是需要的，而官员的提升更是需要更多的支持的，所以我们经常可以看到一些官员明明在位时很风光，但一旦退下来或是去世了就难免会落得穷困潦倒，甚至惨死街头。
所以每次改朝换代之后，总是会有无数的人削尖脑袋想方设法谋求官职，他们觉得自己随着官职的升高，就会拥有越来越大的权力，到那时候也就可以为所欲为了。
然而正是这种天真的想法才使得封建王朝走向覆灭。
我们又可以从另一个角度来思考这个问题：一些部门实际管理人员与其所应承担的法律责任之间存在矛盾，这就是我们所谓的官僚主义。
这样的情况下，官员们往往并不直接面对公众，只对上负责，久而久之，这种极端的官僚化必将导致整个政府机构的瘫痪。
与此同时，由于没有人民的监督，一些基层公务人员会利用手中的职权贪污受贿，最终祸害百姓。
线性结构相当于一种社会等级体系，掌握了更高权力的官员自然就处在更高的地位，而处在较低等级的官员虽然会羡慕那些位高权重的官员，但却并不敢有太大的想法，否则极有可能引来杀身之祸。
相反，那些地位较低的官员们则往往心怀鬼胎，既希望成为上级官员的手下，又觊觎着他们的职位。
这样一来，他们就有可能发生行贿受贿或滥用职权的现象，而这两者无论哪一条路都会给国家的财政带来巨大的损失。
中国的官僚政治常常通过“权力依附”形成强大的行政权，以便于皇权维护统治阶级的利益。
线性结构知识点总结一、线性结构的定义线性结构是数据元素之间存在一对一的线性关系。
数据元素是有序排列的，在数据元素之间存在唯一的前驱和后继关系。
线性结构是最基本、最常用的一种数据结构，具有清晰的先后次序关系。
二、线性结构的特点1. 有序性：线性结构中的元素是有序排列的，每个元素都有唯一的前驱和后继。
2. 直接关系：除了首尾两个元素外，任意两个相邻的元素都有直接关系。
三、线性结构的常见类型线性结构的常见类型包括线性表、栈、队列、串、数组、链表等。
下面分别介绍这些线性结构的特点和实现方式。
1. 线性表线性表是线性结构的一种基本形式，它是具有相同特性的数据元素的有限序列。
线性表的特点是元素之间有直接关系，元素的个数是有限的。
线性表常用的实现方式包括顺序表和链表。
1.1 顺序表顺序表是指用一维数组实现的线性表。
它的特点是元素的逻辑顺序和物理顺序相同，元素之间通过数组下标来进行访问。
顺序表的优点是支持随机访问和元素的快速插入和删除，缺点是需要提前确定表的大小，插入和删除操作可能需要移动大量元素。
1.2 链表链表是另一种常见的线性表实现方式。
它的特点是通过指针将元素连接在一起，元素的逻辑顺序和物理顺序可以不同。
链表的优点是可以动态分配内存空间，插入和删除操作效率高，缺点是无法随机访问，需要额外的指针空间。
2. 栈栈是一种特殊的线性表，它只允许在一端进行插入和删除操作。
栈的特点是先进后出，后进先出，类似于弹夹。
栈的常见实现方式包括顺序栈和链式栈，其应用包括函数调用、表达式求值、括号匹配等。
3. 队列队列也是一种特殊的线性表，它只允许在一端进行插入操作，在另一端进行删除操作。
队列的特点是先进先出，后进后出，类似于排队。
队列的常见实现方式包括顺序队列和链式队列，其应用包括任务调度、缓冲区管理等。
4. 串串是由零个或多个字符组成的有限序列，它是线性结构的一种特殊形式。
串的特点是每个字符之间存在唯一的前驱和后继关系，同时支持字符的插入、删除和替换等操作。
一、插入排序(Insertion Sort)1. 基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
2. 排序过程：【示例】：[初始关键字] [49] 38 65 97 76 13 27 49J=2(38) [38 49] 65 97 76 13 27 49J=3(65) [38 49 65] 97 76 13 27 49J=4(97) [38 49 65 97] 76 13 27 49J=5(76) [38 49 65 76 97] 13 27 49J=6(13) [13 38 49 65 76 97] 27 49J=7(27) [13 27 38 49 65 76 97] 49J=8(49) [13 27 38 49 49 65 76 97]Procedure InsertSort(Var R : FileType);//对R[1..N]按递增序进行插入排序, R[0]是监视哨//Beginfor I := 2 To N Do //依次插入R[2],...,R[n]//beginR[0] := R[I]; J := I - 1;While R[0] < R[J] Do //查找R[I]的插入位置//beginR[J+1] := R[J]; //将大于R[I]的元素后移//J := J - 1endR[J + 1] := R[0] ; //插入R[I] //endEnd; //InsertSort //二、选择排序1. 基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
2. 排序过程：【示例】：初始关键字 [49 38 65 97 76 13 27 49]第一趟排序后 13 ［38 65 97 76 49 27 49]第二趟排序后 13 27 ［65 97 76 49 38 49]第三趟排序后 13 27 38 [97 76 49 65 49]第四趟排序后 13 27 38 49 [49 97 65 76]第五趟排序后 13 27 38 49 49 [97 97 76]第六趟排序后 13 27 38 49 49 76 [76 97]第七趟排序后 13 27 38 49 49 76 76 [ 97]最后排序结果 13 27 38 49 49 76 76 97Procedure SelectSort(Var R : FileType); //对R[1..N]进行直接选择排序 // Beginfor I := 1 To N - 1 Do //做N - 1趟选择排序//beginK := I;For J := I + 1 To N Do //在当前无序区R[I..N]中选最小的元素R[K]// beginIf R[J] < R[K] Then K := Jend;If K <> I Then //交换R[I]和R[K] //begin Temp := R[I]; R[I] := R[K]; R[K] := Temp; end;endEnd; //SelectSort //三、冒泡排序(BubbleSort)1. 基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。
