Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Списки

Автор: SectoR 15.10.2005, 14:45

Вот код:

Код


/* List */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

// структура данных
 struct TPers
{ 
 char *Fam,*Nam;
 unsigned int Tel;
};

// структура node
 struct node
{
 struct TPers * data;
 struct node * previous_node;
 struct node * next_node;
};

int add_data ( struct node * current, char * _Fam, char * _Nam, int _Tel );
int del_data ( struct node * current );
int next_node( struct node * current );
int prev_node( struct node * current );

int main()
{
 clrscr();
  struct node * current;
 getch();
}

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

Автор: nikitao 15.10.2005, 20:23

Вот код программы (не под твой исходник) демонстрирующий две основные ф-ции (доб и удаление).Разберись с ним и жизнь станет легче

Код


#include<iostream>
#include<conio>
using namespace std;
struct ochered{
  public:
  int c;
  ochered *head;
  ochered *next;
  ochered *tail;
  ochered(){head=tail=next=NULL;}
  void add(int i) //добовляет новый элемент в конец списка
  {
    ochered *temp;
    temp=new ochered;
    if (!head)
    {
      head=temp;
      tail=head;
      tail->next=NULL;
      tail->c=i;
    }
    else
    {
      tail->next=temp;
      tail=tail->next;
      tail->c=i;
    }
  }
  int delet()//убивает первый элемент и выводит его значение на экран
  {
    int k;
    if (head==NULL)
    {
      cerr<<"Spisok pust";
      return 0;
    }
    ochered *p;
    p=head;
    head=head->next;
    k=p->c;
    delete [] p;
    return k;
  }
  };
int main()
{
  ochered ob;
  ob.add(30);
  ob.add(239);
  ob.add(566);
  cout<<ob.delet()<<endl;
  cout<<ob.delet()<<endl;
  cout<<ob.delet()<<endl;
  getch();
  return 0;
}

Он под С++,но с принципом можно разобраться.В функции add замени new yf malloc а delete на flush(как-то так). smile

Автор: Void 15.10.2005, 20:53

Perchilla
Скорее, Си. В C++ эти бесконечные struct не нужны.

Автор: LPBOY 15.10.2005, 21:36

Цитата(Void @ 15.10.2005, 20:53)

Perchilla
Скорее, Си. В C++ эти бесконечные struct не нужны.

Void, а причем здесь Perchilla? smile

В дополнение к примеру nikitao, вот еще примерчик списка. Надеюсь поможет.

Код


#include <iostream>
#include <cassert>

    template<class T>
    class List
    {
    private:
        struct List_node
        {
            List_node* pnext;
            List_node* pprev;
            T data;

            List_node(const T& val, List_node* n = 0, List_node* p = 0)
                : data(val), pnext(n), pprev(p) 
            {
            }
            ~List_node()
            {
            }
        };

        List_node* head;
        List_node* tail;
    public:
        List():head(0), tail(0) {}

        void push_back(const T&);
        void pop_back();
        
        T& back();

        void push_front(const T&);
        void pop_front();

        T& front();

        void insert(const T& val, unsigned int pos);

        ~List();

        void dump();

    };

    template<class T>
    void List<T>::push_back(const T& val)
    {
        if(head == 0)
        {
            head = tail = new List_node(val);
        }
        else
        {
            assert(head != NULL && tail != NULL);
            List_node* pnode = new List_node(val);
            pnode->pprev = tail;
            tail = tail->pnext = pnode;            
        }
    }

    template<class T>
    void List<T>::pop_back()
    {
        if(head == 0)
        {
            assert(tail == 0);
            throw "Empty List";
        }
        else
        {
            List_node* node = tail->pprev;
            delete tail;
            tail = node;
            if(tail == NULL)
                head = NULL;
            else
            tail->pnext = 0;
        }
    }

    template<class T>
    inline
    T& List<T>::back()
    {
        return tail->data;
    }

    template<class T>
    inline
    T& List<T>::front()
    {
        return head->data;
    }

    template<class T>
    void List<T>::push_front(const T& val)
    {
        if(head == 0)
        {
            head = tail = new List_node(val);
        }
        else
        {
            assert(head != NULL && tail != NULL);
            List_node* pnode = new List_node(val);
            pnode->pnext = head;
            head = head->pprev = pnode;            
        }
    }

    template<class T>
    void List<T>::pop_front()
    {

        if(head == 0)
        {
            assert(tail == 0);
            throw "Empty List";
        }
        else
        {
            List_node* node = head->pnext;
            delete head;
            head = node;
            if(head == 0)
                tail = 0;
            else
            head->pprev = 0;
        }

    }

    template<class T>
    void List<T>::insert(const T& val, unsigned int pos)
    {
        if(pos == 0)
        {
            push_front(val);
            return;
        }
        List_node* node = head;
        while(node->pnext && --pos)
        {
            node = node->pnext;

        }
        if(node->pnext == 0) push_back(val);
        else
        {
            List_node* newnode = new List_node(val, node->pnext, node);
            node->pnext->pprev = newnode;
            node->pnext = newnode;
        }
        
    }

    template<class T>
    List<T>::~List()
    {
        for(List_node* p = head; p ;)
        {
            List_node* t = p;
            p = p->pnext;
            delete t; 
        }
    }

    template<class T>
    void List<T>::dump()
    {
        std::cout << "--------------------" << std::endl;
        for(List_node* p = head; p ;)
        {
            List_node* t = p;
            p = p->pnext;
            std::cout << t->data << std::endl; 
        }
        std::cout << "--------------------" << std::endl;
    }

int main()
{                //тестируем
    try
    {
    List<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    l.push_back(4);
    l.dump();
    l.insert(23, 53);
    l.dump();
    l.pop_back();
    std::cout << "Back = " << l.back() << std::endl;
    l.pop_back();
    l.dump();
    l.pop_back();
    l.pop_back();
    l.pop_back();
    l.pop_back();
    l.dump();
    return 0;
    }
    catch(const char*& what)
{
    std::cout << what << std::endl;
}
    catch(...)
    {
        std::cout << "in catch(...)" << std::endl;
    }
}

Автор: S.A.P. 15.10.2005, 21:41

LPBOY
Void

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

Автор: LPBOY 15.10.2005, 21:56

Интересно, а что бывают учебные заведения, где заставляют писать на чистом С?

Автор: B3cK 15.10.2005, 23:13

Цитата(LPBOY @ 15.10.2005, 21:56)

Интересно, а что бывают учебные заведения, где заставляют писать на чистом С?

Думаю почти во всех, перед тем как учить С++, дают семестр или даже целый курс чистому С.
В моем случае алгоритмизация была на С, а С++ начали с ООП...

Автор: SectoR 16.10.2005, 01:10

Благодарю всех и ухожу в offline, разбираться что к чему smile

Автор: Emantuohtiw 16.10.2005, 10:59

Цитата(Void @ 15.10.2005, 20:53)

Скорее, Си. В C++ эти бесконечные struct не нужны.

Это почему же?

Автор: Void 16.10.2005, 16:41

Цитата(Emantuohtiw @ 16.10.2005, 12:59)

Это почему же?

Потому что C++, в отличие от C, не требует тэга (struct или union) при объявлении указателя на неполный тип.
Вместо

Код

struct node {
    struct node *prev, *next;
    int data;
};

можно писать просто

Код

struct node {
    node *prev, *next;
    int data;
};

Автор: SectoR 18.10.2005, 00:27

Мужики, вот что я напрограммил просмотрев ваши примеры:

Код


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define empty printf("\n")

struct node {
  int tel;
  node *ptr;
  } *current=NULL, *next, *prev;
void add();
void del();
void view();
void select();

void add()
{
  next=new node;

  empty;
  printf("Inp telephone: ");
  scanf("%d", &next->tel);
  next->ptr=NULL;

  if(current==NULL) current=next;
  else prev->ptr=next;
  prev=next;
  next=current;

  char vote;
  printf("Add next: ");
  scanf("%s", &vote);
  if(vote=='y' || vote=='Y')
    add();
  else if(vote=='n' || vote=='N')
    select();
  else
    printf("Invalid value!");
}

void del()
{
}

void view()
{
  if(current==NULL)
  {
    printf("\nThe List is empty.\n");
  }
  else
  {
    printf("\nThe List is:\n");
    while(next!=NULL)
    {
      printf("%d\n",next->tel);
      next=next->ptr;
    }
  }
  select();
}

void select()
{
  printf( "\nEnter a choise:\n"
          "1 to add data in list\n"
          "2 to delete from list\n"
          "3 to view list\n"
          "4 to close programm\n"
          ">> ");
  int choice;
  scanf("%d", &choice);
  switch (choice)
  {
    case 1: add(); break;
    case 2: del(); break;
    case 3: view(); break;
    case 4: exit(1);
    default: printf("Choice is invalid!");
  }
}

void main()
{
 select();
getch();
}

Осталась одна проблемма - удаление узлов! Как сделать - хз, потому как нужно отсоединить указанный узел и освободить память, занимаемую им...

P.S.: Кто нить дайте валидную линку, где можно сдаунлодить книжку Х.М. Дейтела и П.Дж. Дейтела "Как программировать на С++", а то все которые я нашел в инете инвалидные ;-(
P.P.S. Народ, прикиньте: в книге Громова и Татаренко список запихивают в массив и операции над списком выполняют обрабатывая массив. Во хаха... какой смысл тогда смысл в использовании динамических структур данных... Они б еще дерево в массиве хранили!
Хотя на счет последнего я может быть чего-то недопонимаю?!... Поясните пожалуста?
Добавлено @ 00:29
Насчет удаления элементов списка:
В 1-ом сорце nikitao просто убив-ет эл-т очереди.
Во 2-м, пердложенном мне сорце, LPBOY использ-т классы - а это уже другая басня!

В книжке Дейтела и Дейтела (не моей), которую мне немного удалось полистать, как я понял исп-ся буфер *temp (наряду с *current, *next и *prev), в который запис-ся эл-ты расположенные после удаляемого эл-та и после его удаления, этот самый буфер снова приклеив-ся к отсавшейся части!
Может у кого-нибудь есть какие-нибудь комментарии?!...

P.S.: все, пора в offline! Еще вся ночь впереди, может и получится сделать smile

Автор: Dov 18.10.2005, 05:55

Код

#include <stdio.h>   
#include <conio.h>   
#include <stdlib.h> 
#include <string.h>
#include <malloc.h>

#define empty printf("\n")
 
struct phone
{
   char name  [20];
   char number[12];
};

struct node
{
    phone   elem;    
    node*   next;
};

void    menu(); 
void    add(phone* ptr);  
void    del(node** pp);
void    delByVal(char* str, node** pp);  
void    viewPhone(phone ph);
void    viewList(node* ptr); 
void    ins(phone ph, node** ptr); 
void    cleanList(node** ptr);
  
void main()
{
   node* head = NULL;
   phone temp;
   char  ch;
   char  answer;
   char  str[20];

   do
   {
       menu();
       ch = toupper(getch());
       empty;

       switch(ch)
       {
       case '1':
           add(&temp);
           ins(temp, &head);
           break;
       case '2':
           printf("Name to delete: ");
           gets(str);
           delByVal(str, &head);
           break;
       case '3':
           printf("Clean list? ");
           answer = toupper(getch());
           if(answer == 'Y')
               cleanList(&head);
           else
               printf("\nCanceled... ");
           break;
       case '4':
           viewList(head);
           break;
       case '5':
           printf("Have a nice day...\n\n");
           break;
       default:
           puts("No such option!!! ");
       }
   } while(ch != '5');

   cleanList(&head);
}

void menu()
{    
    puts("\nMenu: ");
    puts("======================\n");
    puts("1. to add data in list ");
    puts("2. to delete from list ");
    puts("3. to clean all ");
    puts("4. to view list ");
    puts("5. to close programm ");

    puts("\nEnter your choise: ");
}

void add(phone* ptr)
{
    printf("Name  : ");
    flushall();
    gets(ptr->name);
    printf("Number: ");
    gets(ptr->number);
}  
 
void del(node** pp)
{
    node* tmp = *pp;
    *pp = (*pp)->next;

    delete tmp;
}

void delByVal(char* str, node** pp)
{
    while(*pp && strcmp(str, (*pp)->elem.name))
        pp = &(*pp)->next;

    if(*pp)
        del(pp);
    else
        puts("no such item! ");
}
 
void viewPhone(phone ph)
{
    printf("%-20s %s\n", ph.name, ph.number);
}

void viewList(node* ptr)
{
    while(ptr)
    {
        viewPhone(ptr->elem);
        ptr = ptr->next;
    }
}
   
void ins(phone ph, node** ptr)
{
    node* tmp = new node;
    tmp->elem = ph;
    tmp->next = *ptr;
    *ptr      = tmp;
}

void cleanList(node** ptr)
{
    while(*ptr)
        del(ptr);
}

Всё, я иду спать.

Автор: SectoR 18.10.2005, 21:37

Спасибо за сорец Dov!
Все таки ночью хорошо думается и я разобрался как убивать узлы,
юзая list.h, а также как их сортировать:

Код


#include <list.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

int main ()
{
  int num;
  printf("Inp num of telephones: ");
  scanf("%d", &num);

  int *array;
  array=new int[num*sizeof(int)];

  int tel;
  for(int i=0; i<num; i++)
  {
    printf("Inp telephone: ");
    scanf("%d", &tel);
    array[i]=tel;
  }
  // for(int i=0; i<num; i++) printf("%d\n", array[i]);

  list<int> lst (array, array + num);
  list<int>::iterator i = lst.begin ();

  while (i != lst.end ())
    printf("%d\n", *i++);

  // Menu
  /*menu:*/ while(1) {
  printf("\nEnter a choice:\n"
         "1 to sort list\n"
         "2 to delete data from list\n"
         "3 to close programm and go out\n"
         ">>");
  int choice;
  scanf("%d", &choice);

  switch (choice) {
    case 1:
        lst.sort();
        for (i = lst.begin (); i != lst.end (); i++)
        printf("%d\n", *i); break;
    case 2:
        printf("Inp telephone to remove: ");
        scanf("%d", &tel);

        lst.remove (tel);
        for (i = lst.begin (); i != lst.end (); i++)
        printf("%d\n", *i); break;
    case 3: exit(1);
    default: printf("Choice is invalid!"); }
  } //goto menu;
  getch();
  return 0;
}

Еще раз всем спасибо smile

Добавлено @ 21:40
P.S.: баг с подсветкой кода в 1-ой строчке на верхнем листинге smile