Vuvko's Testing Forum

Объявление

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.

Вы здесь » Vuvko's Testing Forum » Домашняя работа по праку гр. 104 » Файлы и структуры данных (07)

Файлы и структуры данных (07)

Страница: 1

Сообщений 1 страница 12 из 12

1

  • Автор: vuvko
  • Администратор
  • Зарегистрирован: 2009-04-12
  • Приглашений: 0
  • Сообщений: 85
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    1 день 4 часа
  • Последний визит:
    2022-11-01 19:24:04

Во всех кодах сделаны ошибки...

Задача 07-2: Domain Name System

Изначально заводится структура данных (можно и без неё, тогда придёться делать 2 массива), которая хранит в себе имя компьютера и его ip-адрес. Затем все известные данные заносятся в массив, каждый элемент которого - созданная структура. В конце каждое введённое имя ищется в сохранённом массиве.
Если попытаться сдачь задачу в таком виде, то мы не пройдём один из тестов по времени. Значит, нужно нашу базу имён-адресов каким-то образом проиндексировать. Здесь поможет хэш-таблица. Для разрешение коллизий я использовал метод цепочек. Важной частью здесь оказалось использование "хорошей" хэш-функции, поэтому в коде ниже она сделана не совсем верно (21 тест не пройдёт по времени).

Код:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum {
    SIZE_HASH = 500000
};

typedef struct copmuter{
    char *name;
    long long int ip;
} computer;

typedef struct hash{
    computer comp;
    struct hash *next;
} hash;

int
hashfunc(char *str)
{
    int i, r = 0;
    for(i = 0; str[i]; i++){
        r = (r + str[i]) % SIZE_HASH;
    }
    return r;
}

void
addcomputer(hash *dnsdb[], char *name, long long int ip)
{
    int i = hashfunc(name);
    hash *list;
    list = (hash*)malloc(sizeof(hash));
    list->comp.ip = ip;
    list->comp.name = (char*)malloc((strlen(name) + 1) * sizeof(char));
    strcpy(list->comp.name, name);
    list->next = dnsdb[i];
    dnsdb[i] = list;
}

long long int
findip(hash *head, char *str)
{
    hash *list = head;
    while(list){
        if(!strcmp(list->comp.name, str))
            return list->comp.ip;
        list = list->next;
    }
    return -1;
}

int
main(void)
{
    FILE *input = fopen("input.txt", "r");
    FILE *output = fopen("output.txt", "w");
    hash *dnsdb[SIZE_HASH];
    char buf[101];
    int n, m, i, idx;
    long long int tmpip, ip;
    for(i = 0; i < SIZE_HASH; i++){
        dnsdb[i] = NULL;
    }
    fscanf(input, "%d", &n);
    for(i = 0; i < n; i++){
        fscanf(input, "%s%lld", buf, &tmpip);
        addcomputer(dnsdb, buf, tmpip);
    }
    fscanf(input, "%d", &m);
    for(i = 0; i < m; i++){
        fscanf(input, "%s", buf);
        idx = hashfunc(buf);
        if(dnsdb[idx]){
            ip = findip(dnsdb[idx], buf);
            if(ip != -1)
                fprintf(output, "%lld\n", ip);
            else
                fprintf(output, "-1\n");
        } else
            fprintf(output, "-1\n");
    }

    fclose(input);
    fclose(output);
    return 0;
}

0

2

  • Автор: vuvko
  • Администратор
  • Зарегистрирован: 2009-04-12
  • Приглашений: 0
  • Сообщений: 85
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    1 день 4 часа
  • Последний визит:
    2022-11-01 19:24:04

Задача 07-3-a: 1-перемешивание

В задаче логично использовать списки, а не массивы, ведь для того, чтобы передвинуть часть списка в начало, нужно порядка 10 итераций. Для массива же количество итераций сравнимо с количеством элементов массива. Но! если использовать обычный двунаправленный (или однонаправленный) список, подвешенный даже с 2х концов, то задача не пройдёт по времени, так как для того, чтобы добраться до i-го элемента списка, нам нужно совершить i итерации. Чтобы добираться до каждого элемента списка за О(1) нам и понадобится массив указателей на каждый элемент списка. Причем в массиве будет всегда выполняться условие, что a[i] = i.

В данном коде есть ошибка в функции создания списка.

Код:
#include <stdio.h>
#include <stdlib.h>

typedef struct elem {
    struct elem *next;
    struct elem *prev;
    int key;
} elem;

void
makelist(elem *list, int n, elem *array[], int d)
{
    if(d <= n){
        list->key = d;
        array[d] = &(*list);
         ist->next = (elem*)malloc(sizeof(elem));
        array[d + 1] = (elem*)malloc(sizeof(elem));
        list->next->prev = &(*list);
        makelist(list->next, n, array, d + 1);
    }
}

void
printlist(elem *list)
{
    if(list != NULL){
        printf("%d ", list->key);
        printlist(list->next);
    }
}

void
fprintlist(FILE *output, elem *list)
{
    if(list != NULL){
        fprintf(output, "%d ", list->key);
        fprintlist(output, list->next);
    }
}

elem *findtail(elem *list)
{
    if(list->next != NULL)
        return findtail(list->next);
    else
        return list;
}

void
freelist(elem *list)
{
    if(list != NULL){
        freelist(list->next);
        free(list);
    }
}

int
main(void)
{
    FILE *input = fopen("input.txt", "r");
    FILE *output = fopen("output.txt", "w");
    elem *list = NULL, *tail = NULL, *p = NULL;
    elem **array = NULL;
    int n, m, i, ptrans;
    fscanf(input, "%d%d", &n, &m);
    list = (elem*)malloc(sizeof(elem));
    list->prev = NULL;
    tail = (elem*)malloc(sizeof(elem));
    array = (elem**)malloc((n + 1) * sizeof(elem*));
    array[1] = (elem*)malloc(sizeof(elem));
    makelist(list, n, array, 1);
    tail = findtail(list);
    for(i = 0; i < m; i++){
        fscanf(input, "%d", &ptrans);
        tail->next = &(*list);
        p = &(*array[ptrans]);
        list->prev = tail;
        list =  &(*(p));
        p->prev->next = NULL;
        tail = (elem*)malloc(sizeof(elem));
        tail = &(*p->prev);
        p->prev = NULL;
    }
    fprintlist(output, list);
    fclose(input);
    fclose(output);
    freelist(list);
    free(array);
    free(tail);
    return 0;
}

0

3

  • Автор: vuvko
  • Администратор
  • Зарегистрирован: 2009-04-12
  • Приглашений: 0
  • Сообщений: 85
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    1 день 4 часа
  • Последний визит:
    2022-11-01 19:24:04

Задача 07-3-b: 2-перемешивание

Задача абсолютно аналогична предыдущей.

Код:
#include <stdio.h>
#include <stdlib.h>

typedef struct elem {
    struct elem *next;
    struct elem *prev;
    int key;
} elem;

void
makelist(elem *list, int n, elem *array[], int d)
{
    int i;
    elem *head = &(*list);
    for(i = 1; i < n; i++){
        list->key = i;
        array[i] = &(*list);
        list->next = (elem*)malloc(sizeof(elem));
        array[i + 1] = (elem*)malloc(sizeof(elem));
        list->next->prev = list;
        list = list->next;
    }
    list->key = n;
    array[n] = list;
    list = head;
}

void
printlist(elem *list)
{
    elem *head = &(*list);
    while(list != NULL){
        printf("%d ", list->key);
        list = list->next;
    }
    list = head;
}

void
fprintlist(FILE *output, elem *list)
{
    elem *head = &(*list);
    while(list != NULL){
        fprintf(output, "%d ", list->key);
        list = list->next;
    }
    list = head;
}

void
freelist(elem *list)
{
    if(list != NULL){
        freelist(list->next);
        free(list);
    }
}

int
main(void)
{
    FILE *input = fopen("input.txt", "r");
    FILE *output = fopen("output.txt", "w");
    elem *list = NULL, *p1 = NULL, *p2 = NULL;
    elem **array = NULL;
    int n, m, i, ptrans1, ptrans2;
    fscanf(input, "%d%d", &n, &m);
    list = (elem*)malloc(sizeof(elem));
    list->prev = NULL;
    array = (elem**)malloc((n + 1) * sizeof(elem*));
    array[1] = (elem*)malloc(sizeof(elem));
    makelist(list, n, array, 1);
    for(i = 0; i < m; i++){
        fscanf(input, "%d%d", &ptrans1, &ptrans2);
        if(ptrans1 != list->key){
            p2 = array[ptrans2];
            p1 = array[ptrans1];
            if(p2->next != NULL){
                p2->next->prev = p1->prev;
            }
            p1->prev->next = p2->next;
            list->prev = p2;
            p1->prev = NULL;
            p2->next = list;
            list = p1;
        }
    }
    fprintlist(output, list);
    fclose(input);
    fclose(output);
    freelist(list);
    free(array);
    return 0;
}

0

4

  • Автор: vuvko
  • Администратор
  • Зарегистрирован: 2009-04-12
  • Приглашений: 0
  • Сообщений: 85
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    1 день 4 часа
  • Последний визит:
    2022-11-01 19:24:04

Задача 07-4-a: Сортировка списка

Не все сортировки, подходящие для массивов, хороши для списков, потому что (как уже говорилось ранее), чтобы попасть в i-й элемент списка нужно совершить i итераций. Поэтому нам подошел бы алгоритм, который не требует много перемещаться по списку. Алгоритм сортировки пузырьком мне сразу пришел в голову.

Код:
#include <stdio.h>
#include <stdlib.h>

typedef struct elem {
    struct elem *next;
    struct elem *prev;
    int data;
} elem;

void
printlist(elem *list)
{
    elem *head = list;
    while(list != NULL){
        printf("%d ", list->data);
        list = list->next;
    }
    list = head;
}

void
freelist(elem *list)
{
    if(list != NULL){
        freelist(list->next);
        free(list);
    }
}

void
fprintlist(FILE *output, elem *list)
{
    if(list != NULL){
        fprintf(output, "%d ", list->data);
        fprintlist(output, list->next);
    }
}

int
main(void)
{
    FILE *input = fopen("input.txt", "r");
    FILE *output = fopen("output.txt", "w");
    elem *list, *head;
    int num;
    char fl = 1;
    list = (elem*)malloc(sizeof(elem));
    list->prev = NULL;
    head = list;
    while(fscanf(input, "%d", &num) != EOF){
        list->data = num;
        list->next = (elem*)malloc(sizeof(elem));
        list->next->prev = list;
        list = list->next;
    }
    list = head;
    while(fl){
        fl = 0;
        while(list->next != NULL){
            if(list->data > list->next->data){
                fl = 1;
                num = list->data;
                list->data = list->next->data;
                list->next->data = num;
            }
            list = list->next;
        }
        list = head;
    }
    fprintlist(output, list);
    fclose(input);
    fclose(output);
    freelist(list);
    return 0;
}

0

5

  • Автор: vuvko
  • Администратор
  • Зарегистрирован: 2009-04-12
  • Приглашений: 0
  • Сообщений: 85
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    1 день 4 часа
  • Последний визит:
    2022-11-01 19:24:04

Задача 07-1: Статистика текста

Задача на самом деле достаточно простая, надо всего лишь строго следовать определениям, данным в условии. Главное:
1) Пустой считается строка, либо не содержащая символов вовсе, либо состоящая лишь из символов пробела.
2) Абзацы разделены одной или более пустыми строками.
3) Слово может содержать в себе заглавные или строчные латинские буквы, а также дефисы (символы «минус»). Слово начинается с буквы и заканчивается буквой.
4) Переносы
Итак, считывать текст лучше всего (имхо) построчно, затем обрабатывать считанную строку. Если она пустая и ранее мы не засчитали считанные абзац (флаг = 0), то увеличиваем кол-ыо абзацев (и присваиваем флаг 1).

В коде сделана ошибка, но её достаточно просто найти.

Код:
#include <stdio.h>
#include <stdlib.h>

void
count(char *str, int *w, int *s)
{
    int i = 0;
    while(str[i] != '\n' && str[i]){
        while((str[i] < 'a' || str[i] > 'z') && (str[i] < 'A' || str[i] > 'Z') && str[i] != '\n' && str[i]){
            i++;
        }
        if(str[i] != '\n' && str[i]){
            while((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z') || str[i] == '-')
                i++;
            if((str[i - 1] >= 'a' && str[i - 1] <= 'z') || (str[i - 1] >= 'A' && str[i - 1] <= 'Z'))
               (*w)++;
            while(str[i] == ' ')
                i++;
            if(str[i] == '.'){
                (*s)++;
                i++;
            }
        }
    }
}

char
empty(char *str)
{
    int i = 0;
    while(str[i] == ' ')
        i++;
    if(str[i] == '\n' || !str[i])
        return 1;
    else
        return 0;
}

int
main(void)
{
    FILE *input = fopen("input.txt", "r");
    char buf[20001], fl = 1, fl2 = 0;
    int w, s, p, tmpw, tmps;
    w = s = p = 0;
    while(fgets(buf, 20001, input) != NULL){
        tmpw = tmps = 0;
        count(buf, &tmpw, &tmps);
        fl2 = empty(buf);
        if(fl2 && !fl){
            p++;
            fl = 1;
        } else if(!fl2)
            fl = 0;
        s += tmps;
        w += tmpw;
    }
    fclose(input);
    FILE *output = fopen("output.txt", "w");
    fprintf(output, "%d %d %d\n", w, s, p);
    printf("%d %d %d\n", w, s, p);
    fclose(output);
    return 0;
}

0

6

  • Автор: vuvko
  • Администратор
  • Зарегистрирован: 2009-04-12
  • Приглашений: 0
  • Сообщений: 85
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    1 день 4 часа
  • Последний визит:
    2022-11-01 19:24:04

Задача 07-5-a: Деревья поиска

Самое сложное в задаче - написать функцию удаления из дерева. Все алгоритмы операций с деревом поиска можно найти здесь.

Функцию поиска элемента в дереве и процедуру удаления дерева предлагается написать самим.

Код:
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    struct node *parent;
    struct node *left;
    struct node *right;
    int key;
    int data;
} node;

void
adddata(node **root, node *cur)
{
    if(*root){
        if(cur->key == (*root)->key){
            (*root)->data = cur->data;
            free(cur);
            cur = NULL;
        } else if(cur->key > (*root)->key){
            if((*root)->right){
                adddata(&(*root)->right, cur);
            } else{
                cur->parent = *root;
                (*root)->right = cur;
            }
        } else {
            if((*root)->left)
                adddata(&(*root)->left, cur);
            else{
                cur->parent = *root;
                (*root)->left = cur;
            }
        }
    } else
        *root = cur;
}

node *findmin(node *tree)
{
    if(tree->left)
        return findmin(tree->left);
    else
        return tree;
}

node *
findkey(node *tree, int key)
{
    if(tree){
        if(tree->key == key)
            return tree;
        if(tree->key > key)
            return findkey(tree->left, key);
        else
            return findkey(tree->right, key);
    }
    return NULL;
}

node *
findroot(node *tree)
{
    if(tree->parent)
        return findroot(tree->parent);
    return tree;
}

node *
findsucc(node *tree)
{
    if(tree->right)
        return findmin(tree->right);
    node *cur = tree->parent;
    while(cur && tree == cur->right){
        tree = cur;
        cur = cur->parent;
    }
    return cur;
}

node *
dropkey(node *tree, int key)
{
    node *cur = findkey(tree, key);
    node *del, *tmp;
    if(!cur) return NULL;
    if(!cur->left || !cur->right){
        del = cur;
    } else {
        del = findsucc(cur);
    }
    if(del->left)
        tmp = del->left;
    else
        tmp = del->right;
    if(tmp){
        tmp->parent = del->parent;
    }
    if(!del->parent){
        return del;
    } else if(del == del->parent->left){
        del->parent->left = tmp;
    } else {
        del->parent->right = tmp;
    }
    if(del != cur){
        cur->key = del->key;
        cur->data = del->data;
    }
    return del;
}

int
main(void)
{
    node *root = NULL, *cur = NULL;
    char c;
    int key, data;
    while((c = getchar()) != 'F'){
        if(c == 'A'){
            scanf("%d%d", &key, &data);
            cur = (node*)malloc(sizeof(node));
            cur->key = key;
            cur->data = data;
            cur->left = NULL;
            cur->right = NULL;
            cur->parent = NULL;
            adddata(&root, cur);
        } else if(c == 'S'){
            scanf("%d", &key);
            cur = finddata(root, key);
            if(cur){
                printf("%d %d\n", cur->key, cur->data);
            }
        } else if(c == 'D'){
            scanf("%d", &key);
            cur = dropkey(root, key);
            if(cur){
                if(cur == root){
                    if(!root->left)
                        root = root->right;
                    else if(!root->right)
                        root = root->left;
                }
                free(cur);
            }
        }
    }
    return 0;
}

0

7

  • Автор: vuvko
  • Администратор
  • Зарегистрирован: 2009-04-12
  • Приглашений: 0
  • Сообщений: 85
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    1 день 4 часа
  • Последний визит:
    2022-11-01 19:24:04

Задача 07-6-a: Простой калькулятор

Данная задача, имхо, является одной из простейших в данном контесте.
Т.к. скобок нет и приоритет всех операций одинаковый, то можно считывать выражение вида <число><операция><число> и запоминать результат в отдельной переменной, с которой затем будем работать.

Код:
#include <stdio.h>
#include <stdlib.h>

int
main(void)
{
    FILE *input = fopen("input.txt", "r");
    FILE *output = fopen("output.txt", "w");
    char op, c;
    long long int num1, num2;
    fscanf(input, "%lld", &num1);
    while((c = fgetc(input)) != EOF){
        num2 = 0;
        op = c;
        fscanf(input, "%lld", &num2);
        if(op == '+')
            num1 += num2;
        else
            num1 -= num2;
    }
    fprintf(output, "%lld\n", num1);
    fclose(input);
    fclose(output);
    return 0;
}

0

8

  • Автор: vuvko
  • Администратор
  • Зарегистрирован: 2009-04-12
  • Приглашений: 0
  • Сообщений: 85
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    1 день 4 часа
  • Последний визит:
    2022-11-01 19:24:04

Задача 07-7-a: Удаление

Хорошая задача на понимае списков. Самое сложное в задаче - реализация списка и его ввод (что не является на самом деле сложным, достаточно лишь аккуратно работать с указателями).

Код:
#include <stdio.h>
#include <stdlib.h>

typedef struct elem{
    struct elem *next;
    int data;
} elem;

int
find(int data, elem *list)
{
    if(list != NULL){
        if(list->data == data)
            return 1;
        else
            return find(data, list->next);
    } else {
        return 0;
    }
}

void
fprintlist(FILE *output, elem *list, elem *except)
{
    if(list != NULL){
        if(!find(list->data, except))
            fprintf(output, "%d ", list->data);
        fprintlist(output, list->next, except);
    }
}

void
freelist(elem *list)
{
    if(list != NULL){
        freelist(list->next);
        free(list);
    }
}

void
readlist(FILE *input, elem *list)
{
    int n;
    fscanf(input, "%d", &n);
    if(n != -1){
        list->data = n;
        list->next = (elem*)malloc(sizeof(elem));
        readlist(input, list->next);
    } else {
        list->data = -1;
    }
}

int
main(void)
{
    FILE *input = fopen("input.txt", "r");
    FILE *output = fopen("output.txt", "w");
    elem *list = NULL, *except = NULL;
    list = (elem*)malloc(sizeof(elem));
    readlist(input, list);
    except = (elem*)malloc(sizeof(elem));
    readlist(input, except);
    fprintlist(output, list, except);
    fclose(input);
    fclose(output);
    freelist(list);
    freelist(except);
    return 0;
}

0

9

  • Автор: vuvko
  • Администратор
  • Зарегистрирован: 2009-04-12
  • Приглашений: 0
  • Сообщений: 85
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    1 день 4 часа
  • Последний визит:
    2022-11-01 19:24:04

Задача 07-7-b: Удаление наоборот

Аналогичная задача...

Код:
#include <stdio.h>
#include <stdlib.h>

typedef struct elem{
    struct elem *next;
    int data;
} elem;

int
find(int data, elem *list)
{
    if(list != NULL){
        if(list->data == data)
            return 1;
        else
            return find(data, list->next);
    } else {
        return 0;
    }
}

void
fprintlist(FILE *output, elem *list, elem *except)
{
    if(list != NULL){
        if(!find(list->data, except))
            fprintf(output, "%d ", list->data);
        fprintlist(output, list->next, except);
    }
}

void
freelist(elem *list)
{
    if(list != NULL){
        freelist(list->next);
        free(list);
    }
}

void
readlist(FILE *input, elem *list)
{
    int n;
    fscanf(input, "%d", &n);
    if(n != -1){
        list->data = n;
        list->next = (elem*)malloc(sizeof(elem));
        readlist(input, list->next);
    }
}

int
main(void)
{
    FILE *input = fopen("input.txt", "r");
    FILE *output = fopen("output.txt", "w");
    elem *list = NULL, *except = NULL;
    except = (elem*)malloc(sizeof(elem));
    readlist(input, except);
    list = (elem*)malloc(sizeof(elem));
    readlist(input, list);
    fprintlist(output, list, except);
    fclose(input);
    fclose(output);
    freelist(list);
    freelist(except);
    return 0;
}

0

10

  • Автор: vuvko
  • Администратор
  • Зарегистрирован: 2009-04-12
  • Приглашений: 0
  • Сообщений: 85
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    1 день 4 часа
  • Последний визит:
    2022-11-01 19:24:04

Задача 07-8: Слова

Код:
#include <stdio.h>
#include <stdlib.h>

typedef struct elem{
    struct elem *next;
    struct elem *prev;
    char letter;
} elem;

typedef struct node{
    struct node *next;
    struct node *prev;
    elem *down;
    int length;
} node;

void
fprintlist(FILE *output, node *list)
{
    int middle = 0, i = 0;
    elem *word = NULL;
    if(list != NULL){
        if(list->length > 1){
            if(list->prev != NULL)
                fprintf(output, " ");
            word = list->down;
            if(list->length % 2 == 1){
                middle = (list->length + 1) / 2;
                for(i = 1; word != NULL; i++){
                    if(i != middle)
                        fprintf(output, "%c", word->letter);
                    word = word->next;
                }
            } else {
                while(word != NULL){
                    fprintf(output, "%c", word->letter);
                    word = word->next;
                }
            }
        }
        fprintlist(output, list->next);
    }
}

void
freeword(elem *word)
{
    if(word != NULL){
        freeword(word->next);
        free(word);
    }
}

void
freelist(node *list)
{
    if(list != NULL){
        freelist(list->next);
        freeword(list->down);
        free(list);
    }
}

int
main(void)
{
    FILE *input = fopen("words.in", "r");
    FILE *output = fopen("words.out", "w");
    node *list, *head;
    elem *word;
    list = (node*)malloc(sizeof(node));
    list->prev = NULL;
    list->down = (elem*)malloc(sizeof(elem));
    list->down->prev = NULL;
    word = list->down;
    head = &(*list);
    char c = ' ';
    int len = 0;
    while(c == ' ')
        c = fgetc(input);
    while(c != '.' && c != EOF){
        if(c == ' ' && len > 0){
            list->length = len;
            len = 0;
            list->next = (node*)malloc(sizeof(node));
            list->next->prev = list;
            list = list->next;
            list->down = (elem*)malloc(sizeof(elem));
            word = word->prev;
            word = list->down;
        }
        while(c == ' ')
                c = fgetc(input);
        if(c != EOF && c != '.'){
            word->letter = c;
            len++;
            word->next = (elem*)malloc(sizeof(elem));
            word->next->prev = word;
            word = word->next;
            c = fgetc(input);
        }
    }
    if(word->prev != NULL){
        word = word->prev;
        word->next = NULL;
    } else {
        word->next = NULL;
    }
    list->next = NULL;
    list->length = len;
    list = head;
    word = list->down;
    fprintlist(output, list);
    fprintf(output, ".\n");

    freelist(list);
    fclose(input);
    fclose(output);
    return 0;
}

0

11

  • Автор: vuvko
  • Администратор
  • Зарегистрирован: 2009-04-12
  • Приглашений: 0
  • Сообщений: 85
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    1 день 4 часа
  • Последний визит:
    2022-11-01 19:24:04

Задача 07-4-b: Сортировка большого списка

Максимальное число элементов в списке говорит о том, что алгоритмы, работающие за О(n^2) в этой задаче не пройдут, т.к. 1 секунда ~10^9 итераций. Но, алгоритмы, работающие для массивов за О(nlogn), могут не работать хорошо для списков, ведь до i-го элемента списка мы добираемся за О(i).
Я реализовал несколько модифицированную сортировку слиянием для списков. Мы не вызывает функцию рекурсивно, пока не получим массив из одного элемента, мы сразу имеет список списков, каждый из которых состоит из 1го элемента. Для каждой пары списков (i и i+1) мы производим слияние, записываем результат в i, и удаляем ссылку на i+1. И так, пока у нас не получится один список.

Код:
#include <stdio.h>
#include <stdlib.h>

typedef struct elem{
    struct elem *next;
    int data;
} elem;

typedef struct node{
    struct node *next;
    struct elem *down;
} node;

void
freelist(elem *head)
{
    if(head){
        freelist(head->next);
        free(head);
    }
}

void
printlist(elem *head)
{
    elem *list = head;
    while(list){
        printf("%d\n", list->data);
        list = list->next;
    }
}

void
fprintlist(FILE *output, elem *head)
{
    elem *list = head;
    while(list){
        fprintf(output, "%d\n", list->data);
        list = list->next;
    }
}

elem *merge(elem *head, elem *buf)
{
    elem *cur1 = head, *cur2 = buf;
    elem *tmp = NULL, *h = NULL;
    h = (elem*)malloc(sizeof(elem));
    h->next = NULL;
    h->data = 0;
    tmp = h;
    while(cur1 && cur2){
        if(cur1->data > cur2->data){
            tmp->next = cur2;
            cur2 = cur2->next;
        } else {
            tmp->next = cur1;
            cur1 = cur1->next;
        }
        tmp = tmp->next;
    }
    return h;
}

elem *
createlist(node *head)
{
    if(!head) return NULL;
    while(head->next){
        node *t = head;
        while(t){
            if(t->next)
                t->down = merge(t->down, t->next->down);
            t = t->next;
        }
    }
    return head->down;
}

int
main(void)
{
    FILE *input = fopen("input.txt", "r");
    FILE *output = fopen("output.txt", "w");
    elem *head = NULL;
    node *cur = NULL, *buf = NULL;
    int num;
    buf = (node*)malloc(sizeof(node));
    buf->next = NULL;
    buf->down = (elem*)malloc(sizeof(elem));
    buf->down->data = 0;
    buf->down->next = NULL;
    cur = buf;
    while(fscanf(input, "%d", &num) != EOF){
        cur->next = (node*)malloc(sizeof(node));
        cur = cur->next;
        cur->next = NULL;
        cur->down = (elem*)malloc(sizeof(elem));
        cur->down->data = num;
        cur->down->next = NULL;
    }
    head = createlist(buf->next);
    fprintlist(output, head);
    fclose(input);
    fclose(output);
    return 0;
}

0

12

  • Автор: vuvko
  • Администратор
  • Зарегистрирован: 2009-04-12
  • Приглашений: 0
  • Сообщений: 85
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    1 день 4 часа
  • Последний визит:
    2022-11-01 19:24:04

Задача 07-6-b: Непростой калькулятор

Реализована через обратную польскую запись.

Код:
#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    long long int num;
    char op;
} Node;

typedef struct StackNode{
    struct StackNode *next;
    Node elem;
} StackNode;

void
freelist(StackNode *head)
{
    if(head){
        freelist(head->next);
        free(head);
    }
}

long long int
readnum(FILE *input, char *c)
{
    long long int num = *c - '0';
    while((*c = fgetc(input)) >= '0' && *c <= '9'){
        num = num * 10 + *c - '0';
    }
    return num;
}

int
priority(char op)
{
    if(op == '+' || op =='-')
        return 1;
    else if(op == '*' || op == '/')
        return 2;
}

long long int
count(StackNode *stack)
{
    StackNode *cur = stack->next;
    long long int res = 0, tmp = 0;
    switch (cur->elem.op){
        case '+':
            res = count(cur) + count(cur);
            stack->next = cur->next;
            break;
        case '-':
            tmp = count(cur);
            res = count(cur) - tmp;
            stack->next = cur->next;
            break;
        case '*':
            res = count(cur) * count(cur);
            stack->next = cur->next;
            break;
        case '/':
            tmp = count(cur);
            res = count(cur) / tmp;
            stack->next = cur->next;
            break;
        default:
            res = cur->elem.num;
            stack->next = cur->next;
            break;
    }
    return res;
}

int
main(void)
{
    FILE *input = fopen("input.txt", "r");
    FILE *output = fopen("output.txt", "w");
    StackNode *stack, *opstack, *bottom, *opbot, *tmp = NULL, *buf = NULL;
    char c, fl = 1, op;
    long long int num;
    stack = (StackNode*)malloc(sizeof(StackNode));
    stack->next = NULL;
    stack->elem.op = '#';
    stack->elem.num = 0;
    bottom = stack;
    opstack = (StackNode*)malloc(sizeof(StackNode));
    opstack->next = NULL;
    opstack->elem.op = '#';
    opstack->elem.num = 0;
    opbot = opstack;
    c = fgetc(input);
    while(c != EOF){
        fl = 1;
        while(c == ' ')
            c = fgetc(input);
        op = c;
        num = 0;
        if(c >= '0' && c <= '9'){
            num = readnum(input, &c);
            op = 'n';
            if(c != ' ')
                fl = 0;
        }
        tmp = (StackNode*)malloc(sizeof(StackNode));
        tmp->next = NULL;
        tmp->elem.op = op;
        tmp->elem.num = num;

        if(op == 'n'){
            tmp->next = stack;
            stack = tmp;
        } else if(op == '('){
            tmp->next = opstack;
            opstack = tmp;
        } else if(op == ')'){
            while(opstack->elem.op != '('){
                buf = opstack->next;
                opstack->next = stack;
                stack = opstack;
                opstack = buf;
            }
            free(tmp);
            opstack = opstack->next;
        } else {
            while(priority(op) <= priority(opstack->elem.op)){
                buf = opstack->next;
                opstack->next = stack;
                stack = opstack;
                opstack = buf;
            }
            tmp->next = opstack;
            opstack = tmp;
        }
        if(fl)
            c = fgetc(input);
    }
    while(opstack){
        buf = opstack->next;
        opstack->next = stack;
        stack = opstack;
        opstack = buf;
    }
    num = count(stack);
    fprintf(output, "%lld\n", num);
    fclose(input);
    fclose(output);
    freelist(stack);
    return 0;
}

0

Страница: 1

Вы здесь » Vuvko's Testing Forum » Домашняя работа по праку гр. 104 » Файлы и структуры данных (07)