实验一约瑟夫问题
实验学时:3学时
实验类型:设计
实验要求:必修
一、实验目的
熟练掌握线性链表的基础知识;
能够使用C++或其他程序设计语言编程实现线性链表;
能够使用线性链表构造正确而且时间复杂度低的算法解决实际问题;
锻炼程序设计能力。
二、实验内容
M个教徒和N个非教徒在深海上遇险,必须将N个人投入海中,其余的人才能幸免于难,于是想了一个办法:所有人围成一圆圈,从第一个人开始依次报数,每数到第K个人就将他扔入大海,如此循环进行直到仅余M个人为止。设计一个算法,找出这样一个排序:使每次被扔进大海的都是非教徒。并用程序设计语言实现。
三、实验原理、方法和手段
使用循环单链表,将每个人作为一个结点,每个结点的指针域指向下一个人,采用循环链表的遍历对每隔N-1个结点的结点进行标记,直至标记出N个结点为止。该实验亦可用顺序表实现。
四、实验组织运行要求
本实验采用集中授课形式,每个同学独立完成上述实验要求。
五、实验条件
每人一台计算机独立完成实验,有如下条件:
(1)硬件:联想高性能PC机;
(2)软件:VC++ 6.0、VC++.Net。
六、实验步骤
(1)编写循环链表构造函数Node *Create( ),使链表中每个结点的数据域值为0,并让最后一个结点的指针域指向第一个结点;
(2)编写约瑟夫问题函数
Node *Move(Node *H,int n);
void Insert(Node *H,int pos,int data);
(5)主函数中调用Create,Move和Insert,采用具体数据计算,输出结果。
七、实验程序
// stdafx.h : 标准系统包含文件的包含文件,
// 或是经常使用但不常更改的
// 特定于项目的包含文件
//
#pragma once
#include"targetver.h"
#include
#include
#include
using namespace std;
struct Node
{
int judgement;
int number;
Node *Next;
};
Node *Create();
Node *Move(Node *H,int n);
void Insert(Node *H,int pos,int data);
// px.cpp : 定义控制台应用程序的入口点。//
#include"stdafx.h"
int _tmain(int argc, _TCHAR* argv[]) {
int n1,n2,k,c,j=1;
cout<<"请输入n1,n2和k"< cin>>n1>>n2>>k; c=n1+n2; Node *H=Create(); for(int i=2;i<=c;i++) { Insert(H,i,i); } Node *p=H; Node *q; for (int i=0;i { q=Move(p,k); q->judgement=1; p=q->Next; } p=H; cout<<"排列标记为"< do { cout< p=p->Next; j++; }while(j<=c); system("PAUSE"); return 0; } Node *Create() { Node *H; H=new Node[1]; H->judgement=0; H->number=1; H->Next=H; return H; } void Insert(Node *H,int pos,int data) { Node *p=Move(H,pos-1); Node *q=new Node[1]; p->Next=q; q->Next=H; q->number=data; q->judgement=0; } Node *Move(Node *H,int n) { Node *p=H; for(int i=1;i { p=p->Next; if (p->judgement==1) { continue; } i++; } return p; } // TODO: 在此处引用程序需要的其他头文件 八、实验结果 实验二串的模式匹配 实验学时:2学时 实验类型:设计 实验要求:必修 一、实验目的 通过实验,实现串的模式匹配的程序的设计。 二、实验内容 对于输入的串T和S,如果S是T的子串,求出S在T中的位置。 三、实验原理、方法和手段 KMP算法的改进:每当一趟匹配过程中出现字符比较不等时,不需指针回溯,而是利用得到的部分匹配的结果,将模式向右滑动尽可能远的一段距离后,继续进行比较。如主串‘s1s2…sn’,模式串‘p1p2…pm’。当匹配过程中产生失配(即,si1pj)时,将模式串向右移动至模式中的第k个字符和主串中的第i个字符对齐。令next[j]=k。 四、实验组织运行要求 本实验采用集中授课形式,每个同学独立完成上述实验要求。 五、实验条件 每人一台计算机独立完成实验,如下条件: (1)硬件:微机; (2)软件:VC++6.0、VC++.Net。 六、实验步骤 (1)编写GetNext函数,函数头建议为int *GetNext(HString T); (2)调用Next函数,实现KMP函数函数头为int KMP(HString T,HString S);(3)采用具体实例串,检验所写KMP函数是否正确。 七、实验程序 // stdafx.h : 标准系统包含文件的包含文件, // 或是经常使用但不常更改的 // 特定于项目的包含文件 // #pragma once #include"targetver.h" #include #include #include using namespace std; void Judge(char s1[50],char s2[50]); // TODO: 在此处引用程序需要的其他头文件 // Ex10.cpp : 定义控制台应用程序的入口点。 // #include"stdafx.h" int _tmain(int argc, _TCHAR* argv[]) { char s1[50]; char s2[50]; cout<<"请输入第一个字符串:" < cin.getline(s1,50); cout<<"请输入第二个字符串:"< cin.getline(s2,50); cout<<"第一个字符串为:"< cout<<"第二个字符串为:"< Judge(s1,s2); system("PAUSE"); return 0; } void Judge(char s1[50],char s2[50]) { int flag=0; for(int i=0;s1[i]!=NULL;i++) { int j; for (j=0;j<50&&s2[j]!=NULL;j++) { if (s1[i+j]==s2[j]) continue; else break; } if (s2[j]==NULL) { cout<<"第二个字符串从第"< flag=1; }else continue; } if (flag==0) { cout<<"第二个字符串在第一个字符串中找不到匹配。"< } } 八、实验结果 实验三稀疏矩阵三元组表的转置 实验学时:2学时 实验类型:综合 实验要求:必修 一、实验目的 通过实验,实现串的模式匹配的程序的设计。 二、实验内容 将以数组形式存储的稀疏矩阵转换为三元组表,并将其转置,输出转置后的结果。 三、实验原理、方法和手段 创建一个class QOLList用来构架矩阵结构OLNode,在QOLList中写入void Insert(int y, int x, int Data)方法。通过使用遍历和Insert方法进行转置功能的实现。 四、实验组织运行要求 本实验采用集中授课形式,每个同学独立完成上述实验要求。 五、实验条件 每人一台计算机独立完成实验,如下条件: (1)硬件:微机; (2)软件:VC++6.0、VC++.Net。 六、实验步骤 (1)编写二维数组到三元组表的转换函数。 (2)编写三元组转置函数; (3)在主函数中调用转换函数和转置函数,输出结果。 七、实验程序 // stdafx.h : 标准系统包含文件的包含文件, // 或是经常使用但不常更改的 // 特定于项目的包含文件 // #pragma once #include"targetver.h" #include #include #include #include"QOLList.h" using namespace std; // TODO: 在此处引用程序需要的其他头文件 #pragma once struct OLNode { int x,y; int Data; OLNode *pRight,*pDown; }; class QOLList { public: QOLList(void); QOLList(int H,int W); ~QOLList(void); int m_H,m_W; OLNode *pXHead,*pYHead; OLNode* GetXTail(int x); OLNode* GetYTail(int y); void Insert(int y, int x, int Data); void Cout(void); void DeleteRow(int y); void RemoveNodeX(int x, int y); void InsertRow(OLNode *p,int y); void InsertNodeX(OLNode * p, int x); }; #include"StdAfx.h" #include"QOLList.h" QOLList::QOLList(void) { } QOLList::QOLList(int H,int W) { m_H=H; m_W=W; pXHead=new OLNode[W]; pYHead=new OLNode[H]; for(int x=0;x { pXHead[x].pDown=NULL; pXHead[x].x=x; } for(int y=0;y { pYHead[y].pRight=NULL; pYHead[y].y=y; } } QOLList::~QOLList(void) { } OLNode* QOLList::GetXTail(int x) { OLNode *pX=&pXHead[x]; while(pX->pDown!=NULL) pX=pX->pDown; return pX; } OLNode* QOLList::GetYTail(int y) { OLNode *pY=&pYHead[y]; while(pY->pRight!=NULL) pY=pY->pRight; return pY; } void QOLList::Insert(int y, int x, int Data) { OLNode *p=new OLNode; p->Data=Data; p->pDown=NULL; p->pRight=NULL; p->x=x; p->y=y; OLNode *pX=GetXTail(x); OLNode *pY=GetYTail(y); pX->pDown=p; pY->pRight=p; } void QOLList::Cout(void) { for(int y=0;y { OLNode *pX=&pYHead[y]; while(pX->pRight!=NULL) { cout< pX=pX->pRight; } cout< } } void QOLList::DeleteRow(int y) { OLNode *p=pYHead[y].pRight; for(int x=0;x RemoveNodeX(x,y); for(int my=y;my pYHead[my].pRight=pYHead[my+1].pRight; pYHead[m_H-1].pRight=NULL; for(int my=y;my { OLNode *pX=&pYHead[y]; while(pX->pRight!=NULL) { pX=pX->pRight; pX->y--; } } } void QOLList::RemoveNodeX(int x, int y) { OLNode *p=&pXHead[x]; while(p->pDown!=NULL) { if(p->pDown->y!=y) p=p->pDown; else { p->pDown=p->pDown->pDown; break; } } } void QOLList::InsertRow(OLNode *p,int y) { for(int x=0;x RemoveNodeX(x,y); for(int my=y;my pYHead[my].pRight=pYHead[my+1].pRight; pYHead[m_H-1].pRight=NULL; for(int my=y;my { OLNode *pX=&pYHead[y]; while(pX->pRight!=NULL) { pX=pX->pRight; pX->y--; } } } void QOLList::InsertNodeX(OLNode * p, int x) { OLNode *q=&pXHead[x]; while(q->pDown!=NULL) { if(p->pDown->y q=q->pDown; else { p->pDown=q->pDown; q->pDown=p; break; } } } // Ex9.cpp : 定义控制台应用程序的入口点。 // #include"stdafx.h" int _tmain(int argc, _TCHAR* argv[]) { int w,h; QOLList mO(4,5); int a[][5]={ 0,0,2,4,5, 0,1,9,0,6, 2,0,1,3,7, 2,4,1,4,7 }; w=4;h=5; for(int y=0;y<4;y++) for(int x=0;x<5;x++) if(a[y][x]!=0) mO.Insert(y,x,a[y][x]); cout<<"原矩阵为:"< mO.Cout(); cout< QOLList m1(h,h); for(int y=0;y { OLNode *pX=&mO.pYHead[y]; while(pX->pRight!=NULL) { pX=pX->pRight; m1.Insert(pX->x,pX->y,pX->Data); } } cout<<"转置矩阵为:"< m1.Cout(); system("PAUSE"); return 0; } 八、实验结果 实验四求带权图的最小生成树和最短路径 实验学时:3学时 实验类型:综合 实验要求:必修 一、实验目的 熟练理解求最小生成的Prim算法; 锻炼程序设计能力。 二、实验内容 编程实现求无向带权图的最小生成树。 三、实验原理、方法和手段 设图G =(V,E),其生成树的顶点集合为U。 ①、把v0放入U。 ②、在所有u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边,加入生成树。 ③、把②找到的边的v加入U集合。如果U集合已有n个元素,则结束,否则继续执行②。 四、实验组织运行要求 本实验采用集中授课形式,每个同学独立完成上述实验要求。 五、实验条件 每人一台计算机独立完成实验,如下条件: (1)硬件:微机; (2)软件:VC++6.0、VC++.Net。 六、实验步骤 (1)编写生成一个邻接矩阵表示的无向带权图的函数。 (2)编写Prim函数; (3)在主函数中调用上述函数,并将结果中所有的边输出。输出边的格式为:i,j,w。其中i和j为该边关联的点的下标,w为该边权值。 七、实验程序 // stdafx.h : 标准系统包含文件的包含文件, // 或是经常使用但不常更改的 // 特定于项目的包含文件 // #pragma once #include"targetver.h" #include #include #include #include #include using namespace std; const int MaxSize = 10; const int Max = 999; class MGraph { public: MGraph(string a , int n , int e); ~MGraph(){} void DFSTraverse(int v); void BFSTraverse(int v); friend void Prim(MGraph G); friend void Dijkstra(MGraph G,int v); friend void Floyd(MGraph G); private: string vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum , arcNum; }; int MinEdge(int lowcost[] ,int n); void Prim(MGraph G); void Dijkstra(MGraph G,int v); void Floyd(MGraph G); // TODO: 在此处引用程序需要的其他头文件 // Path.cpp : 定义控制台应用程序的入口点。 // #include"stdafx.h" int _tmain(int argc, _TCHAR* argv[]) { string a = "ABCDEF"; MGraph graph(a , 6 ,9); graph.DFSTraverse(0); cout< graph.BFSTraverse(0); cout< Prim(graph); Dijkstra(graph,0); Floyd(graph); system("PAUSE"); } MGraph::MGraph(string a, int n, int e) { vertexNum = n; arcNum = e; for(int i = 0;i < vertexNum;i++) vertex[i] = a[i]; for(int i =0 ;i for(int j =0;j { if(i==j) arc[i][j] = 0; else arc[i][j] = Max; } for(int i = 0; i < arcNum ;i++) { int a ,b ; int c; cin>>a>>b>>c; arc[a][b] = arc[b][a] = c; } } int visited[20]; void MGraph::DFSTraverse(int v) { cout< visited[v] = 1; for(int j =0;j if(arc[v][j]!=Max&&visited[j]!=1) DFSTraverse(j); } int visited2[20]; void MGraph::BFSTraverse(int v) { int queue[100]; int front ,rear; front = rear =-1; cout< visited2[v] = 1; queue[++rear] =v; while(front != rear) { v = queue[++front]; for(int i = 0;i if(arc[v][i]!=Max&&visited2[i]!=1) { cout< visited2[i]=1; queue[++rear] =i; } } } int lowcost[100]; int MinEdge(int lowcost[] ,int n) { int k=0; for(int i = 1;i { while(lowcost[k]==0) k++; if(lowcost[i]!=0&&lowcost[i] k = i; } return k; } void Prim(MGraph G) { int adjvex[100]; for(int i=1;i { lowcost[i]=G.arc[0][i]; adjvex[i]=0; } lowcost[0]=0; for(int i=1;i { int k=MinEdge(lowcost,G.vertexNum); cout<<"("< lowcost[k]=0; for(int j=1;j if(G.arc[k][j] { lowcost[j]=G.arc[k][j]; adjvex[j]=k; } } } ////Dijkstra 算法 string Path[100]; int Dist[100]; string s[100]; void Dijkstra(MGraph G,int v) { for(int i=0;i { Dist[i]=G.arc[v][i]; if(Dist[i]!=Max) Path[i]=G.vertex[v]+G.vertex[i]; else Path[i]=""; } s[0]=G.vertex[v]; Dist[v]=0; int num=1; while(num { int k=0; while(Dist[k]==0) k++; for(int i=0;i if(Dist[i]!=0&&Dist[i] k=i; cout< "< s[++num]=G.vertex[k]; for(int i=0;i { if(Dist[i]>Dist[k]+G.arc[k][i]) { Dist[i]=Dist[k]+G.arc[k][i]; Path[i]=Path[k]+G.vertex[i]; } } Dist[k]=0; } } int dist[100][100]; string path[100][100]; void Floyd(MGraph G) { for(int i=0;i for(int j=0;j { dist[i][j] =G.arc[i][j]; if(dist[i][j]!=Max) path[i][j] =G.vertex[i] +G.vertex[j]; else path[i][j] = ""; } for(int k =0;k for(int i=0;i for(int j=0;j if(dist[i][k]+dist[k][j] { dist[i][j] =dist[i][k]+dist[k][j]; string s =path[k][j]; char *p = &s[1]; path[i][j] =path[i][k]+p; } cout<<"*********dist*********"< for(int i=0;i { for(int j=0;j cout< cout< } cout<<"********path***********"< for(int i=0;i { for(int j=0;j cout< cout< } } 八、实验结果 实验五排序算法的比较 实验学时:2学时 实验类型:设计 实验要求:必修 一、实验目的 熟练掌握各种排序算法; 能够使用C++或其他程序设计语言编程实现各种排序算法; 锻炼程序设计能力。 二、实验内容 冒泡排序、选择排序、插入排序、shell排序、归并排序、快速排序三、实验原理、方法和手段 上述排序算法至少编程实现两个。 四、实验组织运行要求 本实验采用集中授课形式,每个同学独立完成上述实验要求。 五、实验条件 每人一台计算机独立完成实验,有如下条件:(1)硬件:联想高性能PC机; (2)软件:VC++ 6.0、VC++.Net。 六、实验步骤 略。 七、实验程序 // stdafx.h : 标准系统包含文件的包含文件, // 或是经常使用但不常更改的 // 特定于项目的包含文件 // #pragma once #include"targetver.h" #include #include #include using namespace std; void BubbleSort(int a[],int n); void SelectionSort(int a[],int n); void InsertSort(int a[],int n); void ShellSort(int a[],int n); void QuickSort(int a[],int low,int high); void Merge(int array[],int start,int mid,int end); void MergeSort(int array[], int start, int end); void DisplayArr(int a[],int n); // TODO: 在此处引用程序需要的其他头文件 // Sort.cpp : 定义控制台应用程序的入口点。 // #include"stdafx.h" int _tmain(int argc, _TCHAR* argv[]) { Int a[]={11,8,4,9,0,48,2,32,19}; int b[]={11,8,4,9,0,48,2,32,19}; int c[]={11,8,4,9,0,48,2,32,19}; int d[]={11,8,4,9,0,48,2,32,19}; int e[]={11,8,4,9,0,48,2,32,19}; int f[]={11,8,4,9,0,48,2,32,19}; cout<<"原数组为:"< DisplayArr(a,9); BubbleSort(a,9); cout<<"冒泡排序后结果为:"< DisplayArr(a,9); cout<<"原数组为:"< DisplayArr(b,9); SelectionSort(b,9); cout<<"选择排序后结果为:"< DisplayArr(b,9); cout<<"原数组为:"< DisplayArr(c,9); InsertSort(c,9); cout<<"插入排序后结果为:"< DisplayArr(c,9); cout<<"原数组为:"< DisplayArr(d,9); ShellSort(d,9); cout<<"shell排序后结果为:"< DisplayArr(d,9); cout<<"原数组为:"< DisplayArr(e,9); QuickSort(e,0,8); cout<<"快速排序后结果为:"< DisplayArr(e,9); cout<<"原数组为:"< DisplayArr(f,9); MegerSort(f,0,8); cout<<"归并排序后结果为:"< DisplayArr(f,9); system("pause"); return 0; } void BubbleSort(int a[],int n) { for(int i=0;i for(int j=0;j { if(a[j]>a[j+1]) { int temp; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } void SelectionSort(int a[],int n) { for(int k=0;k for(int i=0;i { int min_index=i; for(int j=i+1;j { if(a[j] { int temp; temp=a[min_index]; a[min_index]=a[j]; a[j]=temp; } } } } void InsertSort(int a[],int n) {