335 lines
9.8 KiB
C++
335 lines
9.8 KiB
C++
/*Notes: 輸入可為
|
||
w={"Mary":10, "Tom":3, "Charlie":5, "Bob":6, "Dickens":20, 4:9, "z":0, "Za":12, "aZ":8}
|
||
w={10:10, 20:3, 5:5, 17:6, 23:20, 18:9, 3:0, 9:12}
|
||
w={10:10, 5:5, 9:6, 3:20, 7:9}
|
||
w={"A":10, "B":3, "Charlie":5, "Bob":6, "Dickens":20}
|
||
w={"A":6,"B":5,"C":3,"D":10}
|
||
w={"A":6,"B":5}
|
||
del w["A"]
|
||
del w["Dickens"]
|
||
del w["Mary"]
|
||
del w["aZ"]
|
||
del w
|
||
w["Mary"]=1
|
||
w["Tom"]+=2
|
||
w[4]?
|
||
w?
|
||
*/
|
||
|
||
#include <stdio.h> /* for sscanf(), printf() */
|
||
#include <stdlib.h>
|
||
#include <string.h> /* for strstr(), strtok(), strtok_r() */
|
||
#include <conio.h>
|
||
|
||
/* 定義student結構 */
|
||
typedef struct student {
|
||
char name[20]; /* 學生姓名 */
|
||
int score; /* 學生成績 */
|
||
struct student *llink; /* 左子鏈結 */
|
||
struct student *rlink; /* 右子鏈結 */
|
||
}student;
|
||
|
||
void show(void); /* 輸出函數 */
|
||
void insert(char [], int); /* 將資料加入二元搜尋樹 */
|
||
void removing(char []); /* 將資料從二元搜尋樹中移除 */
|
||
void inorder(struct student *); /* 資料以中序法輸出 */
|
||
void free_all_nodes(struct student *node);
|
||
void find_newroot(void); /* 搜尋新的樹跟節點 */
|
||
|
||
student *search_p(struct student *node);
|
||
student *search(char []); /* 搜尋節點 */
|
||
|
||
student *root, *ptr, *prev;
|
||
|
||
int main(){
|
||
char *token, key[12], line[128];
|
||
const char *s = " ={},"; /* 分隔符記的字元 */
|
||
int value;
|
||
char *rest ,choice[3];
|
||
|
||
printf("輸入存取字典的陳述，逕按<Enter>結束程式\n");
|
||
while (1) {
|
||
printf("\n指令 => ");
|
||
fgets(line,128,stdin); /* 使用gets()讀取也可以，但因gets()未設讀入字元數的限制，可能導致儲存輸入字元的陣列空間爆掉 */
|
||
if (line[0]=='\n') break; /* 輸入空字串則跳離此迴圈 */
|
||
if (strstr(line,"{")) { /* line含有"{" */
|
||
sscanf(line,"w = {%[^}]}",line);
|
||
rest = line;
|
||
while (token = strtok_r(rest,s,&rest)) { /* strtok_r()的用法可參見 http://bit.ly/3VcvbbZ */
|
||
/* printf("%s\n",token); */
|
||
if (strstr(token,":")) {/* token含有":" */
|
||
sscanf(token,"%[^:]:%d",key,&value);
|
||
insert(key,value);
|
||
// printf("Token #%d: 鍵=%s; 值=%d\n",++i,key,value);
|
||
}
|
||
}
|
||
}else if (strstr(line,"del")) {
|
||
if(strcmp(line,"del w\n")==0){
|
||
printf("無法判讀將刪除哪一個元素，將刪除整個字典(y/n) => ");
|
||
fgets(choice, sizeof(choice), stdin);
|
||
if(strcmp(choice,"y\n")==0){
|
||
free_all_nodes(root);
|
||
root = NULL;
|
||
}else{
|
||
printf("取消刪除所有字典\n");
|
||
}
|
||
}else{
|
||
if(sscanf(line,"del w[%[^]]]",key)==1){
|
||
if(strcmp(key,root->name)==0){
|
||
// printf("刪除的元素w[%s]為root節點\n",key);
|
||
find_newroot();
|
||
// printf("新的root節點為w[%s]\n",root->name);
|
||
}else{
|
||
removing(key);
|
||
}
|
||
}
|
||
}
|
||
}else if (strstr(line,"+=")) { /* line含有"+=" */
|
||
sscanf(line,"w[%[^]]] +=%d",key,&value);
|
||
student *modify_node;
|
||
if((modify_node = search(key)) == NULL){ /* 找不到資料則顯示錯誤 */
|
||
printf("錯誤! %s 不在此二元搜尋樹中!\n", key);
|
||
}else{
|
||
modify_node->score += value;
|
||
printf("新設w[%s]=%d\n",key,modify_node->score);
|
||
}
|
||
}else if (strstr(line,"=")) { /* line含有"=" */
|
||
sscanf(line,"w[%[^]]] = %d",key,&value);
|
||
student *add_node;
|
||
if (root == NULL){
|
||
insert(key,value);
|
||
printf("新設w[%s]=%d\n",key,root->score);
|
||
}else{
|
||
if((add_node = search(key)) == NULL){ /* 找不到資料則新增資料 */
|
||
insert(key,value);
|
||
printf("%s 不在此二元搜尋樹中!\n", key);
|
||
printf("新設w[%s]=%d\n",key,value);
|
||
}else{
|
||
add_node->score = value;
|
||
printf("新設w[%s]=%d\n",key,add_node->score);
|
||
}
|
||
}
|
||
}else if (sscanf(line,"w[%[^]]]?",key)==1){
|
||
student *read_node;
|
||
if((read_node = search(key)) == NULL){ /* 找不到資料則新增資料 */
|
||
printf("錯誤! %s 不在此二元搜尋樹中!\n", key);
|
||
}else{
|
||
printf("字典元素w[%s]=%d\n",key,read_node->score);
|
||
}
|
||
}else if (strstr(line,"?")) show();
|
||
else printf("語法無法辨認，sorry!\n");
|
||
}
|
||
|
||
printf("\n程式結束，bye ~\n");
|
||
return 0;
|
||
}
|
||
|
||
/* 處理二元搜尋樹，將新增資料加入至二元搜尋樹中 */
|
||
void insert(char name[], int score){
|
||
struct student *node, *prev;
|
||
/* 資料已存在則顯示錯誤 */
|
||
if (search(name) != NULL) {
|
||
printf("%s 已存在!\n", name);
|
||
return;
|
||
}
|
||
ptr = (struct student *) malloc(sizeof(struct student));
|
||
strcpy(ptr->name, name);
|
||
ptr->score = score;
|
||
ptr->llink = ptr->rlink = NULL;
|
||
if (root == NULL) /* 當根節點為NULL的狀況 */
|
||
root = ptr;
|
||
else { /* 當根節點不為NULL的狀況 */
|
||
node = root;
|
||
while (node != NULL) { /* 搜尋資料插入點 */
|
||
prev = node;
|
||
if(strcmp(ptr->name, node->name) < 0)
|
||
node = node->llink;
|
||
else
|
||
node = node->rlink;
|
||
}
|
||
if (strcmp(ptr->name, prev->name) < 0)
|
||
prev->llink = ptr;
|
||
else
|
||
prev->rlink = ptr;
|
||
}
|
||
}
|
||
|
||
/* 將資料從二元搜尋樹中移除 */
|
||
void removing(char name[]){
|
||
student *del_node = search(name);
|
||
if (del_node == NULL) {
|
||
printf("%s 不在此二元搜尋樹中!\n", name);
|
||
return;
|
||
}
|
||
|
||
student *parent = search_p(del_node);
|
||
|
||
// 處理沒有子節點的情況
|
||
if (del_node->llink == NULL && del_node->rlink == NULL) {
|
||
if (parent->llink == del_node) {
|
||
parent->llink = NULL;
|
||
} else {
|
||
parent->rlink = NULL;
|
||
}
|
||
}else if (del_node->llink == NULL || del_node->rlink == NULL) { // 處理一邊有子節點的情況
|
||
student *child = (del_node->llink != NULL) ? del_node->llink : del_node->rlink;
|
||
if (parent->llink == del_node) {
|
||
parent->llink = child;
|
||
} else {
|
||
parent->rlink = child;
|
||
}
|
||
}else{ //處理兩邊有子節點的情況
|
||
if(del_node == parent->rlink){
|
||
parent->rlink = del_node->llink;
|
||
if(del_node->llink->rlink != NULL){ //若刪除的節點的子節點還有右節點的情況
|
||
student *child = del_node->llink->rlink;
|
||
printf("%s\n",child->name);
|
||
while(child->rlink!= NULL){ //找右節點直到最底
|
||
child = child->rlink;
|
||
printf("%s\n",child->name);
|
||
}
|
||
child->rlink = del_node->rlink;
|
||
}else parent->rlink->rlink = del_node->rlink; //沒有則直接替換
|
||
|
||
}else{
|
||
parent->llink = del_node->llink;
|
||
if(del_node->rlink->llink != NULL){ //若刪除的節點的子節點還有左節點的情況
|
||
student *child = del_node->rlink->llink;
|
||
printf("%s\n",child->name);
|
||
while(child->llink!= NULL){ //找左節點直到最底
|
||
child = child->llink;
|
||
printf("%s\n",child->name);
|
||
}
|
||
child->llink = del_node->llink;
|
||
}else parent->llink->rlink = del_node->rlink; //沒有則直接替換
|
||
}
|
||
}
|
||
free(del_node); /* 釋放記憶體 */
|
||
printf("刪除w[%s]元素\n",name);
|
||
}
|
||
|
||
/* 輸出函數，將資料輸出至螢幕 */
|
||
void show(void){
|
||
/* 判斷根節點是否為NULL */
|
||
if (root == NULL) {
|
||
puts("二元搜尋樹是空的!");
|
||
return;
|
||
}
|
||
// printf("root為%s\n", root->name);
|
||
printf("字典變數內部儲存的元素(key：value)如下\n");
|
||
inorder(root); /* 以中序法輸出資料 */
|
||
}
|
||
|
||
/* 以中序法輸出資料，採遞迴方式 */
|
||
void inorder(struct student *node ){
|
||
if(node != NULL) {
|
||
|
||
inorder(node->llink);
|
||
printf("%s：%d\n", node->name, node->score);
|
||
inorder(node->rlink);
|
||
}
|
||
}
|
||
|
||
void find_newroot(){ /* 搜尋新的樹跟節點 左連結最大值*/
|
||
struct student *newroot_node ,*prev;
|
||
|
||
if(root->llink == NULL && root->rlink == NULL){
|
||
printf("刪除w[%s]元素\n",root->name);
|
||
free(root);
|
||
root = NULL;
|
||
return;
|
||
}
|
||
|
||
if(root->llink!=NULL){ //找左連結的最大值
|
||
newroot_node = root->llink;
|
||
|
||
while(newroot_node->rlink!=NULL){ //找根的替代節點
|
||
prev = newroot_node;
|
||
newroot_node = newroot_node->rlink;
|
||
}
|
||
if(newroot_node->llink!=NULL){ //若新的根節點有左節點
|
||
prev->rlink = newroot_node->llink;
|
||
}else prev->rlink = NULL;
|
||
|
||
if(newroot_node != root->llink ){ //若新的根節點不等於原本根的左節點
|
||
newroot_node->llink = root->llink;
|
||
newroot_node->rlink = root->rlink;
|
||
}else{ //若新的根節點等於原本根的左節點
|
||
newroot_node->rlink = root->rlink;
|
||
}
|
||
printf("刪除w[%s]元素\n",root->name);
|
||
free(root);
|
||
root = newroot_node;
|
||
}else if(root->rlink!=NULL){ //找右連結的最小值
|
||
newroot_node = root->rlink;
|
||
|
||
while(newroot_node->llink!=NULL){ //找根的替代節點
|
||
prev = newroot_node;
|
||
newroot_node = newroot_node->llink;
|
||
}
|
||
if(newroot_node->rlink!=NULL){ //若新的根節點有右節點
|
||
prev->llink = newroot_node->rlink;
|
||
}else prev->llink = NULL;
|
||
|
||
if(newroot_node != root->rlink ){ //若新的根節點不等於原本根的右節點
|
||
newroot_node->llink = root->llink;
|
||
newroot_node->rlink = root->rlink;
|
||
}else{ //若新的根節點等於原本根的右節點
|
||
newroot_node->llink = root->llink;
|
||
}
|
||
printf("刪除w[%s]元素\n",root->name);
|
||
free(root);
|
||
root = newroot_node;
|
||
}
|
||
}
|
||
|
||
/* 搜尋target所在節點 */
|
||
struct student *search(char target[]){
|
||
struct student *node;
|
||
node = root;
|
||
while(node != NULL){
|
||
if (strcmp(target, node->name) == 0)
|
||
return node;
|
||
else
|
||
/* target小於目前節點，往左搜尋 */
|
||
if (strcmp(target, node->name) < 0)
|
||
node = node->llink;
|
||
else /* target大於目前節點，往右搜尋 */
|
||
node = node->rlink;
|
||
}
|
||
return node;
|
||
}
|
||
|
||
/* 搜尋node的父節點 */
|
||
struct student *search_p(struct student *node){
|
||
struct student *parent;
|
||
parent = root;
|
||
while (parent != NULL) {
|
||
if (strcmp(node->name, parent->name) < 0) {
|
||
if (strcmp(node->name, parent->llink->name) == 0)
|
||
return parent;
|
||
else
|
||
parent = parent->llink;
|
||
}else {
|
||
if (strcmp(node->name, parent->rlink->name) == 0)
|
||
return parent;
|
||
else
|
||
parent = parent->rlink;
|
||
}
|
||
}
|
||
return NULL;
|
||
}
|
||
|
||
/* 遞迴釋放所有節點的記憶體 */
|
||
void free_all_nodes(struct student *node) {
|
||
if (node == NULL) return;
|
||
|
||
// 先遞迴釋放左子樹
|
||
free_all_nodes(node->llink);
|
||
// 再遞迴釋放右子樹
|
||
free_all_nodes(node->rlink);
|
||
printf("刪除'w[%s]=%d'節點\n",node->name,node->score);
|
||
// 最後釋放當前節點
|
||
free(node);
|
||
}
|