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

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

1.理解線性數(shù)據(jù)結(jié)構(gòu)的概念和存儲方法；2.理解數(shù)組處理數(shù)據(jù)的優(yōu)缺點(diǎn)；3.掌握鏈表的定義及操作方法；*4.掌握棧的定義、存儲方法及對應(yīng)的操作方法；*5.掌握隊(duì)列的定義、存儲方法及對應(yīng)的操作方法；*6.了解鏈表、棧和隊(duì)列在嵌入式軟件中的應(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)系，且只有一個(gè)起始數(shù)據(jù)元素和一個(gè)終止數(shù)據(jù)元素。數(shù)據(jù)元素也稱為節(jié)點(diǎn)。常用的線性數(shù)據(jù)結(jié)構(gòu)：線性表、棧和隊(duì)列等。

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

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

隊(duì)列（Queue）：排隊(duì)購票時(shí)，先來先購先走，后來后購后走——先進(jìn)先出（FIFO）的線性表。線性數(shù)據(jù)結(jié)構(gòu)的兩種存儲方法：順序存儲、鏈?zhǔn)酱鎯Α?/p>

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

鏈?zhǔn)酱鎯Γ哼壿嬌舷噜彽臄?shù)據(jù)元素對應(yīng)的物理存儲位置可以不相鄰，可用指針來實(shí)現(xiàn)。7.2.1線性表的定義

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

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

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

缺點(diǎn)：

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

鏈?zhǔn)酱鎯Φ木€性表——鏈表，可以彌補(bǔ)數(shù)組存在的以上缺陷。7.2.2單向鏈表的定義7.2線性表

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

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

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

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

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

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

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

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

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

插入字符c的詳細(xì)過程：c

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

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

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

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

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

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

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

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