525 lines
15 KiB
C++
525 lines
15 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, "C":5, "Bob":6, "D":20}
|
||
w={"D":10, "C":3, "B":5, "A":6}
|
||
del w["A"]
|
||
del w["Dickens"]
|
||
del w["Mary"]
|
||
del w["aZ"]
|
||
del w
|
||
w={"B":3, "A":10}
|
||
w["A"]=10
|
||
w["B"]=20
|
||
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>
|
||
|
||
/* 定義dict結構 */
|
||
typedef struct dict { /* 引線二元搜尋樹節點之資料結構，實作字典 */
|
||
char key[20]; /* 紀錄該節點的「鍵」(key)內容 */
|
||
int value; /* 紀錄「鍵」對應之「值」(value)內容 */
|
||
struct dict *llink; /* 指向左子樹根或引線用途 */
|
||
struct dict *rlink; /* 指向右子樹根或引線用途 */
|
||
int lbit; /* 指示 llink 是否為正常指標 */
|
||
int rbit; /* 指示 rlink 是否為正常指標 */
|
||
} dict;
|
||
|
||
void show(void); /* 輸出函數 */
|
||
void insert(char [], int); /* 將資料加入二元搜尋樹 */
|
||
void insert_left(struct dict *s, struct dict *t);
|
||
void insert_right(struct dict *s, struct dict *t);
|
||
void removing(char []); /* 將資料從二元搜尋樹中移除 */
|
||
void inorder(struct dict *); /* 資料以中序法輸出 */
|
||
void free_all_nodes(struct dict *node);
|
||
void find_newroot(void); /* 搜尋新的樹跟節點 */
|
||
|
||
dict *search_p(struct dict *node);
|
||
dict *search(char []); /* 搜尋節點 */
|
||
dict *insuc(dict *ptr);
|
||
|
||
dict *root = NULL, *ptr, *prev ,*head = NULL ;
|
||
|
||
int main(){
|
||
|
||
head = (dict *)malloc(sizeof(dict));
|
||
if (head == NULL) {
|
||
printf("記憶體分配失敗！\n");
|
||
return 1;
|
||
}
|
||
head->lbit = head->rbit = 1;
|
||
head->rlink = head;
|
||
head->llink = root;
|
||
|
||
char *token, key[12], line[128];
|
||
const char *s = " ={},"; /* 分隔符記的字元 */
|
||
int value;
|
||
char *rest ,option;
|
||
|
||
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);
|
||
// printf("key=%s,value=%d\n",key,value);
|
||
insert(key,value);
|
||
// printf("Token #%d: 鍵=%s; 值=%d\n",++i,key,value);
|
||
}
|
||
}
|
||
}else if (strstr(line,"del")) {
|
||
if(sscanf(line,"del w[%[^]]]",key)){
|
||
if(strcmp(key,root->key)==0){
|
||
// printf("刪除的元素w[%s]為root節點\n",key);
|
||
find_newroot();
|
||
// printf("新的root節點為w[%s]\n",root->key);
|
||
}else removing(key);
|
||
}else{
|
||
printf("無法判讀將刪除哪一個元素，將刪除整個字典? (y/n) => ");
|
||
scanf("%c",&option);
|
||
fflush(stdin);
|
||
if (option == 'y' || option == 'Y') {
|
||
free_all_nodes(root);
|
||
root = NULL;
|
||
}else{
|
||
printf("取消刪除所有字典\n");
|
||
}
|
||
}
|
||
}else if (strstr(line,"+=")) { /* line含有"+=" */
|
||
sscanf(line,"w[%[^]]] +=%d",key,&value);
|
||
dict *modify_node;
|
||
if((modify_node = search(key)) == NULL){ /* 找不到資料則顯示錯誤 */
|
||
printf("錯誤! %s 不在此二元搜尋樹中!\n", key);
|
||
}else{
|
||
modify_node->value += value;
|
||
printf("新設w[%s]=%d\n",key,modify_node->value);
|
||
}
|
||
}else if (strstr(line,"=")) { /* line含有"=" */
|
||
sscanf(line,"w[%[^]]] = %d",key,&value);
|
||
dict *add_node;
|
||
if (root == NULL){
|
||
insert(key,value);
|
||
printf("新設w[%s]=%d\n",key,root->value);
|
||
}else{
|
||
if((add_node = search(key)) == NULL){ /* 找不到資料則新增資料 */
|
||
insert(key,value);
|
||
printf("%s 不在此二元搜尋樹中!\n", key);
|
||
printf("新設w[%s]=%d\n",key,value);
|
||
}else{
|
||
add_node->value = value;
|
||
printf("新設w[%s]=%d\n",key,add_node->value);
|
||
}
|
||
}
|
||
}else if (sscanf(line,"w[%[^]]]?",key)==1){
|
||
dict *read_node;
|
||
if((read_node = search(key)) == NULL){ /* 找不到資料則新增資料 */
|
||
printf("錯誤! %s 不在此二元搜尋樹中!\n", key);
|
||
}else{
|
||
printf("字典元素w[%s]=%d\n",key,read_node->value);
|
||
}
|
||
}else if (strstr(line,"?")) show();
|
||
else printf("語法無法辨認，sorry!\n");
|
||
}
|
||
printf("\n程式結束，刪除所有節點，bye ~\n");
|
||
free_all_nodes(root);
|
||
free(head);
|
||
|
||
return 0;
|
||
}
|
||
|
||
// 修改後的insert函數
|
||
void insert(char key[], int value) {
|
||
// 檢查是否已存在
|
||
if (search(key) != NULL) {
|
||
printf("%s 已存在!\n", key);
|
||
return;
|
||
}
|
||
|
||
// 建立新節點
|
||
ptr = (struct dict *) malloc(sizeof(struct dict));
|
||
strcpy(ptr->key, key);
|
||
ptr->value = value;
|
||
ptr->lbit = ptr->rbit = 0;
|
||
ptr->llink = ptr->rlink = NULL; // 明確初始化為 NULL
|
||
|
||
// 處理空樹的情況
|
||
if (root == NULL) {
|
||
root = ptr;
|
||
head->llink = root; // head 的左鏈結指向 root
|
||
root->llink = head; // root 的左執行緒指向 head
|
||
root->rlink = head; // root 的右執行緒指向 head
|
||
return;
|
||
}
|
||
|
||
// 尋找插入位置
|
||
dict *current = root;
|
||
dict *parent;
|
||
|
||
while (1) {
|
||
parent = current;
|
||
if (strcmp(ptr->key, current->key) < 0) { // 往左走
|
||
if (current->lbit == 0) { // 找到插入位置
|
||
insert_left(current, ptr);
|
||
break;
|
||
}
|
||
current = current->llink;
|
||
}else { // 往右走
|
||
if (current->rbit == 0) { // 找到插入位置
|
||
insert_right(current, ptr);
|
||
break;
|
||
}
|
||
current = current->rlink;
|
||
}
|
||
}
|
||
}
|
||
|
||
// 在某節點左方插入新節點
|
||
void insert_left(struct dict *s, struct dict *t) {
|
||
t->llink = s->llink; // 新節點的左子節點指向原節點的左子節點
|
||
t->rlink = s; // 新節點的右子節點指向原節點
|
||
t->lbit = s->lbit; // 新節點繼承原節點的左位元值
|
||
t->rbit = 0; // 設定右位元為執行緒
|
||
s->llink = t; // 原節點的左子節點指向新節點
|
||
s->lbit = 1; // 設定左位元為正常鏈結
|
||
|
||
if (t->lbit == 1) {
|
||
dict *p = t->llink;
|
||
while (p->rbit == 1)
|
||
p = p->rlink;
|
||
p->rlink = t;
|
||
}
|
||
}
|
||
|
||
// 在某節點右方插入新節點（根據圖片所示）
|
||
void insert_right(struct dict *s, struct dict *t) {
|
||
t->rlink = s->rlink; // 新節點的右子節點指向原節點的右子節點
|
||
t->rbit = s->rbit; // 新節點繼承原節點的右位元值
|
||
t->llink = s; // 新節點的左子節點指向原節點
|
||
t->lbit = 0; // 設定左位元為執行緒
|
||
s->rlink = t; // 原節點的右子節點指向新節點
|
||
s->rbit = 1; // 設定右位元為正常鏈結
|
||
|
||
// 尋找前驅節點並更新引線
|
||
if (t->rbit == 1) {
|
||
dict *p = t->rlink;
|
||
while (p->lbit == 1)
|
||
p = p->llink;
|
||
p->llink = t;
|
||
}
|
||
}
|
||
|
||
/* 將資料從二元搜尋樹中移除 */
|
||
void removing(char key[]) {
|
||
dict *del_node = search(key);
|
||
if (del_node == NULL) {
|
||
printf("%s 不在此二元搜尋樹中!\n", key);
|
||
return;
|
||
}
|
||
|
||
dict *parent = search_p(del_node);
|
||
|
||
// Case 1: 葉節點 (沒有子節點)
|
||
if (del_node->lbit == 0 && del_node->rbit == 0) {
|
||
if (parent == NULL) { // 刪除的是根節點
|
||
root = NULL;
|
||
head->llink = head;
|
||
} else if (parent->llink == del_node) {
|
||
parent->llink = del_node->llink; // 繼承左執行緒
|
||
parent->lbit = 0;
|
||
} else {
|
||
parent->rlink = del_node->rlink; // 繼承右執行緒
|
||
parent->rbit = 0;
|
||
}
|
||
free(del_node);
|
||
}
|
||
|
||
// Case 2: 只有左子樹
|
||
else if (del_node->lbit == 1 && del_node->rbit == 0) {
|
||
dict *left_child = del_node->llink;
|
||
dict *successor = del_node->rlink; // 保存後繼節點
|
||
|
||
// 找到左子樹的最右節點
|
||
dict *rightmost = left_child;
|
||
while (rightmost->rbit == 1) {
|
||
rightmost = rightmost->rlink;
|
||
}
|
||
|
||
// 更新連接
|
||
rightmost->rlink = successor;
|
||
if (parent == NULL) {
|
||
root = left_child;
|
||
head->llink = root;
|
||
} else if (parent->llink == del_node) {
|
||
parent->llink = left_child;
|
||
} else {
|
||
parent->rlink = left_child;
|
||
}
|
||
free(del_node);
|
||
}
|
||
|
||
// Case 3: 只有右子樹
|
||
else if (del_node->lbit == 0 && del_node->rbit == 1) {
|
||
dict *right_child = del_node->rlink;
|
||
dict *predecessor = del_node->llink; // 保存前驅節點
|
||
|
||
// 找到右子樹的最左節點
|
||
dict *leftmost = right_child;
|
||
while (leftmost->lbit == 1) {
|
||
leftmost = leftmost->llink;
|
||
}
|
||
|
||
// 更新連接
|
||
leftmost->llink = predecessor;
|
||
if (parent == NULL) {
|
||
root = right_child;
|
||
head->llink = root;
|
||
} else if (parent->llink == del_node) {
|
||
parent->llink = right_child;
|
||
} else {
|
||
parent->rlink = right_child;
|
||
}
|
||
free(del_node);
|
||
}
|
||
|
||
// Case 4: 有兩個子樹
|
||
else {
|
||
// 找到中序後繼節點（右子樹中最小的節點）
|
||
dict *successor = del_node->rlink;
|
||
dict *succ_parent = del_node;
|
||
|
||
while (successor->lbit == 1) {
|
||
succ_parent = successor;
|
||
successor = successor->llink;
|
||
}
|
||
|
||
// 複製後繼節點的數據到被刪除節點
|
||
strcpy(del_node->key, successor->key);
|
||
del_node->value = successor->value;
|
||
|
||
// 移除後繼節點
|
||
if (succ_parent == del_node) {
|
||
del_node->rlink = successor->rlink;
|
||
del_node->rbit = successor->rbit;
|
||
} else {
|
||
succ_parent->llink = successor->llink;
|
||
succ_parent->lbit = successor->lbit;
|
||
}
|
||
|
||
free(successor);
|
||
}
|
||
|
||
printf("刪除w[%s]元素\n", key);
|
||
}
|
||
|
||
void find_newroot() {
|
||
struct dict *newroot_node, *prev;
|
||
|
||
if(root->lbit == 0 && root->rbit == 0 ){
|
||
printf("刪除w[%s]元素\n", root->key);
|
||
free(root);
|
||
root = NULL;
|
||
return;
|
||
}
|
||
|
||
if (root->lbit == 1) { // 有左子樹，找左子樹中最大的節點
|
||
newroot_node = root->llink;
|
||
prev = root;
|
||
|
||
// 找到左子樹中最大的節點
|
||
while (newroot_node->rbit == 1) {
|
||
prev = newroot_node;
|
||
newroot_node = newroot_node->rlink;
|
||
}
|
||
|
||
// 處理新根節點的連接
|
||
if (newroot_node != root->llink) {
|
||
// 如果新根不是原根的直接左子節點
|
||
prev->rbit = newroot_node->rbit; // 繼承新根的右執行緒狀態
|
||
prev->rlink = newroot_node->rlink; // 繼承新根的右執行緒
|
||
|
||
newroot_node->lbit = root->lbit; // 繼承原根的左指標狀態
|
||
newroot_node->llink = root->llink; // 繼承原根的左子樹
|
||
newroot_node->rbit = root->rbit; // 繼承原根的右指標狀態
|
||
newroot_node->rlink = root->rlink; // 繼承原根的右子樹
|
||
} else {
|
||
// 如果新根是原根的直接左子節點
|
||
newroot_node->rbit = root->rbit; // 繼承原根的右指標狀態
|
||
newroot_node->rlink = root->rlink; // 繼承原根的右子樹
|
||
}
|
||
|
||
} else if (root->rbit == 1) { // 有右子樹，找右子樹中最小的節點
|
||
newroot_node = root->rlink;
|
||
prev = root;
|
||
|
||
// 找到右子樹中最小的節點
|
||
while (newroot_node->lbit == 1) {
|
||
prev = newroot_node;
|
||
newroot_node = newroot_node->llink;
|
||
}
|
||
|
||
// 處理新根節點的連接
|
||
if (newroot_node != root->rlink) {
|
||
// 如果新根不是原根的直接右子節點
|
||
prev->lbit = newroot_node->lbit; // 繼承新根的左執行緒狀態
|
||
prev->llink = newroot_node->llink; // 繼承新根的左執行緒
|
||
|
||
newroot_node->lbit = root->lbit; // 繼承原根的左指標狀態
|
||
newroot_node->llink = root->llink; // 繼承原根的左子樹
|
||
newroot_node->rbit = root->rbit; // 繼承原根的右指標狀態
|
||
newroot_node->rlink = root->rlink; // 繼承原根的右子樹
|
||
} else {
|
||
// 如果新根是原根的直接右子節點
|
||
newroot_node->lbit = root->lbit; // 繼承原根的左指標狀態
|
||
newroot_node->llink = root->llink; // 繼承原根的左子樹
|
||
}
|
||
}
|
||
|
||
// 更新頭節點的連接
|
||
if(root != NULL){
|
||
head->llink = newroot_node;
|
||
printf("刪除w[%s]元素\n", root->key);
|
||
free(root);
|
||
root = newroot_node;
|
||
}
|
||
}
|
||
|
||
void show(void) {
|
||
if (root == NULL) {
|
||
puts("二元搜尋樹是空的!");
|
||
return;
|
||
}
|
||
printf("字典變數內部儲存的元素(key：value)如下\n");
|
||
inorder(root);
|
||
}
|
||
|
||
// 使用引線特性進行中序遍歷
|
||
void inorder(dict *root) {
|
||
if (root == NULL) {
|
||
printf("二元搜尋樹是空的!\n");
|
||
return;
|
||
}
|
||
|
||
dict *current = root;
|
||
// 找到最左邊的節點
|
||
while (current->lbit == 1) {
|
||
current = current->llink;
|
||
}
|
||
|
||
// 使用引線特性遍歷
|
||
while (current != head) {
|
||
printf("%s：%d\n", current->key, current->value);
|
||
current = insuc(current);
|
||
}
|
||
}
|
||
|
||
// 尋找中序後繼節點
|
||
dict *insuc(dict *ptr) {
|
||
dict *current;
|
||
|
||
// 若右指標是執行緒（rbit = 0），直接返回右指標
|
||
if (ptr->rbit == 0) {
|
||
return ptr->rlink;
|
||
}
|
||
|
||
// 否則往右走一步後，一直往左走直到到達最左邊的節點
|
||
current = ptr->rlink;
|
||
while (current->lbit == 1) {
|
||
current = current->llink;
|
||
}
|
||
return current;
|
||
}
|
||
|
||
/* 搜尋target所在節點 */
|
||
struct dict *search(char target[]) {
|
||
struct dict *node = root;
|
||
|
||
while (node != NULL && node != head) { // 加入 head 的檢查以防止走到頭節點
|
||
int cmp = strcmp(target, node->key);
|
||
if (cmp == 0) {
|
||
return node; // 找到目標節點
|
||
} else if (cmp < 0) { // target 小於目前節點，往左搜尋
|
||
if (node->lbit == 0) { // 如果左邊是執行緒
|
||
return NULL; // 代表找不到目標
|
||
}
|
||
node = node->llink;
|
||
} else { // target 大於目前節點，往右搜尋
|
||
if (node->rbit == 0) { // 如果右邊是執行緒
|
||
return NULL; // 代表找不到目標
|
||
}
|
||
node = node->rlink;
|
||
}
|
||
}
|
||
return NULL; // 找不到目標
|
||
}
|
||
|
||
/* 搜尋node的父節點 */
|
||
struct dict *search_p(struct dict *node) {
|
||
if (node == NULL || node == root) {
|
||
return NULL;
|
||
}
|
||
|
||
struct dict *current = root;
|
||
struct dict *parent = NULL;
|
||
|
||
while (current != NULL && current != head) {
|
||
int cmp = strcmp(node->key, current->key);
|
||
|
||
if (cmp == 0) { // 找到目標節點，返回其父節點
|
||
return parent;
|
||
}
|
||
|
||
parent = current; // 更新父節點
|
||
|
||
if (cmp < 0) { // 目標在左子樹
|
||
if (current->lbit == 0) { // 如果是執行緒
|
||
return NULL; // 找不到目標
|
||
}
|
||
current = current->llink;
|
||
} else { // 目標在右子樹
|
||
if (current->rbit == 0) { // 如果是執行緒
|
||
return NULL; // 找不到目標
|
||
}
|
||
current = current->rlink;
|
||
}
|
||
}
|
||
|
||
return NULL; // 沒有找到目標節點
|
||
}
|
||
|
||
// 釋放所有節點的非遞迴版本
|
||
void free_all_nodes(struct dict *root) {
|
||
if (root == NULL) {
|
||
return;
|
||
}
|
||
|
||
dict *current = root;
|
||
dict *temp;
|
||
|
||
// 找到最左邊的節點
|
||
while (current->lbit == 1) {
|
||
current = current->llink;
|
||
}
|
||
|
||
// 使用引線特性遍歷並釋放節點
|
||
while (current != head) {
|
||
temp = current;
|
||
current = insuc(current);
|
||
printf("刪除'w[%s]=%d'節點\n", temp->key, temp->value);
|
||
free(temp);
|
||
}
|
||
root = NULL;
|
||
}
|