~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
開發工具與關鍵技術：線性表
作者：李宥良
撰寫時間：2020年5月18日
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
線性表線性表的定義及特點：
1、存在唯一的第一個元素；（這一點決定了圖不是線性表）
2、存在唯一的最后一個元素；
3、除第一個元素外，其它均只有一個前驅（這一點決定了樹不是線性表）
4、除最后一個元素外，其它均只有一個后繼。
線性表的順序表示和實作
1、 線性表的順序存盤表示
線性表的順序存盤結構：把線性表的結點按邏輯順序依次存放在一組地址連續的存盤單元里。用這種方法存盤的線性表簡稱順序表。是一種隨機存取的存盤結構。順序存盤指記憶體地址是一塊的，隨機存取指訪問時可以按下標隨機訪問，存盤和存取是不一樣的。如果是存盤，則是指按順序的，如果是存取，則是可以隨機的，可以利用元素下標進行訪問。
陣列比線性表速度更快的是：原地逆序、回傳中間節點、選擇隨機節點。
便于線性表的構造和任意元素的訪問
插入：插入新結點，之后結點后移。平均時間復雜度:O(n)
洗掉：洗掉節點，之后結點前移。平均時間復雜度:O(n)
2、 順序表中基本操作的實作
順序表：他是在計算機記憶體中以陣列形式保存的線性表。使用一組地址連續的存盤單元依次存盤資料元素的線性結構。
線性表的鏈式表示和實作
線性鏈表：用一組任意的存盤單元來依次存放線性表的結點，這組存盤單元即可以是連續的，也可以是不連續的，甚至是零散分布在記憶體中的任意位置上的。
因此，鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存盤每個結點值的同時，還必須存盤指示其后繼結點的地址。data域是資料域，用來存放結點的值。next是指標域（亦稱鏈域），用來存放結點的直接后繼的地址（或位置）。不需要事先估計存盤空間大小。
1、 單鏈表的定義與表示
單鏈表：是一種鏈式存盤的結構。用一組地址任意的存盤單元存放線性表中的資料元素。（存盤地址空間不需要是連續的）
單鏈表中每個結點的存盤地址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指標head指向開始結點。同時，由于最后一個結點無后繼，故結點的指標域為空，即NULL。頭插法建表(逆序)、尾插法建表(順序)。增加頭結點的目的是演算法實作上的方便，但增大了記憶體開銷。
查找：只能從鏈表的頭指標出發，順鏈域next逐個結點往下搜索，直到搜索到第i個結點為止。因此，鏈表不是隨機存取結構。
插入：先找到表的第i-1的存盤位置，然后插入。新結點先連后繼，再連前驅。
洗掉：首先找到ai-1的存盤位置p。然后令p–>next指向ai的直接后繼結點，即把ai從鏈上摘下。最后釋放結點ai的空間.r=p->next;p->next=r->next;delete r。
判斷一個單向鏈表中是否存在環的最佳方法是快慢指標。
2、單鏈表基本操作的實作
3、回圈鏈表
回圈鏈表：是一種頭尾相接的鏈表。其特點是無須增加存盤量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。
在單鏈表中，將終端結點的指標域NULL改為指向表頭結點的或開始結點，就得到了單鏈形式的回圈鏈表，并簡單稱為單回圈鏈表。由于回圈鏈表中沒有NULL指標，故涉及遍歷操作時，其終止條件就不再像非回圈鏈表那樣判斷p或p—>next是否為空，而是判斷它們是否等于某一指定指標，如頭指標或尾指標等。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/54140.html
標籤：非技術區