数据结构实验线性表的插入和删除单链表操作Huffman编码树.docx
- 文档编号:14504590
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:22
- 大小:20.07KB
数据结构实验线性表的插入和删除单链表操作Huffman编码树.docx
《数据结构实验线性表的插入和删除单链表操作Huffman编码树.docx》由会员分享,可在线阅读,更多相关《数据结构实验线性表的插入和删除单链表操作Huffman编码树.docx(22页珍藏版)》请在冰点文库上搜索。
数据结构实验线性表的插入和删除单链表操作Huffman编码树
实验一线性表的插入和删除
一、实验目的
1、掌握使用TurboC上机调试线性表的基本方法;
2、掌握线性表的基本操作:
插入、删除、查找以及合并等在顺序存储结构上的运算。
二、实验要求
1、认真阅读和掌握本实验的给定的程序;
2、按照你的操作需要,编制程序、上机调试运行程序;
3、保存程序的运行结果,并结合程序进行分析。
注意事项
在磁盘上创建一个目录,专门用于存储数据结构实验的程序。
三、实验内容
利用顺序表完成线性表信息的管理。
要求首先建立并初始化线性表,并实现增加、删除、查找、修改和遍历表等功能。
程序代码如下:
#include
#include
#defineMAX100
typedefintdatatype;
typedefstructList
{
datatypeelem[MAX];
intLast;
}*SeqList;//定义顺序表类型
SeqListInitList()//初始化顺序表
{
SeqListL;
L=(SeqList)malloc(sizeof(List));
L->Last=-1;
returnL;
}
voidCreateList(SeqListL)//创建顺序表
{
intn;
cout<<"请输入你要创建的顺序表元素个数n=";
cin>>n;
cout<<"请输入你要创建的顺序表:
";
for(inti=0;i { cin>>L->elem[i]; L->Last++; } } intLocation(SeqListL,datatypex)//查找某元素所在位置 { inti=0; while(L->elem[i]! =x&&i<=L->Last) { i++; } if(i>L->Last) return-1; else returni; } voidInsertelem(SeqListL,datatypem)//插入元素 { intn; cout<<"请输入你要插入的位置n="; cin>>n; if((L->Last+1)>MAX) cout<<"表以满,能插入"< else { L->Last++; for(inti=L->Last;i>=n-1;i--) { L->elem[i+1]=L->elem[i]; } L->elem[n-1]=m; } } voidDeleteelem(SeqListL,datatypem)//删除表中某元素 { inti; i=Location(L,m); while(i==-1) { datatypen; cout<<"你所查找的元素不在表中,请重新输入你要删除的元素"< cin>>n; i=Location(L,n); } for(intj=i;j<=L->Last;j++) { L->elem[i]=L->elem[i+1]; } L->Last--; } voidShowList(SeqListL)//显示当前顺序表 { cout<<"当前顺序表元素为: "; for(inti=0;i<=L->Last;i++) { cout< } cout< } voidmain()///////////////主函数 { SeqListL; L=InitList(); CreateList(L); intOpration; cout<<"输入操作: 1为删除某元素,2为插入,3为查找,4为输出当前顺序表,5为退出"< while(Opration! =5) { cin>>Opration; if(Opration==1) { intn; cout<<"请输入你要删除的元素n="; cin>>n; Deleteelem(L,n); } if(Opration==2) { intn; cout<<"请输入你要插入的元素n="; cin>>n; Insertelem(L,n); } if(Opration==3) { datatypex; cout<<"请输入你要查找的元素x="; cin>>x; cout<<"此元素在顺序表中的位置为: "< } if(Opration==4) { ShowList(L); } if(Opration==5) { break; } } } 实验二单链表操作 一、实验目的 1.掌握握单链表的基本操作: 插入、删除、查找等运算; 2.理解掌握使用结构体来表述复杂信息的方法及其基本操作。 二、实验要求 1.认真思考,编制本实验的程序。 2.上机调试、运行本程序。 3.保存程序的运行结果,并结合程序进行分析。 4.按照你对单链表的操作需要,重新改写主程序并运行,保存文件清单和运行结果 三、实验内容 利用单链表完成一个班级的所有学生信息的管理: 能够增加、删除、查找、修改学生的记录。 1.学生信息内容包括: 姓名、性别、年龄、成绩; 2.节点结构: 定义一个结构类型,用来存放学生信息。 程序代码如下: #include #include typedefstructStudentInfo { charstu_name[10]; charstu_sex[4]; intstu_age; intstu_num; intstu_english_grade; StudentInfo*pNext; }StudentInfo,*PStudentInfo; PStudentInfoListHead; PStudentInfoListTail; intListCount; voidInsertInfo() { PStudentInfoInfo=(PStudentInfo)LocalAlloc(0x40,sizeof(StudentInfo)); printf("请输学生姓名\r\n"); scanf("%s",&Info->stu_name); printf("请输入学生学号\r\n"); scanf("%d",&Info->stu_num); printf("请输入学生性别\r\n"); scanf("%s",&Info->stu_sex); printf("请输入学生年龄\r\n"); scanf("%d",&Info->stu_age); printf("请输入学生英语成绩\r\n"); scanf("%d",&Info->stu_english_grade); PStudentInfoptemp=ListHead; if(ptemp) { while(ptemp) { if(ptemp->stu_num==Info->stu_num) { printf("请不要重复插入相同学号的信息\r\n"); LocalFree(Info); return; } ptemp=ptemp->pNext; } } if(ListHead) { if(ListCount==1) { ListTail=Info; ListTail->pNext=NULL; ListHead->pNext=ListTail; } else { Info->pNext=NULL; ListTail->pNext=Info; } } else { Info->pNext=NULL; ListHead=Info; } ListCount++; printf("当前的学生信息数量%d\r\n",ListCount); } voidRemoveInfo(intnStuNum) { if(ListHead) { PStudentInfotemp,pretemp; temp=ListHead; pretemp=temp; while(temp) { if(temp->stu_num==nStuNum) { pretemp->pNext=temp->pNext; LocalFree(temp); printf("删除成功\r\n"); ListCount--; printf("当前的学生信息数量%d\r\n",ListCount); return; } pretemp=temp; temp=temp->pNext; } printf("没有找到要删除的信息"); } else { printf("没有可供操作的学生信息\r\n"); } } voidfindInfo(intnStuNum) { PStudentInfotemp; temp=ListHead; while(temp) { if(temp->stu_num==nStuNum) { printf("姓名: %s性别: %s学号: %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("没有找到相关信息\r\n"); } } intmain() { ListHead=NULL; ListTail=NULL; ListCount=0; intnOperateState; while(TRUE) { printf("选择你要操作的方法,1为插入,2为删除,3为查询! 4为退出\r\n"); scanf("%d",&nOperateState); switch(nOperateState) { case1: InsertInfo(); break; case2: { printf("请输入你要删除的学号\r\n"); intntemp; scanf("%d",&ntemp); RemoveInfo(ntemp); } break; case3: printf("请输入你要查询的学号\r\n"); intntemp; scanf("%d",&ntemp); findInfo(ntemp); break; case4: exit(0); break; default: break; } } return0; } 实验四Huffman编码树(选作) 一.实验目的 1.进一步理解掌握指针变量的含义; 2.掌握二叉树的结构特征,以及各种存储结构的特点及使用范围; 3.掌握有Huffman编码基本原理; 4.掌握Huffman编码树的建立以及利用它进行编码/反编码的方法。 二.实验要求 1.认真阅读和掌握本实验的要求; 2.上机运行本程序; 3.保存和打印出程序的运行结果,并结合程序进行分析; 4.按照你对图的操作需要,重新改写主程序并运行,打印出文件清单和运行结果。 三.实验内容 利用Huffman进行通信可以提高信道利用率、缩短传输时间。 要求为使用Huffman编码的通信系统实现信息收发编写程序,以顺序存储结构方式存储二叉树,实现Huffman编译码。 参考程序如下: ◆一棵有n个叶子结点的Huffman树有2n-1个结点 ◆采用顺序存储结构——一维结构数组 ◆结点类型定义 程序代码如下: typedefstruct {intdata; intpa,lc,rc; }JD; Huffman算法实现: voidhuffman(intn,intw[],JDt[]) {inti,j,k,x1,x2,m1,m2; for(i=1;i<(2*n);i++) {t[i].pa=t[i].lc=t[i].rc=0; if(i<=n) t[i].data=w[i]; else t[i].data=0; } for(i=1;i {m1=m2=MAX; x1=x2=0; for(j=1;j<(n+i);j++) {if((t[j].data {m2=m1;x2=x1; m1=t[j].data;x1=j; } elseif((t[j].data {m2=t[j].data;x2=j;} } k=n+i; t[x1].pa=t[x2].pa=k; t[k].data=m1+m2; t[k].lc=x1; t[k].rc=x2; } } 实验五交通信息查询(选作) 一.实验目的 1.掌握图的基本存储方法; 2.熟悉掌握有关图存储结构和构造算法,了解实际问题的求解与采用何种存储结构及算法有密切的关系; 3.掌握图的最短路径求解算法并编程实现。 二.实验要求 1.认真查阅有关资料,编写和掌握本实验的程序; 2.上机输入、调试实验程序; 3.保存程序的运行结果,并结合程序进行分析。 三.实验内容 输入交通图,编制交通信息咨询程序。 不同客户对交通工具的选择有不同的要求(时间、费用等),为旅客提供最优交通路线信息服务。 1.选择适当的存储结构,实现对地图的输入、编辑和输出; 2.提供友好的用户界面,满足不同客户的各种信息查询。 #include #include #include #include #defineMAX_NUM2000 usingnamespacestd; inti,j,n; intw[27]; charstr[200]; charch; typedefstruct{ chars; intnum; }Node; Nodenode[27];//用结构数组存放输入的字符及其权值 typedefstruct{ unsignedintweight; unsignedintparent,lchild,rchild; }HTNode,*HuffmanTree;//动态分配数组储存哈夫曼树 typedefchar**HuffmanCode; HuffmanTreeHT; HuffmanCodeHC; voidSelect(HuffmanTreeHT,intend,int&s1,int&s2) //在HT[1..end]中选择parent为0且weight最小的两个结点s1和s2,end为总长度 {intmin1=MAX_NUM; intmin2; for(i=1;i {if((HT[i].parent==0)&&(HT[i].weight {s1=i; min1=HT[i].weight; } } min2=MAX_NUM; for(j=1;j {if((HT[j].parent==0)&&(s1! =j)&&(HT[j].weight {s2=j; min2=HT[j].weight; } } } fstreamoutfile1("hufmtree.txt",ios: : out); fstreamoutfile2("TreePrint.txt",ios: : out); voidprinttree(intm,HuffmanTree&HT,inti) { if(HT[m].lchild! =0||HT[m].rchild! =0) { for(intp=0;p cout<<"",outfile1<<"",outfile2<<""; cout< outfile1< outfile2< printtree(HT[m].lchild,HT,i+3); printtree(HT[m].rchild,HT,i+3); } if(HT[m].lchild==0&&HT[m].rchild==0){ for(intp=0;p cout< outfile1< outfile2< } }//递归算法,以凹入形式输出树 voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn) //构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC. {if(n<1)return; intm=2*n-1; ints1,s2; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用 HuffmanTreep; for(p=HT+1,i=1;i<=n;++i,++p,++w) {p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; } for(;i<=m;++i,++p) {p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } for(i=n+1;i<=m;++i){//建哈夫曼树 Select(HT,i,s1,s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } //从叶子到根逆向求每个字符的哈夫曼编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量 char*cd; cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; intc,f,start; for(i=1;i<=n;i++){ start=n-1; for(c=i,f=HT[i].parent;f! =0;c=f,f=HT[f].parent) {if(HT[f].lchild==c)cd[--start]='0'; elsecd[--start]='1'; } HC[i]=(char*)malloc((n-1)*sizeof(char)); strcpy(HC[i],&cd[start]); } cout<<"各个字符及其编码如下: "< for(j=1;j<=n;j++)cout< free(cd); cout<<"哈夫曼树输出如下(凹入形式)"< printtree(2*n-1,HT,0); getchar(); getchar(); } voidEncoding() {HuffmanCoding(HT,HC,w,n); cout<<"请输入要进行编码的句子($代替空格): "< fstreaminfile1("ToBeTran.txt",ios: : out); if(! infile1)exit(-1); cin>>str; infile1< infile1.close(); fstreaminfile2("ToBeTran.txt",ios: : in); if(! infile2)exit(-1); fstreamoutfile("CodeFile.txt",ios: : out); if(! outfile)exit(-1); infile2.get(ch);//读字符 cout<<"该句子编码后为"; while(! infile2.eof()){ for(j=1;j<=n;j++){ if(ch==node[j-1].s){ cout< outfile< } } infile2.get(ch); } infile2.close(); outfile.close(); }//存放编译后的二进制编码 voidDecoding(intn) {fstreaminfile("CodeFile.txt",ios: : in); if(! infile)exit(-1); fstreamoutfile("TextFile.txt",ios: : out); if(! outfile)exit(-1); inta; cout<<"译码后如下($为空格): "< infile.get(ch); while(! infile.eof()) {a=2*n-1; while(a>n) { if(ch=='0')a=HT[a].lchild; elsea=HT[a].rchild; infile.get(ch); } cout< outfile< } infile.clos
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 线性 插入 删除 单链表 操作 Huffman 编码