2024年4月30日发(作者：)

实验

一、实验目的

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、保存和打印出程序的运行结果，并结合程序进行分析。

五、实验中出现的问题与解决方法

1

实验3：查找

一、实验目的

1、掌握用VC++6.0实现查找算法的方法。

2、掌握常用的查找方法。

3、掌握二叉排序树的构造及其查找方法。

二、实验内容

1、练习顺序查找。

2、练习有序表的对分查找。

3、练习二叉排序树查找。

三、实验前的准备

1、复习相关课程内容。

2、准备相关的程序清单。

四、实验要求

1、建立个人的工作目录。

2、完成顺序表上顺序查找元素的算法。

3、完成有序表上对分法查找元素的算法。

4、完成二叉排序树的构造以及利用二叉排序树进行查找。

5、源程序给出注释。

6、保存和打印出程序的运行结果，并结合程序进行分析。

五、实验中出现的问题与解决方法

2

实验4：排序

一、实验目的

1、掌握用VC++6.0实现排序算法的方法。

2、理解排序的定义和各种排序方法的特点，并能加以灵活应用。

二、实验内容

1、练习冒泡排序法。

2、练习快速排序法。

3、练习简单插入排序法。

4、练习简单选择排序法。

三、实验前的准备

1、复习相关课程内容。

2、准备相关的程序清单。

四、实验要求

1、建立个人的工作目录。

2、完成顺序表上的各种排序算法。

3、源程序给出注释。

4、保存和打印出程序的运行结果，并结合程序进行分析。

五、实验中出现的问题与解决方法

3

实验1代码及结果

：

#include

using namespace std;

template

class sq_LList

{private:

int mm;

int nn;

T *v;

public:

sq_LList(){mm=0;nn=0;return;}

sq_LList(int);

void prt_sq_LList();

int flag_sq_LList();

void ins_sq_LList(int,T);

void del_sq_LList(int);

};

//建立空顺序表

template

sq_LList::sq_LList(int m)

{mm=m;

v=new T[mm];

nn=0;

return;

}

//顺序输出顺序表中的元素与顺序表长度

template

void sq_LList::prt_sq_LList()

{int i;

cout<<"nn="<

for(i=0;i

return;

}

//检测顺序表的状态

template

int sq_LList::flag_sq_LList()

{if(nn=mn)return(-1);

if(nn=0)return(0);

return (1);

}

//在表的指定元素前插入新元素

template

void sq_LList::ins_sq_LList(int i,T b)

4

{int k;

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

void sq_LList::del_sq_LList(int i)

{int k;

if(nn==0)

{cout<<"underflow!"<

return;

}

for(k=i;k

v[k-1]=v[k];

nn=nn-1;

return ;

}

int main()

{sq_LLists1(100);

cout<<"第一次输出顺序表对象s1:"<

_sq_LList();

_sq_LList(0,1.5);

_sq_LList(1,2.5);

_sq_LList(4,3.5);

cout<<"第二次输出顺序表对象s1:"<

_sq_LList();

_sq_LList(0);

_sq_LList(2);

cout<<"第三次输出顺序表对象s1:"<

_sq_LList();

return 0;

}

运行及结果：

5

实验2代码

#include

#include

6

using namespace std;

struct node{

float data;

node *next;

};

node *create(){ //建立单链表

node *head,*p,*s;

head=new node;

p=head;

p->data=0;

p->next=0; //表头创建完成

float newnum=0;

cin>>newnum;

if(newnum<0){

cout<<"未输入数据...n";//输入负数则结束

system("pause");}

while(newnum>=0 ){ //??如何用字符型作为结束标志

s=new node; //创建表中数据

s->data=newnum;

p->next=s;

p=s;

cin>>newnum;}

p->next=NULL; //最后元素指针

return(head); //返回空表头

}

//插入一个结点x，将成为第i个节点

void insertnode(node *head,int i,float x){

node *s,*p;

int j;

s=new node;

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

void deletenode(node *head,float x){

node *p,*s;

7

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);

}

else cout<<"未找到!n";

}

}

//存取链表某节点K

void read(node*head,int k){

while(head->next!=0&&k>0){

head=head->next;

k--;

}

cout<<"该处数据为"<data<<".nn";

}

int main( ) {

node *linktable=0;

int choice=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){

case 0: exit(0);

case 1:

8

{cout<<"输入正数数据，并以负数作为结束标记n";

linktable=create();break;}

case 2:

{cout<<"链表长度为"<

printlist(linktable);break;}

case 3:

{cout<<"要删除的数据为？n";

float del;

cin>>del;

deletenode(linktable,del);break;}

case 4:

{if(linktable->next==0)

cout<<"链表为空，不能查找n";

else{

cout<<"要查找数据为?";

float search;

cin>>search;

find(linktable,search);

} break;}

case 5:

{cout<<"存储数据为？";

int des;

float it;

cin>>it;

cout<<"想让该数据存储为第几个节点？";

cin>>des;

if((des>(length(linktable)+1)||des<1))

cout<<"输入错误n";

else

insertnode(linktable,des,it);break;}

case 6:

{cout<<"想读取第几个节点？";

int c;

cin>>c;

if(c<1||c>length(linktable))

cout<<"位置不合法n";

else

read(linktable,c);

break;

}

default :cout<<"输入错误!n";

}

system("pause");

system("cls");

9

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;

}

return 0;

}

实验三 查找

实验名称： 实验3 查找

实验目的：掌握顺序表和有序表的查找方法及算法实现；掌握二叉排序树和哈希表的构造和

查找方法。通过上机操作,理解如何科学地组织信息存储,并选择高效的查找算法。

实验内容：（2选1）内容1： 基本查找算法；内容2： 哈希表设计。

实验要求：1）在C++系统中编程实现；2）选择合适的数据结构实现查找算法；3）写出算

法设计的基本原理或画出流程图；4）算法实现代码简洁明了；关键语句要有注释；5）给出

调试和测试结果；6）完成实验报告。

实验步骤：

(1)算法设计

a.构造哈希函数的方法很多，常用的有(1)直接定址法(2)数字分析法;(3)平方取中法;(4)折叠

法;( 5)除留余数法;(6)随机数法；本实验采用的是除留余数法:取关键字被某个不大于哈希表

表长m的数p除后所得余数为哈希地址

(2)算法实现

hash hashlist[n];

void listname(){

char *f;

int s0,r,i;

NameList[0].py="baojie";

NameList[1].py="chengaoyang";

………………………………

NameList[29].py="wurenke";

for(i=0;i

10

for(r=0;*(f+r)!='0';r++) s0+=*(f+r);NameList[i].k=s0; }}

void creathash(){int i;

for(i=0;i

hashlist[i].py=""; hashlist[i].k=0; hashlist[i].si=0; }

for(i=0;i

int sum=0;

int adr=(NameList[i].k)%M;

int d=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;}}}

void findlist(){

string nam;int s0=0,r,sum=1; cout<<"请输入姓名的拼音："<>nam;

for(r=0;r<20;r++)

s0+=nam[r];int adr=s0%M;int d=adr;

if(hashlist[adr].k==s0)

cout<<"姓名："<

else if(hashlist[adr].k==0) cout<<"无此记录！"<

else{int g=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"<

void display(){int i;

for(i=0;i<30;i++)cout<

int main(){

char x;

listname();

creathash();

cout<<"d. 显示哈希表 f.查找 任意键退出 请选择"<

while(cin>>x){

if(x=='d'){display();cout<

else if(x=='f'){findlist();cout<

else break; }

return 0;

}

实验结果：

11

实验四排序

一、实验目的和要求：

掌握各种排序方法的排序过程；

了解一些排序算法的实现，如插入排序、选择排序、冒泡排序、快速排序、堆排序等。

二、实验原理：

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.堆排序

12

归并排序：将两个或两个以上的有序表组合成一个新的有序表。

三、实验内容：

学生成绩由学生的学号、姓名和成绩组成，设计一个程序对给定的n个学生信息实现：

按分数的高低排序，打印每个学生在考试中的排名，分数相同的为同一名次，同一名次的同

学按学号从小到大排列。

按照名次列出每个学生的名次、学号、姓名和成绩。

四、程序设计：

程序设计思想：

建立一个学生类：其中包含学生的基本信息：学号、姓名成绩以及名次。

主函数包括：

学生信息输入函数：要求从键盘上输入学生的学号、姓名、以及成绩。

学生成绩排序函数：按照学生成绩排序——冒泡排序，用一个数组b[n]记录学生的名次。

学生信息输出函数：按照学生的名次列出每个学生的名次、学号、姓名和成绩。

源代码：

#include

using namespace std;

#include

#include

#define N 7 //学生人数；

class Student

{ public:

charxingming[20];

intnum;

int score;

};

int main()

{ Student a[N];

cout<<"请输入注册学生的人数："<

for(inti=0;i

{cout<<"请输入学生的学号、姓名和成绩："<

cin>>a[i].num>>a[i].xingming>>a[i].score;}

for(int m=0;m

{printf("%d %s %d",a[m].num,a[m].xingming,a[m].score);

printf("n");}

cout<<"按名次列出学生的学号、姓名、成绩和名次："<

charch[10];

for(int q=1;q

{for(int p=0;p

if(a[p].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;

13

a[p+1].score=sc;

int l=a[p].num;

a[p].num=a[p+1].num;

a[p+1].num=l;

}}

int b[N];

for(int j=1;j

{b[0]=1;

if(a[j].score==a[j-1].score)

b[j]=j;

else b[j]=j+1;

}

for(inti=0;i

printf("%d %s %d %d",a[i].num,a[i].xingming,a[i].score,b[i]);

printf("n");}

system("PAUSE");

}

五、运行结果：

六、编程心得：

14

理解了排序的重要性，也深刻体会到排序在我们周围的广泛应用。通过片成体会到排序的两

项基本操作：比较关键字的大小和将记录的位置从一个位置转换到另一个位置。

感触尤为深的是C++语言中对象和排序在学生信息系统中的应用，让我感到这些知识的实用

性。

15