二章數(shù)據(jù)結(jié)構(gòu)實用類

C#實用類我們編寫過的類順序表ArrayList鏈表LinkedList堆棧ArrayStack、LinkedStack隊列ArrayQueue、LinkedQueue優(yōu)點：熟悉了語法，鍛煉了邏輯思維能力缺點：處理能力非常有限只能處理學(xué)生只能按學(xué)號排序我們編寫過的類功能能否擴展？順序表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帶<>稱為范型，意為在<>內(nèi)，用戶可以自己定義元素的類型不帶<>的實用類型，在System.Collections名字空間中，不帶<>的實用類，其元素只能是Object類范型類在System.Collections.Generic空間中司馬相如，藺相如，名相如，實不相如！我們謙虛點！應(yīng)用舉例ArrayList這不是一個泛型類只能接受Object對象從文件讀學(xué)生追加到表中的代碼ArrayListal=newArrayList();stringline=sr.ReadLine();while(sr.Peek()>0){line=sr.ReadLine();string[]data=line.Split(delimiters,……);Students=newStudent(……);al.Add(s);}學(xué)生是Object對象嗎？裝箱操作應(yīng)用舉例ArrayList輸出所有學(xué)生數(shù)據(jù)privatevoidbtnPrintAll_Click(……){rtbScoreList.Clear();rtbScoreList.Text="學(xué)號"+…

for(inti=0;i<al.Count;i++){Students=(Student)al[i];rtbScoreList.Text+=s.no+"\t"+……;}}拆箱操作用ArrayList，把我們的作業(yè)再做一遍ArrayList其他操作逆轉(zhuǎn)al.Reverse();排序al.Sort();可惜，沒這么簡單查找？沒有，需要自己編寫;必須為表中的元素實現(xiàn)ICompareble接口有點累！Student類繼承IComparable接口publicclassStudent:IComparable<Student>{publicStringno,name;publicintmath,english,computer,total;//構(gòu)造函數(shù)……..

publicintCompareTo(Students){if(this.total==s.total)return0;returnthis.total>s.total?1:-1;}}只能按總分排序這種接口方法的缺陷我要將學(xué)生按學(xué)號排序我還要將學(xué)生按總分排序我還要將學(xué)生按數(shù)學(xué)分排序我要找最高分有靈活的方式嗎！很多很多。。。。泛型類List<>—追加讀student.txt文件并形成表窗體類中定義：

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

讀文件的循環(huán)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<>的排序?qū)ist<Student>按學(xué)號升序排序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，=>的右邊，是運算邏輯，可寫在{}內(nèi),像函數(shù)List<>簡單類型的排序整型：List<int>la=newList<int>();la.Sort();實型：List<double>la=newList<double>();la.Sort();List<>的查找根據(jù)輸入的學(xué)號，找到學(xué)生Students=ll.Find(o=>o.no==tbNoSearch.Text);查找最高分intmax=ll.Max(o=>o.total);改寫Students=ll.Find(o=>{returno.no==tbNoSearch.Text;});如何查找最高分的學(xué)生將List<Student>按總分倒敘排序List<Student>llnew=ll.OrderByDescending(o=>o.total).ToList();StudentstuMax=llnew[0];List<>的逆轉(zhuǎn)ll.Reverse();List<>的刪除—刪除指定學(xué)號stringno=tbNoDelete.Text;Students=ll.Find(o=>o.no==no);ll.Remove(s);必須先找到，再刪除，為什么？用List<>泛型，把作業(yè)重做一遍哈希表Hashtable存儲鍵/值對，一個鍵對應(yīng)一個值。例如：系名為鍵數(shù)學(xué)系1360物理系1370化學(xué)系1380代碼例子

Hashtableht=newHashtable();ht.Add("數(shù)學(xué)系","1360");ht.Add("物理系","1370");ht.Add("化學(xué)系","1380");鍵值Hashtable的遍歷foreach(DictionaryEntrydeinht){stringdeptName=(string)de.Key;//取鍵stringdeptNo=(string)de.Value;//取值}Hashtable有什么用？--案例院系名字及代碼都存在數(shù)據(jù)庫里如何加入到界面中？foreach(DictionaryEntrydeinht){stringdeptName=(string)de.Key;//取鍵comboBox1.Items.Add(deptName);}Hashtable有什么用？--案例取用戶選擇的院系的IDStringdeptID=(String)ht[comboBox1.text];數(shù)據(jù)庫中存儲學(xué)生所在院系時，存的是院系的ID做個ComboBox小實驗根據(jù)鍵取值更復(fù)雜的例子—學(xué)生作業(yè)統(tǒng)計表學(xué)號姓名11111張好22222李厲害作業(yè)號作業(yè)名17窗體設(shè)計21實驗二學(xué)號作業(yè)號成績1111117優(yōu)1111121良2222217優(yōu)2222221中更復(fù)雜的例子—學(xué)生作業(yè)統(tǒng)計表從學(xué)生表，得到所有學(xué)生，建立哈希表HashtablerowMap=newHashtable();for(inti=0;i<studentNos.Count;i++){rowMap.Add(studentNos[i],“”+i);}學(xué)號姓名11111張好22222李厲害根據(jù)作業(yè)ID，就可以找到列號更復(fù)雜的例子—學(xué)生作業(yè)統(tǒng)計表HashtablecolMap=newHashtable();for(inti=0;i<homeworkIds.Count;i++){colMap.Add(homeworkIds[i],""+i));}從作業(yè)表，得到所有布置的作業(yè)，建立哈希表作業(yè)號作業(yè)名17窗體設(shè)計21實驗二根據(jù)作業(yè)ID，就可以找到列號填充數(shù)據(jù)String[,]score=newString[學(xué)生數(shù),作業(yè)數(shù)];for(intk=0;k<homeworkIds.Count;k++){hID=homeworkIds[k];//用作業(yè)號hID，查詢所有的學(xué)生作業(yè)記錄while(還有記錄){

取一條記錄的學(xué)生sID和成績s

行號i=rowMar[sID];

列號j=colMap[hID];score[i,j]=s;}}學(xué)生為行，作業(yè)為列，定義數(shù)據(jù)表String[,]score學(xué)號作業(yè)號成績1111117優(yōu)1111121良2222217優(yōu)2222221中LinkedList<>泛型定義LinkedList<Student>ll=newLinkedList<Student>();添加ll.AddLast(student);LinkedList<>泛型遍歷//使用迭代器

IEnumeratoriter=ll.GetEnumerator();while(iter.MoveNext()){Students=(Student)iter.Current;……//輸出？還是？}迭代器的產(chǎn)生歸并排序采用二路歸并，每次將數(shù)組中兩個相鄰的有序序列歸并為一個有序序列。排序過程為：假設(shè)待排序文件含有n個記錄，則可看成是n個有序的子序列，每個子序列的長度為1兩兩歸并，得到[n/2]個長度為2或1的有序子序列再兩兩歸并。直到得到一個長度為n的有序文件為止。數(shù)據(jù)舉例-二路歸并排序過程示例

初態(tài)[45][21][34][19][52][60][34]┕━━┙┕━━┙┕━━┙第一趟[2145][1934][5260][34]┕━━┙┕━━┙第二趟[19213445][345260]┕━━━━━━┙第三趟19213434455260關(guān)鍵點對順序存儲方式二合一“一趟”整理，需要多次二合一需要多個“一趟”整理不一定有正好一樣多數(shù)據(jù)的兩個序列二合一存在沒有配對的可能二合一two2One二合一調(diào)用多次，一次全部文件的二合一merge多次調(diào)用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]的指示器。兩個子文件都有數(shù)據(jù)一個子文件有數(shù)據(jù)假設(shè)序列長度為n,每個子序列的長度為k，歸并結(jié)果存放在數(shù)組b中，則一趟歸并描述如下:“一趟”歸并多個二合一privatevoidmerge(int[]a,intk,int[]b){intn=a.Length;inti=0;while(n-i>=2*k)//剩下的數(shù)據(jù)，可以形成偶對時，{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，結(jié)果在b中；二趟后，子序列長度為4，結(jié)果在data中。重復(fù)此過程，直到有序子序列為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，如果第一個就已經(jīng)超過了數(shù)組長度，怎么辦？例如n=2的時候data放到bb放到data樹形選擇排序樹形選擇排序又稱堆排序，是對選擇排序的改進。

定義：對樹中任一結(jié)點i，若R2i+1,R2i+2

存在，并且滿足

Ki<=K2i+1Ki<=K2i+2i=0,1,2...則稱之為堆。從定義得出，堆頂記錄的關(guān)鍵字K0，就是最小者。數(shù)值舉例堆{5,20,10,40,30,50,25,60}形成的順序二叉樹。堆排序的基本思想建堆：將一組待排序的關(guān)鍵字，按堆的定義排成一個序列，這就找到了最小關(guān)鍵字。調(diào)整:將最小關(guān)鍵字取出，用余下的關(guān)鍵字再建堆，便得到了次最小的關(guān)鍵字。如此反復(fù)，直到將全部關(guān)鍵字排好序為止。先輸出堆頂記錄，用堆中最后一個記錄代替。如下圖(a)堆的輸出—重建堆

abc比較左、右子樹的根結(jié)點，取值小者，與根交換如圖(b)對右子樹重復(fù)上述過程，直至葉子結(jié)點。這時便建成了一個新堆，如下圖(c)所示。privatevoidheapShift(intstartPos,intendPos){inti,j,k;i=startPos;j=2*i+1;//j是startPos為根的樹的左孩子結(jié)點的位置k=data[i];while(j<=endPos){if(j<endPos&&data[j]>data[j+1])//如果右孩子比左孩子小，則選擇右孩子j++;/*j為左右孩子中小的下標(biāo)*/if(k>data[j]){