數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
1.1問題描述
編制一個能演示執(zhí)行集合的交、并和差運算的程序。
要求：
-
集合元素用小寫英文字母，執(zhí)行各種操作應(yīng)以對話方式執(zhí)行。
-
算法要點：利用單鏈表表示集合；理解好三種運算的含義
1.2需求分析
分析：
輸入：輸入應(yīng)該具有判斷是否為小寫字母的功能，如果不是小寫字母，應(yīng)該舍去，同時打印有效輸入給用戶看，用來檢查輸入。并且應(yīng)該去除用戶輸入的重復(fù)元素，滿足集合的互異性。并且能處理好空集的問題。
結(jié)果：實現(xiàn)與用戶的交互功能并且能輸出集合的交、并和差運算的結(jié)果。對于無效輸入，也要處理。
1.3概要設(shè)計
數(shù)據(jù)類型：
采用的數(shù)據(jù)類型是單鏈表，單鏈表用來儲存元素，方便后面的插入操作，具體實現(xiàn)如下所示：
/*鏈表*/
typedef struct LNode{
ElemType data;
struct LNode * next;
}LinkNode;
流程：
主程序主要就是通過用戶輸入來判斷執(zhí)行哪些操作，首先是輸入操作，既要避免無效輸入（非小寫字母），還要去重，最后還要將有效輸入打印出來。
當(dāng)輸入為i（Intersection）的時候，調(diào)用Intersection()函數(shù)求交集，當(dāng)輸入為u（Union）的時候，調(diào)用Union()函數(shù)求并集，當(dāng)輸入為d（Difference）的時候，調(diào)用Difference()函數(shù)求差集，本次是將A – B輸出，并且輸出B – A。當(dāng)輸入為 q 時，程序結(jié)束。而當(dāng)輸入是無效輸入的時候，也會提醒用戶。
1.4詳細設(shè)計
主函數(shù)偽代碼：
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;
}
}
結(jié)束;
//return 0;
}
主函數(shù)流程圖：
交集偽代碼：
//交集
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調(diào)試分析
調(diào)試過程中也是遇到一些問題的，首先就是單個功能測試正常，然后多次測試就失敗了，然后一直在找具體原因，最后還是在刪除L3鏈表的時候出了問題，因為自己的疏忽，不小心把L3鏈表全刪了，導(dǎo)致第二次執(zhí)行的時候，是找不到L3鏈表的，導(dǎo)致程序異常終止，后來經(jīng)過修改，也是解決了這個問題。
以及對于輸入，一開始覺得太復(fù)雜，就沒有做去重操作，后來發(fā)現(xiàn)這樣對于后面的操作帶來了極大的不便，就將其修改為了去重。
對于算法復(fù)雜度，輸入，交集，并集都是O(nm)的復(fù)雜度，目前沒有什么好的優(yōu)化方法，不過如果是改用高級語言，就可以用集合去解，也比較方便，而且如果用Python的話，這些操作都是自帶的。
總結(jié)的話，還是要細心一點吧，特別是代碼量一大，或者是函數(shù)調(diào)用比較多的時候，就容易犯錯誤，這個時候也不好修改，而且你也不知道到底是哪個環(huán)節(jié)出的問題。
1.6測試結(jié)果
測試輸入：
1. // 1、兩個都正常并且有無效輸入
2. qwerte12DRrtyu
3. sdfdFY0egr7tgrt
4. // 2、其中一個為空集
5. (空集）
6. rwqfwerrw
7. // 3、兩個都為空集
8. (空集）
9. (空集）
測試結(jié)果：
1、兩個都正常并且有無效輸入
2、其中一個為空集
3、兩個都為空集
1.7參考文獻
[1]李春葆主編；尹為民，蔣晶玨，喻丹丹，蔣林編著.數(shù)據(jù)結(jié)構(gòu)教程 第5版[M].北京：清華大學(xué)出版社,2017
[2]史蒂芬·普拉達.C Primer Plus 第6版 中文版[M].北京：人民郵電出版社,2019文章來源：http://www.zghlxwxcb.cn/news/detail-784842.html
[3]史蒂芬·普拉達.C++ Primer Plus中文版[M].北京：人民郵電出版社,2019文章來源地址http://www.zghlxwxcb.cn/news/detail-784842.html
1.8源碼
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType; /* ElemType類型根據(jù)實際情況而定 */
/*鏈表*/
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) {// //當(dāng)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;//遍歷L1
while (p) {
q = L2->next;//遍歷L2
while (q) {
if (p->data == q->data)
break;//找到相同的就返回
else
q = 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;//遍歷L1
while (p) {
q = L2->next;
while (q) {
if (q->data == p->data)
break;
else
q = 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;
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
