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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 5.00
Lexa_Aleynik
0 / 0 / 0
Регистрация: 19.08.2010
Сообщений: 8
19.08.2010, 14:30     удаление/добавление записи по ключу в односвязном списке #1
Возможно-ли удаление или добавление записи по ключу в односвязном списке?
Если да, то не пойму, как "перемещаться по списку" не разрывая связь между записями...
Если не трудно, покажите на примерчике функции удаления или записи
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
19.08.2010, 17:17     удаление/добавление записи по ключу в односвязном списке #2
А Вам точно нужен односвязный список? Может, лучше здесь использовать std::map?
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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);
}
Nameless One
19.08.2010, 17:43
  #4

Не по теме:

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

easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
19.08.2010, 17:52     удаление/добавление записи по ключу в односвязном списке #5
Nameless One, не, я просто так серьёзно переделывать не стал. Но принцип там примерно тот же, только полей в структуре больше. А так точно тем же макаром (только сравнивать ключи нужно) отыскивается структура перед которой нужно вставлять новую. Ну и вывод изменяется с учётом того, что нужно пары "ключ" - "значение" печатать... Но опять же для таких целей лучше всё-таки двухсвязные списки использовать - будет значительно быстрее, особенно, если элемент куда-то в конец списка добавляется.
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
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 минут

Не по теме:

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

Lexa_Aleynik
0 / 0 / 0
Регистрация: 19.08.2010
Сообщений: 8
19.08.2010, 18:14  [ТС]     удаление/добавление записи по ключу в односвязном списке #7
благодарю вас обоих, помогли
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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);
}
Вводится строка текста, выводятся слова, отсортированные по алфавиту + количество их в строке.
удаление/добавление записи по ключу в односвязном списке
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.07.2013, 02:53     удаление/добавление записи по ключу в односвязном списке
Еще ссылки по теме:

C++ Добавление узла перед заданным в односвязном списке
Добавление и удаление элемента в списке C++
Ошибка в односвязном списке C++

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

Или воспользуйтесь поиском по форуму:
Kant
 Аватар для Kant
24 / 24 / 8
Регистрация: 15.05.2013
Сообщений: 213
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;
}
Yandex
Объявления
20.07.2013, 02:53     удаление/добавление записи по ключу в односвязном списке
Ответ Создать тему
Опции темы

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