Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //реализицаия АВЛ-дерева
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #define linesPerPage 20
- typedef struct tnode {
- char* word;
- int ct;
- int pageNum;
- int stringNum;
- unsigned char height;
- struct tnode* left;
- struct tnode* right;
- }tnode;
- char* eatword (FILE*, FILE*, int*);
- void man(int);
- unsigned char treeheight(tnode* node) {
- return node ? node->height : 0; }
- int bfactor(tnode* node){
- return treeheight(node->right) - treeheight(node->left);}
- void fixheight(tnode* node) {
- unsigned char leftHeight = treeheight(node->left);
- unsigned char rightHeight = treeheight(node->right);
- node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; }
- tnode* rotateRight(tnode* node) {
- tnode* tempNode = node->left;
- node->left = tempNode->right;
- tempNode->right = node;
- fixheight(node);
- fixheight(tempNode);
- return tempNode; }
- tnode* rotateLeft(tnode* node) {
- tnode* tempNode = node->right;
- node->right = tempNode->left;
- tempNode->left = node;
- fixheight(node);
- fixheight(tempNode);
- return tempNode; }
- tnode* balance(tnode* node) {
- fixheight(node);
- if (bfactor(node) == 2) {
- if (bfactor(node->right) < 0)
- node->right = rotateRight(node->right);
- return rotateLeft(node); }
- if (bfactor(node) == -2) {
- if (bfactor(node->left) > 0)
- node->left = rotateLeft(node->left);
- return rotateRight(node); }
- return node;
- }
- tnode* addtree(tnode* node, char* word, int str, int page) {
- if (node == NULL) {
- node = (tnode*)malloc(sizeof(tnode));
- node->left = NULL;
- node->right = NULL;
- node->word = (char*)malloc(strlen(word) + 1);
- strcpy(node->word, word);
- node->ct = 1;
- node->stringNum = str;
- node->pageNum = page;
- return node; }
- else {
- int cmp = strcmp(word, node->word);
- if (cmp == 0) {
- node->ct += 1;
- node->stringNum = str;
- node->pageNum = page; }
- else if (cmp < 0)
- node->left = addtree(node->left, word, str, page);
- else
- node->right = addtree(node->right, word, str, page); }
- return balance(node);
- }
- void treeprint(tnode *p) {
- if (p != NULL) {
- treeprint(p->left);
- printf("%-20s%10d%15d%15d\n", p->word, p->ct, p->pageNum, p->stringNum);
- treeprint(p->right); }
- }
- void nodefree(struct tnode* node){
- if (node == NULL) return;
- nodefree(node->left);
- nodefree(node->right);
- free(node->word);
- free(node);
- node = NULL;}
- void main(int argc, char * argv[]) {
- if (argc != 2) man(2);
- if (strcmp(argv[1], "-?") == 0) man(0);
- tnode* root = NULL;
- char chr, *word;
- int i = 0, str = 1, page = 1;
- FILE *file, *tmpFile;
- tmpFile = tmpfile();
- if ((file = fopen(argv[1], "r")) == NULL) man(3);
- while ((word = eatword(file, tmpFile, &str)) != NULL){
- root = addtree(root, word, str, page);
- if (str >= linesPerPage+1) {
- page++;
- str = 1; }
- }
- fclose(file);
- printf("%d страниц и %d строк в файле \n\n", page, linesPerPage*(page-1)+str);
- printf("Word Repeats Page Line\n");
- treeprint(root);
- nodefree(root);
- }
- char* eatword(FILE *file, FILE *tmpFile, int *stringCount) {
- char c, *word;
- int i = 0;
- fpos_t pos;
- fgetpos(tmpFile, &pos);
- c = fgetc(file);
- while ((c == '\n') || (c == '\r')) {(*stringCount)++; c = fgetc(file);}
- while (((c >= '0') && (c <= '9')) ||
- ((c >= 'A') && (c <= 'Z')) ||
- ((c >= 'a') && (c <= 'z'))) {
- fputc(c, tmpFile);
- c = fgetc(file);
- i++; }
- if (c == EOF) return NULL;
- fputc('\0', tmpFile);
- fsetpos(tmpFile, &pos);
- word = malloc(i+1);
- fgets(word, i+1, tmpFile);
- fsetpos(tmpFile, &pos);
- if ((c == '\n') || (c == '\r')) (*stringCount)++;
- return word;
- }
- void man(int var) {
- if (var == 0) printf("Программа предназначена для работы с файлами.\nФайл выбирается при помощи аргумента.\nПример: ./a.out file1.txt\nВызов справки -?.\n");
- if (var == 2) printf("Ошибка аргуметов. Укажите файлы при помощи аргумента. -? для справки.\n");
- if (var == 3) printf("Файл не найден.\n");
- exit(0);
- }
Advertisement
Add Comment
Please, Sign In to add comment