1、線性表的邏輯結構
    線性結構是最常用、最簡單的一種數據結構。而線性表是一種典型的線性結構。其基
    本特點是線性表中的數據元素是有序且是有限的。在這種結構中：
    1 存在一個唯一的被稱為“第一個”的數據元素；
    2 存在一個唯一的被稱為“最後一個”的數據元素；
    3 除第一個元素外，每個元素均有唯一一個直接前驅；
    4 除最後一個元素外，每個元素均有唯一一個直接後繼。
    例如： 線性序列 a1，a2， …an 線性表：是由 n(n≧0)個數據元素(結點)a1，a2， …an 組成的有限序列。該序列中的
    所有結點具有相同的數據類型。其中數據元素的個數 n 稱為線性表的長度。
    當 n=0 時，稱為空表。
    當 n＞0 時，將非空的線性表記作： (a1，a2，…an)
    a1 稱為線性表的第一個(首)結點，an 稱為線性表的最後一個(尾)結點。
    a1，a2，…ai1 都是 ai(2≦i≦n)的前驅，其中 ai1 是 ai 的直接前驅;
    ai+1，ai+2，…an 都是 ai(1≦i ≦n1)的後繼，其中 ai+1。
    2、順序表
    順序存儲 ：把線性表的結點按邏輯順序依次存放在一組地址連續的存儲單元裏。用這
    種方法存儲的線性表簡稱順序表。
    有非空的線性表：(a1，a2，…an) 。順序存儲如圖所示。
    順序存儲的線性表的特點：
    ◆ 線性表的邏輯順序與物理順序一致;
    ◆ 數據元素之間的關係是以元素在計算機內
    “物理位置相鄰”來體現。設有非空的線性表：(a1，
    a2，…an) 。順序存儲如圖所示。
    設線性表的每個元素需占用  個存儲單元，以所
    占的第一個單元的存儲地址作為數據元素的存儲位
    置。則線性表中第i+1個數據元素的存儲位置oc(ai+1)
    和第 i 個數據元素的存儲位置 oc(ai)之間滿足下列關
    係： oc(ai+1)=oc(ai)+
    線性表的第 i 個數據元素 ai 的存儲位置為：數組具有隨機存取的特性
    oc(ai)=oc(a0)+(i)
    在高級語言(如 c 語言)環境下：數組具有隨機存取的特性，因此，借助數組來描述順序
    表。除了用數組來存儲線性表的元素之外，順序表還應該有表示線性表的長度屬性，所以用
    結構類型來定義順序表類型。    typedef struct  定義線性表結構體    int engtist; 線性表的名稱
    順序表小結。
    1、單鏈表的定義
    鏈式存儲：用一組任意的存儲單元存儲線性表中的數據元素。用這種方法存儲的線性表
    簡稱線性鏈表。
    為了正確表示結點間的邏輯關係，在存儲每個結點值的同時，還必須存儲指示其直接後
    繼結點的地址(或位置)，稱為指針(pointer)或鏈(ink)，這兩部分組成了鏈表中的結點結構，
    鏈表是通過每個結點的指針域將線性表的 n 個結點按其邏輯次序鏈接在一起的。每一個結隻
    包含一個指針域的鏈表，稱為單鏈表。
    存儲鏈表中結點的一組任意的存儲單元可以是連續的，也可以是不連續的，甚至是零散
    分布在內存中的任意位置上的。鏈表中結點的邏輯順序和物理順序不一定相同。
    操作方便，總是在鏈表的第一個結點之前附設一個頭結點(頭指針)e inked ist) 指的是構成鏈表的每個結點中設立兩個指針域：一個指向
    其直接前趨的指針域 prior，一個指向其直接後繼的指針域 next。這樣形成的鏈表中有兩個
    方向不同的鏈，故稱為雙向鏈表。將頭結點和尾結點鏈接起來也能構成循環鏈表，並稱之為
    雙向循環鏈表。
    雙向鏈表的結點的類型定義如下。其結點形式如圖所示，帶頭結點的雙向鏈表的形式如
    圖所示。
    就是用數組來實現鏈式存儲結構，目的是方便在不設指針類型的高級程序設計語言中使
    用鏈式結構。實現原理：
    1、使用結構體數組，結構體有指針域 cur 和數據域 data
    2、一個數組分量表示一個節點，用 cur 代替指針指示節點在數組中
    本小章還未完，請點擊下一頁繼續閱讀後麵精彩內容！
    的相對位置
    靜態鏈表，就是用數組來實現鏈式存儲結構，目的是方便在不設指
    針類型的高級程序設計語言中使用鏈式結構。
    1、在雙向鏈表指針 p 的結點前插入一個指針 q 的結點操作是 ）
    2．某線性表中最常用的操作是在最後一個元素之後插入一個元素和刪除第一個元素，則采
    用 ）存儲方式最節省運算時間。
    a．單鏈表 b．僅有頭指針的單循環鏈表
    c．雙鏈表 d．僅有尾指針的單循環鏈表
    3、下列關於線性表的敘述中，錯誤的是 ）。
    a. 順序表是使用一維數組實現的線性表
    b. 順序表必須占用一片連續的存儲單元
    c. 順序表的空間利用率高於鏈表
    d. 在鏈表中，每個結點隻有一個鏈域
    【2016 年】已知表頭元素為 c 的單鏈表在內存中的存儲狀態如下表所示
    假設該鏈表隻給出了頭指針 ist。在不改變鏈表的前提下，請設計一個盡可能高效的算
    法，查找鏈表中 倒數第 k 個位置上的結點( k 為正整數)。若查找成功，算法輸出該結點的
    data 域的值，並返回 1；否則，隻 返回 0。要求：
    1 描述算法的基本設計思想；
    2 描述算法的詳細實現步驟；
    3 根據設計思想和實現步驟，采用程序設計語言描述算法使用 c、c++語言實現），
    關鍵之處請給出簡要注釋。
    1）算法的基本設計思想：
    問題的關鍵是設計一個盡可能高效的算法， 通過鏈表的一趟遍曆，找到倒數第 k 個結
    點的位置。算法的基 本設計思想是：定義兩個指針變量 p 和 q，初始時均指向頭結點的下。
    如圖d）所示，當|t1t2| == 1 時，表示共享棧滿。那麽大家可能會問一個問題，反正
    就是這麽一塊空間，那我們二一添作五，直接均分不就行了你好，我好，大家好，一片和
    諧，此處應該有掌聲）。均分看似合理，其實會導致很大問題，大家請想一下，程序的執行
    是不確定的，也是不均衡的好像說的有點玄乎），有的程序需要的空間大，有的程序需要
    的空間小，圖b）中表示的是棧 1 占用的空間的大一些；圖b）中表示的是棧 2 占用的
    空間的大一些，如果均分，就會出現旱澇不均，圖b）中棧 1 就會旱死空間不夠，而報
    錯），圖c）中棧 2 就會旱死空間不夠，而報錯）。
    5. 括號匹配問題
    在文字處理軟件或編譯程序設計時，常常需要檢查一個字符串或一個表達式中的括號是
    否相匹配?
    匹配思想：從左至右掃描一個字符串(或表達式)，則每個右括號將與最近遇到的那個左
    括號相匹配。則可以在從左至右掃描過程中把所遇到的左括號存放到堆棧中。每當遇到一個
    右括號時，就將它與棧頂的左括號(如果存在)相匹配，同時從棧頂刪除該左括號。
    算法思想：設置一個棧，當讀到左括號時，左括號進棧。當讀到右括號時，則從棧中彈
    出一個元素，與讀到的左括號進行匹配，若匹配成功，繼續讀入；否則匹配失敗，返回 fase。
    6. 棧與遞歸調用的實現
    棧的另一個重要應用是在程序設計語言中實現遞歸調用。遞歸調用：一個函數(或過程)
    直接或間接地調用自己本身，簡稱遞歸(recursive)。為了使遞歸調用不至於無終止地進行下
    去，實際上有效的遞歸調用函數(或過程)應包括兩部分：遞推規則(方法)，終止條件, 初始。
    喜歡離語請大家收藏：()離語書更新速度全網最快。