C#实现顺序表(线性表)完整实例
程序员文章站
2023-11-08 15:10:34
本文实例讲述了c#实现顺序表(线性表)的方法。分享给大家供大家参考,具体如下:
基本思想是使用数组作为盛放元素的容器,数组一开始的大小要实现确定,并使用一个pointer...
本文实例讲述了c#实现顺序表(线性表)的方法。分享给大家供大家参考,具体如下:
基本思想是使用数组作为盛放元素的容器,数组一开始的大小要实现确定,并使用一个pointer指向顺序表中最后的元素。顺序表中的元素是数组中元素的子集。顺序表在内存中是连续的,优势是查找,弱势是插入元素和删除元素。
为避免装箱拆箱,这里使用泛型,代替object。使用object的例子可以参照本站这篇文章:,这个链接中的例子实现的是队列,并没 有使用pointer来标识 顺序表中最后一个元素,而是动态的调整数组的大小,这与本例明显不同,动态调整数组大小开销较大。使用object同样可以完成顺序表数据结构,但是频繁装箱拆箱造成较大的开销,应使用泛型代替。
using system; using system.collections.generic; using system.linq; using system.text; namespace linearlist { public interface ilistds<t> { int getlength(); void insert(t item, int i); void add(t item); bool isempty(); t getelement(int i); void delete(int i); void clear(); int locateelement(t item); void reverse(); } //顺序表类 class sequencelist<t>:ilistds<t> { private int intmaxsize;//最大容量事先确定,使用数组必须先确定容量 private t[] titems;//使用数组盛放元素 private int intpointerlast;//始终指向最后一个元素的位置 public int maxsize { get { return this.intmaxsize; } set { this.intmaxsize = value; } } public t this[int i]//索引器方便返回 { get { return this.titems[i]; } } public int pointerlast { get { return this.intpointerlast; } } public sequencelist(int size) { this.intmaxsize = size; this.titems = new t[size];//在这里初始化最合理 this.intpointerlast = -1;//初始值设为-1,此时数组中元素个数为0 } public bool isfull()//判断是否超出容量 { return this.intpointerlast+1 == this.intmaxsize; } #region ilistds<t> 成员 public int getlength() { return this.intpointerlast + 1;//不能返回titems的长度 } public void insert(t item, int i)//设i为第i个元素,从1开始。该函数表示在第i个元素后面插入item { if (i < 1 || i > this.intpointerlast + 1) { console.writeline("the inserting location is wrong!"); return; } if (this.isfull()) { console.writeline("this linear list is full! can't insert any new items!"); return; } //如果可以添加 this.intpointerlast++; for(int j=this.intpointerlast;j>=i+1;j--) { this.titems[j] = this.titems[j - 1]; } this.titems[i] = item; } public void add(t item) { if (this.isfull())//如果超出最大容量,则无法添加新元素 { console.writeline("this linear list is full! can't add any new items!"); } else { this.titems[++this.intpointerlast] = item;//表长+1 } } public bool isempty() { return this.intpointerlast == -1; } public t getelement(int i)//设i最小从0开始 { if(this.intpointerlast == -1) { console.writeline("there are no elements in this linear list!"); return default(t); } if (i > this.intpointerlast||i<0) { console.writeline("exceed the capability!"); return default(t); } return this.titems[i]; } public void delete(int i)//设i最小从0开始 { if (this.intpointerlast == -1) { console.writeline("there are no elements in this linear list!"); return; } if (i > this.intpointerlast || i < 0) { console.writeline("deleting location is wrong!"); return; } for (int j = i; j < this.intpointerlast; j++) { this.titems[j] = this.titems[j + 1]; } this.intpointerlast--;//表长-1 } public void clear() { this.intpointerlast = -1; } public int locateelement(t item) { if (this.intpointerlast == -1) { console.writeline("there are no items in the list!"); return -1; } for (int i = 0; i <= this.intpointerlast; i++) { if (this.titems[i].equals(item))//若是自定义类型,则t类必须把equals函数override { return i; } } console.writeline("not found"); return -1; } public void reverse() { if (this.intpointerlast == -1) { console.writeline("there are no items in the list!"); } else { int i = 0; int j = this.getlength() / 2;//结果为下界整数,正好用于循环 while (i < j) { t tmp = this.titems[i]; this.titems[i] = this.titems[this.intpointerlast - i]; this.titems[this.intpointerlast - i] = tmp; i++; } } } #endregion } class program { static void main(string[] args) { } } }
基于顺序表的合并排序:
//基于顺序表的合并排序 static private sequencelist<int> merge(sequencelist<int> s1,sequencelist<int> s2) { sequencelist<int> slist = new sequencelist<int>(20); int i = 0; int j = 0; while(i<=s1.pointerlast&&j<=s2.pointerlast) { if (s1[i] < s2[j]) { slist.add(s1[i]); i++; } else { slist.add(s2[j]); j++; } } if (i > s1.pointerlast) { while (j <= s2.pointerlast) { slist.add(s2[j]); j++; } return slist; } else//即j>s2.pointerlast { while (i <= s1.pointerlast) { slist.add(s1[i]); i++; } return slist; } }
更多关于c#相关内容感兴趣的读者可查看本站专题:《c#数据结构与算法教程》、《c#遍历算法与技巧总结》、《c#程序设计之线程使用技巧总结》、《c#操作excel技巧总结》、《c#中xml文件操作技巧汇总》、《c#常见控件用法教程》、《winform控件用法总结》、《c#数组操作技巧总结》及《c#面向对象程序设计入门教程》
希望本文所述对大家c#程序设计有所帮助。