Дашики
7 / 7 / 1
Регистрация: 26.09.2008
Сообщений: 477
1

Линейные списки и циклические списки

21.10.2008, 17:57. Показов 13697. Ответов 21
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Подскажите,кто как может,у меня тут 2 лабы,с чего мне начать,где можно материал взять??

1-ая лабораторная:
Линейные списки

Описать указанный абстракный тип данных (АТД) и основные функции работы с ним на абстрактном уровне. Реализовать процедуры необходимые для вставки, удаления элемента в указанный вид АТД, процедуру печати содержимого АТД, а также дополнительно реализовать процедуру указанную в варианте.Мой вариант: линейный двунаправленный список символов. Вставку и удаление символов производить по принципу очереди. Реализовать процедуру подсчета числа элементов.

2-ая лабораторная:
Циклические списки

Описать указанный абстракный тип данных и основные функции работы с ним на абстрактном уровне. Реализовать процедуры необходимые для вставки, удаления элемента в указанный вид АТД, процедуру печати содержимого АТД, а также дополнительно реализовать процедуру указанную в варианте, на конкретном языке программирования.Мой вариант однонаправленный циклический список символов. Реализовать процедуру подсчета суммы элементов.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.10.2008, 17:57
Ответы с готовыми решениями:

Линейные списки
Помогите пожалуйста в решении задачи! 1.Используйте линейные списки для хранения...

линейные списки
помогите пожалуйста срочно с написанием программы по линейным спискам: Создать список Р, что...

Линейные списки
Помогите пожалуста решить задачу. Уже неделю не могу решить! Где-то в воде нового элемена ошибка,...

Линейные списки
Представить одну из приведенную ниже таблицу в виде линейного списка L, элементами которого...

21
257 / 173 / 27
Регистрация: 17.10.2008
Сообщений: 770
22.10.2008, 00:59 2
Как я понял, это создание динамических списков, только первый простой, а второй после последнего элемента переходит на первый, попробуем реализовать...

Возможно попробуй почитать динамические списки, связные списки,или большой раздельчик "типы данных определяемые программистами".Только вот где почитать не подскажу...
0
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
22.10.2008, 04:36 3
А вот я подскажу где посмотреть, глянь тут... начиная с этой главы и пару вперёд, мот что почерпнёшь.
И кстати советую пользоваться системой поиска google.com там можно много чего найти
0
Брюс Всемогущий
35 / 35 / 1
Регистрация: 02.09.2008
Сообщений: 256
22.10.2008, 04:48 4
Задания впринцепи несложные, здеся вот накидал примерный образец, как первое задание делать(как я понял)
Delphi
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
PLineList=^TLineList;
TMyProc=procedure(p:PLineList);
TLineList=record //описывается типы данных
Data:integer;
Next:PlineList;
Last:PLineList;
end;
TMyList=class(TObject)
protected
Root,Tail:PLineList;
public
Constructor Create;
procedure AddNewElement(NewData:Integer);
procedure DelBedData(BedData:Integer);
function Search(MyData:Integer):integer;
procedure Process(MyProc:TMyProc);
procedure Clear;
Destructor Destroy;override;
end; 
 
Constructor TMyList.Create;
BEGIN
inherited Create;
Root:=nil;
Tail:=nil;
END;
 
procedure TMyList.AddNewElement(NewData:Integer);
VAR
MyElement, Poz:PLineList;
BEGIN
New(MyElement);
MyElement.Data:=NewData;
MyElement.Next:=nill;
if Root<>nil then 
begin
Root.Next:=MyElement;
MyElement.Last:=Root;
Root:=MyElement;
end
else
begin
MyElement.Last:=nil;
MyElement.Next:=nil;
Root:=MyElement;
Tail:=MyElement;
Exit;
end;
 
END;
 
procedure TMyList.DelBedData(BedData:Integer);
VAR
Cell, Key:PLineList;
BEGIN
if Root=nil then Exit;
New(Cell);
Cell.Data:=BedData;
Root.Next:=Cell;
Key:=Tail;
while (Key.Data<>BedData) do Key:=Key.Next;
if Key<>Root.Next then
begin
Root.Next:=nil;
Dispose(Cell);
if (Key=Root) and (Root=Tail) then
begin
Root:=nil;
Tail:=nil;
Dispose(Key);
Exit;
end;
if Key=Tail then
begin
Tail:=Key.Next;
Tail.Last:=nil;
Dispose(Key);
Exit;
end;
if Key=Root then
begin
Root:=Root.Last;
Dispose(Key);
Root.Next:=nil;
Exit;
end;
Cell:=Key.Last;
Cell.Next:=Key.Next;
Cell:=Cell.Next;
Cell.Last:=Key.Last;
Dispose(Key);
end
else
begin
Dispose(Root.Next);
Root.Next:=nil;
end;
END;
 
Destructor TMyList.Destroy;
BEGIN
Clear;
inherited;
END;
 
//до этого все было в отдельном модуле
 
//все в модуле где форма
procedure Graf(P:PLineList);
BEGIN
Form1.Memo1.Lines.Add(IntToStr(P.Data));
END; 
 
procedure TForm1.Button1Click(Sender: TObject);//AddElement
BEGIN
.....
Form1.Memo1.Clear;
MyList.Process(Graf);
..... //распечатываешь содержимое в мемо
END;
P.S. Здеся я в линейный двунаправленный список с сылкой на начало и конец (Root, Tail) вставлял Integer, если тебе надо символ (возможно за символ ты считаешь значение String), то тебе надо переделать тип данных в этом списке. Второе задание делать не буду, принцип такойже.

Код проверил, работает нармально
0
Дашики
7 / 7 / 1
Регистрация: 26.09.2008
Сообщений: 477
22.10.2008, 16:31  [ТС] 5
а как теперь в Паскале его реализовать?

Добавлено через 59 минут 24 секунды
и составте,плиз,2-ую прогу....

Добавлено через 2 часа 25 минут 26 секунд
и не могу разобраться,что с первой делать...
0
1513 / 780 / 103
Регистрация: 22.04.2008
Сообщений: 1,610
22.10.2008, 17:00 6
Дашустрик а сам не пробовал что-то делать ?
0
Дашики
7 / 7 / 1
Регистрация: 26.09.2008
Сообщений: 477
22.10.2008, 19:25  [ТС] 7
я пробовала,но просто я в списках дуб-дерево(((

Добавлено через 42 секунды
допустим,с сортировкой я разобралась

Добавлено через 1 час 25 минут 19 секунд
я так поняла 4 программы составить или как?

Добавлено через 54 секунды
или все процедуры в 1 прогу объединить?

Добавлено через 44 минуты 48 секунд
ну не даются мне списки,ну что я могу сделать?
0
Брюс Всемогущий
35 / 35 / 1
Регистрация: 02.09.2008
Сообщений: 256
22.10.2008, 19:44 8
Цитата Сообщение от Дашустрик Посмотреть сообщение
а как теперь в Паскале его реализовать?
а я на чем делал? на С+ по твоему чтоли, эт тоже паскаль.
А вообще как было сказано, лучше книжки почитай и сам все зделай, у тя все впереди
0
Дашики
7 / 7 / 1
Регистрация: 26.09.2008
Сообщений: 477
25.10.2008, 15:18  [ТС] 9
правильно ли я составила процедуру вставки согласно моему условию задания???

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
procedure IncludeInQueue( var FirstElem, LastElem: Queue; NewElem: TypeOfElem); 
 
var 
 
  ServiceVar: Queue; 
 
begin
 
new( ServiceVar ); 
 
  ServiceVar^.Elem:= NewElem;
ServiceVar^.NextElem:= nil; 
 
  if ( FirstElem= nil ) and ( LastElem= nil ) then begin
FirstElem:= ServiceVar; 
 
    LastElem:= ServiceVar 
 
  end 
 
    else begin
FirstElem^.NextElem:=ServiceVar;
FirstElem:=ServiceVar
end
end;
Жду ответа!!!!!

Добавлено через 18 минут 21 секунду
вот ещё вариант
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
procedure AddToList(X: Integer; var PointerEndList: List);
begin
   if PointerEndList = nil then
      begin
           New(PointerEndList);
           PointerEndList ^.Info := X;   
           PointerEndList ^.Next := nil;    
       end
  else         
    begin
        New(PointerEndList ^.Next);    
        PointerEndList := PointerEndList ^.Next;
        PointerEndList ^.Info := X;
        PointerEndList ^.Next := nil;
    end;
end;
та же процедура вставки
подскажите какая правильней!!

Добавлено через 51 минуту 26 секунд
нутак как?

Добавлено через 20 часов 32 минуты 31 секунду
я так поняла,что мою тему игнорируют
0
257 / 173 / 27
Регистрация: 17.10.2008
Сообщений: 770
25.10.2008, 20:48 10
Я то прогу написал, только всё никак не могу разобраться с дополнительными заданиями, поэтому и не выкладываю. Сам только в эти списки залез. думаю ещё недельку и разберуся,как только так сразу
0
Брюс Всемогущий
35 / 35 / 1
Регистрация: 02.09.2008
Сообщений: 256
26.10.2008, 19:27 11
На вскидку, магу тебе сказать что нужно примерно так
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
procedure AddToList(X: Integer);
var 
     NewElement: List;
begin
   New(NewElement);
NewElement^.Next:=nill;
NewElement^.info: =x;  
if PointerEndList = nil then         //предположительно у тебя ссылка на начало гдето до этого была описана
      begin
           PointerEndList := NewElement;   
       end
  else         
    begin
        PointerEndList^.Next := NewElement;
        PointerEndList:=NewElement;
    end;
end;
Но вазможно будет ошибка, т.к. я не понял какой вид данных ты создаешь(его структуру)
P.S. в будушем работай сам, не так это уж и сложно, это азы алгоритмизации.
0
257 / 173 / 27
Регистрация: 17.10.2008
Сообщений: 770
27.10.2008, 20:29 12
Дашустрик,
вот у меня и первые плоды.
Выкладываю первую лабораторную работу с двунаправленным списком.

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
program Project2;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
type
   StrPerem=string;
   List=^First;
   First=record
   data:StrPerem;
   next,pred:List;
   end;
   Second=record
   fir,las:List;//от first и last
   end;
 
procedure Add(var  L:Second);
var s:StrPerem;
    NowElem:List;
begin
   repeat
    Writeln('vvedi element spiska s:');
    Readln(s);
     if length(s)<>0 then
          begin
             NowElem:=new(List);
             NowElem^.next:=nil;
             NowElem^.pred:=nil;
             NowElem^.data:=s;
              if L.fir=nil then
                L.fir:=NowElem
              else
                 begin  //установка двойной связи между элементами
                    L.las^.next:=NowElem;//задание указателя предыдущего элемента на текущий
                    NowElem^.pred:=L.las;//задание указателя текущего элемента на предыдущий
                 end;
 
             L.las:=NowElem;//вставляем следующий элемент
          end;
   until length(s)=0;
end;
 
procedure Delete(var L:Second);
var NowElem,ElemWasDel:List;
    DelEl,Num:integer;
begin
   WriteLn('skoka udalit'' elementov DelEl:');
   ReadLn(DelEl);
   NowElem:=L.fir;
   Num:=1;
    while Num<>DelEl+1 do
      begin
         L.fir:=NowElem^.next;
         ElemWasDel:=NowElem;
         NowElem:=NowElem^.next;
         dispose(ElemWasDel);
         Num:=Num+1;
      end;
 
end;
 
procedure print(var L:Second);
var NowElem:List;
begin
   NowElem:=L.fir;
    while NowElem<>nil do
      begin
         Writeln(NowElem^.data);
         NowElem:=NowElem^.next;
      end;
end;
 
 
var i:integer;
    L:Second;
begin
   repeat
   Writeln('vvedi comandu i:');
   Readln(i);
     case i of
      1: Add(L);
      2: Delete(L);
      3: Print(L);
      4: i:=4;
     end;
   until i=4;
 
end.
Если необходимо могу пояснить как я делаю и что делаю,буквально по строчкам. Не стесняйся обращайся.
0
(Yellow_Duck)
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
27.10.2008, 20:44 13
когда вопрос задали?.аа 21ого.
как я понимаю, вторую еще не решили?

Добавлено через 2 минуты 21 секунду
Люди, а что такое абстрактный тип данных?
как я понимаю-массив?
и надо процедуры написать, для любого количества измерений этого массива?
то есть и трех и четырехмерный и пяти и т.д.хмм...или?
0
257 / 173 / 27
Регистрация: 17.10.2008
Сообщений: 770
27.10.2008, 21:10 14
упс забыл самое последнее,подсчитать число элементов.
вот маленькие изменения основной части программы и добавил ещё одну процедурку, чтоб наглядно было

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
procedure NumberEl(var L:Second);
var NowElem:List;
    Chis:integer;
begin
   NowElem:=L.fir;
   Chis:=0;
    while NowElem<>nil do
      begin
         Chis:=Chis+1;
         NowElem:=NowElem^.next;
      end;
         Writeln('Chislo Elementov=',chis);
end;
 
var i:integer;
    L:Second;
begin
   repeat
   Writeln('vvedi comandu i:');
   Readln(i);
     case i of
      1: Add(L);
      2: Delete(L);
      3: Print(L);
      4: NumberEl(L);
      5: i:=5;
     end;
   until i=5;
Добавлено через 5 минут 43 секунды
YeLLoW DucK,
Абстрактный, это любой тип данных который создаётся конкретно программистом, для удобства-если это не так, то подправьте, буду знать.

т.е. ты хочешь сказать чтоб в одном элементе 1 типа данных содержался ещё один абстрактный тип данных--это уже на дерево смахивает.если не вру
В данном примере нужен только одномерный.
0
Почетный модератор
64305 / 47600 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
27.10.2008, 21:50 15
Абстрактный, или как сейчас более принято, пользовательский тип данных это по сути объект или класс, как положено с полями, конструкторами и деструкторвми, набором функций и процедур. Например тип список, тип очередь, тип стек и т.д.
0
257 / 173 / 27
Регистрация: 17.10.2008
Сообщений: 770
27.10.2008, 23:14 16
Цитата Сообщение от Puporev Посмотреть сообщение
Абстрактный, или как сейчас более принято, пользовательский тип данных это по сути объект или класс, как положено с полями, конструкторами и деструкторвми, набором функций и процедур. Например тип список, тип очередь, тип стек и т.д.
Вопрос возник, значит, тот код что я парочку сообщений назад выложил, не является абстрактным типом данных?


Дашустрик,
У меня вопросик возник по второй лабораторке, процедура подсчёта суммы элементов:есть два варианта, метить как бы первый элемент(каким нибудь дополнительным знаком) и считать сумму до него, или же методом разрушения всего списка. поочерёдно удаляя каждый элемент?
0
Дашики
7 / 7 / 1
Регистрация: 26.09.2008
Сообщений: 477
28.10.2008, 10:21  [ТС] 17
Arriba,честно говоря я сама запуталась

Добавлено через 17 минут 29 секунд
Arriba,а у тя первая лаба компилируется??
0
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
28.10.2008, 14:44 18
Дашустрик, для того что-бы заработала убери
Код
{$APPTYPE CONSOLE}

uses
  SysUtils;
И убери все //bla-bla-bla
0
Дашики
7 / 7 / 1
Регистрация: 26.09.2008
Сообщений: 477
28.10.2008, 15:18  [ТС] 19
я уже это поняла,просто не успела написать....)))))))
0
Of Wolf and Man
999 / 198 / 5
Регистрация: 09.07.2008
Сообщений: 1,784
28.10.2008, 16:18 20
Цитата Сообщение от Arriba Посмотреть сообщение
Вопрос возник, значит, тот код что я парочку сообщений назад выложил, не является абстрактным типом данных?
Ты же создал свой собственный пользовательский тип прописав "type" - значит является.
Список сам по себе не является ... *забыл как его называть* ... встроенным чтоль * типом данных, ты его описываешь сам.
То что ты сделал - это динамический список.
Есть еще простой
Pascal
1
2
3
4
5
Type
list = record
a,b:integer;
n,i:boolean;
end;
Вышеописанная структура - тоже является пользовательским типом данных - списком, только статическим, ибо :
Pascal
1
var arr:array[0..5] of list;
ЗЫЖ
Динамические списки - моя любимая тема
0
28.10.2008, 16:18
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.10.2008, 16:18
Помогаю со студенческими работами здесь

Линейные 1направленные списки.
Вставка в нач. и конец списка, просмотр, поиск и удаление. Помогите поправить код программы....

Линейные связанные списки
Составить программу обработки списка. Вид списка: линейный дважды связанный. Тело программы должно...

ДСД. Линейные списки
Attention! Даны два целочисленных списка L1 и L2. Построить новый список L3, включив в него...

Имеются линейные однонаправленные списки
Имеются линейные однонаправленные списки: type p=^item; item=record ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru