《数据结构大作业封面.pdf》由会员分享，可在线阅读，更多相关《数据结构大作业封面.pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、12 级软件设计大作业题目概念图难度系数0.7成绩班级011213完成者 1 学号 01121345姓名杨英杰完成者 2 学号 01121278姓名曹伟完成者 3 学号 01121289姓名赵汉卿完成日期2014.6.22（若是多人合作，填写下面的内容，给出所有合作者的信息）姓名：杨英杰主要完成的工作：线性表、栈和队列、数组和串姓名：曹伟主要完成的工作：图、索引、散列姓名：赵汉卿主要完成的工作：树、绪论、算法设计与分析一、软件系统名称完整线性表输出。二、软件分析与设计1、问题分析：线性表内容包含两部分，分别是字母（表示下个链表）和数字。因此链表中节点需要包含指向下一个节点或下个链表的指针等多个
2、数据类型。系统输入：线性表名称（字母）和线性表内容（数字）。系统输出：线性表（包括线性表名称和线性表内容）。总功能：可在原有链表基础上不断添加数字或新链表，并显示每个链表的内容及整体链表的内容。2、测试样例在程序输入均含有提示，如果输入错误，会导致重新输入，不会直接退出程序。输入包含：输入提示请输入需要添加的链表名称(输入 END 结束)测试样例ENDSg 或 D 或 12（任何不是线性表字母的输入）请输入数字或新链表名称(输入 end 结束)end132（数字）或 Q（未保存在线性表中的链表字母）Ass 或 46s（不正常输入）预期结果退出输入有误，请重新输入退出显示下个输入输入有误，请重新
3、输入C（已在线性表中的链表字母）显示下个输入3、全局变量包括：所有链表的指针和表示链表指针数目的数字变量；用语构成队列的数组指针和表示表示队列的两个变量front 和 rear。4、模块分类创建链表模块函数名称：CreateList函数参数：链表名称 name函数功能：生成链表返回值：链表头指针伪代码描述：定义头指针；分配节点空间；节点数据初始化（链表名=name）；返回头指针初始化模块函数名称：InitList函数参数：无函数功能：链表初始化返回值：无伪代码描述：在链表中原有链表中插入数字和链表；新链表的插入数字和链表；插入链表模块函数名称：AtLast函数参数：链表头指针函数功能：寻找链表
4、中最后指针返回值：最后指针伪代码描述：While（下一个节点指针不空）指向下一个节点指针返回函数名称：InsertNumber函数参数：链表头指针，数字函数功能：链表中插入数字返回值：新节点指针伪代码描述：寻找最后指针；分配节点空间；节点数据初始化；链表与节点链接返回节点指针函数名称：InsertList函数参数：链表头指针，要插入链表头指针函数功能：链表中插入指针返回值：新链表头指针伪代码描述：寻找最后指针；分配节点空间；节点数据初始化原链表与节点连接节点与要插入链表头指针链接返回节点指针数组队列模块函数名称：Qinit函数参数：无函数功能：队列初始化返回值：无伪代码描述：front=rea
5、r=0函数名称：push函数参数：指针函数功能：入队列返回值：无伪代码描述：指针进入数组front+函数名称：pop函数参数：无函数功能：出队列返回值：无伪代码描述：rear+函数名称：top函数参数：指针函数功能：返回队列头指针返回值：队列头指针伪代码描述：返回队列头指针函数名称：empty函数参数：无函数功能：判断队列是否空返回值：bool 变量伪代码描述：队列空；返回 true；Else 返回 false删除模块函数名称：DeleteList函数参数：链表头指针函数功能：释放线性表空间返回值：无伪代码描述：队列初始化；头指针入队列While（队列不空）出队列并存储队首值指向下一个节点If
6、（节点为数字）释放空间、else指针入队列并释放空间显示模块函数名称：Show函数参数：无函数功能：输出只有数值的完整线性表返回值：无伪代码描述：显示线性表字母输出函数换行函数名称：ShowL函数参数：指针函数功能：输出链表内容返回值：无伪代码描述：指向下一个节点If（节点为数字）输出数字else递归调用函数，传递此节点指针函数名称：ShowList函数参数：指针函数功能：输出线性表内容返回值：无伪代码描述：队列初始化；头指针入队列While（队列不空）出队列并存储队首值显示链表头字母指向下一个节点If（节点为链表节点）显示链表头字母和，入队列else显示数字和，输入模块函数名称：NoCrea
7、te函数参数：链表名称 name函数功能：判断队列是否存在于线性表返回值：bool 量伪代码描述：数组中依次寻找If 找到false无返回 true函数名称：Input函数参数：无函数功能：输入处理返回值：无伪代码描述：ShowList输出提示输入（为字符串）While（输入不结束）If（输入合理（为单一字母且已存在线性表）找到线性表中的该链表输出提示输入（为字符串）While（输入不结束）If（输入为新单一字母）新建链表并插入，并存储如全局数组中Else if（为数字）字符串转化为数字并加入原链表中Else提示输入错误提示并重新输入Else提示输入错误提示并重新输入5、流程图创建链表初始化M
8、ain部分输入链表完成输入输入完成显示线性表删除显示只有数值的完整线性表三、运行环境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;HList;HList ListHea
9、d100;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=Cre
10、ateList(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*
11、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(
12、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);InsertNumber(head,4);InsertNumber(head,5);List*head1=Cr
13、eateList(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=head2;ListHead0.name=A;ListHead1.name=B;ListH
14、ead2.name=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-nextNumber;while(temp)if(temp-isList)printf(%c,t
15、emp-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(temp1)if(temp1-isList)push(tem
16、p1-nextList);temp2=temp1-nextNumber;free(temp1);temp1=temp2;void ShowL(List*head)List*temp=head-nextNumber;while(temp)if(temp-isList)ShowL(temp-nextList);elseprintf(%d,temp-number);temp=temp-nextNumber;void Show()List*head=ListHead0.head;printf(%c-,ListHead0.name);ShowL(head);puts();六、测试七、对算法的时间效率进行分析在程序中，队列操作时间复杂度均为 O（1），而线性表的基本操作：删除，显示，检查，查找链表的时间复杂度均为O（n）。八、收获、体会、对课程的意见或建议。