数据结构c++顺序表单链表的基本操作查找排序代码.docx
- 文档编号:4364593
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:21
- 大小:102.75KB
数据结构c++顺序表单链表的基本操作查找排序代码.docx
《数据结构c++顺序表单链表的基本操作查找排序代码.docx》由会员分享,可在线阅读,更多相关《数据结构c++顺序表单链表的基本操作查找排序代码.docx(21页珍藏版)》请在冰点文库上搜索。
数据结构c++顺序表单链表的基本操作查找排序代码
实验1:
顺序表的基本操作
一、实验目的
1、掌握使用VC++6.0上机调试顺序表的基本方法。
2、通过实验,掌握顺序表的建立与输出。
3、通过实验,掌握顺序表的基本操作。
二、实验内容
1、使用malloc函数,实现顺序空间定义。
2、练习顺序表的建立与输出。
3、练习顺序表的基本操作。
三、实验前的准备
1、复习相关课程内容。
2、理解并掌握顺序表的存储结构、基本操作。
3、准备相关的程序清单。
四、实验要求
1、建立个人的工作目录。
2、编写算法,完成顺序表中指定位置数据的输出、元素的插入和删除。
4、源程序给出注释。
4、保存和打印出程序的运行结果,并结合程序进行分析。
五、实验中出现的问题与解决方法
实验2:
单链表的基本操作
一、实验目的
1、掌握使用VC++6.0上机调试单链表的基本方法。
2、掌握不带头结点单链表的建立、查找、插入、删除等基本操作。
3、掌握带头结点单链表的建立、查找、插入、删除等基本操作。
二、实验内容
1、练习单链表的建立与输出。
2、练习单链表的基本操作的实现。
3、练习单链表基本操作的应用。
三、实验前的准备
1、复习相关课程内容。
2、理解并掌握单链表基本操作。
3、准备相关的程序清单。
四、实验要求
1、建立个人的工作目录。
2、编写算法,完成建立单链表、计算单链表长度、输出单链表中元素。
3、编写算法,完成单链表指定位置元素的插入、删除。
4、源程序给出注释。
5、保存和打印出程序的运行结果,并结合程序进行分析。
五、实验中出现的问题与解决方法
实验3:
查找
一、实验目的
1、掌握用VC++6.0实现查找算法的方法。
2、掌握常用的查找方法。
3、掌握二叉排序树的构造及其查找方法。
二、实验内容
1、练习顺序查找。
2、练习有序表的对分查找。
3、练习二叉排序树查找。
三、实验前的准备
1、复习相关课程内容。
2、准备相关的程序清单。
四、实验要求
1、建立个人的工作目录。
2、完成顺序表上顺序查找元素的算法。
3、完成有序表上对分法查找元素的算法。
4、完成二叉排序树的构造以及利用二叉排序树进行查找。
5、源程序给出注释。
6、保存和打印出程序的运行结果,并结合程序进行分析。
五、实验中出现的问题与解决方法
实验4:
排序
一、实验目的
1、掌握用VC++6.0实现排序算法的方法。
2、理解排序的定义和各种排序方法的特点,并能加以灵活应用。
二、实验内容
1、练习冒泡排序法。
2、练习快速排序法。
3、练习简单插入排序法。
4、练习简单选择排序法。
三、实验前的准备
1、复习相关课程内容。
2、准备相关的程序清单。
四、实验要求
1、建立个人的工作目录。
2、完成顺序表上的各种排序算法。
3、源程序给出注释。
4、保存和打印出程序的运行结果,并结合程序进行分析。
五、实验中出现的问题与解决方法
实验1代码及结果:
#include
usingnamespacestd;
template
classsq_LList
{private:
intmm;
intnn;
T*v;
public:
sq_LList(){mm=0;nn=0;return;}
sq_LList(int);
voidprt_sq_LList();
intflag_sq_LList();
voidins_sq_LList(int,T);
voiddel_sq_LList(int);
};
//建立空顺序表
template
sq_LList
:
sq_LList(intm)
{mm=m;
v=newT[mm];
nn=0;
return;
}
//顺序输出顺序表中的元素与顺序表长度
template
voidsq_LList
:
prt_sq_LList()
{inti;
cout<<"nn="< for(i=0;i return; } //检测顺序表的状态 template intsq_LList : flag_sq_LList() {if(nn=mn)return(-1); if(nn=0)return(0); return (1); } //在表的指定元素前插入新元素 template voidsq_LList : ins_sq_LList(inti,Tb) {intk; if(nn==mm) {cout<<"overflow"< if(i>nn)i=nn+1; if(i<1)i=1; for(k=nn;k>=i;k--) v[k]=v[k-1]; v[i-1]=b; nn=nn+1; return; } //在顺序表中删除指定元素 template voidsq_LList : del_sq_LList(inti) {intk; if(nn==0) {cout<<"underflow! "< return; } for(k=i;k v[k-1]=v[k]; nn=nn-1; return; } intmain() {sq_LList cout<<"第一次输出顺序表对象s1: "< s1.prt_sq_LList(); s1.ins_sq_LList(0,1.5); s1.ins_sq_LList(1,2.5); s1.ins_sq_LList(4,3.5); cout<<"第二次输出顺序表对象s1: "< s1.prt_sq_LList(); s1.del_sq_LList(0); s1.del_sq_LList (2); cout<<"第三次输出顺序表对象s1: "< s1.prt_sq_LList(); return0; } 运行及结果: 实验2代码 #include #include usingnamespacestd; structnode{ floatdata; node*next; }; node*create(){//建立单链表 node*head,*p,*s; head=newnode; p=head; p->data=0; p->next=0;//表头创建完成 floatnewnum=0; cin>>newnum; if(newnum<0){ cout<<"未输入数据...\n";//输入负数则结束 system("pause");} while(newnum>=0){//? ? 如何用字符型作为结束标志 s=newnode;//创建表中数据 s->data=newnum; p->next=s; p=s; cin>>newnum;} p->next=NULL;//最后元素指针 return(head);//返回空表头 } //插入一个结点x,将成为第i个节点 voidinsertnode(node*head,inti,floatx){ node*s,*p; intj; s=newnode; s->data=x; p=head; j=1;//查找第i个结点,由p指向 while(p! =NULL&&j j++; p=p->next;} s->next=p->next; p->next=s; } //删除结点x voiddeletenode(node*head,floatx){ node*p,*s; if(head->next==NULL) cout<<"这是空链表,不能执行删除操作\n"; else{ s=head; p=head->next; while(p! =NULL&&p->data! =x) if(p->data! =x){ s=p; p=p->next; } if(p! =NULL){ s->next=p->next; delete(p); } elsecout<<"未找到! \n"; } } //存取链表某节点K voidread(node*head,intk){ while(head->next! =0&&k>0){ head=head->next; k--; } cout<<"该处数据为"< } intmain(){ node*linktable=0; intchoice=1; cout<<"1.创建链表\n"; cout<<"2.显示信息\n"; cout<<"3.删除信息\n"; cout<<"4.查找信息\n"; cout<<"5.插入信息\n"; cout<<"6.读取信息\n"; cout<<"0.退出程序\n"; cout<<"请输入您的选择: "; cin>>choice; while (1){ switch(choice){ case0: exit(0); case1: {cout<<"输入正数数据,并以负数作为结束标记\n"; linktable=create();break;} case2: {cout<<"链表长度为"< \n"; printlist(linktable);break;} case3: {cout<<"要删除的数据为? \n"; floatdel; cin>>del; deletenode(linktable,del);break;} case4: {if(linktable->next==0) cout<<"链表为空,不能查找\n"; else{ cout<<"要查找数据为? "; floatsearch; cin>>search; find(linktable,search); }break;} case5: {cout<<"存储数据为? "; intdes; floatit; cin>>it; cout<<"想让该数据存储为第几个节点? "; cin>>des; if((des>(length(linktable)+1)||des<1)) cout<<"输入错误\n"; else insertnode(linktable,des,it);break;} case6: {cout<<"想读取第几个节点? "; intc; cin>>c; if(c<1||c>length(linktable)) cout<<"位置不合法\n"; else read(linktable,c); break; } default: cout<<"输入错误! \n"; } system("pause"); system("cls"); cout<<"当前信息: \n"; printlist(linktable); cout<<"\n1.创建链表\n"; cout<<"2.显示信息\n"; cout<<"3.删除信息\n"; cout<<"4.查找信息\n"; cout<<"5.插入信息\n"; cout<<"6.读取信息\n"; cout<<"0.退出程序\n"; cout<<"继续选择: \n"; cin>>choice; } return0; } 实验三查找 实验名称: 实验3查找 实验目的: 掌握顺序表和有序表的查找方法及算法实现;掌握二叉排序树和哈希表的构造和查找方法。 通过上机操作,理解如何科学地组织信息存储,并选择高效的查找算法。 实验内容: (2选1)内容1: 基本查找算法;内容2: 哈希表设计。 实验要求: 1)在C++系统中编程实现;2)选择合适的数据结构实现查找算法;3)写出算法设计的基本原理或画出流程图;4)算法实现代码简洁明了;关键语句要有注释;5)给出调试和测试结果;6)完成实验报告。 实验步骤: (1)算法设计 a.构造哈希函数的方法很多,常用的有 (1)直接定址法 (2)数字分析法;(3)平方取中法;(4)折叠法;(5)除留余数法;(6)随机数法;本实验采用的是除留余数法: 取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址 (2)算法实现 hashhashlist[n]; voidlistname(){ char*f; ints0,r,i; NameList[0].py="baojie"; NameList[1].py="chengaoyang"; ……………………………… NameList[29].py="wurenke"; for(i=0;i for(r=0;*(f+r)! ='\0';r++)s0+=*(f+r);NameList[i].k=s0;}} voidcreathash(){inti; for(i=0;i hashlist[i].py="";hashlist[i].k=0;hashlist[i].si=0;} for(i=0;i intsum=0; intadr=(NameList[i].k)%M; intd=adr; if(hashlist[adr].si==0){ hashlist[adr].k=NameList[i].k; hashlist[adr].py=NameList[i].py; hashlist[adr].si=1;} else{while(hashlist[d].k! =0) {d=(d+NameList[i].k%10+1)%M;sum=sum+1;} hashlist[d].k=NameList[i].k;hashlist[d].py=NameList[i].py; hashlist[d].si=sum+1;}}} voidfindlist(){ stringnam;ints0=0,r,sum=1;cout<<"请输入姓名的拼音: "< for(r=0;r<20;r++) s0+=nam[r];intadr=s0%M;intd=adr; if(hashlist[adr].k==s0) cout<<"姓名: "< "< elseif(hashlist[adr].k==0)cout<<"无此记录! "< else{intg=0;while(g==0){ d=(d+s0%10+1)%M;sum=sum+1; if(hashlist[d].k==0){cout<<"无此记录! "< if(hashlist[d].k==s0){ cout<<"姓名: "< "< 1"< voiddisplay(){inti; for(i=0;i<30;i++)cout< intmain(){ charx; listname(); creathash(); cout<<"d.显示哈希表f.查找任意键退出请选择"< while(cin>>x){ if(x=='d'){display();cout< elseif(x=='f'){findlist();cout< elsebreak;} return0; } 实验结果: 实验四排序 一、实验目的和要求: 掌握各种排序方法的排序过程; 了解一些排序算法的实现,如插入排序、选择排序、冒泡排序、快速排序、堆排序等。 二、实验原理: 1.排序的相关术语: 内部排序: 对内存中的数据进行排序,即排序不涉及数据内、外存交换。 外部排序: 按照某种策略将外存数据分批调入内存进行排序,从而达到整体有序。 排序时涉及数据的内、外存交换。 关键字: 用于标识记录的数据项。 排序方法的稳定性: 具有相同关键字的记录之间相对次序保持不变的排序方法是稳定的,否则是不稳定的。 堆: 关键字K1,K2,…Kn构成堆当且仅当排序满足如下性质: Ki<=K2i且Ki<=K2i+1或Ki>=K2i且Ki>=K2i+1(1<=i<=n/2) 就地排序: 排序算法所需的辅助空间不依赖于问题的规模n. 2.排序方法: 插入排序: a.直接插入排序 b.希尔排序: 将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。 交换排序: a.冒泡排序 b.快速排序: 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小。 然后分别对这两部分记录继续进行排序,以达到整个序列有序。 选择排序: a.简单选择排序 b.堆排序 归并排序: 将两个或两个以上的有序表组合成一个新的有序表。 三、实验内容: 学生成绩由学生的学号、姓名和成绩组成,设计一个程序对给定的n个学生信息实现: 按分数的高低排序,打印每个学生在考试中的排名,分数相同的为同一名次,同一名次的同学按学号从小到大排列。 按照名次列出每个学生的名次、学号、姓名和成绩。 四、程序设计: 程序设计思想: 建立一个学生类: 其中包含学生的基本信息: 学号、姓名成绩以及名次。 主函数包括: 学生信息输入函数: 要求从键盘上输入学生的学号、姓名、以及成绩。 学生成绩排序函数: 按照学生成绩排序——冒泡排序,用一个数组b[n]记录学生的名次。 学生信息输出函数: 按照学生的名次列出每个学生的名次、学号、姓名和成绩。 源代码: #include usingnamespacestd; #include #include #defineN7//学生人数; classStudent {public: charxingming[20]; intnum; intscore; }; intmain() {Studenta[N]; cout<<"请输入注册学生的人数: "< for(inti=0;i {cout<<"请输入学生的学号、姓名和成绩: "< cin>>a[i].num>>a[i].xingming>>a[i].score;} for(intm=0;m {printf("%d%s%d",a[m].num,a[m].xingming,a[m].score); printf("\n");} cout<<"按名次列出学生的学号、姓名、成绩和名次:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 c+ 顺序 表单 基本 操作 查找 排序 代码