热门：网页模板.net视频教程JQueryMVCjsonExtJs源码示例三级联动JQuery菜单
您现在的位置：.Net中文社区>> .Net编程>>正文内容

C#数据结构之线性表

发布时间：2010年03月30日点击数： 次生鱼片

一：介绍
线性表是最基本，最简单也是应用最广的数据结构。线性表是线性数据的抽象，其特点是结构中的数据元素之间存在着一对一的线性关系，
是一种数据元素序列的数据结构。
线性表是由n>=0个相同的数据元素构成的有限序列，有限指的是线性表中的数据元素个数是有限的，并且每一个数据元素都有自己的位置。
二：代码实现
1. 线性表的一些通用操作，我们统一为接口：

  1. public interface IListDS<T> 
  2. { 
  3.         int GetLength(); 
  4.         void Clear(); 
  5.         bool IsEmpty(); 
  6.         void Append(T item); 
  7.         void Insert(T item, int i); 
  8.         T Delete(int i); 
  9.         T GetElem(int i); 
  10.         int Locate(T value); 
  11.         void Reverse(); 
  12. } 

2. 线性表中常见的有顺序表，单链表，双向链表，循环链表。
3. 顺序表

  1. using System; 
  2. using System.Collections.Generic; 
  3. using System.Linq; 
  4. using System.Text;  
  5. namespace SeqDS 
  6. { 
  7.     public class SeqList<T>:IListDS<T> 
  8.     { 
  9.         private int maxsize;//顺序表的容量 
  10.         private T[] data;//数组，用于存储顺序表中的数据元素 
  11.         private int last;//指示顺序表最后一个元素的位置  
  12.         //索引器 
  13.         public T this[int index] 
  14.         { 
  15.             get { return data[index]; } 
  16.             set { data[index] = value; } 
  17.         }  
  18.         public int Last 
  19.         { 
  20.             get { return last; } 
  21.         }  
  22.         public int Maxsize 
  23.         { 
  24.             get{return maxsize;} 
  25.             set { maxsize = value; } 
  26.         }  
  27.         //构造器 
  28.         public SeqList(int size) 
  29.         { 
  30.             data = new T[size]; 
  31.             maxsize = size; 
  32.             last = -1; 
  33.         }  
  34.         //求顺序表的长度 
  35.         public int GetLength() 
  36.         { 
  37.             return last + 1; 
  38.         }  
  39.         //清空顺序表 
  40.         public void Clear() 
  41.         { 
  42.             last = -1; 
  43.         }  
  44.         //判断顺序表是否为空 
  45.         public bool IsEmpty() 
  46.         { 
  47.             if (last == -1) 
  48.                 return true; 
  49.             else 
  50.                 return false; 
  51.         }  
  52.         //判断顺序表是否为满 
  53.         public bool IsFull() 
  54.         { 
  55.             if (last == maxsize - 1) 
  56.                 return true; 
  57.             else 
  58.                 return false; 
  59.         }  
  60.         //在顺序表的末尾添加新元素 
  61.         public void Append(T item) 
  62.         { 
  63.             if (IsFull()) 
  64.             { 
  65.                 Console.WriteLine("List is full"); 
  66.                 return; 
  67.             } 
  68.             data[++last] = item; 
  69.         }  
  70.         //在顺序表的第i个数据元素的位置插入一个数据元素 
  71.         public void Insert(T item, int i) 
  72.         { 
  73.             if (IsFull()) 
  74.             { 
  75.                 Console.WriteLine("List is full"); 
  76.                 return; 
  77.             } 
  78.             if (i < 1 || i > last + 2) 
  79.             { 
  80.                 Console.WriteLine("Position is error!"); 
  81.                 return; 
  82.             } 
  83.             if (i == last + 2) 
  84.             { 
  85.                 data[last + 1] = item; 
  86.             } 
  87.             else 
  88.             { 
  89.                 for (int j = last; j > i - 1; --j) 
  90.                 { 
  91.                     data[j + 1] = data[j]; 
  92.                 } 
  93.                 data[i - 1] = item; 
  94.             } 
  95.             ++last; 
  96.         }  
  97.         //删除顺序表的第i个数据元素 
  98.         public T Delete(int i) 
  99.         { 
  100.             T tmp = default(T); 
  101.             if (IsEmpty()) 
  102.             { 
  103.                 Console.WriteLine("List is empty!"); 
  104.                 return tmp; 
  105.             } 
  106.             if (i < 1 || i > last + 1) 
  107.             { 
  108.                 Console.WriteLine("Position is error!"); 
  109.                 return tmp; 
  110.             } 
  111.             if (i == last + 1) 
  112.             { 
  113.                 tmp = data[last--]; 
  114.             } 
  115.             else 
  116.             { 
  117.                 tmp = data[i - 1]; 
  118.                 for (int j = i; j <= last; ++j) 
  119.                 { 
  120.                     data[j] = data[j + 1]; 
  121.                 } 
  122.             } 
  123.   
  124.             --last; 
  125.             return tmp; 
  126.         }  
  127.         //获得顺序表的第i个数据元素 
  128.         public T GetElem(int i) 
  129.         { 
  130.             if (IsEmpty() || (i < 1) || (i > last + 1)) 
  131.             { 
  132.                 Console.WriteLine("List is empty or Position is erroe!"); 
  133.                 return default(T); 
  134.             } 
  135.   
  136.             return data[i - 1]; 
  137.         }  
  138.         //在顺序表中查找值为value的数据元素 
  139.         public int Locate(T value) 
  140.         { 
  141.             if (IsEmpty()) 
  142.             { 
  143.                 Console.WriteLine("List is Empty!"); 
  144.                 return -1; 
  145.             } 
  146.             int i = 0; 
  147.             for (i = 0; i <= last; ++i) 
  148.             { 
  149.                 if (value.Equals(data[i])) 
  150.                     break; 
  151.             } 
  152.             if (i > last) 
  153.                 return -1; 
  154.             return i; 
  155.         }  
  156.         public void Reverse() 
  157.         { 
  158.             T tmp = default(T); 
  159.             int length = GetLength(); 
  160.             for (var i = 0; i < length / 2; i++) 
  161.             { 
  162.                 tmp = data[i]; 
  163.                 data[i] = data[length - i - 1]; 
  164.                 data[length - i - 1] = tmp;  
  165.             } 
  166.         }  
  167.     } 
  168. } 

4. 单向链表 

  1. using System; 
  2. using System.Collections.Generic; 
  3. using System.Linq; 
  4. using System.Text;  
  5. namespace SeqDS 
  6. { 
  7.     public class LinkList<T>:IListDS<T> 
  8.     { 
  9.         private Node<T> head; 
  10.         public Node<T> Head 
  11.         { 
  12.             get { return head; } 
  13.             set { head = value; } 
  14.         }  
  15.         public LinkList() 
  16.         { 
  17.             head = null; 
  18.         }  
  19.         public int GetLength() 
  20.         { 
  21.             Node<T> p = head; 
  22.             int len = 0; 
  23.             while (p != null) 
  24.             { 
  25.                 ++len; 
  26.                 p = p.Next; 
  27.             } 
  28.             return len; 
  29.         }  
  30.         public bool IsEmpty() 
  31.         { 
  32.             if (head == null) 
  33.                 return true; 
  34.             else 
  35.                 return false; 
  36.         }  
  37.         public void Clear() 
  38.         { 
  39.             head = null; 
  40.         }  
  41.         public void Append(T item) 
  42.         { 
  43.             Node<T> q = new Node<T>(item); 
  44.             Node<T> p=new Node<T>(); 
  45.             if(head==null) 
  46.             { 
  47.                 head=p; 
  48.                 return; 
  49.             } 
  50.             p=head; 
  51.             while(p.Next!=null) 
  52.             { 
  53.                 p=p.Next; 
  54.             } 
  55.             p.Next=q; 
  56.         }  
  57.         public void Insert(T item, int i) 
  58.         { 
  59.             if(IsEmpty()||i<1) 
  60.             { 
  61.                 Console.WriteLine("List is empty or Position is error"); 
  62.                 return; 
  63.             }  
  64.             if (i == 1) 
  65.             { 
  66.                 Node<T> q = new Node<T>(item); 
  67.                 q.Next = head; 
  68.                 head = q; 
  69.                 return; 
  70.             } 
  71.             Node<T> p = head; 
  72.             Node<T> r = new Node<T>(); 
  73.             int j = 1; 
  74.             while (p.Next != null && j < i) 
  75.             { 
  76.                 r = p; 
  77.                 p = p.Next; 
  78.                 ++j; 
  79.             }  
  80.             if (j == i) 
  81.             { 
  82.                 Node<T> q = new Node<T>(item); 
  83.                 q.Next = p; 
  84.                 r.Next = q; 
  85.             } 
  86.         }  
  87.         public void InsertPost(T item, int i) 
  88.         { 
  89.             if (IsEmpty() || i < 1) 
  90.             { 
  91.                 Console.WriteLine("List is empty or Position is error"); 
  92.                 return; 
  93.             } 
  94.             if (i == 1) 
  95.             { 
  96.                 Node<T> q = new Node<T>(item); 
  97.                 q.Next = head.Next; 
  98.                 head.Next = q; 
  99.                 return; 
  100.             } 
  101.             Node<T> p = head; 
  102.             int j = 1; 
  103.             while (p != null && j < i) 
  104.             { 
  105.                 p = p.Next; 
  106.                 ++j; 
  107.             } 
  108.             if (j == i) 
  109.             { 
  110.                 Node<T> q = new Node<T>(item); 
  111.                 q.Next = p.Next; 
  112.                 p.Next = q; 
  113.             } 
  114.         }  
  115.         public T Delete(int i) 
  116.         { 
  117.             if (IsEmpty() || i < 0) 
  118.             { 
  119.                 Console.WriteLine("Link is empty or Positon is error"); 
  120.                 return default(T); 
  121.             } 
  122.             Node<T> q = new Node<T>(); 
  123.             if (i == 1) 
  124.             { 
  125.                 q = head; 
  126.                 head = head.Next; 
  127.                 return q.Data; 
  128.             } 
  129.             Node<T> p = head; 
  130.             int j = 1; 
  131.             while (p.Next != null && j < i) 
  132.             { 
  133.                 ++j; 
  134.                 q = p; 
  135.                 p = p.Next; 
  136.             }  
  137.             if (j == i) 
  138.             { 
  139.                 q.Next = p.Next; 
  140.                 return p.Data; 
  141.             } 
  142.             else 
  143.             { 
  144.                 Console.WriteLine("The ith node is not exist!"); 
  145.                 return default(T); 
  146.             } 
  147.         }  
  148.         public T GetElem(int i) 
  149.         { 
  150.             if (IsEmpty()) 
  151.             { 
  152.                 Console.WriteLine("List is empty"); 
  153.                 return default(T); 
  154.             }  
  155.             Node<T> p = new Node<T>(); 
  156.             p = head; 
  157.             int j = 1;  
  158.             while (p.Next != null && j < i) 
  159.             { 
  160.                 ++j; 
  161.                 p = p.Next; 
  162.             } 
  163.             if (j == i) 
  164.             { 
  165.                 return p.Data; 
  166.             } 
  167.             else 
  168.             { 
  169.                 Console.WriteLine("the ith node is not exist!"); 
  170.                 return default(T); 
  171.             } 
  172.         }  
  173.         public int Locate(T value) 
  174.         { 
  175.             if (IsEmpty()) 
  176.             { 
  177.                 Console.WriteLine("List is Empty"); 
  178.                 return -1; 
  179.             } 
  180.             Node<T> p = new Node<T>(); 
  181.             p = head; 
  182.             int i = 1; 
  183.             while (!p.Data.Equals(value) && p.Next != null) 
  184.             { 
  185.                 p = p.Next; ; 
  186.                 ++i; 
  187.             } 
  188.             return i; 
  189.         }  
  190.         public void Reverse() 
  191.         { 
  192.             Node<T> p = head.Next; 
  193.             Node<T> q = new Node<T>(); 
  194.             head.Next = null; 
  195.             while (p != null) 
  196.             { 
  197.                 q = p; 
  198.                 p = p.Next; 
  199.                 q.Next = head.Next; 
  200.                 head.Next = q; 
  201.             } 
  202.         } 
  203.     }  
  204.     public class Node<T> 
  205.     { 
  206.         private T data;//数据域 
  207.         private Node<T> next;//引用域 
  208.   
  209.         public Node(T val, Node<T> p) 
  210.         { 
  211.             data = val; 
  212.             next = p; 
  213.         }  
  214.         public Node(Node<T> p) 
  215.         { 
  216.             next=p; 
  217.         } 
  218.         public Node(T val) 
  219.         { 
  220.             data = val; 
  221.             next = null; 
  222.         } 
  223.         public Node() 
  224.         { 
  225.             data = default(T); 
  226.             next = null; 
  227.         }  
  228.         public T Data 
  229.         { 
  230.             get { return data; } 
  231.             set { data = value; } 
  232.         } 
  233.         public Node<T> Next 
  234.         { 
  235.             get { return next; } 
  236.             set { next = value; } 
  237.         }        
  238.     } 
  239. } 

下面实现两个创建链表的函数如下：

  1. //在头部插入结点建立单链表 
  2.         static LinkList<int> CreateListHead() 
  3.         { 
  4.             int d; 
  5.             LinkList<int> l = new LinkList<int>(); 
  6.             d = Int32.Parse(Console.ReadLine()); 
  7.             while (d != -1) 
  8.             { 
  9.                 Node<int> p = new Node<int>(d); 
  10.                 p.Next = l.Head; 
  11.                 l.Head = p; 
  12.                 d = Int32.Parse(Console.ReadLine()); 
  13.             } 
  14.             return l; 
  15.         }  
  16.         //在尾部插入节点建立单链表 
  17.         static LinkList<int> CreateListTail() 
  18.         { 
  19.             Node<int> r = new Node<int>(); 
  20.             int d; 
  21.             LinkList<int> l = new LinkList<int>(); 
  22.   
  23.             r = l.Head; 
  24.             d = Int32.Parse(Console.ReadLine()); 
  25.   
  26.             while (d != -1) 
  27.             { 
  28.                 Node<int> p = new Node<int>(d); 
  29.                 if (l.Head == null) 
  30.                 { 
  31.                     l.Head = p; 
  32.                 } 
  33.                 else 
  34.                 { 
  35.                     r.Next = p; 
  36.                 } 
  37.                 r = p; 
  38.                 d = Int32.Parse(Console.ReadLine()); 
  39.             } 
  40.             if (r != null) 
  41.             { 
  42.                 r.Next = null; 
  43.             } 
  44.             return l; 
  45.         }  

5. 双向链表
5.1.双向链表的结点实现如下：

  1. public class DbNode<T> 
  2.     { 
  3.         private T data; 
  4.         private DbNode<T> prev; 
  5.         private DbNode<T> next; 
  6.   
  7.         public DbNode(T val, DbNode<T> p) 
  8.         { 
  9.             data = val; 
  10.             next = p; 
  11.         } 
  12.         public DbNode(DbNode<T> p) 
  13.         {            
  14.             next = p; 
  15.         } 
  16.         public DbNode(T val) 
  17.         { 
  18.             data = val; 
  19.             next = null; 
  20.         } 
  21.         public DbNode() 
  22.         { 
  23.             data = default(T); 
  24.             next = null; 
  25.         }  
  26.         public T Data 
  27.         { 
  28.             get { return data; } 
  29.             set { data = value; } 
  30.         } 
  31.         public DbNode<T> Prev 
  32.         { 
  33.             get { return prev; } 
  34.             set { prev = value; } 
  35.         } 
  36.         public DbNode<T> Next 
  37.         { 
  38.             get { return next; } 
  39.             set { next = value; } 
  40.         } 
  41. } 

5.2. 插入
由于双向链表的结点有两个引用，所以在双向链表中插入和删除结点比单链表要复杂，双向链表中结点的插入也分前插和后插，例如：设p指向某一结点，即p存储的是结点的地址，现将s插入到p前面，插入过程如下图：

clip_image002

对应的操作如下：

  1. p.Next.Prev=s; 
  2. s.Prev=p; 
  3. s.Next=p.Next; 
  4. p.Next=s; 

5.3.删除
我们以删除p结点的后面的结点为例，删除过程如下：

clip_image004

操作如下：

  1. p.Next=p.Next.Next; 
  2. P.Next.Prev=p.Prev; 

双向链表的其他操作与单链表相似。

随机文章推荐

本站热点业务

更多模板/案例展示

热门推荐

最近更新

关于我们 | 联系我们 | 团队日志 | 网站地图 | 网站合作
本站部份资源来于互联网,只供学习之用,不得用于商业,如有侵犯版权请联系告知,本站将第一时间删除!
copyright © 2008-2010 .Net中文社区 ASPXCS.NET™.All Rights Reserved 滇ICP备08102132号