数据结构 叶核亚(例题)-例题-例题-第3章.doc

【例3.1】 顺序表的直接插入排序的算法实现与测试。程序如下：import ds_java.LinearList1; /顺序存储结构的线性表类public class InsertSort1 extends LinearList1 /直接插入排序 public InsertSort1(int table) /将table数组元素依次插入已排序顺序表 super(table.length); for(int i=0;i=i;j-) this.set(j+1,this.get(j); /将第j个元素值后移一位 this.set(i,k); /设置第i个元素值为k this.output(); public int search(int k) /顺序查找k值 /返回k值应在的位置 int i=1; while(ithis.get(i)/短路计算 i+; return i; public static void main(String args) int table=5,3,2,4,7,1,8,6; new InsertSort1(table); 程序运行结果如下：k=5 i=1 table: 5 0 0 0 0 0 0 0k=3 i=1 table: 3 5 0 0 0 0 0 0k=2 i=1 table: 2 3 5 0 0 0 0 0k=4 i=3 table: 2 3 4 5 0 0 0 0k=7 i=5 table: 2 3 4 5 7 0 0 0k=1 i=1 table: 1 2 3 4 5 7 0 0k=8 i=7 table: 1 2 3 4 5 7 8 0k=6 i=6 table: 1 2 3 4 5 6 7 8【例3.2】 双向链表的直接插入排序。程序如下：import ds_java.TwolinkNode; /双向链表的结点类import ds_java.Twolink1; /双向链表类public class Twolink2 extends Twolink1 /双向链表插入排序 protected TwolinkNode rear; /引用链表最后一个结点 Twolink2() /建立空链表 super(); /head=null rear=null; Twolink2(int n) /n个随机值插入双向链表 int i=0,k; System.out.print(insert: ); for(i=0;in;i+) k=(int)(Math.random()*100); System.out.print(k+ ); insert(k); System.out.println(); public void insert(int k) /k值插入已排序的双向链表 TwolinkNode p=null,q=null; try q=new TwolinkNode(k) ; /创建k值结点q if(head=null) head=q ; /空表插入 rear=head; else if(kp.data) p=p.next; /向后走 if(p!=null) /表中插入 q.prior=p.prior; /将q插入在结点p之前 q.next=p; (p.prior).next=q; p.prior=q; else /表尾插入 rear.next=q; /将q插在rear结点之后 q.prior=rear; rear=q; catch(Exception e) /捕获异常 System.out.println(e); /显示异常信息 output(); /输出双向链表 public static void main(String args) (new Twolink2(8).output(); 程序运