VPF::Динам.память, списки, массивы, файлы...

KasMP

Дата 15.3.2009, 16:25 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: нет
Всего: 30

Есть граф.
В файле сначала записано число его вершин, потом - его матрица смежности (через пробел, предположительно).

Из этой матрицы смежности нужно получить представление графа в виде массива списков (каждый список смежности - динамического линейного списка, адреса первых элементов – в массиве указателей).

Потом вывести этот массив списков в выходной файл (сначала - число вершин графа, затем все списки смежности по возрастанию номеров вершин в списках и номеров вершин, которым списки принадлежат; в конце каждого списка - "0").

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

Посмотрите, пожалуйста, что можно усовершенствовать smile

.

Пример входного файла:

Цитата

4
1 0 1 0
1 1 1 1
0 1 0 0
1 0 1 1

Код


#include <stdio.h>
#include <fstream>
#include <iostream>
using namespace std;

const char path1[]="C:\\in.txt";        // входной файл
const char path2[]="C:\\out.txt";        // выходной файл

// матрица смежности
struct AdjacencyMatrix
{
    short n;            // число вершин
    bool **adjacency;    // указатель на двумерный массив строк
};

// элемент списка смежности
struct ListEl
{
    short el;            // значение элемента
    ListEl *next;            // указатель на след.элемент
};

// массив списков
struct ArrayOfLists
{    
    short n;            // число вершин
    ListEl **lines;        // указатель на (массив указателей на ListEl)
};

// выделение памяти для матрицы смежности
// чтение матрицы смежности из файла в выделенную память
void NewCreateMatrix (AdjacencyMatrix *p_matrix)
{
    short t;
    ifstream f(path1); f >> t;
    
    // выделение памяти для м-ы смежности из bool, запись м-ы
    (p_matrix->adjacency) = new bool *[t];
    for (int i=0; i<t; i++) {
        p_matrix->adjacency[i] = new bool[t];
        // чтение строки из файлы в строку м-ы смежности
        for (int j=0; j<t; j++)
            f >> p_matrix->adjacency[i][j];
    }
}

void NewMatrix (AdjacencyMatrix *p_matrix)
{
    short t = p_matrix->n;

    (p_matrix->adjacency) = new bool *[t];
    for (int i=0; i<t; i++)
        p_matrix->adjacency[i] = new bool[t];
}

void CreateMatrix (AdjacencyMatrix *p_matrix)
{
    short t;
    ifstream f(path1); f >> t;

    for (int i=0; i<t; i++)
        for (int j=0; j<t; j++)
            f >> p_matrix->adjacency[i][j];
}

void NewArrayOfLists (ArrayOfLists *p_lists)
{
    short n = p_lists->n;

    (p_lists->lines) = new ListEl *[n];
    for (int i=0; i<n; i++)
        p_lists->lines[i] = new ListEl;
}

void AddOneList (AdjacencyMatrix *p_matrix, ListEl *pp, short i)
{
    short n = p_matrix->n;
    pp->el = -1; // добавление фиктивного элемента

    for (short j=0; j<n; j++) {
        if (p_matrix->adjacency[i][j]) {
            pp->next = new ListEl;
            pp = pp->next;
            pp->el=j+1;    
        }
    }
    pp->next = NULL;
}

void Interpretation (AdjacencyMatrix *p_matrix, ArrayOfLists *p_lists)
{
    short n = p_matrix->n;
    for (short i=0; i<n; i++) AddOneList(p_matrix,p_lists->lines[i],i);
}

void PrintMatrix (AdjacencyMatrix *p_matrix)
{
    short n = p_matrix->n;

    cout << "Size=" << n << "\n";    
    for (short i=0; i<n; i++) {
        for (short j=0; j<n; j++)
            cout << p_matrix->adjacency[i][j] << ' ';
        cout << "\n";
    }
    cout << "\n";
}
void PrintOneList (ListEl *pp, short i, ofstream *f)
{
    cout << "*** List for vertice #" << i+1 << " ***\n\n";
    *f << "List for vertice #" << i+1 << ":\n";

    pp = pp->next; // перешагиваем через фиктивный элемент

    while (pp) {
        cout << pp->el << ' ' << pp->next << "\n";
        *f << pp->el << ' ';
        pp = pp->next;
    }

    *f << "0 \n\n"; cout << "\n\n";
}

void PrintArrayOfLists (ArrayOfLists *p_lists, ofstream *f)
{
    short n = p_lists->n;
    for (short i=0; i<n; i++)
        PrintOneList(p_lists->lines[i],i,f);
}

void DeleteMatrix (AdjacencyMatrix *p_matrix)
{
    short n = p_matrix->n;

    for (short i=0; i<n; i++)
        delete[] p_matrix->adjacency[i];
    delete [] p_matrix->adjacency;
}

void DeleteOneList (ListEl *pp)
{
    ListEl *next = pp->next;

    if (pp->next) {
        while (next->next) {
            delete pp;
            pp = next;
            next = pp->next;
        }
        delete next;
        delete pp;
    }
    else delete pp;
}

void DeleteArrayOfLists (ArrayOfLists *p_lists)
{
    short n = p_lists->n;

    for (short i=0; i<n; i++) DeleteOneList(p_lists->lines[i]);
    delete[] p_lists->lines;
}

int main()
{
    short i;

    AdjacencyMatrix matrix;    ArrayOfLists lists;
    ifstream fin(path1); ofstream fout(path2);

    short n; fin >> n;
    matrix.n = lists.n = n;

    NewCreateMatrix(&matrix); NewArrayOfLists(&lists);
    //NewMatrix(&matrix); CreateMatrix(&matrix);
    Interpretation(&matrix,&lists);

    PrintMatrix(&matrix); PrintArrayOfLists(&lists,&fout);

    DeleteMatrix(&matrix); DeleteArrayOfLists(&lists);
    fin.close(); fout.close();

    cin >> i;
    return(0);
}

mes

Дата 15.3.2009, 17:16 (ссылка)

(голосов:1)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

1. NewCreateMatrix является копипастом содержимого NewMatrix и CreateМатрих a также открывает файл который открыт в main
2. есть ListEl и ArrayofLists, но не нету List.
3. Размерность передается в функцию не параметром, а посредством значения размерности структуры.
4. Чтение с файла внутри функций не предназначенных для этого
4а. При этом файл чтения не передан как аргумент.
5. использование фиктивного эллемента
6..
Ну для начала хватит smile

--------------------

http://opendots.net

KasMP

Дата 15.3.2009, 19:25 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: нет
Всего: 30

Цитата(mes @ 15.3.2009, 17:16

)

5. использование фиктивного эллемента

Ну, здесь я немного поленилась... Переделаю smile

.
А вообще это считается большим серьезным минусом?

Цитата(mes @ 15.3.2009, 17:16

)

4. Чтение с файла внутри функций не предназначенных для этого

Из файла я читаю только тогда, когда заполняю матрицу. Эта функция (CreateMatrix или NewCreateMatrix) как раз и предназначена для того, чтобы читать из файла в память.
Или что ты предлагаешь smile

Цитата(mes @ 15.3.2009, 17:16

)

4а. При этом файл чтения не передан как аргумент.

Да!! Это плохо smile

Цитата(mes @ 15.3.2009, 17:16

)

3. Размерность передается в функцию не параметром, а посредством значения размерности структуры.

Долго думала, что могла значить эта фраза... Разные варианты продумала...
Ты имел в виду, что не надо передавать в ф-ю 2 параметра - размерность и указатель на структуру, что достаточно только указателя (т.к. структура содержит размерность)? У меня вроде бы так и сделано smile

Цитата(mes @ 15.3.2009, 17:16

)

2. есть ListEl и ArrayofLists, но не нету List.

Интересная мысль smile

.
С одной стороны, в логической цепочке [элемент списка] -> [список] -> [массив списков] действительно не должно быть пробелов...
Но с другой, что такое список? Правильнее всего представлять его указателем на первый элемент... Не создавать же структуру, состоящую из одного указателя!

Цитата(mes @ 15.3.2009, 17:16

)

1. NewCreateMatrix является копипастом содержимого NewMatrix и CreateМатрих

Я понимаю

.
Просто с одной стороны хочется рациональности (NewCreateMatrix - за один цикл м-а и создается, и заполняется), с другой - наглядности (NewMatrix+CreateMatrix - четко видно и понятно, кто что делает и зачем...). Я еще не выбрала, какой вариант лучше smile

Цитата(mes @ 15.3.2009, 17:16

)

a также открывает файл который открыт в main

Ну, если передавать ссылку на файл, то, конечно, я не буду открывать его снова...

Добавлено через 1 минуту и 44 секунды
А удаляющие ф-ии у меня правильные? Все чистят?
Я проверяла на несколько раз, но чувства Уверенности все равно нет...

mes

Дата 15.3.2009, 19:42 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(KasMP @ 15.3.2009, 18:25

)

Ты имел в виду, что не надо передавать в ф-ю 2 параметра - размерность и указатель на структуру, что достаточно только указателя (т.к. структура содержит размерность)? У меня вроде бы так и сделано smile .

как раз наоборот. размерность нужно передавать параметром, а не внутри структуры, так как то поле внутри структуры несет по смыслу текущий размер матрицы, а не требуемый.

Цитата(KasMP @ 15.3.2009, 18:25

)

Но с другой, что такое список?

Код


struct List
{
   ListEl * Head;
// ListEl * Tail; 
};

из за нехватки этой структуры тебе приходится вводить фиктивный элемент. smile

Цитата(KasMP @ 15.3.2009, 18:25

)

(NewCreateMatrix - за один цикл м-а и создается, и заполняется), с другой - наглядности (NewMatrix+CreateMatrix - четко видно и понятно, кто что делает и зачем...).

Так вызывай в функции NewCreateMatrix функции NewMatrix и CreateMatrix.. хотя функция по загрузке с файла звучала бы лучше как LoadMatrix..

Это сообщение отредактировал(а) mes - 15.3.2009, 19:42

--------------------

http://opendots.net

mes

Дата 15.3.2009, 19:58 (ссылка)

(голосов:1)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

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

Это сообщение отредактировал(а) mes - 15.3.2009, 20:01

--------------------

http://opendots.net

KasMP

Дата 15.3.2009, 20:03 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: нет
Всего: 30

Цитата(mes @ 15.3.2009, 19:42

)

Когда я это делала, я думала так:
ф-ии, начинающиеся с "New", изначально предназначены для конструирования, и поэтому в них можно передавать не до конца определенные структуры;
во все другие ф-ии надо передавать уже полноценные, правильно заполненные структуры, где все поля соответствуют именно текущему состоянию друг друга.

Неужели так мыслить - плохо :( ?

Цитата(mes @ 15.3.2009, 19:42

)

из за нехватки этой структуры тебе приходится вводить фиктивный элемент.

Я не введу его другим способом smile

.
Имхо вводить структуру из одного указателя ради фиктивного элемента (его отсутствия, точнее smile

) - загромождение...

Цитата(mes @ 15.3.2009, 19:42

)

Так вызывай в функции NewCreateMatrix функции NewMatrix и CreateMatrix.. хотя функция по загрузке с файла звучала бы лучше как LoadMatrix..

И тогда рациональный вариант (где за 1 цикл делается все) исчезнет совсем smile

.

Добавлено через 3 минуты и 24 секунды

Цитата(mes @ 15.3.2009, 19:58

)

и еще у тебя все функции между собой перемешаны..

Они идут по порядку и разделены на группы для:
создания (выделения памяти)
заполнения
перевода
вывода
удаления

Цитата(mes @ 15.3.2009, 19:58

)

т.е к примеру все что касается матриц вместе, при этом функция удаления сразу за функцией создания..

так тоже можно разбить smile

mes

Дата 15.3.2009, 20:11 (ссылка)

(голосов:1)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(KasMP @ 15.3.2009, 19:03

)

Неужели так мыслить - плохо :( ?

плохо это :

Цитата(KasMP @ 15.3.2009, 19:03

)

не до конца определенные структуры;

одно и то же поле несет двойную логику в зависимости от функции.

Цитата(KasMP @ 15.3.2009, 19:03

)

Я не введу его другим способом smile .
Имхо вводить структуру из одного указателя ради фиктивного элемента (его отсутствия, точнее smile ) - загромождение...

Обратная логика : структуру списка нужно ввести не для устранения фиктивного элемента, а для того чтоб спокойно работать со списком.
А вот фиктивный элемент появился в следствии отсутствия списка и является загромаждением.

Цитата(KasMP @ 15.3.2009, 19:03

)

И тогда рациональный вариант (где за 1 цикл делается все) исчезнет совсем smile .

А рациональность то в чем ? в том что он пару тактов процессора съэкономит ? Это как при покупке мерса торговаться за цент smile

Добавлено через 3 минуты и 35 секунд

Цитата(KasMP @ 15.3.2009, 19:03

)

В таком порядке у тебя нет наглядности.

--------------------

http://opendots.net

KasMP

Дата 15.3.2009, 20:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: нет
Всего: 30

Цитата(mes @ 15.3.2009, 20:11

)

одно и то же поле несет двойную логику в зависимости от функции.

Ну да, дискомфортно... Получается, чтобы выбрать логику, надо найти название ф-ии, выделить начало и вспомнить, какое свойство этому началу приписывал автор smile

.
Допишем в New* и Create* второй параметр smile

...

Цитата(mes @ 15.3.2009, 20:11

)

Сейчас я сделаю без фик.эл-та и без структуры smile

Цитата(mes @ 15.3.2009, 20:11

)

А рациональность то в чем ? в том что он пару тактов процессора съэкономит ? Это как при покупке мерса торговаться за цент

А если в графе много-много вершин?

Добавлено через 55 секунд

Цитата(mes @ 15.3.2009, 20:11

)

В таком порядке у тебя нет наглядности.

Это большая правда.
Спасибо за советы smile

.

Добавлено через 5 минут и 14 секунд
А может некоторые переменные как-то по-другому назвать, чтобы читалось легче? Или нормально smile

mes

Дата 15.3.2009, 20:43 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(KasMP @ 15.3.2009, 19:37

)

А если в графе много-много вершин?

Ну и в чем выйгрыш вместо вызова двух функций все описывать в одной ?

Это сообщение отредактировал(а) mes - 15.3.2009, 20:45

--------------------

http://opendots.net

KasMP

Дата 15.3.2009, 20:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: нет
Всего: 30

Цитата(KasMP @ 15.3.2009, 20:37

)

Сейчас я сделаю без фик.эл-та и без структуры

Да... Получается какая-то сложная, совсем ненаглядная штука (которая еще и вылетает в некоторых случаях в ф-х вывода по понятным причинам).

Код


void AddOneList (AdjacencyMatrix *p_matrix, ListEl *pp, short i)
{
    short n = p_matrix->n;

    short j = 0;

    while (
        ( !(p_matrix->adjacency[i][j]) )
        &&
        (j < n-1)
        )
        j++;

    if (p_matrix->adjacency[i][j]) {
        pp->el = j;    j++;
        for (; j<n; j++) {
            if (p_matrix->adjacency[i][j]) {
                pp->next = new ListEl;
                pp = pp->next;
                pp->el=j+1;    
            }
        }
        pp->next = NULL;
    }
    else
        pp = NULL;
}

Добавлено через 4 минуты и 27 секунд

Цитата(mes @ 15.3.2009, 20:43

)

Ну и в чем выйгрыш вместо вызова двух функций все описывать в одной ?

NewCreate - внешний цикл до t-1, в нем внутренний цикл до t-1.
New - цикл до t-1.
Create - в плане циклов то же, что NewCreate.

Если сложить New и Create, то получается на 1 цикл больше...
Или это не так важно?

mes

Дата 15.3.2009, 20:59 (ссылка)

(голосов:1)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(KasMP @ 15.3.2009, 19:51

)

Если сложить New и Create, то получается на 1 цикл больше...
Или это не так важно?

Разница в один цикл получается вследствии того, что у тебя в одной из функций идет обнуление.
Так вынеси обнуление как отдельную функцию Clear () smile

Добавлено через 3 минуты и 51 секунду

Цитата(KasMP @ 15.3.2009, 19:51

)

void AddOneList (AdjacencyMatrix *p_matrix, ListEl *pp, short i)

Попробуй ответить, эта функция по конвертированию матрицы в список или по добавлению списка в массив ?

--------------------

http://opendots.net

KasMP

Дата 15.3.2009, 21:14 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: нет
Всего: 30

Цитата(mes @ 15.3.2009, 20:59

)

Попробуй ответить, эта функция по конвертированию матрицы в список или по добавлению списка в массив ?

AddOneList добавляет в массив один список (соответствующий одной вершине, т.е. одной строке матрицы).
Interpretation переводит матрицу в список, используя AddOneList.

Добавлено через 2 минуты и 43 секунды
Вот, теперь у меня хотя бы файлы не открываются дважды smile

, открываемые файлы передаются по ссылке (а не жестко прописываются второй раз в процедуре smile

), поля структуры всегда находятся в гармонии друг с другом smile

. Все-таки лучше, чем было smile

.

Добавлено через 4 минуты и 32 секунды
А фиктивный элемент я оставлю... На нем слишком много всего завязано.
(да и неоднократно из уст преподавателя вылетала фраза: "в списках всегда нужно создавать фиктивный элемент... в них всегда проблема с 1-м элементом - необходимо создавать фиктивный")

Добавлено через 6 минут и 15 секунд

Цитата(mes @ 15.3.2009, 17:16

)

1. +
2. +
3. +
4(а). +
5. smile

mes

Дата 15.3.2009, 21:27 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(KasMP @ 15.3.2009, 20:14

)

(да и неоднократно из уст преподавателя вылетала фраза: "в списках всегда нужно создавать фиктивный элемент... в них всегда проблема с 1-м элементом - необходимо создавать фиктивный")

Без комментариев (из уважения к почетному званию Учитель)

Цитата(KasMP @ 15.3.2009, 20:14

)

Все-таки лучше, чем было smile .

Ну хоть бы выложила, чтоб можно было сравнить smile

Цитата(KasMP @ 15.3.2009, 20:14

)

AddOneList добавляет в массив один список

ну ка еще раз посмотрим на объявление:

Цитата(KasMP @ 15.3.2009, 19:51

)

void AddOneList (AdjacencyMatrix *p_matrix, ListEl *pp, short i)

чудеса

Это сообщение отредактировал(а) mes - 15.3.2009, 21:27

--------------------

http://opendots.net

KasMP

Дата 15.3.2009, 21:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: нет
Всего: 30

Цитата(mes @ 15.3.2009, 21:27

)

Без комментариев (из уважения к почетному званию Учитель)

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

Цитата(mes @ 15.3.2009, 21:27

)

чудеса

"Добавлением одного списка" я называю непосредственно добавление и перевод одной строки из м-ы в этот список.
short i - ну, номер строки, которую сейчас добавляем-переводим (нам нужно знать, к какой строке м-ы обращаться)
ListEl *pp - ук-ль на начало списка, соответствующего строке (вершине) i...
AdjacencyMatrix *p_matrix - smile

Цитата(mes @ 15.3.2009, 21:27

)

Ну хоть бы выложила, чтоб можно было сравнить

Пожалуйста smile

Код


#include <stdio.h>
#include <fstream>
#include <iostream>
using namespace std;

const char path1[]="C:\\in.txt";        // входной файл
const char path2[]="C:\\out.txt";        // выходной файл

// матрица смежности
struct AdjacencyMatrix
{
    short n;            // число вершин
    bool **adjacency;    // указатель на двумерный массив строк
};

// элемент списка смежности
struct ListEl
{
    short el;            // значение элемента
    ListEl *next;            // указатель на след.элемент
};

// массив списков
struct ArrayOfLists
{    
    short n;            // число вершин
    ListEl **lines;        // указатель на (массив указателей на ListEl)
};

// выделение памяти для матрицы смежности
// чтение матрицы смежности из файла в выделенную память
void NewCreateMatrix (AdjacencyMatrix *p_matrix, short t, ifstream *p_f)
{
    p_matrix->n = t;

    // выделение памяти для м-ы смежности из bool, запись м-ы
    (p_matrix->adjacency) = new bool *[t];
    for (int i=0; i<t; i++) {
        p_matrix->adjacency[i] = new bool[t];
        // чтение строки из файлы в строку м-ы смежности
        for (int j=0; j<t; j++)
            *p_f >> p_matrix->adjacency[i][j];
    }
}

void NewMatrix (AdjacencyMatrix *p_matrix, short t)
{
    p_matrix->n = t;

    (p_matrix->adjacency) = new bool *[t];
    for (int i=0; i<t; i++)
        p_matrix->adjacency[i] = new bool[t];
}

void CreateMatrix (AdjacencyMatrix *p_matrix, ifstream *p_f)
{
    short t = p_matrix->n;
    
    for (int i=0; i<t; i++)
        for (int j=0; j<t; j++)
            *p_f >> p_matrix->adjacency[i][j];
}

void PrintMatrix (AdjacencyMatrix *p_matrix)
{
    short n = p_matrix->n;

    cout << "Size=" << n << "\n";    
    for (short i=0; i<n; i++) {
        for (short j=0; j<n; j++)
            cout << p_matrix->adjacency[i][j] << ' ';
        cout << "\n";
    }
    cout << "\n";
}

void DeleteMatrix (AdjacencyMatrix *p_matrix)
{
    short n = p_matrix->n;

    for (short i=0; i<n; i++)
        delete[] p_matrix->adjacency[i];
    delete [] p_matrix->adjacency;
}

void NewArrayOfLists (ArrayOfLists *p_lists, short n)
{
    p_lists->n = n;

    (p_lists->lines) = new ListEl *[n];
    for (int i=0; i<n; i++)
        p_lists->lines[i] = new ListEl;
}

void PrintOneList (ListEl *pp, short i, ofstream *f)
{
    cout << "*** List for vertice #" << i+1 << " ***\n\n";
    *f << "List for vertice #" << i+1 << ":\n";

    pp = pp->next; // перешагиваем через фиктивный элемент

    while (pp) {
        cout << pp->el << ' ' << pp->next << "\n";
        *f << pp->el << ' ';
        pp = pp->next;
    }

    *f << "0 \n\n"; cout << "\n\n";
}

void PrintArrayOfLists (ArrayOfLists *p_lists, ofstream *f)
{
    short n = p_lists->n;
    for (short i=0; i<n; i++)
        PrintOneList(p_lists->lines[i],i,f);
}

void DeleteOneList (ListEl *pp)
{
    ListEl *next = pp->next;

    if (pp->next) {
        while (next->next) {
            delete pp;
            pp = next;
            next = pp->next;
        }
        delete next;
        delete pp;
    }
    else delete pp;
}

void DeleteArrayOfLists (ArrayOfLists *p_lists)
{
    short n = p_lists->n;

    for (short i=0; i<n; i++) DeleteOneList(p_lists->lines[i]);
    delete[] p_lists->lines;
}

void AddOneList (AdjacencyMatrix *p_matrix, ListEl *pp, short i)
{
    short n = p_matrix->n;
    pp->el = -1; // добавление фиктивного элемента

    for (short j=0; j<n; j++) {
        if (p_matrix->adjacency[i][j]) {
            pp->next = new ListEl;
            pp = pp->next;
            pp->el=j+1;    
        }
    }

    pp->next = NULL;
}

void Interpretation (AdjacencyMatrix *p_matrix, ArrayOfLists *p_lists)
{
    short n = p_matrix->n;
    for (short i=0; i<n; i++) AddOneList(p_matrix,p_lists->lines[i],i);
}


int main()
{
    short i;

    AdjacencyMatrix matrix;    ArrayOfLists lists;
    ifstream fin(path1); ofstream fout(path2);

    short n; fin >> n;

    //NewCreateMatrix(&matrix,n,&fin);
    NewArrayOfLists(&lists,n);
    NewMatrix(&matrix,n); CreateMatrix(&matrix,&fin);
    Interpretation(&matrix,&lists);

    PrintMatrix(&matrix); PrintArrayOfLists(&lists,&fout);

    DeleteMatrix(&matrix); DeleteArrayOfLists(&lists);
    fin.close(); fout.close();

    cin >> i;
    return(0);
}

Добавлено @ 21:37
Я еще порядок хотела поменять. Сейчас!

Это сообщение отредактировал(а) KasMP - 15.3.2009, 21:41

mes

Дата 16.3.2009, 00:38 (ссылка)

(голосов:1)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(KasMP @ 15.3.2009, 20:36

)

"Добавлением одного списка" я называю непосредственно добавление и перевод одной строки из м-ы в этот список.

лови подарок smile

// базовые функции работы с матрицей смежности

Код


struct AdjMatrix
{
    unsigned size;
    bool  ** data;
};

void AdjMatrixNew (AdjMatrix& m, unsigned size =0)
{
    m.size = size;
    if (size > 0)
    {
        m.data = new  bool* [size];
        for (unsigned  i=0; i<size; ++i)  m.data[i]= new bool[size];
    }
    else
    m.data = NULL;
}

void AdjMatrixDestroy (AdjMatrix& m)
{
    if (m.size>0)
    {
        for (unsigned i=0; i<m.size; ++i)  delete [] m.data[i];
        delete m.data;
    }
    m.data= NULL;
    m.size=0;
}
void AdjMatrixResize (AdjMatrix& m, unsigned size =0)
{
     AdjMatrixDestroy (m);
     AdjMatrixNew (m, size);
}

void AdjMatrixClear  (AdjMatrix& m)
{
     for (int i=0; i<m.size; ++i)
      for (int j=0; j<m.size; ++j)
       m.data[i][j] = false;
}

// базовые функции работы со списком и его массивом

Код



struct AdjListNode
{
    int           value;
    AdjListNode * next;
};

struct AdjList
{
    AdjListNode * Head;
};


void AdjListNew (AdjList& l)
{
     l.Head = NULL;
}


void AdjListPushFront (AdjList& l, int value )
{
    AdjListNode * node =  new AdjListNode;

    node->value = value;
    node->next  = l.Head;

    l.Head = node;
}

void AdjListPopFront (AdjList& l)
{

   AdjListNode * node =  l.Head;
    l.Head = node->next;
    delete node;
}

void AdjListDestroy (AdjList& l)
{
     while (l.Head) AdjListPopFront(l);
}

struct AdjListArray
{
    unsigned  size;
    AdjList * data;
};

void AdjListArrayNew (AdjListArray& la, unsigned size =0)
{
    la.size = size;
    if (size > 0)
    {
         la.data = new  AdjList [size];
         for (unsigned i=0; i<la.size; ++i)   AdjListNew (la.data[i]);
    }
    else          la.data = NULL;
}

void AdjListArrayDestroy (AdjListArray& la)
{
    if (la.size>0)
    {
        for (unsigned i=0; i<la.size; ++i)   AdjListDestroy (la.data[i]);
        delete la.data;
    }
    la.data= NULL;
    la.size=0;
}
void AdjListArrayResize (AdjListArray& la, unsigned size =0)
{
     AdjListArrayDestroy (la);
     AdjListArrayNew     (la, size);
}

void AdjListArrayCreateFromAdjMatrix (AdjListArray& la, AdjMatrix &m)
{
    AdjListArrayNew (la, m.size);

     for (unsigned i=0; i<m.size; ++i)
     for (unsigned k=m.size; k--;) if (m.data[i][k]) AdjListPushFront (la.data[i], k+1); // +1 если вершины начинаются с 1;
}

// потоковые функции :

Код


#include  <ostream>

void AdjMatrixOut (AdjMatrix& m, std::ostream& out)
{
     out<<m.size<<std::endl;
     for (unsigned i=0; i<m.size; ++i)
     {
       for (unsigned j=0; j<m.size; ++j)
          out << m.data[i][j] <<" ";
       out <<std::endl;
     }
}

void AdjMatrixCreateFromStream (AdjMatrix& m, std::istream& in)
{
     unsigned size;
     in>>size;
     AdjMatrixNew (m, size);

     for (unsigned i=0; i<m.size; ++i)
      for (unsigned j=0; j<m.size; ++j)
       in>>m.data[i][j];
}

void AdjListArrayOut (AdjListArray& la, std::ostream& out)
{
     out<<la.size<<std::endl;
     for (unsigned i=0; i<la.size; ++i)
     {
       AdjListNode * node = la.data[i].Head;
       for (;node; node=node->next)
          out << node->value <<" ";
       out <<std::endl;
     }
}

ну и само выполнения задания на основе вышеприведенных функций

Код


// включить предыдущий код или через include или просто скопировать.

const char path1[]="C:\\in.txt";        // входной файл
const char path2[]="C:\\out.txt";        // выходной файл


int main()
{

    ifstream fin(path1);
    ofstream fout(path2);

    AdjMatrix matrix;
    AdjMatrixCreateFromStream (matrix, fin);

    cout << "Debug AdjMatrixCreateFromStream(..) " << std::endl; // for test
    AdjMatrixOut (matrix, cout);       // for test;

    AdjListArray lists;
    AdjListArrayCreateFromAdjMatrix (lists, matrix);

    cout << "Debug AdjListArrayCreateFromAdjMatrix (..) " << std::endl; // for test
    AdjListArrayOut (lists, cout);       // for test;

    AdjListArrayOut (lists, fout);

    AdjMatrixDestroy (matrix);
    AdjListArrayDestroy (lists);

     system ("pause");
    return(0);
}

Ну a дальше тестируй и ровняй под свои нужды..

P.S. и никаких фиктивных элементов при работе со списком smile

Это сообщение отредактировал(а) mes - 16.3.2009, 00:49

--------------------

http://opendots.net

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »