[it認(rèn)證]java語言程序設(shè)計應(yīng)試輔導(dǎo)二級(編輯修改稿)
2025-02-12 03:43 本頁面
【文章內(nèi)容簡介】 為n+1的線性表為1≤j≤i1則插入前后的兩線性表中的元素滿足如下關(guān)系：≤≤j=i在一般情況下，要在第i（1≤i≤n）個元素之前插入一個新元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共n–i+1個元素依次向后移動一個位置，移動結(jié)束后，第i個位置就被空出，然后將新元素插入到第i項。插入結(jié)束后，線性表的長度就增加了1。顯然，在線性表采用順序存儲結(jié)構(gòu)時，如果插入運(yùn)算在線性表的末尾進(jìn)行，即在第n個元素之后（可以認(rèn)為是在第n+1個元素之前）插入新元素，則只要在表的末尾增加一個元素即可，不需要移動表中的元素；但如果要在線性表的第1個元素之前插入一個新元素，則需要移動表中所有的元素。在一般情況下，如果插入運(yùn)算在第i（1≤i≤n）個元素之前進(jìn)行，則原來第i個元素之后（包括第i個元素）的所有元素都必須移動。在平均情況下，要在線性表中插入一個新元素，需要移動表中一半的元素。因此，在線性表順序存儲的情況下，要插入一個新元素，其效率是很低的，特別是在線性表比較大的情況下更為突出，由于數(shù)據(jù)元素的移動而消耗較多的處理時間。（4）順序表的刪除運(yùn)算設(shè)長度為n的線性表為……現(xiàn)要刪除第i個元素，刪除后得到長度為n–1的線性表為……ajaj+11≤j≤i1i≤j≤n1則刪除前后的兩線性表中的元素滿足如下關(guān)系：在一般情況下，要刪除第i（1≤i≤n）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n–i個元素依次向前移動一個位置。刪除結(jié)束后，線性表的長度就減小了1。顯然，在線性表采用順序存儲結(jié)構(gòu)時，如果刪除運(yùn)算在線性表的末尾進(jìn)行，即刪除第n個元素，則不需要移動表中的元素；但如果要刪除線性表中的第1個元素，則需要移動表中所有的元素。在一般情況下，如果要刪除第i（1≤i≤n）個元素，則原來第i個元素之后的所有元素都必須依次往前移動一個位置。在平均情況下，要在線性表中刪除一個元素，需要移動表中一半的元素。因此，在線性表順序存儲的情況下，要刪除一個元素，其效率也是很低的，特別是在線性表比較大的情況下更為突出，由于數(shù)據(jù)元素的移動而消耗較多的處理時間。4．棧和隊列（1）棧及其基本運(yùn)算① 棧的基本概念棧實際上也是線性表，只不過是一種特殊的線性表。在這種特殊的線性表中，其插入與刪除運(yùn)算都只在線性表的一端進(jìn)行。即在這種線性表的結(jié)構(gòu)中，一端是封閉的，不允許進(jìn)行插入與刪除元素；另一端是開口的，允許插入與刪除元素。即棧（stack）是限定在一端進(jìn)行插入與刪除的線性表。在棧中，允許插入與刪除的一端稱為棧頂，而不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，從而也是最先能被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。即棧是按照“先進(jìn)后出”（First In Last Out，F(xiàn)ILO）或“后進(jìn)先出”（Last In First Out，LIFO）的原則組織數(shù)據(jù)的，因此，棧也被稱為“先進(jìn)后出”表或“后進(jìn)先出”表。由此可以看出，棧具有記憶作用。通常用指針top來指示棧頂?shù)奈恢?，用指針bottom指向棧底。往棧中插入一個元素稱為入棧運(yùn)算，從棧中刪除一個元素（即刪除棧頂元素）稱為退棧運(yùn)算。棧頂指針top動態(tài)反映了棧中元素的變化情況。② 棧的順序存儲及其運(yùn)算與一般的線性表一樣，在程序設(shè)計語言中，用一維數(shù)組S（1∶m）作為棧的順序存儲空間，其中m為棧的最大容量。通常，棧底指針指向棧空間的低地址一端（即數(shù)組的起始地址這一端）。在棧的順序存儲空間S（1∶m）中，S（bottom）通常為棧底元素（在棧非空的情況下），S（top）為棧頂元素。top=0表示棧空；top=m表示棧滿。棧的基本運(yùn)算有3種：入棧、退棧與讀棧頂元素。 入棧運(yùn)算入棧運(yùn)算是指在棧頂位置插入一個新元素。這個運(yùn)算有兩個基本操作：首先將棧頂指針進(jìn)一（即top加1），然后將新元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲空間的最后一個位置時，說明?？臻g已滿，不可能再進(jìn)行入棧操作。這種情況稱為棧“上溢”錯誤。 退棧運(yùn)算退棧運(yùn)算是指取出棧頂元素并賦給一個指定的變量。這個運(yùn)算有兩個基本操作：首先將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量，然后將棧頂指針退一（即top減1）。當(dāng)棧頂指針為0時，說明?？?，不可能進(jìn)行退棧操作。這種情況稱為棧“下溢”錯誤。 讀棧頂元素讀棧頂元素是指將棧頂元素賦給一個指定的變量。必須注意，這個運(yùn)算不刪除棧頂元素，只是將它的值賦給一個變量，因此，在這個運(yùn)算中，棧頂指針不會改變。當(dāng)棧頂指針為0時，說明?？眨x不到棧頂元素。（2）隊列及其基本運(yùn)算① 隊列的基本概念隊列（Equeue）是指允許在一端進(jìn)行插入而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊尾，通常用一個稱為尾指針（rear）的指針指向隊尾元素，即尾指針總是指向最后被插入的元素；允許刪除的一端稱為排頭（也稱為隊頭），通常也用一個排頭指針（front）指向排頭元素的前一個位置。顯然，在隊列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先能夠被刪除，反之，最后插入的元素將最后才能被刪除。因此，隊列又稱為“先進(jìn)先出”（First In First Out，F(xiàn)IFO）或“后進(jìn)后出”（Last In Last Out，LILO）的線性表，它體現(xiàn)了“先來先服務(wù)”的原則。在隊列中，隊尾指針rear與排頭指針front共同反映了隊列中元素動態(tài)變化的情況。往隊列的隊尾插入一個元素稱為入隊運(yùn)算，從隊列的排頭刪除一個元素稱為退隊運(yùn)算。② 循環(huán)隊列及其運(yùn)算所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在循環(huán)隊列結(jié)構(gòu)中，當(dāng)存儲空間的最后一個位置已被使用而再要進(jìn)行入隊運(yùn)算時，只要存儲空間的第一個位置空閑，便可將元素加入到第一個位置，即將存儲空間的第一個位置作為隊尾。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從排頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素。循環(huán)隊列的初始狀態(tài)為空，即rear=front=m。循環(huán)隊列主要有兩種基本運(yùn)算：入隊運(yùn)算與退隊運(yùn)算。每進(jìn)行一次入隊運(yùn)算，隊尾指針就進(jìn)一。當(dāng)隊尾指針rear=m+1時，則置rear=1。每進(jìn)行一次退隊運(yùn)算，排頭指針就進(jìn)一。當(dāng)排頭指針front=m+1時，則置front=1。在實際使用循環(huán)隊列時，為了能區(qū)分隊列滿還是隊列空，通常還需增加一個標(biāo)志s，s值的定義如下：由此可以得出隊列空與隊列滿的條件如下。隊列空的條件為 s=0；隊列滿的條件為（s=1）且（front=rear）。循環(huán)隊列入隊與退隊的算法如下。假設(shè)循環(huán)隊列的初始狀態(tài)為空，即s=0，且front=rear=m。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1