下载文档原格式
数据结构严蔚敏ppt课件数据结构（严蔚敏）版●资料上传者：安徽大学研究生●资料使用范围：各大学考研及本科教学●欢迎报考安徽大学研究生●“星光考研书屋”祝您学习愉快[学习目标]掌握线性表的顺序存储结构和抽象数据类型中定义的每一种操作的含义，在顺序存储方式下每一种操作的具体实现和相应的时间复杂度；掌握链接存储的概念，线性表的单、双链接存储结构，对它们进行插入和删除结点的方法，循环单、双链表和带表头附加结点的单、双链表的结构和操作特点；掌握每一种线性表操作在由动态结点构成的单链表上具体实现的算法以及相应的时间复杂度。
2第2章线性表线性结构是最常用、最简单的一种数据结构。
而线性表是一种典型的线性结构。
其基本特点是线性表中的数据元素是有序且是有限的。
在这种结构中：① 存在一个唯一的被称为“第一个”的数据元素；② 存在一个唯一的被称为“最后一个”的数据元素；③ 除第一个元素外，每个元素均有唯一一个直接前驱；④ 除最后一个元素外，每个元素均有唯一一个直接后继。
32.1 线性表的逻辑结构线性表(Linear List ) ：是由n(n ≧0)个数据元素(结点)a 1，a 2，…a n 组成的有限序列。
该序列中的所有结点具有相同的数据类型。
其中数据元素的个数n 称为线性表的长度。
当n=0时，称为空表。
当n>0时，将非空的线性表记作： (a 1，a 2，…a n ) a 1称为线性表的第一个(首)结点，a n 称为线性表的最后一个(尾)结点。
2.1.1 线性表的定义4a1，a2，…a i-1都是a i(2≦i≦n)的前驱，其中a i-1是a i的直接前驱;a i+1，a i+2，…a n都是a i(1≦i ≦n-1)的后继，其中a i+1是a i 的直接后继。
2.1.2线性表的逻辑结构线性表中的数据元素a i所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。
◆线性表中的结点可以是单值元素(每个元素只有一个数据项) 。
数据结构严蔚敏第10章内部排序Java 实现内部排序1.概述⼀、什么是排序？排序是计算机内经常进⾏的⼀种操作，其⽬的是将⼀组“⽆序”的记录序列调整为“有序”的记录序列。
⼀般情况下，假设含n 个记录的序列为{R1,R2,…,Rn}，其相应的关键字序列为 { K1, K2, …，Kn }，这些关键字相互之间可以进⾏⽐较，即在它们之间存在着这样⼀个关系Kp1≤Kp2≤…≤Kpn ，按此固有关系将上式记录序列重新排列为{ Rp1, Rp2, …，Rpn }，的操作称作排序。
假设对记录的次关键字进⾏排序，记录之中有两条记录Ri 和Rj ，它们的关键字Ki 和Kj 相等，在排序之前记录Ri 在Rj 之前，若排序之后记录Ri 仍在Rj 之前，则称排序⽅法是稳定的；相反，若经过某种排序之后Ri 在Rj 在之后，则称所⽤的排序⽅法是不稳定的。
⼆、内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很⼤，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
书写规范：数组第⼀个元素L[0]预留，数组长度为L.length-1，尽可能采⽤和课本相同命名2.插⼊排序插⼊排序是⼀种简单直观的排序⽅法，其基本思想是每次将⼀个待排序的记录按其关键字⼤⼩插⼊到前⾯⼰排好序的⼦序列中，直到全部记录插⼊完成。
由插⼊排序的思想可以引申出三个重要的排序算法： 直接插⼊排序、折半插⼊排序和希尔排序。
2.1直接插⼊排序2.2-1 折半插⼊排序相⽐直接插⼊，减少⽐较次数2.2-2 2路插⼊排序相对上⾯减少移动此代码由于涉及到+n%n ，第⼀个元素L[0]不预留static void InsertSort(int[] L){//对数组L 作直接插⼊排序．for (int i = 2; i <=L.length-1 ; i++) {//从第⼆个元素到最后⼀个元素，依次往前插⼊ if(L[i]<L[i-1]){//要插⼊的元素⽐前⼀个⼩，如果⼤于等于就不动 L[0]=L[i];//将L[i]暂存到L[0] L[i]=L[i-1];//前⼀个元素往后移 int j;for ( j= i-2; L[0]<L[j]; j--) {//L[0]⽐前⼀个⼩，继续元素往后移 L[j+1]=L[j]; }L[j+1]=L[0]; } }}static void BinsertSort(int[] L){//对颉序表L 作折半插⼊排序 for (int i = 2; i <=L.length-1 ; i++) { L[0]=L[i];//将L[i]暂存到L[O] int low=1,high=i-1; while(low<=high){ int m=(low+high)/2; if(L[0]<L[m]){ high=m-1; }else{low=m+1; } }for(int j=i-1;j>=high+1;j--){//最终状态⼀定是high 在左，low 在右，low 的位置是插⼊位置 L[j+1]=L[j]; }L[high+1]=L[0];// for(int j=i-1;j>=low;j--){//上⾯四⾏可以替换⼀下 // L[j+1]=L[j]; // }// L[low]=L[0]; }}static void TWayInsertSort(int[] L){ int[] TP=new int[L.length]; int n=L.length; TP[0] = L[0]; int head, tail;head = tail = 0;//两个都指向第⼀个元素 for(int i=1; i<n; ++i) {if(L[i] < TP[head]) {//待排序元素⼩于头往前插 head = (head-1+n)%n; TP[head] = L[i]; }else if(L[i] > TP[tail]) {//待排序元素⼤于头往后插 tail++;TP[tail] = L[i]; }else{//往中间插 tail++;2.2-3 表插⼊排序表插⼊排序，即使⽤链表的存储结构对数据进⾏插⼊排序。
