推薦閱讀：

• ?我的CSDN
• ?我的博客園
• ?QQ群：704621321

1.常見的4類數(shù)據(jù)結(jié)構(gòu)： 1.集合。 2.線性結(jié)構(gòu)。3.樹形結(jié)構(gòu)。4.圖狀結(jié)構(gòu)。

2.數(shù)據(jù)結(jié)構(gòu)(Data Structure)簡(jiǎn)記為 DS，是一個(gè)二元組，DS = (D,R)

其中：D 是數(shù)據(jù)元素的有限集合，R 是數(shù)據(jù)元素之間關(guān)系的有限集合。

3.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種。C#語(yǔ)言中用數(shù)組來(lái)實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)。

4.算法的5個(gè)重要特征： 1.有窮性。2.確定性。3.可行性。4.輸入。5.輸出。

5.線性表：存在一對(duì)一的線性關(guān)系，一對(duì)一的關(guān)系指的是數(shù)據(jù)元素之間的位置關(guān)系

特點(diǎn)：
（1）除第一個(gè)位置的數(shù)據(jù) 元素外，其它數(shù)據(jù)元素位置的前面都只有一個(gè)數(shù)據(jù)元素

（2）除最后一個(gè)位置的 數(shù)據(jù)元素外，其它數(shù)據(jù)元素位置的后面都只有一個(gè)元素

6.線性表(List)是由 n(n≥0)個(gè)相同類型的數(shù)據(jù)元素構(gòu)成的有限序列。線性表通常記為：L=(a1,a2,…,ai-1,ai, ai+1,…,an)，a1是線性 表中第一個(gè)位置的數(shù)據(jù)元素。an是線性表中最后一個(gè)位置 的數(shù)據(jù)元素，。n為線性表的表長(zhǎng)，n=0 時(shí)的線性表被稱 為空表（Empty List）。

線性表的接口如下所示：

public interface IListDS<T> {int GetLength(); //求長(zhǎng)度void Clear(); //清空操作bool IsEmpty(); //判斷線性表是否為空void Append(T item); //附加操作 void Insert(T item, int i); //插入操作 T Delete(int i); //刪除操作 T GetElem(int i); //取表元 int Locate(T value); //按值查找 }

7.線性表的順序存儲(chǔ)是指在內(nèi)存中用一塊地址連續(xù)的空間依次存放線性表的數(shù)據(jù)元素， 用這種方式存儲(chǔ)的線性表叫順序表(Sequence List)。

順序表的特點(diǎn)是:表中相鄰的數(shù)據(jù)元素在內(nèi)存中存儲(chǔ)位置也相鄰。數(shù)據(jù)元素占w個(gè)存儲(chǔ)單元，設(shè)第i個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為L(zhǎng)oc(ai)，則有：Loc(ai)= Loc(a1)+(i-1)*w 1≤i≤n。

由于計(jì)算順序表中每個(gè)數(shù)據(jù)元素存儲(chǔ)地址的時(shí)間相同，所以順序表 具有隨機(jī)存取的特點(diǎn)。數(shù)組具有表示順序表的數(shù)據(jù)存儲(chǔ)區(qū)域的特 性。

last 表示順序 表中最后一個(gè)數(shù)據(jù)元素在數(shù)組中的位置。如果順序表中有數(shù)據(jù)元素時(shí)，last 的變 化范圍是 0 到 maxsize-1，如果順序表為空，last=-1

8.順序表類 SeqList的實(shí)現(xiàn)說(shuō)明如下所示：

public class SeqList<T> : IListDS<T> {private int maxsize; //順序表的容量private T[] data; //數(shù)組，用于存儲(chǔ)順序表中的數(shù)據(jù)元素private int last; //指示順序表最后一個(gè)元素的位置//索引器public T this[int index]{get { return data[index]; }set { data[index] = value; }}//最后一個(gè)數(shù)據(jù)元素位置屬性public int Last{get { return last; }}//容量屬性public int Maxsize{get { return maxsize; }set { maxsize = value; }}//構(gòu)造器public SeqList(int size){data = new T[size];maxsize = size;last = -1;}//求順序表的長(zhǎng)度public int GetLength(){return last + 1;}//清空順序表public void Clear(){last = -1;}//判斷順序表是否為空public bool IsEmpty(){if (last == -1){return true;}else{return false;}}//判斷順序表是否為滿public bool IsFull(){if (last == maxsize - 1){return true;}else{return false;}}//在順序表的末尾添加新元素public void Append(T item){if (IsFull()){System.Console.WriteLine("滿了");return;}data[++last] = item;}//在順序表的第i位置插入一個(gè)數(shù)據(jù)元素public void Insert(T item, int i){if (IsFull()){System.Console.WriteLine("滿了");return;}if (i < 1 || i> last+2){System.Console.WriteLine("越界");return;}if(i==last+2){data[last+1]=item;}else{for (int j = last; j >= i - 1; --j){data[j + 1] = data[j];}data[i - 1] = item;}++last;}//刪除順序表的第i個(gè)數(shù)據(jù)元素public T Delete(int i){T tmp = default(T);if (IsEmpty()){Console.WriteLine("List is empty");return tmp;}if (i < 1 || i > last + 1){Console.WriteLine("Position is error!");return tmp;}if (i == last + 1){tmp = data[last--];}else{tmp = data[i - 1];for (int j = i; j <= last; ++j){data[j] = data[j + 1];}}--last;return tmp;}//獲得順序表的第i個(gè)數(shù)據(jù)元素public T GetElem(int i){if (IsEmpty() || (i < 1) || (i > last + 1)){Console.WriteLine("List is empty or Position is error!");return default(T);}return data[i - 1];}//在順序表中查找值為value的數(shù)據(jù)元素public int Locate(T value){if (IsEmpty()){Console.WriteLine("List is Empty!");return -1;}int i = 0;for (i = 0; i <= last; ++i){if (value.Equals(data[i])){break;}}if (i > last){return -1;}return i;} }

9.順序表的倒置
算法思路：把第一個(gè)元素與最后一個(gè)元素交換，把第二個(gè)元素與倒數(shù)第二個(gè)元素交換。一般地，把第 i 個(gè)元素與第 n-i 個(gè)元素交換，i 的取值范圍是 0 到 n/2（n 為順序表的長(zhǎng)度）。
算法實(shí)現(xiàn)如下：

public void ReversSeqList(SeqList<int> L) {int tmp = 0;int len = L.GetLength();for (int i = 0; i<= len/2; ++i){tmp = L[i];L[i] = L[len - i]; 　　　 L[len - i] = tmp;} }

10按升序合并兩個(gè)表
算法思路：依次掃描 La 和 Lb 的數(shù)據(jù)元素，比較 La 和 Lb 當(dāng)前數(shù)據(jù)元素的 值，將較小值的數(shù)據(jù)元素賦給 Lc，如此直到一個(gè)順序表被掃描完，然后將未完 的那個(gè)順序表中余下的數(shù)據(jù)元素賦給 Lc 即可。Lc 的容量要能夠容納 La 和 Lb 兩個(gè)表相加的長(zhǎng)度。
C#實(shí)現(xiàn)如下：

public SeqList<int> Merge(Seqlist<int> La, SeqList<int> Lb) {SeqList<int> Lc = new SeqList<int>(La.Maxsize + Lb.Maxsize);int i = 0; int j = 0; int k = 0;//兩個(gè)表中都有數(shù)據(jù)元素while ((i <= (La.GetLength()-1))&& (j <= (Lb.GetLength()-1))){if (La[i] <Lb[j]){Lc.Append(La[i++]);}else{Lc.Append(Lb[j++]);} }//a表中還有數(shù)據(jù)元素while (i <= (La.GetLength() - 1)){Lc.Append(La[i++]);}//b表中還有數(shù)據(jù)元素while (j <= (Lb.GetLength() - 1)){Lc.Append(Lb[j++]);}return Lc; }

11已知一個(gè)存儲(chǔ)整數(shù)的順序表 La，試構(gòu)造順序表 Lb，要求順序表 Lb 中 只包含順序表 La 中所有值不相同的數(shù)據(jù)元素

算法思路：先把順序表 La 的第 1 個(gè)元素賦給順序表 Lb，然后從順序表 La 的第 2 個(gè)元素起，每一個(gè)元素與順序表 Lb 中的每一個(gè)元素進(jìn)行比較，如果不相 同，則把該元素附加到順序表 Lb 的末尾。

public SeqList<int> Purge(SeqList<int> La) {SeqList<int> Lb = new SeqList<int>(La.Maxsize);//將a表中的第1個(gè)數(shù)據(jù)元素賦給b表 Lb.Append(La[0]);//依次處理a表中的數(shù)據(jù)元素for (int i=1; i<=La.GetLength()-1; ++i){int j = 0;//查看b表中有無(wú)與a表中相同的數(shù)據(jù)元素for (j = 0; j<=Lb.GetLength()-1; ++j){//有相同的數(shù)據(jù)元素if (La[i].CompareTo(Lb[j]) == 0){break;}}//沒(méi)有相同的數(shù)據(jù)元素，將a表中的數(shù)據(jù)元素附加到b表的末尾。if(j>Lb.GetLength()-1){Lb.Append(La[i]);}}return Lb; }

鏈表進(jìn)行插入 和刪除時(shí)不需要移動(dòng)數(shù)據(jù)元素，但同時(shí)也失去了順序表可隨機(jī)存儲(chǔ)的優(yōu)點(diǎn)

12單鏈表結(jié)點(diǎn)類的實(shí)現(xiàn)：

public class Node<T> {private T data; //數(shù)據(jù)域private Node<T> next; //引用域//構(gòu)造器public Node(T val, Node<T> p){data = val;next = p;}//構(gòu)造器public Node(Node<T> p){next = p;}//構(gòu)造器public Node(T val){data = val;next = null;}//構(gòu)造器public Node(){data = default(T);next = null;}//數(shù)據(jù)域?qū)傩詐ublic T Data{get{return data;}set{ data = value; }}//引用域?qū)傩詐ublic Node<T> Next{get { return next; }set { next = value; }} }

13單鏈表類 LinkList的實(shí)現(xiàn)

public class LinkList<T> : IListDS<T> {private Node<T> head; //單鏈表的頭引用//頭引用屬性public Node<T> Head{get{ return head; }set{ head = value; }}//構(gòu)造器public LinkList(){head = null;}//求單鏈表的長(zhǎng)度public int GetLength(){Node<T> p = head;int len = 0;while (p != null){++len;p = p.Next;}return len;}//清空單鏈表public void Clear(){head = null;}//判斷單鏈表是否為空public bool IsEmpty(){if (head == null){return true;}else{return false;}}//在單鏈表的末尾添加新元素public void Append(T item){Node<T> q = new Node<T>(item); Node<T> p = new Node<T>();if (head == null){head = q;return;}p = head;while (p.Next != null){p = p.Next;}p.Next = q;}//在單鏈表的第i個(gè)結(jié)點(diǎn)的位置前插入一個(gè)值為item的結(jié)點(diǎn)public void Insert(T item, int i){if (IsEmpty() || i < 1){Console.WriteLine("List is empty or Position is error!");return;}if (i == 1){Node<T> q = new Node<T>(item);q.Next = head; head = q; return;}Node<T> p = head;Node<T> r = new Node<T>();int j = 1;while (p.Next != null&& j < i){r = p;p = p.Next;++j;}if (j == i){Node<T> q = new Node<T>(item);q.Next = p;r.Next = q;}}//在單鏈表的第i個(gè)結(jié)點(diǎn)的位置后插入一個(gè)值為item的結(jié)點(diǎn)public void InsertPost(T item, int i){if (IsEmpty() || i < 1){Console.WriteLine("List is empty or Position is error!");return;}if (i == 1){Node<T> q = new Node<T>(item);q.Next = head.Next; head.Next = q; return;}Node<T> p = head;int j = 1;while (p != null&& j < i){p = p.Next;++j;}if (j == i){Node<T> q = new Node<T>(item);q.Next = p.Next;p.Next = q;}}//刪除單鏈表的第i個(gè)結(jié)點(diǎn)public T Delete(int i){if (IsEmpty()|| i < 0){Console.WriteLine("Link is empty or Position is error!");return default(T);}Node<T> q = new Node<T>();if (i == 1){q = head;head = head.Next;return q.Data;}Node<T> p = head;int j = 1;while (p.Next != null&& j < i){++j;q = p;p = p.Next;}if (j == i){q.Next = p.Next;return p.Data;}else{Console.WriteLine("The ith node is not exist!");return default(T);}}//獲得單鏈表的第i個(gè)數(shù)據(jù)元素public T GetElem(int i){if (IsEmpty()){Console.WriteLine("List is empty!");return default(T);}Node<T> p = new Node<T>();p = head;int j = 1;while (p.Next != null&& j < i){++j;p = p.Next;}if (j == i){return p.Data;}else{Console.WriteLine("The ith node is not exist!");return default(T);}}//在單鏈表中查找值為value的結(jié)點(diǎn)public int Locate(T value){if(IsEmpty()){Console.WriteLine("List is Empty!");return -1;}Node<T> p = new Node<T>();p = head;int i = 1;while (!p.Data.Equals(value)&& p.Next != null){P = p.Next;++i;}return i;} }

總結(jié)

以上是生活随笔為你收集整理的数据结构（C#版本）_基本概念及线性表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。