数据结构课程设计报告数据结构演示系统文档格式.docx
《数据结构课程设计报告数据结构演示系统文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告数据结构演示系统文档格式.docx（41页珍藏版）》请在冰点文库上搜索。
查找输入为各合法字符。
3.插入根据用户输入，在指定位置插入指定元素，若输入位置超出链表范围，给出越界错误提示；
若用户未输入插入元素，亦给出相应提示提示。
入元素为各合法字符，插入位置为0-100间整数。
4.删除根据用户输入，删除链表中指定位置对应元素，并返回被删除元素。
若用户输入位置超出链表范围，给出相应错误提示。
5.合并根据用户输入，将输入无序表排序后，进行有序合并。
三、KMP部分
1.数据输入输入主串及模式串元素为各合法输入（含中文）。
2.求解next对用户输入模式串T根据KMP算法求解各元素对应next值。
3.模式匹配利用求得的next值对用户输入的主串S及模式串T进行模式匹配，并返回匹配结果信息。
4.求解nextval对用户输入模式串T根据改进算法求解各元素对应nextval值。
第2章
概要设计
一、数据结构
1.主对话框
classCDS_DEMO_1Dlg:
publicCDialog
{
……//构造函数及其它基本数据元素与操作
public:
各控件事件
}
2.顺序表
classCSqDialog:
……//构造函数及其它基本数据元素与操作
protected:
各控件变量及其它相关变量
各控件事件及其它成员函数
全局友元
3.链表
classCListDialog:
protected:
4.KMP
classCKmpDialog:
二、程序主流程
三、模块层次
主对话框响应三个不同单击事件，对应打开三个模态对话框：
顺序表演示、链表演示、KMP演示。
1.顺序表演示
创建按钮：
响应事件，将用户输入转换为以空格分隔的顺序表输出到对应文本框。
若此时顺序表非空，启用插入、删除按钮。
插入按键：
响应事件，在顺序表非空及插入位置合法时，按用户输入将元素插入到指定位置。
删除按钮：
响应事件，在顺序表非空及删除位置合法时，将用户指定位置对应元素从顺序表中删除，并返回该元素。
合并按钮：
响应事件，将用户输入的两个无序表排序后进行有序合并。
合并操作不依赖于创建操作。
2.链表演示
响应事件，将用户输入转换为以->
分隔的链表输出到对应文本框。
若此时链表非空，启用查找、插入、删除按钮。
查找按钮：
响应事件，从链表中查找用户输入元素。
查找成功时，返回元素位置；
查找失败时，给出提示信息。
插入按钮：
响应事件，在链表非空及插入位置合法时，在链表中指定位置插入指定元素。
响应事件，在链表非空及删除位置合法时，删除链表中指定位置元素，并返回被删除元素。
3.KMP演示
输入按钮：
响应事件，获取用户主串及模式串数据输入。
当模式串非空时，启用求NEXT、求NEXTVAL按钮；
当模式串及主串均非空时，启用匹配按钮。
求NEXT按钮：
响应事件，求取KMP算法中模式串各元素的next值。
匹配按钮：
响应事件，根据KMP算法，对主串及模式串进行匹配操作。
求NEXTVAL按钮：
响应事件，求取KMP改进算法中模式串各元素的nextval值。
4.窗口关闭按钮
无演示操作时，单击关闭按钮，关闭当前对话框并返回上级对话框或退出演示程序；
演示操作进行过程中，关闭按钮禁用，防止意外程序终止发生。
第3章
详细设计
一、数据类型
1.顺序表
CStringm_CurrSq;
//当前顺序表各元素以空格分隔
intm_CurrLength;
//当前顺序表表长
intm_CurrSize;
//当前顺序表容量
intm_InsertPos;
//元素插入位置
CStringm_InsertValue;
//待插入元素
CStringm_OpValue;
//当前操作元素
intm_OpPos;
//当前操作位置
intm_DeletePos;
//删除元素位置
CStringm_DeleteValue;
//删除元素值
CStringm_StringA;
//待排序原始表A
CStringm_StringB;
//待排序原始表B
CStringm_SortedA;
//已排序有序表A
CStringm_SortedB;
//已排序有序表B
CStringm_SortedC;
//排序后合并表C
intm_PosA;
//当前有序A操作元素位置
intm_PosB;
//当前有序表B操作元素位置
CStringm_ValueA;
//当前有序表A操作元素
CStringm_ValueB;
//当前有序表B操作元素
2.链表
CStringm_CreateList;
//创建操作中原始链表
//当前表长不含头结点
CStringm_CurrList;
//当前链表以->
分隔
//当前操作元素原始位置
CStringm_ListA;
//待排序原始链表A
CStringm_ListB;
//待排序链表B
//合并后链表C->
//已排序链表A
//已排序链表B
//当前操作中链表A元素位置
//当前操作中链表B元素位置
//当前操作中链表A元素值
//当前操作中链表B元素值
//待删除元素位置
//待删除元素值
CStringm_FindValue;
//待查找元素
intm_FindPos;
//待查找元素所以位置-1为元素不存在
//元素待插入位置
3.KMP
CStringm_S;
//原始输入主串无空格分隔
CStringm_T;
//原始输入子串无空格分隔
CStringm_IndexS;
//模式匹配过程中主串S以空格分隔操作字符以（）标识
CStringm_IndexT;
//模式匹配过程中子串T以空格分隔操作字符以（）标识
CStringm_NextT1;
//求next过程中模式串T1
CStringm_NextT2;
//求next过程中模式串T2
CStringm_Next;
//模式串的next值
CStringm_NextvalT1;
//求nextval操作中模式串T1
CStringm_NextvalT2;
//求nextval操作中模式串T2
CStringm_Nextval;
//求nextval操作中nextval值
二、相关函数
afx_msgvoidOnSqCreateButton（）;
//响应创建按钮事件
afx_msgvoidOnSqInsertButton（）;
//响应插入按钮事件
afx_msgvoidOnSqDeleteButton（）;
//响应删除按钮事件
afx_msgvoidOnSqMergeButton（）;
//响应合并按钮事件
afx_msgLRESULTOnSqUpdate（WPARAMwParameter,LPARAMlpParameter）;
//响应对话框数据更新
afx_msgvoidOnListCreateButton（）;
//响应创建按键事件
afx_msgvoidOnListFindButton（）;
//响应查找按钮事件
afx_msgvoidOnListInsertButton（）;
afx_msgvoidOnListDeleteButton（）;
afx_msgvoidOnListMergeButton（）;
afx_msgLRESULTOnListUpdate（WPARAMwParameter,LPARAMlpParameter）;
//响应对话框数据更新
afx_msgvoidOnKmpInputButton（）;
//响应数据输入事件
afx_msgvoidOnKmpIndexButton（）;
//响应模式匹配事件
afx_msgvoidOnKmpNextButton（）;
//响应求Next值事件
afx_msgvoidOnKmpNextvalButton（）;
//响应求Nextval事件
afx_msgLRESULTOnKmpUpdate（WPARAMwParameter,LPARAMlpParameter）;
4.线程处理
UINTsqDlgCreate（LPVOIDlpParam）;
//顺序表创建
UINTsqDlgInsert（LPVOIDlpParam）;
//顺序表插入
UINTsqDlgDelete（LPVOIDlpParam）;
//顺序表删除
UINTsqDlgMerge（LPVOIDlpParam）;
//顺序表合并
UINTlistDlgCreate（LPVOIDlpParam）;
//链表创建
UINTlistDlgFind（LPVOIDlpParam）;
//链表查找
UINTlistDlgInsert（LPVOIDlpParam）;
//链表插入
UINTlistDlgDelete（LPVOIDlpParam）;
//链表删除
UINTlistDlgMerge（LPVOIDlpParam）;
//链表合并
UINTkmpDlgIndex（LPVOIDlpParam）;
//模式匹配
UINTkmpDlgNext（LPVOIDlpParam）;
//求Next值
UINTkmpDlgNextval（LPVOIDlpParam）;
//求Nextval值
5.其它函数
voidGetNext（CKmpDialog*pDlg,intnext[]）;
//求Next用于模式匹配
三、详细流程
四、重要算法
算法1.1
//顺序表创建线程函数
UINTsqDlgCreate（LPVOIDlpParam）
CSqDialog*pDlg=（CSqDialog*）lpParam;
//更新过程中禁用相关按钮及系统菜单关闭按钮
…………
for（inti=0;
i<
pDlg->
m_CreateSq.GetLength（）;
++i）
{
pDlg->
m_OpPos=i;
m_CurrSq+=pDlg->
m_CreateSq.GetAt（i）;
m_OpValue.SetAt（0,pDlg->
m_CreateSq.GetAt（i））;
m_CurrSq+=_T（"
"
）;
++（pDlg->
m_CurrLength）;
if（pDlg->
m_CurrSize<
=pDlg->
m_CurrLength）
pDlg->
m_CurrSize*=2;
//增加容量到原容量2倍
Sleep（1000）;
//发送消息给主线程更新对话框
SendMessage（WM_USER+1,NULL,NULL）;
}
//重新启用创建按钮及系统菜单关闭按钮
//若顺序表不为空启用相关控件
if（0!
（pDlg->
GetDlgItem（IDC_SQ_INSERT_BUTTON））->
EnableWindow（TRUE）;
GetDlgItem（IDC_SQ_DELETE_BUTTON））->
return0;
算法1.2
//顺序表插入线程函数
UINTsqDlgInsert（LPVOIDlpParam）
if（pDlg->
m_InsertValue.IsEmpty（））
MessageBox（NULL,_T（"
不能插入空元素！
"
）,_T（"
插入元素非法"
）,MB_OK）;
return0;
m_InsertPos>
请输入正确的插入位置！
插入位置越界"
//更新过程中禁用相关按钮及系统菜单关闭按钮
…………
++（pDlg->
//元素长度加1
//给显示串增加两个空字符
for（inti=pDlg->
m_CurrLength-1;
i>
m_InsertPos;
--i）
if（1==i）
{//当i为1时保留紧接元素0的空格
m_CurrSq.SetAt（2,pDlg->
m_CurrSq.GetAt（0））;
}
else
{
m_CurrSq.SetAt（2*i,pDlg->
m_CurrSq.GetAt（2*i-2））;
m_CurrSq.SetAt（2*i-1,pDlg->
m_CurrSq.GetAt（2*i-3））;
}
//插入元素
m_OpPos=pDlg->
m_CurrSq.SetAt（2*pDlg->
m_InsertPos,pDlg->
m_InsertValue.GetAt（0））;
Sleep（1000）;
//重新启用相关按钮及系统菜单关闭按钮
算法1.3
//顺序表删除线程函数
UINTsqDlgDelete（LPVOIDlpParam）
m_DeletePos>
m_CurrLength-1）
请输入正确的删除位置！
删除位置越界"
//获取待删除元素
m_DeleteValue.SetAt（0,pDlg->
m_CurrSq.GetAt（2*pDlg->
m_DeletePos））;
//删除前顺序表只有一个元素
if（1==pDlg->
m_OpPos=0;
m_CurrLength=0;
m_CurrSq=_T（"
//清空顺序表
//删除成功后顺序表空只启用创建按钮和合并按钮
GetDlgItem（IDC_SQ_CREATE_BUTTON））->
GetDlgItem（IDC_SQ_MERGE_BUTTON））->
EnableMenuItem（hSysMenu,nCloseItemID,MF_ENABLED）;
m_DeletePos;
if（0==i）
m_CurrSq.SetAt（0,pDlg->
m_CurrSq.GetAt
（2））;
m_CurrSq.GetAt（2*i+2））;
m_CurrSq.SetAt（2*i+1,pDlg->
m_CurrSq.GetAt（2*i+3））;
m_CurrSq.Delete（pDlg->
m_CurrSq.GetLength（）-2,2）;
--（pDlg->
//重新启用相关按钮及系统菜单关闭按钮
算法1.4
//顺序表合并线程函数
UINTsqDlgMerge（LPVOIDlpParam）
intpa=0;
intpb=0;
intpc=0;
//m_SortedAm_SortedB含空格分隔符长度判断时应忽略
while（pa<
m_StringA.GetLength（）&
&
pb<
m_StringB.GetLength（））
m_SortedA.GetAt（2*pa）<
m_SortedB.GetAt（2*pb））
m_SortedC+=pDlg->
m_SortedA.GetAt（2*pa）;
m_SortedC+=_T（"
m_OpPos=pc;
m_OpValue=pDlg->
m_PosA=pa;
m_ValueA=pDlg->
++pa;
++pc;
m_SortedB.GetAt（2*pb）;
m_CurrSq
升级会员 