用单链表实现集合交并补.docVIP

课程设计(论文)任务书 软件 　学院　　软件工程　专业　2010 - 3　班 一、课程设计(论文)题目　数据结构课程设计(A)　 二、课程设计(论文)工作自 2011 年 12月 22日起至 2011 年 12月 23 日止。 三、课程设计(论文) 地点: 软件学院机房 四、课程设计(论文)内容要求： 1．本课程设计的目的 （1）使学生熟练掌握抽象数据类型的组织和定义； （2）使学生熟练掌握数据类型的定义和实现； （3）培养学生组织和分析数据的能力； （4）培养学生分析和应用基于不同数据结构的算法的能力； （5）提高学生的科技论文写作能力。 2．基本要求： 每位同学在以下题目中任选一题（在方框中打勾），独立完成课程设计： □ 集合的并交差运算：参见《数据结构题集》P80。 □ 赫夫曼编/译码器：参见《数据结构题集》P149。 □ 井字棋：参见《数据结构》教材P2。设计棋谱，当对方落子后，能从棋谱中选择一种 应对方式，并能判断胜负。 3．课程设计论文编写要求 （1）要按照书稿的规格打印誊写课设报告； （2）报告分为封面、任务书（本文档）、正文、课程设计体会和参考文献四部分； 学生签名： 2011年 12月 日 课程设计(论文)评审意见 （1）题目分析 （20分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （2）流程分析　 （30分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （3）数据定义　 （30分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （4）代码编写　 （10分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （5）创新能力　 （10分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （6）格式规范性、设计态度及考勤是否降等级：是（　）、否（　） 评阅人： 　　　 职称： 讲 师 2012年 1 月 5 日 PAGE \* MERGEFORMAT15 正 文 数据结构定义 抽象数据类型 本设计中用到的数据结构ADT定义如下： ADT List{ 数据对象：D={} 数据关系：={} 基本操作：InitList(L) 操作结果：构造一个空的线性表L； DestroyList(L) 初始条件：线性表L已存在 操作结果：销毁线性表L ClearList(L) 初始条件：线性表L已存在 操作结果：将L重置为空表 ListEmpty(L) 初始条件：线性表L已存在 操作结果：若L为空表，则返回TRUE，否则返回FALSE ListLenght(L) 初始条件：线性表L已存在 操作结果：返回L中数据元素的个数 存储结构定义 数据存储结构的C语言定义如下： typedef struct LNode//定义单链表结点类型 { ElemType data; struct LNode *next; }LinkList; 基本操作 数据结构的基本操作实现如下： DispList(LinkList *L)：输出单链表L CreatListR(LinkList *L,ElemType a[],int n)：运用尾插法建立单链表 Sort(LinkList *head)：单链表元素排序 shanchu(LinkList *head)：在进行过Sort排序之后，删除单链表里相同的元素 bing(LinkList *ha,LinkList *hb,LinkList *hc )：求两个有序集合的并 jiao(LinkList *ha,LinkList *hb,LinkList *hc)：求两个有序集合的交 cha(LinkList *ha,LinkList *hb,LinkList *hc)：求两个有序集合的差、 main()：采用尾差法建立单链表，使用Sort进行单链表排序构成有序链表，在使用shanchu函数删除相同元素和非小写字母。利用一个switch语句进行运算的选择，使用相关函数对有序链表进行交并差的相关运算 解题过程 问题分解 该问题主要应实现以下功能： 利用尾差法建立单链表 对于输入的链表进行有序排列 删除有序链表中不符合要求的元素 调