VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > temp > C#教程 >
  • c#数据结构之线性表

制作者:剑锋冷月 单位:无忧统计网,www.51stat.net
 

  理论基础: 

  线性表是最简单、最基本、最常用的数据结构。线性表是线性结构的抽象(Abstract),线性结构的特点是结构中的数据元素之间存在一对一的线性关系。这种一对一的关系指的是数据元素之间的位置关系,即:

  (1)除第一个位置的数据元素外,其它数据元素位置的前面都只有一个数据元素;

  (2)除最后一个位置的数据元素外,其它数据元素位置的后面都只有一个元素。

  也就是说,数据元素是一个接一个的排列。因此,可以把线性表想象为一种数据元素序列的数据结构。

  线性表(List)是由n(n≥0)个相同类型的数据元素构成的有限序列.

  注意:“有限”,指的是线性表中的数据元素的个数是有限的,线性表中的每一个数据元素都有自己的位置(Position)。本书不讨论数据元素个数无限的线性表。

  “相同类型”,指的是线性表中的数据元素都属于同一种类型。

  C#实现:

  1接口

  由于现在只考虑线性表的基本操作,所以以C#接口的形式表示线性表,接口中的方法成员表示基本操作。并且,为了使线性表对任何数据类型都适用,数据元素的类型使用泛型的类型参数。在实际创建线性表时,元素的实际类型可以用应用程序中任何方便的数据类型来代替,比如用简单的整型或者用户自定义的更复杂的类型来代替。

  线性表的接口如下所示。

  Code

  [copy to clipboard]

  CODE:

1 public interface IListDS<T>
2  {
3    /**//// <summary>
4    /// 获取长度
5    /// </summary>
6    /// <returns></returns>
7    int GetLength();
8
9    /**//// <summary>
10    /// 清空操作
11    /// </summary>
12    void Clear();
13
14    /**//// <summary>
15    /// 判断线性表是否为空
16    /// </summary>
17    /// <returns></returns>
18    bool IsEmpay();
19
20    /**//// <summary>
21    /// 附加操作,线性表未满,将值为item的新元素添加到末尾
22    /// </summary>
23    /// <param name="item"></param>
24    void Append(T item);
25
26    /**//// <summary>
27    /// 插入操作
28    /// </summary>
29    /// <param name="item"></param>
30    /// <param name="i"></param>
31    void Insert(T item,int i);
32
33    /**//// <summary>
34    /// 删除操作
35    /// </summary>
36    /// <param name="i"></param>
37    /// <returns></returns>
38    T Delete(int i);
39
40    /**//// <summary>
41    /// 去表元
42    /// </summary>
43    /// <param name="i"></param>
44    /// <returns></returns>
45    T GetElem(int i);
46
47    /**//// <summary>
48    /// 按值查找
49    /// </summary>
50    /// <param name="value"></param>
51    /// <returns></returns>
52    int Locate(T value);
53  }

 

  2 实现

  实现过程中,算法时间复杂度没有做过多的考虑和计算,有兴趣的朋友可以完成

  Code

  [copy to clipboard]

  CODE:

1/**//// <summary>
 2  /// 线性表
 3  /// </summary>
 4  /// <typeparam name="T"></typeparam>
 5  public class SeqList<T> : IListDS<T>
 6  {
 7    private int maxsize; //顺序表的容量
 8    private T[] data;  //数组,用于存储顺序表中的数据元素
 9    private int last;  //指示顺序表最后一个元素的位置
10
11    //索引器
12    public T this[int index]
13    {
14      get
15      {
16        return data[index];
17      }
18      set
19      {
20        data[index] = value;
21      }
22    }
23
24    //最后一个数据元素的位置属性
25    public int List
26    {
27      get
28      {
29        return last;
30      }
31    }
32
33    //容量属性
34    public int MaxSize
35    {
36      get
37      {
38        return maxsize;
39
40      }
41      set
42      {
43        maxsize = value;
44      }
45    }
46
47    //构造函数
48    public SeqList(int size)
49    {
50      data = new T[size];
51      maxsize = size;
52      last = -1;
53    }
54    /**//// <summary>
55    /// 获取长度
56    /// </summary>
57    /// <returns></returns>
58    public int GetLength()
59    {
60      return last + 1;
61    }
62
63    /**//// <summary>
64    /// 清空操作
65    /// </summary>
66    public void Clear()
67    {
68      last = -1;    
69    }
70
71
72    /**//// <summary>
73    /// 判断线性表是否为空
74    /// </summary>
75    /// <returns></returns>
76    public bool IsEmpay()
77    {
78      if (last == -1)
79      {
80        return true;
81      }
82      else
83      {
84        return false;
85      }
86    }
87
88    /**//// <summary>
89    /// 判断线性表是否已满
90    /// </summary>
91    /// <returns></returns>
92    public bool IsFull()
93    {
94      if (last == maxsize - 1)
95      {
96        return true;
97      }
98      else
99      {
100        return false;
101      }
102    }
103
104    /**//// <summary>
105    /// 附加操作,线性表未满,将值为item的新元素添加到末尾
106    /// </summary>
107    /// <param name="item"></param>
108   public void Append(T item)
109    {
110      if (IsFull())
111      {
112        Console.Write("list is full");
113        return;
114      }
115
116      data[++last] = item;
117    }
118
119    /**//// <summary>
120    /// 插入操作
121    /// </summary>
122    /// <param name="item"></param>
123    /// <param name="i"></param>
124    public void Insert(T item, int i)
125    {
126      if (IsFull())
127      {
128        Console.Write("List is full");
129        return;
130      }
131
132      if (i < 1 || i > last + 2)
133      {
134        Console.Write("Posotion is error");
135        return;
136      }
137
138      if (i == last + 2)
139      {
140        data[last + 1] = item;
141      }
142      else
143      {
144        for (int j = last; j >= i - 1; --j)
145        {
146          data[j + 1] = data[j];
147        }
148        data[i - 1] = item;
149      }
150      ++last;
151    }
152
153    /**//// <summary>
154    /// 删除操作
155    /// </summary>
156    /// <param name="i"></param>
157    /// <returns></returns>
158    public T Delete(int i)
159    {
160      T t = default(T);
161      if (IsEmpay())
162      {
163        Console.Write("List is empty!");
164        return t;
165      }
166      if (i < 1 || i > last + 1)
167      {
168        Console.Write("Position is Error");
169        return t;
170      }
171      if (i == last + 1)
172      {
173        t = data[last--];
174
175      }
176      else
177      {
178        t = data[i - 1];
179        for (int j = i; j <= last; j++)
180        {
181          data[j] = data[j + 1];
182        }
183      }
184      --last;
185      return t;
186
187    }
188
189    /**//// <summary>
190    /// 取表元
191    /// </summary>
192    /// <param name="i"></param>
193    /// <returns></returns>
194    public T GetElem(int i)
195    {
196      T t = default(T);
197      if (IsEmpay())
198      {
199        Console.Write("List is Empty");
200        return t;
201      }
202
203      if (i < 1 || i > last + 1)
204      {
205        Console.Write("Position is error");
206        return t;
207      }
208      return data[i - 1];
209
210    }
211
212    /**//// <summary>
213    /// 按值查找
214    /// </summary>
215    /// <param name="value"></param>
216    /// <returns></returns>
217    public int Locate(T value)
218    {
219      if (IsEmpay())
220      {
221        Console.Write("List is empty");
222        return -1;
223      }
224
225      int i = 0;
226      for ( i = 0; i <= last; ++i)
227      {
228        if (value.Equals(data))
229        {
230          break;
231        }
232      }
233      if (i > last)
234      {
235        return -1;
236      }
237      return i;
238    }
239  }

 

  以上代码用C#实现了线性表的操作,具体的测试没有做,有兴趣的朋友,可以写一个简单的测试程序。

 

 

  2 实现

  实现过程中,算法时间复杂度没有做过多的考虑和计算,有兴趣的朋友可以完成

  Code

  [copy to clipboard]

  CODE:

1/**//// <summary>
 2  /// 线性表
 3  /// </summary>
 4  /// <typeparam name="T"></typeparam>
 5  public class SeqList<T> : IListDS<T>
 6  {
 7    private int maxsize; //顺序表的容量
 8    private T[] data;  //数组,用于存储顺序表中的数据元素
 9    private int last;  //指示顺序表最后一个元素的位置
10
11    //索引器
12    public T this[int index]
13    {
14      get
15      {
16        return data[index];
17      }
18      set
19      {
20        data[index] = value;
21      }
22    }
23
24    //最后一个数据元素的位置属性
25    public int List
26    {
27      get
28      {
29        return last;
30      }
31    }
32
33    //容量属性
34    public int MaxSize
35    {
36      get
37      {
38        return maxsize;
39
40      }
41      set
42      {
43        maxsize = value;
44      }
45    }
46
47    //构造函数
48    public SeqList(int size)
49    {
50      data = new T[size];
51      maxsize = size;
52      last = -1;
53    }
54    /**//// <summary>
55    /// 获取长度
56    /// </summary>
57    /// <returns></returns>
58    public int GetLength()
59    {
60      return last + 1;
61    }
62
63    /**//// <summary>
64    /// 清空操作
65    /// </summary>
66    public void Clear()
67    {
68      last = -1;    
69    }
70
71
72    /**//// <summary>
73    /// 判断线性表是否为空
74    /// </summary>
75    /// <returns></returns>
76    public bool IsEmpay()
77    {
78      if (last == -1)
79      {
80        return true;
81      }
82      else
83      {
84        return false;
85      }
86    }
87
88    /**//// <summary>
89    /// 判断线性表是否已满
90    /// </summary>
91    /// <returns></returns>
92    public bool IsFull()
93    {
94      if (last == maxsize - 1)
95      {
96        return true;
97      }
98      else
99      {
100        return false;
101      }
102    }
103
104    /**//// <summary>
105    /// 附加操作,线性表未满,将值为item的新元素添加到末尾
106    /// </summary>
107    /// <param name="item"></param>
108   public void Append(T item)
109    {
110      if (IsFull())
111      {
112        Console.Write("list is full");
113        return;
114      }
115
116      data[++last] = item;
117    }
118
119    /**//// <summary>
120    /// 插入操作
121    /// </summary>
122    /// <param name="item"></param>
123    /// <param name="i"></param>
124    public void Insert(T item, int i)
125    {
126      if (IsFull())
127      {
128        Console.Write("List is full");
129        return;
130      }
131
132      if (i < 1 || i > last + 2)
133      {
134        Console.Write("Posotion is error");
135        return;
136      }
137
138      if (i == last + 2)
139      {
140        data[last + 1] = item;
141      }
142      else
143      {
144        for (int j = last; j >= i - 1; --j)
145        {
146          data[j + 1] = data[j];
147        }
148        data[i - 1] = item;
149      }
150      ++last;
151    }
152
153    /**//// <summary>
154    /// 删除操作
155    /// </summary>
156    /// <param name="i"></param>
157    /// <returns></returns>
158    public T Delete(int i)
159    {
160      T t = default(T);
161      if (IsEmpay())
162      {
163        Console.Write("List is empty!");
164        return t;
165      }
166      if (i < 1 || i > last + 1)
167      {
168        Console.Write("Position is Error");
169        return t;
170      }
171      if (i == last + 1)
172      {
173        t = data[last--];
174
175      }
176      else
177      {
178        t = data[i - 1];
179        for (int j = i; j <= last; j++)
180        {
181          data[j] = data[j + 1];
182        }
183      }
184      --last;
185      return t;
186
187    }
188
189    /**//// <summary>
190    /// 取表元
191    /// </summary>
192    /// <param name="i"></param>
193    /// <returns></returns>
194    public T GetElem(int i)
195    {
196      T t = default(T);
197      if (IsEmpay())
198      {
199        Console.Write("List is Empty");
200        return t;
201      }
202
203      if (i < 1 || i > last + 1)
204      {
205        Console.Write("Position is error");
206        return t;
207      }
208      return data[i - 1];
209
210    }
211
212    /**//// <summary>
213    /// 按值查找
214    /// </summary>
215    /// <param name="value"></param>
216    /// <returns></returns>
217    public int Locate(T value)
218    {
219      if (IsEmpay())
220      {
221        Console.Write("List is empty");
222        return -1;
223      }
224
225      int i = 0;
226      for ( i = 0; i <= last; ++i)
227      {
228        if (value.Equals(data))
229        {
230          break;
231        }
232      }
233      if (i > last)
234      {
235        return -1;
236      }
237      return i;
238    }
239  }

 

  以上代码用C#实现了线性表的操作,具体的测试没有做,有兴趣的朋友,可以写一个简单的测试程序。

 



相关教程