Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
vaselisa
0 / 0 / 0
Регистрация: 04.05.2012
Сообщений: 4
#1

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

11.05.2012, 04:21. Просмотров 622. Ответов 0
Метки нет (Все метки)

Ребятки, помогите разобраться с програмкой:
В качестве аргумента командной строки программе передаются числа 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);       
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.05.2012, 04:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как добавить новый узел в XOR связный список? (C++):

Связный список (Используя структуру описания даты, построить связный список студентов, сформированный в алфавитном порядке) - C++
Здраствуйте! Помогите пожалуйста найти косяк. Выводится только первая строчка из списка студентов. Вот такая задачка : Программа...

Добавить элементы из текстового файла в связный список - C++
Нужно создать программу, считывающую целые числа из файла. 1. определить переменную, определяющую число столбцов двумерного массива 2....

Однонаправленный связанный список (Вставить новый узел с нулевым значением перед первым отрицательным элементом...) - C++
Помогите выполнить задание: Тип информационной части узла списка - INT Вид списка - Однонаправленный связанный список ...

Как заполнить связный список? - C++
Доброго времени суток, уважаемые форумчане) Начал изучать С++, дошёл до связных списков и вот тут встала проблема... Я не понимаю как...

Связный список как часть друго класса - C++
всем привет. общая задача написать систему для управления колледжем с классами: College, Department, Course, Student у каждого...

Добавить в список новый элемент после заданного - C++
#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;cstring&gt; #include &lt;windows.h&gt; using namespace std; struct element{ ...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.05.2012, 04:21
Привет! Вот еще темы с ответами:

Создать класс для работы со стеком, организованным как связный однонаправленный список - C++
Люди помогите, не могу сделать лабораторную, отчисляют из универа дали 2 дня на сдачу долгов, все сдал кроме лабораторной последней......

Список: связный список, в котором информация о книгах сортируется по убыванию стоимости. - C++
Друзья помогите с реализацией списка. Нужно запрограммировать связный список, в котором информация о книгах сортируется по убыванию...

Связанный список. Создать, записать в связный список последовательность слов,обозначающих месяцы года,заданных пользователем - C++
Создать связанный список.Кроме информационных полей он должен обязательно содержать указатели на предыдущий и следующий за ним...

Написать программу, реализующую связный список с информацией о студентах и отображающую список в порядке убывания возраста студента - C++
Написать программу, реализующую связный список с информацией о студентах и отображающую список в порядке убывания возраста студента


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.