Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.71/14: Рейтинг темы: голосов - 14, средняя оценка - 4.71
0 / 0 / 0
Регистрация: 19.08.2010
Сообщений: 8
1

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

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

Возможно-ли удаление или добавление записи по ключу в односвязном списке?
Если да, то не пойму, как "перемещаться по списку" не разрывая связь между записями...
Если не трудно, покажите на примерчике функции удаления или записи
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.08.2010, 14:30
Ответы с готовыми решениями:

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

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

Удаление чисел в односвязном списке
С клавиатуры вводится последовательность целых чисел, завершающаяся нулем. Создать односвязный...

Удаление узлов в односвязном списке
Помогите пожалуйста, не могу понять что не так. Нужно удалить узлы содержащие простые...

8
Эксперт С++
5811 / 3462 / 356
Регистрация: 08.02.2010
Сообщений: 7,448
19.08.2010, 17:17 2
А Вам точно нужен односвязный список? Может, лучше здесь использовать std::map?
1
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
10855 / 6730 / 1616
Регистрация: 25.07.2009
Сообщений: 12,469
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
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
10855 / 6730 / 1616
Регистрация: 25.07.2009
Сообщений: 12,469
19.08.2010, 17:52 5
Nameless One, не, я просто так серьёзно переделывать не стал. Но принцип там примерно тот же, только полей в структуре больше. А так точно тем же макаром (только сравнивать ключи нужно) отыскивается структура перед которой нужно вставлять новую. Ну и вывод изменяется с учётом того, что нужно пары "ключ" - "значение" печатать... Но опять же для таких целей лучше всё-таки двухсвязные списки использовать - будет значительно быстрее, особенно, если элемент куда-то в конец списка добавляется.
1
Эксперт С++
5811 / 3462 / 356
Регистрация: 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
0 / 0 / 0
Регистрация: 19.08.2010
Сообщений: 8
19.08.2010, 18:14  [ТС] 7
благодарю вас обоих, помогли
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
10855 / 6730 / 1616
Регистрация: 25.07.2009
Сообщений: 12,469
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
33 / 33 / 18
Регистрация: 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.07.2013, 02:53

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Добавление узла перед заданным в односвязном списке
Вот такой код я нашел, но он похоже с ошибками, нету * как минимум. проставил их но тоже не помогло...

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

Удаление всех вхождений элемента Х в односвязном списке L
Доброй ночи. Ситуация HELP, ситуация SOS. Есть задача &quot;Написать программу удаление всех...

Как можно сместить ID в односвязном списке после удаление элемента
народ можете подсказать как можно сместить айди в односвязном списке послу удаление элемента, на...


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

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

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