Обработка строки/Двусвязный список

@Зума · Регистрация: 12.03.2010

Студворк — интернет-сервис помощи студентам

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

Так звучит задание.
Я не совсем понимаю, что от меня хотят. Загнать каждое слово в отдельный элемент списка? А смысл? Намного проще обрабатывать напрямую строку.
Загонять по букве? Ещё глупее.
Помогите, пожалуйста, понять принцип. Сам я никак.

Добавлено через 1 час 17 минут
И, да. Ежели что, я не прошу писать за меня программу. Я прошу объяснить мне только принцип её действия, буде таковой найдётся. Сам я это сделать не в силах.

@Dnnn · 15.04.2010, 10:57

если "двусвязные списки" и нужно "перевернуть слово", то наверное каждый символ строки в отдельном элементе списка. смысла особого нет, просто работа с двусв списками.
может как-то так - идете по первому списку. запоминаете ссылку на начало очередного слова и ссылку на предыдущий элемент, считаете кол-во символов в слове.
если текущий элемент = пробел, то слово закончилось. Надо внести его посимвольно во второй список.
В зависимости от четной или нечетной длины слова двигаетесь от начала слова до конца (ссылка на начало слова запоминается заранее, на конец слова = указателю на предыдущий элемент списка) или наоборот от конца до начала (вот тут-то и пригодится то, что список двунаправленный) и заносите буквы слова во второй список.
потом возвращаетесь к первому списку, запоминаете начало следующего слова, обнуляете размер следующего слова и идете дальше.

@Зума · 15.04.2010, 12:09 **[ТС]**

Всё ясно. Спасибо большое за объяснение!

@Зума · 11.05.2010, 11:33 **[ТС]**

Спустя месяц всё та же проблема.
Итак, я написал процедуру:

Pascal
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
procedure main(spis1,spis2:list);
var i,j:integer; tmp,tmp1,tmp2:list;
begin
i:=0;
tmp:=spis1;
while tmp^.next<>nil do begin
 tmp2:=tmp;
 j:=i;
 while (tmp^.data<>' ') and (tmp^.next<>nil) do begin
  tmp:=tmp^.next;
  i:=i+1;
 end;
 j:=i-j;
 tmp1:=tmp;
 if j mod 2=0 then begin
  repeat
   add(spis1,spis2,tmp1^.data);
   tmp1:=tmp1^.prev;
  until tmp1^.data=tmp2^.data;
 end
 else
  repeat
   add(spis1,spis2,tmp2^.data);
   tmp2:=tmp2^.next;
  until tmp2^.data=tmp1^.data;
 if tmp^.next^.data=' ' then add(head,tail,' ');
 while (tmp^.next^.data=' ') and (tmp^.next<>nil) do tmp:=tmp^.next;
 end;
end;

Data здесь - переменная типа char.
Странное дело - при вводе просто строки процедура не работает совсем (выдаёт пустой список), а если в строке два слова, разделённых пробелами - вообще вылетает с heap overflow error.
Halp!

@Dnnn · 11.05.2010, 17:13

heap overflow error - переполнение области кучи, те где-то видно зацикливается.
а что на входе в эту процедуру? spis1 - указатель на 1 эл-т первого списка? в первом списке данные нормальные?
как работает процедура add и зачем там 2 указателя ( spis1 и spis2) ведь добавляете в какой-то один список?
if tmp^.next^.data=' ' then add(head,tail,' '); - вот эта команда к чему относится и что такое head и tail ?

@Зума · 13.05.2010, 09:22 **[ТС]**

Значит так. spis1 - начало первого списка, spis2 - второго.
Данные нормальные, всё прекрасно выводится.
Процедуру add я взял из этой темы, а начало и конец для того, чтобы добавлялось в том порядке, в котором элементы идут, а не задом наперёд. вообще в ту процедуру ещё входит создание списка, если его нет, поэтому надо указывать начало и конец. Не очень-то удобно, я это уберу.
Head и tail - начало и конец уже заданного в начале программы второго списка. Т.е. head=spis2. Команда задана для добавления одного пробела, вне зависимости от того, сколько их было в исходной строке.

@Dnnn · 13.05.2010, 09:58

приведите уж тогда целиком программу )
то, что начало списка2 в одной процедуре в 2 разных переменных - не есть хорошо по-моему.
а список 2 в начале работы процедуры пустой?
почему параметр spis2 передается в процедуру по значению, только как входной (без var)?

@Зума · 13.05.2010, 17:52 **[ТС]**

Pascal
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
program lab14;
uses crt;
type
  Tinf=char; {тип данных, который будет храниться в элементе списка}
  List=^TList;  {Указатель на элемент типа TList}
  TList=record {А это наименование нашего типа "запись" обычно динамические структуры описываются через запись}
    data:tinf;  {данные, хранимые в элементе}
    next,    {указатель на следующий элемент списка}
    prev:List;   {указатель на предыдущий элемент списка}
  end;
 
  var
  SpisNach,head, {указатель на начало списка и}
  SpisEnd,tail,   {указатель на конец списка. Эти два указателя }
  tmpl,tmpl2:List; {неотъемлемая часть в двунаправленном списке}
  znach:tinf;
 
procedure Add(var nach,ends:List;znach:TInf);
begin
  if nach=nil then {не пуст ли список, если пуст, то}
  begin
    Getmem(nach,SizeOf(TList)); {создаём элемент, указатель nach уже будет иметь адрес}
    nach^.next:=nil; {никогда не забываем "занулять" указатели}
    nach^.prev:=nil; {аналогично}
    nach^.data:=znach;
    ends:=nach; {изменяем указатель конца списка}
  end
  else {если список не пуст}
  begin
    GetMem(ends^.next,SizeOf(Tlist)); {создаём новый элемент}
    ends^.next^.prev:=ends; {связь нового элемента с последним элементом списка}
    ends:=ends^.next;{конец списка изменился и мы указатель "переставляем"}
    ends^.next:=nil; {не забываем "занулять" указатели}
  end;
  ends^.data:=znach; {заносим данные}
end;
 
procedure Print(spis1:List);
begin
  if spis1=nil then
  begin
    writeln('‘ЇЁб®Є Їгбв.');
    exit;
  end;
  while spis1<>nil do
  begin
    Write(spis1^.data);
    spis1:=spis1^.next
  end;
end;
 
Procedure FreeStek(spis1:List);
var
  tmp:List;
begin
  while spis1<>nil do
  begin
    tmp:=spis1;
    spis1:=spis1^.next;
    FreeMem(tmp,SizeOf(Tlist));
  end;
end;
 
procedure main(spis1,spis2:list);
var i,j:integer; tmp,tmp1,tmp2:list;
begin
i:=0;
tmp:=spis1;
while tmp^.next<>nil do begin
 tmp2:=tmp;
 j:=i;
 while (tmp^.data<>' ') and (tmp^.next<>nil) do begin
  tmp:=tmp^.next;
  i:=i+1;
 end;
 j:=i-j;
 tmp1:=tmp;
 if j mod 2=0 then begin
  repeat
   add(spis1,spis2,tmp1^.data);
   tmp1:=tmp1^.prev;
  until tmp1^.data=tmp2^.data;
 end
 else
  repeat
   add(spis1,spis2,tmp2^.data);
   tmp2:=tmp2^.next;
  until tmp2^.data=tmp1^.data;
 if tmp^.next^.data=' ' then add(head,tail,' ');
 while (tmp^.next^.data=' ') and (tmp^.next<>nil) do tmp:=tmp^.next;
 end;
end;
 
begin
  SpisNach:=nil;
  SpisEnd:=nil;
  head:=nil;
  tail:=nil;
  clrscr;
            read(znach);
            while znach<>'#' do begin
            Add(SpisNach,SpisEnd,znach);
            read(znach);
          end;
            Print(SpisNach);
            readkey;
            main(spisnach,head);
            print(head);
            readkey;
  FreeStek(SpisNach);
end.

Комментарии не мои. Как и сами процедуры, впрочем.

@Dnnn · 14.05.2010, 12:18

Pascal
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
program lab14;
uses crt;
type
  Tinf=char; {тип данных, который будет храниться в элементе списка}
  List=^TList;  {Указатель на элемент типа TList}
  TList=record {А это наименование нашего типа "запись" обычно динамические
структуры описываются через запись}
    data:tinf;  {данные, хранимые в элементе}
    next,    {указатель на следующий элемент списка}
    prev:List;   {указатель на предыдущий элемент списка}
  end;
 
  var
  Spis1,Spis2, {указатель на начало списка и}
  Spis1End,Spis2End   {указатель на конец списка. Эти два указателя }
      :List; {неотъемлемая часть в двунаправленном списке}
  znach:tinf;
 
procedure Add(var nach,ends:List;znach:TInf);
var tmp: List;
begin
  new(tmp);
  tmp^.data := znach;
  tmp^.next := nil;
  tmp^.prev := ends;
 
  if nach=nil then {не пуст ли список, если пуст, то}
     nach:=tmp
  else {если список не пуст}
     ends^.next:=tmp; {связь нового элемента с последним элементом
списка}
 
  ends:= tmp;{конец списка изменился и мы указатель "переставляем"}
end;
 
procedure Print(spis1:List);
begin
  if spis1=nil then
  begin
    writeln('Pusto!');
    exit;
  end;
  while spis1<>nil do
  begin
    Write(spis1^.data);
    spis1:=spis1^.next
  end;
  writeln;
end;
 
Procedure FreeDec(spis1:List);
var
  tmp:List;
begin
  while spis1<>nil do
  begin
    tmp:=spis1;
    spis1:=spis1^.next;
    dispose(tmp);
  end;
end;
 
procedure main(VAR spis1,Spis1End, spis2, spis2END:list);
  var j:integer; tmp,tmp1,tmp2:list;
 
begin
 
 tmp:=spis1;
 while tmp<>nil do begin {идем по первому списку до конца}
 
   while (tmp^.data = ' ') and (tmp<>nil) do {пропускаем пробелы}
       tmp := tmp^.next;
 
   tmp1:=tmp; {указатель на начало слова!}
 
   j:=0; {длина слова}
   while (tmp^.data<>' ') and (tmp<>nil) do
     begin {пока не пробел и не конец списка1 }
      tmp:=tmp^.next;
      j:=j+1;
     end;
 
   if j = 0 then break; { нет слова }
 
   if tmp = nil then { последнее слово }
     tmp2 := Spis1End
   else
     tmp2:=tmp; {указатель на конец слова}
 
   while (tmp2<>nil) and (tmp2^.data = ' ') do { если пробел в конце - возвращаемся обратно}
            tmp2 := tmp2^.prev;
 
   if spis2<>nil then add(spis2,spis2END,' '); {если в списке 2 что-то уже есть - добавл. пробел перед очередным словом}
 
   if j mod 2=0 then
    repeat
     add(spis2,spis2END,tmp2^.data);
     tmp2:=tmp2^.prev;
    until (tmp2^.next = tmp1) or (tmp2 = nil)
   else
    repeat
      add(spis2,spis2END,tmp1^.data);
      tmp1:=tmp1^.next;
    until (tmp1 = nil) or (tmp2=tmp1^.prev) or (j=1) ;
 
 end;
end;
 
begin
  Spis1    :=nil;  Spis1End :=nil;
  Spis2    :=nil;  Spis2End :=nil;
  clrscr;
  writeln('vvedite el-ti 1 spiska (konec vvoda - #)');
  read(znach); 
  while znach<>'#' do begin
     Add(Spis1,Spis1End,znach); 
     read(znach);
  end;
  Print(Spis1); readkey;
  main(spis1, spis1End, Spis2, Spis2End);
  writeln('Poluch. spisok:'); print(Spis2); readkey;
  FreeDec(Spis1);
end.

@Зума · 15.05.2010, 07:41 **[ТС]**

О, спасибо большое! Я, к слову, переписал программу с нуля без кражи чьих-то процедур, но в ней всё равно что-то не то. Целый вечер над ней сидел - безрезультатно.
Ваш пост был весьма приятной неожиданностью

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@Dnnn 1063 / 130 / 34 Регистрация: 09.10.2009 Сообщений: 271
	15.04.2010, 10:57
	если "двусвязные списки" и нужно "перевернуть слово", то наверное каждый символ строки в отдельном элементе списка. смысла особого нет, просто работа с двусв списками. может как-то так - идете по первому списку. запоминаете ссылку на начало очередного слова и ссылку на предыдущий элемент, считаете кол-во символов в слове. если текущий элемент = пробел, то слово закончилось. Надо внести его посимвольно во второй список. В зависимости от четной или нечетной длины слова двигаетесь от начала слова до конца (ссылка на начало слова запоминается заранее, на конец слова = указателю на предыдущий элемент списка) или наоборот от конца до начала (вот тут-то и пригодится то, что список двунаправленный) и заносите буквы слова во второй список. потом возвращаетесь к первому списку, запоминаете начало следующего слова, обнуляете размер следующего слова и идете дальше. 0

@Зума 3 / 3 / 1 Регистрация: 12.03.2010 Сообщений: 28
	15.04.2010, 12:09 [ТС]
	Всё ясно. Спасибо большое за объяснение! 0

@Dnnn 1063 / 130 / 34 Регистрация: 09.10.2009 Сообщений: 271
	11.05.2010, 17:13
	heap overflow error - переполнение области кучи, те где-то видно зацикливается. а что на входе в эту процедуру? spis1 - указатель на 1 эл-т первого списка? в первом списке данные нормальные? как работает процедура add и зачем там 2 указателя ( spis1 и spis2) ведь добавляете в какой-то один список? if tmp^.next^.data=' ' then add(head,tail,' '); - вот эта команда к чему относится и что такое head и tail ? 0

@Зума 3 / 3 / 1 Регистрация: 12.03.2010 Сообщений: 28
	13.05.2010, 09:22 [ТС]
	Значит так. spis1 - начало первого списка, spis2 - второго. Данные нормальные, всё прекрасно выводится. Процедуру add я взял из этой темы, а начало и конец для того, чтобы добавлялось в том порядке, в котором элементы идут, а не задом наперёд. вообще в ту процедуру ещё входит создание списка, если его нет, поэтому надо указывать начало и конец. Не очень-то удобно, я это уберу. Head и tail - начало и конец уже заданного в начале программы второго списка. Т.е. head=spis2. Команда задана для добавления одного пробела, вне зависимости от того, сколько их было в исходной строке. 0

@Dnnn 1063 / 130 / 34 Регистрация: 09.10.2009 Сообщений: 271
	13.05.2010, 09:58
	приведите уж тогда целиком программу ) то, что начало списка2 в одной процедуре в 2 разных переменных - не есть хорошо по-моему. а список 2 в начале работы процедуры пустой? почему параметр spis2 передается в процедуру по значению, только как входной (без var)? 0

@Зума 3 / 3 / 1 Регистрация: 12.03.2010 Сообщений: 28
	15.05.2010, 07:41 [ТС]
	О, спасибо большое! Я, к слову, переписал программу с нуля без кражи чьих-то процедур, но в ней всё равно что-то не то. Целый вечер над ней сидел - безрезультатно. Ваш пост был весьма приятной неожиданностью 0