【408資料結構與算法】—單連結清單的基本操作（六）

一、單連結清單—取第i個元素值

算法的思路：分别取出第3個元素和第i個元素的内容。從連結清單的頭指針出發，順着鍊域next逐個結點往下搜尋，直到搜尋到第i個結點為止，是以，連結清單不是随機存取結構

算法的思路：

• 從第1個結點（L->next）順鍊掃描，用指針p指向目前掃描到的結點，p初始值p=L->next
• j做計數器，累計目前掃描過的節點數，j的初始值為1
• 當p指向掃描到的下一結點時，計數器j加1
• 當j==i時，p所指的結點就是要找的第i個結點

二、單連結清單—按值查找

按值查找—根據指定資料擷取該資料所在的位置（位址）例如：分别查找30和值為15的元素

算法步驟：

• 從第一個結點起，依次和e相比較
• 如果找到一個其值與e相等的資料元素，則傳回其在連結清單中的位置或位址
• 如果查遍整個連結清單都沒有找到其值和e相等的元素則傳回0或null

算法描述

算法設計—根據指定資料擷取該資料位置序号

三、單連結清單—插入

插入—在第i個結點前插入值為e的新結點

算法步驟：

• 首先找到ai-1的存儲位置p
• 生成一個資料域為e的新結點s

• 插入新結點：新結點的指針域指向結點ai;結點ai-1的指針域指向新結點

  📢思考：步驟1和步驟2能互換位置嗎？先執行2後執行1，可以嗎？

  📢不可以，會丢失ai的位址

算法描述：

四、單連結清單—删除

• 删除第i個結點

  算法步驟：

• 首先找到ai-1的存儲位置p,儲存要删除的a的值
• 令p->next指向ai+1

• 釋放結點ai的空間

  算法描述

五、單連結清單的查找時間效率分析

• 查找：因線性表隻能順序存取，即在查找時要從頭指針找起，查找的時間複雜度為O(n)
• 插入和删除：因線性表不需要移動元素，隻要修改指針，一般情況下時間複雜度為O（1）； 但是，如果要在單連結清單中進行前插或删除操作，由于要從頭查找前驅結點，所耗時間複雜度為O(n)

六、單連結清單的建立

1️⃣ 建立單連結清單—頭插法：元素插入在連結清單頭部，也叫前插法

算法思路：

• 從一個空表開始，重複讀入資料
• 生成新結點，将讀入資料存放到新結點的資料域中
• 從最後一個結點開始，依次将各結點插入到連結清單的前端

例如：建立連結清單L（a,b,c,d,e）

2️⃣ 建立單連結清單—尾插法：元素插入在連結清單尾部，也叫後插法

• 從一個空表L開始，将新結點逐個插入到連結清單的尾部，尾指針r指向連結清單的尾結點。
• 初始時，r同L均指向頭結點，每讀一個資料元素則申請一個新結點，将新結點插入到尾結點後，r 指向新結點