数据结构实验指导书.docx
- 文档编号:703335
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:25
- 大小:26.67KB
数据结构实验指导书.docx
《数据结构实验指导书.docx》由会员分享,可在线阅读,更多相关《数据结构实验指导书.docx(25页珍藏版)》请在冰点文库上搜索。
数据结构实验指导书
实验一、线性结构的插入和删除
实验目的和要求:
掌握线性结构的定义、组织形式、结构特征和类型说明以及在这两种存储方式下实现的插入、删除和按值查找的算法。
循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。
实验内容:
实验题目
1、已知长度为n的线性表,要求将new_data插入到线性表中使之成为第j个元素。
2、已知长度为n的线性表,要求将线性表中第j个位置上的数据元素删除。
实验准备
1、思考怎样实现线性表顺序存储结构中元素的插入。
2、思考怎样实现线性表顺序存储结构中元素的删除。
实验步骤
1、将new_data插到长度为n的线性表中,使之成为第j个元素。
(1)腾位置
将自第n个位置开始至第j个位置上的所有数据元素统统往后移动一个位置。
(2)插入元素
将new_data插入到线性表中第j个位置。
(3)线性表长度增1
顺序表的类型
structseqlist
{datatypelist[max];
intlength;};
voidinsert(structseqlist*L,inti,intnew_data)
{intj;
if(L->length==max)
exit();
else
{for(j=L->length-1;j>=i;j++)
L->list[j+1]=L->list[j];
L->list[i]=new_data;
L->length++;}
}
2、将长度为n的线性表中第j个位置上的数据元素删除
(1)移动删除
将自第j+1个位置开始至线性表中最后一个位置的数据元素全部前移一个位置。
(2)线性表长度减1
顺序表的类型
structseqlist
{datatypelist[max];
intlength;};
voiddelete(structseqlist*L,inti,intnew_data)
{intj;
if(L->length==-1)
exit();
else
{for(j=i+1;j
L->list[j-1]=L->list[j];
L->length--;}
}
实验二、树型结构的遍历
实验目的和要求:
树的遍历是树的算法中最具有典型的,它的特点为递归,树的其它算法如:
求树的高度、求叶子数等,都同该算法同出一辙,另外树的遍历算法应用比较广泛。
实验内容:
实验题目
编写前序遍历、中序遍历、后序遍历二叉树的程序。
实验准备
1、掌握二叉树的特点及其存储方式。
2、掌握二叉树的创建和显示方法。
3、掌握二叉树遍历的基本方法:
前序(DLR)、中序(LDR)、后序(LRD)
实验步骤
按下图的二叉树进行操作。
1、按上图建立二叉树,输入方法为:
请输入按先序建立二叉树的结点序列:
说明:
‘0’代表后继结点为空,请逐个输入,按回车键输入下一个结点。
请输入根结点:
a
请输入a结点的左子结点:
b
请输入b结点的左子结点:
d
请输入d结点的左子结点:
0
请输入d结点的右子结点:
0
请输入b结点的右子结点:
0
请输入a结点的右子结点:
c
请输入c结点的左子结点:
e
请输入e结点的左子结点:
0
请输入e结点的右子结点:
0
请输入c结点的右子结点:
f
请输入f结点的左子结点:
0
请输入f结点的右子结点:
0
2、检查前序、中序、后序算法的正确。
例:
该二叉树前序遍历序列为:
abdcef
该二叉树中序遍历序列为:
dbaecf
该二叉树后序遍历序列为:
dbefca
3、遍历算法(递归过程)
(1)前序遍历
若二叉树为空,遍历结束。
否则
A、访问根结点。
B、前序遍历根结点的左子树。
C、前序遍历根结点的右子树。
voidpreorder(BT*T)
{if(T!
=NULL)
{printf(“%c”,T->data);
preorder(T->lchild);
preorder(T->rchild);
}
(2)中序遍历
若二叉树为空,遍历结束。
否则
A、中序遍历根结点的左子树。
B、访问根结点。
C、中序遍历根结点的右子树。
voidpreorder(BT*T)
{if(T!
=NULL)
{preorder(T->lchild);
printf(“%c”,T->data);
preorder(T->rchild);
}
(3)后序遍历
若二叉树为空,遍历结束。
否则
A、后序遍历根结点的左子树。
B、后序遍历根结点的右子树。
C、访问根结点
voidpreorder(BT*T)
{if(T!
=NULL)
{preorder(T->lchild);
preorder(T->rchild);
printf(“%c”,T->data);
}
实验三、图型结构算法及应用
实验目的和要求:
图有二个存储结构:
邻接矩阵和邻接表,邻接矩阵的实验可以借鉴于实验一,邻接表的实验类似于单链表,图是最复杂的一种数据结构,掌握它有一定的代表意义。
实验内容:
实验题目
邻接表表示图,并进行深度优先遍历
实验准备
了解什么是邻接表,什么是深度优先遍历
实验步骤
1、定义数据类型
#define MAX_VERTEX_NUM 20 //最大顶点数
#define MAX_EDGE_NUM 40 //最大边数
int visited[ MAX_VERTEX_NUM];
typedef int VertexType ; //顶点数据类型
typedef struct ArcNode
{
int adjvex;
int weight;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
2、创建一个图
void CreateDG(ALGraph &G)
{
int i,j,k;
ArcNode *p;
cout<<"创建一个图:
"< cout<<"顶点数: "; cin>>G.vexnum;cout< cout<<"边数: "; cin>>G.arcnum; cout< for(i=0;i { G.vertices[i].data=i; G.vertices[i].firstarc=NULL; } for(k=0;k { cout<<"请输入第"< "; cin>>i>>j; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; } } 3、输出图 void Disp(ALGraph G) { int i,j; ArcNode *p; cout<<"输出图为: "< for(i=0;i { p=G.vertices[i].firstarc; j=0; while(p! =NULL) { cout<<"("<adjvex<<")"; p=p->nextarc; j=1; } if(j==1) cout< } } 4、图的深度优先遍历 void dfs(ALGraph G,int v) //深度优先遍历 { ArcNode *p; cout< visited[v]=1; p=G.vertices[v].firstarc; while(p! =NULL) {if(! visited[p->adjvex]) dfs(G,p->adjvex); p=p->nextarc; } return ; } void dfs1(ALGraph G) { int i; for(i=0;i if(visited[i]==0) dfs(G,i); } 5、主函数 void main() { ALGraph G; CreateDG(G); int v; Disp(G); cout<<"输入顶点: "; cin>>v; cout<<"深度优先序列: "; dfs1(G); cout< } 实验四、查找算法应用 实验目的和要求: 查找是日常经常使用的一种操作,掌握各种数据结构的查找算法有十分重要的意义。 通过本次实验掌握顺序查找、树表查找、散列表查找的基本思想及存储、运算的实现。 实验内容: 实验题目 设有关键字序列k={5,14,18,21,23,29,31,35}查找key=21的数据元素 实验准备 1、从键盘输入上述8个整数,存放在数组bub[8]中,并输出其值。 2、从键盘输入21,查找是否存在该数据元素,若存在,则输出该数据元素在表中位置,否则给出查找失败的信息。 2、从键盘输入25,查找是否存在该数据元素,若存在,则输出该数据元素在表中位置,否则给出查找失败的信息。 3、具体算法 intbinarysearch(structsstablest[n+1],elemtypek) {intlow=1,high=1; while(low<=high) mid=(low+high)/2; if(k==st[mid].key) return(mid); elseif(k high=mid-1; else low=mid-1; } return(0); } 实验步骤 1、low=1;high=length;//设初始区间 2、当low>high时,返回查找失败信息;//表空,查找失败 3、low<=high,mid=(low+high)/2//取中点 (1)若key (2)若key>bub[mid],low=mid+1;转2 (3)若key=bub[mid],返回数据元素在表中位置。 实验五、排序算法应用 实验目的和要求: 掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序及基数排序的基本思想及实现。 实验内容: 实验题目 将一组数据(97、49、65、76、49、13、38、27)进行大堆排序 实验准备 1、只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间 2、掌握堆的概念 什么是堆? n个元素的序列{k1,k2,...,kn}当且仅当满足下列关系时,称之为堆。 关系一: ki<=k2i关系二: ki<=k2i1(i=1,2,...,n/2) 3、堆排序要解决两个问题: a、如何由一个无序序列建成一个堆? b、如何在输出堆顶元素之后,调整剩余元素成为一个新的堆? 实验步骤 sift(ListType&r,intk,intm) { i=k;j=2*i;x=r[k].key;finished=FALSE; t=r[k]; while((j<=m)&&(! finished)) { if((j if(x<=r[j].key) finished: =TRUE; else{r[i]=r[j];i=j;j=2*i;} } r[i]=t; } HeapSort(ListType&r) { for(i=n/2;i>0;i--)sift(r,i,n); for(i=n;i>1;i--){ r[1]<->r[i]; sift(r,i,i-1) } } 实验六、设计学生成绩管理系统 实验目的和要求: 这是一个综合性、设计性实验,是为了让大家将前面所学的知识点进行概括和总结,并能够解决实际的应用问题。 实验内容: 实验题目 利用前面所学到的知识设计出学生成绩管理系统合适的数据结构,并编程实现增加记录、删除记录、查找和排序功能。 实验准备 先复习链表结构、c语言的各种数据类型及操作语言的用法。 熟练查找和排序的多种算法。 实验步骤 1、定义学生成绩的数据结构 structnode {intnumber;/*学号*/ charname[10];/*姓名*/ floatyuwen;/*语文成绩*/ floatyingyu;/*英语成绩*/ floatshuxue;/*数学成绩*/ structnode*next; }; 2、创建链表 3、增加学生资料,并且将所有学生资料按学号排序 4、查询学生成绩 struct*search2311(struct*head) /*函数search2311,功能: 查询学生成绩*/ {intnumber; struct*p1,*p2; printf("输入要查询的学生的学号,"); scanf("%d",&number); while(number! =0) { if(head==NULL) {printf("\n没有任何学生资料! \n");return(head);} printf("-----------------------------------------\n"); printf("|学号\t|姓名\t|语文\t|英语\t|数学\t|\n"); printf("-----------------------------------------\n");/*打印表格域*/ p1=head; while(number! =p1->number&&p1->next! =NULL) {p2=p1;p1=p1->next;} if(number==p1->number) {printf("|%d\t|%s\t|%.1f\t|%.1f\t|%.1f\t|\n",p1->number,p1->name,p1->yuwen,p1->yingyu,p1->shuxue); printf("-----------------------------------------\n");}/*打印表格域*/ else printf("%d不存在此学生! \n",number); printf("输入要查询的学生的学号,"); scanf("%d",&number); } printf("已经退出了! \n"); return(head);} 5、删除学生资料 struct*del2311(struct*head)/*函数del2311,功能: 删除学生资料*/ { struct*p1,*p2; intnumber; printf("输入要删除的学生的学号(输入0时退出): "); scanf("%d",&number); getchar(); while(number! =0)/*输入学号为0时退出*/ { if(head==NULL) { printf("\n没有任何学生资料! \n"); return(head); } p1=head; while(number! =p1->number&&p1->next! =NULL) /*p1指向的不是所要找的首结点,并且后面还有结点*/ { p2=p1;p1=p1->next; }/*p1后移一个结点*/ if(number==p1->number) /*找到了*/ { if(p1==head) head=p1->next; /*若p1指向的是首结点,把地二个结点地址赋予head*/ else p2->next=p1->next; /*否则将下一个结点地址赋给前一结点地址*/ printf("删除: %d\n",number);n=n-1; } else printf("%d不存在此学生! \n",number); /*找不到该结点*/ printf("输入要删除的学生的学号: "); scanf("%d",&number); getchar(); } #ifdefDEBUG printf("已经退出了! \n"); #endif printf("现在的学生数为: %d个! \n",n); return(head); } 6、定义排序函数 struct*taxis2311(struct*head) /*定义排序函数。 此函数带回一个指向链表头的指针*/ {struct*p,*max; inti,j,x; floatfen; chart[10]; if(head==NULL) {printf("\n没有任何学生资料,请先建立链表! \n");return(head);}/*链表为空*/ max=p=head; for(i=0;i<80;i) printf("*"); printf("1按学生学号排序\t2按学生姓名排序\t3按语文成绩排序\n"); printf("4按英语成绩排序\t5按数学成绩排序\t\n"); for(i=0;i<80;i) printf("*"); printf("请选择操作: "); scanf("%d",&x);/*选择操作*/ getchar(); switch(x)/*用switch语句实现功能选择*/ {case1: for(i=1;i { for(j=i1;j<=n;j) { max=p; p=p->next; if(max->number>p->number) { k=max->number; max->number=p->number; p->number=k; /*交换前后结点中的学号值,使得学号大者移到后面的结点中*/ scpy(t,max->name); scpy(max->name,p->name); scpy(p->name,t); /*交换前后结点中的姓名,使之与学号相匹配*/ fen=max->yuwen; max->yuwen=p->yuwen; p->yuwen=fen; /*交换前后结点中的语文成绩,使之与学号相匹配*/ fen=max->yingyu; max->yingyu=p->yingyu; p->yingyu=fen; /*交换前后结点中的英语成绩,使之与学号相匹配*/ fen=max->shuxue; max->shuxue=p->shuxue; p->shuxue=fen; /*交换前后结点中的数学成绩,使之与学号相匹配*/ } } max=head;p=head;/*重新使max,p指向链表头*/ } print2311(head);break;/*打印值排序后的链表内容*/ case2: for(i=1;i { for(j=i1;j<=n;j) { max=p; p=p->next; if(scmp(max->name,p->name)>0)/*scmp=>字符串比较函数*/ { scpy(t,max->name);/*scpy=>字符串复制函数*/ scpy(max->name,p->name); scpy(p->name,t); /*交换前后结点中的姓名,使得姓名字符串的值大者移到后面的结点中*/ k=max->number; max->number=p->number; p->number=k; /*交换前后结点中的学号值,使之与姓名相匹配*/fen=max->yuwen; max->yuwen=p->yuwen; p->yuwen=fen; /*交换前后结点中的语文成绩,使之与姓名相匹配*/ fen=max->yingyu; max->yingyu=p->yingyu; p->yingyu=fen; /*交换前后结点中的英语成绩,使之与姓名相匹配*/ fen=max->shuxue; max->shuxue=p->shuxue; p->shuxue=fen; /*交换前后结点中的数学成绩,使之与姓名相匹配*/ } } p=head; max=head; } print2311(head); break; case3: for(i=1;i {for(j=i1;j<=n;j) {max=p; p=p->next; if(max->yuwen>p->yuwen) { fen=max->yuwen; max->yuwen=p->yuwen; p->yuwen=fen; /*交换前后结点中的语文成绩,使得语文成绩高者移到后面的结点中*/ k=max->number; max->number=p->number; p->number=k; /*交换前后结点中的学号,使之与语文成绩相匹配*/ scpy(t,max->name); scpy(max->name,p->name); scpy
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 指导书