C#数据结构与算法总结
線性表
線性表是最簡單、最基本、最常用的數(shù)據(jù)結(jié)構(gòu)。線性表是線性結(jié)構(gòu)的抽象(Abstract)，線性結(jié)構(gòu)的特點(diǎn)是結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的線性關(guān)系。這種一對(duì)一的關(guān)系指的是數(shù)據(jù)元素之間的位置關(guān)系，即：
線性表就是位置有先后關(guān)系，一個(gè)接著一個(gè)排列的數(shù)據(jù)結(jié)構(gòu)。
CLR中的線性表
c# 1.1 提供了一個(gè)非泛型接口IList接口，接口中的項(xiàng)是object,實(shí)現(xiàn)了IList解扣子的類有ArrayList,ListDictionary,StringCollection,StringDictionary.
c# 2.0 提供了泛型的IList接口，實(shí)現(xiàn)了List接口的類有List
線性表的接口定義
interface IListDS<T> {int GetLength(); //求長度void Clear(); //清空操作bool IsEmpty();//判斷線性表是否為空void Add(T item);//附加操作void Insert(T item, int index); //插入操作T Delete(int index); //刪除操作T this[int index] { get; }//定義一個(gè)索引器 獲取元素T GetEle(int index);//取表元int Locate(T value);//按值查找 }線性表的實(shí)現(xiàn)方式
線性表的實(shí)現(xiàn)方式有下面幾種
- 順序表
- 單鏈表
- 雙向鏈表
- 循環(huán)鏈表
順序表
在計(jì)算機(jī)內(nèi)，保存線性表最簡單、最自然的方式，就是把表中的元素一個(gè)接一個(gè)地放進(jìn)順序的存儲(chǔ)單元，這就是線性表的順序存儲(chǔ)(Sequence Storage)。線性表的順序存儲(chǔ)是指在內(nèi)存中用一塊地址連續(xù)的空間依次存放線性表的數(shù)據(jù)元素，用這種方式存儲(chǔ)的線性表叫順序表(Sequence List)，如圖所示。順序表的特點(diǎn)是表中相鄰的數(shù)據(jù)元素在內(nèi)存中存儲(chǔ)位置也相鄰。
順序表的存儲(chǔ)
假設(shè)順序表中的每個(gè)數(shù)據(jù)元素占w個(gè)存儲(chǔ)單元，設(shè)第i個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為Loc(ai)，則有：
Loc(ai)= Loc(a1)+(i-1)*w 1≤i≤n式中的Loc(a1)表示第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)地址，也是順序表的起始存儲(chǔ)地址，稱為順序表的基地址(Base Address)。也就是說，只要知道順序表的基地址和每個(gè)數(shù)據(jù)元素所占的存儲(chǔ)單元的個(gè)數(shù)就可以求出順序表中任何一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址。并且，由于計(jì)算順序表中每個(gè)數(shù)據(jù)元素存儲(chǔ)地址的時(shí)間相同，所以順序表具有任意存取的特點(diǎn)。(可以在任意位置存取東西)
C#語言中的數(shù)組在內(nèi)存中占用的存儲(chǔ)空間就是一組連續(xù)的存儲(chǔ)區(qū)域，因此，數(shù)組具有任意存取的特點(diǎn)。所以，數(shù)組天生具有表示順序表的數(shù)據(jù)存儲(chǔ)區(qū)域的特性。
順序表的實(shí)現(xiàn)
class SeqList<T> : IListDS<T> {private T[] data;//用來存儲(chǔ)數(shù)據(jù)private int count = 0;public SeqList(int size){data = new T[size];}public SeqList() : this(10){}public T this[int index]{get{return GetEle(index);}}public void Add(T item){if (count == data.Length)//當(dāng)前數(shù)組已經(jīng)存滿{Console.WriteLine("當(dāng)前順序表已存滿，不允許再存入");}else{data[count] = item;count++;}}public void Clear(){count = 0;}public T GetEle(int index){if (index >= 0 && index <= count - 1){return data[index];}else{Console.WriteLine("超出順序表索引范圍");return default(T);}}public int GetLength(){return count;}public void Insert(T item, int index){for (int i = count - 1; i >= index; i--){data[i + 1] = data[i];}data[index] = item;count++;}public T Delete(int index){T temp = data[index];for (int i = index + 1; i < count; i++){data[i - 1] = data[i];}count--;return temp;}public bool IsEmpty(){return count == 0;}public int Locate(T value){for (int i = 0; i < count; i++){if (data[i].Equals(value)){return i;}}return -1;} }單鏈表
順序表是用地址連續(xù)的存儲(chǔ)單元順序存儲(chǔ)線性表中的各個(gè)數(shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰。因此，在順序表中查找任何一個(gè)位置上的數(shù)據(jù)元素非常方便，這是順序存儲(chǔ)的優(yōu)點(diǎn)。但是，在對(duì)順序表進(jìn)行插入和刪除時(shí)，需要通過移動(dòng)數(shù)據(jù)元素來實(shí)現(xiàn)，影響了運(yùn)行效率。線性表的另外一種存儲(chǔ)結(jié)構(gòu)——鏈?zhǔn)酱鎯?chǔ)(Linked Storage)，這樣的線性表叫鏈表(Linked List)。鏈表不要求邏輯上相鄰的數(shù)據(jù)元素在物理存儲(chǔ)位置上也相鄰，因此，在對(duì)鏈表進(jìn)行插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)元素，但同時(shí)也失去了順序表可隨機(jī)存儲(chǔ)的優(yōu)點(diǎn)。
單鏈表的存儲(chǔ)
鏈表是用一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中的數(shù)據(jù)元素（這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）。那么，怎么表示兩個(gè)數(shù)據(jù)元素邏輯上的相鄰關(guān)系呢？即如何表示數(shù)據(jù)元素之間的線性關(guān)系呢？為此，在存儲(chǔ)數(shù)據(jù)元素時(shí)，除了存儲(chǔ)數(shù)據(jù)元素本身的信息外，還要存儲(chǔ)與它相鄰的數(shù)據(jù)元素的存儲(chǔ)地址信息。這兩部分信息組成該數(shù)據(jù)元素的存儲(chǔ)映像(Image)，稱為結(jié)點(diǎn)(Node)。把存儲(chǔ)據(jù)元素本身信息的域叫結(jié)點(diǎn)的數(shù)據(jù)域(Data Domain)，把存儲(chǔ)與它相鄰的數(shù)據(jù)元素的存儲(chǔ)地址信息的域叫結(jié)點(diǎn)的引用域(Reference Domain)。因此，線性表通過每個(gè)結(jié)點(diǎn)的引用域形成了一根“鏈條”，這就是“鏈表”名稱的由來。
如果結(jié)點(diǎn)的引用域只存儲(chǔ)該結(jié)點(diǎn)直接后繼結(jié)點(diǎn)的存儲(chǔ)地址，則該鏈表叫單鏈表(Singly Linked List)。把該引用域叫 next。單鏈表結(jié)點(diǎn)的結(jié)構(gòu)如圖所示，圖中 data 表示結(jié)點(diǎn)的數(shù)據(jù)域。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
下圖是線性表(a1,a2,a3,a4,a5,a6)對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖。
另外一種表示形式
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-D01GDnI3-1581864714521)(https://s1.ax1x.com/2018/12/26/F2lFwn.jpg)]
單鏈表節(jié)點(diǎn)定義
class Node<T> {private T data;private Node<T> next;public Node(){data = default(T);next = null;}public Node(T value){this.data = value;this.next = null;}public Node(T value, Node<T> next){this.data = value;this.next = next;}public Node(Node<T> next){this.next = next;}public T Data{get { return data; }set { data = value; }}public Node<T> Next{get { return next; }set { next = value; }} }單鏈表實(shí)現(xiàn)
class LinkList<T> : IListDS<T> {private Node<T> head;public LinkList(){head = null;}public T this[int index]{get{return GetEle(index);}}public void Add(T item){Node<T> newNode = new Node<T>(item);if (head == null){head = newNode;}else{Node<T> temp = head;while (true){if (temp.Next != null){temp = temp.Next;}else{break;}}temp.Next = newNode;}}public void Clear(){head = null;}public T Delete(int index){T data = default(T);if (index == 0){data = head.Data;head = head.Next;}else{Node<T> temp = head;for (int i = 0; i < index - 1; i++){temp = temp.Next;}Node<T> preNode = temp;Node<T> currentNode = temp.Next;data = currentNode.Data;Node<T> nextNode = temp.Next.Next;preNode.Next = nextNode;}return data;}public T GetEle(int index){Node<T> temp = head;T data = temp.Data;if (index == 0){return data = temp.Data;}else{for (int i = 0; i < index; i++){temp = temp.Next;}data = temp.Data;}return data;}public int GetLength(){if (head == null) return 0;Node<T> temp = head;int count = 1;while (true){if (temp.Next != null){count++;temp = temp.Next;}else{break;}}return count;}public void Insert(T item, int index){Node<T> newNode = new Node<T>(item);if (index == 0){newNode.Next = head;head = newNode;}else{Node<T> temp = head;for (int i = 0; i < index - 1; i++){temp = temp.Next;}Node<T> preNode = temp;Node<T> currentNode = temp.Next;preNode.Next = newNode;newNode.Next = currentNode;}}public bool IsEmpty(){return head == null;}public int Locate(T value){Node<T> temp = head;if (temp == null){return -1;}else{int index = 0;while (true){if (temp.Data.Equals(value)){return index;}else{if (temp.Next != null){index++;temp = temp.Next;}else{break;}}}return -1;}} }雙向鏈表
前面介紹的單鏈表允許從一個(gè)結(jié)點(diǎn)直接訪問它的后繼結(jié)點(diǎn)，所以, 找直接后繼結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O(1)。但是,要找某個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，只能從表的頭引用開始遍歷各結(jié)點(diǎn)。如果某個(gè)結(jié)點(diǎn)的 Next 等于該結(jié)點(diǎn)，那么，這個(gè)結(jié)點(diǎn)就是該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。也就是說，找直接前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O(n)， n是單鏈表的長度。當(dāng)然，我們也可以在結(jié)點(diǎn)的引用域中保存直接前驅(qū)結(jié)點(diǎn)的地址而不是直接后繼結(jié)點(diǎn)的地址。這樣，找直接前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度只有 O(1)，但找直接后繼結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O(n)。如果希望找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的時(shí)間復(fù)雜度都是 O(1)，那么，需要在結(jié)點(diǎn)中設(shè)兩個(gè)引用域，一個(gè)保存直接前驅(qū)結(jié)點(diǎn)的地址，叫 prev，一個(gè)直接后繼結(jié)點(diǎn)的地址，叫 next，這樣的鏈表就是雙向鏈表(Doubly Linked List)。雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)示意圖如圖所示。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-UNn84VOH-1581864714522)(https://s1.ax1x.com/2018/12/26/Fg5Mhn.png)]
雙向鏈表節(jié)點(diǎn)實(shí)現(xiàn)
public class DbNode<T> {private T data; //數(shù)據(jù)域private DbNode<T> prev; //前驅(qū)引用域private DbNode<T> next; //后繼引用域//構(gòu)造器public DbNode(T val, DbNode<T> p){data = val;next = p;}//構(gòu)造器public DbNode(DbNode<T> p){next = p;}//構(gòu)造器public DbNode(T val){data = val;next = null;}//構(gòu)造器public DbNode(){data = default(T);next = null;}//數(shù)據(jù)域?qū)傩?/span>public T Data{get { return data; }set { data = value; }}//前驅(qū)引用域?qū)傩?/span>public DbNode<T> Prev{get { return prev; }set { prev = value; }}//后繼引用域?qū)傩?/span>public DbNode<T> Next{get { return next; }set { next = value; }} }雙向鏈表插入示意圖
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-yCTPlLtM-1581864714522)(https://s1.ax1x.com/2018/12/26/Fg5B1x.png)]
循環(huán)鏈表
有些應(yīng)用不需要鏈表中有明顯的頭尾結(jié)點(diǎn)。在這種情況下，可能需要方便地從最后一個(gè)結(jié)點(diǎn)訪問到第一個(gè)結(jié)點(diǎn)。此時(shí)，最后一個(gè)結(jié)點(diǎn)的引用域不是空引用，而是保存的第一個(gè)結(jié)點(diǎn)的地址（如果該鏈表帶結(jié)點(diǎn)，則保存的是頭結(jié)點(diǎn)的地址），也就是頭引用的值。帶頭結(jié)點(diǎn)的循環(huán)鏈表(Circular Linked List)如圖所示。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-Oihv4m5h-1581864714523)(https://s1.ax1x.com/2018/12/26/Fg52AH.png)]
棧和隊(duì)列
棧和隊(duì)列是非常重要的兩種數(shù)據(jù)結(jié)構(gòu)，在軟件設(shè)計(jì)中應(yīng)用很多。棧和隊(duì)列也是線性結(jié)構(gòu)，線性表、棧和隊(duì)列這三種數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素以及數(shù)據(jù)元素間的邏輯關(guān)系完全相同，差別是線性表的操作不受限制，而棧和隊(duì)列的操作受到限制。
棧的操作只能在表的一端進(jìn)行，隊(duì)列的插入操作在表的一端進(jìn)行而其它操作在表的另一端進(jìn)行，所以，把棧和隊(duì)列稱為操作受限的線性表。
棧
棧(Stack)是操作限定在表的尾端進(jìn)行的線性表。表尾由于要進(jìn)行插入、刪除等操作，所以，它具有特殊的含義，把表尾稱為棧頂（ Top），另一端是固定的，叫棧底（ Bottom）。當(dāng)棧中沒有數(shù)據(jù)元素時(shí)叫空棧(Empty Stack)。
棧通常記為： S= (a1,a2,…,an)，S是英文單詞stack的第 1 個(gè)字母。a1為棧底元素，an為棧頂元素。這n個(gè)數(shù)據(jù)元素按照a1,a2,…,an的順序依次入棧，而出棧的次序相反，an第一個(gè)出棧，a1最后一個(gè)出棧。所以，棧的操作是按照后進(jìn)先出(Last In First Out，簡稱LIFO)或先進(jìn)后出(First In Last Out，簡稱FILO)的原則進(jìn)行的，因此，棧又稱為LIFO表或FILO表。棧的操作示意圖如圖所示。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-y4ib2xIf-1581864714523)(https://s1.ax1x.com/2018/12/26/FggUzD.png)]
BCL中的棧
C#2.0 一下版本只提供了非泛型的Stack類(存儲(chǔ)object類型)
C#2.0 提供了泛型的Stack類
重要的方法如下：
棧的接口定義
public interface IStackDS<T> {int Count { get; }int GetLength(); //求棧的長度bool IsEmpty(); //判斷棧是否為空void Clear(); //清空操作void Push(T item); //入棧操作T Pop(); //出棧操作T Peek(); //取棧頂元素 }棧的存儲(chǔ)和代碼實(shí)現(xiàn)
順序棧
用一片連續(xù)的存儲(chǔ)空間來存儲(chǔ)棧中的數(shù)據(jù)元素(使用數(shù)組)，這樣的棧稱為順序棧(Sequence Stack)。類似于順序表，用一維數(shù)組來存放順序棧中的數(shù)據(jù)元素。棧頂指示器 top 設(shè)在數(shù)組下標(biāo)為 0 的端， top 隨著插入和刪除而變化，當(dāng)棧為空時(shí)，top=-1。下圖是順序棧的棧頂指示器 top 與棧中數(shù)據(jù)元素的關(guān)系圖。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-ngxwFMDC-1581864714524)(https://s1.ax1x.com/2018/12/26/FgRZgU.png)]
鏈棧
棧的另外一種存儲(chǔ)方式是鏈?zhǔn)酱鎯?chǔ)，這樣的棧稱為鏈棧(Linked Stack)。鏈棧通常用單鏈表來表示，它的實(shí)現(xiàn)是單鏈表的簡化。所以，鏈棧結(jié)點(diǎn)的結(jié)構(gòu)與單鏈表結(jié)點(diǎn)的結(jié)構(gòu)一樣。由于鏈棧的操作只是在一端進(jìn)行，為了操作方便，把棧頂設(shè)在鏈表的頭部，并且不需要頭結(jié)點(diǎn)。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-5nlAdDJY-1581864714524)(https://s1.ax1x.com/2018/12/26/FgRvI1.png)]
鏈棧結(jié)點(diǎn)實(shí)現(xiàn)
鏈棧結(jié)點(diǎn)代碼實(shí)現(xiàn)：
class Node<T> {private T data;private Node<T> next;public Node(){this.data = default(T);this.next = null;}public Node(T data){this.data = data;this.next = null;}public Node(T value, Node<T> next){this.data = value;this.next = next;}public Node(Node<T> next){this.data = default(T);this.next = next;}public T Data{set { data = value; }get { return data; }}public Node<T> Next{set { next = value; }get { return next; }} }鏈棧代碼實(shí)現(xiàn)
把鏈棧看作一個(gè)泛型類，類名為 LinkStack。 LinkStack類中有一個(gè)字段 top 表示棧頂指示器。由于棧只能訪問棧頂?shù)臄?shù)據(jù)元素，而鏈棧的棧頂指示器又不能指示棧的數(shù)據(jù)元素的個(gè)數(shù)。所以，求鏈棧的長度時(shí)，必須把棧中的數(shù)據(jù)元素一個(gè)個(gè)出棧，每出棧一個(gè)數(shù)據(jù)元素，計(jì)數(shù)器就增加 1，但這樣會(huì)破壞棧的結(jié)構(gòu)。為保留棧中的數(shù)據(jù)元素，需把出棧的數(shù)據(jù)元素先壓入另外一個(gè)棧，計(jì)算完長度后，再把數(shù)據(jù)元素壓入原來的棧。但這種算法的空間復(fù)雜度和時(shí)間復(fù)雜度都很高，所以，以上兩種算法都不是理想的解決方法。理想的解決方法是 LinkStack類增設(shè)一個(gè)字段 num 表示鏈棧中結(jié)點(diǎn)的個(gè)數(shù)。
class LinkStack<T> : IStackDS<T> {private Node<T> top;private int count = 0;public int Count{get{return count;}}public void Clear(){count = 0;top = null;}public int GetLength(){return count;}public bool IsEmpty(){return count == 0;}public T Peek(){return top.Data;}public T Pop(){T data = top.Data;top = top.Next;count--;return data;}public void Push(T item){Node<T> temp = new Node<T>(item);temp.Next = top;top = temp;count++;} }隊(duì)列
隊(duì)列(Queue)是插入操作限定在表的尾部而其它操作限定在表的頭部進(jìn)行的線性表。把進(jìn)行插入操作的表尾稱為隊(duì)尾(Rear)，把進(jìn)行其它操作的頭部稱為隊(duì)頭(Front)。當(dāng)隊(duì)列中沒有數(shù)據(jù)元素時(shí)稱為空隊(duì)列(Empty Queue)。
隊(duì)列通常記為： Q= (a1,a2,…,an)，Q是英文單詞queue的第 1 個(gè)字母。a1為隊(duì)頭元素，an為隊(duì)尾元素。這n個(gè)元素是按照a1,a2,…,an的次序依次入隊(duì)的，出對(duì)的次序與入隊(duì)相同，a1第一個(gè)出隊(duì)，an最后一個(gè)出隊(duì)。所以，對(duì)列的操作是按照先進(jìn)先出(First In First Out)或后進(jìn)后出( Last In Last Out)的原則進(jìn)行的，因此，隊(duì)列又稱為FIFO表或LILO表。隊(duì)列Q的操作示意圖如圖所示。
在實(shí)際生活中有許多類似于隊(duì)列的例子。比如，排隊(duì)取錢，先來的先取，后來的排在隊(duì)尾。
隊(duì)列的操作是線性表操作的一個(gè)子集。隊(duì)列的操作主要包括在隊(duì)尾插入元素、在隊(duì)頭刪除元素、取隊(duì)頭元素和判斷隊(duì)列是否為空等。與棧一樣，隊(duì)列的運(yùn)算是定義在邏輯結(jié)構(gòu)層次上的，而運(yùn)算的具體實(shí)現(xiàn)是建立在物理存儲(chǔ)結(jié)構(gòu)層次上的。因此，把隊(duì)列的操作作為邏輯結(jié)構(gòu)的一部分，每個(gè)操作的具體實(shí)現(xiàn)只有在確定了隊(duì)列的存儲(chǔ)結(jié)構(gòu)之后才能完成。隊(duì)列的基本運(yùn)算不是它的全部運(yùn)算，而是一些常用的基本運(yùn)算。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-FX5KlOEk-1581864714524)(https://s1.ax1x.com/2018/12/26/FgfCYq.png)]
BCL 中的隊(duì)列
C#2.0 以下版本提供了非泛型的Ｑueue類
C#2.0 提供了泛型Queue類
方法：
屬性
隊(duì)列接口定義
interface IQueue<T> {int Count { get; }int GetLeng();bool IsEmpty();void Clear();void Enqueue(T item);T Dequeue();T Peek(); }隊(duì)列的存儲(chǔ)和代碼實(shí)現(xiàn)
順序隊(duì)列
用一片連續(xù)的存儲(chǔ)空間來存儲(chǔ)隊(duì)列中的數(shù)據(jù)元素，這樣的隊(duì)列稱為順序隊(duì)列(Sequence Queue)。類似于順序棧，用一維數(shù)組來存放順序隊(duì)列中的數(shù)據(jù)元素。隊(duì)頭位置設(shè)在數(shù)組下標(biāo)為 0 的端，用 front 表示；隊(duì)尾位置設(shè)在數(shù)組的另一端，用 rear 表示。 front 和 rear 隨著插入和刪除而變化。當(dāng)隊(duì)列為空時(shí)， front=rear=-1。
圖是順序隊(duì)列的兩個(gè)指示器與隊(duì)列中數(shù)據(jù)元素的關(guān)系圖。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-gGCIaKwp-1581864714525)(https://s1.ax1x.com/2018/12/26/FgfEXF.png)]
循環(huán)順序隊(duì)列
如果再有一個(gè)數(shù)據(jù)元素入隊(duì)就會(huì)出現(xiàn)溢出。但事實(shí)上隊(duì)列中并未滿，還有空閑空間，把這種現(xiàn)象稱為“假溢出”。這是由于隊(duì)列“隊(duì)尾入隊(duì)頭出”的操作原則造成的。解決假溢出的方法是將順序隊(duì)列看成是首尾相接的循環(huán)結(jié)構(gòu)，頭尾指示器的關(guān)系不變，這種隊(duì)列叫循環(huán)順序隊(duì)列(Circular sequence Queue)。循環(huán)隊(duì)列如圖所示。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-GKnRoYFl-1581864714525)(https://s1.ax1x.com/2018/12/26/Fgfc7j.png)]
把循環(huán)順序隊(duì)列看作是一個(gè)泛型類，類名叫 CSeqStack，“ C”是英文單詞 circular 的第 1 個(gè)字母。 CSeqStack類實(shí)現(xiàn)了接口 IQueue。用數(shù)組來存儲(chǔ)循環(huán)順序隊(duì)列中的元素，在 CSeqStack類中用字段 data 來表示。用字段maxsize 表示循環(huán)順序隊(duì)列的容量， maxsize 的值可以根據(jù)實(shí)際需要修改，這通過CSeqStack類的構(gòu)造器中的參數(shù) size 來實(shí)現(xiàn)，循環(huán)順序隊(duì)列中的元素由 data[0]開始依次順序存放。字段 front 表示隊(duì)頭， front 的范圍是 0 到 maxsize-1。字段 rear表示隊(duì)尾，rear 的范圍也是 0 到 maxsize-1。如果循環(huán)順序隊(duì)列為空，front=rear=-1。當(dāng)執(zhí)行入隊(duì)列操作時(shí)需要判斷循環(huán)順序隊(duì)列是否已滿，如果循環(huán)順序隊(duì)列已滿，(rear + 1) % maxsize==front ， 循 環(huán) 順 序 隊(duì) 列 已 滿 不 能 插 入 元 素 。 所 以 ，CSeqStack類除了要實(shí)現(xiàn)接口 IQueue中的方法外，還需要實(shí)現(xiàn)判斷循環(huán)順序隊(duì)列是否已滿的成員方法。
鏈隊(duì)列
隊(duì)列的另外一種存儲(chǔ)方式是鏈?zhǔn)酱鎯?chǔ)，這樣的隊(duì)列稱為鏈隊(duì)列(Linked Queue)。同鏈棧一樣，鏈隊(duì)列通常用單鏈表來表示，它的實(shí)現(xiàn)是單鏈表的簡化。所以，鏈隊(duì)列的結(jié)點(diǎn)的結(jié)構(gòu)與單鏈表一樣，如圖所示。由于鏈隊(duì)列的操作只是在一端進(jìn)行，為了操作方便，把隊(duì)頭設(shè)在鏈表的頭部，并且不需要頭結(jié)點(diǎn)。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-x6cYEpNA-1581864714526)(https://s1.ax1x.com/2018/12/26/FgfqE9.png)]
鏈隊(duì)列結(jié)點(diǎn)類
class Node<T> {private T data;private Node<T> next;public Node(T data){this.data = data;}public T Data{set { data = value; }get { return data; }}public Node<T> Next{set { next = value; }get { return next; }} }鏈隊(duì)列代碼實(shí)現(xiàn)
把鏈隊(duì)列看作一個(gè)泛型類，類名為 LinkQueue。 LinkQueue類中有兩個(gè)字段 front 和 rear，表示隊(duì)頭指示器和隊(duì)尾指示器。由于隊(duì)列只能訪問隊(duì)頭的數(shù)據(jù)元素，而鏈隊(duì)列的隊(duì)頭指示器和隊(duì)尾指示器又不能指示隊(duì)列的元素個(gè)數(shù)，所以，與鏈棧一樣，在 LinkQueue類增設(shè)一個(gè)字段 num 表示鏈隊(duì)列中結(jié)點(diǎn)的個(gè)數(shù)。
class LinkQueue<T> : IQueue<T> {private Node<T> front;private Node<T> rear;private int count;public LinkQueue(){front = rear = null;count = 0;}public int Count{get { return count; }}public void Clear(){count = 0;rear = front = null;}public T Dequeue(){if (count == 0){Console.WriteLine("隊(duì)列為空，無法出隊(duì)");return default(T);}else if (count == 1){T temp = front.Data;front = rear = null;count = 0;return temp;}else{T temp = front.Data;front = front.Next;count--;return temp;}}public void Enqueue(T item){Node<T> temp = new Node<T>(item);if (count == 0){front = rear = temp;count = 1;}else{rear.Next = temp;rear = temp;count++;}}public int GetLeng(){return count;}public bool IsEmpty(){return count == 0;}public T Peek(){return front.Data;} }棧和隊(duì)列的應(yīng)用舉例
編程判斷一個(gè)字符串是否是回文。回文是指一個(gè)字符序列以中間字符為基準(zhǔn)兩邊字符完全相同，如字符序列“ ACBDEDBCA”是回文。
算法思想：判斷一個(gè)字符序列是否是回文，就是把第一個(gè)字符與最后一個(gè)字符相比較，第二個(gè)字符與倒數(shù)第二個(gè)字符比較，依次類推，第 i 個(gè)字符與第 n-i個(gè)字符比較。如果每次比較都相等，則為回文，如果某次比較不相等，就不是回文。因此，可以把字符序列分別入隊(duì)列和棧，然后逐個(gè)出隊(duì)列和出棧并比較出隊(duì)列的字符和出棧的字符是否相等，若全部相等則該字符序列就是回文，否則就不是回文。
using System; using System.Collections.Generic;class Program {static void Main(string[] args){string str = Console.ReadLine();Stack<char> stack = new Stack<char>();Queue<char> queue = new Queue<char>();for (int i = 0; i < str.Length; i++){stack.Push(str[i]);queue.Enqueue(str[i]);}bool isHui = true;while (stack.Count > 0){if (stack.Pop() != queue.Dequeue()){isHui = false;break;}}Console.WriteLine("是否是回文字符串：" + isHui);Console.ReadKey();} }串和數(shù)組
在應(yīng)用程序中使用最頻繁的類型是字符串。字符串簡稱串，是一種特殊的線性表，其特殊性在于串中的數(shù)據(jù)元素是一個(gè)個(gè)的字符。字符串在計(jì)算機(jī)的許多方面應(yīng)用很廣。如在匯編和高級(jí)語言的編譯程序中，源程序和目標(biāo)程序都是字符串?dāng)?shù)據(jù)。在事務(wù)處理程序中，顧客的信息如姓名、地址等及貨物的名稱、產(chǎn)地和規(guī)格等，都被作為字符串來處理。另外，字符串還具有自身的一些特性。因此，把字符串作為一種數(shù)據(jù)結(jié)構(gòu)來研究。
串
串的基本概念
串(String)由 n(n≥0)字符組成的有限序列。一般記為：
S=”c1c2…cn” (n≥0)
其中， S是串名，雙引號(hào)作為串的定界符，用雙引號(hào)引起來的字符序列是串值。 ci（ 1≤i≤n）可以是字母、數(shù)字或其它字符， n為串的長度，當(dāng)n=0 時(shí)，稱為空串(Empty String)。
串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串(Substring)。包含子串的串相應(yīng)地稱為主串。子串的第一個(gè)字符在主串中的位置叫子串的位置。如串s1”abcdefg”，它的長度是 7，串s2”cdef”的長度是 4， s2是s1的子串， s2的位置是 3。
如果兩個(gè)串的長度相等并且對(duì)應(yīng)位置的字符都相等，則稱這兩個(gè)串相等。而在 C#中，比較兩個(gè)串是否相等還要看串的語言文化等信息。
串的存儲(chǔ)和代碼實(shí)現(xiàn)
由于串中的字符都是連續(xù)存儲(chǔ)的，而在 C#中串具有恒定不變的特性，即字符串一經(jīng)創(chuàng)建，就不能將其變長、變短或者改變其中任何的字符。所以，這里不討論串的鏈?zhǔn)酱鎯?chǔ)，也不用接口來表示串的操作。同樣，把串看作是一個(gè)類，類名為 StringDS。取名為 StringDS 是為了和 C#自身的字符串類 String 相區(qū)別。類StringDS 只有一個(gè)字段，即存放串中字符序列的數(shù)組 data。由于串的運(yùn)算有很多，類 StringDS 中只包含部分基本的運(yùn)算。串類 StringDS中的方法和屬性:
class StringDS {private char[] data;//用來存放字符串/// <summary>/// 構(gòu)造器/// </summary>/// <param name="array">字符數(shù)組</param>public StringDS(char[] array){data = new char[array.Length];for (int i = 0; i < array.Length; i++){data[i] = array[i];}}/// <summary>/// 構(gòu)造器/// </summary>/// <param name="str">字符串</param>public StringDS(string str){data = new char[str.Length];for (int i = 0; i < str.Length; i++){data[i] = str[i];}}/// <summary>/// 索引器/// </summary>/// <param name="index">索引下標(biāo)</param>/// <returns></returns>public char this[int index]{get{return data[index];}}/// <summary>/// 獲得串的長度/// </summary>/// <returns>長度</returns>public int GetLength(){return data.Length;}/// <summary>/// 如果兩個(gè)字符串一樣長，返回0/// 如果當(dāng)前字符串小于s，那么返回-1/// 如果當(dāng)前字符串大于s，那么返回1/// </summary>/// <param name="">要比較的串</param>/// <returns></returns>public int Compare(StringDS s){int len = this.GetLength() > s.GetLength() ? this.GetLength() : s.GetLength(); //取得較短字符串；int index = -1;//用來記錄兩個(gè)字符串不相同字符的位置；for (int i = 0; i < len; i++){if (this[i] != s[i]){index = i;break;}}if (index != -1){if (this[index] > s[index]){return 1;}else{return -1;}}else{if (this.GetLength() == s.GetLength()){return 0;}else{if (this.GetLength() > s.GetLength()){return 1;}else{return -1;}}}}/// <summary>/// 剪切字符串/// </summary>/// <param name="index">剪切點(diǎn)的下標(biāo)</param>/// <param name="length">要剪切的長度</param>/// <returns></returns>public StringDS SubString(int index, int length){char[] newData = new char[length];for (int i = index; i < index + length; i++){newData[i - index] = data[i];}return new StringDS(newData);}/// <summary>/// 拼接字符串/// </summary>/// <param name="s1">要拼接的串1</param>/// <param name="s2">要拼接的串2</param>/// <returns></returns>public static StringDS Concat(StringDS s1, StringDS s2){char[] newData = new char[s1.GetLength() + s2.GetLength()];for (int i = 0; i < s1.GetLength(); i++){newData[i] = s1[i];}for (int i = s1.GetLength(); i < s1.GetLength() + s2.GetLength(); i++){newData[i] = s2[i - s1.GetLength()];}return new StringDS(newData);}/// <summary>/// 查找當(dāng)前串中與串s相同的第一個(gè)下標(biāo)/// </summary>/// <param name="s">要在當(dāng)前串中查找的串</param>/// <returns></returns>public int IndexOf(StringDS s){for (int i = 0; i <= this.GetLength() - s.GetLength(); i++){bool isEqual = true;for (int j = i; j < i + s.GetLength(); j++){if (this[j] != s[j - i]){isEqual = false;}}if (isEqual){return i;}else{continue;}}return -1;}/// <summary>/// 重寫ToString/// </summary>/// <returns>返回一個(gè)字符串</returns>public override string ToString(){return new string(data);} }C#中的串
在 C#中，一個(gè) String 表示一個(gè)恒定不變的字符序列集合。 String 類型是封閉類型，所以，它不能被其它類繼承，而它直接繼承自 object。因此， String 是引用類型，不是值類型，在托管堆上而不是在線程的堆棧上分配空間。 String 類型還 繼 承 了 IComparable 、 ICloneable 、 IConvertible 、 IComparable<string> 、IEnumerable<char>、 IEnumerable 和 IEquatable<string>等接口。 String 的恒定性指的是一個(gè)串一旦被創(chuàng)建，就不能將其變長、變短或者改變其中任何的字符。所以，當(dāng)我們對(duì)一個(gè)串進(jìn)行操作時(shí)，不能改變字符串，如在本書定義的 StringDS 類中，串連接、串插入和串刪除等操作的結(jié)果都是生成了新串而沒有改變原串。 C#也提供了 StringBuilder 類型來支持高效地動(dòng)態(tài)創(chuàng)建字符串。
在 C#中，創(chuàng)建串不能用 new 操作符，而是使用一種稱為字符串駐留的機(jī)制。
這是因?yàn)?C#語言將 String 看作是基元類型。基元類型是被編譯器直接支持的類型，可以在源代碼中用文本常量(Literal)來直接表達(dá)字符串。當(dāng) C#編譯器對(duì)源代碼進(jìn)行編譯時(shí)，將文本常量字符串存放在托管模塊的元數(shù)據(jù)中。而當(dāng) CLR 初始化時(shí)， CLR 創(chuàng)建一個(gè)空的散列表，其中的鍵是字符串，值為指向托管堆中字符串對(duì)象的引用。散列表就是哈希表。當(dāng) JIT編譯器編譯方法時(shí)，它會(huì)在散列表中查找每一個(gè)文本常量字符串。如果找不到，就會(huì)在托管堆中構(gòu)造一個(gè)新的 String 對(duì)象（指向字符串），然后將該字符串和指向該字符串對(duì)象的引用添加到散列表中；如果找到了，不會(huì)執(zhí)行任何操作。
數(shù)組
c#中的數(shù)組
數(shù)組是一種常用的數(shù)據(jù)結(jié)構(gòu)，可以看作是線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)，其特點(diǎn)是結(jié)構(gòu)中的數(shù)據(jù)元素可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，甚至可以是數(shù)組，但屬于同一數(shù)據(jù)類型。數(shù)組在許多高級(jí)語言里面都被作為固定類型來使用。
數(shù)組是 n(n≥1)個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素的有限序列。一維數(shù)組可以看作是一個(gè)線性表，二維數(shù)組可以看作是“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作是“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依次類推。
C#支持一維數(shù)組、多維數(shù)組及交錯(cuò)數(shù)組（數(shù)組的數(shù)組）。所有的數(shù)組類型都隱含繼承自System.Array。Array 是一個(gè)抽象類，本身又繼承自 System.Object。所以，數(shù)組總是在托管堆上分配空間，是引用類型。任何數(shù)組變量包含的是一個(gè)指向數(shù)組的引用，而非數(shù)組本身。當(dāng)數(shù)組中的元素的值類型時(shí)，該類型所需的內(nèi)存空間也作為數(shù)組的一部分而分配；當(dāng)數(shù)組的元素是引用類型時(shí)，數(shù)組包含是只是引用。
Array類中的常用方法
using System; using System.Collections; public abstract class Array : ICloneable, IList, ICollection, IEnumerable {//判斷 Array 是否具有固定大小。public bool IsFixedSize { get; }//獲取 Array 元素的個(gè)數(shù)。public int Length { get; }//獲取 Array 的秩（維數(shù)）。public int Rank { get; }//實(shí)現(xiàn)的 IComparable 接口，在.Array 中搜索特定元素。public static int BinarySearch(Array array, object value);//實(shí)現(xiàn)的 IComparable<T>泛型接口，在 Array 中搜索特定元素。public static int BinarySearch<T>(T[] array, T value);//實(shí)現(xiàn) IComparable 接口，在 Array 的某個(gè)范圍中搜索值。public static int BinarySearch(Array array, int index, int length, object value);//實(shí)現(xiàn)的 IComparable<T>泛型接口，在 Array 中搜索值。public static int BinarySearch<T>(T[] array, int index, int length, T value);//Array 設(shè)置為零、 false 或 null，具體取決于元素類型。public static void Clear(Array array, int index, int length);//System.Array 的淺表副本。public object Clone();//從第一個(gè)元素開始復(fù)制 Array 中的一系列元素//到另一 Array 中（從第一個(gè)元素開始）。public static void Copy(Array sourceArray,Array destinationArray, int length);//將一維 Array 的所有元素復(fù)制到指定的一維 Array 中。public void CopyTo(Array array, int index);//創(chuàng)建使用從零開始的索引、具有指定 Type 和維長的多維 Array。public static Array CreateInstance(Type elementType, params int[] lengths);//返回 ArrayIEnumerator。public IEnumerator GetEnumerator();//獲取 Array 指定維中的元素?cái)?shù)。public int GetLength(int dimension);//獲取一維 Array 中指定位置的值。public object GetValue(int index);//返回整個(gè)一維 Array 中第一個(gè)匹配項(xiàng)的索引。public static int IndexOf(Array array, object value);//返回整個(gè).Array 中第一個(gè)匹配項(xiàng)的索引。public static int IndexOf<T>(T[] array, T value);//返回整個(gè)一維 Array 中最后一個(gè)匹配項(xiàng)的索引。public static int LastIndexOf(Array array, object value);//反轉(zhuǎn)整個(gè)一維 Array 中元素的順序。public static void Reverse(Array array);//設(shè)置給一維 Array 中指定位置的元素。public void SetValue(object value, int index);//對(duì)整個(gè)一維 Array 中的元素進(jìn)行排序。public static void Sort(Array array); }簡單排序方法
排序
排序（Sort）是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，也是日常生活中經(jīng)常遇到的問題。例如，字典中的單詞是以字母的順序排列，否則，使用起來非常困難。同樣，存儲(chǔ)在計(jì)算機(jī)中的數(shù)據(jù)的次序，對(duì)于處理這些數(shù)據(jù)的算法的速度和簡便性而言，也具有非常深遠(yuǎn)的意義。
基本概念
排序是把一個(gè)記錄（在排序中把數(shù)據(jù)元素稱為記錄）集合或序列重新排列成按記錄的某個(gè)數(shù)據(jù)項(xiàng)值遞增（或遞減）的序列。
下表是一個(gè)學(xué)生成績表，其中某個(gè)學(xué)生記錄包括學(xué)號(hào)、姓名及計(jì)算機(jī)文化基礎(chǔ)、C 語言、數(shù)據(jù)結(jié)構(gòu)等課程的成績和總成績等數(shù)據(jù)項(xiàng)。在排序時(shí)，如果用總成績來排序，則會(huì)得到一個(gè)有序序列；如果以數(shù)據(jù)結(jié)構(gòu)成績進(jìn)行排序，則會(huì)得到另一個(gè)有序序列。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-7CevmBS6-1581864714526)(https://s1.ax1x.com/2018/12/26/FgXCbq.png)]
作為排序依據(jù)的數(shù)據(jù)項(xiàng)稱為“排序項(xiàng)”，也稱為記錄的關(guān)鍵碼(Keyword)。關(guān)鍵碼分為主關(guān)鍵碼(Primary Keyword)和次關(guān)鍵碼(Secondary Keyword)。一般地，若關(guān)鍵碼是主關(guān)鍵碼，則對(duì)于任意待排序的序列，經(jīng)排序后得到的結(jié)果是唯一的；若關(guān)鍵碼是次關(guān)鍵碼，排序的結(jié)果不一定唯一，這是因?yàn)榇判虻男蛄兄锌赡艽嬖诰哂邢嗤P(guān)鍵碼值的記錄。此時(shí)，這些記錄在排序結(jié)果中，它們之間的位置關(guān)系與排序前不一定保持一致。如果使用某個(gè)排序方法對(duì)任意的記錄序列按關(guān)鍵碼進(jìn)行排序，相同關(guān)鍵碼值的記錄之間的位置關(guān)系與排序前一致，則稱此排序方法是穩(wěn)定的；如果不一致，則稱此排序方法是不穩(wěn)定的。
由于待排序的記錄的數(shù)量不同，使得排序過程中涉及的存儲(chǔ)器不同，可將排序方法分為內(nèi)部排序（Internal Sorting）和外部排序（External Sorting）兩大類。
內(nèi)部排序指的是在排序的整個(gè)過程中，記錄全部存放在計(jì)算機(jī)的內(nèi)存中，并且在內(nèi)存中調(diào)整記錄之間的相對(duì)位置，在此期間沒有進(jìn)行內(nèi)、外存的數(shù)據(jù)交換。外部排序指的是在排序過程中，記錄的主要部分存放在外存中，借助于內(nèi)存逐步調(diào)整記錄之間的相對(duì)位置。在這個(gè)過程中，需要不斷地在內(nèi)、外存之間交換數(shù)據(jù)。
直接插入排序
插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分：第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外（讓數(shù)組多一個(gè)空間才有插入的位置），而第二部分就只包含這一個(gè)元素（即待插入元素）。在第一部分排序完成后，再將這個(gè)最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步將一個(gè)待排序的紀(jì)錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上，直到全部插入完為止。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-ufhWfSCk-1581864714527)(https://s1.ax1x.com/2018/12/26/FgX1IK.png)]
冒泡排序
冒泡排序(Bubble Sort)的基本思想是：將相鄰的記錄的關(guān)鍵碼進(jìn)行比較，若前面記錄的關(guān)鍵碼大于后面記錄的關(guān)鍵碼，則將它們交換，否則不交換。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-z8BCTzaR-1581864714527)(https://s1.ax1x.com/2018/12/26/FgXGGD.png)]
簡單選擇排序
簡單選擇排序(Simple Select Sort)算法的基本思想是：從待排序的記錄序列中選擇關(guān)鍵碼最小（或最大）的記錄并將它與序列中的第一個(gè)記錄交換位置；然后從不包括第一個(gè)位置上的記錄序列中選擇關(guān)鍵碼最小（或最大）的記錄并將它與序列中的第二個(gè)記錄交換位置；如此重復(fù)，直到序列中只剩下一個(gè)記錄為止。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-oDcM6OiN-1581864714527)(https://s1.ax1x.com/2018/12/26/FgX8PO.png)]
快速排序
快速排序由于排序效率綜合來說你幾種排序方法中效率較高，因此經(jīng)常被采用，再加上快速排序思想----分治法也確實(shí)實(shí)用，因此很多軟件公司的筆試面試，包括像騰訊，微軟等知名IT公司都喜歡考這個(gè)，還有大大小的程序方面的考試如軟考，考研中也常常出現(xiàn)快速排序的身影。
快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。
該方法的基本思想是：
快速排序詳細(xì)步驟
以一個(gè)數(shù)組作為示例，取區(qū)間第一個(gè)數(shù)為基準(zhǔn)數(shù)。
初始時(shí)，i = 0; j = 9; X = a[i] = 72
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-lqGdbCB6-1581864714528)(https://s1.ax1x.com/2018/12/26/FgjEwt.png)]
由于已經(jīng)將a[0]中的數(shù)保存到X中，可以理解成在數(shù)組a[0]上挖了個(gè)坑，可以將其它數(shù)據(jù)填充到這來。
從j開始向前找一個(gè)比X小或等于X的數(shù)。當(dāng)j=8，符合條件，將a[8]挖出再填到上一個(gè)坑a[0]中。a[0]=a[8]; i++; 這樣一個(gè)坑a[0]就被搞定了，但又形成了一個(gè)新坑a[8]，這怎么辦了？簡單，再找數(shù)字來填a[8]這個(gè)坑。這次從i開始向后找一個(gè)大于X的數(shù)，當(dāng)i=3，符合條件，將a[3]挖出再填到上一個(gè)坑中a[8]=a[3]; j–;
數(shù)組變?yōu)?#xff1a;
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-nkhzr6nQ-1581864714528)(https://s1.ax1x.com/2018/12/26/FgjAeI.png)]
i = 3; j = 7; X=72
再重復(fù)上面的步驟，先從后向前找，再從前向后找。
從j開始向前找，當(dāng)j=5，符合條件，將a[5]挖出填到上一個(gè)坑中，a[3] = a[5]; i++
從i開始向后找，當(dāng)i=5時(shí)，由于i==j退出。
此時(shí)，i = j = 5，而a[5]剛好又是上次挖的坑，因此將X填入a[5]。
數(shù)組變?yōu)?#xff1a;
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-H3fTJ27R-1581864714529)(https://s1.ax1x.com/2018/12/30/FhUB4S.png)]
可以看出a[5]前面的數(shù)字都小于它，a[5]后面的數(shù)字都大于它。因此再對(duì)a[0…4]和a[6…9]這二個(gè)子區(qū)間重復(fù)上述步驟就可以了。
快速排序代碼實(shí)現(xiàn)
using System;class Program {/// <summary>/// 對(duì)數(shù)組dataArray中索引從left到right之間的數(shù)做排序/// </summary>/// <param name="dataArray">要排序的數(shù)組</param>/// <param name="left">要排序數(shù)據(jù)的開始索引</param>/// <param name="right">要排序數(shù)據(jù)的結(jié)束索引</param>static void QuickSort(int[] dataArray, int left, int right){if (left < right){int x = dataArray[left];//基準(zhǔn)數(shù)， 把比它小或者等于它的 放在它的左邊，然后把比它大的放在它的右邊int i = left;int j = right;//用來做循環(huán)的標(biāo)志位while (true && i < j)//當(dāng)i==j的時(shí)候，說明我們找到了一個(gè)中間位置，這個(gè)中間位置就是基準(zhǔn)數(shù)應(yīng)該所在的位置 {//從后往前比較(從右向左比較) 找一個(gè)比x小（或者=）的數(shù)字，放在我們的坑里 坑位于i的位置while (true && i < j){if (dataArray[j] <= x) //找到了一個(gè)比基準(zhǔn)數(shù) 小于或者等于的數(shù)子，應(yīng)該把它放在x的左邊{dataArray[i] = dataArray[j];break;}else{j--;//向左移動(dòng) 到下一個(gè)數(shù)字，然后做比較}}//從前往后（從左向右）找一個(gè)比x大的數(shù)字，放在我們的坑里面 現(xiàn)在的坑位于j的位置while (true && i < j){if (dataArray[i] > x){dataArray[j] = dataArray[i];break;}else{i++;}}}//跳出循環(huán) 現(xiàn)在i==j i是中間位置dataArray[i] = x;// left -i- rightQuickSort(dataArray, left, i - 1);QuickSort(dataArray, i + 1, right);}}static void Main(string[] args){int[] data = new int[] { 42, 20, 17, 27, 13, 8, 17, 48 };QuickSort(data, 0, data.Length - 1);foreach (var temp in data){Console.Write(temp + " ");}Console.ReadKey();} }快排總結(jié)：
總結(jié)
以上是生活随笔為你收集整理的C#数据结构与算法总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 7-151 计算存款利息
- 下一篇： torch tensor去掉1维_维E、