Двунаправленный список на Си.

Являюсь начинающим в разработке на языке Си

начинающим лодырем и попрошайкой

либо ты пишешь свой вариант, кривизну которого тебе помогут поправить местные сердобольные, либо собираешь котомку с вещами и уходишь красиво в закат.

Если все в статике и max size 100 то зачем здесь список? Бери массив на 100 символов и указатель на последний символ и читай свою последовательность

Для решения задачи сформируйте двунаправленный список.

сделайте стек из двунаправленного списка (структур у которых есть указатели на предыдущий и последующий).

Если символ не Ch создать элемент и push его в стек (добавить в конец списка),

если Ch то pop из стека (удалить последний элемент).

Дошли до конца - печать полученного списка от начала до конца.

код за вас вряд-ли будут писать. Это только вредить

Я сделяль:

struct Node {
    char data;
    struct Node* next;
    struct Node* prev;
};

и столкнулся с проблемой в решении следующей задачи

Ты описал задачу. А где описание проблемы с которой ты столкнулся в процессе ее решения?

Всё в статике, никаких динам. массивов и тд. maxsize взять за 100

В задаче про это ни слова.

На бумаге всё проще простого, но с реализацией на Си есть проблемы

Я могу представить, что это за проблемы, раз ты даже код не приложил. Тогда расписывай своё решение «на бумаге», пойдём от него

2 отмены подряд уберут 2 узла, а должны взаимно аннигилировать.

Пофиг :)

нифига, исправляй давай. Либо два указателя, либо перебор в обратном направлении.

Нибудю :3

На бумаге всё проще простого

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

man sys/queue.h

Development.

в спортлото пожалуюсь

2 отмены подряд уберут 2 узла, а должны взаимно аннигилировать.

На самом деле UB, так как в условиях про это ничего нет, равно как и про направление перебора символов.

Среди букв есть специальный символ Ch, появление которого означает отмену предыдущего символа.

Из этого можно сделать вывод, что Ch является точно такой же буквой, как и любоя другая, и может быть отменён.

Но условие всратое, да.

Учитывая вхождение этого символа, преобразуйте последовательность.

Куда преобразовать то?

Ну нельзя же быть таким балбесом! Задай свой вопрос ГПТ хотя бы для начала. Что за люди пошли: ни украсть, ни покараулить. Вообще соображалки нет.

Из списка символов сформировать связный список, где в каждом листе по символу, затем пройтись по этому списку и если встретится определённый символ в листе, то заменить текущим листом предыдущий. Типа есть строка ABXCDEXFG из неё строится список

• A<->B<->X<->C<->D<->E<->X<->F<->G

теперь проходимся по нему и если встретим символ X то убираем предыдущий лист, ставя себя на место него.

• A<->X<->C<->D<->X<->F<->G

Тоесть берём child пред-предыдущего листа и меняем его на себя, а свой parent на на parent из предыдущего, который анигилируем.

X<->X

Из списка символов сформировать связный список, где в каждом листе по символу

связный список, где в каждом листе по символу = список символов

Из списка символов сформировать список символов

ЯННП

Мои полномочия всё, закончились. Все вопросы наверх :3

Одно и тоже, но в разной упаковке. Символы в элементах массива, символы в элементах связного списка.

Из массива символов сформировать двунаправленный связанный список. Ок. А преобразовать то куда?

Налево.

специальный символ Ch

Я не знаю такого символа. Может быть это имя переменной, которая хранит код того специального символа?

Можете предложить свой пример решения?

А то, ня:

package Test;

import java.util.Arrays;

public class AbcPoint
{
	public static void main(String[] args)
	{
		String str[] = {"A", "B", "C", "D", "Ch", ".",};
		int j = 0;
		int k = 0;
		System.out.println(Arrays.toString(str));
		for(int i=0; i<str.length; i++)
		{
			if(str[i].equals("Ch")) 
				{
				str[i-1] = "";
				j++;
				}
		}
	   System.out.println(Arrays.toString(str));
	   String sub[] = new String[(str.length -j)];
	   for(int i=0; i<str.length; i++)
		{
			if(!(str[i].equals("")))
				{
				sub[k] = str[i];
				k++;
				}
		}
       System.out.println(Arrays.toString(sub));
}
}

Либо два указателя, либо перебор в обратном направлении

Как мне видится - даже с аннигиляцией если спец-символ фиксированный то список нафиг не впился. Всё становится веселее если он является функцией предыдущего - тогда без полного прохода назад не обойтись, и без списка придётся двигать потенциально длинный хвост.

ПыСы. Хорошая задачка.

Всё очень просто. Я сейчас объясню.

1. Берёшь свой двусвязный список, обходишь с конца и строешь односвязный список с обратным порядком элементов.

2. Проходишься по односвязному списку, на каждом этапе если текущая буква нормальная, добавляешь её в аккумулятор, а если Ch, то игнорируешь следующую букву.

3. Из полученного односвязного списка строишь обратно двусвязный. Ну или не строишь, нормальные списки рулят, а двусвязные — фигня беспонтовая, вообще неясно зачем нужны и кому.

Re #1 - бессмысленный waste of CPU cycles.

Re #3 - вы из односвязного списка даже элемент удалить не сможете без указателя на предыдущий.

Сильно не тестировал, но вроде работает.

#include <stdbool.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <unistd.h>

struct node {
  char c;
  struct node *prev;
  struct node *next;
};

struct node *read_string(void);

void process_string(struct node **node);

void write_string(struct node *node);

int main(void)
{
  struct node *node = read_string();
  process_string(&node);
  write_string(node);
}

struct node *alloc_node(void);

struct node *read_string(void)
{
  struct node *first = NULL;
  struct node *prev = NULL;
  while (true) {
    char c;
    ssize_t rv = read(0, &c, 1);
    if (rv != 1) abort();
    struct node *curr = alloc_node();
    curr->c = c;
    curr->prev = prev;
    if (prev != NULL) prev->next = curr;
    prev = curr;
    if (first == NULL) first = curr;
    if (c == '.') break;
  }
  prev->next = NULL;
  return first;
}

struct node *alloc_node(void)
{
  static struct node buffer[100];
  static size_t next = 0;
  if (next >= sizeof(buffer) / sizeof(buffer[0])) abort();
  return &buffer[next++];
}

void remove_node(struct node *node);

void process_string(struct node **node)
{
  struct node *n = *node;
  while (n != NULL) {
    if (n->c == 'H') {
      if (n->prev != NULL) remove_node(n->prev);
      remove_node(n);
    }
    n = n->next;
  }
  n = *node;
  while (n->next != NULL && n->next->prev != n) n = n->next;
  *node = n;
}

void remove_node(struct node *node) {
  if (node->prev != NULL) node->prev->next = node->next;
  if (node->next != NULL) node->next->prev = node->prev;
}

void write_string(struct node *node)
{
  while (node != NULL) {
    ssize_t rv = write(1, &node->c, 1);
    if (rv != 1) abort();
    node = node->next;
  }
}

LamerOk: ой, молодца!

Всё очень просто. Я сейчас объясню.

Я бы, наверное, просто шёл по строке и пушил байты в стек, а по Ch выщёлкивал бы один. Зачем списки? почему двусвязные? загадка.

Программа с ошибкой. Что если «Ch» имеет индекс == 0 ?

Выражение str[i-1] скажет «упс»…

Вот рассказ на эту тему - http://samlib.ru/b/bykow_walerij_alekseewich/sboi55.shtml

Java может работать и падать одновременно.

вы с Эрлангом путаете.

Красота! ❤️

Да это спасибо. if надо добавить:

if(i > 0 && str[i].equals("Ch")) 

Можете предложить свой пример решения?

Вы хотите бесплатно?

Господи, да задача яйца выеденного не стоит.

Я бы, наверное, просто шёл по строке и пушил байты в стек, а по Ch выщёлкивал бы один. Зачем списки? почему двусвязные? загадка.

Видимо стек реализован на базе двусвязного списка.

Господи, да задача яйца выеденного не стоит.

А Вы давно на цену яиц смотрели?

А Вы давно на цену яиц смотрели?

Не поверите. Понятия не имею. Этими вопросами благоверная занимается.

Из списка символов сформировать список символов

ЯННП

Ну очевидно же, что на сях надо написать простейший интерпретатор лишпа, в котором реализовать элементарный ДСЛ для решения задачи!

copy-and-swap (комментарий)

очевидно же, что на сях надо написать простейший интерпретатор лишпа, в котором реализовать элементарный ДСЛ для решения задачи!

…чтобы больше никогда не писать на сях.

вы из односвязного списка даже элемент удалить не сможете без указателя на предыдущий.

scheme@(guile-user)> (define l '(1 2 3 4 5 6))
scheme@(guile-user)> (set-cdr! (cdr l) (cdddr l))
scheme@(guile-user)> l
$7 = (1 2 4 5 6)

Ой, что-это, третий элемент списка куда-то делся!

Ой, что-это, третий элемент списка куда-то делся!

Оуеть. Я думал там хоть какие-то зачатки понимания data structures имеются… Удачи!

Что этот пример по Вашему доказывает? Что из односвязного списка модн удалить элемент без ссылки на предыдущий?!

Сейчас будет как с миллионом…:-(