VPF::Списки(хотябы однонаправленные )

afanp

Дата 26.11.2008, 15:07 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет

Просьба помочь со списками(как создававать список, выводить) У кого какая есть информация, советы. Смотрел в "Фундаментальных алгоритмах " ,но там к сожалению мало что понял. Понимаю зачем нужны указатели на начало и на следущий элемент, но как их правильно записать - хз.Поэтому надеюсь на вашу помощь.

666TEHb666

Дата 26.11.2008, 20:00 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 65
Регистрация: 5.10.2008
Где: Новокузнецк

Репутация: нет
Всего: нет

Однонаправленные списки делаются легко,я когда-то на билдере в институте делал их,жаль исходники удалил((так бы скинул.У меня остался код алгоритма ток на Турбо Паскале(на нем учился),я те приведу ниже его.Если голова на плечах есть и руки запросто переведешь в си))

Суть в том,что имеется некий класс,назовем его Tnode или в этом роде.Состоит он из необходимых свойств(переменные int string или что тебе надо чтобы в списке было.Кроме этого есть указатель(nextnode) того же типа что и класс.Имеется некоторый базовый указатель,скажем root,типа Tnode.Вначале он занулен.Ну и потом описываешь разные функции для работы со списком.Создание его - выделяешь память root и даешь значение внутренним полям,nextnode зануляешь.Чтобы создать следующий вглубь узел, объявляешь локальную переменную типа Tnode,run=root,пишешь
run->nextnode=new Tnode();
Продвигаешься путем run=run->nextnode;
И т.д.
Не разберешься совсем(даже по коду) в личку пиши,мож помогу если время будет..Хотя лучше сам ;)

P.S. Меню естественно делаешь на форме))Паскалевскую консоль в топку))В билдере все это легко делается..

Код


program linked_list;
uses
    Crt;
type
    nodeptr=^nodetype;
    nodetype=record
                   field:String;
                   nextnode:nodeptr;
    end;
var
   list:nodeptr;
   item:String;

procedure Menu;

begin
     ClrScr;
     TextColor(2);
     WriteLn;
     WriteLn('1 - Print list');
     WriteLn('2 - Add to the begin');
     WriteLn('3 - Add to the end');
     WriteLn('4 - Delete from the begin');
     WriteLn('5 - Delete from the end');
     WriteLn('6 - Find the node and insert another node before it');
     WriteLn('7 - Find the node and delete it');
     WriteLn('8 - Remove list');
     WriteLn('0 - Exit');
     WriteLn;
end;

procedure print_list;
var
   p:nodeptr;

begin
     p:=list;
     ClrScr;
     WriteLn;
     while p<>nil do
     begin
          TextColor(5);
          Write(p^.field);
          TextColor(1);
          Write(' // ');
          p:=p^.nextnode;
     end;
     WriteLn;WriteLn;
     TextColor(2);
     Write('Press <enter>:');
     TextColor(4);
     ReadLn;
end;

procedure add_begin;
var
   p:nodeptr;

begin
     TextColor(2);
     ClrScr;
     New(p);
     Write('Please enter the node''s field:');
     TextColor(4);
     ReadLn(p^.field);
     p^.nextnode:=list;
     list:=p;
end;

procedure add_end;
var
   run,p:nodeptr;

begin
     ClrScr;
     New(p);
     p^.nextnode:=nil;
     TextColor(2);
     Write('Please enter the node''s field:');
     TextColor(4);
     ReadLn(p^.field);
     if list=nil then
        list:=p
     else
     begin
          run:=list;
          while run^.nextnode<>nil do
                run:=run^.nextnode;
          run^.nextnode:=p;
     end;
end;

procedure delete_begin;
var
   p,t:nodeptr;

begin
     if list=nil then Exit;
     p:=list;
     t:=p^.nextnode;
     Dispose(p);
     p:=nil;
     list:=t;
end;

procedure delete_end;
var
   run,t,prev:nodeptr;

begin
     if list=nil then Exit;
     run:=list;
     if list^.nextnode=nil then
     begin
          Dispose(list);
          list:=nil;
     end
     else
     begin
          while run^.nextnode<>nil do
          begin
               prev:=run;
               run:=run^.nextnode;
          end;
     Dispose(run);
     prev^.nextnode:=nil;
     end;
end;

procedure find_insert;
var
   run,t,p:nodeptr;
   fnode,choose:String;
   i:Byte;

begin
     ClrScr;
     TextColor(2);
     Write('Please enter the node thet will be find:');
     TextColor(4);
     ReadLn(fnode);
     New(p);
     TextColor(2);
     Write('Please enter the node''s field:');
     TextColor(4);
     ReadLn(p^.field);
     if list=nil then
     begin
          p^.nextnode:=nil;
          list:=p;
     end
     else
     begin
          run:=list;
          if run^.field=fnode then
          begin
               p^.nextnode:=run;
               list:=p;
          end
          else
          begin
               i:=0;
               while run^.nextnode^.field<>fnode do
               begin
                    run:=run^.nextnode;
                    Inc(i);
                    if i=100 then
                    begin
                         i:=0;
                         repeat
                               ClrScr;
                               TextColor(2);
                               WriteLn('Can not find ',fnode);
                               WriteLn(' Continue search? y/n');
                               TextColor(4);
                               ReadLn(choose);
                         until (choose='y') or (choose='n');
                         case choose[1] of
                              'n':Exit;
                              'y':Continue;
                         end;
                    end;
               end;
               t:=run^.nextnode;
               run^.nextnode:=p;
               run^.nextnode^.nextnode:=t;
          end;
     end;
end;

procedure kill_list;
var
   t:nodeptr;

begin
     while list<>nil do
     begin
          t:=list^.nextnode;
          Dispose(list);
          list:=t;
     end;
end;

procedure find_delete;
var
   prev,t,run,p:nodeptr;
   fnode,choose:String;
   i:Byte;

begin
     ClrScr;
     TextColor(2);
     Write('Please enter the node thet will be find and delete:');
     TextColor(4);
     ReadLn(fnode);
     if list=nil then Exit;
     run:=list;
     if list^.field=fnode then
     begin
          t:=list^.nextnode;
          Dispose(list);
          list:=t;
     end
     else
     begin
          while run^.field<>fnode do
          begin
               prev:=run;
               run:=run^.nextnode;
               Inc(i);
               if i=100 then
               begin
                    i:=0;
                    repeat
                          ClrScr;
                          TextColor(2);
                          WriteLn('Can not find ',fnode);
                          WriteLn(' Continue search? y/n');
                          TextColor(4);
                          ReadLn(choose);
                    until (choose='y') or (choose='n');
                    case choose[1] of
                         'n':Exit;
                         'y':Continue;
                    end;
               end;
          end;
          t:=run^.nextnode;
          Dispose(run);
          run:=nil;
          prev^.nextnode:=t;
     end;
end;

begin
     list:=nil;
     repeat
           Menu;
           TextColor(1);
           WriteLn;
           Write('Please select item:');
           TextColor(4);
           ReadLn(item);
           if Ord(item[0])>1 then Continue;
           case item[1] of
                '0':Halt;
                '1':print_list;
                '2':add_begin;
                '3':add_end;
                '4':delete_begin;
                '5':delete_end;
                '6':find_insert;
                '7':find_delete;
                '8':kill_list;
           end;
     until item='0';
end.

Это сообщение отредактировал(а) 666TEHb666 - 26.11.2008, 20:03

afanp

Дата 26.11.2008, 20:23 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет

666TEHb666, забыл указать, что классы мы еше не проходили, и делаем все на основе структур smile

еще вся беда в том, что не могу понять в какой момент нужно направлять указатель smile

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

Это сообщение отредактировал(а) afanp - 26.11.2008, 20:26

666TEHb666

Дата 26.11.2008, 21:08 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 65
Регистрация: 5.10.2008
Где: Новокузнецк

Репутация: нет
Всего: нет

Структуры в C++ рассматриваются как классы правда без многих приятных моментов, но все же.Я писал список на структурах,потом препод посоветовал просто заменить слово struct на class,так что с ними и знакомиться особо тогда не пришлось..но если на структурах то тож самое,пиши вместо класса структуру и все.Также указатель типа структуры и т.д.

NULL ток последний указатель(первоначально root,потом root->nextnode,потом root->nextnode->nextnode и т.д.).Когда необходимо создать следующий элемент списка,он(nextnode) получает память а следовательно(он ведь того же типа что и структура) поле nextnode,так как теперь это поле(указатель) последнее то зануляем его.root->nextnode=NULL.Потом при необходимости опять выделяем память ему root->nextnode=new Tnode().У нас новый nextnode,зануляем его(он ведь теперь последний).Вот и весь алгоритм,суть его.Пробег по списку осуществляеьтся как я уже сказал Tnode *run=root;run=run->nextnode.И т.д.Чтоб например последний элемент найти запускаешь цикл аля
while(run->nextnode!=NULL)
run=run->nextnode;
Таким образом найдешь последний элемент и можешь добавлять новый узел в конец списка аля run->nextnode=new Tnode();run->nextnode->nextnode=NULL;

Все еще непонятно?))А вообще есть очень большое количество литературы посвященной спискам,деревьям,очередям и т.д.Та и в нете мануалей полно.Почитай,интересно;)

Если совсем непонятно написал,то может завтра коль будет время напишу те эти списки,но лучше бы чтоб сам конечно понял..Если вы потом начнете изучать их сортировку...запаришься))Разбирай сразу.Я помнится долго делал сортировку хэш-таблицами,в нете почему-то мало инфы про них,да и в книгах чот не нашел у с..тогда я помучался))но сделал...Лан это все лирика,думай)У тя ночь впереди))

P.S.ностальгирую по первому курсу...)) smile

хех..

Это сообщение отредактировал(а) 666TEHb666 - 26.11.2008, 21:09

afanp

Дата 27.11.2008, 16:48 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет

Код


#include "stdafx.h"
#include <iostream>
using namespace std;
struct Man{
    int num;
    Man*next;
};
Man*first=NULL;
void add(){
    if(first=NULL){
    first=new Man;
    cin >> first->num;
    first->next=0;
    }
    else{
        Man*now=new Man;
        now->next=0;
        cin>>now->num;
        first->next=now;
        first=now;
    }
}

int main(){
    int x=1,a;
    while(x!=0){
        cout << "Press 1 for add,2 for exit";
        cin >> a;
        if(a==1) add();
        if(a==2) x=0;
    }
    system("pause");
    return 0;
}

вотъ (
Ну кто подскажет че надо исправить? smile

Это сообщение отредактировал(а) afanp - 27.11.2008, 18:23

Black_Wolf

Дата 28.11.2008, 12:46 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 25.6.2007
Где: Свердловская обла сть

Репутация: нет
Всего: нет

afanp
10-я строка. Не "=" ,а "==".
И не хорошо как то получается, уходим и не убираем за собой.
В односвязном списке указатель на первый элемент лучше не изменять, а завести еще один указатель на текущий элемент в списке.

Это сообщение отредактировал(а) Black_Wolf - 28.11.2008, 12:49

afanp

Дата 28.11.2008, 16:04 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет

а как удалить 1ый элемент из списка? вот када мы удаляем из середины то мы тупо перенаправляем например с 1ого на 3ий, а со 2ого на третий обнуляем. А как быть с первым?

Код


void del(){ 
    int k=1,del;
    now = begin;
    cout << " vvedite nomer elementa ";
    cin >> del;
    if(del!=1){
    while(now){
        if (k==del-1){
            now2=now->next;
            now->next=now2->next;
            now2->next=0;
        }
        now=now->next;
        k++;
        }
    }
    else{
        
    }
}

Black_Wolf

Дата 1.12.2008, 06:33 (ссылка)

(нет голосов)

Загрузка ...

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

Код


Man* tmp = first;
first=first->next;
delete tmp; //Освободим память в куче выделенную для первого элемента

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »