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

Односвязные лнейные списки - C++

Восстановить пароль Регистрация
 
Гамбит
13 / 13 / 1
Регистрация: 19.10.2009
Сообщений: 93
03.07.2010, 16:37     Односвязные лнейные списки #1
Доброго времени суток. Нужно решить задачу, а я в списках не шарю совсем(и скока не пытался разобраться-не получиилось)
Вот задача

Даны текстовый файл и строка s. Группы символов, разделенные пробелами, будем называть словами. Продублировать каждое слово, содержащее в качестве фрагмента строку s.

Со строками вообще полный ноль=( помогите если знаете =)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2010, 16:37     Односвязные лнейные списки
Посмотрите здесь:

односвязные списки C++
C++ Односвязные списки
Односвязные списки C++
Односвязные списки C++
C++ Односвязные списки С++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
03.07.2010, 20:58     Односвязные лнейные списки #2
В принципе тут можно и без всяких списков обойтись, ну надо - так надо...
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct WRD {
    char * text;
    struct WRD * next;
} wrd_t;
 
wrd_t * new_word(const char * s, wrd_t * last);
wrd_t * words_from_file(const char * file_name);
void print_contains(const wrd_t * list, const char * s);
void delete_words(wrd_t * list);
 
int main(void){
    char buf[BUFSIZ];
    wrd_t * list;
 
    printf("Name of input file: ");
    if ( scanf("%s", buf) != 1 ){
        perror("scanf");
        exit(EXIT_FAILURE);
    }
    if ( ( list = words_from_file(buf) ) == NULL ){
        fprintf(stderr, "Can't get words from file %s\n", buf);
        exit(EXIT_FAILURE);
    }
 
    printf("What to searching for: ");
    if ( scanf("%s", buf) != 1 ){
        perror("scanf");
        delete_words(list);
        exit(EXIT_FAILURE);
    }
    print_contains(list, buf);
 
    delete_words(list);
    exit(EXIT_SUCCESS);
}
 
wrd_t * new_word(const char * s, wrd_t * last){
    wrd_t * w;
    if ( ( w = (wrd_t*)malloc(sizeof(wrd_t)) ) == NULL )
        return NULL;
    if ( ( w->text = strdup(s) ) == NULL ){
        free(w);
        return NULL;
    }
    w->next = NULL;
    if ( last )
        last->next = w;
    return w;
}
 
wrd_t * words_from_file(const char * file_name){
    FILE * f;
    wrd_t * first, * last;
    static char buf[BUFSIZ];
 
    if ( ( f = fopen(file_name, "r") ) == NULL )
        return NULL;
    first = last = NULL;
    while ( fscanf(f, "%s", buf) == 1 ){
        if ( ( last = new_word(buf, last) ) == NULL )
            return NULL;
        if ( ! first )
            first = last;
    }
    fclose(f);
    return first;
}
 
void print_contains(const wrd_t * list, const char * s){
    while ( list ){
        if ( strstr(list->text, s) )
            printf("%s\n", list->text);
        list = list->next;
    }
}
 
void delete_words(wrd_t * list){
    wrd_t * tmp;
    while ( list ){
        tmp = list->next;
        free(list->text);
        free(list);
        list = tmp;
    }
}
Гамбит
13 / 13 / 1
Регистрация: 19.10.2009
Сообщений: 93
04.07.2010, 21:53  [ТС]     Односвязные лнейные списки #3
Спасибо, буду разбираться=)

Добавлено через 12 часов 52 минуты
Проверил эту программу, она выводит только слово, в котором есть повторение сегмента, а мне нужно дублировать =( кароче буду разбираться
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
04.07.2010, 22:55     Односвязные лнейные списки #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
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct WRD {
    char * text;
    struct WRD * next;
} wrd_t;
 
wrd_t * new_word(const char * s, wrd_t * last);
wrd_t * words_from_file(const char * file_name);
void print_contains(const wrd_t * list, const char * s);
int double_contains(wrd_t * list, const char * s);
void print_list(const wrd_t * list);
void delete_words(wrd_t * list);
 
int main(void){
    char buf[BUFSIZ];
    wrd_t * list;
    int cnt;
 
    printf("Name of input file: ");
    if ( scanf("%s", buf) != 1 ){
        perror("scanf");
        exit(EXIT_FAILURE);
    }
    if ( ( list = words_from_file(buf) ) == NULL ){
        fprintf(stderr, "Can't get words from file %s\n", buf);
        exit(EXIT_FAILURE);
    }
 
    printf("\nWords in file:\n");
    print_list(list);
 
    printf("\nWhat to searching for: ");
    if ( scanf("%s", buf) != 1 ){
        perror("scanf");
        delete_words(list);
        exit(EXIT_FAILURE);
    }
    /* print_contains(list, buf); */
    if ( ( cnt = double_contains(list, buf) ) < 0 ){
        fprintf(stderr, "Memory or unknown error!\n");
        delete_words(list);
        exit(EXIT_FAILURE);
    }
 
    printf("\n%d words was doubled.\n", cnt);
    print_list(list);
 
    delete_words(list);
    exit(EXIT_SUCCESS);
}
 
wrd_t * new_word(const char * s, wrd_t * last){
    wrd_t * w;
    if ( ( w = (wrd_t*)malloc(sizeof(wrd_t)) ) == NULL )
        return NULL;
    if ( ( w->text = strdup(s) ) == NULL ){
        free(w);
        return NULL;
    }
    w->next = NULL;
    if ( last )
        last->next = w;
    return w;
}
 
wrd_t * words_from_file(const char * file_name){
    FILE * f;
    wrd_t * first, * last;
    static char buf[BUFSIZ];
 
    if ( ( f = fopen(file_name, "r") ) == NULL )
        return NULL;
    first = last = NULL;
    while ( fscanf(f, "%s", buf) == 1 ){
        if ( ( last = new_word(buf, last) ) == NULL )
            return NULL;
        if ( ! first )
            first = last;
    }
    fclose(f);
    return first;
}
 
void print_contains(const wrd_t * list, const char * s){
    while ( list ){
        if ( strstr(list->text, s) )
            printf("%s\n", list->text);
        list = list->next;
    }
}
 
void delete_words(wrd_t * list){
    wrd_t * tmp;
    while ( list ){
        tmp = list->next;
        free(list->text);
        free(list);
        list = tmp;
    }
}
 
int double_contains(wrd_t * list, const char * s){
    int cnt = 0;
    wrd_t * dbl;
    while ( list ){
        if ( strstr(list->text, s) ){
            if ( ( dbl = new_word(list->text, NULL) ) == NULL ){
                fprintf(stderr, "Can't double word!\n");
                return -1;
            }
            dbl->next = list->next;
            list->next = dbl;
            list = list->next;
            ++cnt;
        }
        list = list->next;
    }
    return cnt;
}
 
void print_list(const wrd_t * list){
    while ( list ){
        printf("%s\n", list->text);
        list = list->next;
    }
}
Добавлено через 1 минуту
На всякий случай: точно обратно в файл писать не нужно?
Гамбит
13 / 13 / 1
Регистрация: 19.10.2009
Сообщений: 93
10.07.2010, 16:34  [ТС]     Односвязные лнейные списки #5
а нельзя попроще расписать??? я таких функций как strdub незнаю.=( сложно разобраться без коментариев
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
10.07.2010, 16:49     Односвязные лнейные списки #6
Цитата Сообщение от Гамбит Посмотреть сообщение
я таких функций как strdub незнаю.
Я про strdub тоже ни разу не слышал, а про strdup() в любом справочнике прочитать можно. Вот к примеру: man strdup

Цитата Сообщение от Гамбит Посмотреть сообщение
а нельзя попроще расписать?
Можно, наверное, только кто и с какой целью этим заниматься будет? Попробуйте сами каждую строку прокомментировать и сюда выложите, что получится. Если где не угадаете, обязательно кто-нибудь поправит...
Гамбит
13 / 13 / 1
Регистрация: 19.10.2009
Сообщений: 93
10.07.2010, 19:32  [ТС]     Односвязные лнейные списки #7
Вот собственно прокоментировал что понял (ну или думаю что понял)
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct WRD {
        char * text;
        struct WRD * next;
} wrd_t;
 
wrd_t * new_word(const char * s, wrd_t * last);/*Функция определяет слово*/
wrd_t * words_from_file(const char * file_name);/*Определяет границы слова*/
void print_contains(const wrd_t * list, const char * s);/*нафиг не надо*/
int double_contains(wrd_t * list, const char * s);/*вносит дублируемое слово*/
void print_list(const wrd_t * list);/*Вывод на экран*/
void delete_words(wrd_t * list);/*это я не понял*/
 
int main(void){
        char buf[BUFSIZ];
        wrd_t * list;
        int cnt;
 
        printf("Name of input file: ");
        if ( scanf("%s", buf) != 1 ){
                perror("scanf");   /*с perror я не очень разобрался, но похоже она отвечает за вывод stderr */
                exit(EXIT_FAILURE); /*завершение программы,но почему нельзя написать exit(1)*/
        }
        if ( ( list = words_from_file(buf) ) == NULL ){
                fprintf(stderr, "Can't get words from file %s\n", buf);
                exit(EXIT_FAILURE);/*собственно завершение программы , если неправильно указано имя файла*/
        }
 
        printf("\nWords in file:\n");
        print_list(list);/*Выводит все слова из файла на экран*/
 
        printf("\nWhat to searching for: ");
        if ( scanf("%s", buf) != 1 ){
                perror("scanf");
                delete_words(list);
                exit(EXIT_FAILURE);/*вводим фрагмент*/
        }
        /* print_contains(list, buf); */
        if ( ( cnt = double_contains(list, buf) ) < 0 ){
                fprintf(stderr, "Memory or unknown error!\n");
                delete_words(list);
                exit(EXIT_FAILURE);/*завершение программы, если нет повторений*/
        }
 
        printf("\n%d words was doubled.\n", cnt);
        print_list(list);/*выводим результирующую строку*/
 
        delete_words(list);
        exit(EXIT_SUCCESS);
}
 
wrd_t * new_word(const char * s, wrd_t * last){
        wrd_t * w;
        if ( ( w = (wrd_t*)malloc(sizeof(wrd_t)) ) == NULL )/*если выделение памяти=0. то возвращаем 0(зачем?)*/
                return NULL;
        if ( ( w->text = strdup(s) ) == NULL ){/*если не получилось присоеденить память, то осовбождаем память и возвращаем 0*/
                free(w);
                return NULL;
        }/*далше не понятно=(*/
        w->next = NULL;
        if ( last )
                last->next = w;
        return w;
}
 
wrd_t * words_from_file(const char * file_name){
        FILE * f;
        wrd_t * first, * last;
        static char buf[BUFSIZ];
 
        if ( ( f = fopen(file_name, "r") ) == NULL )/*Если файл не открыт, возвращаем 0*/
                return NULL;
        first = last = NULL;/*это как я понимаю указатели на начало и конец слова*/
        while ( fscanf(f, "%s", buf) == 1 ){
                if ( ( last = new_word(buf, last) ) == NULL )/*это не понятно=(*/
                        return NULL;
                if ( ! first )/*если указатель отличен от 0, то присваеваем ему last*/
                        first = last;
        }
        fclose(f);
        return first;
}
 
void print_contains(const wrd_t * list, const char * s){/*лишняя функция=)*/
        while ( list ){
                if ( strstr(list->text, s) )
                        printf("%s\n", list->text);
                list = list->next;
        }
}
 
void delete_words(wrd_t * list){/*это удаление чего-то, не понятно для чего*/
        wrd_t * tmp;
        while ( list ){
                tmp = list->next;
                free(list->text);
                free(list);
                list = tmp;
        }
}
 
int double_contains(wrd_t * list, const char * s){
        int cnt = 0;
        wrd_t * dbl;
        while ( list ){
                if ( strstr(list->text, s) ){/*собственно если есть вхождения фрагмента*/
                        if ( ( dbl = new_word(list->text, NULL) ) == NULL ){/*это похоже отвечает за выход. если нет вхождений*/
                                fprintf(stderr, "Can't double word!\n");
                                return -1;
                        }
                        dbl->next = list->next;/*собственно добавление дублируемого слова*/
                        list->next = dbl;
                        list = list->next;
                        ++cnt;
                }
                list = list->next;
        }
        return cnt;
}
 
void print_list(const wrd_t * list){/*вывод на экран*/
        while ( list ){
                printf("%s\n", list->text);
                list = list->next;
        }
}
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
10.07.2010, 21:17     Односвязные лнейные списки #8
C
1
2
3
4
5
6
7
8
...
wrd_t * new_word(const char * s, wrd_t * last); // создаёт в динамической памяти объект структуры WRD, возвращает указатель на него
wrd_t * words_from_file(const char * file_name); // читает по слову из файла, создаёт связанный список объектов структуры WRD, возвращает указатель на первый объект
void print_contains(const wrd_t * list, const char * s); // печатает слова, содержащие указанную последовательность букв. уже не нужна.
int double_contains(wrd_t * list, const char * s); // дублирует слова, в которых встречается указанная последовательность
void print_list(const wrd_t * list); // печатает весь список
void delete_words(wrd_t * list); // удаляет весь вписок
...
Гамбит
13 / 13 / 1
Регистрация: 19.10.2009
Сообщений: 93
11.07.2010, 00:15  [ТС]     Односвязные лнейные списки #9
а зачем список то удалять?
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
11.07.2010, 00:27     Односвязные лнейные списки #10
Цитата Сообщение от Гамбит Посмотреть сообщение
а зачем список то удалять?
Память, полученная вызовом malloc() (calloc(), realloc()) должна быть возвращена системе функцией free(). В этой программе, если память перед выходом не вернуть, ничего вроде бы не изменится, но это дурная практика, которая рано или поздно приведёт к краху большой и сложной программы как-раз из-за того, что память, выделяемая под динамические объекты, не возвращается после их использования. Короче, просто запомните: сколько динамической памяти было системой выделено, столько её (памяти) нужно ей (системе) вернуть.
Гамбит
13 / 13 / 1
Регистрация: 19.10.2009
Сообщений: 93
11.07.2010, 18:37  [ТС]     Односвязные лнейные списки #11
Спасибо в общем, но я не думаю что у препода проканает=( он поймёт что это не я делал
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.07.2010, 14:02     Односвязные лнейные списки
Еще ссылки по теме:

Односвязные списки C++
односвязные списки С++ C++
C++ Односвязные списки

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

Или воспользуйтесь поиском по форуму:
Гамбит
13 / 13 / 1
Регистрация: 19.10.2009
Сообщений: 93
14.07.2010, 14:02  [ТС]     Односвязные лнейные списки #12
и снова я=( я написал более понятную для меня программу, но она НЕ РАБОТАЕТ, что бы я не делал. помогите разобраться-где ошибка.
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
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <alloc.h>
typedef struct list {
char word[15];
struct list *next;
} LIST;
LIST *read_list(LIST *lst)
{
  LIST *p;
  FILE *f;
  f=fopen("1.txt","r");
  if (!feof(f))
  {
    lst=(LIST *)malloc(sizeof(LIST));
    p=lst;
    while (1)
    {
      fscanf(f,"%s",&p->word);
      if (!feof(f))
      {
    p->next=(LIST *)malloc(sizeof(LIST));
    p=p->next;
      } else break;
    }
    p->next=NULL;
  }
  else printf("Файл пустой\n");
  fclose(f);
  return lst;
}
 
 
LIST *double_word(LIST * lst,const char *s)
{
        LIST * dbl=NULL;
        while ( lst )
        {
            if ( strstr(lst->word, s) )
            {
                dbl->next = lst->next;
                lst->next = dbl;
                lst = lst->next;
            }
        lst = lst->next;
        }
return lst;
}
void write_list(LIST *lst)
{
FILE *f;
LIST *p=lst,*prev;
prev=lst;
f=fopen("words.txt","w");
while (p)
    {
    fprintf(f,"%s ",p->word);
    prev=p->next;
    free(p);
    p=prev;
    }
fclose(f);
}
Добавлено через 1 час 14 минут
вызов функций происходит в мейне =)

Добавлено через 3 часа 47 минут
Я понял что ошибка в функции double_word но пока не понял в чём=(

Добавлено через 44 минуты
ппц, вот я идиот=) всем спасибо. вот работающий вариант программы (кстати очень лёгкий)

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
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <alloc.h>
typedef struct list {
char word[15];
struct list *next;
} LIST;
 
LIST *read_list(LIST *lst)
{
LIST *p;
FILE *f;
f=fopen("words.txt","r");
if (!feof(f))
    {
    lst=(LIST *)malloc(sizeof(LIST));
    p=lst;
    while (1)
        {
        fscanf(f,"%s",&p->word);
        if (!feof(f))
            {
            p->next=(LIST *)malloc(sizeof(LIST));
            p=p->next;
            } else break;
        }
    p->next=NULL;
    }
else printf("File is empty\n");
fclose(f);
return lst;
}
 
void write_list(LIST *lst,const char *s)
{
FILE *f;
LIST *p=lst,*prev;
prev=lst;
f=fopen("words.txt","w");
while (p)
    {
    fprintf(f,"%s ",p->word);
    if ( strstr(p->word, s) )
    fprintf(f,"%s ",p->word);
    prev=p->next;
    free(p);
    p=prev;
    }
fclose(f);
}
 
void main()
{
char s;
clrscr();
scanf("%s",&s);
LIST *lst=NULL;
lst=read_list(lst);
write_list(lst,&s);
}
Yandex
Объявления
14.07.2010, 14:02     Односвязные лнейные списки
Ответ Создать тему
Опции темы

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