數(shù)據(jù)結(jié)構(gòu)試驗,線性表的插入和刪除,單鏈表操作,Huffman編碼樹

實驗一線性表的插入和刪除一、實驗?zāi)康?、掌握使用TuiboC上機調(diào)試線性表的基本方法；2、掌握線性表的基本操作：插入、刪除、查找以及合并等在順序存儲結(jié)構(gòu)上的運算。二、實驗要求1、認(rèn)真閱讀和掌握本實驗的給定的程序；2、按照你的操作需要，編制程序、上機調(diào)試運行程序；3、保存程序的運行結(jié)果，并結(jié)合程序進行分析。注意事項在磁盤上創(chuàng)建一個目錄，專門用于存儲數(shù)據(jù)結(jié)構(gòu)實驗的程序。三、實驗內(nèi)容利用順序表完成線性表信息的管理。要求首先建立并初始化線性表，并實現(xiàn)增加、刪除、查找、修改和遍歷表等功能。程序代碼如下：#include<iostieam.h>#include<stdlib.li>#defineMAX100typedefintdatatype;typedefstmctList(datatypeelem[MAX];intLast;}*SeqList; 〃定義順序表類型SeqListLutListO//初始化順序表(SeqListL;L=(SeqList)malloc(sizeof(List));L->Last=-1;letuniL;}voidCreateList(SeqListL)〃創(chuàng)建順序表(intn;coutv<”請輸入你要創(chuàng)建的順序表元素個數(shù)n=n；cin?n;COUtVV”請輸入你要創(chuàng)建的順序表:"；fbi(inti=0;i<n;i-H-)(cm?L->elem[i];L->Last++;))mtLocation(SeqListL,datatypex)〃查找某元素所在位置(int1=0;while(L->elem[i]!=x&&i<=L->Last)(i十十；)if(i>L->Last)return-1;elsereturni;)voidIiiseitelem(SeqListL,datatypem)〃土宙入元素intn;coutw”請輸入你要插入的位置n=”;cin?n;if((L->Last+1)>MAX)coutw”表以滿,能插入"wendl;else(L->Last++;i=L->Last;i>=n-1;i")(L->elem[i+1]=L->elem[i];)L->elem[n-l]=m;))voidDeleteelem(SeqListL.datatypem)〃刪除表中某元素(inti;i=Location(L,m);while(i==-l)(datatypen;coutvv”你所查找的元素不在表中,請重新輸入你要刪除的元素yvendl;cui?n;i=Location(L,n);)fbr(intj=i;j<=L->Last;j++)(L->elem[i]=L->elem[i+1];)L->Last--;voidShowList(SeqListL)〃顯示當(dāng)前順序表coutw”當(dāng)前順序表元素為』；fbr(inti=O;i<=L->Last;i++)(cout?L->elem[i]?nH;)cout?endl;)voidmain() ////////////〃/主函數(shù)(SeqListL;L=InitList();CieateList(L);intOpration;coutw”輸入操作:1為刪除某元素,2為插入,3為查找,4為輸出當(dāng)前順序表,5為退出“vvendl;while(Opration?=5)(cm?Opration;if(Opiation=l)(Ult11；coutvv”請輸入你要刪除的元素n=";cin?n;Deleteelem(Lji);)if(Opiation=2)(Ult11；cout?”請輸入你要插入的元素n=M;cin?n;nisertelem(L,n);)if(Opiatioii=3)(datatypex;coutvv”請輸入你要查找的元素x="；C111?X；coutvv”此元素在順序表中的位置為:"《Location(L,x)+lvvendl;)if(Opration=4)(ShowList(L);)if(Opiation=5)(break;)))實驗二單鏈表操作一、實驗?zāi)康?掌握握單鏈表的基本操作：插入、刪除、查找等運算；.理解掌握使用結(jié)構(gòu)體來表述復(fù)雜信息的方法及其基本操作。二、實驗要求.認(rèn)真思考，編制本實驗的程序。.上機調(diào)試、運行本程序。.保存程序的運行結(jié)果，并結(jié)合程序進行分析。.按照你對單鏈表的操作需要，重新改寫主程序并運行，保存文件清單和運行結(jié)果三、實驗內(nèi)容利用單鏈表完成一個班級的所有學(xué)生信息的管理：能夠增加、刪除、查找、修改學(xué)生的記錄。.學(xué)生信息內(nèi)容包括：姓名、性別、年齡、成績；.節(jié)點結(jié)構(gòu)：定義一個結(jié)構(gòu)類型，用來存放學(xué)生信息。程序代碼如下：ftinclude<windows.h>ftinclude<stdio.h>typedefstructStudentinfo(char stu_name[10];char stu_sex[4];int stu_age;int stu_num;int stu_english_grade;Studentinfo*pNext;}StudentInfo,*PStudentlnfo;PStudentlnfoListHead;PStudentlnfoListTail;int ListCount;voidInsertInfo()(PStudentlnfoInfo=(PStudentlnfo)LocalAlloc(0x40,sizeof(Studentinfo));printf(〃請輸學(xué)生姓名\r\n〃);scanf(〃%s〃，&Info->stu_.name);printf(〃請輸入學(xué)生學(xué)號\r\n〃);scanf("%d”,&Info->stu_num);printf(〃請輸入學(xué)生性別\r\n〃);scanf(〃%s〃,&Info->stu_sex);printf(〃請輸入學(xué)生年齡\r\n〃);scanf("%d”,&Info->stu_age);printf(〃請輸入學(xué)生英語成績\r\n〃)；scanf(〃/d〃，&Info->stu_english_grade);PStudentlnfoptemp=ListHead;if(ptemp)while(ptemp)(if(ptemp->stu_num==Info->stu_num)(""printf(〃請不要重復(fù)插入相同學(xué)號的信息\r\n〃);LocalFree(Info);return;)ptemp=ptemp->pNext;))if(ListHead)(if(ListCount==l)(ListTail=Info;ListTail->pNext=NULL;ListHead->pNext=ListTail;)else(Info->pNext=NULL;ListTail->pNext=Info;))else(Info->pNext=NULL;ListHead二Info;)ListCount++;printf(〃當(dāng)前的學(xué)生信息數(shù)量%d\r\n",ListCount);)voidRemoveinfo(intnStuNum)(if(ListHead)(PStudentlnfotemp,pretemp;temp=ListHead;pretemp二temp;while(temp)if(temp->stu_numz:=nStuNum)(一pretemp->pNext=temp->pNext;LocalFree(temp);printf(〃刪除成功\r\n〃);ListCount―;printf(〃當(dāng)前的學(xué)生信息數(shù)量的d\r\n〃,ListCount);return;)pretemp=temp;temp=temp->pNext;)printf(〃沒有找到要刪除的信息〃);)else(printf(〃沒有可供操作的學(xué)生信息\r\n");))voidfindinfo(intnStuNum)(PStudentlnfotemp;temp=ListHead;while(temp)(if(temp->stu_num==nStuNum)(-printf(〃姓名：%s性別：%s學(xué)號格d年齡:/d英語成績:/d\r\n〃，temp->stu_name,temp->stu_sex,temp->stu_num,temp->stu_age,temp->stu_english_grade);break;)temp=temp->pNext;)if(!temp)(printf(〃沒有找到相關(guān)信息\r\n〃)；))intmain()ListHead=NULL;ListTail=NULL;ListCount=0;intnOperateState;while(TRUE)(printf(〃選擇你要操作的方法，1為插入，2為刪除，3為查詢！4為退出\r\n〃);scanf("%d〃,&nOperateState);switch(nOperateState)(Insertinfo();break;(printf(〃請輸入你要刪除的學(xué)號\r\n〃);intntemp;scanf(“%d〃,Sntemp);Removeinfo(ntemp);)break;printf(〃請輸入你要查詢的學(xué)號\r\n〃);intntemp;scanf(“%d〃,Sntemp);findlnfo(ntemp);break;exit(0);break;default：break;))return0;)實驗四Huffman編碼樹（選作）.實驗?zāi)康?進一步理解掌握指針變量的含義；.掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點及使用范圍；.掌握有Huffman編碼基本原理；.掌握Huffman編碼樹的建立以及利用它進行編碼/反編碼的方法。.實驗要求.認(rèn)真閱讀和掌握本實驗的要求；.上機運行本程序；.保存和打印出程序的運行結(jié)果，并結(jié)合程序進行分析；.按照你對圖的操作需要，重新改寫主程序并運行，打印出文件清單和運行結(jié)果。.實驗內(nèi)容利用Huffinan進行通信可以提高信道利用率、縮短傳輸時間。要求為使用Huffman編碼的通信系統(tǒng)實現(xiàn)信息收發(fā)編寫程序，以順序存儲結(jié)構(gòu)方式存儲二義樹，實現(xiàn)Huffman編譯碼。參考程序如下：一棵有n個葉子結(jié)點的Huffinan樹有2n-l個結(jié)點采用順序存儲結(jié)構(gòu)———維結(jié)構(gòu)數(shù)組結(jié)點類型定義程序代碼如下：typedefstnict{intdata;mtpajcjc;}JD;Huffinan算法實現(xiàn)：voidliuffinan(intn,intw[]JDt[]){inti,j,k,x1,x2,m1,m2;fdr(i=l;i<(2*n);i++){t[i].pa=t[i].lc=t[i].ic=O;if(i<=n)t[i].data=w[i];elset[i].data=O;)for(i=l;i<n;i++){ml=m2=MAX;xl=x2=0;for0=l;j<(n+i);j++){if((t[j].data<ml)&&(t[j].pa=O)){ni2=ml;x2=xl;ml=t|j].data;xl=j;)elseif((t[j].data<m2)&&(t|j].pa==0)){ni2=t[j].data;x2可；})k=n+i;t[x1].pa=t[x2].pa=k;t[k].data=ml+m2;t[k].lc=xl;t[k].ic=x2;))實驗五交通信息查詢(選作)一.實驗?zāi)康?掌握圖的基本存儲方法；.熟悉掌握有關(guān)圖存儲結(jié)構(gòu)和構(gòu)造算法，了解實際問題的求解與采用何種存儲結(jié)構(gòu)及算11法有密切的關(guān)系；.掌握圖的最短路徑求解算法并編程實現(xiàn)。.實驗要求.認(rèn)真查閱有關(guān)資料，編寫和掌握本實驗的程序；.上機輸入、調(diào)試實驗程序；.保存程序的運行結(jié)果，并結(jié)合程序進行分析。.實驗內(nèi)容輸入交通圖，編制交通信息咨詢程序。不同客戶對交通工具的選擇有不同的要求（時間、費用等），為旅客提供最優(yōu)交通路線信息服務(wù)。.選擇適當(dāng)?shù)拇鎯Y(jié)構(gòu)，實現(xiàn)對地圖的輸入、編輯和輸出；.提供友好的用戶界面，滿足不同客戶的各種信息查詢。#include<iostieam>#include<fstream>#include<cstrmg>#include<cstdio>#deflneMAX_NUM2000usingnamespacestd;inti,j,n;mtw[27];charsti[200];charch;typedefstruct{chars;mtnum;}Node;Nodenode[27];〃用結(jié)構(gòu)數(shù)組存放輸入的字符及其權(quán)值typedefstmct{unsignedmtweight;unsignedmtparentjchildjchild;12}HTNode,*HuffinanTiee;//動態(tài)分配數(shù)組儲存哈夫曼樹typedefchar**HuffinanCode;HuffinanTieeHT;HuffinanCodeHC;voidSelect(HuffinanTieeHTjntendjnt &s2)〃在HT[l..end]中選擇parent為0且weight最小的兩個結(jié)點si和s2,end為總長度{mtminl=MAX_NUM;mtmm2;fdr(i=1;i<end;i-H-){if((HT[i].parent=0)&&(HT[i].weight<miii1)){sl=i;min1=HT[i].weight;))miii2=MAX_NUM;for(j=l;j<end;j++){if((HT|j].paient==0)&&(sl!=j)&&(HT|j].weight<miii2)){s2=j;mm2=HT|j].weight;)))fstreamoutfilel(,,hufintiee.txt,\ios::out);fstreamoutfile2(,,TieePiuit.txtHJos::out);voidpruittiee(intm.HuffinanTree&HT,inti)(if(HT[m].Ichild!=0||HT[m].rchild?=0)fbr(intp=0;p<i;p++)cout?H,\outfilel?M\outfile2?H,r;13cout?HT[m].weighWv'*'<<endl;outfilel?HT[m].weight?',?,*,?endl;outfile2?HT[m].weight?',?,*,?endl;printtree(HT[m].lcliild,HT,i+3);printtree(HT[m].ichild,HT4+3);)if(HT[m].lchild==O&&HT[m].rcliild=O){for(intp=O;p<i;p-H-)cout?nH,outfilel?MH.outfile2?nH;cout?HT[m].weight?,^nodetm-1].s?endl;outfile1?HT[m].weiglit?,^nodefm-1].s?endl;outfile2?HT[m].weiglit?,^nodefm-1].s?endl;))〃遞歸算法，以凹入形式輸出樹voidHuffinanCodmg(HufiinanTree&HT.HuffinanCode&HC,int*w,intn)//構(gòu)造哈夫曼樹HT,并求出n個字符的哈夫曼編碼HC.{if(n<l)xetuin;nitm=2*n-l;nitsl,s2;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));〃。號單元未用HufiinanTieep;foi(p=HT+l,i=l;i〈=n;十十i,十十p,++w){p->weight=*w;p->parent=0;p->lchild=0;p->ichild=0;)fbr(;i<=m;++i,++p){p->weight=0;p->parent=0;p->lchild=0;14p->ichild=O;)foi(i=n+l 〃建哈夫曼樹Select(HT,i,sl,s2);HT[sl].parent=i;HT[s2].parent=i;HT[i].lcluld=sl;HT[i].rcluld=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;)〃從葉子到根逆向求每個字符的哈夫曼編碼HC=(HuffinanCode)malloc((n+l)*sizeof(char*));〃分配n個字符編碼的頭指針向量char*cd;cd=(chai*)malloc(n*sizeof(chaf));cd[n-l]=,\0,;intc,f,start;fbr(i=l;i<=n;i-H-){stait=n-l;foi(c=i,f=HT[i].parent;f!=0;c=f1f=HT[f].parent){if(HT[f].lchild=c)cd[--start]=O;elsecd[—start]-1';)HC[i]=(char*)malloc((n-l)*sizeof(cliar));sticpy(HC[i],&cd[start]);)coutvv”各個字符及其編碼如下："vvendl;for(j=1;j<=n;j++)cout?node[j-l].s?,,(H<<HC[j]?,,)n?eiidl;fiee(cd);coutw“哈夫曼樹輸出如下(凹入形式)H?endl;pnnttiee(2*n-1,HT,0);15getcharO；getcharO；)voidEncodingO{HuffinanCoding(HT.HC,w,n);cout 請輸入要進行編碼的句子(S代替空格):“VVendl;fstreammfilel(uToBeTran.txtn4OS：:out);if(!infile1)exit(-l);cm?str;infilel?str;infilel.close();fstreammfile2(uToBeTran.txtn4OS：:in);if(