1、int in,out;for（out=nElems-1;out0;out-） for（in=0;inain+1） Swap（in,in+1）;算法的不变性：许多算法中，有些条件在算法执行过程中始终是不变的。这些条件被称 为算法的不变性，如果不变性不为真了，则标记出错了；冒泡排序的效率O（N*N），比较N*N/2，交换N*N/4；2. 选择排序的思想：假设有N条数据，则暂且标记第0个数据为MIN（最小），使用OUT标记最左边未排序的数据，然后使用IN标记第1个数据，依次与MIN进行比较，如果比MIN小，则将该数据标记为MIN，当第一轮比较完后，最终的MIN与OUT标记数据交换，依次类推；选择排序
2、的java代码：Public void selectSort（）Int in,out,min;For（out=0;outnElems-1;out+） Min=out;For（in=out+1;nElems; If（ainamin） Min=in;Swap（out,min）;选择排序的效率：O（N*N），比较N*N/2，交换0& ain-1temp） Ain=ain-1; - -in;Ain=temp;插入排序的效率：O（N*N）, 比较N*N/4，复制N*N/4；插入排序在随机数的情况下，比冒泡快一倍，比选择稍快；在基本有序的数组中，插入排序几乎只需要O（N）；在逆序情况下，并不比冒泡快；二、
3、栈与队列1、栈的定义 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。（1）通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。（2）当表中没有元素时称为空栈。（3）栈为后进先出（Last In First Out）的线性表，简称为LIFO表。 栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中最新的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。【示例】元素是以a1，a2，an的顺序进栈，退栈的次序却是an，an-1，a1。2、栈的基本运算（1）InitStack（S） 构造一个空栈S。（2）StackEmpty
4、（S） 判栈空。若S为空栈，则返回TRUE，否则返回FALSE。（3）StackFull（S） 判栈满。若S为满栈，则返回TRUE，否则返回FALSE。注意： 该运算只适用于栈的顺序存储结构。（4）Push（S，x） 进栈。若栈S不满，则将元素x插入S的栈顶。（5）Pop（S） 退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。（6）StackTop（S） 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。队列的定义及基本运算1、定义 队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表（1）允许删除的一端称为队头（Front）。（2）允许插入的一端称为队
5、尾（Rear）。（3）当队列中没有元素时称为空队列。（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。 队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许加塞），每次离开的成员总是队列头上的（不允许中途离队），即当前最老的成员离队。【例】在队列中依次加入元素a1，a2，an之后，a1是队头元素，an是队尾元素。退出队列的次序只能是a1，a2，an。2、队列的基本逻辑运算（1）InitQueue（Q） 置空队。构造一个空队列Q。（2）QueueEmpty（Q） 判队空。若队列Q为空，则返回真值，否则返回假值。（3） QueueFull（
6、Q） 判队满。若队列Q为满，则返回真值，否则返回假值。 注意：此操作只适用于队列的顺序存储结构。（4） EnQueue（Q，x） 若队列Q非满，则将元素x插入Q的队尾。此操作简称入队。（5） DeQueue（Q） 若队列Q非空，则删去Q的队头元素，并返回该元素。此操作简称出队。（6） QueueFront（Q） 若队列Q非空，则返回队头元素，但不改变队列Q的状态。三、链表1 链结点在链表中，每个数据项都被包含在点“中，一个点是某个类的对象，这个类可认叫做LINK。因为一个链表中有许多类似的链结点，所以有必要用一个不同于链表的类来表达链结点。每个LINK对象中都包含一个对下一个点引用的字段（通常
7、叫做next）但是本身的对象中有一个字段指向对第一个链结点的引用单链表用一组地址任意的存储单元存放线性表中的数据元素。以元素（数据元素的映象） + 指针（指示后继元素存储位置）= 结点（表示数据元素 或 数据元素的映象）以“结点的序列”表示线性表 称作线性链表（单链表）单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 1、链接存储方法链接方式存储的线性表简称为链表（Linked List）。链表的具体存储表示为： 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是
8、不连续的） 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链（link）注意：链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。2、链表的结点结构datanext data域-存放结点值的数据域next域-存放结点的直接后继的地址（位置）的指针域（链域）链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。每个结点只有一个链域的链表称为单链表（Single Linked List）。【例】线性表（bat，cat，ea
9、t，fat，hat，jat，lat，mat）的单链表示如示意图3、头指针head和终端结点指针域的表示单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。【例】头指针名是head的链表可称为表head。终端结点无后继，故终端结点的指针域为空，即NULL。4、单链表的一般图示法由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，线性表（bat，cat，fat，hat，jat，lat，mat）的单链表就可以表示为下图形式。5、单链表类型描述type
10、def char DataType; /假设结点的数据域类型为字符typedef struct node /结点类型定义DataType data; /结点的数据域struct node *next;/结点的指针域ListNodetypedef ListNode *LinkList;ListNode *p;LinkList head;*LinkList和ListNode是不同名字的同一个指针类型（命名的不同是为了概念上更明确）*LinkList类型的指针变量head表示它是单链表的头指针ListNode类型的指针变量p表示它是指向某一结点的指针6、指针变量和结点变量 指针变量结点变量 定义 在
11、变量说明部分显式定义 在程序执行时，通过标准 函数malloc生成 取值 非空时，存放某类型结点 实际存放结点各域内容 的地址 操作方式 通过指针变量名访问 通过指针生成、访问和释放 生成结点变量的标准函数p=（ ListNode *）malloc（sizeof（ListNode）；/函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中释放结点变量空间的标准函数 free（p）；/释放p所指的结点变量空间结点分量的访问 利用结点变量的名字*p访问结点分量方法一：（*p）.data和（*p）.next方法二：p-data和p-next指针变量p和结点变量*
12、p的关系 指针变量p的值结点地址结点变量*p的值结点内容（*p）.data的值p指针所指结点的data域的值（*p）.next的值*p后继结点的地址*（*p）.next）*p后继结点 若指针变量p的值为空（NULL），则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。 有关指针类型的意义和说明方式的详细解释可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。因此，在单链表中第 i 个结点之前进行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。双端链表双端链表与传统
13、的链表非常相似，但是它有一个新增的特性：即对最后一个链结点的引用，就像对第一个链结点的引用一样。对最后一个链结点的引用允许像在表头一样，在表尾直接插入一个链结点。当然，仍然可以在普通的单链表的表尾插入一个链结点，方法是遍历整个链表直到到达表尾，但是这种方法效率很低。像访问表头一样访问表尾的特性，使双端链表更适合于一些普通链表不方便操作的场合，队列的实现就是这样一个情况。下面是一个双端链表的例子。class Link3 public long dData; public Link3 next; /. public Link3（long d） dData=d; public void displa
14、yLink（） System.out.print（dData+ ）;/class FirstLastList private Link3 first; private Link3 last; public FirstLastList（） first=null; last=null; /. public boolean isEmpty（） return first=null; public void insertFirst（long dd） Link3 newLink=new Link3（dd）; if（isEmpty（） last=newLink; newLink.next=first; fi
15、rst=newLink; /. public void insertLast（long dd） else last.next=newLink; /. public long deleteFirst（） long temp=first.dData; if（first.next=null） first=first.next; return temp; /. public void displayList（） System.out.print（List （first-last）: Link3 current=first; while（current!=null） current.displayLin
16、k（）; current=current.next; System.out.println（/public class FirstLastApp public static void main（String args） FirstLastList theList=new FirstLastList（）; theList.insertFirst（22）; theList.insertFirst（44）; theList.insertFirst（66）; theList.insertLast（11）; theList.insertLast（33）; theList.insertLast（55）;
17、theList.displayList（）; theList.deleteFirst（）;为了简单起见，在这个程序中，把每个链结点中的数据字段个数从两个压缩到一个。这更容易显示链结点的内容。（记住，在一个正式的程序中，可能会有非常多的数据字段，或者对另外一个对象的引用，那个对象也包含很多数据字段。）这个程序在表头和表尾各插入三个链点，显示插入后的链表。然后删除头两个链结点，再次显示。注意在表头重复插入操作会颠倒链结点进入的顺序，而在表尾的重复插入则保持链结点进入的顺序。双端链表类叫做FirstLastList。它有两个项，first和last，一个指向链表中的第一个链结点，另一个指向最后一个链
18、结点。如果链表中只有一个链结点，first和last就都指向它，如果没有链结点，两者都为Null值。这个类有一个新的方法insertLast（），这个方法在表尾插入一个新的链结点。这个过程首先改变last.next，使其指向新生成的链结点，然后改变last，使其指向新的链结点。插入和删除方法和普通链表的相应部分类似。然而，两个插入方法都要考虑一种特殊情况，即插入前链表是空的。如果isEmpty（）是真，那么insertFirst（）必须把last指向新的链结点，insertLast（）也必须把first指向新的链结点。如果用insertFirst（）方法实现在表头插入，first就指向新的链结
19、点，用insertLast（）方法实现在表尾插入，last就指向新的链结点。如果链表只有一个链结点，那么多表头删除也是一种特殊情况：last必须被赋值为null值。不幸的是，用双端链表也不能有助于删除最后一个链结点，因为没有一个引用指向倒数第二个链结点。如果最后一个链结点被删除，倒数第二个链结点的Next字段应该变成Null值。为了方便的删除最后一个链结点，需要一个双向链表。（当然，也可以遍历整个链表找到最后一个链结点，但是那样做效率不是很高。有序链表在有序链表中，数据是按照关键值有序排列的。有序链表的删除常常是只限于删除在链表头部的最小链结点。不过，有时也用Find（）方法和Delete（）
20、方法在整个链表中搜索某一特定点。一般，在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度，另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。但是，有序链表实现起来比有序数组更困难一些。后而将看到一个有序链表的应用：为数据排序。有序链表也可以用于实现优先级队列，尽管堆是更常用的实现方法。在有序链表中插入一个数据项的Java代码为了在一个有序链表中插入数据项，算法必须首先搜索链表，直到找到合适的位置：它恰好在第一个比它大的数据项的前面。当算法找到了要插入的位置，用通常的方式插入数据项：把新链结点的Next字段指向下一个链结点，然后把前一个
21、链结点的Next字段改为指向新的链结点。然而，需要考虑一些特殊情况：链结点有可以插在表头，或者插在表尾。看一下这段代码：Public void insert（long key） Link newLink=new Link（key）; Link previous=null; Link current=first; While（current!=null & keycurrent.dData） Previous=current; Current=current.next; If（previous=null） First=newLink; Else Previous.next=newLink; ne
22、wLink.next=current;在链表上移动时，需要用一个previous引用，这样才能把前一个链结点的Next字段指向新的链结点。创建新链结点后，把current变量设为first，准备搜索正确的插入点。这时也把previous设为Null值，这步操作很重要，因为后面要用这个Null值判断是否仍在表头。While循环和以前用来搜索插入点的代码类似，但是有一个附加的条件。如果当前检查的链结点的关键值不再小于待插入的链结点的关键值，则循环结束；这是最常见的情况，即新关键值插在链表中部的某个地方。然而，如果current为Null值，while循环也会停止。这种情况发生在表尾，或者链表为空时
23、。如果current在表头或者链表为空，previous将为Null值；所以让first指向新的链结点。否则current处在链表中部或结尾，就使previous的next字段指向新的链结点。不论哪种情况、都让新链结点的Next字段指向current。如果在表尾，current为Null值，则新链结点的Next字段也本应该设为这个值（Null）。下面是有序链表的程序SortedList.java程序实现了一个SortedList类，它拥有insert（）、remove（）和displayList（）方法。只有insert（）方法与无序链表中的insert（）方法不同。package 有序链表;class Link pub
