【正文】 試探失敗，就逐步回退，換別的路線再進(jìn)行試探。這種方法稱為回溯法?；厮莘ㄔ谔幚韽?fù)雜數(shù)據(jù)結(jié)構(gòu)方面有著廣泛的應(yīng)用。（5）算法復(fù)雜度算法的復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。① 算法的時間復(fù)雜度所謂算法的時間復(fù)雜度，是指執(zhí)行算法所需要的計算工作量。算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=f(n)其中n是問題的規(guī)模。在同一問題規(guī)模下，如果算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某一特定輸入時，可以用以下兩種方法來分析算法的工作量。平均性態(tài)（Average Behavior）所謂平均性態(tài)分析是指用各種特定輸入下的基本運(yùn)算次數(shù)的帶權(quán)平均值來度量算法的工作量。算法的平均性態(tài)定義為其中，x是所有可能輸入中的某個特定輸入，p(x)是x出現(xiàn)的概率（即輸入為x的概率），t(x)是算法在輸入為x時所執(zhí)行的基本運(yùn)算次數(shù)，Dn表示當(dāng)規(guī)模為n時，算法執(zhí)行時所有可能輸入的集合。最壞情況復(fù)雜性（WorstCase Complexity）所謂最壞情況復(fù)雜性，是指在規(guī)模為n時，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。它定義為顯然，W(n)的計算要比A(n)的計算方便得多。由于W(n)實(shí)際上是給出了算法工作量的一個上界，因此，它比A(n)更具有實(shí)用價值。② 算法的空間復(fù)雜度一個算法的空間復(fù)雜度，一般是指執(zhí)行這個算法所需要的內(nèi)存空間。一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間。如果額外空間量相對于問題規(guī)模來說是常數(shù)，則稱該算法是原地（in place）工作的。在許多實(shí)際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技術(shù)，以便盡量減少不必要的額外空間。2．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)作為計算機(jī)的一門學(xué)科，主要研究和討論以下3個方面的問題。 數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)； 在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)； 對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。（1）什么是數(shù)據(jù)結(jié)構(gòu)簡單地說，數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。在數(shù)據(jù)處理領(lǐng)域中，每一個需要處理的對象都可以抽象成數(shù)據(jù)元素。數(shù)據(jù)元素一般簡稱為元素。前后件關(guān)系是數(shù)據(jù)元素之間的一個基本關(guān)系，但前后件關(guān)系所表示的實(shí)際意義是隨具體對象的不同而不同。一般來說，數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來描述。① 數(shù)據(jù)的邏輯結(jié)構(gòu)通俗地說，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。在此，所謂結(jié)構(gòu)實(shí)際上就是指數(shù)據(jù)元素之間的前后件關(guān)系。一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面的信息。 表示數(shù)據(jù)元素的信息； 表示各數(shù)據(jù)元素之間的前后件關(guān)系。所謂數(shù)據(jù)的邏輯結(jié)構(gòu)，是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。由前面的敘述可以知道，數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關(guān)系，它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。即一個數(shù)據(jù)結(jié)構(gòu)可以表示成B=(D，R)其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。例如，假設(shè)a與b是D中的兩個數(shù)據(jù)，則二元組（a，b）表示a是b的前件，b是a的后件。這樣，在D中的每兩個元素之間的關(guān)系都可以用這種二元組來表示。② 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。一個數(shù)據(jù)結(jié)構(gòu)中的各數(shù)據(jù)元素在計算機(jī)存儲空間中的位置關(guān)系與邏輯關(guān)系有可能是不同的。由于數(shù)據(jù)元素在計算機(jī)存儲空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此，為了表示存放在計算機(jī)存儲空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系（即前后件關(guān)系），在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。而采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時，選擇合適的存儲結(jié)構(gòu)是很重要的。（2）數(shù)據(jù)結(jié)構(gòu)的圖形表示在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡稱為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對于關(guān)系R中的每一個二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。有時在不會引起誤會的情況下，在前件結(jié)點(diǎn)到后件結(jié)點(diǎn)連線上的箭頭可以省去。在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，沒有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)（也稱為葉子結(jié)點(diǎn)）。數(shù)據(jù)結(jié)構(gòu)中除了根結(jié)點(diǎn)與終端結(jié)點(diǎn)外的其他結(jié)點(diǎn)一般稱為內(nèi)部結(jié)點(diǎn)。（3）線性結(jié)構(gòu)與非線性結(jié)構(gòu)根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個非空的數(shù)據(jù)結(jié)構(gòu)同時滿足下列兩個條件：① 有且只有一個根結(jié)點(diǎn)；② 每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，線性結(jié)構(gòu)又稱線性表。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。一個空的數(shù)據(jù)結(jié)構(gòu)究竟是屬于線性結(jié)構(gòu)還是屬于非線性結(jié)構(gòu)，這要根據(jù)具體情況來確定。如果對該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是按線性結(jié)構(gòu)的規(guī)則來處理的，則屬于線性結(jié)構(gòu)；否則屬于非線性結(jié)構(gòu)。3．線性表及其順序存儲結(jié)構(gòu)（1）線性表的基本概念線性表是由n（n≥0）個數(shù)據(jù)元素a1，a2，…，an組成的一個有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。即線性表或是一個空表，或可以表示為（a1，a2，…，ai，…，an）其中ai（i=1，2，…，n）是屬于數(shù)據(jù)對象的元素，通常也稱其為線性表中的一個結(jié)點(diǎn)。顯然，線性表是一種線性結(jié)構(gòu)。數(shù)據(jù)元素在線性表中的位置只取決于它們自己的序號，即數(shù)據(jù)元素之間的相對位置是線性的。非空線性表有如下一些結(jié)構(gòu)特征。① 有且只有一個根結(jié)點(diǎn)a1，它無前件；② 有且只有一個終端結(jié)點(diǎn)an，它無后件；③ 除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個前件，也有且只有一個后件。線性表中結(jié)點(diǎn)的個數(shù)n稱為線性表的長度。當(dāng)n=0時，稱為空表。（2）線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點(diǎn)。① 線性表中所有元素所占的存儲空間是連續(xù)的；② 線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。由此可以看出，在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面。（3）順序表的插入運(yùn)算設(shè)長度為n的線性表為（a1，a2，…，ai，…，an）現(xiàn)要在線性表的第i個元素ai之前插入一個新元素b，插入后得到長度