C#实现顺序表(线性表)完整实例
本文实例讲述了C#实现顺序表(线性表)的方法。分享给大家供大家参考,具体如下:
基本思想是使用数组作为盛放元素的容器,数组一开始的大小要实现确定,并使用一个Pointer指向顺序表中最后的元素。顺序表中的元素是数组中元素的子集。顺序表在内存中是连续的,优势是查找,弱势是插入元素和删除元素。
为避免装箱拆箱,这里使用泛型,代替object。使用object的例子可以参照本站这篇文章:https://www.nhooo.com/article/87603.htm,这个链接中的例子实现的是队列,并没有使用Pointer来标识顺序表中最后一个元素,而是动态的调整数组的大小,这与本例明显不同,动态调整数组大小开销较大。使用object同样可以完成顺序表数据结构,但是频繁装箱拆箱造成较大的开销,应使用泛型代替。
usingSystem; usingSystem.Collections.Generic; usingSystem.Linq; usingSystem.Text; namespaceLinearList { publicinterfaceIListDS<T> { intGetLength(); voidInsert(Titem,inti); voidAdd(Titem); boolIsEmpty(); TGetElement(inti); voidDelete(inti); voidClear(); intLocateElement(Titem); voidReverse(); } //顺序表类 classSequenceList<T>:IListDS<T> { privateintintMaxSize;//最大容量事先确定,使用数组必须先确定容量 privateT[]tItems;//使用数组盛放元素 privateintintPointerLast;//始终指向最后一个元素的位置 publicintMaxSize { get{returnthis.intMaxSize;} set{this.intMaxSize=value;} } publicTthis[inti]//索引器方便返回 { get{returnthis.tItems[i];} } publicintPointerLast { get{returnthis.intPointerLast;} } publicSequenceList(intsize) { this.intMaxSize=size; this.tItems=newT[size];//在这里初始化最合理 this.intPointerLast=-1;//初始值设为-1,此时数组中元素个数为0 } publicboolIsFull()//判断是否超出容量 { returnthis.intPointerLast+1==this.intMaxSize; } #regionIListDS<T>成员 publicintGetLength() { returnthis.intPointerLast+1;//不能返回tItems的长度 } publicvoidInsert(Titem,inti)//设i为第i个元素,从1开始。该函数表示在第i个元素后面插入item { if(i<1||i>this.intPointerLast+1) { Console.WriteLine("Theinsertinglocationiswrong!"); return; } if(this.IsFull()) { Console.WriteLine("Thislinearlistisfull!Can'tinsertanynewitems!"); return; } //如果可以添加 this.intPointerLast++; for(intj=this.intPointerLast;j>=i+1;j--) { this.tItems[j]=this.tItems[j-1]; } this.tItems[i]=item; } publicvoidAdd(Titem) { if(this.IsFull())//如果超出最大容量,则无法添加新元素 { Console.WriteLine("Thislinearlistisfull!Can'taddanynewitems!"); } else { this.tItems[++this.intPointerLast]=item;//表长+1 } } publicboolIsEmpty() { returnthis.intPointerLast==-1; } publicTGetElement(inti)//设i最小从0开始 { if(this.intPointerLast==-1) { Console.WriteLine("Therearenoelementsinthislinearlist!"); returndefault(T); } if(i>this.intPointerLast||i<0) { Console.WriteLine("Exceedthecapability!"); returndefault(T); } returnthis.tItems[i]; } publicvoidDelete(inti)//设i最小从0开始 { if(this.intPointerLast==-1) { Console.WriteLine("Therearenoelementsinthislinearlist!"); return; } if(i>this.intPointerLast||i<0) { Console.WriteLine("Deletinglocationiswrong!"); return; } for(intj=i;j<this.intPointerLast;j++) { this.tItems[j]=this.tItems[j+1]; } this.intPointerLast--;//表长-1 } publicvoidClear() { this.intPointerLast=-1; } publicintLocateElement(Titem) { if(this.intPointerLast==-1) { Console.WriteLine("Therearenoitemsinthelist!"); return-1; } for(inti=0;i<=this.intPointerLast;i++) { if(this.tItems[i].Equals(item))//若是自定义类型,则T类必须把Equals函数override { returni; } } Console.WriteLine("Notfound"); return-1; } publicvoidReverse() { if(this.intPointerLast==-1) { Console.WriteLine("Therearenoitemsinthelist!"); } else { inti=0; intj=this.GetLength()/2;//结果为下界整数,正好用于循环 while(i<j) { Ttmp=this.tItems[i]; this.tItems[i]=this.tItems[this.intPointerLast-i]; this.tItems[this.intPointerLast-i]=tmp; i++; } } } #endregion } classProgram { staticvoidMain(string[]args) { } } }
基于顺序表的合并排序:
//基于顺序表的合并排序 staticprivateSequenceList<int>Merge(SequenceList<int>s1,SequenceList<int>s2) { SequenceList<int>sList=newSequenceList<int>(20); inti=0; intj=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++; } returnsList; } else//即j>s2.PointerLast { while(i<=s1.PointerLast) { sList.Add(s1[i]); i++; } returnsList; } }
更多关于C#相关内容感兴趣的读者可查看本站专题:《C#数据结构与算法教程》、《C#遍历算法与技巧总结》、《C#程序设计之线程使用技巧总结》、《C#操作Excel技巧总结》、《C#中XML文件操作技巧汇总》、《C#常见控件用法教程》、《WinForm控件用法总结》、《C#数组操作技巧总结》及《C#面向对象程序设计入门教程》
希望本文所述对大家C#程序设计有所帮助。