7- 常用的三種線性數(shù)據(jù)結(jié)構(gòu)

教學(xué)內(nèi)容： 第1章：C語言語法基礎(chǔ)第2章：C程序設(shè)計基礎(chǔ)第3章：利用數(shù)組處理同類型的批量數(shù)據(jù)第4章：利用函數(shù)實現(xiàn)模塊化程序設(shè)計第5章：靈活使用指針第6章：結(jié)構(gòu)體、共用體、枚舉類型及其應(yīng)用第7章：常用的三種線性數(shù)據(jù)結(jié)構(gòu)第8章：利用文件進行數(shù)據(jù)管理第9章：嵌入式技術(shù)基礎(chǔ)實踐方法C語言程序設(shè)計7.1線性數(shù)據(jù)結(jié)構(gòu)概述7.2線性表*7.3棧*7.4隊列【學(xué)習(xí)內(nèi)容】

第7章常用的三種線性數(shù)據(jù)結(jié)構(gòu)【學(xué)習(xí)目標】

1.理解線性數(shù)據(jù)結(jié)構(gòu)的概念和存儲方法；2.理解數(shù)組處理數(shù)據(jù)的優(yōu)缺點；3.掌握鏈表的定義及操作方法；*4.掌握棧的定義、存儲方法及對應(yīng)的操作方法；*5.掌握隊列的定義、存儲方法及對應(yīng)的操作方法；*6.了解鏈表、棧和隊列在嵌入式軟件中的應(yīng)用。7.1線性數(shù)據(jù)結(jié)構(gòu)概述

線性數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對一”的線性邏輯關(guān)系，即數(shù)據(jù)元素存在著依次排列的先后次序關(guān)系，且只有一個起始數(shù)據(jù)元素和一個終止數(shù)據(jù)元素。數(shù)據(jù)元素也稱為節(jié)點。常用的線性數(shù)據(jù)結(jié)構(gòu)：線性表、棧和隊列等。

線性表（LinearList）：1~100之間的自然數(shù)序列、26個字符組成的英文字母表、一個班級的學(xué)生信息表等。

棧（Stack）：盤子、作業(yè)疊放時，先放的在底部，后放的在頂部；取出時，先取頂部的，才能取下面的——后進先出（LIFO）的線性表。

隊列（Queue）：排隊購票時，先來先購先走，后來后購后走——先進先出（FIFO）的線性表。線性數(shù)據(jù)結(jié)構(gòu)的兩種存儲方法：順序存儲、鏈式存儲。

順序存儲：邏輯上相鄰的數(shù)據(jù)元素對應(yīng)的物理存儲位置也相鄰，可用數(shù)組來實現(xiàn)。

鏈式存儲：邏輯上相鄰的數(shù)據(jù)元素對應(yīng)的物理存儲位置可以不相鄰，可用指針來實現(xiàn)。7.2.1線性表的定義

線性表是由n（n≥0）個性質(zhì)相同的數(shù)據(jù)元素組成的有限序列，記作：（a1，a2，…，ai-1，ai，ai+1，…，an）。除了首元素a1外，其他每個元素都有一個直接前趨（ai直接前趨為ai-1）；除了尾元素an外，其他每個元素都有一個直接后繼（ai直接后繼為ai+1）。7.2線性表

采用順序存儲結(jié)構(gòu)的線性表稱為順序表，常用數(shù)組實現(xiàn)順序表。數(shù)組占用一片連續(xù)的存儲空間。優(yōu)點：可用下標隨機訪問任一數(shù)組元素。

（2）當(dāng)待處理的數(shù)據(jù)個數(shù)不確定時，很難確定合適的數(shù)組長度。

缺點：

（1）對數(shù)組元素的插入或刪除操作不方便，效率低。

鏈式存儲的線性表——鏈表，可以彌補數(shù)組存在的以上缺陷。7.2.2單向鏈表的定義7.2線性表

一個單向鏈表由頭指針（head）和若干個節(jié)點組成。每個節(jié)點由數(shù)據(jù)域（存放本節(jié)點的實際數(shù)據(jù)）和指針域（存放下一個節(jié)點的地址）兩部分組成。

頭指針用于存放第1個節(jié)點的地址，指向第1個節(jié)點，因此可通過頭指針找到第1個節(jié)點，然后再通過第1個節(jié)點找到第2個節(jié)點，依次類推，直到找到最后一個節(jié)點（其指針域為空，不指向任何節(jié)點）。

若不關(guān)心每個節(jié)點的實際地址，而只注重各節(jié)點的邏輯關(guān)系，則可簡化為：7.2線性表

可以設(shè)計一個結(jié)構(gòu)體類型來描述單向鏈表節(jié)點的結(jié)構(gòu)：鏈表主要有建立、輸出、查找、插入、刪除等操作。

為了便于操作，常在鏈表中增加一個頭節(jié)點（不存放數(shù)據(jù)）。帶頭節(jié)點的單向鏈表包括1個頭節(jié)點（0號節(jié)點）和3個數(shù)據(jù)節(jié)點（1～3號節(jié)點）。7.2.2單向鏈表的定義7.2線性表

7.2.3單向鏈表的基本操作1、鏈表的建立

建立鏈表：從無到有，一個一個地開辟節(jié)點和輸入各節(jié)點的數(shù)據(jù)，并建立起前后相鏈接的關(guān)系。

“尾插法”建立單向鏈表的過程：

頭節(jié)點的指針域始終指向第1個數(shù)據(jù)節(jié)點，新增節(jié)點鏈接到原鏈表的尾部。

插入字符c的詳細過程：c

需要設(shè)定3個指針：頭指針head、尾節(jié)點指針e、新增節(jié)點指針p7.2線性表

ruturn(head);7.2.3單向鏈表的基本操作1、鏈表的建立7.2線性表

建立鏈表后，可將鏈表中各節(jié)點的數(shù)據(jù)依次輸出。

//函數(shù)參數(shù)：鏈表的頭指針head7.2.3單向鏈表的基本操作2、鏈表的輸出7.2線性表

在鏈表中，不能像數(shù)組那樣直接通過序號訪問到節(jié)點，而必須從鏈表的頭節(jié)點開始，逐個節(jié)點進行搜索，直到搜索到指定序號節(jié)點為止。如果指定的節(jié)點序號非法（序號小于0或序號大于數(shù)據(jù)節(jié)點數(shù)），則查找失敗，需要返回NULL。

下圖所示的鏈表，包含1個頭節(jié)點（0號節(jié)點）和4個數(shù)據(jù)節(jié)點（1號～4號節(jié)點）。7.2.3單向鏈表的基本操作3、鏈表的查找——按序號查找7.2線性表

從鏈表的第1個節(jié)點開始，逐個節(jié)點進行搜索，直到搜索到指定節(jié)點值為止。在搜索過程中，如果找到指定節(jié)點，則返回指定節(jié)點的地址；當(dāng)掃描到最后一個節(jié)點，仍找不到指定節(jié)點值時，則返回NULL。7.2.3單向鏈表的基本操作3、鏈表的查找——按值查找7.2線性表

在第3個位置（第2個位置后）上插入給定節(jié)點值x的運算過程：按序號查找2號節(jié)點：7.