數(shù)據(jù)結(jié)構(gòu)主講人：張靜常州信息職業(yè)技術(shù)學院2.4線性表的應用Part01順序表的應用

1.順序表的就地逆置順序表的應用6925201260453730順序表的應用//順序表逆置public

voidreverse(SeqList<Integer>list){int

t;//i下標從頭開始往后,j下標從尾開始往前

for(int

i=0,j=list.size()-1;i<j;i++,j--){

t=list.data[i];list.data[i]=list.data[j];list.data[j]=t; }}public

classReverseListTest{public

static

voidmain(String[]args){ Integera[]={25,30,20,45,60,12,37,69}; SeqListlist=newSeqList(a);

System.out.println("逆置前：");

list.printList();//輸出逆置前的順序表

list.reverse(list);//順序表逆置

System.out.println("\n逆置后：");

list.printList();//輸出逆置后的順序表

}}算法實現(xiàn)假設(shè)有兩個包含若干整數(shù)的有序順序表listA和listB，其元素均已按從小到大的升序排列。編寫一個算法將它們合并成一個有序順序表listC，要求listC的元素也是從小到大排列的。2.有序順序表的合并順序表的應用123689100224391112123689100120ListAListBListCij12<2222<362236<434391112120順序表的應用public

classMergeList{//有序順序表的合并public

voidmerge(SeqListlistA,SeqListlistB,SeqListlistC){int

i,j;i=j=0;//兩表均從第一個元素開始依次掃描、比較while(i<listA.size()&&j<listB.size()){

if(listA.get(i)<listB.get(j)){//將兩表中較小的數(shù)插入到listC表中

listC.insert(listA.get(i));

i++; }else{

listC.insert(listB.get(j));

j++; } }while(i<listA.size()){//若剩余的是listA表，將表中剩余元素全部插入到listC表中

listC.insert(listA.get(i));

i++;}while(j<listB.size()){//若剩余的是listB表，將表中剩余元素全部插入到listC表中

listC.insert(listB.get(j));

j++;}}}public

classMergeListTest{public

static

voidmain(String[]args){ //通過有序數(shù)組創(chuàng)建順序表listA，listBIntegera[]={12,36,89,100};Integerb[]={22,43,91,112,120}; SeqListlistA=newSeqList(a); SeqListlistB=newSeqList(b);

SeqListlistC=newSeqList();//創(chuàng)建順序表listC-空表

MergeListml=newMergeList();ml.merge(listA,listB,listC);//有序順序表合并

listC.printList();//輸出順序表listC}}算法實現(xiàn)Part02單鏈表的應用和順序表的就地逆置一樣，單鏈表的就地逆置是在原鏈表上進行逆置，不額外增加新結(jié)點，不重新建鏈表。1.單鏈表的就地逆置單鏈表的應用head2147∧65逆置前head476515∧21逆置后單鏈表的應用head2147∧65逆置前head∧2147∧65qpr算法分析phead2115∧47∧65qpr單鏈表的應用public

voidreverse(SinglyLinkedList<Integer>list){Nodep,q,r;p=list.head.next;if(p==null||p.next==null){//若單鏈表為空或只有一個結(jié)點，無需逆置

return;}

q=p;p=p.next;//p指向第二個結(jié)點，準備和前面的結(jié)點斷開，成一無頭結(jié)點的鏈表q.next=null;//將第一個結(jié)點的next域置空，將原鏈表一分為二while(p!=null){

r=p.next;

p.next=q;//將無頭結(jié)點鏈表上的第一個結(jié)點摘下，插入到帶頭結(jié)點的第一個結(jié)點處

q=p;

p=r;}list.head.next=q; } }public

classReverseLinkedListTest{public

static

voidmain(String[]args){Integera[]={25,30,20,45,60,12,37,69}; SinglyLinkedListlist=newSinglyLinkedList(a);

System.out.println("逆置前：");list.printList();//輸出逆置前的單鏈表

list.reverse(list);//單鏈表逆置System.out.println("\n逆置后：");list.printList();//輸出逆置前的單鏈表}}算法實現(xiàn)與有序順序表的合并類似，有序單鏈表的合并采用“指針平行移動，依次掃描比較”的方法。從兩張表listA和listB的開始結(jié)點沿著鏈表逐個將對應數(shù)據(jù)元素進行比較，將較小的數(shù)據(jù)元素插入listC表尾。當兩表之一掃描完畢時，將另一個鏈表的剩余結(jié)點插入listC表尾即可。2.有序單鏈表的合并單鏈表的應用單鏈表的應用public

classSortedSinglyList<TimplementsComparable<T>>extendsSinglyLinkedList<T>{publicSortedSinglyList(){

super();}publicSortedSinglyList(T[]values){//數(shù)組中所有對象排序插入for(int

i=0;i<values.length;i++){

this.insert(values[i]);//排序單鏈表按對象大小插入}}//不支持父類的以下兩個方法，將其覆蓋并拋出異常@Overridepublic

voidset(int

i,Tt){

throw

newjava.lang.UnsupportedOperationException("set(inti,Tx)");}public

intinsert(int

i,Tt){

throw

newjava.lang.UnsupportedOperationException("insert(inti,Tx)");}

排序單鏈表類//重寫父類的insert(t)方法，根據(jù)t的大小插入在相應位置，保證鏈表是按數(shù)據(jù)遞增排列public

intinsert(Tt){int

i=0;Nodefront=this.head,p=front.next;//front指向p的前驅(qū)結(jié)點while(p!=null&&t.compareTo(p.data)>0){//尋找插入位置

front=p;

p=p.next;

i++;}front.next=newNode(t,p);//在front之后p之前插入值為t的結(jié)點

return

i;}}單鏈表的應用public

classMergeLinkedList{//有序單鏈表的合并public

voidmerge(SortedSinglyListlistA,SortedSinglyListlistB,SortedSinglyListlistC){Nodepa=listA.head.next;Nodepb=listB.head.next;

//兩表均從第一個元素開始依次掃描、比較

while(pa!=null&&pb!=null){

if(pa.data<pb.data){//將兩表中較小的數(shù)插入到listC表中

listC.insert(pa.data);

pa=pa.next; }else{

listC.insert(pb.data);

pb=pb.next; }}while(pa!=null){//若剩余的是listA表，將表中剩余元素全部插入到listC表中

listC.in