數(shù)據(jù)結(jié)構(gòu)第1章緒論

1、第一章第一章 緒論緒論1. 了解數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容了解數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容2. .掌握數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念掌握數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念3. 掌握算法、算法的時間復雜度及其分析的掌握算法、算法的時間復雜度及其分析的簡易方法簡易方法 教學目標教學目標1.1 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容1.2 基本概念和術(shù)語基本概念和術(shù)語1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn) 1.4 算法與算法分析算法與算法分析教學內(nèi)容教學內(nèi)容&N.N.沃思（沃思（Niklaus Wirth)Niklaus Wirth)教授提出：教授提出： 程序程序=算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)&

2、計算機的主要用途：計算機的主要用途： 早期：早期： 主要用于數(shù)值計算。主要用于數(shù)值計算。 后來：后來： 處理逐漸擴大到非數(shù)值計算領(lǐng)域，能處理處理逐漸擴大到非數(shù)值計算領(lǐng)域，能處理多種復雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)多種復雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)1.1 1.1 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容例：例： 例例1 線性結(jié)構(gòu)線性結(jié)構(gòu) 學學 號號 姓姓 名名 數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu) 系系統(tǒng)統(tǒng)結(jié)結(jié)構(gòu)構(gòu) 數(shù)數(shù)學學 1 20001 劉劉揚揚 89 69 67 2 20002 李李平平 70 83 89 3 20003 王王方方 86 81 78 4 20004 張張策策 69 69 78 5 20005 董董立立

3、79 89 68 6 20006 謝謝平平 80 88 79 7 20007 高高月月 81 81 80 8 20008 劉劉平平 89 85 87 9 20009 好好園園 86 80 84 例例2 樹型結(jié)構(gòu)：樹型結(jié)構(gòu)： 學校組織形式學校組織形式學校學校計算機學院計算機學院理學院理學院。外語院外語院計算機系計算機系信管系信管系數(shù)學系數(shù)學系 物理系物理系 化學系化學系英語系英語系 公外公外張三張三李四。李四。李洪。李洪。王五王五吳梅吳梅AFCBDE例例3 圖型結(jié)構(gòu)：圖型結(jié)構(gòu)： 城市交通道路圖城市交通道路圖4550683025801004070&求解非數(shù)值計算的問題：求解非數(shù)值計算的問題

4、： 設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)及相應的算法設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)及相應的算法 即：首先要考慮即：首先要考慮對相關(guān)的各種信息如何表示、組織對相關(guān)的各種信息如何表示、組織和存儲？和存儲？ 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容為：數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容為： 研究非數(shù)值計算的程序設(shè)計問題中計算機的研究非數(shù)值計算的程序設(shè)計問題中計算機的操作操作對象對象以及它們之間的以及它們之間的關(guān)系和操作關(guān)系和操作。 三要素：操作對象、關(guān)系、操作（算法）三要素：操作對象、關(guān)系、操作（算法）是數(shù)據(jù)的基本單位，是數(shù)據(jù)的基本單位，通常作為一個整體來處理。通常作為一個整體來處理。data item)：組成數(shù)據(jù)元素的、有獨立含組成數(shù)據(jù)元素的、有獨立含義的義的

5、最小單位最小單位，也稱域，也稱域( (field)field)。四者之間的關(guān)系：四者之間的關(guān)系： 數(shù)據(jù)數(shù)據(jù) 數(shù)據(jù)對象數(shù)據(jù)對象 數(shù)據(jù)元素數(shù)據(jù)元素 數(shù)據(jù)項數(shù)據(jù)項例：例： 學生表學生表 個人記錄個人記錄 學號、姓名學號、姓名是相互之間存在一種或多是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。種特定關(guān)系的數(shù)據(jù)元素的集合。 邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 從解決問題的需要出發(fā)，為實現(xiàn)必要的功能所建立的數(shù)據(jù)模從解決問題的需要出發(fā)，為實現(xiàn)必要的功能所建立的數(shù)據(jù)模型。用于描述數(shù)據(jù)元素之間的邏輯關(guān)系，與數(shù)據(jù)的存儲無關(guān)。型。用于描述數(shù)據(jù)元素之間的邏輯關(guān)系，與數(shù)據(jù)的存儲無關(guān)。 物理（存儲）結(jié)構(gòu)：物理（存儲）結(jié)構(gòu)： 數(shù)據(jù)元

6、素及其關(guān)系在計算機存儲器中的存儲方式。數(shù)據(jù)元素及其關(guān)系在計算機存儲器中的存儲方式。即數(shù)據(jù)邏即數(shù)據(jù)邏輯結(jié)構(gòu)的物理存儲方式。輯結(jié)構(gòu)的物理存儲方式。劃分方法一劃分方法一 （1 1）線性結(jié)構(gòu)）線性結(jié)構(gòu)- 有且僅有一個開始和一個終端結(jié)點，并且有且僅有一個開始和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個后繼。所有結(jié)點都最多只有一個直接前趨和一個后繼。 例如：線性表、棧、隊列、串例如：線性表、棧、隊列、串 （2 2）非線性結(jié)構(gòu)）非線性結(jié)構(gòu)- 一個結(jié)點可能有多個直接前趨和直接后繼。一個結(jié)點可能有多個直接前趨和直接后繼。 例如：樹、圖例如：樹、圖邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)一對一，如線性表、棧、

7、隊列一對一，如線性表、棧、隊列樹形結(jié)構(gòu)樹形結(jié)構(gòu)一對多，如樹一對多，如樹集合集合數(shù)據(jù)元素間除數(shù)據(jù)元素間除“同屬于一個集合同屬于一個集合”外，無其它關(guān)系外，無其它關(guān)系圖形結(jié)構(gòu)圖形結(jié)構(gòu)多對多，如圖多對多，如圖邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)劃分方法二劃分方法二數(shù)據(jù)結(jié)構(gòu)示例：數(shù)據(jù)結(jié)構(gòu)示例： 工號工號 姓名姓名 性別性別 出生年月出生年月 職務(wù)職務(wù) 班排班排 01 張三張三 男男 1972.3.20 連長連長 二連二連 02 李四李四 男男 1978.6.14 排長排長 一排一排 03 王五王五 男男 1974.12.7 排長排長 二排二排 04 趙一趙一 女女 1982.8.5 排長排長 三排三排 05 趙二趙二 男

8、男 1969.8.15 士兵士兵 一排一排 06 趙七趙七 男男 1985.4.1 士兵士兵 一排一排 07 趙八趙八 男男 1982.6.28 士兵士兵 二排二排 08 錢一錢一 男男 1977.317 士兵士兵 二排二排 09 錢二錢二 男男 1985.10.12 士兵士兵 二排二排 10 錢三錢三 女女 1986.7.5 士兵士兵 三排三排 工號工號 姓名姓名 性別性別 出生年月出生年月 職務(wù)職務(wù) 班排班排 01 張三張三 男男 1972.3.20 連長連長 二連二連 02 李四李四 男男 1978.6.14 排長排長 一排一排 03 王五王五 男男 1974.12.7 排長排長 二排二

9、排 04 趙一趙一 女女 1982.8.5 排長排長 三排三排 05 趙二趙二 男男 1969.8.15 士兵士兵 一排一排 06 趙七趙七 男男 1985.4.1 士兵士兵 一排一排 07 趙八趙八 男男 1982.6.28 士兵士兵 二排二排 08 錢一錢一 男男 1977.317 士兵士兵 二排二排 09 錢二錢二 男男 1985.10.12 士兵士兵 二排二排 10 錢三錢三 女女 1986.7.5 士兵士兵 三排三排定義：定義：data_structure=( D , S ) D= 01,02,03,04,05,06,07,08,09,10S= 0102030405060708091

10、0集合集合不考慮該表中記錄之間的任何次序不考慮該表中記錄之間的任何次序定義：定義：data_structure=( D , S ) D= 01,02,03,04,05,06,07,08,09,10S=, , 05010308020704060910線性結(jié)構(gòu)線性結(jié)構(gòu)考慮按人員出生年月從大到小排列組織數(shù)據(jù)考慮按人員出生年月從大到小排列組織數(shù)據(jù) 工號工號 姓名姓名 性別性別 出生年月出生年月 職務(wù)職務(wù) 班排班排 01 張三張三 男男 1972.3.20 連長連長 二連二連 02 李四李四 男男 1978.6.14 排長排長 一排一排 03 王五王五 男男 1974.12.7 排長排長 二排二排 04

11、 趙一趙一 女女 1982.8.5 排長排長 三排三排 05 趙二趙二 男男 1969.8.15 士兵士兵 一排一排 06 趙七趙七 男男 1985.4.1 士兵士兵 一排一排 07 趙八趙八 男男 1982.6.28 士兵士兵 二排二排 08 錢一錢一 男男 1977.317 士兵士兵 二排二排 09 錢二錢二 男男 1985.10.12 士兵士兵 二排二排 10 錢三錢三 女女 1986.7.5 士兵士兵 三排三排定義：定義：data_structure=( D , S ) D= 01,02,03,04,05,06,07,08,09,10S=, , 05010308020704060910

12、樹形結(jié)構(gòu)樹形結(jié)構(gòu)考慮領(lǐng)導與被領(lǐng)導之間的關(guān)系考慮領(lǐng)導與被領(lǐng)導之間的關(guān)系 工號工號 姓名姓名 性別性別 出生年月出生年月 職務(wù)職務(wù) 班排班排 01 張三張三 男男 1972.3.20 連長連長 二連二連 02 李四李四 男男 1978.6.14 排長排長 一排一排 03 王五王五 男男 1974.12.7 排長排長 二排二排 04 趙一趙一 女女 1982.8.5 排長排長 三排三排 05 趙二趙二 男男 1969.8.15 士兵士兵 一排一排 06 趙七趙七 男男 1985.4.1 士兵士兵 一排一排 07 趙八趙八 男男 1982.6.28 士兵士兵 二排二排 08 錢一錢一 男男 1977.

13、317 士兵士兵 二排二排 09 錢二錢二 男男 1985.10.12 士兵士兵 二排二排 10 錢三錢三 女女 1986.7.5 士兵士兵 三排三排定義：定義：data_structure=( D , S ) D= 01,02,03,04,05,06,07,08,09,10S=, , , 05010302070406圖形結(jié)構(gòu)圖形結(jié)構(gòu)考慮好朋友關(guān)系考慮好朋友關(guān)系 工號工號 姓名姓名 性別性別 出生年月出生年月 職務(wù)職務(wù) 班排班排 01 張三張三 男男 1972.3.20 連長連長 二連二連 02 李四李四 男男 1978.6.14 排長排長 一排一排 03 王五王五 男男 1974.12.7

14、排長排長 二排二排 04 趙一趙一 女女 1982.8.5 排長排長 三排三排 05 趙二趙二 男男 1969.8.15 士兵士兵 一排一排 06 趙七趙七 男男 1985.4.1 士兵士兵 一排一排 07 趙八趙八 男男 1982.6.28 士兵士兵 二排二排 08 錢一錢一 男男 1977.317 士兵士兵 二排二排 09 錢二錢二 男男 1985.10.12 士兵士兵 二排二排 10 錢三錢三 女女 1986.7.5 士兵士兵 三排三排兩種：兩種：順序順序存儲結(jié)構(gòu)存儲結(jié)構(gòu) 借助元素在存儲器中的借助元素在存儲器中的相對位置相對位置來表示數(shù)據(jù)元素來表示數(shù)據(jù)元素間的邏輯關(guān)系。要求用地址連續(xù)的一

15、整片存儲空間間的邏輯關(guān)系。要求用地址連續(xù)的一整片存儲空間（數(shù)組）。（數(shù)組）。鏈式鏈式存儲結(jié)構(gòu)存儲結(jié)構(gòu) 借助指示元素存儲地址的借助指示元素存儲地址的指針指針表示數(shù)據(jù)元素間的表示數(shù)據(jù)元素間的邏輯關(guān)系。無需一整塊存儲空間。邏輯關(guān)系。無需一整塊存儲空間。存儲結(jié)構(gòu)存儲結(jié)構(gòu)元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲地址存儲內(nèi)容存儲內(nèi)容Loc(元素元素i)=L0+（i-1)*m順序存儲順序存儲每個元素占每個元素占m個字節(jié)個字節(jié)L0為整片存儲空間的起始地址為整片存儲空間的起始地址1536元素元素2 21400元素元素1 1134

16、6元素元素3 3 元素元素4 41345h存儲地址存儲地址 存儲內(nèi)容存儲內(nèi)容 指針指針 13451345 元素元素1 1 1400 1400 13461346 元素元素4 4 . . . . . 14001400 元素元素2 2 1536 1536 . . . . . 15361536 元素元素3 3 1346 1346 鏈式存儲鏈式存儲 h后繼元素后繼元素所在地址所在地址記住首元記住首元素地址素地址對于一種數(shù)據(jù)結(jié)構(gòu)對于一種數(shù)據(jù)結(jié)構(gòu), , 常見的運算包括：常見的運算包括： 插入插入 刪除刪除 修改修改 查找查找 排序排序 邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)都相同邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)都相同, , 但運算不同但運算

17、不同, , 則數(shù)據(jù)則數(shù)據(jù)結(jié)構(gòu)不同。結(jié)構(gòu)不同。 例如例如, , 棧與隊列棧與隊列數(shù)據(jù)結(jié)構(gòu)關(guān)心的三個方面：數(shù)據(jù)結(jié)構(gòu)關(guān)心的三個方面： 1數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 2、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu) A線性結(jié)構(gòu)線性結(jié)構(gòu) B非線性結(jié)構(gòu)非線性結(jié)構(gòu)A 順序存儲順序存儲 B 鏈式存儲鏈式存儲 線性表線性表 棧、隊列棧、隊列樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面數(shù)據(jù)結(jié)構(gòu)的三個方面 3、數(shù)據(jù)的運算：插入、刪除、修改、查找、排序等。、數(shù)據(jù)的運算：插入、刪除、修改、查找、排序等。 串、數(shù)組串、數(shù)組集合結(jié)構(gòu)集合結(jié)構(gòu)1.3 1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn)一個數(shù)據(jù)的集合一個數(shù)據(jù)的集

18、合, , 以及定義于這個數(shù)以及定義于這個數(shù)據(jù)集合上的一組操作的總稱。據(jù)集合上的一組操作的總稱。 C C語言中的數(shù)據(jù)類型：語言中的數(shù)據(jù)類型： 基本數(shù)據(jù)類型、指針類型、數(shù)組類型、結(jié)構(gòu)基本數(shù)據(jù)類型、指針類型、數(shù)組類型、結(jié)構(gòu)體類型、公用體類型、枚舉類型體類型、公用體類型、枚舉類型(ADT: Abstract Data Types) 是指是指用戶定義的用戶定義的一個數(shù)學模型以及定義在此數(shù)一個數(shù)學模型以及定義在此數(shù)學模型上的一組操作的總稱。學模型上的一組操作的總稱。 （僅（僅定義定義數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說明，不考慮在數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說明，不考慮在計算機內(nèi)部的表示和實現(xiàn)）計算機內(nèi)部的表示和實現(xiàn)）抽象數(shù)據(jù)

19、類型抽象數(shù)據(jù)類型可以用以下的三元組來表示：可以用以下的三元組來表示： ADT = （D，S，P） 數(shù)據(jù)對象數(shù)據(jù)對象 D上的關(guān)系集上的關(guān)系集 D上的操作集上的操作集 ADTADT抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)數(shù)據(jù)對象對象： 數(shù)據(jù)數(shù)據(jù)關(guān)系關(guān)系： 基本基本 ： ADT ADT抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型名名ADT常用常用定義定義格式格式 抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。實型、字符型等）來表示和實現(xiàn)。 教材中用的是類教材中用的是類C C語言作為描述工具，語言作為描述工具，p8p8。例題：例題： 定義矩形的抽象數(shù)據(jù)類型

20、，其數(shù)據(jù)包括矩形的長和寬，定義矩形的抽象數(shù)據(jù)類型，其數(shù)據(jù)包括矩形的長和寬，操作包括初始化矩形的長和寬，計算矩形的周長與面積。操作包括初始化矩形的長和寬，計算矩形的周長與面積。 ADT Rectangle 數(shù)據(jù)對象數(shù)據(jù)對象：D=e1,e2|e1,e2是實數(shù)是實數(shù) 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：S=|e1是矩形長，是矩形長，e2是矩形寬是矩形寬 基本操作基本操作： InitRectangle (&R, len, wid); 操作結(jié)果：構(gòu)造矩形操作結(jié)果：構(gòu)造矩形R，長與寬分別被賦予參數(shù)，長與寬分別被賦予參數(shù) len 與與wid的值的值 Circumference (R); 初始條件：初始條件：R已存在

21、已存在 操作結(jié)果：返回矩形操作結(jié)果：返回矩形R的周長的周長 Area (R); 初始條件：初始條件：R已存在已存在 操作結(jié)果：返回矩形操作結(jié)果：返回矩形R的面積的面積 ADT Rectangle 表示部分：表示部分： typedef struct Rect float length, width; Rectangle;實現(xiàn)部分：實現(xiàn)部分： void InitRectangle(&Rectangle r, float len, float wid) r. Length = len; r. Width = wid; float Circumference (Rectangle r) ret

22、urn 2*(r.length + r.width); float Area (Rectangle r) return r.length * r.width; void Main() Rectangle x; InitRectangle(x,10,5); cout Area (x)endl; .( algorithm)1.4 1.4 算法和算法分析算法和算法分析算法效率分析方法：算法效率分析方法： 事后統(tǒng)計：事后統(tǒng)計： 事前分析估算：事前分析估算：通常采用這種方法，計算漸進復雜度通常采用這種方法，計算漸進復雜度 同一個算法用不同的語言、不同的編譯程序、同一個算法用不同的語言、不同的編譯程序、在

23、不同的計算機上運行，效率均不同，在不同的計算機上運行，效率均不同，使用使用絕對時間單位絕對時間單位衡量算法效率不合適衡量算法效率不合適算法的時間復雜度算法的時間復雜度是一個算法運行時間的相對量度是一個算法運行時間的相對量度算法的運行時間算法的運行時間 = = 計算機執(zhí)行一種簡單操作的時間計算機執(zhí)行一種簡單操作的時間* *簡單操作的執(zhí)行次數(shù)簡單操作的執(zhí)行次數(shù) （與機器有關(guān)，不考慮）（與機器有關(guān)，不考慮）如：如：t=x; x=y; y=t;t=x; x=y; y=t; 運行時間運行時間 = = 一條賦值語句的執(zhí)行時間一條賦值語句的執(zhí)行時間* *3 3 通常把算法中包含簡單操作次數(shù)的多少叫做該算法通

24、常把算法中包含簡單操作次數(shù)的多少叫做該算法的時間復雜度，用它來衡量一個算法的運行時間性能。的時間復雜度，用它來衡量一個算法的運行時間性能。 若解決一個問題的規(guī)模為若解決一個問題的規(guī)模為n n，即表示待處理的數(shù)據(jù)中即表示待處理的數(shù)據(jù)中包含有包含有n n個元素，則算法的個元素，則算法的時間復雜度時間復雜度通常是通常是n n的一個函的一個函數(shù)，記為數(shù)，記為f(n)f(n)。例例1 1：分析以下程序的時間復雜度：分析以下程序的時間復雜度 int Sum(int b, int n) int i, s=0; /頻度為頻度為1 for ( i=0; in; i+ ) /頻度為頻度為(n+1) s=s+bi;

25、 /頻度為頻度為n return s; /頻度為頻度為1 （一條語句重復執(zhí)行的次數(shù)稱語句的頻度）（一條語句重復執(zhí)行的次數(shù)稱語句的頻度） 時間復雜度時間復雜度: : f(n) = 2 2n+3 = O(n)例例2 2：分析以下程序段的時間復雜度：分析以下程序段的時間復雜度 for ( i=1; i=n; i+) /n+1次次 y+ ; /n次次 for ( j=1; j= n0n = n0時，時， T(n)T(n)=M=M* *f(n)|f(n)| 表示隨問題規(guī)模表示隨問題規(guī)模n n的增大，算法執(zhí)行時間的增長率的增大，算法執(zhí)行時間的增長率與函數(shù)與函數(shù)f(n)f(n)的增長率相同。的增長率相同。

26、當當 f(n)= c0nm+c1nm-1+cm-1n+cm 時，時， T(n)= O(nm) 采用數(shù)量級的形式表示后采用數(shù)量級的形式表示后，時間復雜度不必計算出時間復雜度不必計算出簡單操作的精確次數(shù)，只要計算出相應的簡單操作的精確次數(shù)，只要計算出相應的數(shù)量級數(shù)量級即可。即可。 例：例：lx =x+1; y =y+1; O(1)lfor (i=1;i=n;i+) x=x+1 O(n)lfor (i=1;i=n;i+) for (j=1; j=i-1; j+) x=x+1 O(n2)算法的時間復雜度是由算法的時間復雜度是由嵌套最深層嵌套最深層語句的頻度決定的語句的頻度決定的算法的時間復雜度通常具有

27、形式：算法的時間復雜度通常具有形式：O(1)、 O(log2n) 、 O(n) 、O(n*log2n)、O(n2)、O(n3)、O(2n) 、O(n!)隨著隨著n n的增大，各種數(shù)量級對應值的增長速度大不相同，的增大，各種數(shù)量級對應值的增長速度大不相同，對應關(guān)系如下：對應關(guān)系如下： P14 圖圖1.7 O(1) O(log2n) O(n) O(n*log2n) O(n2) O(2n) O(n!) 一個算法的一個算法的時間復雜度時間復雜度還可以具體分為還可以具體分為最好最好、最最差差和和平均平均三種情況來討論三種情況來討論 。例：順序查找算法例：順序查找算法 int SequenceSearch(int a , int n, int item) /若查找成功則返回元素的下標，否則返回若查找成功則返回元素的下標，否則返回-1。 for (int i=0; in; i+) if (ai=item) return i; return -1; 第