1、,DATA,10,65,865,姓名 學(xué)號 成績 班級 李紅 9761059 95 機97.6,數(shù)據(jù)結(jié)構(gòu),第2章 線性數(shù)據(jù)結(jié)構(gòu),2.1 基本概念 2.1.1 數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu) 2.1.2 算法的描述和評價 2.2 線性表 2.2.1 線性表的定義及操作 2.2.2 線性表的 順序存儲結(jié)構(gòu) 2.2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 2.2.4 循環(huán)鏈表和雙向鏈表 2.3 棧和隊列 2.3.1 棧 2.3.2 隊列,2.1 基 本 概 念,2.1.1 數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu) 現(xiàn)代數(shù)字計算機原是作為能快速地進行復(fù)雜、耗時計算的工具而發(fā)明的。隨著計算機的發(fā)展，在計算機的絕大多數(shù)應(yīng)用中，能夠存取、處理大量信息的能力卻被認(rèn)

2、為是計算機的首要特征，而它的計算能力在許多情況下已經(jīng)幾乎被忽略了。有鑒于此，常常把計算機稱作數(shù)據(jù)處理機。,什么是數(shù)據(jù)？數(shù)據(jù)就是信息的載體,它可以用計算機表示并加工?？梢钥闯觯瑪?shù)據(jù)這個概念本身是隨著計算機的發(fā)展而不斷擴展的概念。在計算機發(fā)展的初期，由于計算機主要用于數(shù)值計算，數(shù)據(jù)指的就是數(shù)值。計算機硬件和軟件技術(shù)的不斷發(fā)展，擴大了計算機的應(yīng)用領(lǐng)域，諸如字符、文字、表格、圖形、圖像、聲音等也屬于數(shù)據(jù)的范疇。,數(shù)據(jù)元素是數(shù)據(jù)集合中的一個個體，它是組成數(shù)據(jù)的基本單位。例如：全部學(xué)生的學(xué)籍登記卡組成學(xué)生的學(xué)籍?dāng)?shù)據(jù)，每個學(xué)生的學(xué)籍登記卡就是學(xué)籍?dāng)?shù)據(jù)的一個數(shù)據(jù)元素。 數(shù)據(jù)元素可以是一個數(shù)或字符串，也可以由若

3、干數(shù)據(jù)項組成(數(shù)據(jù)的最小單位)，在這種情況下，通常把數(shù)據(jù)元素稱為記錄。如表2-1所示的學(xué)生學(xué)籍登記表，在這個表中每一個學(xué)生的學(xué)籍登記卡作為一個數(shù)據(jù)元素，每一個元素由學(xué)號、姓名、性別、民族、籍貫、專業(yè)六個數(shù)據(jù)項組成。,表2-1 學(xué)生學(xué)籍登記表,什么是數(shù)據(jù)結(jié)構(gòu)？在任何問題中，構(gòu)成數(shù)據(jù)的數(shù)據(jù)元素并不是孤立存在的，它們之間存在著一定的關(guān)系以表達(dá)不同的事物及事物之間的聯(lián)系。所以簡單地說，數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)及數(shù)據(jù)元素之間關(guān)系的一門學(xué)科。它不僅是一般程序設(shè)計的基礎(chǔ)，而且是設(shè)計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。它包括三個方面的內(nèi)容： 數(shù)據(jù)的邏輯結(jié)構(gòu)。 數(shù)據(jù)的存儲結(jié)構(gòu)

4、。 數(shù)據(jù)的運算。,1. 數(shù)據(jù)的邏輯結(jié)構(gòu),2. 數(shù)據(jù)的存儲結(jié)構(gòu),3. 數(shù)據(jù)的運算： 檢索、排序、插入、刪除、修改等。,A . 線性結(jié)構(gòu),B . 非線性結(jié)構(gòu),A . 順序存儲,B . 鏈?zhǔn)酱鎯?線性表,棧,隊,樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個方面,反映數(shù)據(jù)元素之間的邏輯關(guān)系,數(shù)據(jù)元素在計算機內(nèi)部的組織方式,C . 散列結(jié)構(gòu)（散列表）,D . 索引結(jié)構(gòu)（索引表）,1. 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)元素之間的邏輯關(guān)系?？梢杂靡粋€二元組，給出其形式定義為 DataStructure =(D，R) 其中，D是組成數(shù)據(jù)的數(shù)據(jù)元素的有限集合，R是數(shù)據(jù)元素之間的關(guān)系集合。 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同

5、特性，數(shù)據(jù)結(jié)構(gòu)又可分為兩大類：線性數(shù)據(jù)結(jié)構(gòu)和非線性數(shù)據(jù)結(jié)構(gòu)。按照這種劃分原則，本書介紹的所有數(shù)據(jù)結(jié)構(gòu)如圖2-1所示。,圖2-1 數(shù)據(jù)結(jié)構(gòu)分類,2數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯上來描述數(shù)據(jù)元素之間的關(guān)系的，是獨立于計算機的。然而討論數(shù)據(jù)結(jié)構(gòu)的目的是為了在計算機中實現(xiàn)對它的處理。因此還需要研究數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計算機中表示，這就是數(shù)據(jù)的存儲結(jié)構(gòu)。 計算機的存儲器是由很多存儲單元組成的，每個存儲單元有惟一的地址。數(shù)據(jù)的存儲結(jié)構(gòu)要討論的就是數(shù)據(jù)結(jié)構(gòu)在計算機存儲器上的存儲映像方法。,實現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)到計算機存儲器的映像有多種不同的方式。一般來說，數(shù)據(jù)在存儲器中的存儲有四種基本的

6、映像方法。 (1) 順序存儲結(jié)構(gòu)。這種存儲方式主要用于線性數(shù)據(jù)結(jié)構(gòu)，就是把數(shù)據(jù)元素按某種順序放在一塊連續(xù)的存儲單元中。其特點是邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中，元素之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。 某些非線性數(shù)據(jù)結(jié)構(gòu)也可以采用順序方式存儲，例如完全二叉樹、多維數(shù)組等，具體方法將在后面介紹。,(2) 鏈?zhǔn)酱鎯Y(jié)構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)可以把邏輯上相鄰的兩個元素存放在物理上不相鄰的存儲單元中。即可用一組任意的存儲單元來存儲數(shù)據(jù)元素，這些存儲單元可以是連續(xù)的，也可以是不連續(xù)的。 鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點就是將存放每個數(shù)據(jù)元素的結(jié)點分為兩部分：一部分存放數(shù)據(jù)元素(稱為數(shù)據(jù)域),另一部分存放指示

7、存儲地址的指針(稱為指針域)，借助指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。,(3) 索引存儲結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素可以排成一個序列：R1、R2、R3、Rn ，每個數(shù)據(jù)元素Ri在序列里都有對應(yīng)的位置數(shù)據(jù)i，這就是元素的索引。索引存儲結(jié)構(gòu)就是通過數(shù)據(jù)元素的索引號i來確定數(shù)據(jù)元素Ri的存儲地址。一般索引存儲結(jié)構(gòu)的實現(xiàn)方法是建立附加的索引表，索引表里第i項的值就是第i個元素的存儲地址。,(4) 散列存儲結(jié)構(gòu)。這種存儲方法就是在數(shù)據(jù)元素與其在存儲器上的存儲位置之間建立一個映像關(guān)系F。根據(jù)這個映像關(guān)系F，已知某數(shù)據(jù)元素就可以得到它的存儲地址。即D=F(E)，這里E是要存放的數(shù)據(jù)元素，D是該數(shù)據(jù)元素的存儲位置。

8、可見，這種存儲結(jié)構(gòu)的關(guān)鍵是設(shè)計這個函數(shù)F。但函數(shù)F不可能解決數(shù)據(jù)存儲中的所有問題，還應(yīng)有一套意外事件的處理方法，它們共同實現(xiàn)數(shù)據(jù)的散列存儲結(jié)構(gòu)。本書第4章中介紹的哈希表，就是散列存儲結(jié)構(gòu)的一個實例。,3. 數(shù)據(jù)的運算 數(shù)據(jù)的運算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，每種數(shù)據(jù)結(jié)構(gòu)都有一個運算的集合。常用的運算有檢索、插入、刪除、更新、排序等。運算的具體實現(xiàn)要在存儲結(jié)構(gòu)上進行。 數(shù)據(jù)的運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面。討論任何一種數(shù)據(jù)結(jié)構(gòu)時都離不開對該結(jié)構(gòu)上的數(shù)據(jù)運算及實現(xiàn)算法的討論。,2.2 線 性 表,2.2.1 線性表的定義及操作 定義2-1 線性表(Linear-list)是n(n0)個數(shù)據(jù)元素的有限

9、序列。記為： (a1，a2, ., an) 其中，數(shù)據(jù)元素個數(shù)n稱為表的長度，n = 0時，稱此線性表為空表。,線性表的邏輯結(jié)構(gòu)：若線性表是非空表，則第一個元素a1無前趨，最后一個元素an無后繼，其它元素ai(1in)均只有一個直接前驅(qū)ai-1和一個直接后繼ai+1。 下面給出幾個線性表的例子： 例2-1 26個大寫的英文字母表：(A，B，C，.，Z) 例2-2 某校從1996年到2002年各種型號計算機擁有量的變化情況，可以用線性表給出： (200，220，250，300，400，700，1200),例2-3 某單位職工政治面貌登記表如表2-2所示，每個職工的情況為一條記錄，它由職工號、姓名

10、、性別、職稱、工齡、政治面貌六個數(shù)據(jù)項組成。 在表2-2中，一個數(shù)據(jù)元素由若干個數(shù)據(jù)項組成。在這種情況下，常把數(shù)據(jù)元素稱為記錄，含有大量記錄的線性表又稱為文件。,表2-2 職工政治面貌登記表,線性表的特點: 同一性。線性表中每個數(shù)據(jù)元素ai的具體含義，在不同情況下各不相同，它可以是一個數(shù)，或是一個符號，甚至是其它更復(fù)雜的信息。但在同一個線性表中的數(shù)據(jù)元素必須具有相同的特性(或者說具有相同的類型)。 有窮性。線性表中數(shù)據(jù)元素的個數(shù)是有限的。 有序性。若線性表是非空表，(a1，a2, ., an), ai-1領(lǐng)先于ai (1in) ，稱ai-1是ai的直接前驅(qū)元素, ai是ai-1的直接后繼元素。

11、除了第一個元素a1外,每個元素ai有且僅有一個被稱為其直接前驅(qū)的結(jié)點ai-1,除了最后一個元素an外,每個元素ai有且僅有一個被稱為其直接后繼的結(jié)點ai+1。這種位置上的有序性就是一種線性關(guān)系，所以線性表是一種線性結(jié)構(gòu)。,線性表是一個相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，它的長度可以根據(jù)需要增減，操作也比較靈活方便。線性表的基本操作有以下幾種： (1) INITIATE(L)。初始化操作，設(shè)定一個空的線性表L。 (2) LENGTH(L)。求表長，求出線性表L中數(shù)據(jù)元素個數(shù)。 (3) GET(L，i)。取元素函數(shù)，若1iLENGTH(L)， 則函數(shù)值為給定線性表L中第i個數(shù)據(jù)元素，否則為空元素NULL。,(4)

12、 PRIOR(L，elm)。求前趨函數(shù)，若elm的位序大于1，則函數(shù)值為elm的前趨，否則為空元素。 (5) NEXT(L，elm)。求后繼函數(shù)，若elm的位序小于LENGTH(L)，則函數(shù)值為elm的后繼，否則為空元素。 (6) LOCATE(L，x)。定位函數(shù)，返回元素x在線性表L中的位置。若L中有多個x，則只返回第一個x的位置，若在L中不存在x，則返回0。 (7) INSERT(L，i，x)。插入操作，若1iLENGTH(L)+1，則在線性表L中的第i個位置上插入元素x，運算結(jié)果使得線性表的長度增加1。否則空操作,(8) DELETE(L，i)。刪除操作，若1iLENGTH(L)，刪除給

13、定線性表L中的第i個數(shù)據(jù)元素，使得線性表的長度減1。否則空操作 (9) EMPTY(L)。判空表函數(shù)，若L為空表，則返回布爾值“true”，否則返回布爾值“false”。 對線性表還有一些更為復(fù)雜的操作，如將兩個線性表合并成一個線性表；把一個線性表拆分成兩個或兩個以上的線性表；重新復(fù)制一個線性表；對線性表中的元素按值的大小重新排序等。這些運算都可以通過上述基本運算來實現(xiàn)。,2.2.2 線性表的順序存儲結(jié)構(gòu) 在計算機內(nèi)可以用不同的方式來表示線性表，其中最簡單和最常用的方式是用一組地址連續(xù)的存儲單元依次存儲線性表中的元素。,線性表的順序存儲結(jié)構(gòu)就是將線性表的元素按其邏輯次序依次存放在一組地址連續(xù)的

14、存儲單元里。 (1) 設(shè)有線性表(a1，a2，.，an)，若1個數(shù)據(jù)元素只占1個存儲單元，則這種分配方式如圖2-2所示。 若用Loc表示某元素的地址，則線性表中第i個數(shù)據(jù)元素的存儲地址為： Loc(ai)= Loc(a1)+(i-1) 其中，Loc(a1)是線性表第一個數(shù)據(jù)元素的存儲地址，通常稱做線性表的起始地址或者基地址。,(2) 若1個數(shù)據(jù)元素占d個存儲單元，則有 Loc(ai)= Loc(a1)+(i-1)*d Loc(ai+1)= Loc(ai)+ d 可見，線性表中每個元素的存儲地址是該元素在表中序號i的線性函數(shù)。只要確定了線性表的起始地址和每個元素所占存儲單元的多少，就可以計算出任

15、一數(shù)據(jù)元素的存儲地址,從而實現(xiàn)對順序表中任一數(shù)據(jù)元素的隨機存取，所以線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。,圖2-2 線性表順序存儲結(jié)構(gòu)示意圖(設(shè)每個數(shù)據(jù)元素占有1個存儲單元),順序存儲結(jié)構(gòu)是以元素在計算機內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間相鄰的邏輯關(guān)系。 在C語言中，可用一維數(shù)組Vn來描述順序存儲結(jié)構(gòu)。因此,可以借助一維數(shù)組來描述順序表。除了用來存儲線性表的元素外,還應(yīng)該用一個變量來表示線性表的長度屬性。,注意：在C語言中數(shù)組的下標(biāo)是從0開始，即： Vn的有效范圍是從 V0Vn-1,線性表的順序存儲結(jié)構(gòu)兩種實現(xiàn)方法 (1)數(shù)組表示法：數(shù)組中的分量下標(biāo)即為元素在線性表中的序號

16、 #define maxlen 100 datatype elemmaxlen; int last; 其中， maxlen是線性表的最大長度，它可以根據(jù)實際需要而修改。 datatype抽象數(shù)據(jù)類型，可用int, float, double, char 或結(jié)構(gòu)體類型等代替如： typedef int datatype,數(shù)據(jù)域elem描述了線性表中數(shù)據(jù)元素占用的數(shù)組空間，線性表的各個元素a1，a2，an依次存放在一維數(shù)組elem的各個分量elem0，elem1，elemlast-1中。 數(shù)據(jù)域last表示線性表的當(dāng)前長度。,typedef定義類型,語言不僅提供了豐富的數(shù)據(jù)類型，而且還允許由用戶

17、自己定義類型說明符，也就是說允許由用戶為數(shù)據(jù)類型取 “別名”。類型定義符typedef即可用來完成此功能。 例如，有整型量a,b,其說明如下： int a,b;其中int是整型變量的類型說明符。 int的完整寫法為integer，為了增加程序的可讀性， 可把整型說明符用typedef定義為：typedef int INTEGER 例如： INTEGER a,b;它等效于： int a,b;,例如： typedef char NAME20; 表示NAME是字符數(shù)組類型，數(shù)組長度為20。然后可用NAME 說明變量，如： NAME a1,a2,s1,s2;完全等效于： char a120,a220,

18、s120,s220,2）將last與data封裝在一起，單獨定義一種順序表類型用結(jié)構(gòu)體建立, last與data作為該結(jié)構(gòu)體的成員項。 #define maxlen 100 typedef struct datatype elemmaxlen; int last; sqlisttp;,用變量方式定義兩個順序表L和P,sqlisttp L , P ;,L. last =2;,L.elem0=91;,L.elem1=82;,P. last =10;,P.elem0=93;,P.elem1=78;,結(jié)構(gòu)體,1、結(jié)構(gòu)體類型的定義 2、結(jié)構(gòu)體變量的定義及引用,結(jié)構(gòu)體類型的引入,問題：為了描述一個事物的不

19、同屬性，需要用到各種不同類型的數(shù)據(jù)，這 些數(shù)據(jù)彼此相關(guān)，形成一個有機的整體。 例如：一個教師的基本信息由姓名、性別、年齡、職稱、工資等幾項組合 而成。如何描述一個教師的情況呢？ 變量之間是相互獨立的，無任何聯(lián)系；而數(shù)組只能用來表示一批相同類型 的數(shù)據(jù)。因此，若用單個變量分別表示教師的姓名、性別、年齡等屬性， 則難以反映他們之間的內(nèi)在聯(lián)系；若用數(shù)組，則根本無法表示，因為姓 名、性別、年齡等不屬同一種數(shù)據(jù)類型。 C語言中用“結(jié)構(gòu)體”來描述由多個不同類型的數(shù)據(jù)組成的數(shù)據(jù)集合。相當(dāng)于 其他高級語言中的“記錄”.,表 教師信息登記表,1.結(jié)構(gòu)體類型的定義,與基本數(shù)據(jù)類型不同的是，結(jié)構(gòu)體是又一種構(gòu)造類型，

20、是由多個類型的數(shù)據(jù)成員組合而來的。因此該類型的具體內(nèi)容應(yīng)根據(jù)需要先定義，后使用。 可以定義如下結(jié)構(gòu)體類型來描述教師的基本情況： struct teacher /*struct 是關(guān)鍵字*/ char name30; /*內(nèi)是該類型的各成員*/ char sex; int age; char position10; float salary; ; /*語句末尾是“;” */ 該結(jié)構(gòu)體類型名為struct teacher，teacher 是該結(jié)構(gòu)體的標(biāo)識符；該類型包含有6個成員的數(shù)據(jù)項：name、 sex、 age、 position 和salary，其中每個成員項都有自己的類型。,可見，定義一種

21、新的結(jié)構(gòu)體類型的一般形式是： struct 結(jié)構(gòu)體類型名 成員類型 成員名； 成員類型 成員名； ； 其中，struct 是 關(guān)鍵字，結(jié)構(gòu)體類型名、結(jié)構(gòu)體成員名的命名規(guī)則同變量的命名規(guī)則一樣。,2.結(jié)構(gòu)體變量的定義及引用,經(jīng)以上定義后，結(jié)構(gòu)體類型struct teacher與系統(tǒng)定義的類型int、long、 float 等一樣，可以用它來定義該類型的變量、數(shù)組、函數(shù)等。 例 定義一個結(jié)構(gòu)體變量，用于存放一個教師的信息，然后將其輸出。,main() struct teacher char name30; char sex; int age; char position10; float sala

22、ry; ; struct teacher person; /*定義結(jié)構(gòu)體變量person*/ strcpy(,wang li); person.sex=f; /*給各成員賦值*/ person.age=30; strcpy(person.position,middle); person.salary=1600;,printf(n name sex age position salary); printf(n%10s %3c %5d %10s %8.2f,, person.sex,person.age,person.position,person.sa

23、lary); 分析： * 先定義結(jié)構(gòu)體類型，后定義結(jié)構(gòu)體變量。 * 對結(jié)構(gòu)體變量輸入輸出操作、或?qū)⒒绢愋偷臄?shù)據(jù)賦給結(jié)構(gòu)體變量時，需分別訪問各個基本類型的成員，不能整體賦值或輸入輸出。 如：printf(“%s%c%d%s%f”,person); 錯！ person=“l(fā)i li”,f, 24, “primary”,1000; 錯！,(一)所謂輸入輸出是以計算機主機為主體而言的 輸出:從計算機向外部輸出設(shè)備(顯示器,打印機) 輸出數(shù)據(jù)。 輸入:從輸入設(shè)備(鍵盤,鼠標(biāo),掃描儀)向計算機 輸入數(shù)據(jù)。,數(shù)據(jù)輸入輸出的概念及在C語言中的實現(xiàn),(二)C語言本身不提供輸入輸出語句,輸入和輸出操作是由C函數(shù)

24、庫中的函數(shù)來實現(xiàn)的。 例如: 字符輸入函數(shù): getchar 字符輸出函數(shù):putchar 格式輸入函數(shù): scanf 格式輸出函數(shù): printf 字符串輸入函數(shù):gets 字?jǐn)?shù)串輸出函數(shù):puts,數(shù)據(jù)輸入輸出的概念及在C語言中的實現(xiàn),(三)在使用系統(tǒng)庫函數(shù)時,要用預(yù)編譯命令“#include”將有關(guān)的“頭文件”包括到用戶源文件中。 例如：在調(diào)用標(biāo)準(zhǔn)輸入輸出庫函數(shù)時，文件開頭應(yīng)該有： #include “stdio.h” 或： #include ,頭文件,數(shù)據(jù)輸入輸出的概念及在C語言中的實現(xiàn),（一）字符輸出函數(shù) 一般形式：putchar（c） 函數(shù)作用：向終端輸出一個字符,字符型變量整型變

25、量,字符數(shù)據(jù)的輸入輸出,字符數(shù)據(jù)的輸入輸出,例4.1 輸出單個字符。#includevoid main()char a,b,c;a=B;b=O;c=Y;putchar(a);putchar(b);putchar(c);putchar(n);,運行結(jié)果：BOY,putchar(a);putchar(n);putchar(b);putchar(n);putchar(c);putchar(n);,運行結(jié)果：B O Y,字符數(shù)據(jù)的輸入輸出,（二）字符輸入函數(shù) 一般形式：getchar（） 函數(shù)作用：從終端（或系統(tǒng)隱含指定的輸入設(shè)備）輸入一個字符。 函數(shù)值： 從輸入設(shè)備得到的字符。,字符數(shù)據(jù)的輸入輸出,

26、例4.2 輸入單個字符。#includevoid main() char c; c=getchar(); putchar(c); putchar(n);,格式輸入與輸出,（一）格式輸出函數(shù) 函數(shù)作用：向終端（或系統(tǒng)隱含指定的輸出設(shè)備）輸出若干個任意類型的數(shù)據(jù)。 一般格式：printf（格式控制，輸出表列）,%d:以帶符號的十進制形式輸出整數(shù) %o:以八進制無符號形式輸出整數(shù) %x:以十六進制無符號形式輸出整數(shù) To be continued,格式輸入與輸出,%u:以無符號十進制形式輸出整數(shù) %c:以字符形式輸出，只輸出一個字符 %s:輸出字符串 %f:以小數(shù)形式輸出單，雙精度數(shù)，隱含輸出六位小

27、數(shù) %e:以指數(shù)形式輸出實數(shù) %g:選用%f或%e格式中輸出寬度較短的一種格式，不輸 出無意義的0,格式輸入與輸出,格式符。用來輸出十進制整數(shù)。 幾種用法： :按十進制整型數(shù)據(jù)的實際長度輸出。 :為指定的輸出字段的寬度。如果數(shù)據(jù)的位數(shù)小于， 則左端補以空格，若大于，則按實際位數(shù)輸出。 例: （，）; 若，則輸出結(jié)果為 ，,格式輸入與輸出,(2)格式符，用來輸出一個字符。 如：d； （，d）； 輸出字符.,格式輸入與輸出,(3)s格式符 輸出字符串. 。例如： （，） 輸出字符串“”（不包括雙引號）。 %ms，輸出的字符串占m列，若串長大于m，則全部輸出，若串長 小于m，則左補空格。,格式輸入與

28、輸出,(4)格式符。用來以小數(shù)形式輸出實數(shù)（包括單雙精度） 有以下幾種用法： 。不指定字段寬度，由系統(tǒng)自動指定字段寬度，使整數(shù) 部分全部輸出，并輸出位小數(shù)。應(yīng)當(dāng)注意，在輸出的數(shù)字中 并非全部數(shù)字都是有效數(shù)字。單精度實數(shù)的有效位數(shù)一般為位。 .。指定輸出的數(shù)據(jù)共占列，其中有位小數(shù)。如果 數(shù)值長度小于，則左端補空格。,格式輸入與輸出,（一）.格式輸入函數(shù) 函數(shù)作用：按照變量在內(nèi)存的地址將變量值存 進去。 一般格式：scanf（格式控制，地址表列）,同printf函數(shù),是由若干個地址組成的表列，可以是變量的地址，或字符串的首地址,格式輸入與輸出,例 用scanf函數(shù)輸入數(shù)據(jù)。#includevoid

29、 main()int a,b,c;scanf(“%d%d%d”,a在內(nèi)存中的地址 int last; /* last=length */ sqlisttp; void insert(sqlisttp *v, int i, int x) int k; if (iv- last+1) /* 非法位置*/ printf( 插入位置不合適！n );,else if (v-last=maxlen) /* 表空間溢出*/ printf( 線性表已滿！n ); else for( k = v- last-1; k = i-1; k- ) v- elemk+1 = v- elemk; v- elemi-1 =

30、 x; /* 插入x */ v- last+; ,void main( ) sqlisttp lp; int i, a, j, data; for (i=0; i maxlen; i+) scanf( %d, ,線性表中所有數(shù)據(jù)：12，23，56，21，8，10,插入的數(shù)據(jù)元素的位置、值：1，28,在上述算法中v為何設(shè)計成指針參數(shù)? C語言中參數(shù)傳遞是”值”傳遞方式,若參數(shù)設(shè)計成sqlisttp v這種類型,在調(diào)用 函數(shù)時,會把實參的值復(fù)制到系統(tǒng)為形參開辟的臨時單元中,然后對形參進 行處理,形參是局部變量,當(dāng)該函數(shù)執(zhí)行完,返回主調(diào)函數(shù)后,形參即被釋放, 對形參所作的任何修改都不可能反映到主調(diào)函

31、數(shù)中。而把參數(shù)設(shè)計成指向 線性表的指針后,在調(diào)用時傳給形參的是指向線性表的指針即線性表的地 址,在被調(diào)函數(shù)中,可以通過這個地址直接對地址中存儲的線性表的各項的 值進行修改。在主調(diào)函數(shù)中訪問線性表時仍然是對相同的地址空間進行訪 問,當(dāng)然這樣的修改就可以反映到主調(diào)函數(shù)中。,算法2-2 線性表的刪除算法。 已知線性表的當(dāng)前狀態(tài)是(a1，a2，ai-1，ai，ai+1，an)，若要刪除第i個元素ai，則線性表成為(a1，a2，ai-1，ai+1，an)。 具體實施步驟為： (1) 若i值合法，則將第i+1至第n個位置上的元素依次向前移動一個存儲單位； (2) 將線性表的長度減1。,.,a2,a1,al

32、ast,.,ai+1,ai,0,1,i-1,i,last-1,刪除線性表的第i個元素，后面所有元素前移。,ai-1,.,a2,a1,alast,ai+1,ai,刪除 結(jié)點ai,ai+1,alast,#define maxlen 100 typedef struct int elemmaxlen; int last; sqlisttp; void delete(sqlisttp *v, int i) int k; if (iv- last) printf( 刪除位置不合適！n );,else for( k = i; k last-1; k+ ) v- elemk-1 = v- elemk; v-

33、 last-; ,從上述算法中不難看出，當(dāng)在順序存儲結(jié)構(gòu)的線性表中某個位置上插入或刪除一個數(shù)據(jù)元素時，其時間主要耗費在移動元素上，而移動元素的個數(shù)取決于插入或刪除元素的位置。,當(dāng)線性表的元素很多，且每個元素的數(shù)據(jù)項較多時， 花費在移動元素上的時間會很長。 一般情況下，線性表的順序存儲結(jié)構(gòu)適合于表中元素 變動較少的線性表。,2.2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 上節(jié)介紹的線性表的順序存儲結(jié)構(gòu)，它的特點是邏輯關(guān)系上相鄰的兩個元素在物理位置上也是相鄰的。因此，可以隨機存取表中任一元素，它的存儲位置可用一個簡單、直觀的公式來表示。 然而，這種存儲結(jié)構(gòu)有三個缺點：第一，在作插入或刪除操作時，需移動大量元素；

34、第二，在給長度變化較大的線性表預(yù)先分配空間時，必須按最大空間分配，使存儲空間不能得到充分利用；為克服線性表順序存儲結(jié)構(gòu)的缺點，引進了另一種存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)。,1鏈?zhǔn)酱鎯Y(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。這樣，邏輯上相鄰的元素在物理位置上就不一定是相鄰的，為了能體現(xiàn)元素之間的邏輯關(guān)系，就必須在存儲每個元素ai的同時，存儲其直接后繼元素的存儲位置。這兩部分信息組成一個數(shù)據(jù)元素的存儲映像，稱為結(jié)點。這時，結(jié)點至少包括兩個域，一個域存放該元素的數(shù)據(jù)，稱為數(shù)據(jù)域(data)；另一個域存放后繼結(jié)點在存儲器中的地址，稱為指

35、針域或鏈域(next)。,一般情況下，鏈表中每個結(jié)點可以包含若干個數(shù)據(jù)域和指針域。若每個結(jié)點中只有一個指針域，則稱此鏈表為線性鏈表或單鏈表，否則被稱為多鏈表。,data,next,鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點: 存儲空間不一定連續(xù); 邏輯關(guān)系是由指針來體現(xiàn)的; 邏輯上相鄰,物理上不一定相鄰; 非隨機存儲取(順序存取),例2-4 設(shè)有線性表由動物名組成：(cat, horse, monkey, elephant, pig, panda)。 它的物理狀態(tài)如圖2-3所示。 當(dāng)鏈表采用圖2-3來表示時，邏輯上的順序不易觀察，所以經(jīng)常把鏈表用圖2-4所示的邏輯狀態(tài)來表示。,圖2-4 線性鏈表的邏輯狀態(tài)示意圖,圖2

36、-3 線性鏈表的物理狀態(tài)示意圖,在圖2-4中，指針域的值用箭頭代替了，線性鏈表結(jié)點的相鄰關(guān)系用箭頭來指示，邏輯結(jié)構(gòu)的表示非常形象、清晰。整個鏈表的存取需從頭指針開始進行，依次順著每個結(jié)點的指針域next找到線性表的各個元素，直到next域為空為止。 在此單鏈表中，head是指向單鏈表中第一個結(jié)點的指針，我們稱之為頭指針；最后一個元素panda所在結(jié)點不存在后繼，因而其指針域為“空”(用NULL或 表示)。,通常，我們在單鏈表第一個元素所在的結(jié)點之前附設(shè)一個結(jié)點頭結(jié)點，頭結(jié)點的指針域存儲第一個元素所在結(jié)點的存儲位置；頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，也可以存儲如線性表的長度等附加信息。若線性表為

37、空表，則頭結(jié)點的指針域為“空”，如圖2-5所示。 頭結(jié)點指針:指向頭結(jié)點的指針,圖2-5 帶頭結(jié)點的單鏈表,單鏈?zhǔn)酱鎯Y(jié)構(gòu)的C語言描述為： struct node int data; struct node *next; ; typedef struct node NODE;,NODE是結(jié)點類型；,typedef struct node int data; struct node *next; NODE;,定義結(jié)點類型的變量 NODE L L.data=x; L.next=NULL;,定義指向Node類型結(jié)點的指針變量 NODE *p p-data=y；p-next=NULL；,3線性鏈表的運

38、算 線性鏈表是線性表的鏈?zhǔn)酱鎯Ρ硎荆詫€性鏈表的運算與前面所介紹的對線性表的運算相同，只是相應(yīng)的算法與順序存儲的線性表有所不同。,對鏈表操作時，最基本的操作為插入、刪除運算。在討論插入、刪除操作之前，首先要解決插入時的新結(jié)點從何處取出，刪除后的結(jié)點又往何處送的問題。在采用鏈接分配時，總存在一個可利用的內(nèi)存空間稱為可利用空間表。這樣，每當(dāng)要調(diào)用新結(jié)點時就到這個可利用空間表里去取，刪除時就把結(jié)點歸還給這個可利用空間表。,在C語言的編程實現(xiàn)時，申請與釋放一結(jié)點對應(yīng)于C語言中兩個標(biāo)準(zhǔn)函數(shù)malloc(sizeof(NODE)和free(p)。 (1) malloc 是從可利用空間表中調(diào)用一新結(jié)點，

39、并返回該結(jié)點的地址。,庫函數(shù)提供動態(tài)地開辟和釋放存儲單元的函數(shù)： malloc函數(shù) 其函數(shù)原型為void *malloc(unsigned int size);其作用是在內(nèi)存的 動態(tài)存儲區(qū)中分配一個長度為size的連續(xù)空間。此函數(shù)的值（即 “返回值”）是一個指向分配域起始地址的指針（類型為 void）。如果此函數(shù)未能成功地執(zhí)行（例如內(nèi)存空間不足），則 返回空指針(NULL)。,struct node int data; struct node *next; ; typedef struct node NODE;,NODE *p;,p= (NODE *) malloc(sizeof(NODE),

40、(2) free(p)將p指向的結(jié)點歸還給可利用空間表。,申請分配能存放一個鏈表結(jié)點NODE類型數(shù)據(jù)的存儲空間，并返回這個存儲空間的首地址，即指針型變量p指向新申請的結(jié)點，為方便起見，以后把指針型變量p所指向的結(jié)點稱為p結(jié)點。,free函數(shù) 其函數(shù)原型為void free（void *p）;其作用是釋放由指向 的內(nèi)存區(qū)，使這部分內(nèi)存區(qū)能被其他變量使用。是最近一次 調(diào)用malloc函數(shù)時返回的值。free函數(shù)無返回值。,結(jié)點的表示,100,218,165,333,p,p=? p-data=? p-next=? (p-next)-data=? (p-next)-next=?,1)帶頭結(jié)點單鏈表的初

41、始化 初始化帶頭結(jié)點的單鏈表就是建立一個只有頭結(jié)點的空鏈表。 NODE* Initlist (NODE *head) head=(NODE *)malloc (sizeof(NODE); head-next=NULL; return (head); ,2) 單鏈表的查找 按序號查找 在鏈表中，即使知道被訪問結(jié)點的序號i,也不能像順序表中那樣直接按 序號i訪問結(jié)點，實現(xiàn)隨機存取，而只能從鏈表的頭指針出發(fā)，沿結(jié)點 的指針域逐個往后查找，直至搜索到第i個結(jié)點為止。 設(shè)帶頭結(jié)點的單鏈表的長度為n，要查找表中第i個結(jié)點，則需要從單鏈 表的頭指針head出發(fā)，從頭結(jié)點開始順著指針域掃描，用指針p指向當(dāng) 前

42、掃描到的結(jié)點，初值指向第一個結(jié)點，用counter做計數(shù)器，累計當(dāng) 前掃描過的結(jié)點數(shù)（初值為1，把第一個結(jié)點看做是第1個結(jié)點），當(dāng) counter=i時，指針p所指結(jié)點就是要找的第i個結(jié)點。,N ODE * get( NODE *head, int i) NODE *p; int counter = 1 ; p = head- next; /* 從第一個結(jié)點開始掃描 */ while ( p!=NULL) /* 已掃描結(jié)點計數(shù)*/,/*在帶頭結(jié)點的單鏈表中找出第i個元素所在結(jié)點，若找到，返回該結(jié)點的存儲位置p，否則返回 NULL */, if ( p!= NULL) /* 找不到, in或i=

43、0 */ ,注意需事先定義NULL的具體數(shù)值，比如： #define NULL 0,按值查找 按值查找是指在單鏈表中查找是否有結(jié)點的值等于給定 值x的結(jié)點，若有的話，則返回首次找到其值為x的結(jié)點 的存儲位置，否則返回NULL。查找過程從第一個節(jié)點開 始，順著指針域?qū)⒔Y(jié)點的值和給定值x作比較。算法如 下： int FoundList (NODE *head, int x ) /*在帶頭結(jié)點的單鏈表中查找其值為x的結(jié)點，若找到，返回該結(jié)點在單鏈表中的序號，即是第幾個結(jié)點，否則返回0*/, NODE *p; int pos=1; p=head-next; while (p!=NULL) ,3) 單鏈

44、表的插入 設(shè)有線性表(a1，a2，.，ai-1，ai，.，an)，用帶頭結(jié) 點的單鏈表存儲，頭指針為head，要求將值為x的元 素插入到第i(1in+1)個位置上，即插入到ai-1與ai 之間，線性表變?yōu)?a1，a2，ai-1，x，ai，an) 插入前單鏈表的邏輯狀態(tài)如圖2-6所示。,圖2-6 帶頭結(jié)點單鏈表的邏輯狀態(tài),為插入數(shù)據(jù)元素x， (1) 首先要生成一個數(shù)據(jù)域為x的新結(jié)點s； (2) 然后確定插入位置，即找到ai之前的元素 ai-1，并使指針p指向之； (3) 最后改變鏈接，將x插在ai-1與ai之間，修改結(jié)點p和結(jié)點s的指針域。即 s-next = p-next；p-next = s

45、。 插入結(jié)點s后單鏈表的邏輯狀態(tài)如圖2-7所示。,圖2-7 在單鏈表中插入結(jié)點S,算法2-4 void insert(NODE *head, int i, int x) NODE *p, *s; int j=0; p = head; while ( p!=NULL) ,if (p=NULL) | (j！= i-1) printf( i值不合法 n); /* 找不到,in+1或i data = x; /* */ s - next =NULL; s - next = p - next; /* */ p - next = s; /* */ ,設(shè)有線性表(a1，a2，.，ai-1，ai，ai+1，.，

46、an)，用帶頭結(jié)點的單鏈表存儲，刪除第i(1in)個元素ai所在的結(jié)點 刪除前的邏輯狀態(tài)如圖2-8所示。 為刪除數(shù)據(jù)元素x,(1) 首先要搜索單鏈表以找到指定刪除結(jié)點的前趨結(jié)點(假設(shè)為p)； (2) 然后改變鏈接，即只要將待刪除結(jié)點的指針域內(nèi)容賦予p結(jié)點的指針域即可。,4) 單鏈表的刪除,圖2-8 帶頭結(jié)點的單鏈表,圖2-9 在單鏈表中刪除一個結(jié)點,算法2-5 void delete(NODE *head, int i) NODE *p, *s; int j=0; p = head; while ( p-next != NULL) ,if (p-next = NULL) | (j != i-1

47、) printf(“i值不合法 n”); /* 找不到,in或i next; p - next = s - next; free(s); ,5) 動態(tài)建立單鏈表的算法,輸入線性表元素,以單鏈?zhǔn)酱鎯Ψ绞酱鎯?即創(chuàng)建單鏈表 方法一:正向建立單鏈表（尾插法） 思想：從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù) 據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表尾結(jié) 點之后，直至讀入結(jié)束標(biāo)志為止，即從第一個元素結(jié)點逐個創(chuàng)建 各個元素結(jié)點,每次都是鏈接到當(dāng)前鏈表的最后。 創(chuàng)建頭結(jié)點: head = (NODE *)malloc(sizeof(NODE); head - next = NULL;

48、p = head; 讀入一個元素,鏈入其中: s = (NODE *)malloc(sizeof(NODE); scanf (,head,p,s,算法2-7 NODE * creatlink2( ) NODE *head, *p, *s; int num; head = (NODE *)malloc(sizeof(NODE); /*生成頭結(jié)點*/ scanf(“%d”, /* 頭指針=尾指針 */ while (num!=0) /* 輸入為0為輸入結(jié)束符*/, s = (NODE *)malloc(sizeof(NODE);/*生成新結(jié)點*/ s - data = num; /* 新結(jié)點上填入

49、輸入值 */ p - next = s; /* 新結(jié)點*s插入到尾結(jié)點*p之后 */ p = s; /* 尾指針p指向新的表尾 */ scanf(“%d”, /* 返回單鏈表頭指針 */ ,方法二：反向建立鏈表（頭插法） 思想：若線性表的元素已順序存放在一維數(shù)組AN 中，建表方法是從線性表的最后一個元素開始，從后向 前依次插入到當(dāng)前鏈表的第一個結(jié)點之前,頭結(jié)點之 后。,創(chuàng)建頭結(jié)點: head = (NODE *)malloc(sizeof(NODE); head - next = NULL; 讀入一個元素,鏈入其中: s = (NODE *)malloc(sizeof(NODE); s - d

50、ata = Ai; s - next = head - next ; head - next = s;,算法2-6 #define N m /* m為鏈表中數(shù)據(jù)元素的個數(shù),如m=10 */ int AN; NODE * creatlink1( ) NODE *head, *s; int i; head = (NODE *)malloc(sizeof(NODE); /*生成頭結(jié)點*/ head - next = NULL; /* 置空表 */ for(i=N-1; i=0; i-) /* 插入10個數(shù)據(jù) */, s = (NODE *)malloc(sizeof(NODE); /*生成新結(jié)點*/

51、 s - data = Ai; /*將輸入數(shù)據(jù)放入新結(jié)點數(shù)據(jù)域*/ s - next = head - next; /*新結(jié)點與原首結(jié)點鏈接*/ head - next = s; /* 將新結(jié)點插入到表頭 */ return head; /* 返回單鏈表頭指針 */ ,4. 線性鏈表算法示例 例2-5 求不帶頭結(jié)點的頭指針為head的單鏈表中的結(jié)點數(shù)目。 解： int length(NODE *head) NODE *p; int j; p = head; j = 0;,while ( p != NULL ) p = p - next; j+; return j; ,例2-6 設(shè)計算法：將一個

52、帶頭結(jié)點的單鏈表A分解為兩個帶頭結(jié)點的單鏈表A和B，使得A表中含有原表中序號為奇數(shù)的元素，B表中含有原表中序號為偶數(shù)的元素，且保持其相對順序。,解： void disA(NODE *A, NODE *B) NODE *r, *p, *q; B = (NODE *)malloc(sizeof(NODE); /*建立單鏈表B的頭結(jié)點*/ r = B; p = A-next; while (p!=NULL) p-next = q-next; r-next = q; r = q; p = p-next; r-next = NULL; p-next = NULL; ,例2-7 已知兩個不帶頭結(jié)點的單鏈表

53、A、B分別表示兩個集合，其元素遞增有序。試設(shè)計算法求出A與B的交集C。要求C另外開辟存儲空間，并同樣以元素值遞增的帶頭結(jié)點的單鏈表形式存儲。,解： void intersectionset(NODE *A, NODE *B, NODE *C) NODE *r, *p, *q, *s; C = (NODE *)malloc(sizeof(NODE); r = C; p = A; q = B; while (p!=NULL) else if (p-data q-data) q = q-next; else if (p-data = q-data) s = (NODE *)malloc(sizeof

54、(NODE); s-data = p-data;,r-next = s; r = s; p = p-next; q = q-next; r-next = NULL; ,2.2.4 循環(huán)鏈表和雙向鏈表 1. 循環(huán)鏈表 如果鏈表最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)，這樣的鏈表稱為循環(huán)鏈表。 這樣，從表中任一結(jié)點出發(fā)均可找到表中其它結(jié)點，其邏輯狀態(tài)圖如圖2-10。,圖2-10 循環(huán)單鏈表,與單鏈表比較，循環(huán)鏈表有以下特點： (1) 在循環(huán)單鏈表中，從表中任何一個結(jié)點出發(fā)都能訪問到其它所有的結(jié)點；而單鏈表一般把頭指針作為入口點，從某一結(jié)點出發(fā)，只能訪問到其所有后繼結(jié)點。 (2) 循環(huán)單鏈

55、表的空表判定條件是： head-next=head。,循環(huán)鏈表的存儲結(jié)構(gòu)的C語言描述為：同單鏈?zhǔn)?完全一樣 struct node int data; struct node *next; ; typedef struct node NODE;,線性表的各個運算在循環(huán)單鏈存儲結(jié)構(gòu)下的虛擬實現(xiàn) 基本與單鏈?zhǔn)酱鎯Y(jié)構(gòu)的相同,區(qū)別只在于最后一個結(jié)點的判斷（即循環(huán)的條件不同），算法中的循環(huán)條件不是p!= NULL或p-next!=NULL，而是p!= head或p-next!=head 。但利用循環(huán)鏈表實現(xiàn)某些運算較單鏈表方便（從某個結(jié)點出發(fā)能求出它的直接前驅(qū)，而單鏈表是不行的，只能從頭出發(fā)）。,2雙

56、向鏈表 前面討論的鏈?zhǔn)酱鎯Y(jié)構(gòu)中只有一個指示直接后繼的指針域，所以從某結(jié)點出發(fā)只能順指針往后查找其它結(jié)點。若要查找結(jié)點的直接前趨，則應(yīng)從頭指針出發(fā)(或在循環(huán)單鏈表中從p結(jié)點出發(fā))一直往后找，直到結(jié)點q滿足q-next=p，那么q是p的前趨結(jié)點。為克服鏈表這種單向性的缺點，為有更大的靈活性來操作線性鏈表，可采用雙向鏈表存儲結(jié)構(gòu)。,雙向鏈表存儲結(jié)構(gòu) 方式:用任意存儲空間單元來存放線性表的各個元素,為了能體現(xiàn)元素之間的前驅(qū)和后繼邏輯關(guān)系,在存放每個元素的同時,也存放其前驅(qū)和后繼元素的信息(即前驅(qū)和后繼元素的存儲地址),即用兩個指針來表示元素之間的前驅(qū)和后繼邏輯關(guān)系,在每個結(jié)點上增加另一個指向線性表中

57、每個元素的前趨結(jié) 點的指針域prior，就得到雙向鏈表。其結(jié)點的結(jié)構(gòu)如圖2-11 所示。 其中，prior是指向前趨結(jié)點的指針域；data是數(shù)據(jù)域； next是指向后繼結(jié)點的指針域。,圖2-11 雙向鏈表結(jié)點結(jié)構(gòu),圖2-12 帶頭結(jié)點的空雙向鏈表,雙向鏈表的幾種不同狀態(tài)如圖2-12，圖2-13所示。,圖2-13 帶頭結(jié)點的非空雙向鏈表,在圖2-13中的非空雙向鏈表中，設(shè)p是指向鏈表中任一結(jié)點的指針，則有： p-next-prior = p-prior-next = p 這個等式反映了這種鏈表的本質(zhì)，在此鏈表上進行插入或刪除操作是十分方便的。雙向鏈表雖然多花了存儲空間，但卻換得了操作上的更大靈活性。 雙向鏈表存儲結(jié)構(gòu)C語言實現(xiàn) struct dnode int data; struct dnode *next; struct dnode *prior; ; typedef struct dnode DNODE;,雙向鏈表的運算如LENGTH(Head)，GET(Head, i)，LOCATE(Head, x)等操作，僅涉及一個方向的