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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 5.00
Lexa_Aleynik
0 / 0 / 0
Регистрация: 19.08.2010
Сообщений: 8
#1

Удаление/добавление записи по ключу в односвязном списке - C++

19.08.2010, 14:30. Просмотров 1964. Ответов 8
Метки нет (Все метки)

Возможно-ли удаление или добавление записи по ключу в односвязном списке?
Если да, то не пойму, как "перемещаться по списку" не разрывая связь между записями...
Если не трудно, покажите на примерчике функции удаления или записи
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.08.2010, 14:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Удаление/добавление записи по ключу в односвязном списке (C++):

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

Поиск и удаление в односвязном списке - C++
Помогите с удаление элемента по ключу(номеру этажа). При удалении 2-го элемента в списке, удаляется вместе с 1-ым, но если удалять 3, то 2...

Удаление узлов в односвязном списке - C++
Помогите пожалуйста, не могу понять что не так. Нужно удалить узлы содержащие простые числа.Программа не удаляет! #include<iostream> ...

Добавление узла перед заданным в односвязном списке - C++
Вот такой код я нашел, но он похоже с ошибками, нету * как минимум. проставил их но тоже не помогло void AddBefore(PNode PHead, PNode p,...

Удаление повторяющихся элементов в односвязном списке - C++
Добрый день! Задание такое: построить линейный список из нескольких динамических переменных, содержащих вводимые целые числа....

Как можно сместить ID в односвязном списке после удаление элемента - C++
народ можете подсказать как можно сместить айди в односвязном списке послу удаление элемента, на пример у меня там были айди 1, 2, 3, 4 ...

8
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
19.08.2010, 17:17 #2
А Вам точно нужен односвязный список? Может, лучше здесь использовать std::map?
1
easybudda
Модератор
Эксперт CЭксперт С++
9719 / 5670 / 972
Регистрация: 25.07.2009
Сообщений: 10,916
19.08.2010, 17:38 #3
Цитата Сообщение от Nameless One Посмотреть сообщение
А Вам точно нужен односвязный список? Может, лучше здесь использовать std::map?
На самом деле для подобных задач односвязный список - не лучший выбор. Вот переделанный пример отсюда. Читает значения, пока ноль не ввести, выводит уникальные значения, отсортированные по возрастанию:
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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct LISTNODE {
    int nVal;
    struct LISTNODE * pNext;
} listnode_t;
 
listnode_t * new_node(int val, listnode_t * last){
    listnode_t * ln;
    if ( ( ln = (listnode_t*)malloc(sizeof(listnode_t)) ) == NULL ){
        perror("malloc");
        return NULL;
    }
    ln->nVal = val;
    ln->pNext = NULL;
    if ( last )
        last->pNext = ln;
    return ln;
}
 
void clear_list(listnode_t * ln){
    listnode_t * tmp;
    while ( ln ){
        tmp = ln->pNext;
        free(ln);
        ln = tmp;
    }
}
 
listnode_t * create_list(void){
    listnode_t * first, * last, * found, * prev, * inserted;
    int val;
 
    first = last = NULL;
    while ( 1 ){
        printf("> ");
        if ( scanf("%d", &val) != 1 ){
            fprintf(stderr, "Wrong input!\n");
            if ( first )
                clear_list(first);
            return NULL;
        }
        if ( ! val )
            break;
        if ( ! first ){
            if ( ( first = new_node(val, NULL) ) == NULL ){
                fprintf(stderr, "Memory error!\n");
                return NULL;
            }
            last = first;
        }
        else {
            for ( found = first; found != NULL && val > found->nVal; found = found->pNext )
                ;
            if ( ! found ){
                if ( ( last = new_node(val, last) ) == NULL ){
                    fprintf(stderr, "Memory error!\n");
                    clear_list(first);
                    return NULL;
                }
            }
            else if ( found->nVal == val )
                continue;
            else if ( found == first ){
                if ( ( inserted = new_node(val, NULL) ) == NULL ){
                    fprintf(stderr, "Memory error!\n");
                    clear_list(first);
                    return NULL;
                }
                inserted->pNext = first;
                first = inserted;
            }
            else {
                for ( prev = first; prev->pNext != found; prev = prev->pNext )
                    ;
                if ( ( inserted = new_node(val, NULL) ) == NULL ){
                    fprintf(stderr, "Memory error!\n");
                    clear_list(first);
                    return NULL;
                }
                prev->pNext = inserted;
                inserted->pNext = found;
            }
        }
    }
 
    return first;
}
 
void print_list(const listnode_t * ln){
    while ( ln ){
        printf("%d\n", ln->nVal);
        ln = ln->pNext;
    }
}
 
int main(void){
    listnode_t * ln;
 
    printf("Enter some numbers, 0 = finish:\n");
    if ( ( ln = create_list() ) == NULL ){
        fprintf(stderr, "Can't create list!\n");
        exit(EXIT_FAILURE);
    }
    print_list(ln);
    clear_list(ln);
 
    exit(EXIT_SUCCESS);
}
1
Nameless One
19.08.2010, 17:43
  #4

Не по теме:

easybudda, кажется, я чего-то не понимаю Разве для хранения пар ключ-значение подойдет такой список?

1
easybudda
Модератор
Эксперт CЭксперт С++
9719 / 5670 / 972
Регистрация: 25.07.2009
Сообщений: 10,916
19.08.2010, 17:52 #5
Nameless One, не, я просто так серьёзно переделывать не стал. Но принцип там примерно тот же, только полей в структуре больше. А так точно тем же макаром (только сравнивать ключи нужно) отыскивается структура перед которой нужно вставлять новую. Ну и вывод изменяется с учётом того, что нужно пары "ключ" - "значение" печатать... Но опять же для таких целей лучше всё-таки двухсвязные списки использовать - будет значительно быстрее, особенно, если элемент куда-то в конец списка добавляется.
1
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
19.08.2010, 18:11 #6
Вот пример с отображением std::map:
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
#include <iostream>
#include <cstdlib>
#include <map>
#include <string>
 
int main()
{
    std::string line;
    // Отображение: ключ - символ, значение - число повторов символа в строке
    std::map<char, size_t> map;
    std::cout << "Input a string:" << std::endl;
    // Заполнение отображения
    std::getline(std::cin, line);
    /* Оператор [] возвращает ссылку на существующее значение,
     * ассоциированное с ключем;
     * если такого значения не существует, то создается новое
     */
    for(std::string::const_iterator it = line.begin(); it != line.end(); ++it)
        ++map[*it];
    /* "Перемещение по отображению" - печать */
    for(std::map<char, size_t>::const_iterator it = map.begin();
        it != map.end();
        ++it)
        std::cout << "[" << it->first << "] => " << it->second << std::endl;
    /* Ищем значение, ассоциируемое с ключем 'l', удаляем его, если оно
     * существует, и печатаем отображение опять
     */
    std::map<char, size_t>::iterator at_l;
    if((at_l = map.find('l')) != map.end())
    {
        // Если значение нашлось
        std::cout << "Letter \'l\' was found. Deleting the value" << std::endl;
        // ... удаляем значение вместе с ключем
        map.erase(at_l); // можно map.erase('l');
        for(std::map<char, size_t>::const_iterator it = map.begin();
            it != map.end();
            ++it)
            std::cout << "[" << it->first << "] => " << it->second << std::endl;
    }
    else
        std::cout << "Letter \'l\' was not found" << std::endl;
    return EXIT_SUCCESS;
}

Не по теме:

Кстати, std::map ведь не получится сортировать с помощью std::sort? Как отсортировать по ключу, я еще представляю, а вот как сделать это по значению?



Добавлено через 10 минут

Не по теме:

Все, догадался

1
Lexa_Aleynik
0 / 0 / 0
Регистрация: 19.08.2010
Сообщений: 8
19.08.2010, 18:14  [ТС] #7
благодарю вас обоих, помогли
0
easybudda
Модератор
Эксперт CЭксперт С++
9719 / 5670 / 972
Регистрация: 25.07.2009
Сообщений: 10,916
19.08.2010, 18:57 #8
Вот в догонку сортированный двухсвязный список на С
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define DELIM " ,.\t\n"
 
typedef struct WRD {
    char * pszText;
    int nCount;
    struct WRD * pPrev;
    struct WRD * pNext;
} wrd_t;
 
wrd_t * new_word(const char * s){
    wrd_t * w;
 
    if ( ( w = (wrd_t*)malloc(sizeof(wrd_t)) ) == NULL ){
        fprintf(stderr, "new_word: memory allocation error!\n");
        return NULL;
    }
    if ( ( w->pszText = strdup(s) ) == NULL ){
        fprintf(stderr, "new_word: string duplicate error!\n");
        free(w);
        return NULL;
    }
    w->nCount = 1;
    w->pPrev = NULL;
    w->pNext = NULL;
 
    return w;
}
 
void clear_list(wrd_t * first){
    wrd_t * tmp;
 
    while ( first ){
        tmp = first->pNext;
        free(first->pszText);
        free(first);
        first = tmp;
    }
}
 
wrd_t * create_list(const char * str, const char * delim){
    char * buf, * p;
    wrd_t * first, * last, * found, * inserted;
    int cmp;
 
    if ( ( buf = strdup(str) ) == NULL ){
        fprintf(stderr, "create_list: string duplicate error!\n");
        return NULL;
    }
 
    first = NULL;
    for ( p = strtok(buf, delim); p != NULL; p = strtok(NULL, delim) ){
        if ( ! first ){
            if ( ( first = new_word(p) ) == NULL ){
                fprintf(stderr, "create_list: can't create the first word!\n");
                free(buf);
                return NULL;
            }
            last = first;
        }
        else {
            for ( found = first; found != NULL; found = found->pNext ){
               if ( ( cmp = strcmp(found->pszText, p) ) < 0 )
                   continue;
               else if ( cmp == 0 ){
                   found->nCount += 1;
                   break;
               }
               else {
                   if ( ( inserted = new_word(p) ) == NULL ){
                       fprintf(stderr, "create_list: can't create a new word!\n");
                       clear_list(first);
                       free(buf);
                       return NULL;
                   }
                   if ( found == first ){
                       first->pPrev = inserted;
                       inserted->pNext = first;
                       first = inserted;
                   }
                   else {
                       found->pPrev->pNext = inserted;
                       inserted->pPrev = found->pPrev;
                       inserted->pNext = found;
                       found->pPrev = inserted;
                   }
                   break;
               }
            }
            if ( found == NULL ){
                if ( ( inserted = new_word(p) ) == NULL ){
                    fprintf(stderr, "create_list: can't create a last word!\n");
                    clear_list(first);
                    free(buf);
                    return NULL;
                }
                inserted->pPrev = last;
                last->pNext = inserted;
                last = inserted;
            }
        }
    }
 
    free(buf);
    return first;
}
 
void print_list(const wrd_t * w){
    while ( w ){
        printf("%-20s : %d\n", w->pszText, w->nCount);
        w = w->pNext;
    }
}
 
int main(void){
    char buf[BUFSIZ];
    wrd_t * list;
 
    while ( printf("\nString: ") && fgets(buf, BUFSIZ, stdin) ){
        if ( *buf == '\n' )
            break;
        if ( ( list = create_list(buf, DELIM) ) == NULL ){
            fprintf(stderr, "Can't create list!\n");
            exit(EXIT_FAILURE);
        }
        print_list(list);
        clear_list(list);
    }
 
    exit(EXIT_SUCCESS);
}
Вводится строка текста, выводятся слова, отсортированные по алфавиту + количество их в строке.
Удаление/добавление записи по ключу в односвязном списке
0
Kant
33 / 33 / 9
Регистрация: 15.05.2013
Сообщений: 236
20.07.2013, 02:53 #9
Сам недавно эту тему разбирал. Вот максимально простой пример для понимания.

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
#include <iostream>
#include <time.h>
using  std::cout;
using  std::endl;
 
struct Element {
    // Данные
    int data;
    // Адрес следующего элемента списка
    Element * Next;
};
 
// Односвязный список
class List {
    // Адрес первого элемента списка
    Element * Head;
    // Адрес первого элемента списка
    Element * Tail;
 
public:
    // Конструктор
    List() : Head(0), Tail(0) {}
    // Деструктор
    ~List() { /*DelAll(); */    }
 
    void push_back(const int data);
    void removing_duplicate_items();
    void Print() const;
};
 
void List::push_back(const int data)  {
    // создание нового элемента
    Element * temp = new Element;
 
    // заполнение данными
    temp->data = data;
    // следующий элемент отсутствует
    temp->Next = NULL;
    // новый элемент становится последним элементом списка
    // если он не первый добавленный
 
    if(Head != NULL){
        Tail->Next=temp;
        Tail = temp;
    }
    // новый элемент становится единственным
    // если он первый добавленный
    else{
        Head=Tail=temp;
    }
}
 
void List::removing_duplicate_items() {
    //Если нет элементов, то return
    if (NULL == Head) 
        return; 
 
/*Как работает штука, что снизу. 
Есть текущий элемент он находится во внешнем цикле i = Head, который указывает на первый элемент. 
Два указателя pre_j и j бегают от текущего эл. до конца.        
Чтобы удалить эл. из списка необходимо знать эл. перед удаляемым для этого заводим pre_j.
Чтобы удалить эл. необходимо перебросить указатель предыдущего эл. pre_j на следующий после удаляемого
j->next и удалить память по адресу j элемента. */
 
    Element *i, *j, *pre_j, *item_to_remove;
 
    for (i = Head; NULL != i; i = i->Next) {
        for (pre_j = i, j = i->Next; NULL != j;) {
            if (i->data == j->data) {
                cout << i->data << " = " << j->data << endl;
 
                item_to_remove = j;
                pre_j->Next = j = j->Next;
                delete item_to_remove;
 
                Print();
            } 
            else {
                pre_j=pre_j->Next;
                j = j->Next;
            }
        }
    }
}
 
 
void List::Print() const
{
    if(Head != 0) {
        // запоминаем адрес головного элемента
        Element * temp = Head;
        // Пока еще есть элементы
        while(temp != 0)
        {
            // Выводим данные
            cout << temp->data << " ";
            // Переходим на следующий элемент
            temp = temp->Next;
        }
 
        cout << "\n\n";
    }
    else 
        cout << "\nList emty\n";
}
 
 
int main() {
    srand(time(NULL));
 
    List lst;
 
    int val;
    for(int i = 0; i < 15; ++i) {
        val = rand() % 10;
        lst.push_back(val);
    }
 
    lst.Print();
    lst.removing_duplicate_items();
    lst.Print();
    return 0;
}
0
20.07.2013, 02:53
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.07.2013, 02:53
Привет! Вот еще темы с ответами:

Добавление и удаление элемента в списке - C++
Ребят сделал код создания элементов списка, но не могу написать 1) код добавления элемента списка в конец списка 2) код удаления...

Ошибка в односвязном списке - C++
Помогите решить эти 2 проблемы C4101: NextNode: неиспользованная локальная переменная (в 118 строке) C4703: используется потенциально...

Ошибка в односвязном списке - C++
#include&lt;iostream&gt; #include&lt;clocale&gt; using namespace std; #define DEBUG class Monom{ protected: int...

Использование деструктора в односвязном списке с++ - C++
Здравствуйте. Нужна срочная помощь!!! Есть реализация односвязного списка в котором узел - класс, а не структура. Вначале программы...


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

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

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