数据结构实验之最长公共子序列

简介: 本实验旨在通过编程实践帮助学生理解串的基本概念及求解最长公共子序列的算法。实验内容包括使用动态规划方法设计并实现算法,以找出给定两序列的最大公共子序列。示例代码展示了如何通过构建状态矩阵和回溯路径来找到解决方案。实验总结指出,`memset()`函数用于内存初始化,且对于特定输入,程序能正确输出最长公共子序列之一。

 实验目的

1、了解串的基本概念

2、掌握求最长公共子序列的算法

  • 实验内容和代码

设计并实现,求最长公共子序列的算法。使用动态规划算法解决最长公共子序列问题:给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。(使用动态规划的思想)(递归)

#include<iostream>

#include<stack>

#include<string>

#include<cstring>

using namespace std;

void GetLCS(string &str1, string &str2){

   int m = str1.length() + 1;

   int n = str2.length() + 1;

   int length[m][n];

   int state[m][n];

   memset( state, 100, sizeof(state) );//初始化函数,将全部内容设定为指定的值

   for(int i=0; i<m; i++){  //初始化第1列

       length[i][0] = 0;

   }

   for(int j=0; j<n; j++){//初始化第1行

       length[0][j] = 0;

   }

   for(int i=1; i<m; i++){

       for(int j=1; j<n; j++){

           if(str1[i-1] == str2[j-1]) {

               length[i][j] = length[i-1][j-1] + 1;

               state[i][j] = 0;

           }else if(length[i][j-1] >= length[i-1][j]) {

               length[i][j] = length[i][j-1];

               state[i][j] = -1;  //列数减一

           }else {

               length[i][j] = length[i-1][j];

               state[i][j] = 1;  //行数减一

           }

       }

   }

   //打印最长子序列

   stack<char> lcs;//常用栈函数,栈的一些基本操作包括在stack文件中

   for(int i=m-1, j=n-1; i>=0 && j>=0;){

       if(state[i][j] == 0){//说明str1的第i个元素和str2的第j个元素相同        

           lcs.push(str1[i-1]);

           i--;

           j--;

       }else if(state[i][j] == 1){

           i--;  //行数减一

       }else{

           j--; //列数减一

       }

   }

   if(lcs.empty()){

       cout<<"没有公共子序列"<<endl;

       return ;

   }

   cout<<"最长的子序列:";

   while(!lcs.empty()){

       cout<<lcs.top();

       lcs.pop();

   }

   cout<<"\n其长度为:"<<length[m-1][n-1];

   return ;

}

int main(){

   string str1 = "abcdefghijklmnree";

   string str2 = "cdfgrrze";

   cout<<"序列1:"<<str1<<endl;

   cout<<"序列2:"<<str2<<endl;

   GetLCS(str1,str2);

   return 0;

}

  • 实验小结

image.gif 编辑

memset()函数是初始化函数,作用是将某一块内存中的全部内容设置为指定的值

序列1和序列2最大公共子序列有三种:BCAB、BDAB、BCBA,只能输出BDAB的情形

四、教师评语

目录
打赏
0
4
4
0
71
分享
相关文章
数据结构实验之矩阵的运算器(二维数组)
本实验旨在通过团队合作,掌握数组和矩阵相关运算的代码实现,包括矩阵的加减、数乘、转置、乘法、n次方及行列式的计算。实验过程中,成员们需分工协作,解决编程难题,最终实现一个功能完备的矩阵计算器。通过本实验,不仅锻炼了编程能力,还加深了对数学概念的理解,同时培养了团队合作精神。
89 4
|
3月前
数据结构实验之串模式匹配问题
本实验旨在掌握串模式匹配技术,通过创建文本文件、实现单词计数与定位功能,最终构建一个包含文件建立、单词统计与定位、程序退出等选项的主菜单,以增强对字符串处理的理解与应用能力。
82 4
|
3月前
|
数据结构实验之操作系统打印机管理器问题
本实验旨在通过实现操作系统中的打印机管理器问题,掌握队列的基本操作如入队、出队等,利用队列的先进先出特性解决先申请先打印的问题。实验包括队列的初始化、入队、出队、打印队列内容等功能,并通过菜单式界面进行交互。实验结果显示基本功能可正常执行,但在连续操作时存在执行失败的情况,需进一步优化。
65 4
|
3月前
|
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
84 4
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
133 4
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
83 4
【Python学习篇】Python实验小练习——高级数据结构(五)
【Python学习篇】Python实验小练习——高级数据结构(五)
91 1
|
4月前
|
计科一二班算法数据结构实验9答案
计科一二班算法数据结构实验9答案
29 0
数据结构实验(四)二叉树的基本操作
数据结构实验(四)二叉树的基本操作
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等