算法--代码实验

一、实验内容和要求八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

例如：图1 八数码问题示意图请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A 算法或A* 算法）编程求解八数码问题（初始状态任选）。

选择一个初始状态，画出搜索树，填写相应的OPEN 表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。

二、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。

三、实验算法A*算法是一种常用的启发式搜索算法。

在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。

A*算法的估价函数可表示为：f'(n) = g'(n) + h'(n)这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。

由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数：f(n) = g(n) + h(n)其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。

在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。

用f(n)作为f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。

这样必须满足两个条件：（1）g(n)>=g'(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。

（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。

k-近邻算法一、 实验题目1. kNN 代码实现-AB 分类采用测量不同特征值之间的距离方法进行分类，用所给的函数创建具有两个特征与一个标签类型的数据作 为训练集，编写 classify0 函数对所给的数据进行 AB 分类。

2. k-近邻算法改进约会网站的配对效果k-近邻算法改进约会网站的配对效果通过收集的一些约会网站的数据信息，对匹配对象的归类：不喜欢的人、魅力一般的人、极具魅力的人。

数据中包含了 3 种特征：每年获得的飞行常客里程数、玩视频游戏所耗时间百分比、每周消费的冰淇淋公升数二、 实验代码1. kNN 代码实现-AB 分类kNN from http.client import ImproperConnectionStatefrom numpy import ∗ from collections importCounter import operator def createDataSet():group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])labels = [’A ’, ’A ’, ’B’, ’B’] return group, labelsdef classify0(inX, group, labels, k = 3):res1 = (inX − group)∗∗2 dist =res1[:,0] + res1[:,1] dic = argsort(dist) dic = dic[0:k:1] newdic = [] for i in range (k): newdic.append(labels[dic[i]]) c = Counter(newdic).most_common(1) return c[0][0] tests import kNN group, lables = kNN.createDataSet() print (’分类结果’) print (’[0,0] %c’ %(kNN.classify0([0, 0], group, lables, k = 3))) print (’[0.8,0.7] %c’ %(kNN.classify0([0.8, 0.7], group, lables, k = 3)))2.k-近邻算法改进约会网站的配对效果1 2 3 4 5 67 8 910111213141516171819 1 2 3 4 5import pandas as pdimport kNNfrom sklearn.model_selection import train_test_splitdf = pd.read_table(’datingTestSet2.txt’,sep=’\s+’, names = [’A ’, ’B’, ’C’, ’Y’])# 对特征进行归一化处理df2 = df.iloc[:, :3] df2 =(df2−df2.mean())/df2.std() lable=df.iloc[:,3:4] df2.loc[:, ’Y’] =lable# 对数据集进行测试集和训练集划分，90%作为训练集，10%作为测试集X_train, X_test, Y_train, Y_test = train_test_split(df2.iloc[:, :3], df2.Y, train_size=.90)# 将DataFrame 格式转化为numpy 格式处理 group = X_train.values label =Y_train.values length =len (X_test) X_test.iloc[0:1,:]# res 以储存测试结果res = []# 设置错误正确数count 以计算正确率Tnum = 0 Fnum = 0 for iin range (length):inX = X_test.iloc[i:i+1 , :].values res.append(kNN.classify0(inX,group, label, k = 3)) if (kNN.classify0(inX, group, label, k = 3) ==Y_test.values[i]):Tnum += 1 else :Fnum += 1res1 = pd.DataFrame(data = res, columns=[’TestResult’])Y_test.reset_index(inplace=True,drop=True)res1.loc[:, ’OriginTest’] = Y_testprint (’前20个数据测试结果和原数据比较’) print (’−−−−−−−−−−−−−−−−−−−−−——−−−−’) print (res1.head(20))print (’−−−−−−−−−−−−−−−−−−−−−——−−−−’) print (’正确率%.2f%%’ %(100∗Tnum/(Tnum+Fnum))) 三、 实验结果及分析1. kNN 代码实现-AB 分类分类结果[0, 0] B[0.8, 0.7] A2. k-近邻算法改进约会网站的配对效果1 2 3 45 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2526 27 28 29 3031 32 33 3435363738 1 2 3前20个数据测试结果和原数据比较−−−−−−−−−−−−−−−−−−−−−——−−−TestResult OriginTest0 2 2 1 3 3 2 1 3 3 2 2 4 2 2 5 3 3 6 3 3 7 2 2 8 1 1 9 1 1 10 1 1 11 3 3 12 2 2 13 2 2 14 1 1 15 2 2 16 1 1 17 2 2 18 1 1 19 3 3−−−−−−−−−−−−−−−−−−−−−——−−− 正确率97.00%从实验结果可以看出，通过 k-近邻算法改进后的约会网站的配对效果比较显著，多次随机划分测试集和训练集后发现正确率基本可以达到 90% 以上。

第1篇实验名称：基于仿真平台的编码算法性能评估实验日期：2023年4月10日实验地点：计算机实验室实验目的：1. 了解编码算法的基本原理和应用场景。

2. 通过仿真实验，评估不同编码算法的性能。

3. 分析编码算法在实际应用中的优缺点。

实验环境：1. 操作系统：Windows 102. 编译器：Visual Studio 20193. 仿真平台：MATLAB 2020a4. 编码算法：Huffman编码、算术编码、游程编码实验内容：1. 编写Huffman编码算法，实现字符序列的编码和解码。

2. 编写算术编码算法，实现字符序列的编码和解码。

3. 编写游程编码算法，实现字符序列的编码和解码。

4. 在仿真平台上，分别对三种编码算法进行性能评估。

实验步骤：1. 设计Huffman编码算法，包括构建哈夫曼树、编码和解码过程。

2. 设计算术编码算法，包括编码和解码过程。

3. 设计游程编码算法，包括编码和解码过程。

4. 编写仿真实验代码，对三种编码算法进行性能评估。

5. 分析实验结果，总结不同编码算法的优缺点。

实验结果及分析：一、Huffman编码算法1. 编码过程：- 对字符序列进行统计，计算每个字符出现的频率。

- 根据频率构建哈夫曼树，叶子节点代表字符，分支代表编码。

- 根据哈夫曼树生成编码，频率越高的字符编码越短。

2. 解码过程：- 根据编码，从哈夫曼树的根节点开始，沿着编码序列遍历树。

- 当遍历到叶子节点时，输出对应的字符。

3. 性能评估：- 编码长度：Huffman编码的平均编码长度最短，编码效率较高。

- 编码时间：Huffman编码算法的编码时间较长，尤其是在构建哈夫曼树的过程中。

二、算术编码算法1. 编码过程：- 对字符序列进行统计，计算每个字符出现的频率。

- 根据频率，将字符序列映射到0到1之间的实数。

- 根据映射结果，将实数序列编码为二进制序列。

2. 解码过程：- 对编码的二进制序列进行解码，得到实数序列。

进程调度算法的模拟实现⏹实验目的1．本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。

2．利用程序设计语言编写算法，模拟实现先到先服务算法FCFS、轮转调度算法RR、最短作业优先算法SJF、优先级调度算法PRIOR、最短剩余时间优先算法SRTF。

3．进行算法评价，计算平均等待时间和平均周转时间。

⏹实验内容及结果1．先来先服务算法2．轮转调度算法3. 优先级调度算法4. 最短时间优先算法5. 最短剩余时间优先算法⏹实验总结在此次模拟过程中，将SRTF单独拿了出来用指针表示，而其余均用数组表示。

⏹完整代码【Srtf.cpp代码如下：】//最短剩余时间优先算法的实现#include<stdio.h>#include<stdlib.h>#include<time.h>typedef struct{int remain_time; //进程剩余执行时间int arrive_time; //进程到达时间int Tp; //进入就绪队列的时间int Tc; //进入执行队列的时间int To; //进程执行结束的时间int number; //进程编号}Process_Block; //定义进程模块typedef struct _Queue{Process_Block PB;struct _Queue *next;}_Block,*Process; //定义一个进程模块队列中结点typedef struct{Process head; //队列头指针Process end; //队列尾指针}Process_Queue; //进程队列Process_Queue PQ; //定义一个全局队列变量int t; //全局时间Process Run_Now; //当前正在运行的进程，作为全局变量void InitQueue(Process_Queue PQ){PQ.head ->next = NULL;PQ.end ->next = PQ.head;}/*初始化队列*/int IsEmpty(Process_Queue PQ){if(PQ.end->next == PQ.head)return 1; //队列空的条件为头指针指向尾指针并且尾指针指向头指针elsereturn 0;}/*判定队列是否为空队列*/void EnQueue(Process_Queue PQ,Process P){Process temp =(Process)malloc(sizeof(_Block));temp = PQ.end;temp->next->next = P;PQ.end->next = P;}/*插入队列操作*/Process DeQueue(Process_Queue PQ){if(IsEmpty(PQ))return NULL;Process temp = PQ.head->next;PQ.head->next= temp ->next;if(PQ.end->next == temp)PQ.end->next = PQ.head;return temp;}/*出列操作*/Process ShortestProcess(Process_Queue PQ){if(IsEmpty(PQ)) //如果队列为空，返回{if(!Run_Now)return NULL;elsereturn Run_Now;}Process temp,shortest,prev;int min_time;if(Run_Now) //如果当前有进程正在执行，{shortest = Run_Now; //那么最短进程初始化为当前正在执行的进程，min_time = Run_Now->PB.remain_time;}else//如果当前没有进程执行，{shortest = PQ.head->next; //则最短进程初始化为队列中第一个进程min_time = PQ.head->next->PB.remain_time;}temp = PQ.head;prev = temp;while(temp->next){if(temp->next->PB.remain_time <min_time) //如果当前进程的剩余时间比min_time短，{shortest = temp->next; //则保存当前进程，min_time = shortest->PB.remain_time;prev=temp; //及其前驱}temp=temp->next;}if(shortest == PQ.end->next) //如果最短剩余时间进程是队列中最后一个进程，PQ.end->next = prev; //则需要修改尾指针指向其前驱prev->next = shortest->next; //修改指针将最短剩余时间进程插入到队头return shortest;}/*调度最短剩余时间的进程至队头*/void Run(){Run_Now->PB.remain_time--; //某一时间运行它的剩余时间减return;}/*运行函数*/void Wait(){return ;}int sum(int array[],int n){int i,sum=0;for(i=0;i<n;i++)sum+=array[i];return sum;}int main(){PQ.head = (Process)malloc(sizeof(_Block));PQ.end = (Process)malloc(sizeof(_Block));Run_Now = (Process)malloc(sizeof(_Block));Run_Now =NULL;InitQueue(PQ);int i,N,Total_Time=0; //Total_Time为所有进程的执行时间之和printf("请输入计算机中的进程数目:\n");scanf("%d",&N);Process *P,temp;P = (Process*)malloc(N*sizeof(Process));int *wt,*circle_t;wt =(int*)malloc(N*sizeof(int));circle_t =(int*)malloc(N*sizeof(int));for(i=0;i<N;i++){P[i] = (Process)malloc(sizeof(_Block));P[i]->PB.number =i+1;P[i]->next =NULL;wt[i] =0;circle_t[i] =0;printf("输入第%d个进程的到达时间及剩余执行时间:\n",i+1);scanf("%d %d",&P[i]->PB.arrive_time,&P[i]->PB.remain_time);}for(i=0;i<N;i++)Total_Time+=P[i]->PB.remain_time;printf("\n进程按顺序运行依次为:\n");i=0;int k=0;for(t=0;;t++){if(Run_Now) //如果当前有进程正在执行{Run();if(t == P[i]->PB.arrive_time) //如果当前时间正好有进程进入{if(P[i]->PB.remain_time < Run_Now->PB.remain_time){temp = P[i];P[i] = Run_Now;Run_Now = temp; //则调度它至运行队列中，Run_Now->PB.Tp=t;Run_Now->PB.Tc=t;wt[Run_Now->PB.number-1]+=Run_Now->PB.Tc-Run_Now->PB.Tp;printf("%d ",Run_Now->PB.number);}EnQueue(PQ,P[i]); //并将当前运行进程重新插入队列中P[i]->PB.Tp=t;k++;i=(i+1)>(N-1)?(N-1):(i+1);}if(Run_Now->PB.remain_time == 0) //如果当前进程运行结束，{Run_Now->PB.To=t; //进程运行结束的时间circle_t[Run_Now->PB.number-1] +=t-Run_Now->PB.arrive_time;free(Run_Now); //则将它所占资源释放掉，Run_Now =NULL; //并修改Run_Now为NULLRun_Now = ShortestProcess(PQ); //从就绪队列中调出最短剩余时间进程至队头，if(!Run_Now) //如果队列为空，转为等待状态{if(IsEmpty(PQ) && k >= N) break;Wait();continue;}else{Run_Now->PB.Tc=t;wt[Run_Now->PB.number-1]+=Run_Now->PB.Tc-Run_Now->PB.Tp;printf("%d ",Run_Now->PB.number);}}}else//如果当前运行进程为空，那么{if(t == P[i]->PB.arrive_time) //如果正好这时有进程入队{k++;EnQueue(PQ,P[i]);Run_Now = DeQueue(PQ); //则直接被调入运行队列中Run_Now->PB.Tp=t;Run_Now->PB.Tc=t;printf("%d ",Run_Now->PB.number);i=(i+1)>(N-1)?(N-1):(i+1);}else{Wait();continue;}}}printf("\n");printf("平均等待时间是:\n%f\n",((float)sum(wt,N))/N);printf("平均周转时间是:\n%f\n",((float)sum(circle_t,N))/N);return 0;}//////////////////////////////////////////////////////【Process.cpp代码如下：】#include<iostream>#include<string>using namespace std;class Process{public:string ProcessName; // 进程名字int Time; // 进程需要时间int leval; // 进程优先级int LeftTime; // 进程运行一段时间后还需要的时间};void Copy ( Process proc1, Process proc2); // 把proc2赋值给proc1void Sort( Process pr[], int size) ; // 此排序后按优先级从大到小排列void sort1(Process pr[], int size) ; // 此排序后按需要的cpu时间从小到大排列void Fcfs( Process pr[], int num, int Timepice); // 先来先服务算法void TimeTurn( Process process[], int num, int Timepice); // 时间片轮转算法void Priority( Process process[], int num, int Timepice); // 优先级算法void main(){int a;cout<<endl;cout<<" 选择调度算法："<<endl;cout<<" 1: FCFS 2: 时间片轮换 3: 优先级调度 4: 最短作业优先 5: 最短剩余时间优先"<<endl; cin>>a;const int Size =30;Process process[Size] ;int num;int TimePice;cout<<" 输入进程个数:"<<endl;cin>>num;cout<<" 输入此进程时间片大小: "<<endl;cin>>TimePice;for( int i=0; i< num; i++){string name;int CpuTime;int Leval;cout<<" 输入第"<< i+1<<" 个进程的名字、cpu时间和优先级:"<<endl;cin>>name;cin>> CpuTime>>Leval;process[i].ProcessName =name;process[i].Time =CpuTime;process[i].leval =Leval;cout<<endl;}for ( int k=0;k<num;k++)process[k].LeftTime=process[k].Time ;//对进程剩余时间初始化cout<<" ( 说明: 在本程序所列进程信息中，优先级一项是指进程运行后的优先级!! )";cout<<endl; cout<<endl;cout<<"进程名字"<<"共需占用CPU时间 "<<" 还需要占用时间 "<<" 优先级"<<" 状态"<<endl;if(a==1)Fcfs(process,num,TimePice);else if(a==2)TimeTurn( process, num, TimePice);else if(a==3){Sort( process, num);Priority( process , num, TimePice);}else// 最短作业算法，先按时间从小到大排序，再调用Fcfs算法即可{sort1(process,num);Fcfs(process,num,TimePice);}}void Copy ( Process proc1, Process proc2){proc1.leval =proc2.leval ;proc1.ProcessName =proc2.ProcessName ;proc1.Time =proc2.Time ;}void Sort( Process pr[], int size) //以进程优先级高低排序{// 直接插入排序for( int i=1;i<size;i++){Process temp;temp = pr[i];int j=i;while(j>0 && temp.leval<pr[j-1].leval){pr[j] = pr[j-1];j--;}pr[j] = temp;} // 直接插入排序后进程按优先级从小到大排列for( int d=size-1;d>size/2;d--){Process temp;temp=pr [d];pr [d] = pr [size-d-1];pr [size-d-1]=temp;} // 此排序后按优先级从大到小排列}/* 最短作业优先算法的实现*/void sort1 ( Process pr[], int size) // 以进程时间从低到高排序{// 直接插入排序for( int i=1;i<size;i++){Process temp;temp = pr[i];int j=i;while(j>0 && temp.Time < pr[j-1].Time ){pr[j] = pr[j-1];j--;}pr[j] = temp;}}/* 先来先服务算法的实现*/void Fcfs( Process process[], int num, int Timepice){ // process[] 是输入的进程，num是进程的数目，Timepice是时间片大小while(true){if(num==0){cout<<" 所有进程都已经执行完毕!"<<endl;exit(1);}if(process[0].LeftTime==0){cout<<" 进程"<<process[0].ProcessName<< " 已经执行完毕!"<<endl;for (int i=0;i<num;i++)process[i]=process[i+1];num--;}else if(process[num-1].LeftTime==0){cout<<" 进程"<<process[num-1].ProcessName<< " 已经执行完毕!"<<endl;num--;}else{cout<<endl; //输出正在运行的进程process[0].LeftTime=process[0].LeftTime- Timepice;process[0].leval =process[0].leval-1;cout<<" "<<process[0].ProcessName <<" "<<process[0].Time <<" ";cout<<process[0].LeftTime <<" "<<process[0].leval<<" 运行";cout<<endl;for(int s=1;s<num;s++){cout<<" "<<process[s].ProcessName <<" "<<process[s].Time <<"";cout<<process[s].LeftTime <<" "<<process[s].leval<<" 等待"<<endl; ;}} // elsecout<<endl;system(" pause");cout<<endl;} // while}/* 时间片轮转调度算法实现*/void TimeTurn( Process process[], int num, int Timepice){while(true){if(num==0){cout<<" 所有进程都已经执行完毕!"<<endl;exit(1);}if(process[0].LeftTime==0){cout<<" 进程"<<process[0].ProcessName<< " 已经执行完毕!"<<endl;for (int i=0;i<num;i++)process[i]=process[i+1];num--;}if( process[num-1].LeftTime ==0 ){cout<<" 进程" << process[num-1].ProcessName <<" 已经执行完毕! "<<endl;num--;}else if(process[0].LeftTime > 0){cout<<endl; //输出正在运行的进程process[0].LeftTime=process[0].LeftTime- Timepice;process[0].leval =process[0].leval-1;cout<<" "<<process[0].ProcessName <<" "<<process[0].Time <<" ";cout<<process[0].LeftTime <<" "<<process[0].leval<<" 运行";cout<<endl;for(int s=1;s<num;s++){cout<<" "<<process[s].ProcessName <<" "<<process[s].Time <<"";cout<<process[s].LeftTime <<" "<<process[s].leval;if(s==1)cout<<" 就绪"<<endl;elsecout<<" 等待"<<endl;}Process temp;temp = process[0];for( int j=0;j<num;j++)process[j] = process[j+1];process[num-1] = temp;} // elsecout<<endl;system(" pause");cout<<endl;} // while}/* 优先级调度算法的实现*/void Priority( Process process[], int num, int Timepice){while( true){if(num==0){cout<< "所有进程都已经执行完毕!"<<endl;exit(1);}if(process[0].LeftTime==0){cout<<" 进程" << process[0].ProcessName <<" 已经执行完毕! "<<endl;for( int m=0;m<num;m++)process[m] = process[m+1]; //一个进程执行完毕后从数组中删除num--; // 此时进程数目减少一个}if( num!=1 && process[num-1].LeftTime ==0 ){cout<<" 进程" << process[num-1].ProcessName <<" 已经执行完毕! "<<endl;num--;}if(process[0].LeftTime > 0){cout<<endl; //输出正在运行的进程process[0].LeftTime=process[0].LeftTime- Timepice;process[0].leval =process[0].leval-1;cout<<" "<<process[0].ProcessName <<" "<<process[0].Time <<" "; cout<<process[0].LeftTime <<" "<<process[0].leval<<" 运行";cout<<endl; // 输出其他进程for(int s=1;s<num;s++){cout<<" "<<process[s].ProcessName <<" "<<process[s].Time <<" "; cout<<process[s].LeftTime <<" "<<process[s].leval ;if(s==1)cout<<" 就绪"<<endl;elsecout<<" 等待 "<<endl;}} // elseSort(process, num);cout<<endl;system(" pause");cout<<endl;} // while}。

操作系统教程——银行家算法院系计算机与软件学院班级08软件工程2班学号***********姓名何丽茗一、实验目的银行家算法是避免死锁的一种重要方法。

通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法。

二、实验内容根据银行家算法的基本思想，编写和调试一个实现动态资源分配的模拟程序，并能够有效地防止和避免死锁的发生。

三、实验方法1.2.算法数据结构1)可利用资源向量Available ，它是一个最多含有100个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。

其数值随该类资源的分配和回收而动态地改变。

如果Available（j）=k，标是系统中现有j 类资源k个。

2)最大需求矩阵Max，这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。

如果Max（i，j）=k，表示进程i需要j类资源的最大数目为k。

3)分配矩阵Allocation，这也是一个n×m的矩阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。

如果Allocation（i，j）=k，表示进程i当前已经分到j类资源的数目为k。

Allocation i表示进程i的分配向量，有矩阵Allocation的第i行构成。

4)需求矩阵Need，这还是一个n×m的矩阵，用以表示每个进程还需要的各类资源的数目。

如果Need（i，j）=k，表示进程i还需要j类资源k个，才能完成其任务。

Need i 表示进程i的需求向量，由矩阵Need的第i行构成。

5)上述三个矩阵间存在关系：Need（i，j）=Max（i，j）-Allocation（i，j）；3.银行家算法设Request[i] 是进程i的请求向量，如果Request[i，j]=K,表示进程i需要K个j类型的资源。

一、实验目的1. 理解逻辑代码算法的基本原理和实现方法。

2. 掌握逻辑代码算法在实际问题中的应用。

3. 提高编程能力和算法设计能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.73. 开发工具：PyCharm三、实验内容本次实验主要涉及以下逻辑代码算法：1. 排序算法2. 搜索算法3. 图算法四、实验步骤1. 排序算法（1）选择排序选择排序是一种简单直观的排序算法。

它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

代码实现如下：```pythondef selection_sort(arr):n = len(arr)for i in range(n):min_index = ifor j in range(i+1, n):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]return arr# 测试arr = [64, 25, 12, 22, 11]print("原始数组：", arr)sorted_arr = selection_sort(arr)print("排序后的数组：", sorted_arr)```（2）冒泡排序冒泡排序是一种简单的排序算法。

它的工作原理是：比较相邻的元素。

如果第一个比第二个大（升序排序），就交换它们两个；对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。

这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后已经排序好的元素。

代码实现如下：```pythondef bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):arr[j], arr[j+1] = arr[j+1], arr[j]return arr# 测试arr = [64, 34, 25, 12, 22, 11]print("原始数组：", arr)sorted_arr = bubble_sort(arr)print("排序后的数组：", sorted_arr)```2. 搜索算法（1）二分查找二分查找是一种在有序数组中查找特定元素的搜索算法。

数据结构与算法实验源代码数据结构与算法实验源代码一、实验目的本实验旨在通过编写数据结构与算法的实验源代码，加深对数据结构与算法的理解，并提高编程能力。

二、实验环境本实验使用以下环境进行开发和测试：- 操作系统：Windows 10- 开发工具：IDEA（集成开发环境）- 编程语言：Java三、实验内容本实验包括以下章节：3.1 链表在本章节中，我们将实现链表数据结构，并实现基本的链表操作，包括插入节点、删除节点、查找节点等。

3.2 栈和队列在本章节中，我们将实现栈和队列数据结构，并实现栈和队列的基本操作，包括入栈、出栈、入队、出队等。

3.3 树在本章节中，我们将实现二叉树数据结构，并实现二叉树的基本操作，包括遍历树、搜索节点等。

3.4 图在本章节中，我们将实现图数据结构，并实现图的基本操作，包括广度优先搜索、深度优先搜索等。

3.5 排序算法在本章节中，我们将实现各种排序算法，包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。

3.6 搜索算法在本章节中，我们将实现各种搜索算法，包括线性搜索、二分搜索、广度优先搜索、深度优先搜索等。

四、附件本文档附带实验源代码，包括实现数据结构和算法的Java源文件。

五、法律名词及注释5.1 数据结构（Data Structure）：是指数据对象中数据元素之间的关系。

包括线性结构、树形结构、图形结构等。

5.2 算法（Algorithm）：是指解决问题的一系列步骤或操作。

算法应满足正确性、可读性、健壮性、高效性等特点。

5.3 链表（Linked List）：是一种常见的数据结构，由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

5.4 栈（Stack）：是一种遵循后进先出（LIFO）原则的有序集合，用于存储和获取数据。

5.5 队列（Queue）：是一种遵循先进先出（FIFO）原则的有序集合，用于存储和获取数据。

5.6 树（Tree）：是由节点组成的层级结构，其中一种节点作为根节点，其他节点按照父子关系连接。

第1篇一、实验目的1. 理解快速排序算法的基本原理和实现方法。

2. 掌握快速排序算法的时间复杂度和空间复杂度分析。

3. 通过实验验证快速排序算法的效率。

4. 提高编程能力和算法设计能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019三、实验原理快速排序算法是一种分而治之的排序算法，其基本思想是：选取一个基准元素，将待排序序列分为两个子序列，其中一个子序列的所有元素均小于基准元素，另一个子序列的所有元素均大于基准元素，然后递归地对这两个子序列进行快速排序。

快速排序算法的时间复杂度主要取决于基准元素的选取和划分过程。

在平均情况下，快速排序的时间复杂度为O(nlogn)，但在最坏情况下，时间复杂度会退化到O(n^2)。

四、实验内容1. 快速排序算法的代码实现2. 快速排序算法的时间复杂度分析3. 快速排序算法的效率验证五、实验步骤1. 设计快速排序算法的C++代码实现，包括以下功能：- 选取基准元素- 划分序列- 递归排序2. 编写主函数，用于生成随机数组和测试快速排序算法。

3. 分析快速排序算法的时间复杂度。

4. 对不同规模的数据集进行测试，验证快速排序算法的效率。

六、实验结果与分析1. 快速排序算法的代码实现```cppinclude <iostream>include <vector>include <cstdlib>include <ctime>using namespace std;// 生成随机数组void generateRandomArray(vector<int>& arr, int n) {srand((unsigned)time(0));for (int i = 0; i < n; ++i) {arr.push_back(rand() % 1000);}}// 快速排序void quickSort(vector<int>& arr, int left, int right) { if (left >= right) {return;}int i = left;int j = right;int pivot = arr[(left + right) / 2]; // 选取中间元素作为基准 while (i <= j) {while (arr[i] < pivot) {i++;}while (arr[j] > pivot) {j--;}if (i <= j) {swap(arr[i], arr[j]);i++;j--;}}quickSort(arr, left, j);quickSort(arr, i, right);}int main() {int n = 10000; // 测试数据规模vector<int> arr;generateRandomArray(arr, n);clock_t start = clock();quickSort(arr, 0, n - 1);clock_t end = clock();cout << "排序用时：" << double(end - start) / CLOCKS_PER_SEC << "秒" << endl;return 0;}```2. 快速排序算法的时间复杂度分析根据实验结果，快速排序算法在平均情况下的时间复杂度为O(nlogn)，在最坏情况下的时间复杂度为O(n^2)。

区域⽣长算法（附MATLAB代码实现）⼀、理论概念 区域⽣长是按照事先定义的⽣长准则将⼀个像素或者⼦区域逐步聚合成⼀个完整独⽴的连通区域过程。

对于图像感兴趣⽬标区域R，z为区域R上事先发现的种⼦点，按照规定的⽣长准则逐步将与种⼦点z⼀定邻域内符合相似性判据的像素合并成⼀个种⼦群以备下⼀阶段的⽣长，这样不断的进⾏循环⽣长直到满⾜⽣长停⽌条件为⽌，从⽽完成了对感兴趣区域由⼀个种⼦点⽣长为⼀个独⽴连通区域的过程。

其中相似性判据可以是像素灰度值、颜⾊、纹理特征等图像信息。

因此区域⽣长算法⼀般分为三个步骤实现：(1) 确定⽣长种⼦点(2) 规定⽣长准则(3) 确定⽣长停⽌条件实际⼯程应⽤中区域⽣长算法常被⽤于对⼆值化图像指定连通区域的分割。

图1以图⽂⽅式对区域⽣长算法的三步骤进⾏解释：①原始⼆值化图像(a)中的红⾊标注的像素为指定⽣长点；②图像(b)和(c)是采⽤不同⽣长准则进⾏区域⽣长的结果，其中图(b)是在4邻域下，待测像素与⽣长点像素灰度值相等的像素集合。

正如图中所⽰第1次⽣长时，与⽣长点像素灰度相等的像素有上、下、左、右四个像素，接着第⼆次⽣长时，就由前⼀次已经⽣长的像素按照同样的准则进⾏下去，直到遇到图像边界或背景区域时⽣长停⽌。

图(c)是在8邻域下，待测像素与⽣长点像素灰度值相等的像素集合。

⼆、MATLAB⽰例代码实现2.1 主函数⽂件%主⽂件clc;clear all;close all;%申明全局变量 R：区域⽣长的结果图像；BW：⼆值化图像；counter：感兴趣连通区域的像素个数%row：图像的⾏数；col：图像的列数global R BW counter row colI = imread('E:\MATLAB仿真\fsr.bmp');I = I(:,:,1);[row,col] = size(I);figure,imshow(I);level = graythresh(I);BW = im2bw(I,level);figure,imshow(BW);[y0,x0] = getpts;x0 = uint32(x0);y0 = uint32(y0);counter = 0;R = zeros(row,col);R = uint8(R);fsrRegiongrow(x0,y0,4);% fsrRegiongrow1(x0,y0,4);figure,imshow(R);2.2 函数模块1function fsrRegiongrow(x0,y0,mode)%功能：通过函数递归⽅法对⼆值化图像指定连通区域实现区域⽣长%输⼊参数： x0,y0表⽰⽣长点像素坐标，mode表⽰以多⼤邻域进⾏区域⽣长，常取mode = 4；mode = 8；%输出参数： void%作者&时间：奔跑在湘边———2016年5⽉6⽇global R BW counter row colif 8 == modefor i = -1 : 1for j = -1 : 1x1 = x0 + i;y1 = y0 + j;%⽣长准则：判断⽣长点8邻域内像素的各⾃灰度值是否与⽣长点所在像素灰度值相等if x1 > 0 && x1 <= row && y1 > 0 && y1 <= col && BW(x1,y1) == BW(x0,y0) && 0 == R(x1,y1)R(x1,y1) = 255;counter = counter + 1;fsrRegiongrow(x1,y1,mode);endendendelseif 4 == modefor i = -1 : 1x1 = x0 + i;y1 = y0;if x1 > 0 && x1 <= row && y1 > 0 && y1 <= col && BW(x1,y1) == BW(x0,y0) && 0 == R(x1,y1)R(x1,y1) = 255;counter = counter + 1;fsrRegiongrow(x1,y1,mode);endendx1 = x0;y1 = y0 - 1;if x1 > 0 && x1 <= row && y1 > 0 && y1 <= col && BW(x1,y1) == BW(x0,y0) && 0 == R(x1,y1)R(x1,y1) = 255;counter = counter + 1;fsrRegiongrow(x1,y1,mode);endx1 = x0;y1 = y0 + 1;if x1 > 0 && x1 <= row && y1 > 0 && y1 <= col && BW(x1,y1) == BW(x0,y0) && 0 == R(x1,y1)R(x1,y1) = 255;counter = counter + 1;fsrRegiongrow(x1,y1,mode);endendend2.3 函数模块2function fsrRegiongrow1(x0,y0,mode)%功能：模拟栈的先进后出思路对⼆值化图像指定连通区域实现区域⽣长%输⼊参数： x0,y0表⽰⽣长点像素坐标，mode表⽰以多⼤邻域进⾏区域⽣长，常取mode = 4；mode = 8；%输出参数： void%作者&时间：奔跑在湘边———2016年5⽉6⽇global R BW counter row colzhan = zeros(row*col,2);%创建栈数组pzhan = 1; %栈计数zhan(pzhan,1) = x0;zhan(pzhan,2) = y0;R(x0,y0) = 255;counter = 1;if 8 == modewhile pzhan > 0x1 = zhan(pzhan,1);%出栈y1 = zhan(pzhan,2);pzhan = pzhan - 1; %栈计数减⼀for i = -1 : 1for j = -1 : 1%⽣长准则：判断⽣长点8邻域内像素的各⾃灰度值是否与⽣长点所在像素灰度值相等if x1+i > 0 && x1+i <= row && y1+j > 0 && y1+j <= col && BW(x1+i,y1+j) == BW(x1,y1) && R(x1+i,y1+j) ~= R(x1,y1) R(x1+i,y1+j) = R(x1,y1);counter = counter + 1;pzhan = pzhan + 1; %栈计数增⼀zhan(pzhan,1) = x1 + i;%⼊栈zhan(pzhan,2) = y1 + j;endendendendelseif 4 == modewhile pzhan > 0x1 = zhan(pzhan,1);y1 = zhan(pzhan,2);pzhan = pzhan - 1;for i = -1 : 2 : 1j = 0;if x1+i > 0 && x1+i <= row && y1+j > 0 && y1+j <= col && BW(x1+i,y1+j) == BW(x1,y1) && R(x1+i,y1+j) ~= R(x1,y1)R(x1+i,y1+j) = R(x1,y1);counter = counter + 1;pzhan = pzhan + 1;zhan(pzhan,1) = x1 + i;zhan(pzhan,2) = y1 + j;endendfor j = -1 : 2 : 1i = 0;if x1+i > 0 && x1+i <= row && y1+j > 0 && y1+j <= col && BW(x1+i,y1+j) == BW(x1,y1) && R(x1+i,y1+j) ~= R(x1,y1)R(x1+i,y1+j) = R(x1,y1);counter = counter + 1;pzhan = pzhan + 1;zhan(pzhan,1) = x1 + i;zhan(pzhan,2) = y1 + j;endendendendend三、说明在基于MATLAB7.11.0(R2010b)平台调⽤函数模块fsrRegiongrow时，MATLAB会弹出如下警告??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)to change the limit. Be aware that exceeding your available stack space can crash MATLAB and/or your computer.Error in ==> fsrRegiongrow上述警告表⽰递归次数超出了MATLAB默认值，也就是说待处理的感兴趣连通区域像素个数太多（⼤于500），此时⽤户可以尝试通过提⽰的set函数来修改函数递归次数，但是本⽂通过测试发现如果递归次数超出1591时（不同的平台该值可能不同），MATLAB软件会⾃动⽴即关闭。