数据结构课程设计

news/2024/11/24 12:00:13/

数据结构课程设计

文章目录

  • 数据结构课程设计
    • 1.1问题描述
    • 1.2需求分析
    • 1.3概要设计
    • 1.4详细设计
    • 1.5调试分析
    • 1.6测试结果
    • 1.7参考文献
    • 1.8源码

1.1问题描述

编制一个能演示执行集合的交、并和差运算的程序。

要求：

  1. 集合元素用小写英文字母，执行各种操作应以对话方式执行。

  2. 算法要点：利用单链表表示集合；理解好三种运算的含义

1.2需求分析

分析：

输入：输入应该具有判断是否为小写字母的功能，如果不是小写字母，应该舍去，同时打印有效输入给用户看，用来检查输入。并且应该去除用户输入的重复元素，满足集合的互异性。并且能处理好空集的问题。

结果：实现与用户的交互功能并且能输出集合的交、并和差运算的结果。对于无效输入，也要处理。

1.3概要设计

数据类型：

采用的数据类型是单链表，单链表用来储存元素，方便后面的插入操作，具体实现如下所示：

	/*链表*/  typedef struct LNode{  ElemType data;  struct LNode * next;  }LinkNode;

流程：

主程序主要就是通过用户输入来判断执行哪些操作，首先是输入操作，既要避免无效输入（非小写字母），还要去重，最后还要将有效输入打印出来。

当输入为i（Intersection）的时候，调用Intersection()函数求交集，当输入为u（Union）的时候，调用Union()函数求并集，当输入为d（Difference）的时候，调用Difference()函数求差集，本次是将A – B输出，并且输出B – A。当输入为 q 时，程序结束。而当输入是无效输入的时候，也会提醒用户。

1.4详细设计

主函数伪代码：

	int main() {  定义3个链表；    初始化链表;  // InitList();   输入集合元素;   //Input();  输出有效集合元素;   //DispList()；  while (flag)  {  打印功能菜单;   //menu();  switch (选择) {  case 'q':  flag  <- 0;  break;  case 'i':  求交集;   //Intersection(L1, L2, L3);  break;  case 'u':  求并集;   //Union (L1, L2, L3);  break;  case 'd':  求差集;   //Difference(L1, L2, L3);  break;  default:  处理无效输入;  continue;  }  }  结束;   //return 0;  }

主函数流程图：

在这里插入图片描述

交集伪代码：

	//交集  void Intersection(L1, L2, L3) {  while (L1不为空) {  while (L2不为空) {  if (L1元素等于L2)  break;  else  L2指向下一个元素;  }  if (找到相同元素) {  插入L3 ;   }  L1指向下一个元素;  }  }

交集流程图：

在这里插入图片描述

并集伪代码：

	//并集  void Union (L1, L2, L3) {  // 直接将L1赋给L3   L3 = L1;   //对L2插入L3中  while (L2 -> next != NULL) {  if (L3没有这个元素) {   将这个元素插入L3 ;   }  L2指向下一个元素;}  }

并集流程图：

在这里插入图片描述

差集伪代码：

1.	//差集  
2.	void Difference(L1, L2, L3) {  
3.	     while (L1不为空) {    
4.	            while (L2不为空) {    
5.	                if (L1元素等于L2)    
6.	                    break;    
7.	                else    
8.	                    L2指向下一个元素;    
9.	            }    
10.	            if (找到不同元素) {    
11.	                插入L3 ;     
12.	            }    
13.	        L1指向下一个元素;    
14.	        }    
15.	}

差集流程图：
在这里插入图片描述

1.5调试分析

调试过程中也是遇到一些问题的，首先就是单个功能测试正常，然后多次测试就失败了，然后一直在找具体原因，最后还是在删除L3链表的时候出了问题，因为自己的疏忽，不小心把L3链表全删了，导致第二次执行的时候，是找不到L3链表的，导致程序异常终止，后来经过修改，也是解决了这个问题。

以及对于输入，一开始觉得太复杂，就没有做去重操作，后来发现这样对于后面的操作带来了极大的不便，就将其修改为了去重。

对于算法复杂度，输入，交集，并集都是O(nm)的复杂度，目前没有什么好的优化方法，不过如果是改用高级语言，就可以用集合去解，也比较方便，而且如果用Python的话，这些操作都是自带的。

总结的话，还是要细心一点吧，特别是代码量一大，或者是函数调用比较多的时候，就容易犯错误，这个时候也不好修改，而且你也不知道到底是哪个环节出的问题。

1.6测试结果

测试输入：

1.	// 1、两个都正常并且有无效输入  
2.	qwerte12DRrtyu  
3.	sdfdFY0egr7tgrt  
4.	// 2、其中一个为空集  
5.	(空集）  
6.	rwqfwerrw  
7.	// 3、两个都为空集  
8.	(空集）  
9.	(空集）

测试结果：

1、两个都正常并且有无效输入

在这里插入图片描述

2、其中一个为空集

在这里插入图片描述

3、两个都为空集

在这里插入图片描述

1.7参考文献

[1]李春葆主编；尹为民，蒋晶珏，喻丹丹，蒋林编著.数据结构教程 第5版[M].北京：清华大学出版社,2017

[2]史蒂芬·普拉达.C Primer Plus 第6版 中文版[M].北京：人民邮电出版社,2019

[3]史蒂芬·普拉达.C++ Primer Plus中文版[M].北京：人民邮电出版社,2019

1.8源码

#include<stdio.h>
#include<stdlib.h>typedef char ElemType; /* ElemType类型根据实际情况而定 *//*链表*/
typedef struct LNode{ElemType data;struct LNode * next;
}LinkNode;//链表的初始化
void InitList(LinkNode* &L) {L = (LinkNode *)malloc(sizeof(LinkNode));L->next = NULL;
}//去重输入操作
void Input(LinkNode* &L) {LinkNode* s, * p;    ElemType n;scanf("%c", &n);while (n != '\n') {p = L ;while (p && (p->data != n)) {//集合中不含有相同的元素p = p ->next;}if (p == NULL && n >= 97 && n <= 122) {s = (LinkNode*)malloc(sizeof(LinkNode));s->data = n;s->next = L->next;L->next = s;}scanf("%c", &n);}
}不去重输入操作
//void Input(LinkNode* &L) {
//    LinkNode* s;    
//    ElemType n;
//    scanf("%c", &n);
//    while (n != '\n') {
//        if (n >= 97 && n <= 122) {
//            s = (LinkNode*)malloc(sizeof(LinkNode));
//            s->data = n;
//            s->next = L->next;
//            L->next = s;
//        }
//        scanf("%c", &n);
//    }
//}//输出操作
void DispList(LinkNode * L)
{LinkNode * p = L -> next;if (!p) {    printf("空集\n");return;}while(p != NULL){printf("%c ", p -> data);p = p -> next;}printf("\n");
}
//链表的清空
void ClearList(LinkNode * &L) {LinkNode * pre = L, * p = L -> next;while (p != NULL) {pre = p;p = pre -> next; free(pre);  }L -> next = NULL;
}//集合的并
void Union (LinkNode *&L1, LinkNode *&L2, LinkNode *&L3) {LinkNode *p, *q, *s;// 如果输入去重L3 = L1; 
//    //如果未去重，对!1插入L3中
//    p = L1 -> next;
//    while (p) {
//        q = L3->next;
//        while (q && (q->data != p->data)) {//C3号中不含有与1号相同的元素
//            q = q->next;
//        }
//        if (q == NULL) {
//            s = (LinkNode*)malloc(sizeof(LinkNode));
//            s->data = p->data;
//            s->next = L3->next;
//            L3->next = s;
//        }
//        p = p->next;
//    }//对L2插入L3中p = L2 -> next;while (p) {q = L3->next;while (q && (q->data != p->data)) {//L3中不含有与L2相同的元素q = q->next;}if (q == NULL) {// //当q遍历完一次都没有找到的话，即q的最后为空时就可以将L2的元素插入L3中s = (LinkNode*)malloc(sizeof(LinkNode));s->data = p->data;s->next = L3->next;L3->next = s;}p = p->next;}
}//交集
void Intersection(LinkNode *&L1, LinkNode *&L2, LinkNode *&L3) {LinkNode *p, *q, *r, *s;p = L1->next;//遍历L1while (p) {q = L2->next;//遍历L2while (q) {if (p->data == q->data)break;//找到相同的就返回elseq = q->next;}if (q) {r = (LinkNode*)malloc(sizeof(LinkNode));r->data = p->data;r->next = L3->next;L3->next = r;}p = p->next;}
}//差集
void Difference(LinkNode *&L1, LinkNode *&L2, LinkNode *&L3) {LinkNode *p, *q, *r;p = L1->next;//遍历L1while (p) {q = L2->next;while (q) {if (q->data == p->data)break;elseq = q->next;}if (q == NULL) {//说明L2遍历完了，并且有不一样的r = (LinkNode*)malloc(sizeof(LinkNode));r->data = p->data;r->next = L3->next;L3->next = r;}p = p->next;}
}void menu(){printf("                           功能菜单                          \n");printf("-------------------------------------------------------------\n");printf("| q---退出程序 | i---交集运算 | u---并集运算 | d---差集运算 |\n");printf("-------------------------------------------------------------\n");
}int main() {LinkNode *L1, *L2, *L3;L1 = (LinkNode*)malloc(sizeof(LinkNode));L2 = (LinkNode*)malloc(sizeof(LinkNode));L3 = (LinkNode*)malloc(sizeof(LinkNode));InitList(L1);InitList(L2);InitList(L3);printf("请输入小写字母哦！\n");printf("请输入SetA： ");Input(L1);printf("SetA的有效输入为： ");DispList(L1);printf("请输入SetB： ");Input(L2);printf("SetB的有效输入为： ");DispList(L2);char i;int flag = 1;while (flag){menu();printf("请选择：");scanf("%c", &i);getchar();switch (i) {case 'q':flag = 0;printf("感谢您的使用！");break;case 'i':Intersection(L1, L2, L3);printf("交集是：");DispList(L3);ClearList(L3);break;case 'u':Union (L1, L2, L3);printf("并集是：");DispList(L3);ClearList(L3);break;case 'd':Difference(L1, L2, L3);printf("(A-B)差集是：");DispList(L3);ClearList(L3);printf("(B-A)差集是：");Difference(L2, L1, L3);DispList(L3);ClearList(L3);break;default:printf("无效输入！\n");continue;}}return 0;
}

http://www.ppmy.cn/news/10856.html

相关文章

在CSDN年收入竟达五位数？----大学生技术自媒体成长之路

在CSDN年收入竟达五位数？----大学生技术自媒体成长之路

前言&#xff1a; Hello大家好&#xff0c;我是Dream。 还有不到两周就要过年了&#xff0c;自己也马上迈入了21岁&#xff0c;感慨时间飞快&#xff0c;从19岁开始入驻C站&#xff0c;到现在也已经整整两年了&#xff0c;把自己最好的两年青春时光留在了CSDN&#xff0c;超百万…
阅读更多...
Java支付宝沙箱环境支付，官方Demo远程调试【内网穿透】

Java支付宝沙箱环境支付，官方Demo远程调试【内网穿透】

文章目录1. 下载当面付demo2. 修改配置文件3. 打包成web服务4. 局域网测试5. 内网穿透6. 测试公网访问7. 配置二级子域名8. 测试使用固定二级子域名访问在沙箱环境调试支付SDK的时候&#xff0c;往往沙箱环境部署在本地&#xff0c;局限性大&#xff0c;在沙箱环境中有多种支付…
阅读更多...
FPGA与数字IC求职知识准备 - 数字电路知识总结

FPGA与数字IC求职知识准备 - 数字电路知识总结

前言 本文整理了数字电路课程中的相关基本的知识点和较为重要的知识点&#xff0c;用于求职的数电部分的知识准备&#xff0c;差缺补漏。 二进制数的算术运算 无符号二进制数的算术运算 加法&#xff1a;同十进制加法&#xff0c;逢二进一&#xff0c;无符号二进制数的加法…
阅读更多...
漏洞挖掘-不安全的HTTP方法

漏洞挖掘-不安全的HTTP方法

前言&#xff1a; 年关将至&#xff0c;这可能是年前最后一篇文章了。已经有一段时间没有更新文章了&#xff0c;因为最近也没有学到什么新的知识&#xff0c;也就没什么可写的&#xff0c;又不想灌水。最近关注的好兄弟们多了很多&#xff0c;在这里也是十分感谢大家的支持&am…
阅读更多...
一个自定义的html5视频播放器

一个自定义的html5视频播放器

// 功能:// 1.视频的播放与暂停(图标变化)// 2.总时间的显示// 3.当前时间的显示(进度)// 4.进度条的显示// 5.跳跃播放// 6.全屏<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport"…
阅读更多...
【2004NOIP普及组】T2.花生采摘 试题解析

【2004NOIP普及组】T2.花生采摘 试题解析

【2004NOIP普及组】T2.花生采摘 试题解析 时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。 鲁宾逊先生…
阅读更多...
RHCE ansible第二次作业

RHCE ansible第二次作业

1)安装和配置ansible以及ansible控制节点server.example.com如下&#xff1a; 2)创建一个名为/home/student/ansible/inventory的静态库存文件如下所示&#xff1a; 2.1)node1 是dev主机组的成员 2.2)node2是test主机组的成员 2.3)node1和node2是prod主机组的成员 2.4)node1是b…
阅读更多...
Apollo本地快速部署

Apollo本地快速部署

GitHub项目地址 Gitee项目地址 Apollo&#xff08;阿波罗&#xff09;是携程框架部门研发的分布式配置中心&#xff0c;能够集中化管理应用不同环境、不同集群的配置&#xff0c;配置修改后能够实时推送到应用端&#xff0c;并且具备规范的权限、流程治理等特性&#xff0c;适…
阅读更多...
最新文章

Copyright @ 2022~2023