[工學(xué)]chap2順序表-閱讀頁(yè)
2024-11-02 23:34本頁(yè)面
【正文】 s[]){ LiearList addressBook=new ArrayList(6)。 (new Address(“李明 ” ,”13602225611”,”中原路 201號(hào) ” ))。 (new Address(“王五 ” ,”13502356781”,”中原路 14號(hào) ” ))。 (“查找王五的位置 ” )。 (“王五位于第 “ +k+”個(gè)元素 ” )。 (3, Address(“馬六 ” ,”13688723421”,”中原路 36號(hào) ” ))。 Address add=search(new Address(“王五 ” ,””,””))。 (())。 ? 算法分析不是我們的重點(diǎn)，我們只給出結(jié)論 ?刪除、插入以外的操作很顯然是與線性表的數(shù)據(jù)多少無(wú)關(guān)的所以，時(shí)間復(fù)雜度為 O(1) ?刪除、插入操作最主要的操作是移動(dòng)數(shù)據(jù)，很顯然數(shù)據(jù)越多，可能需要移動(dòng)的數(shù)據(jù)就越多，平均 n/2 所以，時(shí)間復(fù)雜度為 O(n). 第二章 線性表 32 綜合舉例 ? 約瑟夫 (Josephus)環(huán)問(wèn)題 描述：一個(gè)圓周上的N個(gè)人，從第 s個(gè)開(kāi)始數(shù)，數(shù)到 d時(shí)，刪除此人。 while(jd) { i=i%N+1。 } (“out:” +(i)。 k。 } while(i=N amp。 (i)==0) i++。 } } Import LinearList1 Public class Josephus1 { public static void main(string arg[]) { int N=5,s=1,d=2。 int i,j,k。 ()。 k=N。// j=0。 j++。 (i)。 ()。 } } Import LinearList1 Public class Josephus1 { public static void main(string arg[]) { int N=5,s=1,d=2。 int i,j,k。 ()。 //i=s1。 i=1 1 2 3 4 5 第二章 線性表 36 例：演示一個(gè)數(shù)據(jù)元素為 person對(duì)象的線性表 ? 構(gòu)成一個(gè)線性表，每個(gè)元素代表一個(gè)人的基本信息。 (, First name: + firstName)。 } // public String getLast() // get last name { return lastName。 private String firstName。 // public Person(String last, String first, int a) { // constructor lastName = last。 age = a。 for(j=0。 j++) // look for it if( a[j].getLast().equals(searchName) ) break。t find it return false。knElems。 nElems。 } } // end delete() // public void displayA() // displays array contents { for(int j=0。 j++) // for each element, a[j].display()。 // reference to array private int nElems。 // create the array nElems = 0。 for(j=0。 j++) // for each element, if( a[j].getLast().equals(searchName) ) // break。 // yes, can39。 // no, found it } // end find() // // put person into array public void insert(String last, String first, int age) { a[nElems] = new Person(last, first, age)。 // increment size } 第二章 線性表 39 String searchKey = Stimson。 found=(searchKey)。 ()。t find + searchKey)。 (Smith)。 (Creswell)。 // display items again } // end main() } // end class ClassDataApp // // data items as class objects // to run this program: Cjava ClassDataApp /////////////////////// class ClassDataApp { public static void main(String[] args) { int maxSize = 100。 // reference to array arr = new ClassDataArray(maxSize)。 (Smith, Lorraine, 37)。 (Adams, Henry, 63)。 (Stimson, Henry, 29)。 (Lamarque, Henry, 54)。 (Creswell, Lucinda, 18)。 // display items 第二章 線性表 40 ? 線性表 ?線性表的概念 ?順序存儲(chǔ)的線性表 ? 順序表的類(lèi)定義 ? 順序表的操作 ? 順序表操作的算法分析 ? 綜合舉例 ?鏈?zhǔn)酱鎯?chǔ)的線性表
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1