VPF::Двухсвязный линейный список на C

lesha_od

Дата 3.12.2006, 15:19 (ссылка)

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

Загрузка ...

Новичок

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

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

В университете дали задание сделать двухсвязный линейный список, над которым можно было бы выполнять определенные действия.
Но при этом я не понимаю, что представляет этот тип списка. И что именно должны делать те или иные операции, куда добавлять элементы и т.п.
Преподавателя увы сложно выловить. Вот само задание:
-------
Задание
Реализовать линейный двухсвязный список для хранения следующих данных:
- фамилия,
- год поступления,
-средний балл.
Обеспечить выполнение операций:
- добавление элемента в неупорядоченный список,
- удаление элемента с заданным полем «фамилия» в неупорядоченном списке,
- сортировка списка по полю «фамилия»,
- добавление и удаление заданного элемента из упорядоченного списка с поиском «слева» и «справа»,
- распечатка содержимого списка.
-------
То есть должен быть список, его элементы, и связи между элементами. А вот какие связи - это мне неизвестно.
Вот так я начинал делать программу (но это неправильно - нужен другой тип списка).

Код


#include <iostream>
#include <conio.h>
#include <windows.h>
using namespace std;

struct Elem 
{
    char surname[30];
    int year;
    double avg;
    Elem * next;
    Elem * prev;
    Elem(char * sn,int y, double a)
    {
        strcpy(surname,sn);
        year = y;
        avg = a;
        next=NULL;
        prev=NULL;
    }
    Elem()
    {
        year = 0;
        avg=0;
        strcpy(surname,"");
        next=NULL;
        prev=NULL;
    }
};

class List
{
    Elem *head;
    Elem *tail;
public:
    List():head(NULL),tail(NULL){}
    void Print()const;
    void AddToHead(const Elem &value);
};



void List::Print()
{
    Elem * ptr = head;
    if (head==NULL)
        cout<<endl<<" List is Empty"<<endl;
    cout<<endl;
    while(ptr)
    {
        cout<<ptr->surname<<endl;
        cout<<ptr->year<<endl;
        cout<<ptr->avg<<endl;
        ptr = ptr->next;
    }

}

void List::AddToHead(const Elem & value)
{
    Elem * newvalue = new Elem;
    strcpy(newvalue->surname,
        value.surname);
    newvalue->year = value.year;
    newvalue->avg = value.avg;
    if (NULL == head)
    {
        head = tail = newvalue;
    }
    else{
        newvalue->next = head;
        head = newvalue;
        newvalue->next->prev = head;
    }
}

void main() {
List l1;
Elem e1;
strcpy(e1.surname,"aaa");
e1.year=1997;
e1.avg=15;
l1.AddToHead(e1);
Elem e2;
strcpy(e2.surname,"bbb");
e2.year=1953;
e2.avg=16;
l1.AddToHead(e2);
l1.Print();
}

Поясните, пожалуйста, что от меня хотят. Либо если не сложно, как это реализовать.

DFooz

Дата 3.12.2006, 16:15 (ссылка)

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

Загрузка ...

Шустрый

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

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

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

Код


#include <iostream>
#include <cstdlib> //for exit
#include <iomanip>
using namespace std;

struct card {
                            char *author;
                            char *title;
                            char *firm;
                            int edition;
                            int year;
                        };
//--------------------
void printbook(card & car) //printing of record
{
    static int count = 0;
    cout << "\n" << ++count << ". " << car.author;
    cout << " - " << car.title << ", " << car.firm;
    cout << ", " << car.edition << ", " << car.year;
}
//--------------------                        
struct record {
                                card book;
                                record *prior;
                                record *next;
                            };                        
//--------------------
card books[] = {
    {"Wiener", "Turbo C++", "Mir", 3, 1991},
    {"Stroustrup", "C++", "DiaSoft", 2, 1991},
    {"Turbo C++", "Programming", "INTKV", 1, 1993},
    {"Lippman", "C++ for beginners", "GELION", 1, 1994}
};
//--------------------
int main(void)
{
    record *begin = NULL,    //begin list pointer
                 *current = NULL,    //current record pointer
                 *list; // record pointer
    
    int n = sizeof(books)/sizeof(books[0]);
    for (int i = 0; i < n; i++)
        {    //
            current = new(record);
            //
            (*current).book.author = books[i].author;
            (*current).book.title = books[i].title;
            current->book.firm = books[i].firm;
            current->book.edition =  books[i].edition;
            current->book.year = books[i].year;
            
            if (begin == NULL)
                {
                    current->prior = NULL;
                    current->next = NULL;
                    begin = current;
                    list = begin;
                }
            else
                {
                    current->next = NULL;
                    current->prior = list;
                    list->next = current;
                    list = list->next;
                    
                }
      }

    list = begin;
    while (list)
        {
            printbook(list->book);
            list = list->next;
        }
            
    
  cin.get();
  return 0;
}

lesha_od

Дата 3.12.2006, 23:17 (ссылка)

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

Загрузка ...

Новичок

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

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

Спасибо за ответ.
Двунаправленный - это линейный двухсвязный или другой?

Anikmar

Дата 3.12.2006, 23:24 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

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

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

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

lesha_od

Дата 4.12.2006, 11:51 (ссылка)

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

Загрузка ...

Новичок

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

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

Я такое и сделал вначале. А мне сказали, что надо по-другому.
Может, кто-нибудь знает наверняка?

p.s. В поиске нашел многое, но не то...

Anikmar

Дата 4.12.2006, 12:09 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

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

Цитата(lesha_od @ 4.12.2006, 11:51)

Я такое и сделал вначале. А мне сказали, что надо по-другому.

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

Mayk

Дата 4.12.2006, 12:11 (ссылка)

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

Загрузка ...

^аВаТаР^ сообщение>>

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

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

Цитата(Anikmar @ 4.12.2006, 16:09

)

Многие преподаватели несколько по-разному подходят к таким вопросам.

Ну не имели же они в виду двунаправленную очередь.

Их можно отправить читать Кормена и др.

Цитата(Cormen et al)

Как показано на рис 10 3 каждый элемент дважды связанного списка(doubly linked list) L - это объект с одним полем key и двумя полями-указателями: next(следующий) и prev(предыдущий)

И двухсвязный список сложно понять как-то по иному smile

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

Anikmar

Дата 4.12.2006, 12:22 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

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

Цитата(Mayk @ 4.12.2006, 12:11)

И двухсвязный список сложно понять как-то по иному smile

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

Недавно лично видел, как бедолага студент делал свою минисубд в курсовике по теме "Динамическое распределение памяти".

Ну на фига в такой теме заставлять свою СУБД писать?! Человек больше провозился с файловыми операциями чем с заданием по теме...

lesha_od

Дата 4.12.2006, 15:17 (ссылка)

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

Загрузка ...

Новичок

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

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

Ок, чем отличается линейный двухсвязный от простого двухсвязного?
И в задании говорится:

- добавление элемента в неупорядоченный список,
.....
- добавление и удаление заданного элемента из упорядоченного списка с поиском «слева» и «справа»,

То есть возможно указатели next и prev указывают не так что 1 <-> 2 <-> 3 а по-другому?
1 -> 2 -> 3 -> 4
2 <- 4 <- 1 <- 3

Anikmar

Дата 4.12.2006, 15:53 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

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

Кто-то писал так:

Цитата

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

Отсюда вывод: двусвязный список является частным случаем линейного...
Ромб, он же параллелограмм...

Хотя быть может я и не прав smile

lesha_od

Дата 4.12.2006, 15:56 (ссылка)

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

Загрузка ...

Новичок

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

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

Спасибо, понял. То есть код который я написал в 1 сообщении этой темы, правильно описывает нужный тип списка?

Anikmar

Дата 4.12.2006, 15:58 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

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

Описывает да, на счет реализации - не смотрел, если честно.

Arks

Дата 4.12.2006, 16:21 (ссылка)

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

Загрузка ...

Бывалый

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

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

Lesh_od
Неплохо бы проверять длину строки sn в конструкторе прежде, чем копировать иначе можешь память попортить.
Вместо strcpy(surname,"") не проще ли написать surname[0] = '\0' ?
В AddToHead нужно ещё: newvalue->prev=NULL сделать.
Также у тебя там описан неупорядоченный список, т.к. всегда добавляется к голове. В упорядоченном списке тебе следует проходить список вперёд или назад и искать ту позицию в которую нужно добавить элемент.
Кроме того, у тебя не написан деструктор к классу List!
И ещё удаления отдельного элемента из класса List у тебя нет smile

Добавлено @ 16:25
Подписался

Это сообщение отредактировал(а) Arks - 4.12.2006, 16:58

lesha_od

Дата 6.12.2006, 00:44 (ссылка)

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

Загрузка ...

Новичок

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

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

Arks, Спасибо. Да, я знаю, что над программой надо работать и работать. Сейчас займусь этим, и напишу о результатах.

lesha_od

Дата 6.12.2006, 01:35 (ссылка)

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

Загрузка ...

Новичок

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

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

Взял за основу программу человека из другого варианта, и изменил под свой вариант. Все вроде бы ничего, учитывая, что в C++ я ничего не понимаю в указателях. Но почему-то при выполнении выдается ошибка.

Код


#include <iostream>
#include <conio.h>
#include <windows.h>
using namespace std;

struct Elem 
{
    char surname[30];
    int year;
    double avg;
    Elem * next;
    Elem * prev;
    Elem(char * sn,int y, double a)
    {
        strcpy(surname,sn);
        year = y;
        avg = a;
        next=NULL;
        prev=NULL;
    }
    Elem()
    {
        year = 0;
        avg=0;
        strcpy(surname,"");
        next=NULL;
        prev=NULL;
    }
};

class List
{
    Elem *head;
    Elem *tail;
public:
    List():head(NULL),tail(NULL){}
    /*virtual ~List()
    {
        ClearAll();
    }*/
    void Print()const;
    void AddToHead(const Elem &value);
    int DelSurname(const char *name);
    int HowMany();
    void DelNum(const int & position);
    void DeleteFromHead();
    void DeleteFromTail();
};



void List::Print()const
{
    Elem * ptr = head;
    if (head==NULL)
        cout<<endl<<" List is Empty"<<endl;
    cout<<endl;
    while(ptr)
    {
        cout<<ptr->surname<<endl;
        cout<<ptr->year<<endl;
        cout<<ptr->avg<<endl;
        ptr = ptr->next;
    }

}

void List::AddToHead(const Elem & value)
{
    Elem * newvalue = new Elem;
    strcpy(newvalue->surname,
        value.surname);
    newvalue->year = value.year;
    newvalue->avg = value.avg;
    if (head == NULL)
    {
        head = tail = newvalue;
    }
    else{
        newvalue->next = head;
        head = newvalue;
        newvalue->next->prev = head;
    }
}

int List::DelSurname(const char *name)
{
    Elem * ptr=head;
    int i=0;
    int count=0;
    while(ptr)
    {
        if (!strcmp(ptr->surname,name))
        {    
            ptr=ptr->next;
            this->DelNum(i);            
            count++;            
        }
        else
        {
            ptr=ptr->next;
            i++;
        }
    } ;
    return count;
}

int List::HowMany()
{
    Elem * ptr = head;
    int counter = 0;
    while (ptr)
    {
        ptr = ptr->next;
        counter++;
    }
    return counter;
}

void List::DeleteFromHead()
{
    if(NULL==head)
    {
        cout<<endl<<"\tList Is Empty !!!!!"<<endl;
        return;
    }
    Elem * ptr = head; 
    head = head->next; 
    if(head)
        head->prev = NULL;  
    delete ptr;
}

void List::DeleteFromTail()
{
    if(NULL==tail)
    {
        cout<<endl<<"\tList  Is Empty !!!!! \t\t\t"<<endl;
        return;
    }
    Elem * ptr = tail; 
    tail = tail->prev; 
    if(tail)
        tail->next = NULL;  
    delete ptr;
}

void List::DelNum(const int & position)
{
    int temp = HowMany();
    if (position>=0 && position<=temp-1)
    {
        if (0==position)
            DeleteFromHead();
        else if (HowMany()-1==position)
            DeleteFromTail();
        else
        {
            int count=0;
            Elem * ptr=head;
            while (position-1!=count)
            {
                ptr=ptr->next;
                count++;
            }
            Elem * temp=ptr->next;
            ptr->next=ptr->next->next;
            ptr->next->next->prev=temp;
            delete temp;
            return;
        }
    }else
    {
        cout<<endl<<"\t Wrong index !!!!! \t\t\t"<<endl;    
        return;
    }
    
}

void main() {
List l1;
Elem e1;
strcpy(e1.surname,"aaa");
e1.year=1997;
e1.avg=15;
l1.AddToHead(e1);
Elem e2;
strcpy(e2.surname,"bbb");
e2.year=1953;
e2.avg=16;
l1.AddToHead(e2);
Elem e3;
strcpy(e3.surname,"ccc");
e3.year=1964;
e3.avg=16;
l1.AddToHead(e3);
Elem e4;
strcpy(e4.surname,"ddd");
e4.year=1955;
e4.avg=16;
l1.AddToHead(e4);
l1.Print();
l1.DelNum(2);
l1.Print();
l1.DelSurname("bbb");
l1.Print();
}

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