数据结构c++顺序表单链表的基本操作查找排序代码Word文件下载.docx
- 文档编号:6642125
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:21
- 大小:102.75KB
数据结构c++顺序表单链表的基本操作查找排序代码Word文件下载.docx
《数据结构c++顺序表单链表的基本操作查找排序代码Word文件下载.docx》由会员分享,可在线阅读,更多相关《数据结构c++顺序表单链表的基本操作查找排序代码Word文件下载.docx(21页珍藏版)》请在冰点文库上搜索。
4、练习简单选择排序法。
2、完成顺序表上的各种排序算法。
3、源程序给出注释。
实验1代码及结果:
#include<
iostream>
usingnamespacestd;
template<
classT>
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);
};
//建立空顺序表
sq_LList<
T>
:
sq_LList(intm)
{mm=m;
v=newT[mm];
nn=0;
return;
//顺序输出顺序表中的元素与顺序表长度
voidsq_LList<
prt_sq_LList()
{inti;
cout<
<
"
nn="
nn<
endl;
for(i=0;
i<
nn;
i++)cout<
v[i]<
//检测顺序表的状态
intsq_LList<
flag_sq_LList()
{if(nn=mn)return(-1);
if(nn=0)return(0);
return
(1);
//在表的指定元素前插入新元素
template<
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;
//在顺序表中删除指定元素
del_sq_LList(inti)
if(nn==0)
underflow!
for(k=i;
k<
k++)
v[k-1]=v[k];
nn=nn-1;
intmain()
{sq_LList<
double>
s1(100);
第一次输出顺序表对象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);
第二次输出顺序表对象s1:
s1.del_sq_LList(0);
s1.del_sq_LList
(2);
第三次输出顺序表对象s1:
return0;
运行及结果:
实验2代码
#include<
iomanip>
structnode{
floatdata;
node*next;
};
node*create(){//建立单链表
node*head,*p,*s;
head=newnode;
p=head;
p->
data=0;
next=0;
//表头创建完成
floatnewnum=0;
cin>
>
newnum;
if(newnum<
0){
cout<
未输入数据...\n"
;
//输入负数则结束
system("
pause"
);
while(newnum>
=0){//?
?
如何用字符型作为结束标志
s=newnode;
//创建表中数据
s->
data=newnum;
next=s;
p=s;
}
next=NULL;
//最后元素指针
return(head);
//返回空表头
//插入一个结点x,将成为第i个节点
voidinsertnode(node*head,inti,floatx){
node*s,*p;
intj;
data=x;
j=1;
//查找第i个结点,由p指向
while(p!
=NULL&
&
j<
i){
j++;
p=p->
next;
next=p->
//删除结点x
voiddeletenode(node*head,floatx){
node*p,*s;
if(head->
next==NULL)
这是空链表,不能执行删除操作\n"
else{
s=head;
p=head->
data!
=x)
if(p->
=x){
s=p;
}
if(p!
=NULL){
delete(p);
elsecout<
未找到!
\n"
//存取链表某节点K
voidread(node*head,intk){
while(head->
next!
=0&
0){
head=head->
k--;
}
该处数据为"
head->
data<
.\n\n"
intmain(){
node*linktable=0;
intchoice=1;
1.创建链表\n"
2.显示信息\n"
3.删除信息\n"
4.查找信息\n"
5.插入信息\n"
6.读取信息\n"
0.退出程序\n"
请输入您的选择:
choice;
while
(1){
switch(choice){
case0:
exit(0);
case1:
{cout<
输入正数数据,并以负数作为结束标记\n"
linktable=create();
break;
case2:
链表长度为"
length(linktable)<
详细信息:
printlist(linktable);
case3:
{cout<
要删除的数据为?
floatdel;
cin>
del;
deletenode(linktable,del);
case4:
{if(linktable->
next==0)
cout<
链表为空,不能查找\n"
else{
要查找数据为?
floatsearch;
search;
find(linktable,search);
}break;
}
case5:
存储数据为?
intdes;
floatit;
it;
想让该数据存储为第几个节点?
des;
if((des>
(length(linktable)+1)||des<
1))
输入错误\n"
else
insertnode(linktable,des,it);
case6:
想读取第几个节点?
intc;
c;
if(c<
1||c>
length(linktable))
cout<
位置不合法\n"
else
read(linktable,c);
break;
default:
输入错误!
cls"
当前信息:
printlist(linktable);
\n1.创建链表\n"
继续选择:
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;
q;
i++){s0=0;
f=NameList[i].py;
for(r=0;
*(f+r)!
='
\0'
r++)s0+=*(f+r);
NameList[i].k=s0;
}}
voidcreathash(){inti;
n;
i++){
hashlist[i].py="
hashlist[i].k=0;
hashlist[i].si=0;
M;
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;
请输入姓名的拼音:
nam;
for(r=0;
r<
20;
r++)
s0+=nam[r];
intadr=s0%M;
intd=adr;
if(hashlist[adr].k==s0)
姓名:
hashlist[adr].py<
"
关键字:
s0<
查找长度为1"
elseif(hashlist[adr].k==0)cout<
无此记录!
else{intg=0;
while(g==0){
d=(d+s0%10+1)%M;
if(hashlist[d].k==0){cout<
g=1;
if(hashlist[d].k==s0){
查找长度为:
1"
}}}}
voiddisplay(){inti;
30;
NameList[i].py<
NameList[i].k<
intmain(){
charx;
listname();
creathash();
d.显示哈希表f.查找任意键退出请选择"
while(cin>
x){
if(x=='
d'
){display();
elseif(x=='
f'
){findlist();
elsebreak;
实验结果:
实验四排序
一、实验目的和要求:
掌握各种排序方法的排序过程;
了解一些排序算法的实现,如插入排序、选择排序、冒泡排序、快速排序、堆排序等。
二、实验原理:
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]记录学生的名次。
学生信息输出函数:
按照学生的名次列出每个学生的名次、学号、姓名和成绩。
源代码:
stdlib.h>
string.h>
#defineN7//学生人数;
classStudent
{public:
charxingming[20];
intnum;
intscore;
{Studenta[N];
请输入注册学生的人数:
N<
for(inti=0;
N;
i++)
请输入学生的学号、姓名和成绩:
cin>
a[i].num>
a[i].xingming>
a[i].score;
for(intm=0;
m<
m++)
{printf("
%d%s%d"
a[m].num,a[m].xingming,a[m].score);
printf("
按名次列出学生的学号、姓名、成绩和名次:
charch[10];
for(intq=1;
q<
q++)
{for(intp=0;
p<
N-q;
p++)
if(a[p].score<
a[p+1].score)
{strcpy(ch,a[p].xingming);
strcpy(a[p].xingming,a[p+1].xingming);
strcpy(a[p+1].xingming,ch);
intsc=a[p].score;
a[p].score=a[p+1].score;
a[p+1].score=sc;
intl=a[p].num;
a[p].num=a[p+1].num;
a[p+1].num=l;
intb[N];
for(intj=1;
j<
j++)
{b[0]=1;
if(a[j].score==a[j-1].score)
b[j]=j;
elseb[j]=j+1;
%d%s%d%d"
a[i].num,a[i].xingming,a[i].score,b[i]);
system("
PAUSE"
五、运行结果:
六、编程心得:
理解了排序的重要性,也深刻体会到排序在我们周围的广泛应用。
通过片成体会到排序的两项基本操作:
比较关键字的大小和将记录的位置从一个位置转换到另一个位置。
感触尤为深的是C++语言中对象和排序在学生信息系统中的应用,让我感到这些知识的实用性。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 c+ 顺序 表单 基本 操作 查找 排序 代码