Форум программистов, компьютерный форум CyberForum.ru

Как добавить новый узел в XOR связный список? - C++

Восстановить пароль Регистрация
 
vaselisa
0 / 0 / 0
Регистрация: 04.05.2012
Сообщений: 4
11.05.2012, 04:21     Как добавить новый узел в XOR связный список? #1
Ребятки, помогите разобраться с програмкой:
В качестве аргумента командной строки программе передаются числа n и a. Используя структуры создать XOR связный список из n узлов. Для хранения чисел в узлах ис-пользовать объединения. В 1-ом узле должно быть записано число a, во 2-ом 2*a и так далее. Для каждого узла вывести значение хранимого числа в виде 4-ех сим-волов (char). Предусмотреть возможность добавление нового узла в список.
Имеется готовый код программы с удалением узла из списка, т.е надо только переделать блок удаления на добавление:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
#include "stdafx.h"
#include <iostream>
using namespace std;
typedef uintptr_t INT_P;
 
struct node{
    union {
    float fl_x;
    struct  {char ch_x1,ch_x2,ch_x3,ch_x4;}ch_x;
    }data_x;
    INT_P xor_address;
    node *link;
};
 
node* create_list(int n, float a);
void show_list(node *first);
node* delete_item(node *first, int id_del);
void re_xor (node *previous, node  *current, int id_del);
void free_mem(node *first);
int n;
float a;
node *first = NULL;
 
 
int main(int argc, char** argv){    
    if (argc > 2){
        n = atoi(argv[1]);
        a = atof(argv[2]);
    } else {
      n = 2;
      a = 2;
      }
    first = create_list(n,a);
    char rep;
    do{ 
        if (n==0){
            system("PAUSE");
            exit(0);
        }
        cout<<n<<"  "<<a<<endl;
        show_list(first);
        cout <<"Do you want to delete some items? (y/n)";
        cin >> rep;
        if (rep == 'y'){
            cout<< "Input number of deleting point:";
            int id_del;
            cin >> id_del;
            first = delete_item(first, id_del); 
        }
    }
    while (rep != 'n');
    system ("PAUSE");
    free_mem(first);
}
 
node* create_list (int n, float a){
    node   *last = NULL, *current = NULL, *previous=NULL, *temp=NULL;
    switch (n){
        case 1:
            first = new node;
            first->data_x.fl_x = a;
            first->xor_address = NULL;
            first->link=NULL;
        break;
        case 2:
            first = new node;
            last = new node;
            first->data_x.fl_x = a;
            first->xor_address = NULL;
            last->data_x.fl_x = 2*a;
            last->xor_address = NULL;
            first->link=last;
        break;
        default:
            first = new node;
            first->data_x.fl_x = a;
            first->xor_address = NULL;
            last = new node;
            last->data_x.fl_x = n*a;
            last->xor_address = NULL;
            last->link = NULL;
            previous = first;
            for (int i = 2; i<n; i++){
                current = new node;
                if (previous->xor_address != NULL){
                    previous->xor_address = (reinterpret_cast<INT_P>(temp)^reinterpret_cast<INT_P>(current));
                }
                current->data_x.fl_x=i*a;
                current->link = NULL;
                current->xor_address = (reinterpret_cast<INT_P>(previous)^reinterpret_cast<INT_P>(last));
                if (previous->xor_address == NULL){
                    previous->link = current;
                }
                temp = previous;
                previous = current;
            }
    }
    return first;
}
 
void show_list(node *first){
    if (n>0){
        node *previous = NULL, *current = NULL, *temp = NULL;
        cout << "Item 1 (float) = " << first->data_x.fl_x;
        cout << "   Item 1 (char) = " << first->data_x.ch_x.ch_x1 <<first->data_x.ch_x.ch_x2 <<first->data_x.ch_x.ch_x3 <<first->data_x.ch_x.ch_x4 << endl;
        if (first->link !=NULL){
            previous = first;
            current = first->link;
            int i=2;
            cout << "Item "<<i<< " (float) = " << current->data_x.fl_x;
            cout << "   Item "<<i<< " (char) = " << current->data_x.ch_x.ch_x1 <<current->data_x.ch_x.ch_x2 <<current->data_x.ch_x.ch_x3 <<current->data_x.ch_x.ch_x4 << endl;
            if (n>2){
                do {
                    temp = current;
                    current = reinterpret_cast<node*>(reinterpret_cast<INT_P>(previous)^temp->xor_address);
                    previous = temp;
                    i++;
                    cout << "Item "<<i<< " (float) = " << current->data_x.fl_x;
                    cout << "   Item "<<i<< " (char) = " << current->data_x.ch_x.ch_x1 <<current->data_x.ch_x.ch_x2 <<current->data_x.ch_x.ch_x3 <<current->data_x.ch_x.ch_x4 << endl;
                }
                while (current->xor_address != NULL);
            }
        }
    }
}
 
node* delete_item(node *first, int id_del){
    node *temp = NULL;
    //Если удаляем 1 из 1
    if ((n==1)&&(id_del==1)){
        delete first;
    }
    //Если удаляем 1 из 2
    if ((n==2)&&(id_del==1)){
        temp = first;
        first = temp->link;
        first->link = NULL;
        cout << first->data_x.fl_x;
        delete temp;
    }
    //Если удаляем 2 из 2
    if ((n==2)&&(id_del==2)){
        temp = first->link;
        first->link = NULL;
        delete temp;
    }
    //Если удаляем 1 из n
    if ((n>2)&&(id_del==1)){
        temp = first;
        first = first->link;
        first->link = reinterpret_cast<node*>(reinterpret_cast<INT_P>(temp)^first->xor_address);
        delete temp;
        first->xor_address = NULL;
    }
    //Если удаляем не 1 из n
    node *current = NULL, *previous = NULL;
    if ((n>2)&&(id_del!=1)){
        current = first->link;
        temp = first;
        previous = temp;
        int i = 2;
        while (i != id_del){
            temp = current; 
            current = reinterpret_cast<node*>(reinterpret_cast<INT_P>(previous)^temp->xor_address);
            previous = temp;
            i++;
            }
        re_xor(previous, current, id_del);
    }
    n--;
    return first;
}
 
void re_xor (node *previous, node  *current, int id_del){
    //Удаляем последний при n>2
    if (id_del == n){
        previous->xor_address = NULL;
        delete current;
    }
    else{
        node *next = reinterpret_cast<node*>(reinterpret_cast<INT_P>(previous)^current->xor_address);
        //Если 2 из 3
        if ((previous->xor_address == NULL)&&(next->xor_address == NULL)){
            previous->link = next;
            next->link = previous;
            delete current;
        }
        node *s_next= NULL, *s_previous=NULL;
        //Если 2 из n
        if ((previous->xor_address == NULL)&&(next->xor_address != NULL)){
            s_next = reinterpret_cast<node*>(reinterpret_cast<INT_P>(current)^next->xor_address);
            previous->link = next;
            next->xor_address = (reinterpret_cast<INT_P>(previous)^reinterpret_cast<INT_P>(s_next));
            delete current;
        }
        //Если n-1 из n
        if ((previous->xor_address != NULL)&&(next->xor_address == NULL)){
            s_previous = reinterpret_cast<node*>(reinterpret_cast<INT_P>(current)^previous->xor_address);
            previous->xor_address = (reinterpret_cast<INT_P>(next)^reinterpret_cast<INT_P>(s_previous));
            delete current;
        }
        //Полный пересчет
        if ((previous->xor_address != NULL)&&(next->xor_address != NULL)){
            s_previous = reinterpret_cast<node*>(reinterpret_cast<INT_P>(current)^previous->xor_address);
            s_next = reinterpret_cast<node*>(reinterpret_cast<INT_P>(current)^next->xor_address);
            previous->xor_address = (reinterpret_cast<INT_P>(next)^reinterpret_cast<INT_P>(s_previous));
            next->xor_address = (reinterpret_cast<INT_P>(previous)^reinterpret_cast<INT_P>(s_next));
            delete current;
        }
    }
}
 
void free_mem(node *first){
    for (int i=1; i<=n;i++){
        first = delete_item(first,i);       
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.05.2012, 04:21     Как добавить новый узел в XOR связный список?
Посмотрите здесь:

Как заполнить связный список? C++
Создать класс для работы со стеком, организованным как связный однонаправленный список C++
Список: связный список, в котором информация о книгах сортируется по убыванию стоимости. C++
Связный список (Используя структуру описания даты, построить связный список студентов, сформированный в алфавитном порядке) C++
C++ Однонаправленный связанный список (Вставить новый узел с нулевым значением перед первым отрицательным элементом...)
Связанный список. Создать, записать в связный список последовательность слов,обозначающих месяцы года,заданных пользователем C++
C++ Написать программу, реализующую связный список с информацией о студентах и отображающую список в порядке убывания возраста студента
Добавить элементы из текстового файла в связный список C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 10:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru