数据结构与算法课程设计

1、数据结构与算法课程设计实习一需求规格说明1、单链表的输出要求：使用“递归”算法实现单链表中数据的顺序和逆序输出，但不允许引入额外的空间复杂度。总体分析与设计利用链表的存储结构，并采用递归的思想；主函数 void OpSeqOutput(int n) void SeqOutput() 利用主函数调用void OpSeqOutput(int n)和void SeqOutput()实现数序列逆序和顺序输出；编码void SeqOutput()利用递归的方法，输出头结点后，删除该节点；void OpSeqOutput(int n)利用递归的方法，为尾节点计数，并依次逆序输出；程序及算法分析输入n个数进

2、行测试，输出结果：List is: 5 4 9 8 7 4 5 6 7 8 9 6 8 6 4 5 6 7 5 3 9 8 7 6 5 4 2 6 4 2 9 8 2 5 4 3 2 1 5 4 9 8 7 4 5 6 7 8 9 6 8 6 4 5 6 7 5 3 9 8 7 6 5 4 2 6 4 2 9 8 2 5 4 3 2 1 5 4 9 8 7 4 5 6 7 8 9 6 8 6 4 5 6 7 5 3 9 8 7 6 5 4 2 6 4 2 9 8 2 5 4 3 2 1List sequence reverse output:1 2 3 4 5 2 8 9 2 4 6 2 4

3、5 6 7 8 9 3 5 7 6 5 4 6 8 6 9 8 7 6 5 4 7 8 9 4 5 1 23 4 5 2 8 9 2 4 6 2 4 5 6 7 8 9 3 5 7 6 5 4 6 8 6 9 8 7 6 5 4 7 8 9 4 5 1 2 3 45 2 8 9 2 4 6 2 4 5 6 7 8 9 3 5 7 6 5 4 6 8 6 9 8 7 6 5 4 7 8 9 4 5List sequence output:5 4 9 8 7 4 5 6 7 8 9 6 8 6 4 5 6 7 5 3 9 8 7 6 5 4 2 6 4 2 9 8 2 5 4 3 2 1 5 49

4、 8 7 4 5 6 7 8 9 6 8 6 4 5 6 7 5 3 9 8 7 6 5 4 2 6 4 2 9 8 2 5 4 3 2 1 5 4 9 87 4 5 6 7 8 9 6 8 6 4 5 6 7 5 3 9 8 7 6 5 4 2 6 4 2 9 8 2 5 4 3 2 1请按任意键继续. . .采用递归的方法，如果数序列较大，则时间复杂度较大；小结利用递归的方法空间复杂度较小；附录void Chain<T>:SeqOutput() ChainNode<T> *current=first;if(current) int i=0;T x; cout<

5、<current->data<<" "i+;Delete(i,x);SeqOutput();elsecout<<endl;/*cout<<"List sequence sequence output over!"<<endl;*/逆序输出template <class T>void Chain<T>:OpSeqOutput(int n)ChainNode<T> *current=first;ChainNode<T> *trail;if(first

6、&& n>0) for(int i=0;current&&i<n;i+)trail=current; current=current->link;cout<<trail->data<<" "OpSeqOutput(n-1);/*cout<<"List sequence reverse output over!"<<endl;*/ 实习二需求规格说明2、二值图像的像元分组算法简介：二值图像中每个元素的值只能为1或0，其中1表示有效像元，0表示图像的背景。

7、如果一个元素在另外一个元素的上、下、左、右四个方向，称两个元素为相邻元素。“像元分组”算法是将二值图像中处于相邻的元素进行分组标号，使得属于同一个分组的像元集合，其编号都相同。如下图所示：110000110000000100001101001001000001110000110000000200002203002003000003 分组前 分组后 要求：使用“队列”来实现二值图像的像元分组，图像数据采用TXT文件形式给出，把分组结果图像输出到另外一个文件总体分析与设计利用队列的存储结构；数字化图像是一个m*n的像素矩阵。识别图元就是对元像素进行标记，当且仅当两个像素属于同一图元时，它们的标号相

8、同；在识别图元的过程中，图像的周围包上一圈空白像素（即0像素）；采用数组0offset来确定与一个给定像素相邻的像素。通过逐行扫描像素来识别图元。当遇到一个没有标号的图元的像素时，就给它指定一个图元编号（使用数字2、3、等为图元编号），该像素就为一个新图元种子，通过识别和标记与种子相邻的所有图元像素，可以确定图元中的其它像素。编码先在图像外围包上一圈背景像素，并对offset进行初始化，接下来的两个for循环通过扫描图像寻找下一个图元的种子。再图元标号设置为种子标号，接下来借助于链表队列的帮助，可以识别出该图元的其余像素。程序及算法分析1091 1 1 1 0 0 0 0 0 0 0 0 0

9、0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 3 3 3 3 3 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 3 3 3 0 0 1 1 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 5 5 5 0 0 1 1 1 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 7 0 0 0 0

10、0 0 1 1 1 0 1 0 0 0 0 7 7 7 0 8 0 对于任一个图元来说，识别标记该图元的的每个像素（种子除外）所需时间为O(cnum)，识别并标记所有非种子图元像素所需要的总时间为（）。小结其存储方式可以用公式化队列，链表堆栈，或公式化堆栈。附录#include "stdafx.h"#include "Disgra.h"#include <iostream>#include <fstream>using namespace std;#define max 40int _tmain(int argc, _TCHAR*

11、 argv)ifstream f1("data.txt",ios:_Nocreate);Disgra D; /创建Disgra的对象DD.pixel;int rows(0),cols(0);f1>>rows>>cols; /读入行数和列数int n(0); for(int i=0;i<rows;i+)for(int j=0;j<cols;j+)f1>>n; /读入像元数据，并存入pixel数组D.pixelij=n;f1.close(); D.Lable(rows,cols); /调用函数Lableofstream f2(&q

12、uot;data2.txt",ios:out);int l(0); /计数 for(int i=0;i<rows;i+)for(int j=0;j<cols;j+) l+;f2<<D.pixelij<<" " /输出被标记的像元if(l=9) f2<<endl; l=0;f2.close(); return 0;#ifndef Disgra_#define Disgra_#include "positoin.h"#include "lqueue.h"#define MAXSIZ

13、E 50struct Disgraint pixelMAXSIZEMAXSIZE; /存储数据的二维数组void Lable(int rows,int cols);/标记函数;void Disgra:Lable(int rows,int cols)/*int pixelMAXSIZEMAXSIZE;*/*int rows(0),cols(0);*/for(int i=0;i<=cols;i+)pixel0i=pixelrows+1i=0;for(int i=0;i<rows;i+) pixeli0=pixelicols+1=0;Position offset4;offset0.ro

14、w=0;offset0.col=1;offset1.row=1;offset1.col=0;offset2.row=0;offset2.col=-1;offset3.row=-1;offset3.col=0;int NumOfNbrs=4;LinkedQueue<Position> Q;int id=1;Position here,nbr;for(int r=1;r<=rows;r+)for(int c=1;c<=cols;c+)if(pixelrc=1)pixelrc=+id;here.row=r;here.col=c;dofor(int i=0;i<NumOf

15、Nbrs;i+)nbr.row=here.row+offseti.row;nbr.col=here.col+offseti.col;if(pixelnbr.rownbr.col=1)pixelnbr.rownbr.col=id;Q.Add(nbr);if(Q.IsEmpty()break;Q.Delete(here);while(true);#endif实习三需求规格说明3、课程安排问题一套好的课程体系有如下要求：各个课程之间有着严格的先后顺序关系；两个相邻课程之间的跨度为一个时间段（具体就是一个学期）。课程安排问题，是为了验证专业课程安排方案是否合理，并提供多种选课方案供学生进行选择。现有软

16、件工程专业课程表（采用TXT文件格式），格式如下：课程代号 课程名称 先修课程代号11049 高等代数C25003 计算机高级语言22222 计算机导论33333 计算机结构与组成 25003,22222要求：使用“拓扑排序”算法，设计一个程序：（1）验证软件工程专业课程表是否合理？若不合理，指出并修改不合理的课程安排，产生新的软件工程专业课程表；（2）对软件工程专业课程表，输出多种选课方案，以供学生进行选择。总体分析与设计利用图和栈存储结构；并利用贪婪算法来求解问题；有向图的顶点代表任务，有向边（，）表示先后关系，任务开始前任务必须完成。利用数组来描述课程，用一个栈来保存可加入的候选点，并用

17、一维数组，表示与顶点相连的节点数目，其中顶点不是中的成员，它们之间有向图得边为（，），当变为时，表示成为一个候选点。序列初始时为空。为顶点的入度。每次向中加入一个顶点时，所有与新加入顶点临接的顶点，其减主函数bool Topological(int v)S.Add(i)Begin(w)S.Delete(w)NextVertex(w)编码每一步，从栈中去出一个顶点将其加入，同时减去与其邻接的顶点的值。程序及算法分析测试数据：课程代号 课程名称 先修课程代号11049 高等代数C25003 计算机高级语言22222 计算机导论33333 计算机结构与组成 25003,2222244444 软件工程

18、概论 2222255555 面向对象程序设计 2500311016 离散数学 11049,2500325057 数据结构与算法 11016,2500366666 操作系统 33333,2505770000 计算机网络 2505770010 统一建模语言 44444,5555570020 软件需求 4444470030 软件测试 4444470040 软件过程与管理 70020,7003070050 软件项目管理 7004070060 软件能力成熟度模型 70050运行结果：软公选课课程推荐表：课程代号 课程名称22222 计算机导论25003 计算机高级语言33333 计算机结构与组成1104

19、9 高等代数C11016 离散数学55555 面向对象程序设计25057 数据结构与算法66666 操作系统44444 软件工程概论70010 统一建模语言70020 软件需求70030 软件测试70040 软件过程与管理70050 软件项目管理70060 软件能力成熟度模型70000 计算机网络第一和第三个循环的时间开销为（），利用邻接矩阵，改程序的时间复杂度为（）小结当算法失败时，有向图没有拓扑序列，若算法没有失败，则为一个拓扑序列。附录bool Network:Topological(int v)/ Compute topological ordering of digraph vert

20、ices. / Return true if a topological order is found. / In this case return the order in v0:n-1. / Return false if there is no topological order. int n = Vertices(); / Compute in-degrees int *InDegree = new int n+1; InitializePos(); / graph iterator array for (int i = 1; i <= n; i+) / initialize I

21、nDegreei = 0; for (int i = 1; i <= n; i+) / edges out of i int u = Begin(i); while (u) InDegreeu+; u = NextVertex(i); / Stack vertices with zero in-degree LinkedStack<int> S; for (int i = 1; i <= n; i+) if (!InDegreei) S.Add(i); / Generate topological order int i = 0; / cursor for array

22、v while (!S.IsEmpty() / select from stack int w; / next vertex S.Delete(w); vi+ = w; int u = Begin(w); while (u) / update in-degrees InDegreeu-; if (!InDegreeu) S.Add(u); u = NextVertex(w); DeactivatePos(); delete InDegree; return (i = n);/ CourseSequence.cpp : 定义控制台应用程序的入口点。/#include "stdafx.h

23、"#include "course.h"#include <fstream>#include <iostream>using namespace std;#include "ldigraph.h"int _tmain(int argc, _TCHAR* argv)ifstream f1("data.txt",ios:_Nocreate);int n=0;/读取文件f1>>n;int *T=new intn+1;/*for(int i=0;i<n;i+)Ti=0;*/ course*

24、Mycou=new coursen+1;/*course* T_Mycou=new couresn+1;*/for(int i=0;i<n;i+)if(i=9|i=11|i=12|i=14|i=15)f1>>Mycoui.v>>Mycoui.num>>M>>Mycoui.fnum1;else if(i=0|i=1|i=2)f1>>Mycoui.v>>Mycoui.num>>M;elsef1>>Mycoui.v>>Mycoui.num>&

25、gt;M>>Mycoui.fnum1>>Mycoui.fnum2;f1.close();/初始化图LinkedDigraph DG(n);for(int i=0;i<n;i+)if(Mycoui.v=10|Mycoui.v=12|Mycoui.v=13|Mycoui.v=15|Mycoui.v=16)DG.Add(Mycoui.fnum1,Mycoui.v);else if(Mycoui.v=1|Mycoui.v=2|Mycoui.v=3)continue;elseDG.Add(Mycoui.fnum1,Mycoui.v);DG.Add(Myc

26、oui.fnum2,Mycoui.v); /*cout << "The graph is" << endl; DG.Output();*/DG.Topological(T);/拓扑排序ofstream f2("data1.txt",ios:out);f2<<"软公选课课程推荐表："<<endl; f2<<"课程代号"<<" "<<"课程名称"<<endl;/输出排序后课表 for(

27、int i=0;i<n;i+)f2<<MycouTi-1.num<<" "<<MycouT<<endl; f2.close(); return 0; 实习四需求规格说明电话簿软件的实现（动态查找表算法的应用）【问题描述】 在很多实际应用中，动态索引结构在文件创建或初始装入记录时生成，在系统运行过程中插入或删除记录时，为了保持较好的检索性能，索引结构本身将随之发生改变。教材上已经介绍的动态查找数据结构包括：二叉搜索树（BST）、平衡二叉树（AVL）、红黑树（RBT）、B-树。本题要求选取一种已经学过的动态搜

28、索树结构，设计并实现一个手机电话薄软件。【基本要求】一个完整的电话簿软件应具有以下功能：（1）支持复式电话簿数据的存储，数据条目不少于500条。每个人名下可保存的信息包括：姓名、手机号码、住宅电话号码、办公电话号码、电子邮件地址、所属群组、备忘录等。（2）支持电话簿记录的添加、删除、编辑等操作。（3）将不同类型的人群按照同事、朋友、家人、商务伙伴等分组，支持群组记录的添加、删除、编辑等操作。（4）支持所有电话簿记录的导入、导出操作，外部数据采用TXT格式。（5）支持电话簿记录的各种查询操作，具体包括： 逐条翻看能显示所有的电话簿记录，支持分屏查看。 电话号码查找输入一个电话号码（手机、住宅、办

29、公），能将包含该号码的电话簿记录显示出来。 人名查找 输入一个人名（全名或者部分名），能将包含该姓名的电话簿记录显示出来。 群组查找 选择一种群组类型，能将属于该群组的所有电话簿记录显示出来。（6）要求使用BST或者AVL实现动态索引结构。【提高要求】（1）系统支持铃声库和图片库的数据存储，提供添加、删除、修改、播放等操作。铃声库和图片库可直接使用文件目录进行管理；铃声格式可使用WAV、MP3或者WMA格式；图片格式可使用BMP、JPG等格式。（2）电话簿记录信息支持：来电铃声、来电图片等信息，用户可通过界面编辑或者浏览某条电话簿记录的来电铃声、来电图片。（3）人名查询支持：输入姓名的首字母查

30、找。（4）使用红黑树或者B-树的数据结构，来实现动态索引结构。【测试数据】自行随机生成5001000条电话簿数据记录。【实现提示】（1）设计合适的电话簿数据文件格式；（2）设计合适的索引文件格式。 总体分析与设计利用二叉搜索数为存储结构进行存储；利用mfc进行实习；Phone_Book_2Dlg MyDlg_1MyDlg_2MyDlg_3MyDlg_4MyDlg_5MyDlg_6MyDlg_7由Phone_Book_2Dlg调用MyDlg_1（显示姓名号码的对话框），MyDlg_2（新建分组对话框）， MyDlg_3 （导入对话框），MyDlg_4（到处对话框） MyDlg_5（编辑名片对话框

31、） MyDlg_6（显示联系人编辑框）， MyDlg_7（新建分组编辑框）；编码Mfc的使用，即各对话框的调用函数使用；编辑框的设计；程序及算法分析 小结Mfc的使用还有待熟练，需要了解基本的mfc的使用方法；附录/ Phone_Book_2Dlg.cpp : implementation file/电话簿主页 #include "stdafx.h"#include "Phone_Book_2.h"#include "Phone_Book_2Dlg.h"#include <string>#include <fstre

32、am>using namespace std;#ifdef _DEBUG#define new DEBUG_NEW#endifCBook *PhBook=new CBook1000; /电话簿int n; /电话簿的个数int n_new=0; /创建的电话记录的个数int m_int=0; /表示被选中的位置/ CAboutDlg dialog used for App Aboutclass CAboutDlg : public CDialogpublic:CAboutDlg();/ Dialog Dataenum IDD = IDD_ABOUTBOX ;protected:virtu

33、al void DoDataExchange(CDataExchange* pDX); / DDX/DDV support/ Implementationprotected:DECLARE_MESSAGE_MAP();CAboutDlg:CAboutDlg() : CDialog(CAboutDlg:IDD)void CAboutDlg:DoDataExchange(CDataExchange* pDX)CDialog:DoDataExchange(pDX);BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)END_MESSAGE_MAP()/ CPhone_Book_

34、2Dlg dialogCPhone_Book_2Dlg:CPhone_Book_2Dlg(CWnd* pParent /*=NULL*/): CDialog(CPhone_Book_2Dlg:IDD, pParent), m_boxv(_T(""), m_search(_T("")m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);void CPhone_Book_2Dlg:DoDataExchange(CDataExchange* pDX)CDialog:DoDataExchange(pDX);DDX_C

35、ontrol(pDX, IDC_TAB1, m_tab);DDX_Control(pDX, IDC_COMBO1, m_box);DDX_CBString(pDX, IDC_COMBO1, m_boxv);DDX_Text(pDX, IDC_EDIT1, m_search);BEGIN_MESSAGE_MAP(CPhone_Book_2Dlg, CDialog)ON_WM_SYSCOMMAND()ON_WM_PAINT()ON_WM_QUERYDRAGICON()/AFX_MSG_MAP/*ON_BN_CLICKED(IDC_BUTTON1, &CPhone_Book_2Dlg:OnB

36、nClickedButton1)*/*ON_BN_CLICKED(IDC_BUTTON2, &CPhone_Book_2Dlg:OnBnClickedButton2)*/ON_NOTIFY(TCN_SELCHANGE, IDC_TAB1, &CPhone_Book_2Dlg:OnTcnSelchangeTab1)ON_CBN_SELCHANGE(IDC_COMBO1, &CPhone_Book_2Dlg:OnCbnSelchangeCombo1)ON_WM_LBUTTONDBLCLK()ON_EN_CHANGE(IDC_EDIT1, &CPhone_Book_2

37、Dlg:OnEnChangeEdit1)ON_BN_CLICKED(IDC_BUTTON3, &CPhone_Book_2Dlg:OnBnClickedButton3)ON_BN_CLICKED(IDC_RADIO1, &CPhone_Book_2Dlg:OnBnClickedRadio1)ON_BN_CLICKED(IDC_RADIO2, &CPhone_Book_2Dlg:OnBnClickedRadio2)END_MESSAGE_MAP()/ CPhone_Book_2Dlg message handlersBOOL CPhone_Book_2Dlg:OnInit

38、Dialog()CDialog:OnInitDialog();/ Add "About." menu item to system menu./ IDM_ABOUTBOX must be in the system command range.ASSERT(IDM_ABOUTBOX & 0xFFF0) = IDM_ABOUTBOX);ASSERT(IDM_ABOUTBOX < 0xF000);CMenu* pSysMenu = GetSystemMenu(FALSE);if (pSysMenu != NULL)CString strAboutMenu;strA

39、boutMenu.LoadString(IDS_ABOUTBOX);if (!strAboutMenu.IsEmpty()pSysMenu->AppendMenu(MF_SEPARATOR);pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);/ Set the icon for this dialog. The framework does this automatically/ when the application's main window is not a dialogSetIcon(m_hIc

40、on, TRUE);/ Set big iconSetIcon(m_hIcon, FALSE);/ Set small icon/ TODO: Add extra initialization here/*添加选项卡m_tab.InsertItem( 0 , "联系人" ); /添加参数一选项卡m_tab.InsertItem( 1 , "分组" ); /添加参数二选项卡/m_tab.InsertItem( 2 , "" );/*关联对话框,并且将IDC_TAB1 控件设为父窗口m_dlg_1.Create( IDD_DIALOG1

41、, GetDlgItem(IDC_TAB1) );m_dlg_2.Create( IDD_DIALOG2 , GetDlgItem(IDC_TAB1) );m_dlg_6.Create( IDD_DIALOG6 , GetDlgItem(IDC_TAB1) );/*获得客户区大小CRect rs;m_tab.GetClientRect( &rs );/*调整子对话框在父窗口中的位置rs.top += 20;/rs.bottom -= 8;/rs.left += 8;/rs.right -= 8;/*设置子对话框尺寸并移动到指定位置m_dlg_1.MoveWindow(&rs);

42、m_dlg_6.MoveWindow(&rs);m_dlg_2.MoveWindow(&rs);/*分别设置隐藏和显示m_dlg_1.ShowWindow(true);m_dlg_6.ShowWindow(false);m_dlg_2.ShowWindow(false);/*设置默认的选项卡m_tab.SetCurSel(0); /box控件 m_box.AddString("名片编辑");m_box.AddString("查看");m_box.AddString("创建");m_box.AddString("

43、;修改");m_box.AddString("删除");m_box.AddString("显示联系人"); m_box.AddString("导入"); m_box.AddString("导出");m_box.SetCurSel(1);return TRUE; / return TRUE unless you set the focus to a controlvoid CPhone_Book_2Dlg:OnSysCommand(UINT nID, LPARAM lParam)if (nID &

44、0xFFF0) = IDM_ABOUTBOX)CAboutDlg dlgAbout;dlgAbout.DoModal();elseCDialog:OnSysCommand(nID, lParam);/ If you add a minimize button to your dialog, you will need the code below/ to draw the icon. For MFC applications using the document/view model,/ this is automatically done for you by the framework.v

45、oid CPhone_Book_2Dlg:OnPaint()if (IsIconic()CPaintDC dc(this); / device context for paintingSendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc(), 0);/ Center icon in client rectangleint cxIcon = GetSystemMetrics(SM_CXICON);int cyIcon = GetSystemMetrics(SM_CYICON);CRect rect;

46、GetClientRect(&rect);int x = (rect.Width() - cxIcon + 1) / 2;int y = (rect.Height() - cyIcon + 1) / 2;/ Draw the icondc.DrawIcon(x, y, m_hIcon);elseCDialog:OnPaint();/ The system calls this function to obtain the cursor to display while the user drags/ the minimized window.HCURSOR CPhone_Book_2D

47、lg:OnQueryDragIcon()return static_cast<HCURSOR>(m_hIcon);void CPhone_Book_2Dlg:OnTcnSelchangeTab1(NMHDR *pNMHDR, LRESULT *pResult)/ TODO: Add your control notification handler code here /监控m_tab 的变化int CurSel = m_tab.GetCurSel();switch( CurSel )case 0:m_dlg_1.ShowWindow(true);m_dlg_6.ShowWindo

48、w(false);m_dlg_2.ShowWindow(false);break;case 1:m_dlg_1.ShowWindow(false);m_dlg_6.ShowWindow(false);m_dlg_2.ShowWindow(true);break;default:break;*pResult = 0;void CPhone_Book_2Dlg:OnCbnSelchangeCombo1() /名片编辑 / TODO: Add your control notification handler code hereCString text;CComboBox* m_box=(CComboBox*)GetDlgItem(IDC_COMBO1); /IDC_COMBO1m_bo