Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
6 / 6 / 4
Регистрация: 09.11.2011
Сообщений: 126
1

Написать функцию, которая добавляет новый элемент в связный список

26.08.2013, 19:27. Просмотров 2371. Ответов 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
#include <stdio.h>
 
struct list {
    int value;
    struct list *next;
};
 
int main() {
    struct list n1, n2, n3;
    struct list *listStart;
    
    listStart = &n1;
    n1.value = 10;
    n1.next = &n2;
    
    n2.value = 20;
    n2.next = &n3;
    
    n3.value = 30;
    n3.next = NULL;
    
    return 0;
}
Чтобы вставить новый элемент необходимо создать новую структуру (n2_2) и вставить после n2

C
1
2
3
4
...
n2_2 = n2.next;
n2.next = &n2_2;
...
Автор даёт подсказку, функция принимает 2 аргумента: указатель на на начало списка и указатель на элемент после которого должен встать новый элемент. Мне не понятно, что она должна возвращать. Новый спиcок или указатель на него или вообще должна быть void.

.... insertElem(struct list *listStart, struct list *n)

PS. Там еще много задач на связные списки. Создать программу которая удаляет элементы, двойные связные списки и прочее. Если будет, что-то не понятно, буду писать в эту тему.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.08.2013, 19:27
Ответы с готовыми решениями:

Определите функцию inleft построения списка целых чисел, которая добавляет новый элемент
Определите функцию inleft построения списка целых чисел, которая добавляет новый элемент (первый...

Описать рекурсивную функцию или процедуру, которая добавляет новый элемент Е в конец списка L
Описать рекурсивную функцию или процедуру, которая добавляет новый элемент Е в конец списка L

Связный список. Необходимо создать новый связный список только из положительных элементов
Задача: Прочитать из файла связный список. Потом из этого списка создать еще один, в котором будут...

Написать процедуру, которая вставляет в упорядоченный непустой список новый элемент
Написать процедуру, которая вставляет в непустого список L,элементы которого упорядочены по...

__________________
Помогаю в написании курсовых работ и дипломов здесь.
9
213 / 202 / 85
Регистрация: 09.05.2012
Сообщений: 494
26.08.2013, 21:13 2
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

Цитата Сообщение от gnuvse Посмотреть сообщение
Мне не понятно, что она должна возвращать. Новый спиcок или указатель на него или вообще должна быть void.
завист от ваших потребностей. можете ничего не возвращать.
а если хотите возвращать, то самым ожидаемым (в пдобном случае) значнием был бы указатель на начало списка или флаг который обозначает успешность вставки элемента. в первом случае общая картина будет выглядит так:
C
1
2
3
4
struct list* insertElem(struct list *listStart, struct list *n) {
    //... 
    return listStart;
}
это позволит вам делать примерно такого рода записи в коде:
C
1
insertElem(insertElem(insertElem(insertElem(listhead, node0),node1), node2), node3);
однако дважды подумайте, прежде чем делать подобное. ведь следующая(еквивалентная) запись гараздо легче читается:
C
1
2
3
4
insertElem(listhead, node0);
insertElem(listhead, node1);
insertElem(listhead, node2);
insertElem(listhead, node3);
0
Z3JheSBoYXQ=
339 / 234 / 83
Регистрация: 08.07.2012
Сообщений: 577
26.08.2013, 21:27 3
Функция вставки , имхо разумеется возвращает булево значение, привычно и удобно для анализа. По существу, если будешь использовать что-то вроде,

C
1
2
3
struct Node *CreateNode(struct Node *base); // создание ноды, возвращает указатель на вновь созданную структуру 
int CountNodes(struct Node *base); // возвращает количество созданных нод
bool InsertNode(struct Node *base, int offset); // вставка ноды, в случае успеха получаем true, в обратном случае false
при вставке тебе надо проверить аргумент offset на допустимость if (offset <= CountNodes) { InsertNode }
далее CreateNode - получили указатель на новую ноду
а теперь в цикле добираемся до нужного элемента -1 ( offset - 1) т.к. предпоследний элемент хранит адрес структуры, перед которой мы будем вставлять новую. Заменяем адресацию в указателях в предпоследнем и добавляем указатель на (offset+1) из (Node->next = offset - 1 ) и возвращаем true.
0
6 / 6 / 4
Регистрация: 09.11.2011
Сообщений: 126
27.08.2013, 13:39  [ТС] 4
Цитата Сообщение от lowercase Посмотреть сообщение
C
1
2
3
4
struct list* insertElem(struct list *listStart, struct list *n) {
* * //... 
* * return listStart;
}
А как её реализовать не знаю, свой способ попробовал, но завершается с ошибкой.
C
1
2
3
4
5
6
7
8
struct list *insertElem(struct list *listStart, struct list *n) {
    struct list newElem;
 
    newElem.next = n->next;
    n->next = &newElem;
 
    return listStart;
}
Теория не очень помогла

Цитата Сообщение от gnuvse Посмотреть сообщение
C
1
2
3
4
...
n2_2 = n2.next;
n2.next = &n2_2;
...
Добавлено через 15 часов 38 минут


А почему так много функций, автор утверждает, что можно в одной сделать. Только я не знаю как)

PS. Функцию countNodes я написал, а как написать createNode. С insertNode вроде понятно немного. Offset это элемент после которого вставляем новый элемент?

Т.е.
0
Z3JheSBoYXQ=
339 / 234 / 83
Регистрация: 08.07.2012
Сообщений: 577
27.08.2013, 21:59 5
Можно вообще все писать в main, а че. Зачем нам функции, процедуры. Приятно ведь кушать все по отдельности, наслаждаясь вкусом каждого блюда. Так и тут. Мессиво, даже из хорошо оформленного кода, по меньшей мере вызывает легкую неприязнь. Каждая задача должна решаться в рамках одной функции, процедуры и решаться максимально автономно и хорошо. Кушая маленькими кусочками улучшается пищеварение, а попытка заглотнуть сверх физических возможностей организма чревато

Почему так, тут много всего, и удобство отладки, сопровождения, тестирования и прочее прочее прочее.

зы. по offset'у - это элемент перед которым надо вставить элемент, можно сделать что и после, ничего не мешает. Просто индексация в первом случае будет [offset-1], во втором [offset+1]
0
6 / 6 / 4
Регистрация: 09.11.2011
Сообщений: 126
27.08.2013, 22:14  [ТС] 6
Я только за разделения программы на мелкие блоки, но только я никак не врублюсь как написать createNode

C
1
2
3
4
5
6
...
struct node *createNode(struct list *listStart) {
    struct node *newElem;
    return newElem;
}
...
Так?
PS. Точно не так, ибо зачем мы тогда передаем указатель на начала списка. Не понимаю...
0
Z3JheSBoYXQ=
339 / 234 / 83
Регистрация: 08.07.2012
Сообщений: 577
27.08.2013, 22:51 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
#include <stdio.h>
#include <Stdlib.h>
#include <string.h>
#include <stdbool.h>
 
typedef struct Node{
    int somevalue;
    struct Node *next;
} node;
    
node * CreateNode(node **, int);
 
int main(){
    node *base = NULL;
            
    printf("Base addres: 0x%p\n", base);
    node *result = CreateNode(&base, 123);
    if (result){
            printf("Base addres: 0x%p\nNew node adres: 0x%p\nSomevalue:%d\n", base, result, result->somevalue);
        }
    free(result);           
    return 0;
}
 
node * CreateNode(node **base, int somevalue){
    node *newNode = calloc(1, sizeof(node));
    if (NULL == newNode){
        printf("error callocate memory for new node.Abort\n");
        return NULL;        
    }
    else {
        newNode->somevalue = somevalue;
        newNode->next = (node*)base;
        *base = (node*)&newNode;
        return newNode;
    }
}
Bash
1
2
3
4
Base addres: 0x00000000
Base addres: 0x0028FEBC
New node adres: 0x00740EA8
Somevalue:123
1
6 / 6 / 4
Регистрация: 09.11.2011
Сообщений: 126
27.08.2013, 23:32  [ТС] 8
я же даже в живую никогда "**" не видел.
Есть несколько вопросов: вопросы в комментариях кода.

PS. Мне кажется автор книги подразумевал не такой сложный способ("**" в книге нефига не сказано о них), ибо книга вроде как для нубов.
А можно реализовать добавление ноды, как предлагает автор? Хотя может он и подразумевал юзать **
0
Z3JheSBoYXQ=
339 / 234 / 83
Регистрация: 08.07.2012
Сообщений: 577
28.08.2013, 00:08 9
Можно, все можно . Просто топик называется списки и указатели а моя реализация полностью соответствует этой концепции

#define SIZE 10

**base просто создаем двумерный массив, аналогичен конструкции
array[SIZE][SIZE] - создаем матрицу 10х10
Код на самом деле банальный и простой. Просто надо четко уяснить связь указателей и массивов при передаче их в качестве аргументов функциям. Больше практики, ясность придет. Главное не отступай.

Добавлено через 4 минуты
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
   else {
        newNode->somevalue = somevalue;
        newNode->next = (node*)base;    //Вот здесь newNode указывает туда же куда и base или на сам base?
                            //Хотя, мне кажется, что нода указывает здесь на NULL;
Правильно мыслишь. У нас base выступает в качестве общего указателя на последнюю ноду, аналогично стеку, если список однонаправленный. Аналог регистра SP ( stack pointer ) в x86. 
                                      
        *base = (node*)&newNode; //Здесь, если мы передаём в ф-цию **base, то значит когда мы 
                          //разимновываем указатель "*base" мы записываем адресс новый ноды в base
                          //и теперь он указывает на неё. Я правильно понял?
Совершенно точно. :)
 
        return newNode;
 
    }
}
1
6 / 6 / 4
Регистрация: 09.11.2011
Сообщений: 126
28.08.2013, 00:45  [ТС] 10
fanatdebian, погуглив, выяснил, что ребята тоже юзают ** http://www.ibm.com/developerwo... ctures_02/ . Так как всё таки написать как предлагает автор?
Цитата Сообщение от gnuvse Посмотреть сообщение
Автор даёт подсказку, функция принимает 2 аргумента: указатель на на начало списка и указатель на элемент после которого должен встать новый элемент.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.08.2013, 00:45

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

Написать программу, которая вставляет в список L новый элемент F за каждым вхождением элемента E (2)
Друзья, помогите разобраться с кодом программы. Надо Написать программу, которая вставляет в...

Написать программу, которая реализует связный список
Написать программу, которая реализует связный список. Операции, которые должна выполнять программа:...

Написать процедуру, которая вставляет в непустой список L новый элемент E перед его последним элементом
Помогите пожалуйста

написать функцию которая на основе двух списков формирует новый список в котором чередуются элементы исходных
написать функцию которая на основе двух списков формирует новый список в котором чередуются...


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

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

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