顺序表类SeqList<T>的实现说明如下所示。 public class SeqList<T> : IListDS<T> { private int maxsize; //顺序表的容量 private T[] data; //数组,用于存储顺序表中的数据元素 private int last; //指示顺序表最后一个元素的位置 //索引器 public T this[int index] { get { return data[index]; } set { data[index] = value; } } //最后一个数据元素位置属性 public int Last { get { return last; } } //容量属性 public int Maxsize 数据结构(C#语言版) 2.2 顺序表 26 { get { return maxsize; } set { maxsize = value; } } //构造器 public SeqList(int size) { data = new T[size]; maxsize = size; last = -1; } //求顺序表的长度 public int GetLength() { return last+1; } //清空顺序表 public void Clear() { last = -1; } //判断顺序表是否为空 public bool IsEmpty() { if (last == -1) { return true; } else { return false; } } 数据结构(C#语言版) 2.2 顺序表 27 //判断顺序表是否为满 public bool IsFull() { if (last == maxsize-1) { return true; } else { return false; } } //在顺序表的末尾添加新元素 public void Append(T item) { if(IsFull()) { Console.WriteLine("List is full"); return; } data[++last] = item; } //在顺序表的第i个数据元素的位置插入一个数据元素 public void Insert(T item, int i) { if (IsFull()) { Console.WriteLine("List is full"); return; } if(i<1 || i>last+2) { Console.WriteLine("Position is error!"); return; } if (i == last + 2) { data[last+1] = item; 数据结构(C#语言版) 2.2 顺序表 28 } else { for (int j = last; j>= i-1; --j) { data[j + 1] = data[j]; } data[i-1] = item; } ++last; } //删除顺序表的第i个数据元素 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; 数据结构(C#语言版) 2.2 顺序表 29 } //获得顺序表的第i个数据元素 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的数据元素 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; } }
线性表的接口如下所示。public interface IListDS<T> {int GetLength(); //求长度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); //按值查找}
为了和.NET框架中的接口IList相区分,在IList后面加了“DS”,“DS”表示数据结构。下面对线性表的基本操作进行说明。
1、求长度:GetLength()
初始条件:线性表存在;
操作结果:返回线性表中所有数据元素的个数。
2、清空操作:Clear()
初始条件:线性表存在且有数据元素;
操作结果:从线性表中清除所有数据元素,线性表为空。
3、判断线性表是否为空:IsEmpty()
初始条件:线性表存在;
操作结果:如果线性表为空返回true,否则返回false。
4、附加操作:Append(T item)
初始条件:线性表存在且未满;
操作结果:将值为item的新元素添加到表的末尾。
5、插入操作:Insert(T item, int i)
初始条件:线性表存在,插入位置正确()(1≤i≤n+1,n为插入前的表长)。
操作结果:在线性表的第i个位置上插入一个值为item的新元素,这样使得原序号为i,i+1,…,n的数据元素的序号变为i+1,i+2,…,n+1,插入后表长=原
数据结构(C#语言版)
2.2 顺序表 24
表长+1。
6、删除操作:Delete(int i)
初始条件:线性表存在且不为空,删除位置正确(1≤i≤n,n为删除前的表长)。
操作结果:在线性表中删除序号为i的数据元素,返回删除后的数据元素。删除后使原序号为i+1,i+2,…,n的数据元素的序号变为i,i+1,…,n-1,删除后表长=原表长-1。
7、取表元:GetElem(int i)
初始条件:线性表存在,所取数据元素位置正确(1≤i≤n,n为线性表的表长);
操作结果:返回线性表中第i个数据元素。
8、按值查找:Locate(T value)
初始条件:线性表存在。
操作结果:在线性表中查找值为value的数据元素,其结果返回在线性表中首次出现的值为value的数据元素的序号,称为查找成功;否则,在线性表中未找到值为value的数据元素,返回一个特殊值表示查找失败。
实际上,在.NET框架中,许多类的求长度、判断满和判断空等操作都用属性来表示,这里在接口中定义为方法是为了说明数据结构的操作运算。实际上,属性也是方法。在后面章节的数据结构如栈、队列等的处理也是如此,就不一一说明了。单链表类LinkList<T>的实现说明如下所示。 public class LinkList<T> : IListDS<T> { private Node<T> head; //单链表的头引用 //头引用属性 public Node<T> Head { get { return head; } set { head = value; } } //构造器 public LinkList() { head = null; } //求单链表的长度 public int GetLength() { 数据结构(C#语言版) 2.3 单链表 42 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) 数据结构(C#语言版) 2.3 单链表 43 { p = p.Next; } p.Next = q; } //在单链表的第i个结点的位置前插入一个值为item的结点 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个结点的位置后插入一个值为item的结点 数据结构(C#语言版) 2.3 单链表 44 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个结点 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>(); 数据结构(C#语言版) 2.3 单链表 45 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个数据元素 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) { 数据结构(C#语言版) 2.3 单链表 46 ++j; p = p.Next; } if (j == i) { return p.Data; } else { Console.WriteLine("The ith node is not exist!"); return default(T); } } //在单链表中查找值为value的结点 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; } }
相关文章
- 12-16C# 字符串string和内存流MemoryStream及比特数组byte[]之间相互转换
- 12-16c# – 一个大的System.IO.MemoryStream会导致我的应用程序的内存使用量急剧增加吗?
- 12-16线性表的实验--线性表的简单应用
- 12-16C# 代码实现 Windows服务:计时器=>简单实现
- 12-16C#流总结(文件流、内存流、网络流、BufferedStream、StreamReader/StreamWriter、TextReader/TextWriter、转载)
- 12-16在SQL C#中按最大计数排序
- 12-16线性表的链式存储结构——链表
- 12-16线性表的链式存储结构——链表及其操作(创建,查找,插入,输出,删除)
- 12-16c# – 调试阻塞的Windows消息循环的想法
- 12-16关于线性表中栈的顺序存储和链式存储方式的实现方式