Jeff/Data_Structure
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
master
Data_Structure/資料結構光碟檔/CH09/avlTree.c.txt

436 lines
12 KiB
Plaintext
Raw Permalink Normal View History

上傳教材
2025-01-20 21:25:33 +08:00
/* file name: avlTree.c */
/* <20>Q<EFBFBD><51> AVL-TREE <20>B<EFBFBD>z<EFBFBD>ǥ͸<C7A5><CDB8><EFBFBD>--<2D><><EFBFBD>ɡB<C9A1>s<EFBFBD>ɡB<C9A1><42><EFBFBD>J<EFBFBD>B<EFBFBD>R<EFBFBD><52><EFBFBD>B<EFBFBD>ק<EFBFBD><D7A7>B<EFBFBD><42><EFBFBD>X */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct student {
char name[20]; /* <20>m<EFBFBD>W */
int score; /* <20><><EFBFBD><EFBFBD> */
int bf; /* <20>`<60>IBF<42><46> */
struct student *llink, *rlink; /* <20>`<60>I<EFBFBD>l<EFBFBD>쵲 */
};
void insert_f(void); /* <20><><EFBFBD>J<EFBFBD><4A><EFBFBD><EFBFBD> */
void delete_f(void); /* <20>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
void modify_f(void); /* <20>ק<EFBFBD><D7A7><EFBFBD><EFBFBD><EFBFBD> */
void list_f(void); /* <20><><EFBFBD>X<EFBFBD><58><EFBFBD><EFBFBD> */
void sort_f(char [], int); /* <20><><EFBFBD>J<EFBFBD>ɮ׫<C9AE><D7AB>Ƨ<EFBFBD> */
void inorder(struct student *); /* <20><><EFBFBD>X<EFBFBD>ϥΤ<CFA5><CEA4>ǰl<C7B0><6C> */
void bf_count(struct student *); /* <20>p<EFBFBD><70><EFBFBD>`<60>IBF<42><46> */
int height_count(struct student *); /* <20>p<EFBFBD><70><EFBFBD>`<60>I<EFBFBD><49><EFBFBD><EFBFBD> */
void pivot_find(void); /* <20><><EFBFBD>Xpivot<6F>Ҧb<D2A6>`<60>I */
int type_find(void); /* <20><><EFBFBD>X<EFBFBD>ﵽ<EFBFBD><EFB5BD><EFBFBD>k */
void type_ll(void); /* <20>ϥ<EFBFBD>LL<4C><4C><EFBFBD>A */
void type_rr(void); /* <20>ϥ<EFBFBD>RR<52><52><EFBFBD>A */
void type_lr(void); /* <20>ϥ<EFBFBD>LR<4C><52><EFBFBD>A */
void type_rl(void); /* <20>ϥ<EFBFBD>RL<52><4C><EFBFBD>A */
void flushBuffer(void);
struct student *ptr, *root, *this_n, *prev, *pivot, *pivot_prev;
int nodecount = 0; /* <20>Ψӭp<D3AD><70>node<64>Ӽ<EFBFBD> */
int main()
{
char option;
while(1) {
printf("\n **********************\n");
printf(" <1> insert\n");
printf(" <2> delete\n");
printf(" <3> modify\n");
printf(" <4> list\n");
printf(" <5> exit\n");
printf(" **********************\n");
printf(" Enter your choice: ");
option = getchar();
flushBuffer();
switch(option) {
case '1':
insert_f();
break;
case '2':
delete_f();
break;
case '3':
modify_f();
break;
case '4':
list_f();
break;
case '5':
exit(0);
}
}
return 0;
}
void insert_f(void)
{
char name_t[20];
int score_t;
printf("\n <20>п<EFBFBD><D0BF>J<EFBFBD>m<EFBFBD>W: ");
scanf("%s", name_t);
flushBuffer();
printf(" <20>п<EFBFBD><D0BF>J<EFBFBD><4A><EFBFBD><EFBFBD>: ");
scanf("%d", &score_t);
flushBuffer();
nodecount++;/* <20>Nnode<64>[1 */
sort_f(name_t, score_t); /* <20>I<EFBFBD>s SORT_F <20><><EFBFBD>Ƨ@<40>ƧǤΥ<C7A4><CEA5><EFBFBD> */
}
void sort_f(char name_t[], int score_t)
{
int op;
this_n = root;
while((this_n != NULL) && (strcmp(name_t, this_n->name) != 0)) {
/* <20><><EFBFBD>J<EFBFBD><4A><EFBFBD>Ƥp<C6A4><70><EFBFBD>ثe<D8AB><65><EFBFBD>m<EFBFBD>A<EFBFBD>h<EFBFBD><68><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
if(strcmp(name_t, this_n->name) < 0) {
prev = this_n;
this_n = this_n->llink;
}
else { /* <20>Y<EFBFBD>j<EFBFBD><6A><EFBFBD>ثe<D8AB><65><EFBFBD>m<EFBFBD>A<EFBFBD>h<EFBFBD><68><EFBFBD>k<EFBFBD><6B> */
prev = this_n;
this_n = this_n->rlink;
}
}
/* <20><><EFBFBD>촡<EFBFBD>J<EFBFBD><4A><EFBFBD>m<EFBFBD>A<EFBFBD>L<EFBFBD><4C><EFBFBD>и<EFBFBD><D0B8>Ʀs<C6A6>b */
if(this_n == NULL || strcmp(name_t, this_n->name) != 0) {
ptr = (struct student *) malloc(sizeof(struct student));
strcpy(ptr->name, name_t);
ptr->score = score_t;
ptr->llink = NULL;
ptr->rlink = NULL;
if(root == NULL)
root = ptr; /* ROOT<4F><54><EFBFBD>s<EFBFBD>b<EFBFBD>A<EFBFBD>h<EFBFBD>NROOT<4F><54><EFBFBD>V<EFBFBD><56><EFBFBD>J<EFBFBD><4A><EFBFBD><EFBFBD> */
if(prev != NULL) {
if(strcmp(ptr->name, prev->name) < 0)
prev->llink = ptr;
else
prev->rlink = ptr;
}
bf_count(root);
pivot_find();
/* PIVOT<4F>s<EFBFBD>b<EFBFBD>A<EFBFBD>h<EFBFBD><68><EFBFBD>ﵽ<EFBFBD><EFB5BD>AVL-TREE */
if(pivot != NULL) {
op = type_find();
switch(op) {
case 11:
type_ll();
break;
case 22:
type_rr();
break;
case 12:
type_lr();
break;
case 21:
type_rl();
break;
}
}
bf_count(root); /* <20><><EFBFBD>s<EFBFBD>p<EFBFBD><70><EFBFBD>C<EFBFBD>Ӹ`<60>I<EFBFBD><49>BF<42><46> */
}
/* <20><><EFBFBD><EFBFBD><EFBFBD>J<EFBFBD><4A><EFBFBD><EFBFBD>KEY<45>w<EFBFBD>s<EFBFBD>b<EFBFBD>A<EFBFBD>h<EFBFBD><68><EFBFBD>ܿ<EFBFBD><DCBF>~ */
else {
printf(" %s <20><><EFBFBD>s<EFBFBD>b\n", name_t);
}
}
void delete_f(void)
{
struct student *clear;
char name_t[20];
int op;
/* <20>Y<EFBFBD>ڤ<EFBFBD><DAA4>s<EFBFBD>b<EFBFBD>A<EFBFBD>h<EFBFBD><68><EFBFBD>ܿ<EFBFBD><DCBF>~ */
if(root == NULL)
printf(" AVL Tree <20>L<EFBFBD><4C><EFBFBD><EFBFBD>\n");
else {
printf("\n <20><><EFBFBD>J<EFBFBD><4A><EFBFBD>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD>m<EFBFBD>W: ");
scanf("%s", name_t);
flushBuffer();
this_n = root;
while(this_n != NULL && strcmp(name_t, this_n->name) != 0) {
/* <20>Y<EFBFBD>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ȥp<C8A4><70><EFBFBD>ثe<D8AB>Ҧb<D2A6><62><EFBFBD>ơA<C6A1>h<EFBFBD><68><EFBFBD><EFBFBD><EFBFBD>l<EFBFBD><6C> */
if(strcmp(name_t, this_n->name) < 0) {
prev = this_n;
this_n = this_n->llink;
}
/* <20>_<EFBFBD>h<EFBFBD>h<EFBFBD><68><EFBFBD>k<EFBFBD>l<EFBFBD><6C> */
else {
prev = this_n;
this_n = this_n->rlink;
}
}
/* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD>ƪ<EFBFBD><C6AA><EFBFBD><EFBFBD>p */
if(this_n != NULL) {
/* <20><><EFBFBD><EFBFBD><EFBFBD>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD>Ʃ<EFBFBD><C6A9>U<EFBFBD>L<EFBFBD><4C><EFBFBD>k<EFBFBD>l<EFBFBD><6C><EFBFBD>s<EFBFBD>b<EFBFBD><62><EFBFBD><EFBFBD><EFBFBD>p */
if(this_n->llink == NULL && this_n->rlink == NULL) {
clear = this_n;
if(strcmp(name_t, root->name) == 0) /* <20><><EFBFBD>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD>Ƭ<EFBFBD><C6AC><EFBFBD> */
root = NULL;
else {
/* <20>Y<EFBFBD><59><EFBFBD><EFBFBD><EFBFBD>ڡA<DAA1>h<EFBFBD>P<EFBFBD>_<EFBFBD>䬰<EFBFBD><E4ACB0><EFBFBD>l<EFBFBD><6C><EFBFBD>Υk<CEA5>l<EFBFBD><6C> */
if(strcmp(name_t, prev->name) < 0)
prev->llink = NULL;
else
prev->rlink = NULL;
}
free(clear);
}
else { /* <20>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD>`<60>I<EFBFBD><49><EFBFBD><EFBFBD><EFBFBD>k<EFBFBD>l<EFBFBD>𪺦s<F0AABAA6>b */
/* <20>H<EFBFBD><48><EFBFBD>l<EFBFBD><6C><EFBFBD>̤j<CCA4>I<EFBFBD>N<EFBFBD><4E><EFBFBD>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
if(this_n->llink != NULL) {
clear = this_n->llink;
while(clear->rlink != NULL) {
prev = clear;
clear = clear->rlink;
}
strcpy(this_n->name, clear->name);
this_n->score = clear->score;
if(this_n->llink == clear)
this_n->llink = clear->llink;
else
prev->rlink = clear->llink;
}
/* <20>H<EFBFBD>k<EFBFBD>l<EFBFBD><6C><EFBFBD>̤p<CCA4>I<EFBFBD>N<EFBFBD><4E><EFBFBD>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
else {
clear = this_n->rlink;
while(clear->llink != NULL) {
prev = clear;
clear = clear->llink;
}
strcpy(this_n->name, clear->name);
this_n->score = clear->score;
if(this_n->rlink == clear)
this_n->rlink = clear->rlink;
else
prev->llink = clear->rlink;
}
free(clear);
}
bf_count(root);
if(root != NULL) { /* <20>Y<EFBFBD>ڤ<EFBFBD><DAA4>s<EFBFBD>b<EFBFBD>A<EFBFBD>h<EFBFBD>L<EFBFBD>ݧ@<40><><EFBFBD>ŧﵽ */
pivot_find(); /* <20>M<EFBFBD><4D>PIVOT<4F>Ҧb<D2A6>`<60>I */
while(pivot != NULL) {
op = type_find();
switch(op) {
case 11:
type_ll();
break;
case 22:
type_rr();
break;
case 12:
type_lr();
break;
case 21:
type_rl();
break;
} /* end of switch */
bf_count(root);
pivot_find(); /* <20><><EFBFBD><EFBFBD><EFBFBD>ˬd */
}
}
nodecount--; /* <20>Nnode<64><65>1 */
printf(" %s <20>w<EFBFBD>Q<EFBFBD>R<EFBFBD><52>\n", name_t);
}
/* <20>䤣<EFBFBD><E4A4A3><EFBFBD>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD>ơA<C6A1>h<EFBFBD><68><EFBFBD>ܿ<EFBFBD><DCBF>~ */
else
printf(" %s <20>䤣<EFBFBD><E4A4A3>\n", name_t);
}
}
void modify_f(void)
{
char name_t[20];
printf("\n <20>п<EFBFBD><D0BF>J<EFBFBD><4A><EFBFBD><EFBFBD><EFBFBD>s<EFBFBD><73><EFBFBD>m<EFBFBD>W: ");
scanf("%s", name_t);
flushBuffer();
this_n = root;
/* <20>M<EFBFBD><4D><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƩҦb<D2A6>`<60>I */
while((this_n != NULL) && (strcmp(name_t, this_n->name) != 0)) {
if(strcmp(name_t, this_n->name) < 0)
this_n = this_n->llink;
else
this_n = this_n->rlink;
}
/* <20>Y<EFBFBD><59><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ơA<C6A1>h<EFBFBD>C<EFBFBD>X<EFBFBD><58><EFBFBD><EFBFBD><EFBFBD>ơA<C6A1>ín<C3AD>D<EFBFBD><44><EFBFBD>J<EFBFBD>s<EFBFBD><73><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
if(this_n != NULL) {
printf(" ****************************\n");
printf(" <20>m<EFBFBD>W: %s\n", this_n->name);
printf(" <20><><EFBFBD><EFBFBD>: %d\n", this_n->score);
printf(" ****************************\n\n");
printf(" <20>п<EFBFBD><D0BF>J<EFBFBD>s<EFBFBD><73><EFBFBD><EFBFBD><EFBFBD><EFBFBD>: ");
scanf("%d", &this_n->score);
flushBuffer();
printf(" <20><><EFBFBD>Ƨ<EFBFBD><C6A7>s<EFBFBD><73><EFBFBD><EFBFBD>\n");
}
/* <20>S<EFBFBD><53><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƫh<C6AB><68><EFBFBD>ܿ<EFBFBD><DCBF>~ */
else
printf(" %s <20>䤣<EFBFBD><E4A4A3>\n", name_t);
}
void list_f(void)
{
if(root == NULL)
printf("\n AVL Tree <20>L<EFBFBD><4C><EFBFBD><EFBFBD>\n");
else {
printf("\n Name Score\n");
printf(" --------------------\n");
inorder(root); /* <20>ϥΤ<CFA5><CEA4>Ǫk<C7AA><6B><EFBFBD>X<EFBFBD><58><EFBFBD><EFBFBD> */
}
}
/* <20><><EFBFBD>Ǩϥλ<CFA5><CEBB>j */
void inorder(struct student *trees)
{
if(trees != NULL) {
inorder(trees->llink);
printf(" %-15s %3d\n", trees->name, trees->score);
inorder(trees->rlink);
}
}
void bf_count(struct student *trees) /* <20>p<EFBFBD><70>BF<42>ȡA<C8A1>ϥΫ<CFA5><CEAB>Ǫk<C7AA>v<EFBFBD>@<40>p<EFBFBD><70> */
{
if(trees != NULL) {
bf_count(trees->llink);
bf_count(trees->rlink);
/* BF<42>ȭp<C8AD><70><EFBFBD>覡<EFBFBD><E8A6A1><EFBFBD><EFBFBD><EFBFBD>l<EFBFBD>𰪴<EFBFBD><F0B0AAB4>h<EFBFBD>k<EFBFBD>l<EFBFBD><6C><EFBFBD><EFBFBD> */
trees->bf = height_count(trees->llink) - height_count(trees->rlink);
}
}
int height_count(struct student *trees)
{
if(trees == NULL) return 0;
else
if(trees->llink == NULL && trees->rlink == NULL)
return 1;
else
return 1 + (height_count(trees->llink) >
height_count(trees->rlink) ?
height_count(trees->llink) :
height_count(trees->rlink));
}
void pivot_find(void)
{
int i;
this_n = root;
pivot = NULL;
for (i =0; i<=nodecount-1; i++) {
/* <20><>BF<42>Ȫ<EFBFBD><C8AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ȥj<C8A4>󵥩<EFBFBD>1<EFBFBD>A<EFBFBD>h<EFBFBD>NPIVOT<4F><54><EFBFBD>V<EFBFBD><56><EFBFBD>`<60>I */
if(this_n->bf < -1 || this_n->bf > 1) {
pivot = this_n;
if(pivot != root) pivot_prev = prev;
printf("pivot name: %s", this_n->name);
break;
}
if(this_n->bf > 0) { /* <20><><EFBFBD>l<EFBFBD>𪺰<EFBFBD><F0AABAB0>׸<EFBFBD><D7B8><EFBFBD> */
prev = this_n;
this_n = this_n->llink;
}
else if (this_n->bf < 0 ) { /* <20>k<EFBFBD>l<EFBFBD>𪺰<EFBFBD><F0AABAB0>׸<EFBFBD><D7B8><EFBFBD> */
prev = this_n;
this_n = this_n->rlink;
}
}
}
int type_find(void)
{
int i, op_r = 0;
this_n = pivot;
for(i = 0; i < 2; i++) {
if(this_n->bf > 0) { /* <20><><EFBFBD>l<EFBFBD>𪺰<EFBFBD><F0AABAB0>׸<EFBFBD><D7B8><EFBFBD> */
this_n = this_n->llink;
if(op_r == 0) op_r+=10;
else op_r++;
}
else if (this_n->bf < 0 ) { /* <20>k<EFBFBD>l<EFBFBD>𪺰<EFBFBD><F0AABAB0>׸<EFBFBD><D7B8><EFBFBD> */
this_n = this_n->rlink;
if(op_r == 0) op_r+=20;
else op_r+=2;
}
}
/* <20>Ǧ^<5E><>11<31>B22<32>B12<31>B21<32><31><EFBFBD>O<EFBFBD>N<EFBFBD><4E>LL<4C>BRR<52>BLR<4C>BRL<52><4C><EFBFBD>A */
return op_r;
}
void type_ll(void) /* LL<4C><4C><EFBFBD>A */
{
struct student *pivot_next, *temp;
pivot_next = pivot->llink;
temp = pivot_next->rlink;
pivot_next->rlink = pivot;
pivot->llink = temp;
if(pivot == root) root = pivot_next;
else
if(pivot_prev->llink == pivot)
pivot_prev->llink = pivot_next;
else
pivot_prev->rlink = pivot_next;
}
void type_rr(void) /* RR<52><52><EFBFBD>A */
{
struct student *pivot_next, *temp;
pivot_next = pivot->rlink;
temp = pivot_next->llink;
pivot_next->llink = pivot;
pivot->rlink = temp;
if(pivot == root) root = pivot_next;
else
if(pivot_prev->llink == pivot)
pivot_prev->llink = pivot_next;
else
pivot_prev->rlink = pivot_next;
}
void type_lr(void) /* LR<4C><52><EFBFBD>A */
{
struct student *pivot_next, *temp;
pivot_next = pivot->llink;
temp = pivot_next->rlink;
pivot->llink = temp->rlink;
pivot_next->rlink = temp->llink;
temp->llink = pivot_next;
temp->rlink = pivot;
if(pivot == root) root = temp;
else
if(pivot_prev->llink == pivot)
pivot_prev->llink = temp;
else
pivot_prev->rlink = temp;
}
void type_rl(void) /* RL<52><4C><EFBFBD>A */
{
struct student *pivot_next, *temp;
pivot_next = pivot->rlink;
temp = pivot_next->llink;
pivot->rlink = temp->llink;
pivot_next->llink = temp->rlink;
temp->rlink = pivot_next;
temp->llink = pivot;
if(pivot == root) root = temp;
else
if(pivot_prev->llink == pivot)
pivot_prev->llink = temp;
else
pivot_prev->rlink = temp;
}
void flushBuffer(void)
{
while(getchar() != '\n')
continue;
}
Reference in New Issue Copy Permalink