Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Работа со списками


Автор: Ripper 16.10.2007, 19:44
Я уже писал тут задачу, когда нужно было центрировать строку. Сейчас делаю тоже самое для списков, и вот проблема:
Код

#include <iostream>
using namespace std;

struct Item {
       char c;
       Item *pNext;
};
                    
Item* CreateList(char*);
void AddItem(Item* p);
void DeleteList(Item*);
void PrintList (Item*);
int DelSpaces(Item* from, Item*& to);
bool Skip(Item*&p);

int main () {
    char in[80],buf[80],ready[80];
    
    while (cout<<"Enter string:"<<endl, cin.getline(in,80)) { 
     Item *head=CreateList(in);
     Item *HeadOfBuf = CreateList(buf);
     DelSpaces(head, HeadOfBuf);
     PrintList(HeadOfBuf);
    }
    return 0;
}


Item* CreateList(char* str) {
      Item *head = NULL, *last;
      
for (;*str;str++) {
    Item* cur = new Item;
    cur->c = *str;
    cur->pNext = NULL;
    if(head)
       last->pNext=cur;
    else
       head=cur;
       last=cur;
    }
return head;
}

void AddItem(Item* p) {
     Item* tmp = new Item;
     
}

void DeleteList(Item *p) {
     while (p) {
           Item *tmp = p;
           p=p->pNext;
           delete tmp;
     }
}

void PrintList(Item* p) {
     for (;p;p=p->pNext) 
      cout << p->c;
      cout << endl;
}

bool Skip(Item*& p) {
    for(; p&&(p->c==' ' || p->c=='\t'); p=p->pNext);
    return p!=NULL;
}

int DelSpaces(Item* from, Item*& to) {
    Item* tmp = to;
    Item* last;     

    while(true) {
        if( !Skip(from))
            break;

     if (to) {
     Item* temp = new Item;
     temp->c = ' ';
     temp->pNext=NULL;
     last->pNext=temp;
     last=temp;
    }
        
        while (from&&from->c!=' '&&from->c!='\t') {
              Item* cur = new Item;         
              cur->c = from->c;
              cur->pNext=NULL;
              if (!to) to=cur;
              else last->pNext = cur;
              last = cur;
              from=from->pNext;      
        }
              
    }
    return 1;
}


Вот этот код запускаю в DevC++ с помощью debug. - работает. Без debug не работает, как и в VC++ не работает. Я уже запарился разрисовывать бумагу с этими указателями smile 
Нужно просто сделать например из "  11  3   4 4    3 " -> "11 3 4 4 3" т.е. удалить пробелы (оставить 1 между символами). Что не так?:(
ф-ии создания списков взял с семинарской тетради, хотя впринципе везде должно работать и ошибка видимо в DelSpaces

Автор: archimed7592 16.10.2007, 22:11
Код

#include <algorithm>
#include <functional>
bool pred(char a, char b)
{
    return a == ' ' && b == ' ';
}
// ...
std::unique(in, in + 80, std::ptr_fun(pred));

Автор: Ripper 17.10.2007, 08:36
Это что) Нам запрещено использовать библиотечные ф-ии да и я таких незнаю.
Я что то совсем не понял смысла этого кода

Автор: Lazin 17.10.2007, 08:39
Проблема в том, что в ф-ии DelSpaces происходит использование указателя last до его инициализации, при первом его использовании там находится мусор:
Код

int DelSpaces(Item* from, Item*& to) {
    Item* tmp = to;
    Item* last; <--указатель непроинициализирован    
    //**********
     last->pNext=temp;<---обращение по непроинициализированному указателю
     last=temp;

Автор: Ripper 17.10.2007, 10:46
Первый раз этот блок не работает, т.к. to указывает на null, а потом он уже инициализируется

Автор: archimed7592 17.10.2007, 10:56
Ripper, тебе обязательно реализовывать удаление через список?

Автор: Ripper 17.10.2007, 11:32
Ага. Там все должно быть через списки... 

Автор: Lazin 17.10.2007, 12:03
Цитата(Ripper @  17.10.2007,  10:46 Найти цитируемый пост)
Первый раз этот блок не работает, т.к. to указывает на null, а потом он уже инициализируется 

ты в этом уверен?
Код

Item *HeadOfBuf = CreateList(buf);//<--buf - непроинициализированный массив.
DelSpaces(head, HeadOfBuf);//HeadOfBuf != NULL

потом ты передаешь ф-ии CreateList указатель на buf - который содержит всякий мусор, нужно этот масив инициализировать.
Код

char buf[80] = "";

вот этот код работать не будет, если массив str не содержит строку оканчивающуюся нулем:
Код

Item* CreateList(char* str) {
      Item *head = NULL, *last;
      
for (;*str;str++) {
    Item* cur = new Item;
    cur->c = *str;
    cur->pNext = NULL;
    if(head)
       last->pNext=cur;
    else
       head=cur;
       last=cur;
    }
return head;
}

вернее будет, но при этом будет вылазить за границу массива

Автор: Ripper 17.10.2007, 12:09
Что-то вообще не понимаю :(
что значит char buf[80]="";? 
Если я пишу char gg[80]; значит gg указатель но первый элемент и 
     Item *HeadOfBuf = CreateList(buf); работает. 
Но не понимаю насчет инициализации. И как сделать так чтобы это все дело заработало?

Автор: akizelokro 17.10.2007, 12:12
Lazin прав. На VC++ вырубается. И дальше ни в какую. Сделай Item * last = new Item;
Первая (не столь критичная) ошибка возникает еще раньше, когда ты пытаешься
Код

Item *HeadOfBuf = CreateList(buf);

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

strcpy(buf, in);

И еще проблема, что ты используешь неоптимальный алгоритм. У тебя есть список. Сделай по нему "пробежку"

Код

Item * p = from;
while(p->Next)
{
  if((p->c ==' ')&&(p->Next->c == ' ')
  {
    Item * prom = p->Next;
     p->Next = prom->Next;
  }
  else
  {
     p = p->Next;
  }
}

Автор: Lazin 17.10.2007, 12:24
Ripper, когда ты пишешь 
Код

char buf[80];

то выделяется 80 байт под массив, в стеке. Изначально в этом массиве может быть все что угодно. И если ты вызовешь к примеру strlen(buf);
может произойти ошибка доступа, из-за того, что buf может вообще не содержать '\0', а может и не произойти.
Можно сделать так
Код

buf[0] = '\0';

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

Автор: akizelokro 17.10.2007, 12:30
Смысл последнего куска, что ты работаешь с одним списком, проверяешь текущий элемент на наличие пробела, если есть, тут же смотришь на наличие пробела у следующего элемента. Если там пробел (два пробела подряд), то следующий элемент удаляешь (что я забыл сделать, ну так поправят), а указатель из удаляемего вытаскиваешь в текущий. И так до конца списка.

Код

#include "stdafx.h"
#include <iostream>
using namespace std;

struct Item {
       char c;
       Item *pNext;
};
                    
Item* CreateList(char*);
void AddItem(Item* p);
void DeleteList(Item*);
void PrintList (Item*);
int DelSpaces(Item* from);

int main () {
    char in[80];
    
    while (cout<<"Enter string:"<<endl, cin.getline(in,80)) { 
     Item *head=CreateList(in);
     DelSpaces(head);
     PrintList(head);
    }
    return 0;
}


Item* CreateList(char* str) {
      Item *head = NULL, *last;
      
for (;*str;str++) {
    Item* cur = new Item;
    cur->c = *str;
    cur->pNext = NULL;
    if(head)
       last->pNext=cur;
    else
       head=cur;
       last=cur;
    }
return head;
}

void AddItem(Item* p) {
     Item* tmp = new Item;
     
}

void DeleteList(Item *p) {
     while (p) {
           Item *tmp = p;
           p=p->pNext;
           delete tmp;
     }
}

void PrintList(Item* p) {
     for (;p;p=p->pNext) 
      cout << p->c;
      cout << endl;
}

int DelSpaces(Item* from) {
Item * p = from;
    Item * prom;
while(p->Next)
{
  if((p->c ==' ')&&(p->Next->c == ' ')
  {
    prom = p->Next;
     p->Next = prom->Next;
    delete prom;
  }
  else
  {
     p = p->Next;
  }
}

    return 1;
} 


Не надо определять формальные аргументы с типом Item* &, это не есть хорошо. Все я исправлять не стал, но, попробуй, должно сработать. 

Автор: Ripper 17.10.2007, 12:30
О..эм... спасибо вроде работает.  
Да, тяжело познание си smile Ну ничего.. щас ещё самую главную ф-ию центрирования попробую сделать а потом выложу готовый вариант  smile

Добавлено через 1 минуту и 23 секунды
Это я к варианту Lazina

akizelokro, твой ещё не смотрел... но вроде тока добавив buf[0]='\0' заработало, но щас и твой посмотрю

Добавлено через 4 минуты и 9 секунд
p.s. stdafx.h незя использовать. а что это?smile

Добавлено через 5 минут и 45 секунд
работает, только 1 строчку убрать надо и там мелкие опечатки. + первый пробел не удаляется. 
Блин, щас мозг взорвется..)

Автор: akizelokro 17.10.2007, 12:43
Угу, буквально воспринял задачу, что надо два и более подряд пробелов сводить к одному smile 
Код

int DelSpaces(Item* from) {
Item * p = from;
//для удаления первого пробела
Item * prom = p;
if(prom->c == ' ')
{
if(prom->Next)
  p = prom->Next;
else
{
  p->Next = NULL;
  delete prom;
}
while(p->Next)
{
  if((p->c ==' ')&&(p->Next->c == ' ')
  {
    prom = p->Next;
     p->Next = prom->Next;
    delete prom;
  }
  else
  {
     p = p->Next;
  }
}
    return 1;
} 

<stdafx.h> - стандартный Виндовый хидер для консоли, удаляй его из своего кода.

Автор: Ripper 17.10.2007, 12:50
просто мне ещё удобней вводить 3 массива т.к. потом нужно будет центрировать полученную строку. Покранемере при работе с массивами строк так было удобно. 1 массив вводит пользователь. 2 массив это когда строка имеет корректный вид. третий массив это строка размером 80 символов где по бокам равное кол-во пробелов а в середине 2 массив smile 
Тем неменее спасибо всем!

Автор: akizelokro 17.10.2007, 13:02
И третий массив тоже не нужен. Подсчитаешь количество элементов с пробелами, которые нужно вставить слева и справа, и просто их добавишь в список.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)