顺序表、链表、KMP算法-数据结构报告
- 格式：doc
- 大小：381.50 KB
- 文档页数：40
目录
需求分析-------------------------------------------------P3
概要设计-------------------------------------------------P4
详细设计-------------------------------------------------P9
调试分析-------------------------------------------------P11
测试结果-------------------------------------------------P11
课程设计总结---------------------------------------------P15
参考文献-------------------------------------------------P16
附录------------------------------------------------------P16
一：需求分析：
顺序表的插入、删除、合并等操作：涉及顺序表的创建、插入、删除、查找、合并、显示等。采用数组作为顺序表的结构，定义一个MAXSIZE作为数组的最大长度。从键盘接收用户输入的基本数据类型（这里以char为例，也可以是int等其他类型）为例演示方便，系统自带一个已经含有元素的顺序表。然后接收用户输入指令进行相应的操作。插入演示时，要求用户输入插入的字符串和要插入的位置；删除演示时要求用户输入要删除的长度和起始位置；合并操作演示时，要求用户输入一个字符串用来建立新的顺序表，然后两个顺序表合并并输出新的顺序表。
链表的查找、删除、计数、输出等功能以及有序链表的合并：涉及链表的创建、删除、查找、合并、显示等。需要动态分配内存，用指针连接各节点。先自定义一个ListNode节点用户存储数据和指针。为了演示方便，系统依然自带了一个创建好并且含有若干元素的链表，用户可以在此基础上进行操作。查找操作时，要求用户输入查找的字符，然后输出查找结果；插入操作时，要求用户输入要插入的字符以及要插入的位置；删除演示时要求用户输入要删除的长度和起始位置；合并操作演示时，要求用户输入一个字符串用来建立新的链表，然后两个顺序表合并并输出新的顺序表。
串的模式匹配：为了演示方便，系统依然自带了一个创建好并且含有若干元素的主串，然后接受用户输入的模式串。求出该模式串的next[]和nextval[]，再由此验证模式串在主串中的匹配情况。 二：概要设计：
本程序中用到的所有抽象数据类型的定义如下。
1、顺序表
ADT SqList
{
数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}
数据关系：R1={|ai-1,ai∈D,i=2,…,n}
基本操作：
InitList_Sq(&L)
操作结果：构造一个空的顺序表。
Create_Sq(&L)
初始条件：空顺序表L已经构造。
操作结果：在L中存放数据元素，创建顺序表L。
ListInsert_Sq&L,I,e)
初始条件：顺序表L存在，并且1<=i<=ListLength(L)+1。
操作结果：在L中的第i个位置之前插入新的数据元素e，L的表长加1。
Show_Sq(L)
初始条件：存在非空顺序表L。
操作结果：输出显示顺序表L。
MergeList_Sq(La, Lb, &Lc)
初始条件：存在顺序表La,Lb，Lc。
操作结果：把LaLb合并为Lc。 DeSameElem_Sq(&L)
初始条件：存在非空顺序表L。
操作结果：剔除L中的相同元素。
Sort_Sq(&L)
初始条件：存在非空顺序表L。
操作结果：//对顺序表L按非递减顺序排序。
ListDelete_Sq(&L, i)
初始条件：存在顺序表L非空，1<=i<=ListLength(L)。
操作结果：在顺序表L中删除第i个元素，并用显示其值e
}ADT SqList
2、链表
ADT LinkList
{
数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}
数据关系：R1={|ai-1,ai∈D,i=2,…,n}
基本操作：
InitList_L(& L)
操作结果：构造一个空的链表
CreateList_f(void)
初始条件：存在空的链表L。 操作结果：头插入法实现链表的创建,并且返回头结点给L。
CreateList_r(void)
初始条件：存在空的链表L。
操作结果：尾插入法实现链表的创建,并且返回头结点给L。
LocateElem_L(L, &e)
初始条件：存在空的链表L。
操作结果：查询L第一个与e相等的数据元素，若存在，则返回它的位序，否则返回 0。
NumberElem_L(L)
初始条件：存在链表L。
操作结果：计算并返回L数据元素的个数。
Show_L(L)
初始条件：存在非空链表L。
操作结果：输出显示链表L。
ListDelete_L(&L, i)
初始条件：存在链表L非空，1<=i<=ListLength(L)。
操作结果：在顺序链表L中删除第i个元素，返回其值。
DeSameElem_L(&L)
初始条件：存在非空顺序表L。
操作结果：剔除L中的相同元素。
MergeList_L(La, Lb, &Lc)
初始条件：存在链表La,Lb，Lc。
操作结果：把La，Lb合并为Lc。 SortList_L(&L)
初始条件：存在非空链表L。
操作结果：将L按非递减顺序排序。
ListInsert(&L,i,e)
初始条件：链表L存在非空，并且1<=i<=ListLength(L)+1。
操作结果：在L中的第i个位置之前插入新的数据元素e。
}ADT LinkList
3、串
ADT HString
{
数据对象：D={ai|ai∈CharacterSet,i=1,2,…,n,n>=0}
数据关系：R1={|ai-1,ai∈D,i=2,…,n}
基本操作：
InitStr(&S)
操作结果：构造一个空串
CreateStr(&S,ch)
初始条件：ch是字符串常量。串S已经构造。
操作结果：生成一个其值等于ch 的串S。
ShowStr(S)
初始条件：存在非空串S。 操作结果：输出显示串S。
Index_KMP(S, T, pos, nextval[])
初始条件：串S和T存在，T是非空串，1<=pos<=SteLength(L),nextval是next修正值。
操作结果：若主串S中存在和串T相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；若不则函数值为0。
get_next(S, next[])
初始条件：串S存在且非空。
操作结果：求串S的next值。
get_nextval(S, nextval[])
初始条件：串T存在且非非空。
操作结果：求串S的nextval值。
}ADT HString
三：详细设计
#define MAXSIZE 100
typedef struct node
{
char data;//数据域
struct node *next; //指针域
}ListNode;//ListNode数据结构的定义
void PrintMenu();//打印菜单
void Demo1();//演示一
void Demo1Menu();//演示一的目录
int myinsert(char* s,char* t,int pos);//插入
int mydelete(char* s,int len,int pos);//删除
int mycombine(char* t1,char*t2,char* s);//合并
int mycut(char* s,char* temp,int len,int pos);//顺序表切割
void Demo2();//演示二
void Demo2Menu(); //演示二的菜单
ListNode* CreateList();//只创建一个空链表，返回表头
void Insert(ListNode* head,char data,int pos);//插入一个元素 void Append(ListNode* head,char data); //尾部追加一个元素
int Search(ListNode* head,char data);//某个元素是否在链表中,返回所在位置index
void DeleteByValue(ListNode* head,char data);//依据元素值删除元素
void DeleteByPos(ListNode* head,int pos);//依据元素索引删除元素
int ListLen(ListNode* head);//求链表长度
void DisplayList(ListNode* head);//打印链表
void ListCombine(ListNode *heada,ListNode *headb);
//合并链表,返回合并后的链表的表头
void Demo3();//演示三
int index_KMP(char *s,char *t,int pos,int *next); //模式匹配算法
void get_next(char *t,int * next); //获取next[j]数组的函数声明
void get_nextval(char *t,int *nextal) ;//获取nextval[j]数组的函数声明
int main()
{
……
……
return 0;
}
