算法系列15天速成 第八天 線性表【下】
一：線性表的簡單回顧
上一篇跟大家聊過“線性表"順序存儲，通過實驗，大家也知道，如果我每次向順序表的頭部插入元素，都會引起痙攣，效率比較低下，第二點我們用順序存儲時，容易受到長度的限制，反之就會造成空間資源的浪費。
二：鏈表
對于順序表存在的若干問題，鏈表都給出了相應的解決方案。
1. 概念：其實鏈表的“每個節(jié)點”都包含一個”數(shù)據(jù)域“和”指針域“。
”數(shù)據(jù)域“中包含當前的數(shù)據(jù)。
”指針域“中包含下一個節(jié)點的指針。
”頭指針”也就是head，指向頭結(jié)點數(shù)據(jù)。
“末節(jié)點“作為單向鏈表，因為是最后一個節(jié)點，通常設置指針域為null。
代碼段如下：
#region 鏈表節(jié)點的數(shù)據(jù)結(jié)構(gòu)
/// <summary>
/// 鏈表節(jié)點的數(shù)據(jù)結(jié)構(gòu)
/// </summary>
public class Node<T>
{
7/// <summary>
/// 節(jié)點的數(shù)據(jù)域
/// </summary>
public T data;
/// <summary>
/// 節(jié)點的指針域
/// </summary>
public Node<T> next;
}
#endregion
2.常用操作：
鏈表的常用操作一般有：
①添加節(jié)點到鏈接尾，②添加節(jié)點到鏈表頭，③插入節(jié)點。
④刪除節(jié)點，⑤按關鍵字查找節(jié)點，⑥取鏈表長度。
<1> 添加節(jié)點到鏈接尾：
前面已經(jīng)說過，鏈表是采用指針來指向下一個元素，所以說要想找到鏈表最后一個節(jié)點，必須從頭指針開始一步一步向后找,少不了一個for循環(huán)，所以時間復雜度為O(N)。
代碼段如下：
#region 將節(jié)點添加到鏈表的末尾
/// <summary>
/// 將節(jié)點添加到鏈表的末尾
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <param name="data"></param>
/// <returns></returns>
public Node<T> ChainListAddEnd<T>(Node<T> head, T data)
{
Node<T> node = new Node<T>();
node.data = data;
node.next = null;
///說明是一個空鏈表
if (head == null)
{
head = node;
return head;
}
//獲取當前鏈表的最后一個節(jié)點
ChainListGetLast(head).next = node;
return head;
}
#endregion
#region 得到當前鏈表的最后一個節(jié)點
/// <summary>
/// 得到當前鏈表的最后一個節(jié)點
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <returns></returns>
public Node<T> ChainListGetLast<T>(Node<T> head)
{
if (head.next == null)
return head;
return ChainListGetLast(head.next);
}
#endregion
<2> 添加節(jié)點到鏈表頭:
大家現(xiàn)在都知道，鏈表是采用指針指向的，要想將元素插入鏈表頭，其實還是很簡單的，
思想就是：① 將head的next指針給新增節(jié)點的next。②將整個新增節(jié)點給head的next。
所以可以看出，此種添加的時間復雜度為O(1)。
效果圖：
代碼段如下：
1#region 將節(jié)點添加到鏈表的開頭
/// <summary>
/// 將節(jié)點添加到鏈表的開頭
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="chainList"></param>
/// <param name="data"></param>
/// <returns></returns>
public Node<T> ChainListAddFirst<T>(Node<T> head, T data)
{
Node<T> node = new Node<T>();
node.data = data;
node.next = head;
head = node;
return head;
}
#endregion
<3> 插入節(jié)點:
其實這個思想跟插入到”首節(jié)點“是一個模式，不過多了一步就是要找到當前節(jié)點的操作。然后找到
這個節(jié)點的花費是O(N）。上圖上代碼，大家一看就明白。
效果圖：
代碼段：
#region 將節(jié)點插入到指定位置
/// <summary>
/// 將節(jié)點插入到指定位置
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <param name="currentNode"></param>
/// <param name="data"></param>
/// <returns></returns>
public Node<T> ChainListInsert<T, W>(Node<T> head, string key, Func<T, W> where, T data) where W : IComparable
{
if (head == null)
return null;
if (where(head.data).CompareTo(key) == 0)
{
Node<T> node = new Node<T>();
node.data = data;
node.next = head.next;
head.next = node;
}
ChainListInsert(head.next, key, where, data);
return head;
}
#endregion
<4> 刪除節(jié)點:
這個也比較簡單，不解釋，圖跟代碼更具有說服力，口頭表達反而讓人一頭霧水。
當然時間復雜度就為O(N)，N是來自于查找到要刪除的節(jié)點。
效果圖：
代碼段：
#region 將指定關鍵字的節(jié)點刪除
/// <summary>
/// 將指定關鍵字的節(jié)點刪除
/// </summary>
/// <typeparam name="T"></typeparam>
/// <typeparam name="W"></typeparam>
/// <param name="head"></param>
/// <param name="key"></param>
/// <param name="where"></param>
/// <param name="data"></param>
/// <returns></returns>
public Node<T> ChainListDelete<T, W>(Node<T> head, string key, Func<T, W> where) where W : IComparable
{
if (head == null)
return null;
//這是針對只有一個節(jié)點的解決方案
if (where(head.data).CompareTo(key) == 0)
{
if (head.next != null)
head = head.next;
else
return head = null;
}
else
{
//判斷一下此節(jié)點是否是要刪除的節(jié)點的前一節(jié)點
while (head.next != null && where(head.next.data).CompareTo(key) == 0)
{
//將刪除節(jié)點的next域指向前一節(jié)點
head.next = head.next.next;
}
}
ChainListDelete(head.next, key, where);
return head;
}
#endregion
<5> 按關鍵字查找節(jié)點：
這個思想已經(jīng)包含到“插入節(jié)點”和“刪除節(jié)點”的具體運用中的，其時間復雜度為O(N)。
代碼段：
#region 通過關鍵字查找指定的節(jié)點
/// <summary>
/// 通過關鍵字查找指定的節(jié)點
/// </summary>
/// <typeparam name="T"></typeparam>
/// <typeparam name="W"></typeparam>
/// <param name="head"></param>
/// <param name="key"></param>
/// <param name="where"></param>
/// <returns></returns>
public Node<T> ChainListFindByKey<T, W>(Node<T> head, string key, Func<T, W> where) where W : IComparable
{
if (head == null)
return null;
if (where(head.data).CompareTo(key) == 0)
return head;
return ChainListFindByKey<T, W>(head.next, key, where);
}
#endregion
<6> 取鏈表長度:
在單鏈表的操作中，取鏈表長度還是比較糾結(jié)的，因為他不像順序表那樣是在內(nèi)存中連續(xù)存儲的，
因此我們就糾結(jié)的遍歷一下鏈表的總長度。時間復雜度為O(N)。
代碼段：
#region 獲取鏈表的長度
/// <summary>
///// 獲取鏈表的長度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <returns></returns>
public int ChanListLength<T>(Node<T> head)
{
int count = 0;
while (head != null)
{
++count;
head = head.next;
}
return count;
}
#endregion
好了，最后上一下總的運行代碼：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ChainList
{
class Program
{
static void Main(string[] args)
{
ChainList chainList = new ChainList();
Node<Student> node = null;
Console.WriteLine("將三條數(shù)據(jù)添加到鏈表的尾部:\n");
//將數(shù)據(jù)添加到鏈表的尾部
node = chainList.ChainListAddEnd(node, new Student() { ID = 2, Name = "hxc520", Age = 23 });
node = chainList.ChainListAddEnd(node, new Student() { ID = 3, Name = "博客園", Age = 33 });
node = chainList.ChainListAddEnd(node, new Student() { ID = 5, Name = "一線碼農(nóng)", Age = 23 });
Dispaly(node);
Console.WriteLine("將ID=1的數(shù)據(jù)插入到鏈表開頭:\n");
//將ID=1的數(shù)據(jù)插入到鏈表開頭
node = chainList.ChainListAddFirst(node, new Student() { ID = 1, Name = "i can fly", Age = 23 });
Dispaly(node);
Console.WriteLine("查找Name=“一線碼農(nóng)”的節(jié)點\n");
//查找Name=“一線碼農(nóng)”的節(jié)點
var result = chainList.ChainListFindByKey(node, "一線碼農(nóng)", i => i.Name);
DisplaySingle(node);
Console.WriteLine("將”ID=4“的實體插入到“博客園”這個節(jié)點的之后\n");
//將”ID=4“的實體插入到"博客園"這個節(jié)點的之后
node = chainList.ChainListInsert(node, "博客園", i => i.Name, new Student() { ID = 4, Name = "51cto", Age = 30 });
Dispaly(node);
Console.WriteLine("刪除Name=‘51cto‘的節(jié)點數(shù)據(jù)\n");
//刪除Name=‘51cto‘的節(jié)點數(shù)據(jù)
node = chainList.ChainListDelete(node, "51cto", i => i.Name);
Dispaly(node);
Console.WriteLine("獲取鏈表的個數(shù):" + chainList.ChanListLength(node));
}
//輸出數(shù)據(jù)
public static void Dispaly(Node<Student> head)
{
Console.WriteLine("******************* 鏈表數(shù)據(jù)如下 *******************");
var tempNode = head;
while (tempNode != null)
{
Console.WriteLine("ID:" + tempNode.data.ID + ", Name:" + tempNode.data.Name + ",Age:" + tempNode.data.Age);
tempNode = tempNode.next;
}
Console.WriteLine("******************* 鏈表數(shù)據(jù)展示完畢 *******************\n");
}
//展示當前節(jié)點數(shù)據(jù)
public static void DisplaySingle(Node<Student> head)
{
if (head != null)
Console.WriteLine("ID:" + head.data.ID + ", Name:" + head.data.Name + ",Age:" + head.data.Age);
else
Console.WriteLine("未查找到數(shù)據(jù)！");
}
}
#region 學生數(shù)據(jù)實體
/// <summary>
/// 學生數(shù)據(jù)實體
/// </summary>
public class Student
{
public int ID { get; set; }
public string Name { get; set; }
public int Age { get; set; }
}
#endregion
#region 鏈表節(jié)點的數(shù)據(jù)結(jié)構(gòu)
/// <summary>
/// 鏈表節(jié)點的數(shù)據(jù)結(jié)構(gòu)
/// </summary>
public class Node<T>
{
/// <summary>
/// 節(jié)點的數(shù)據(jù)域
/// </summary>
public T data;
/// <summary>
/// 節(jié)點的指針域
/// </summary>
public Node<T> next;
}
#endregion
#region 鏈表的相關操作
/// <summary>
/// 鏈表的相關操作
/// </summary>
public class ChainList
{
#region 將節(jié)點添加到鏈表的末尾
/// <summary>
/// 將節(jié)點添加到鏈表的末尾
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <param name="data"></param>
/// <returns></returns>
public Node<T> ChainListAddEnd<T>(Node<T> head, T data)
{
Node<T> node = new Node<T>();
node.data = data;
node.next = null;
///說明是一個空鏈表
if (head == null)
{
head = node;
return head;
}
//獲取當前鏈表的最后一個節(jié)點
ChainListGetLast(head).next = node;
return head;
}
#endregion
#region 將節(jié)點添加到鏈表的開頭
/// <summary>
/// 將節(jié)點添加到鏈表的開頭
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="chainList"></param>
/// <param name="data"></param>
/// <returns></returns>
public Node<T> ChainListAddFirst<T>(Node<T> head, T data)
{
Node<T> node = new Node<T>();
node.data = data;
node.next = head;
head = node;
return head;
}
#endregion
#region 將節(jié)點插入到指定位置
/// <summary>
/// 將節(jié)點插入到指定位置
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <param name="currentNode"></param>
/// <param name="data"></param>
/// <returns></returns>
public Node<T> ChainListInsert<T, W>(Node<T> head, string key, Func<T, W> where, T data) where W : IComparable
{
if (head == null)
return null;
if (where(head.data).CompareTo(key) == 0)
{
Node<T> node = new Node<T>();
node.data = data;
node.next = head.next;
head.next = node;
}
ChainListInsert(head.next, key, where, data);
return head;
}
#endregion
#region 將指定關鍵字的節(jié)點刪除
/// <summary>
/// 將指定關鍵字的節(jié)點刪除
/// </summary>
/// <typeparam name="T"></typeparam>
/// <typeparam name="W"></typeparam>
/// <param name="head"></param>
/// <param name="key"></param>
/// <param name="where"></param>
/// <param name="data"></param>
/// <returns></returns>
public Node<T> ChainListDelete<T, W>(Node<T> head, string key, Func<T, W> where) where W : IComparable
{
if (head == null)
return null;
//這是針對只有一個節(jié)點的解決方案
if (where(head.data).CompareTo(key) == 0)
{
if (head.next != null)
head = head.next;
else
return head = null;
}
else
{
//判斷一下此節(jié)點是否是要刪除的節(jié)點的前一節(jié)點
if (head.next != null && where(head.next.data).CompareTo(key) == 0)
{
//將刪除節(jié)點的next域指向前一節(jié)點
head.next = head.next.next;
}
}
ChainListDelete(head.next, key, where);
return head;
}
#endregion
#region 通過關鍵字查找指定的節(jié)點
/// <summary>
/// 通過關鍵字查找指定的節(jié)點
/// </summary>
/// <typeparam name="T"></typeparam>
/// <typeparam name="W"></typeparam>
/// <param name="head"></param>
/// <param name="key"></param>
/// <param name="where"></param>
/// <returns></returns>
public Node<T> ChainListFindByKey<T, W>(Node<T> head, string key, Func<T, W> where) where W : IComparable
{
if (head == null)
return null;
if (where(head.data).CompareTo(key) == 0)
return head;
return ChainListFindByKey<T, W>(head.next, key, where);
}
#endregion
#region 獲取鏈表的長度
/// <summary>
///// 獲取鏈表的長度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <returns></returns>
public int ChanListLength<T>(Node<T> head)
{
int count = 0;
while (head != null)
{
++count;
head = head.next;
}
return count;
}
#endregion
#region 得到當前鏈表的最后一個節(jié)點
/// <summary>
/// 得到當前鏈表的最后一個節(jié)點
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <returns></returns>
public Node<T> ChainListGetLast<T>(Node<T> head)
{
if (head.next == null)
return head;
return ChainListGetLast(head.next);
}
#endregion
}
#endregion
}
運行結(jié)果：
當然，單鏈表操作中有很多是O(N)的操作，這給我們帶來了尷尬的局面，所以就有了很多的優(yōu)化方案，比如：雙向鏈表，循環(huán)鏈表。靜態(tài)鏈表等等，這些希望大家在懂得單鏈表的情況下待深一步的研究。
相關文章
這篇文章主要介紹了Git常用場景使用-分支操作,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-08-08
這篇文章主要介紹了git提交驗證規(guī)范并自動生成日志文件的相關知識，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-11-11
在處理頁面事件時，我們會經(jīng)常會碰到這樣的情況：當我們在提交一項頁面表單時，在提交成功后，當我們試圖按F5刷新頁面時，數(shù)據(jù)會再次的被重復提交2012-10-10
編寫高質(zhì)量代碼的30條黃金守則(首選隱式類型轉(zhuǎn)換)
這篇文章主要介紹了編寫高質(zhì)量代碼的30條黃金守則(首選隱式類型轉(zhuǎn)換),本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-08-08
解決HTTP服務響應數(shù)據(jù)不完整響應數(shù)據(jù)截斷的問題
這篇文章主要介紹了HTTP服務響應數(shù)據(jù)不完整響應數(shù)據(jù)截斷的問題及解決方法，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-03-03
VSCode提高 Node 和 Vue 開發(fā)效率的插件推薦
工欲善其事必先利其器，以下是本人為Node 和 Vue開發(fā)收集的vscode插件，有需要的話趕緊mark起來吧~2020-03-03
代碼著色之SyntaxHighlighter項目(最流行的代碼高亮)
dp.SyntaxHighlighter。它可以在網(wǎng)頁中對各種程序源代碼語法進行加亮顯示。支持當前流 行的各種編程語言：C#、CSS、C++、Delphi、Java、JavaScript、PHP、Python、Ruby、SQL、Visual Basic、XML / HTML等2014-04-04
這篇文章主要介紹了推薦四款可視化工具(解決99%的可視化大屏需求),小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-04-04
使用json顯示日期時，細心的朋友會發(fā)現(xiàn)帶T字母，就是天數(shù)跟小時數(shù)之間出現(xiàn)了一個T，下面為大家介紹下具體的解決方法2013-10-10
Chrome 51 開始，瀏覽器的 Cookie 新增加了一個SameSite屬性，用來防止 CSRF 攻擊和用戶追蹤，下面在通過本文給大家詳細介紹下SameSite 屬性的相關知識，感興趣的朋友一起看看吧2021-10-10