大數(shù)據(jù)結(jié)構(gòu)自組織線性的表實(shí)驗(yàn)7報(bào)告材料

1、實(shí)用標(biāo)準(zhǔn)文案HUNAN UNIVERSITY實(shí)驗(yàn)七最終報(bào)告題目：自組織線性表學(xué)生姓名學(xué)生學(xué)號(hào)專業(yè)班級指導(dǎo)老師完成日期2014年 5月 29日精彩文檔實(shí)用標(biāo)準(zhǔn)文案一、 需求分析1 輸入形式：從文件中讀入 一組漢字集合，用自組織線性表保存，然后從文件中依次讀入要查找的漢字。不對非法輸入做處理，假定輸入的數(shù)據(jù)都合法。2 輸出形式：輸出要查找的漢字和查找結(jié)果及比較次數(shù)輸出到DOS界面，并輸出保存到文件 中。如果找到，返回比較的次數(shù)，如果沒有找到，返回比較的次數(shù)。3 程序功能：程序讀入保存在文件中的漢字集合和要查找的漢字，并用需查找的漢字與漢字集合中漢字進(jìn)行查找比較，并把查找到的漢字在順序表中用轉(zhuǎn)置法排

2、序，輸出查找結(jié)果。4 測試數(shù)據(jù)輸入：從文件中讀入的漢字為：好好學(xué)習(xí)，天天向上需要查找的漢字為：向我學(xué)習(xí)輸出：向 查找成功！查找次數(shù)為：8我 查找失??！查找次數(shù)為：9學(xué) 查找成功！查找次數(shù)為：3習(xí) 查找成功！查找次數(shù)為：4二、概要設(shè)計(jì)抽象數(shù)據(jù)類型定義要求從文件中讀入一組漢字集合， 用自組織線性表保存。 集合中必存在唯一一個(gè)第一元素和最后元素。 除最后元素在外，元素間均有唯一的后繼，除第一元素之外，元素間均有唯一的前驅(qū)，所以為數(shù)據(jù)元素建立一個(gè)線性數(shù)據(jù)關(guān)系。線性表 ADT數(shù)據(jù)對象 ： D a i | ai字符型 , i=1,2,.,n, n 0 數(shù)據(jù)關(guān)系 ： R1 <a i-1 ,a i &g

3、t;|a i-1 ,a i D, i=2,.,n 約定 a1 為線性表頭， an 為線性表尾?；静僮鳎簐oid initList();/初始化變量bool insert();/從文件中讀入漢字int getLengthk(); /獲得需查找漢字的長度int getLengthj(); /獲得漢字集合的長度void printout();/輸出讀入的記錄到屏幕算法的基本思想設(shè)置一個(gè)計(jì)數(shù)器計(jì)數(shù)查找漢字的次數(shù)，每當(dāng)遍歷到線性表中的一個(gè)漢字時(shí)，計(jì)數(shù)器加一。遍歷線性表， 依次用需查找的漢字與保存了讀入漢字的自組織線性表中的每一個(gè)漢字作精彩文檔實(shí)用標(biāo)準(zhǔn)文案比較， 如果相等那么查找到漢字，輸出該漢字查找成

4、功，輸出查找次數(shù)。沒有查找到則輸出查找失敗，輸出查找的次數(shù)。程序的流程（ 1） 讀入模塊 ：從文件中讀入一組漢字集合，并保存在自組織線性表中，讀入要查找的漢字。（ 2） 轉(zhuǎn)置查找模塊 ：依次根據(jù)需查找的漢字對漢字線性表遍歷一次進(jìn)行查找，若查找到該漢字，調(diào)用轉(zhuǎn)置函數(shù)，將該漢字與前一個(gè)位置的漢字轉(zhuǎn)置，然后繼續(xù)查找下一個(gè)漢字。（ 3） 輸出模塊： 若查找到漢字，則輸出到屏幕和文件中查找成功并顯示查找次數(shù)；若沒有查找到該漢字，輸出到屏幕和文件中查找不成功并顯示查找的次數(shù)。各層次模塊之間的調(diào)用關(guān)系轉(zhuǎn)置讀查輸入找出模模模塊塊塊三、詳細(xì)設(shè)計(jì)物理數(shù)據(jù)類型查找時(shí)， 因?yàn)椴恍枰迷黾雍蛣h除操作， 為了使空間效率較

5、高， 同時(shí)方便實(shí)現(xiàn)線性的數(shù)據(jù)關(guān)系，所以使用順序表實(shí)現(xiàn)線性表。漢字字符占兩個(gè)字符型變量大小，用一個(gè)二維數(shù)組保存讀入的漢字集合。( 一 )線性表的基本操作因?yàn)闈h字需要兩個(gè)字符變量的大小，每行需要留出一個(gè)變量空間保存讀入漢字后的結(jié)束符 /0 。void initList()/數(shù)據(jù)初始化char chinese1003;/二維數(shù)組用于保存漢字集合char s203;/保存需查找的漢字i=0;j=0;k=0;用兩個(gè) txt文件分別存儲(chǔ)漢字集合和要查找的漢字?！?zizhuzhi.txt”保存漢字集合，“ chazhao.txt”保存需查找的字。分別從文件中讀入漢字，設(shè)置一個(gè)計(jì)數(shù)器，當(dāng)沒有訪問到文件末尾時(shí)

6、，每讀入一個(gè)漢字將其保存在二維數(shù)組中，計(jì)數(shù)器加一。 直到到達(dá)文件末尾，讀入漢字結(jié)束，取計(jì)數(shù)器的值作為漢字集合的長度。計(jì)數(shù)器清零，同樣的，讀入需查找的漢字后，取計(jì)數(shù)器的值作為需查找漢字的數(shù)組長度。void initList()/數(shù)據(jù)初始化i=0;j=0;k=0;void insert()char *p,temp2;p=temp;fstream outfile1;/創(chuàng)建一個(gè)文件精彩文檔實(shí)用標(biāo)準(zhǔn)文案fstream outfile2;if(!outfile1)cerr<<"file open error!"<<endl;exit(1);outfile1.op

7、en("zizuzhi.txt ",ios:in); /打開文件 zizuzhi.txti=0;while(!outfile1.eof()/沒有到達(dá)文件末尾時(shí)outfile1>>chinesei;/讀入i+;j=i-1;/漢字集合的長度i=0;/計(jì)數(shù)器清空outfile2.open("chazhao.txt",ios:in); /打開文件chazhao.txtwhile(!outfile2.eof()outfile2>>si;i+;k=i;/需查找漢字的個(gè)數(shù)outfile1.close();/關(guān)閉文本文件outfile2.clos

8、e();/ 獲得漢字集合的長度 int getLengthj()return j;/ 獲得需查找漢字?jǐn)?shù)組長度 int getLengthk()return k;/ 輸出讀入的文本文件記錄 void printout()cout<<" 讀入的一組漢字為："<<endl;for(i=0;i<getLengthj();i+)cout<<chinesei;cout<<"n要查找的漢字為:"<<endl;for(i=0;i<getLengthk();i+)cout<<si;cout

9、<<endl;( 二)轉(zhuǎn)置函數(shù)因?yàn)闈h字字符占兩個(gè)字符變量大小， 轉(zhuǎn)置要把存儲(chǔ)漢字字符的兩個(gè)字符單元內(nèi)容互相交換 , ，所以設(shè)置一個(gè)臨時(shí)字符變量 temp 作為轉(zhuǎn)置的中介。精彩文檔實(shí)用標(biāo)準(zhǔn)文案void Inverse(AList L,int i,int j)char temp=L.chinesei0;/臨時(shí)變量L.chinesei0=L.chinesej0;/字符第一個(gè)位置的交換chinesej0=temp;temp=L.chinesei1;L.chinesei1=L.chinesej1;/字符第二個(gè)位置的交換L.chinesej1=temp;( 三)查找函數(shù)設(shè)置一個(gè)全局變量flag

10、 ，當(dāng) flag=1時(shí)表示查找成功，當(dāng) flag=0時(shí)表示查找失敗。用需查找的漢字對一個(gè)已知長度的二維數(shù)組進(jìn)行遍歷，當(dāng)查找漢字的兩個(gè)字符變量分別與漢字集合中的漢字的字符變量對應(yīng)相等時(shí)， flag置為1，并在漢字集合中把查找到的漢字與前一位置的漢字交換位置，返回查找的次數(shù)。int flag;int search(AList L,int n)flag=0;int i;for(i=0;i<L.getLengthj();i+)if(L.chinesei0=L.sn0&&L.chinsesi1=L.sn1)/如果相等flag =1;/標(biāo)志變量為1break;if(flag)if(i

11、>0)Inverse(L,i,i-1); /漢字當(dāng)前位置和前一位置進(jìn)行交換return i+1;/返回查找的次數(shù)elsereturnL.getLengthj();/查找不成功， 查找次數(shù)即為數(shù)組長度算法的具體步驟void main()int i,n,num;AList L;fstream file;/聲明一個(gè)本件file，用于保存查找的結(jié)果L.initList();/初始化L.insert();/讀入漢字L.printout();/輸出漢字到屏幕file.open("查找結(jié)果 .txt",ios:out);精彩文檔實(shí)用標(biāo)準(zhǔn)文案for(i=0;i<L.getLen

12、gthk();i+)num=search(L,i);/返回查找的次數(shù)if(flag)/ 查找成功，輸出查找的次數(shù)else/ 查找不成功，輸出查找的次數(shù)所以各函數(shù)、模塊調(diào)用流程圖如下：開 始打 開 文 件 "zizhuz.txt"從文件讀入漢字集合chinese1003;打 開 文 件 "chazhao.txt"從文件讀入需查漢字s203;L.initList();L.insert();L.printout();int flag=0;fstream file;file.open(" 查 找 結(jié) 果 .txt",ios:out);YNfl

13、ag=1?查 找 成 功 ， 查 找 次 數(shù) 為 n查 找 失 敗 ， 查 找 次 數(shù) 為 n保存到文件結(jié)束算法的時(shí)空分析及改進(jìn)設(shè)想存儲(chǔ)的漢字用二維數(shù)組保存，所占空間復(fù)雜度為(n2) 。查找時(shí)的最好情況是每一次查找均第一次即查找到，此時(shí)的時(shí)間度為(n) ，最糟糕情況是都沒有找到或在末尾找到，時(shí)間復(fù)雜度為(n2) 。輸入和輸出的格式輸入：1.從文件讀入漢字集合到數(shù)組中outfile1.open("zizuzhi.txt",ios:in);/打開文本文件， 打開方精彩文檔實(shí)用標(biāo)準(zhǔn)文案式：讀入while(!outfile1.eof()/當(dāng)沒有訪問到文件末尾，向數(shù)組讀入漢字outf

14、ile1>>chinesei;2. 從文件中讀入查找漢字：outfile2.open("chazhao.txt",ios:in);/打開文本while(!outfile2.eof()outfile2>>si;/讀入要查找的漢字，保存在s1003數(shù)組輸出：1.查找成功if(flag)（輸出到屏幕） cout<<L.si<<"查找成功！ 查找次數(shù)為： "<<num<<endl;（ 輸 出 到 文 件 ） file<<L.si<<"查 找 成 功 ！ 查 找 次 數(shù) 為 ："<<num<<endl;2. 查找不成功 if(flag=0)（輸出到屏幕） cou