2022考研数据结构_1 绪论
https://gitee.com/fakerlove/Data-Structure-文章地址
文章目錄
- 1. 數(shù)據(jù)結(jié)構(gòu)緒論
- 1.1 什么是數(shù)據(jù)結(jié)構(gòu)？
- 1.2 數(shù)據(jù)結(jié)構(gòu)起源
- 1.3 程序設(shè)計(jì)=數(shù)據(jù)結(jié)構(gòu)+算法
- 1.4基本概念和術(shù)語(yǔ)
- 1.4.1數(shù)據(jù)
- 1.4.2 數(shù)據(jù)元素
- 1.4.3 數(shù)據(jù)項(xiàng)
- 1.4.4 數(shù)據(jù)對(duì)象
- 1.4.5 數(shù)據(jù)結(jié)構(gòu)
- 1.5 邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
- **1.5.1** **邏輯結(jié)構(gòu)**
- **1.5.2** **物理結(jié)構(gòu)**
- **1.6** **抽象數(shù)據(jù)類(lèi)型**
- 1.6.1 數(shù)據(jù)類(lèi)型
- 1.6.2 抽象數(shù)據(jù)類(lèi)型
- **1.7**總結(jié)回顧
1. 數(shù)據(jù)結(jié)構(gòu)緒論
1.1 什么是數(shù)據(jù)結(jié)構(gòu)？
數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
1.2 數(shù)據(jù)結(jié)構(gòu)起源
? 1968年，美國(guó)的高德納教授開(kāi)創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的課程體系。
? 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中的操作對(duì)象，以及它們之間的關(guān)系和操作等相關(guān)問(wèn)題的學(xué)科。
? 程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)確定的問(wèn)題選擇一種好的結(jié)構(gòu)，加上設(shè)計(jì)一種好的算法。數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)當(dāng)中占據(jù)了重要的地位。
1.3 程序設(shè)計(jì)=數(shù)據(jù)結(jié)構(gòu)+算法
1.4基本概念和術(shù)語(yǔ)
? 說(shuō)到數(shù)據(jù)結(jié)構(gòu)是什么，我們得先來(lái)談?wù)勈裁唇凶鰯?shù)據(jù)。
? 正所謂“巧婦難為無(wú)米之炊”，在強(qiáng)大的計(jì)算機(jī)，也要有“米”下鍋才可以干活的，否則就是一堆破銅爛鐵。這個(gè)“米”就是數(shù)據(jù)。
1.4.1數(shù)據(jù)
*數(shù)據(jù)：是描述客觀事物的符號(hào)，是計(jì)算機(jī)中可以操作的對(duì)象，是能被計(jì)算機(jī)識(shí)別，并輸入給計(jì)算機(jī)處理的符號(hào)集合。*數(shù)據(jù)不僅僅包括整型、實(shí)型等數(shù)值類(lèi)型，還包括字符及聲音、圖像、視頻等非數(shù)值類(lèi)型。
? 例如平時(shí)我們所用的搜索中會(huì)有網(wǎng)頁(yè)、MP3、圖片、視頻等分類(lèi)。MP3就是聲音數(shù)據(jù)，圖片就是圖像數(shù)據(jù)，而網(wǎng)頁(yè)其實(shí)指的就是全部數(shù)據(jù)的搜索，包括最重要的數(shù)字和文字等文字?jǐn)?shù)據(jù)。
? 也就是說(shuō)我們所說(shuō)的數(shù)據(jù)就是符號(hào)，而且這些符號(hào)必須具備兩個(gè)前提：
? 1.可以輸入到計(jì)算機(jī)中
? 2.能被計(jì)算機(jī)程序處理
? 對(duì)于整型、實(shí)型等數(shù)值類(lèi)型，可以進(jìn)行數(shù)值計(jì)算。
? 對(duì)于字符型數(shù)據(jù)類(lèi)型，就需要進(jìn)行非數(shù)值的處理。而聲音、圖像、視頻等其實(shí)是可以通過(guò)編碼的手段變成字符數(shù)據(jù)來(lái)處理的。
1.4.2 數(shù)據(jù)元素
? 數(shù)據(jù)元素：是組成數(shù)據(jù)的、有一定意義的基本單位，在計(jì)算機(jī)中通常作為整體處理。也被稱為記錄。
? 例如，在人類(lèi)中，人就是數(shù)據(jù)元素。畜類(lèi)中，牛、馬、羊、雞、豬、狗等動(dòng)物就是禽類(lèi)的數(shù)據(jù)元素。
1.4.3 數(shù)據(jù)項(xiàng)
? 數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。
? 例如，人作為一個(gè)數(shù)據(jù)元素，可以有眼、耳、鼻、嘴、手、腳這些數(shù)據(jù)項(xiàng)，也可以有姓名、年齡、性別、出生地址、聯(lián)系電話等數(shù)據(jù)項(xiàng)，具體有哪些數(shù)據(jù)項(xiàng)，要視你做的系統(tǒng)來(lái)決定。
? *數(shù)據(jù)項(xiàng)是不可分割的最小單位。*記住數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。但在真正討論問(wèn)題時(shí)，數(shù)據(jù)元素才是數(shù)據(jù)結(jié)構(gòu)中建立數(shù)據(jù)模型的著眼點(diǎn)。例如討論電影時(shí)，是討論電影角色這樣的“數(shù)據(jù)元素”，而不是針對(duì)這個(gè)角色的姓名或者年齡這樣的“數(shù)據(jù)項(xiàng)”去研究分析。
1.4.4 數(shù)據(jù)對(duì)象
? 數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。
? 性質(zhì)相同就是指數(shù)據(jù)元素具有相同數(shù)量和類(lèi)型的數(shù)據(jù)項(xiàng)，例如，人都有姓名、生日、性別等相同的數(shù)據(jù)項(xiàng)。
? 在實(shí)際運(yùn)用中，在不產(chǎn)生混淆的情況下，我們將數(shù)據(jù)對(duì)象簡(jiǎn)稱為數(shù)據(jù)。
1.4.5 數(shù)據(jù)結(jié)構(gòu)
? 結(jié)構(gòu)，簡(jiǎn)單的理解就是關(guān)系，比如分子結(jié)構(gòu)，就是說(shuō)組成分子的原子之間的排列方式。嚴(yán)格來(lái)說(shuō)，結(jié)構(gòu)是指各個(gè)組成部分相互搭配和排列的方式。在現(xiàn)實(shí)世界中，不同元素之間不是獨(dú)立的，而是存在特定的關(guān)系，我們將這些關(guān)系稱為結(jié)構(gòu)。
數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
在計(jì)算機(jī)中，數(shù)據(jù)元素并不是孤立、雜亂無(wú)序的，而是具有內(nèi)在聯(lián)系的數(shù)據(jù)集合。數(shù)據(jù)元素之間存在的一種或者多種特定關(guān)系，也就是數(shù)據(jù)的組織形式。編寫(xiě)一個(gè)“好”的程序，必須分析待處理對(duì)象的特性及各處理對(duì)象之間存在的關(guān)系。這也就是研究數(shù)據(jù)結(jié)構(gòu)的意義所在。
1.5 邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
? 根據(jù)視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)可以分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩大類(lèi)。
1.5.1 邏輯結(jié)構(gòu)
? *邏輯結(jié)構(gòu)：是指數(shù)據(jù)對(duì)象中元素之間的相互關(guān)系。這是最需要關(guān)注的問(wèn)題。*邏輯結(jié)構(gòu)分為以下四種：
1. 集合結(jié)構(gòu)
? *集合結(jié)構(gòu)：集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外，他們之間沒(méi)有其他關(guān)系。*各個(gè)數(shù)據(jù)元素是“平等”的，共同屬性是“同屬于一個(gè)集合”。類(lèi)似于數(shù)學(xué)中的集合（如圖所示）。
2. 線性結(jié)構(gòu)
? 線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)一的關(guān)系（如圖所示）。
3. 樹(shù)形結(jié)構(gòu)
? 樹(shù)形結(jié)構(gòu)：樹(shù)形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對(duì)多的層次關(guān)系（如圖所示）。
? 圖形結(jié)構(gòu)：圖形結(jié)構(gòu)的數(shù)據(jù)元素是多對(duì)多的關(guān)系（如圖所示）。
? 示意圖表示數(shù)據(jù)的邏輯結(jié)構(gòu)時(shí)，1.將每個(gè)元素看做一個(gè)結(jié)點(diǎn)，用圓圈表示。2.元素之間的邏輯關(guān)系用結(jié)點(diǎn)之間的連線表示，如果關(guān)系是有方向的，那么用帶箭頭的連線表示。
? 由以上例子可以看出，邏輯結(jié)構(gòu)是針對(duì)具體問(wèn)題的，是為了解決某個(gè)問(wèn)題在對(duì)問(wèn)題理解的基礎(chǔ)上，選擇合適的數(shù)據(jù)結(jié)構(gòu)表示數(shù)據(jù)元素之間的邏輯關(guān)系。
1.5.2 物理結(jié)構(gòu)
? 物理結(jié)構(gòu)也叫做存儲(chǔ)結(jié)構(gòu)。
? 物理結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式。
? 數(shù)據(jù)是數(shù)據(jù)元素的集合，根據(jù)物理結(jié)構(gòu)的定義，實(shí)際上就是如何將數(shù)據(jù)元素存儲(chǔ)到計(jì)算機(jī)的存儲(chǔ)器中。存儲(chǔ)器主要針對(duì)內(nèi)存而言的，像硬盤(pán)、軟盤(pán)、光盤(pán)等外部存儲(chǔ)器的數(shù)據(jù)組織通常用文件結(jié)構(gòu)來(lái)描述。
? 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)必須正確反映數(shù)據(jù)元素之間的邏輯關(guān)系，這才是最為關(guān)鍵的，如何存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系，是實(shí)現(xiàn)物理結(jié)構(gòu)的難點(diǎn)和重點(diǎn)。
? 數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)形式有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。
1. 順序存儲(chǔ)結(jié)構(gòu)
? 順序存儲(chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的（如圖所示）。
? 說(shuō)白了就是排隊(duì)占位，大家按順序排好，每個(gè)人占一小段空間，大家誰(shuí)也別插誰(shuí)的隊(duì)。
2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
? 在實(shí)際中，總有人會(huì)插隊(duì)，也會(huì)有人要去上廁所、有人放棄排隊(duì)，所以這個(gè)隊(duì)伍會(huì)有新成員添加，也會(huì)去掉老元素，在面對(duì)這樣要時(shí)常變化的結(jié)構(gòu)時(shí)，順序存儲(chǔ)是不科學(xué)的。
現(xiàn)在在銀行、醫(yī)院等地方，設(shè)置了排隊(duì)系統(tǒng)，也就是每個(gè)人先領(lǐng)一個(gè)號(hào)，等著叫號(hào)，叫到時(shí)去辦理業(yè)務(wù)或者看病。等待的過(guò)程你可以想在哪就在哪待著，你只需要關(guān)注的是你前一個(gè)號(hào)有沒(méi)有被叫到，叫到了，下一個(gè)就輪到你了。
? *鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的也可以不是連續(xù)的。*數(shù)據(jù)元素的存儲(chǔ)關(guān)系并不能反映其邏輯關(guān)系，因此需要 用一個(gè)指針存放數(shù)據(jù)元素的地址，這樣通過(guò)地址就可以找到相關(guān)聯(lián)數(shù)據(jù)元素的位置（如圖所示）。
? 顯然，鏈?zhǔn)酱鎯?chǔ)就靈活多了，數(shù)據(jù)存在哪里不重要，只要有一個(gè)指針存放相應(yīng)的地址就能找到它了。
? 邏輯結(jié)構(gòu)是面向問(wèn)題的，而物理結(jié)構(gòu)就是面向計(jì)算機(jī)的，其基本的目標(biāo)就是將數(shù)據(jù)及其邏輯關(guān)系存儲(chǔ)到計(jì)算機(jī)的內(nèi)存中。
1.6 抽象數(shù)據(jù)類(lèi)型
1.6.1 數(shù)據(jù)類(lèi)型
? 數(shù)據(jù)類(lèi)型：是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。
? 數(shù)據(jù)類(lèi)型是按照值的不同進(jìn)行劃分的。在高級(jí)語(yǔ)言中，每個(gè)變量、常量和表達(dá)式都各有各的取值范圍。類(lèi)型就用來(lái)說(shuō)明變量或表達(dá)式的取值范圍和能進(jìn)行的操作。
? 在C語(yǔ)言中，按照取值的不同，數(shù)據(jù)類(lèi)型就可以分為兩類(lèi)：
? 1. 原子類(lèi)型：是不可以再分解的基本類(lèi)型，包括整型、實(shí)型、字符型等。
? 2. 結(jié)構(gòu)類(lèi)型：由若干個(gè)類(lèi)型組合而成，是可以再分解的。例如，整型數(shù)組是由若干整型數(shù)據(jù)組成的。
? 比如，在C語(yǔ)言中變量聲明int a, b，這就意味著，在給變量a和b賦值時(shí)不能超出int的取值范圍，變量a和b之間的運(yùn)算只能是int類(lèi)型所允許的運(yùn)算。
? 無(wú)論什么計(jì)算機(jī)、什么計(jì)算機(jī)語(yǔ)言，大都會(huì)面臨著如整數(shù)運(yùn)算、實(shí)數(shù)運(yùn)算、字符運(yùn)算等操作，我們可以考慮把它們都抽象出來(lái)。
? *抽象是指抽取出事物具有的普遍性的本質(zhì)。*它是抽出問(wèn)題的特征而忽略非本質(zhì)的細(xì)節(jié)，是對(duì)具體事物的一個(gè)概括。抽象是一種思考問(wèn)題的方式，它隱藏了繁雜的細(xì)節(jié)，只保留實(shí)現(xiàn)目標(biāo)所必需的信息。
1.6.2 抽象數(shù)據(jù)類(lèi)型
? 對(duì)已有的數(shù)據(jù)類(lèi)型進(jìn)行抽象，就有了抽象數(shù)據(jù)類(lèi)型。
? *抽象數(shù)據(jù)類(lèi)型（Abstract Data Type , 簡(jiǎn)稱ADT）：是指一個(gè)數(shù)據(jù)模型及定義在該模型上的一組操作。*抽象數(shù)據(jù)類(lèi)型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何操作如何標(biāo)示和實(shí)現(xiàn)無(wú)關(guān)。
? **“抽象”的意義在于數(shù)據(jù)類(lèi)型的數(shù)學(xué)抽象特性。
? 抽象數(shù)據(jù)類(lèi)型不僅僅指那些已經(jīng)定義并實(shí)現(xiàn)的的數(shù)據(jù)類(lèi)型，還可以是編程者在設(shè)計(jì)程序時(shí)自己定義的數(shù)據(jù)類(lèi)型。例如，在繪圖軟件中，坐標(biāo)x，y，z這三個(gè)變量始終一起出現(xiàn)，我們就可以定義一個(gè)叫point的數(shù)據(jù)抽象類(lèi)型，它有x，y，z三個(gè)整型變量，這樣就能方便的操作一個(gè)point數(shù)據(jù)變量就能知道這一點(diǎn)的坐標(biāo)了。
? 根據(jù)抽象將數(shù)據(jù)類(lèi)型的定義，它還可以定義在該模型上的一組操作。
? 一個(gè)抽象數(shù)據(jù)類(lèi)型定義了：一個(gè)數(shù)據(jù)對(duì)象、數(shù)據(jù)對(duì)象中各元素之間的關(guān)系及對(duì)數(shù)據(jù)元素的操作。至于，一個(gè)抽象數(shù)據(jù)類(lèi)型到底需要哪些操作，這就只能由設(shè)計(jì)者根據(jù)實(shí)際需要來(lái)定。例如，馬里奧這個(gè)游戲，開(kāi)始可能只有走和跳兩種操作，后來(lái)發(fā)現(xiàn)應(yīng)該增加一種打子彈的操作，再后來(lái)有玩家希望可以走快一點(diǎn)，就有了按住打子彈鍵后前進(jìn)就會(huì)“跑”的操作。這都是根據(jù)實(shí)際情況來(lái)設(shè)計(jì)的。
? 事實(shí)上，*抽象數(shù)據(jù)類(lèi)型體現(xiàn)了程序設(shè)計(jì)中問(wèn)題分解、抽象和信息隱藏的特性。*抽象數(shù)據(jù)類(lèi)型把實(shí)際生活中的問(wèn)題分解為多個(gè)規(guī)模小且容易處理的問(wèn)題，然后建立一個(gè)計(jì)算機(jī)能處理的數(shù)據(jù)模型，并把每個(gè)功能模塊的實(shí)現(xiàn)細(xì)節(jié)作為一個(gè)獨(dú)立的單元，從而使具體實(shí)現(xiàn)過(guò)程隱藏起來(lái)。
? 為方便對(duì)抽象數(shù)據(jù)類(lèi)型進(jìn)行規(guī)范的描述，我們可以按照下面描述的抽象數(shù)據(jù)類(lèi)型的標(biāo)準(zhǔn)格式來(lái)編寫(xiě)程序：
1.7總結(jié)回顧
? 前面介紹了數(shù)據(jù)結(jié)構(gòu)的一些相關(guān)概念，如圖所示：
? 這些概念給出了數(shù)據(jù)結(jié)構(gòu)的定義：*數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或者多種特定關(guān)系的數(shù)據(jù)元素的集合。*同樣是結(jié)構(gòu)，從不同角度來(lái)討論，會(huì)有不同的分類(lèi)，如圖所示：
? 還介紹了抽象數(shù)據(jù)類(lèi)型及它的描述方法。
總結(jié)
以上是生活随笔為你收集整理的2022考研数据结构_1 绪论的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 1057: [ZJOI2007]棋盘制作
- 下一篇： MSDE 下载安装、创建管理数据库