数据结构大作业封面模板

12级 软件设计大作业

题 目 概念图

难度系数 0.7 成 绩 班 级 011213 完成者1学 号 01121345 姓 名 杨英杰 完成者2学 号 01121278 姓 名 曹伟 完成者3学 号 01121289 姓 名 赵汉卿

完成日期 2014.6.22 （若是多人合作，填写下面的内容，给出所有合作者的信息） 姓名：杨英杰 主要完成的工作：线性表、栈和队列、数组和串

姓名：曹伟 主要完成的工作：图、索引、散列

姓名：赵汉卿 主要完成的工作：树、绪论、算法设计与分析 一、软件系统名称 完整线性表输出。 二、软件分析与设计 1、问题分析：线性表内容包含两部分，分别是字母（表示下个链表）和数字。因此链表中节点需要包含指向下一个节点或下个链表的指针等多个数据类型。 系统输入：线性表名称（字母）和线性表内容（数字）。 系统输出：线性表（包括线性表名称和线性表内容）。 总功能：可在原有链表基础上不断添加数字或新链表，并显示每个链表的内容及整体链表的内容。 2、测试样例 在程序输入均含有提示，如果输入错误，会导致重新输入，不会直接退出程序。 输入包含： 输入提示 测试样例 预期结果 请输入需要添加的链表名称(输入END结束) END 退出 C（已在线性表中的链表字母） 显示下个输入 Sg或D或12（任何不是线性表字母的输入） 输入有误，请重新输入

请输入数字或新链表名称(输入end结束) end 退出 132（数字）或Q（未保存在线性表中的链表字母） 显示下个输入 Ass或46s（不正常输入） 输入有误，请重新输入

3、全局变量包括：所有链表的指针和表示链表指针数目的数字变量；用语构成队列的数组指针和表示表示队列的两个变量front和rear。 4、模块分类 创建链表模块 函数名称：CreateList 函数参数：链表名称name 函数功能： 生成链表 返回值：链表头指针 伪代码描述： 定义头指针； 分配节点空间； 节点数据初始化（链表名=name）； 返回头指针 初始化模块 函数名称：InitList 函数参数：无 函数功能：链表初始化 返回值： 无 伪代码描述： 在链表中原有链表中插入数字和链表； 新链表的插入数字和链表； 插入链表模块 函数名称：AtLast 函数参数：链表头指针 函数功能： 寻找链表中最后指针 返回值：最后指针 伪代码描述： While（下一个节点指针不空） 指向下一个节点指针 返回 函数名称：InsertNumber 函数参数：链表头指针，数字 函数功能： 链表中插入数字 返回值：新节点指针 伪代码描述： 寻找最后指针； 分配节点空间； 节点数据初始化； 链表与节点链接 返回节点指针 函数名称：InsertList 函数参数：链表头指针，要插入链表头指针 函数功能： 链表中插入指针 返回值：新链表头指针 伪代码描述： 寻找最后指针； 分配节点空间； 节点数据初始化 原链表与节点连接 节点与要插入链表头指针链接 返回节点指针 数组队列模块 函数名称：Qinit 函数参数：无 函数功能： 队列初始化 返回值：无 伪代码描述： front=rear=0 函数名称：push 函数参数：指针 函数功能： 入队列 返回值：无 伪代码描述： 指针进入数组 front++ 函数名称：pop 函数参数：无 函数功能： 出队列 返回值：无 伪代码描述： rear++ 函数名称：top 函数参数：指针 函数功能： 返回队列头指针 返回值：队列头指针 伪代码描述： 返回队列头指针 函数名称：empty 函数参数：无 函数功能： 判断队列是否空 返回值：bool变量 伪代码描述： 队列空；返回true； Else 返回false 删除模块 函数名称：DeleteList 函数参数：链表头指针 函数功能： 释放线性表空间 返回值：无 伪代码描述： 队列初始化； 头指针入队列 While（队列不空） 出队列并存储队首值 指向下一个节点 If（节点为数字） 释放空间、 else 指针入队列并释放空间 显示模块 函数名称：Show 函数参数：无 函数功能： 输出只有数值的完整线性表 返回值：无 伪代码描述： 显示线性表字母 输出函数 换行 函数名称：ShowL 函数参数：指针 函数功能： 输出链表内容 返回值：无 伪代码描述： 指向下一个节点 If（节点为数字） 输出数字 else 递归调用函数，传递此节点指针 函数名称：ShowList 函数参数：指针 函数功能： 输出线性表内容 返回值：无 伪代码描述： 队列初始化； 头指针入队列 While（队列不空） 出队列并存储队首值 显示链表头字母 指向下一个节点 If（节点为链表节点） 显示链表头字母和‘，’ 入队列 else 显示数字和‘，’ 输入模块 函数名称：NoCreate 函数参数：链表名称name 函数功能： 判断队列是否存在于线性表 返回值：bool量 伪代码描述： 数组中依次寻找 If找到 false 无 返回true 函数名称：Input 函数参数：无 函数功能： 输入处理 返回值：无 伪代码描述： ShowList 输出提示 输入（为字符串） While（输入不结束） { If（输入合理（为单一字母且已存在线性表）） { 找到线性表中的该链表 输出提示 输入（为字符串） While（输入不结束） { If（输入为新单一字母） 新建链表并插入，并存储如全局数组中 Else if（为数字） 字符串转化为数字并加入原链表中 Else 提示输入错误 提示并重新输入 } } Else 提示输入错误 提示并重新输入 }

5、流程图

三、运行环境 codeblocks（建议编译器为gcc）。 四、软件使用说明 软件系统输入以输出和异常处理均在上述表格中得到。 五、源代码

Main 创建链表 初始化 输入 显示线性表 删除

部分输入链表完成 输入完成 显示只有数值的完整线性表 #include #include #include #include

using namespace std; typedef struct node { bool isList; int number; node *nextNumber,*nextList; char listName; }List;

typedef struct nodeh { char name; List *head; }HList; HList ListHead[100]; int Nlisthead=0;

List *CreateList(char name); List *AtLast(List *head); List *InsertNumber(List *head,int number); List *InsertList(List *head1,List *head2); void InitList(List *head); void ShowList(List *head); void DeleteList(List *head); void Input(); bool NoCreate(char name); void Show();

int main() { List *head=CreateList('A'); InitList(head); Input(); Show(); DeleteList(head); return 0; } List *CreateList(char name) { List *head; head=(List *)malloc(sizeof(List)); head->listName=name; head->isList=true; head->nextNumber=head->nextList=NULL; return head; }

List *AtLast(List *head) { while(head->nextNumber) head=head->nextNumber; return head; }

List *InsertNumber(List *head,int number) { head=AtLast(head); List *newNode=(List *)malloc(sizeof(List)); newNode->isList=false; newNode->number=number; newNode->nextList=newNode->nextNumber=NULL; head->nextNumber=newNode; return newNode; }

List *InsertList(List *head1,List *head2) { head1=AtLast(head1); List *newNode=(List *)malloc(sizeof(List)); newNode->isList=true; newNode->listName=head2->listName; newNode->nextNumber=NULL; newNode->nextList=head2; head1->nextNumber=newNode; return head2; }

void InitList(List *head)