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

《数据结构 叶核亚(例题)-例题-例题-第3章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、【例3.1】顺序表的直接插入排序的算法实现与测试。程序如下：importds_java.LinearList1;//顺序存储结构的线性表类publicclassInsertSort1extendsLinearList1//直接插入排序{publicInsertSort1(inttable[])//将table数组元素依次插入已排序顺序表{super(table.length);for(inti=0;i

2、ta(intk)//插入k值{inti=search(k);//顺序查找System.out.print("k="+k+"i="+i+"");for(intj=this.length();j>=i;j--)this.set(j+1,this.get(j));//将第j个元素值后移一位this.set(i,k);//设置第i个元素值为kthis.output();}publicintsearch(intk)//顺序查找k值{//返回k值应在的位置inti=1;while(i<=this.length()&&k>thi

3、s.get(i))//短路计算i++;returni;}publicstaticvoidmain(Stringargs[]){inttable[]={5,3,2,4,7,1,8,6};newInsertSort1(table);}}程序运行结果如下：k=5i=1table:50000000k=3i=1table:35000000k=2i=1table:23500000k=4i=3table:23450000k=7i=5table:23457000k=1i=1table:12345700k=8i=7table:123

4、45780k=6i=6table:12345678【例3.2】双向链表的直接插入排序。程序如下：importds_java.TwolinkNode;//双向链表的结点类importds_java.Twolink1;//双向链表类publicclassTwolink2extendsTwolink1//双向链表插入排序{protectedTwolinkNoderear;//引用链表最后一个结点Twolink2()//建立空链表{super();//head==nullrear=null;}Twolink2(intn)/

5、/n个随机值插入双向链表{inti=0,k;System.out.print("insert:");for(i=0;i

6、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

7、结点之后q.prior=rear;rear=q;}}}}catch(Exceptione)//捕获异常{System.out.println(e);//显示异常信息output();//输出双向链表}}publicstaticvoidmain(Stringargs[]){(newTwolink2(8)).output();}}程序运行结果如下：insert:777673878922641Twolink2:1->22->64->73->76->77->87->89