VPF::Линейный однонаправленный список без барьерного эл

MemphisMayFire

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

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

Загрузка ...

Новичок

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

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

нужно реализовать линейный однонаправленный список с функциями добавления элемента, опрления размера размера списка, печатью списка, удаления элемента и переворота списка.
добавления ( push ) - передается 2 аргумента: 1) позиция. 2) значение.
удаление( del ) - передается 1 элемент: значение (нужно удалить первое попавшееся).
переворот ( rewind ) - перевернуть список. например, если список был 1 2 3 4, то после поворта он должен быть таким: 4 3 2 1.

вот код:

Код


#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct elem elem;

struct elem {
 int val;
 elem *next;
};

typedef struct {
elem* head;
} list;

int Lsize(list *s) {
elem *cur = s->head;
int i = 0;
if (s->head != 0) {
    i++;
}
else {
    return 0;
}
while (cur->next != 0) {
    cur = cur->next;
    i++;
}
return i;
}

void Lprint(list *s) {
elem *cur = s->head;
int i = 0;
if (s->head == 0) {
    return;
}
while (cur != 0) {
    printf("%d ", cur->val);
    cur = cur->next;
}
printf("\n");
}

int Push(list *s, int b, int c) {
int e = b - 1;
int i = 0;
elem *cur = s->head;
elem *cur1 = s->head;
elem *d = malloc(sizeof(elem));
if (b == 0) {
 s->head = d;
 d->val = c;
 if (s->head == 0) {
  d->next = 0;
 }
 else {
  d->next = cur;
 }
    printf("OK\n");
 return 1;
}
if ((s->head == 0) && (b != 0)) {
 free(d);
 return 0;
}
if (e > Lsize(&(*s))) {
 free(d);
 return 0;
}
while ((cur != 0) && (i < b) && (b != 0)) {
 cur1 = cur;
 cur = cur->next;
 i++;
}
d->next = cur;
cur1->next = d;
d->val = c;
printf("OK\n");
return 1;
}

void Rewind(list *s) { 
elem *cur1 = s->head;
elem *cur2 = s->head;
elem *cur3 = s->head;
if (cur1->next != 0) { 
    cur2 = cur1->next;
}
else {
    free(cur2);
    return;
}
if (cur2->next != 0) {
    cur3 = cur2->next;
}
else {
    cur2->next = cur1;
    s->head = cur2;
    free(cur3);
    return;
}
while (cur2->next != 0) {
    if (cur3->next != 0) {
        cur2->next = cur1;
        cur1 = cur3->next;
    }
    else {
        cur3->next = cur2;
        cur2->next = cur1;
        s->head = cur3;
        return;
    }
    if (cur1->next != 0) {
        cur3->next = cur2;
        cur2 = cur1->next;
    }
    else {
        cur1->next = cur3;
        cur3->next = cur2;
        s->head = cur1;
        return;
    }
    if (cur2->next != 0) {
        cur1->next = cur3;
        cur3 = cur2->next;
    }
    else {
        cur2->next = cur1;
        cur1->next = cur3;
        s->head = cur2;
        return;
    }
}
printf("OK\n");
} 

void init_list(list *s) {
s->head = 0;
}

void Del(list *s, int x) {
elem *cur = s->head;
elem *cur1 = s->head;
while ((cur != 0) || (cur1 != 0)) {
    if (cur1 != s->head) {
    cur = cur1->next;
}
if (cur->val == x) {
    if(cur == s->head){
        s->head = cur->next;
        free(cur);
    }
    cur1->next = cur->next;
    free(cur);
    printf("OK\n");
    break;
}
cur1 = cur->next;
if (cur1->val == x) {
    cur->next = cur1->next;
    free(cur1);
    printf("OK\n");
    break;
}
}
} 

int main() {
list s;
init_list(&s);
int n = 0, g, h;
scanf("%d", &n);
printf("number of elements %d\n", n);
while (n != 0) {
    scanf("%d %d", &g, &h);
    Push(&s, g, h);
    n--;
}
Lprint(&s);
scanf("%d", &g);
Del(&s, g);
Rewind(&s);
Lprint(&s);
}

Заранее спасибо!

Это сообщение отредактировал(а) MemphisMayFire - 4.5.2011, 17:26

borisbn

Дата 4.5.2011, 21:23 (ссылка)

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

Загрузка ...

Эксперт

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

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

А в чём проблема то ? Вопрос задать забыл ?

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

MemphisMayFire

Дата 5.5.2011, 08:49 (ссылка)

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

Загрузка ...

Новичок

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

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

а ну да

функция rewind вообще вроде не работает, а еще в какой-то функции происходит повторное удаление элемента, изза чего программа падает.

borisbn

Дата 5.5.2011, 10:48 (ссылка)

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

Загрузка ...

Эксперт

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

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

После какой строчки падает ? Пройдись пошагово...

И IMHO ты намудрил немного. Например, ф-ция Del могла бы выглядеть пороще:

Код


void Del(list *s, int x) {
  elem *prev = s->head;
  elem *cur = s->head;
  if ( s->head == 0 ) {
    return;
  }
  while ( cur != 0 && cur->val != xx ) {
     prev = cur;
     cur = cur->next;
  }
  if ( cur == s->head ) {
    s->head = cur->next;
    free( cur );
    return;
  }
  if ( cur != 0 ) {
    prev->next = cur->next;
    free( cur );
  }
}

c rewind посложнее будет. щаз подумаю - напишу чего-нить. а ты пока пройдись отладчиком. мож чего и увидишь...

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

borisbn

Дата 5.5.2011, 16:00 (ссылка)

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

Загрузка ...

Эксперт

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

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

лови rewind (к нему потребуется доп.ф-ция get_last)

Код


void get_last( elem * first, elem * the_end, elem ** last, elem ** prev_last )
{
    *last = first;
    while ( (*last)->next != the_end ) {
        *prev_last = *last;
        *last = (*last)->next;
    }
}

void Rewind( list *s )
{
    elem * first = s->head;
    elem * the_end = 0;
    elem * last;
    elem * prev_last;
    
    while ( first != last && first != the_end ) {
        get_last( first, the_end, &last, &prev_last );

        int tmp = first->val;
        first->val = last->val;
        last->val = tmp;
        
        first = first->next;
        the_end = last;
        last = prev_last;
    }
}

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

MemphisMayFire

Дата 5.5.2011, 19:21 (ссылка)

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

Загрузка ...

Новичок

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

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

падала после делита вроде.
спасибо, попробую с Вашими функциями, вроде не должна будет падать.

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