二章数据结构实用类

C#实用类我们编写过的类顺序表ArrayList链表LinkedList堆栈ArrayStack、LinkedStack队列ArrayQueue、LinkedQueue优点：熟悉了语法，锻炼了逻辑思维能力缺点：处理能力非常有限只能处理学生只能按学号排序我们编写过的类功能能否扩展？顺序表ArrayListStudent[]data;Object[]data;append(StudentnewStu)append(ObjectnewStu)StudentgetValue(inti)ObjectgetValue(inti)主程序：Students=(Student)al.getValue(i);

处理能力仍然有限publicclassBook

{publicStringbookName;publicStringpublisher;publicdoubleprice;…}能处理BOOK吗？C#提供的实用类顺序表ArrayList，List<>链表LinkedList<>堆栈Stack<>,Stack队列Queue<>,Queue带<>称为范型，意为在<>内，用户可以自己定义元素的类型不带<>的实用类型，在System.Collections名字空间中，不带<>的实用类，其元素只能是Object类范型类在System.Collections.Generic空间中司马相如，蔺相如，名相如，实不相如！我们谦虚点！应用举例ArrayList这不是一个泛型类只能接受Object对象从文件读学生追加到表中的代码ArrayListal=newArrayList();stringline=sr.ReadLine();while(sr.Peek()>0){line=sr.ReadLine();string[]data=line.Split(delimiters,……);Students=newStudent(……);al.Add(s);}学生是Object对象吗？装箱操作应用举例ArrayList输出所有学生数据privatevoidbtnPrintAll_Click(……){rtbScoreList.Clear();rtbScoreList.Text="学号"+…

for(inti=0;i<al.Count;i++){Students=(Student)al[i];rtbScoreList.Text+=s.no+"\t"+……;}}拆箱操作用ArrayList，把我们的作业再做一遍ArrayList其他操作逆转al.Reverse();排序al.Sort();可惜，没这么简单查找？没有，需要自己编写;必须为表中的元素实现ICompareble接口有点累！Student类继承IComparable接口publicclassStudent:IComparable<Student>{publicStringno,name;publicintmath,english,computer,total;//构造函数……..

publicintCompareTo(Students){if(this.total==s.total)return0;returnthis.total>s.total?1:-1;}}只能按总分排序这种接口方法的缺陷我要将学生按学号排序我还要将学生按总分排序我还要将学生按数学分排序我要找最高分有灵活的方式吗！很多很多。。。。泛型类List<>—追加读student.txt文件并形成表窗体类中定义：

List<Student>ll=newList<Student>();

读文件的循环while(sr.Peek()>0)//{line=sr.ReadLine();//Students=…….

ll.Add(s);}

List<>的遍历输出for(inti=0;i<ll.Count;i++){Students=ll[i];

rtbScoreList.Text+=……}不需要拆箱吗！List<Student>ll=newList<Student>();对比：Students=(Student)al[i];List<>的排序将List<Student>按学号升序排序List<Student>llnew=ll.OrderBy(o=>o.no).ToList();o=>o.no称为Lamda表达式，=>是运算符将List<Student>按总分倒叙排序List<Student>llnew=ll.OrderByDescending(o=>o.total).ToList();好玩，高效，编程真简单！o是表中一项，自己定义名字。例如用item也可Item=>item.no，=>的右边，是运算逻辑，可写在{}内,像函数List<>简单类型的排序整型：List<int>la=newList<int>();la.Sort();实型：List<double>la=newList<double>();la.Sort();List<>的查找根据输入的学号，找到学生Students=ll.Find(o=>o.no==tbNoSearch.Text);查找最高分intmax=ll.Max(o=>o.total);改写Students=ll.Find(o=>{returno.no==tbNoSearch.Text;});如何查找最高分的学生将List<Student>按总分倒叙排序List<Student>llnew=ll.OrderByDescending(o=>o.total).ToList();StudentstuMax=llnew[0];List<>的逆转ll.Reverse();List<>的删除—删除指定学号stringno=tbNoDelete.Text;Students=ll.Find(o=>o.no==no);ll.Remove(s);必须先找到，再删除，为什么？用List<>泛型，把作业重做一遍哈希表Hashtable存储键/值对，一个键对应一个值。例如：系名为键数学系1360物理系1370化学系1380代码例子

Hashtableht=newHashtable();ht.Add("数学系","1360");ht.Add("物理系","1370");ht.Add("化学系","1380");键值Hashtable的遍历foreach(DictionaryEntrydeinht){stringdeptName=(string)de.Key;//取键stringdeptNo=(string)de.Value;//取值}Hashtable有什么用？--案例院系名字及代码都存在数据库里如何加入到界面中？foreach(DictionaryEntrydeinht){stringdeptName=(string)de.Key;//取键comboBox1.Items.Add(deptName);}Hashtable有什么用？--案例取用户选择的院系的IDStringdeptID=(String)ht[comboBox1.text];数据库中存储学生所在院系时，存的是院系的ID做个ComboBox小实验根据键取值更复杂的例子—学生作业统计表学号姓名11111张好22222李厉害作业号作业名17窗体设计21实验二学号作业号成绩1111117优1111121良2222217优2222221中更复杂的例子—学生作业统计表从学生表，得到所有学生，建立哈希表HashtablerowMap=newHashtable();for(inti=0;i<studentNos.Count;i++){rowMap.Add(studentNos[i],“”+i);}学号姓名11111张好22222李厉害根据作业ID，就可以找到列号更复杂的例子—学生作业统计表HashtablecolMap=newHashtable();for(inti=0;i<homeworkIds.Count;i++){colMap.Add(homeworkIds[i],""+i));}从作业表，得到所有布置的作业，建立哈希表作业号作业名17窗体设计21实验二根据作业ID，就可以找到列号填充数据String[,]score=newString[学生数,作业数];for(intk=0;k<homeworkIds.Count;k++){hID=homeworkIds[k];//用作业号hID，查询所有的学生作业记录while(还有记录){

取一条记录的学生sID和成绩s

行号i=rowMar[sID];

列号j=colMap[hID];score[i,j]=s;}}学生为行，作业为列，定义数据表String[,]score学号作业号成绩1111117优1111121良2222217优2222221中LinkedList<>泛型定义LinkedList<Student>ll=newLinkedList<Student>();添加ll.AddLast(student);LinkedList<>泛型遍历//使用迭代器

IEnumeratoriter=ll.GetEnumerator();while(iter.MoveNext()){Students=(Student)iter.Current;……//输出？还是？}迭代器的产生归并排序采用二路归并，每次将数组中两个相邻的有序序列归并为一个有序序列。排序过程为：假设待排序文件含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1两两归并，得到[n/2]个长度为2或1的有序子序列再两两归并。直到得到一个长度为n的有序文件为止。数据举例-二路归并排序过程示例

初态[45][21][34][19][52][60][34]┕━━┙┕━━┙┕━━┙第一趟[2145][1934][5260][34]┕━━┙┕━━┙第二趟[19213445][345260]┕━━━━━━┙第三趟19213434455260关键点对顺序存储方式二合一“一趟”整理，需要多次二合一需要多个“一趟”整理不一定有正好一样多数据的两个序列二合一存在没有配对的可能二合一two2One二合一调用多次，一次全部文件的二合一merge多次调用merge完成排序二合一

[2145][1934][5260][34]┕━━┙┕━━┙起始位s终止位t中间位ma[s..m]和a[m+1...t]归并为b[s..t]privatevoidtwo2One(int[]a,ints,intm,intt,int[]b){inti=s;intj=m+1;intk=s-1;while(i<=m&&j<=t){k++;if(a[i]<=a[j]){b[k]=a[i];i++;}else{b[k]=a[j];j++;}}if(i>m)for(;j<=t;j++){k++;b[k]=a[j];}elsefor(;i<=m;i++){k++;b[k]=a[i];}}二合一代码i是a[s..m]的指示器；j是a[m+1..t]的指示器；k是b[s..t]的指示器。两个子文件都有数据一个子文件有数据假设序列长度为n,每个子序列的长度为k，归并结果存放在数组b中，则一趟归并描述如下:“一趟”归并多个二合一privatevoidmerge(int[]a,intk,int[]b){intn=a.Length;inti=0;while(n-i>=2*k)//剩下的数据，可以形成偶对时，{two2One(a,i,i+k-1,i+2*k-1,b);i+=2*k;}if(n-i>k)//大于一个文件长度，但小于两个，也可以归并two2One(a,i,i+k-1,n-1,b);else//剩余元素小于一个文件长度，没有其他序列与其配对for(;i<n;i++)b[i]=a[i];}

会算？每两个子序列位置的计算

[2145][1934][5260][34]┕━━┙┕━━┙起始位s终止位t中间位m长度为2two2One(a,i,i+k-1,i+2*k-1,b);00+k-10+2*k-1起始位si+=2*k完整的归并排序一趟后，子序列长度为2，结果在b中；二趟后，子序列长度为4，结果在data中。重复此过程，直到有序子序列为n:publicvoidmergeSort(){intk=1;//定义初始文件长度为1intn=this.length;int[]b=newint[n];while(k<this.length){merge(data,k,b);k=2*k;merge(b,k,data);k=2*k;}}讨论题：上面有2个步骤k=2*k，如果第一个就已经超过了数组长度，怎么办？例如n=2的时候data放到bb放到data树形选择排序树形选择排序又称堆排序，是对选择排序的改进。

定义：对树中任一结点i，若R2i+1,R2i+2

存在，并且满足

Ki<=K2i+1Ki<=K2i+2i=0,1,2...则称之为堆。从定义得出，堆顶记录的关键字K0，就是最小者。数值举例堆{5,20,10,40,30,50,25,60}形成的顺序二叉树。堆排序的基本思想建堆：将一组待排序的关键字，按堆的定义排成一个序列，这就找到了最小关键字。调整:将最小关键字取出，用余下的关键字再建堆，便得到了次最小的关键字。如此反复，直到将全部关键字排好序为止。先输出堆顶记录，用堆中最后一个记录代替。如下图(a)堆的输出—重建堆

abc比较左、右子树的根结点，取值小者，与根交换如图(b)对右子树重复上述过程，直至叶子结点。这时便建成了一个新堆，如下图(c)所示。privatevoidheapShift(intstartPos,intendPos){inti,j,k;i=startPos;j=2*i+1;//j是startPos为根的树的左孩子结点的位置k=data[i];while(j<=endPos){if(j<endPos&&data[j]>data[j+1])//如果右孩子比左孩子小，则选择右孩子j++;/*j为左右孩子中小的下标*/if(k>data[j]){