Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/9: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Mila6777
8 / 8 / 0
Регистрация: 06.01.2013
Сообщений: 47
1

Работа с двусвязным списком - создание, просмотр, добавление и редактирование записей

03.03.2013, 01:09. Просмотров 1732. Ответов 4
Метки нет (Все метки)

Доброе время суток!

Практически моя вторая программа на Си, которую пытаюсь сделать сама. Взяла из разных примеров. Вроде всё работает как надо. Если увидите какие-то очевидные неочевидности, ошибки, недочеты, прошу указать.

Задание:
Разработать программу для создания и работы с двусвязным списком, состоящим из структур. Для работы со списком создать меню со следующими пунктами:
1. Создание списка.
2. Просмотр списка.
3. Добавление в конец списка новой структуры.
4. Корректировка списка.
5. Выход.
Структура содержит название издания, газета или журнал, цена экземпляра. Добавлять новые записи так, чтобы сначала располагались журналы, затем газеты.

Вот что получилось:
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
  #include <stdio.h>
 #include <conio.h>
 #include <alloc.h>
 #include <string.h>
 #include <stdlib.h>
 
 struct spis
 { char izdat[30];
   int type;
   int price;
   struct spis *prev;              
   struct spis *next; 
 };
 
 void create(void); // создание
 void display(void); // просмотр
 void add(void); // добавление в конец списка
 void sort(void); // сортировка (вначале - журналы, потом газеты)
 struct spis *head,*tail; // указатели на начало и конец списка
 
 main()
 { char c;
   FILE *tf;
   while (1)
   { clrscr();
     puts(" 1 - create list"); // создать список
     puts(" 2 - view list"); // показать список
     puts(" 3 - add to the end of list"); // добавить в конец списка
     puts(" 4 - sort list"); // сортировка списка
     puts(" 0 - escape"); // выход
     c=getch();
     switch(c)
     { case '1':create();break;
       case '2':display();break;
       case '3':add();break;
       case '4':sort();break;
       case '0':return 0;
       default : puts("wrong choice");
     }
   }
 }
 
 void create()
 
 { spis *p,*pred;
   pred=NULL;
   clrscr();
   printf("\n Vvedite spisok \n");
   do { p=(spis *)malloc(sizeof(spis));
        printf("Izdatelstvo: "); scanf("%s",p->izdat);
        printf("\n Vid izdanija: Gazeta - 1; Jurnal - 2: "); scanf("%d", &p->type);
        printf("\n Cena: ");  scanf("%d", &p->price);
        p->prev=pred;
        if (pred != NULL)
            pred->next=p;
        else
            head=p;
            pred=p;
            puts(" Zakoncit` - <esc>");
      }
   while (getch()!=27);
   tail=p;
   tail->next=NULL;
 }
 
 void display()
 { spis *p = head;
   while (p != NULL)
                { printf("%30s  ", p->izdat);
                  if (p->type == 1)
                      printf("Gazeta");
                  else
                      printf("Jurnal");
                  printf("%10d\n", p->price);
                  p = p->next;
 
                 }
  getch();
 } 
 
 void add()
 { spis *p 
   printf("\n Vvedite novje dannje \n");
   clrscr();
   do { p=(spis *)malloc(sizeof(spis)); // Выделяем динамическую память
        printf("Izdatelstvo: "); scanf("%s",p->izdat);
        printf("\n Vid izdanija: Gazeta - 1; Jurnal - 2: "); scanf("%d", &p->type);
        printf("\n Cena: ");  scanf("%d", &p->price);
        p->prev = NULL;
        p->next = NULL;
        if (head == NULL) // Если список пустой
        head = tail = p;
        else 
        { tail->next = p;
          p->prev = tail;
          tail = p;
          puts(" Zakonchit` - <esc>");
        }
       }
   while (getch()!=27);
 }
 
int ListSize()
 { int n = 0;
   spis *p = head;
   while (p != NULL)
       { n++;
         p = p->next;
       }
   return n;
 }
 
 void sort()
 { spis *p;
   char s[30];  
   int k;
   int n = ListSize();
   for (int i = 1; i <= n - 1; i++) 
       { p = head;
         for (int j = 1; j <= n - i; j++) 
             { if (p->type < p->next->type) 
                   { strcpy(s, p->izdat);
                     strcpy(p->izdat, p->next->izdat);
                     strcpy(p->next->izdat, s);
                     k = p->type;
                     p->type = p->next->type;
                     p->next->type = k;
                     k = p->price;
                     p->price = p->next->price;
                     p->next->price = k;
                   }
               p = p->next;
             }
       }
 }

Конечно нужно еще подработать вывод на экран, но это уже второе дело. Главное, чтобы логически и концептуально все было правильно.

Буду рада помощи.

Пока вот что заметила:
Если в меню выбрать не 1,2,3,4,0, а другое значение, по идее должно выйти сообщение wrong choice (неправильный выбор), а этого не происходит.

В общем, кто чем может. Жду конструктивной критики и/или исправлений.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.03.2013, 01:09
Ответы с готовыми решениями:

Ошибка в коде из методички. Работа с двусвязным списком
Код из электронной методички не собирается с ошибкой |39|error: dereferencing pointer to incomplete...

Задача с двусвязным списком. Правильно ли решена?
#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;malloc.h&gt; typedef struct node { int data;...

Объясните пожалуйста действия с двусвязным списком типа кольцо
объявляем struct RING { char surname; RING *l, *r; };

Работа с двусвязным нециклическим списком: инверсия списка
Есть программа для работы с двухсвязным списком. Есть проблемы с функцией инверсии списка. Visual...

Работа с двусвязным списком. Проблема с функцией удаления с конца
Есть задача на двусвязный список, но наблюдается непонятная ошибка. Если сделать функцию удаления...

4
easybudda
Модератор
Эксперт CЭксперт С++
10259 / 6147 / 1547
Регистрация: 25.07.2009
Сообщений: 11,702
03.03.2013, 19:17 2
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

Mila6777, не призываю отказаться от своего варианта - в моём тоже полно недочётов, да и работает не совсем так, как задумано, но просто чтобы было, с чем сравнивать:
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
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MAX_NAME_LENGTH (64)
#define READ_NAME(s) ( scanf("%63[^\n]", (s)) == 1 )
 
void flush_input(void) {
    char c;
    while ( scanf("%c", &c) == 1 && c != '\n' )
        ;
}
 
enum PRESS_TYPE { PT_NEWSPAPER = 1, PT_MAGAZINE = 2 };
 
typedef struct PRESS_DATA {
    char name[MAX_NAME_LENGTH];
    int type;
    double price; /* как-то для денежных величин привычнее */
} pressdata_t;
 
/* Функция для сравнения. Принимает указатели на две структуры,
сравнивает их сначала по типу, за тем по имени. */
int pd_cmp(const pressdata_t * a, const pressdata_t * b) {
    return ( a->type == b->type ) ? strcmp(a->name, b->name) : a->type - b->type;
}
 
/* Чтение данных об издании. Возвращает 0, если данные введены, -1 при ошибке. */
int pd_read(pressdata_t * pd) {
    pressdata_t tmp; /* Чтобы не испортить объект, если он уже инициализирован. Пригодится при редактировании. */
    
    printf("Name: ");
    if ( ! READ_NAME(tmp.name) ){
        fprintf(stderr, "Wrong input for name!\n");
        flush_input();
        return -1;
    }
    
    printf("Type (%d - newspapper, %d - magazine): ", PT_NEWSPAPER, PT_MAGAZINE);
    if ( scanf("%d", &(tmp.type)) != 1 ) {
        fprintf(stderr, "Wrong input for type!\n");
        flush_input();
        return -1;
    }
    if ( tmp.type != PT_NEWSPAPER && tmp.type != PT_MAGAZINE ) {
        fprintf(stderr, "Type out of range!\n");
        flush_input();
        return -1;
    }
    
    printf("Price: ");
    if ( scanf("%lf", &(tmp.price)) != 1 ) {
        fprintf(stderr, "Wrong input for price!\n");
        flush_input();
        return -1;
    }
    if ( tmp.price < 0.0 ) {
        fprintf(stderr, "Imposible value for price!\n");
        flush_input();
        return -1;
    }
    
    *pd = tmp;
    flush_input();
    return 0;
}
 
/* Вывод. */
void pd_dump(const pressdata_t * pd) {
    printf("| %-40s | %-10s | %6.2f |\n", pd->name, ( pd->type == PT_NEWSPAPER ) ? "Newspaper" : "Magazine", pd->price);
}
 
/* Структура - узел для списка */
typedef struct NODE {
    pressdata_t * data;
    struct NODE * prev;
    struct NODE * next;
} node_t;
 
node_t * new_node(void) {
    node_t * n = malloc(sizeof(node_t));
    if ( ! n ) {
        fprintf(stderr, "Memory error!\n");
        return NULL;
    }
    
    n->data = malloc(sizeof(pressdata_t));
    if ( ! n->data ) {
        fprintf(stderr, "Memory error!\n");
        free(n);
        return NULL;
    }
    
    n->prev = NULL;
    n->next = NULL;
    
    return n;
}
 
void del_node(node_t * n) {
    free(n->data);
    free(n);
}
 
/* Структура - список */
typedef struct LIST {
    node_t * head;
    node_t * tail;
} list_t;
 
list_t * new_list(void) {
    list_t * l = malloc(sizeof(list_t));
    
    if ( ! l ) {
        fprintf(stderr, "Memory error!\n");
        return NULL;
    }
    
    l->head = NULL;
    l->tail = NULL;
    
    return l;
}
 
void del_list(list_t * l) {
    while ( l->head ) {
        l->tail = l->head->next;
        del_node(l->head);
        l->head = l->tail;
    }
    free(l);
}
 
void ordered_insert(list_t * list, node_t * node) {
    if ( ! list->head ) {
        list->head = node;
        list->tail = node;
    }
    else if ( pd_cmp(list->head->data, node->data) < 0 ) {
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    else {
        node_t * current = list->head;
        while ( current->next && pd_cmp(current->next->data, node->data) <= 0 )
            current = current->next;
        if ( current == list->tail ) {
            node->prev = list->tail;
            list->tail->next = node;
            list->tail = node;
        }
        else {
            node->prev = current;
            node->next = current->next;
            current->next->prev = node;
            current->next = node;
        }
    }
}
 
/* Извлекает узел из списка, не удаляя его */
node_t * detach_from_list(list_t * list, node_t * node) {
    if ( node == list->head ) {
        if ( list->head = list->head->next ) /* если первый элемент не является последним */
            list->head->prev = NULL;
    }
    else if ( node == list->tail ) {
        list->tail = list->tail->prev;
        list->tail->next = NULL;
    }
    else {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    node->prev = NULL;
    node->next = NULL;
    
    return node;
}
 
node_t * find_node(list_t * list) {
    pressdata_t pd;
    node_t * found;
    
    printf("Enter name and type to find (you may use 0 for price value)...\n");
    if ( pd_read(&pd) ) {
        fprintf(stderr, "Can't search this!\n");
        return NULL;
    }
    
    for ( found = list->head; found && pd_cmp(found->data, &pd); found = found->next )
        ;
    
    return found;
}
 
#define SEPARATOR "+------------------------------------------+------------+--------+\n"
 
void print_header(void) {
    printf("%s", SEPARATOR);
    printf("| Name                                     | Type       | Price  |\n");
    printf("%s", SEPARATOR);
}
 
void dump_list(list_t * list) {
    node_t * current = list->head;
    if ( ! current )
        printf("Empty list.\n");
    else {
        print_header();
        for ( ; current; current = current->next ) {
            pd_dump(current->data);
            printf("%s", SEPARATOR);
        }
    }
}
 
 
/* Собственно программа */
/* Меню */
enum MENUSTATE { MS_EXIT = 0, MS_INSERT, MS_FIND, MS_CHANGE, MS_DELETE, MS_SHOW };
 
int menu(void) {
    int ret;
    
    printf("%d - Add one\n%d - Find\n%d - Edit\n%d - Delete\n%d - Show all\n%d - Exit\n> ", MS_INSERT, MS_FIND, MS_CHANGE, MS_DELETE, MS_SHOW, MS_EXIT);
    if ( scanf("%d", &ret) != 1 ) {
        fprintf(stderr, "Wrong input!\n");
        ret = -1;
    }
    
    flush_input();
    return ret;
}
 
int main(void) {
    list_t * list;
    node_t * node;
    pressdata_t pd;
    int m;
    
    if ( ! ( list = new_list() ) ) {
        fprintf(stderr, "Memory error!\n");
        exit(1);
    }
    
    while ( m = menu() ) {
        switch ( m ) {
            case MS_INSERT:
                if ( ! ( node = new_node() ) ) {
                    fprintf(stderr, "Memory error!\n");
                    exit(1);
                }
                if ( pd_read(node->data) ) {
                    fprintf(stderr, "Input error!\n");
                    del_node(node);
                    break;
                }
                ordered_insert(list, node);
                printf("New record added to list.\n");
                break;
            case MS_FIND:
                if ( ! ( node = find_node(list) ) )
                    printf("Not found.\n\n");
                else {
                    print_header();
                    pd_dump(node->data);
                    printf("%s", SEPARATOR);
                    printf("\n");
                }
                break;
            case MS_CHANGE:
                if ( ! ( node = find_node(list) ) ) {
                    printf("Not found.\n");
                    break;
                }
                printf("Current data:\n");
                print_header();
                pd_dump(node->data);
                printf("%s", SEPARATOR);
                printf("Enter new values...\n");
                if ( pd_read(node->data) )
                    fprintf(stderr, "Wrong input!\n");
                else
                    ordered_insert(list, detach_from_list(list, node));
                break;
            case MS_DELETE:
                if ( ! ( node = find_node(list) ) ) {
                    printf("Not found.\n");
                    break;
                }
                del_node(detach_from_list(list, node));
                printf("One record deleted from list.\n");
                break;
            case MS_SHOW:
                dump_list(list);
                break;
            default:
                fprintf(stderr, "Wrongmenu choise!\n");
                break;
        }
    }
    
    del_list(list);
    exit(0);
}
1
Mila6777
8 / 8 / 0
Регистрация: 06.01.2013
Сообщений: 47
03.03.2013, 20:29  [ТС] 3
Спасибо, easybudda. Обязательно посмотрю код чуть позже, когда справлюсь с курсовой, уже надо отправлять.
Переделала сама, буду отсылать как есть, осталось только комменты дописать. Кроме сортировки добавила функцию вставки новой записи при условии сортировки - чтобы запись сразу вставала в нужное место.
Default и всё остальное доработала.
Кое-в чем не понимаю, как работает, и ладно, главное - добилась, чтобы всё было как нужно и в одном стиле по всей программе.
И красиво выглядит (с выводом разных записей в процессе работы для взаимодействия с пользователем). Не учтен только случай неверного ввода данных.

Отпишусь, когда закончу.
0
Mila6777
8 / 8 / 0
Регистрация: 06.01.2013
Сообщений: 47
06.03.2013, 19:57  [ТС] 4
Сдала на пять!!! с замечанием, что эффективнее менять связи, а не информационную часть элементов.

Вот функции: которая возвращает количество элементов, сортировки и вставки в сортированный список:

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
int ListSize() // возвращает количество элементов в списке
 { int n = 0;
   spis *p = head;
   while (p != NULL) // пока не конец списка
       { n++;
         p = p->next; // продвижение по списку
       }
   return n;
 }
 
 void sort() // сортировка списка 
 { spis *p;
   char s[30];  
   int i,j,k;
   int n = ListSize();
   clrscr();
   for (i = 1; i <= n - 1; i++)  // сортируем методом пузырька 
       { p = head;
         for (j = 1; j <= n - i; j++) 
             { if (p->type < p->next->type) 
                   { strcpy(s, p->izdat); // меняем элементы местами
                     strcpy(p->izdat, p->next->izdat);
                     strcpy(p->next->izdat, s);
                     k = p->type;
                     p->type = p->next->type;
                     p->next->type = k;
                     k = p->price;
                     p->price = p->next->price;
                     p->next->price = k;
                   }
               p = p->next; // продвижение по списку
             }
       }
   printf(" Список отсортирован \n\n Чтобы продолжить – нажмите любую клавишу");
   getch();
 }
 
 void InsertIntoSorted (spis* &head, spis* &tail) // вставка элемента в                       
                                     // сортированный список
 { spis *pn,*p;  // pn – указатель на новую структуру
   char c;
 
   clrscr();
   printf("\n Введите новую запись \n");
   pn=(spis *)malloc(sizeof(spis)); // выделяем память
   // вводим все поля списка
   printf("\n Издательство: "); scanf("%s",pn->izdat);
   printf(" Вид издания: Газета - 1; Журнал - 2: "); scanf("%d", &pn->type);
   printf(" Цена: ");  scanf("%d", &pn->price);
   p = head; 
   while (p!=NULL && p->type==2) p=p->next; // ищем в отсортированном      
                                         // списке последний журнал
   if (p==NULL)  // если прошли весь список, то вставляем в конец
       { tail->next = pn;
     pn->prev = tail;
     pn->next = NULL;
     tail = pn;
       } 
   else if (p==head)  // если остались в начале, то вставляем на место первого
       { head->prev = pn;
         pn->next = head;
         pn->prev = NULL;
         head = pn;
       } 
        else  // иначе вставляем в середину
            { pn->next = p;
          pn->prev = p->prev;
          p->prev->next = pn;
          p->prev = pn;
        };
   printf("\n Запись добавлена \n Для просмотра списка нажмите 1 \n Для возврата в меню нажмите любую клавишу");
   c=getch();
   if (c=='1') display();
 }
...
 
 main() // 
 { char c;
// основное меню
   while (1)
    { clrscr();
          puts(" 1 – создать список");
          puts(" 2 – просмотр списка ");
          puts(" 3 – добавить записи в конец списка ");
          puts(" 4 – сортировать список");
          puts(" 5 – сортировать список и добавить новую запись по условию сортировки");
          puts(" 0 - выход");
          c=getch();
          switch(c)
          { case '1':create();break;
            case '2':display();break;
            case '3':add();break;
            case '4':sort();break;
            case '5':sort();InsertIntoSorted(head,tail);break;
            case '0':return 0;
            default : clrscr();printf(" Неверный выбор. Для возврата в меню нажмите любую клавишу");getch();
          }
        }
return 0;
 }


Если не сложно, как все-таки самым простым способом ограничить ввод данных Журнал - 1 и Газета - 2, чтобы можно было вводить только эти 2 значения?
Например, ввел 3 (не 1 и не 2). Программа пишет:неверный выбор, возвращается назад и опять выводит:
Вид издания: Газета - 1; Журнал - 2
???
0
lowercase
212 / 201 / 85
Регистрация: 09.05.2012
Сообщений: 494
06.03.2013, 20:10 5
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

можно так:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
 
int main(){
    int c;
    for(;;){
    // или while(1); 
        printf("Вид издания: Газета - 1; Журнал - 2: ");
        scanf("%d%*c", &c);
        if(c == 1 || c == 2){
            break;
        } else {
            printf("Некорректный выбор\n");
        }
    }
    return 0;
}
0
06.03.2013, 20:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.03.2013, 20:10

Работа с двусвязным списком, поиск и перемена местами двух элементов в списке
Здравствуйте! Есть список List http://pastebin.com/tNSztz50 Не могу разобраться, как найти...

Работа с Access: добавление, редактирование, фильтрация, удаление записей, вывод на форму
В лицее начали изучать новую тему по ИТ - бД, и тут же получили по программированию огромное...

Нужны задачки для упражнения в работе со списком, стеком, очередью и двусвязным списком
Недавно научился строить список, стек, очередь, двусвязный список в С++, что бы закрепить навыки...


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

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

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