数据结构大作业封面模板

1、12级软件设计大作业题 目概念图难度系数 0.7成 绩 班 级 011213完成者1学号01121345姓名 杨英杰完成者2学 号01121278 姓 名 曹伟完成者3学号01121289姓名 赵汉卿完成日期2014.6.22（若是多人合作，填写下面的内容，给出所有合作者的信息） 姓名：杨英杰主要完成的工作：线性表、栈和队列、数组和串姓名：曹伟主要完成的工作：图、索引、散列姓名：赵汉卿主要完成的工作：树、绪论、算法设计与分析 一、软件系统名称完整线性表输出。二、软件分析与设计1、问题分析：线性表内容包含两部分，分别是字母（表示下个链表）和数字。因此链表中节点 需要包含指向下一个节点或下个链表的

2、指针等多个数据类型。系统输入：线性表名称（字母）和线性表内容（数字） 。系统输出：线性表（包括线性表名称和线性表内容）。总功能：可在原有链表基础上不断添加数字或新链表，并显示每个链表的内容及整体链表的内 容。2、测试样例在程序输入均含有提示，如果输入错误，会导致重新输入，不会直接退出程序。 输入包含：输入提示测试样例预期结果请输入需要添加的链表名称（输入END标）END退出C （已在线性表中的链表字母）显布卜个输入Sg或D或12 （任何/、是线性 表字母的输入）输入有误，请重新输入请输入数字或新链表名称（输 入end结束）end退出132 （数字）或Q （未保存在线 性表中的链表字母）显布卜个

3、输入Ass或46s （小止常输入）输入有误，请重新输入3、全局变量包括：所有链表的指针和表示链表指针数目的数字变量；用语构成队列的数组指 针和表示表示队列的两个变量front和rear。4、模块分类创建链表模块函数名称：CreateList函数参数：链表名称 name函数功能：生成链表返回值：链表头指针伪代码描述：定义头指针；分配节点空间；节点数据初始化（链表名 =name）;返回头指针初始化模块函数名称：InitList函数参数：无函数功能：链表初始化返回值：无伪代码描述：在链表中原有链表中插入数字和链表；新链表的插入数字和链表；插入链表模块函数名称：AtLast函数参数：链表头指针函数功能

4、：寻找链表中最后指针返回值：最后指针伪代码描述：While （下一个节点指针不空） 指向下一个节点指针返回函数名称：InsertNumber函数参数：链表头指针，数字函数功能：链表中插入数字返回值：新节点指针伪代码描述：寻找最后指针；分配节点空间；节点数据初始化；链表与节点链接返回节点指针函数名称：InsertList函数参数：链表头指针，要插入链表头指针函数功能：链表中插入指针返回值：新链表头指针伪代码描述：寻找最后指针；分配节点空间；节点数据初始化原链表与节点连接节点与要插入链表头指针链接返回节点指针数组队列模块函数名称：Qinit函数参数：无函数功能：队列初始化返回值：无伪代码描述：fr

5、ont=rear=0函数名称：push函数参数：指针函数功能：入队列返回值：无伪代码描述：指针进入数组front+函数名称函数参数pop无出队列函数功能： 返回值：无 伪代码描述:rear+函数名称：top函数参数：指针函数功能：返回队列头指针返回值：队列头指针伪代码描述：返回队列头指针函数名称：empty函数参数：无函数功能：判断队列是否空返回值：bool变量伪代码描述：队列空；返回true;Else 返回 false删除模块函数名称：DeleteList函数参数：链表头指针函数功能：释放线性表空间返回值：无伪代码描述：队列初始化；头指针入队列While （队列不空）出队列并存储队首值指向下

6、一个节点If （节点为数字）释放空间、else指针入队列并释放空间显示模块函数名称：Show函数参数：无函数功能：输出只有数值的完整线性表返回值：无伪代码描述：显示线性表字母输出函数换行函数名称：ShowL函数参数：指针函数功能：输出链表内容返回值：无伪代码描述：指向下一个节点If （节点为数字）输出数字else递归调用函数，传递此节点指针函数名称：ShowList函数参数：指针函数功能：输出线性表内容返回值：无伪代码描述：队列初始化；头指针入队列While （队列不空）出队列并存储队首值显示链表头字母指向下一个节点If （节点为链表节点）显示链表头字母和，入队列else显示数字和，输入模块函

7、数名称：NoCreate函数参数：链表名称 name函数功能：判断队列是否存在于线性表返回值：bool量伪代码描述：数组中依次寻找If 找到 false无 返回true函数名称：Input函数参数：无函数功能：输入处理返回值：无伪代码描述：ShowList输出提示输入（为字符串）While （输入不结束）5、流程图MainIf （输入合理（为单一字母且已存在线性表）找到线性表中的该链表输出提示输入（为字符串）While （输入不结束）If （输入为新单一字母）新建链表并插入，并存储如全局数组中Else if （为数字）字符串转化为数字并加入原链表中Else提示输入错误提示并重新输入Else提示

8、输入错误 提示并重新输入创建链表初始化部分输入链表完成输入完成显示线性表显示只有数值的完整线性表三、运行环境codeblocks （建议编译器为 gcc）。四、软件使用说明软件系统输入以输出和异常处理均在上述表格中得到。五、源代码#include#include#include#includeusing namespace std;typedef struct nodebool isList;int number;node *nextNumber,*nextList;char listName;List;typedef struct nodehchar name;List *head;HLis

9、t;HList ListHead100;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

10、();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

11、=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) hea

12、d1=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)/A链表初始化InsertNumber(head,1);InsertNumber(head,2);InsertNumber(head,3);InsertNum

13、ber(head,4);InsertNumber(head,5);List *head1=CreateList(B);InsertList(head,head1);/B链表初始化InsertNumber(head1,7);InsertNumber(head1,8);InsertNumber(head1,9);List *head2=CreateList(C);InsertList(head1,head2);/C链表初始化InsertNumber(head2,10);存储所有链表头指针ListHead0.head=head;ListHead1.head=head1;ListHead2.head=

14、head2;ListH=A;ListH=B;ListH=C;Nlisthead=3;队列定义及所有操作const int MAXQ=10000;List * ListQueueMAXQ;int front,rear;初始化(队列清空)void Qinit()front=rear=0;/入队列void push(List *head)if(frontMAXQ)ListQueuefront+=head;出队列void pop()rear+;/返回队首元素List *top()if(rear,temp-listName);temp=temp-ne

15、xtNumber;while(temp)if(temp-isList)printf(%c,temp-listName); push(temp-nextList);if(temp-nextNumber)printf(,);elseprintf(%d,temp-number);if(temp-nextNumber) printf(,);temp=temp-nextNumber;printf(n);判断一个链表名称是否已被创建bool NoCreate(char name)for(int i=0;i=A&temp10=Z&!temp11)for(int i=0;i=A&temp20=0&temp2jnextNumber;while(templ)if(temp1-isList)push(temp1-nextList);temp2=temp1-nextNumber; free(templ);temp1=temp2;void ShowL(List *head)List *temp=head-nextNumber;while(temp)if(temp-isList)Sho