Односвязный линейный список

@Nadin_ · Регистрация: 12.01.2011

Author24 — интернет-сервис помощи студентам

Текст помощи для не которой программы организован в виде линейного списка
Каждая компонента текста помощи содержит термин (слово) и текст,содержащий пояснение к этому термину.

Написать программу,которая обеспечивает
- начальное формирование текста помощи;
- вывод текста помощи;
- вывод поясняющего текста для заданного термина
Программа должна обеспечить диалог с помощью меню и контроль ошибок при вводе.

у меня есть она...но новый элемент она вставляет в начало списка,а нужно в конец.

C++

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#include <string.h>
#include <iostream.h>
struct list{
    char name[100];
    char text[100];
    struct list *next;
    };
 
typedef struct list BASE;
typedef BASE *pr;
 
 
void spisok_dobavit (pr *ptr);
void spisok_print   (pr*, int kolichestvo);
void spisok_poisk   (pr*);
 
 
int proverka(pr);
 
 
void main(void)
{
 int tmp_key;
 clrscr();
 
 
           int kolichestvo=0;
           pr sptr = NULL;
           int tmp_key2;
           clrscr();
 
 
           do
         {
         clrscr();
         fflush(stdin);
 
         printf("     (1) dobavit.\n");
         printf("     (2) show.\n");
         printf("     (3) poisk.\n");
         printf("     (4) Exit.\n");
 
         switch(getch()){
 
             case '1':
 
                 {
                 clrscr();
 
                 printf("vvedite termin: \n");
                 kolichestvo++;
                 spisok_dobavit(&sptr);
                 }
             break;
 
 
             case '2':
 
                 {
 
 
 
                 clrscr();
 
                 if(proverka(sptr)){
                  printf("Error:Spisok pyst ! \n ");
 
                // printf("„«п Їа®¤®«¦Ґ*Ёп **¦¬ЁвҐ «оЎго Є«*ўЁиг");
                 getch();
                 }
 
                 else
                 spisok_print(&sptr,kolichestvo);
                 }
 
             break;
 
             case '3':
 
                 {
                 clrscr();
 
                 if(proverka(sptr)){
                  printf("Ћ&#152;?ЃЉЂ: ‹Ёбв Їгбв! \n ");
                 getch();
                 }
 
                 else
                 spisok_poisk(&sptr);
                 }
 
             break;
 
             case '4':
 
                 {
 
                 tmp_key2='Y';
                 }
             break;
 
             default :
 
                 {
                  printf("Ћ&#152;?ЃЉЂ: vvedite(1-5)! \n ");
                  getch();
                 }
             }
         }
 
           while(tmp_key2!='Y');
 
 
           }
 
 
void spisok_dobavit(pr *ptr)
{
 pr r;
 r=(BASE*)malloc(sizeof(BASE));
 r->next=NULL;
 
 printf("\n -  : ");
 scanf("%s",r->name);
 
 printf("\n - Termin: ");
 scanf("%s",r->text);
 
 
 
 r->next= *ptr;
 *ptr = r;
 /*pr r;
 cin>>r->name;
 cin>>r->text;
 r->next=new BASE;
 r=r->next;
            */
}
 
 
 
 
void spisok_print(pr *ptr, int kolichestvo)
{
 printf("             baza: \n");
 pr r;
 r=*ptr;
 //r=r->next;
 printf("%-5s%-15s%-13s%\n","No.","Termin","Text");
 
 do
   {
   printf("%-5d%-15s%-13s%\n",kolichestvo,r->name,r->text);
   kolichestvo--;
   r=r->next;
   }
 
 while(r != NULL);
 getch();
 free(r);
}
 
 
void spisok_poisk(pr *ptr)
{
 char name[100];
 int poisk;
 
 pr q,p;
 q=*ptr;
 
 printf("\n - Vvedite termin ");
 scanf("%s",&name);
 
 while(q!=NULL && poisk){
     poisk=strcmp(name,q->name);
     p=q;
     q=q->next;
     }
 
 if(poisk!=0){
     printf("\n Sorry no elem \n");
 
     getch();
     }
 
 else{
     q=p;
     printf("%-5s%-15s%-13s%-12s%-10s\n","No.","termin","Text");
     printf("%-5d%-15s%-13s%-12s%-10d\n",1,q->name,q->text);
     getch();
     }
 poisk=1;
}
 
 
 
 
int proverka(pr topptr)
{
 return topptr == NULL;
}

Помогите переделать.

@Ruu · 16.06.2011, 13:49

Сообщение от Nadin_

у меня есть она...но новый элемент она вставляет в начало списка,а нужно в конец.

Если реализацию односвязного списка дам, тебе этого хватит чтобы дальше самому доделать?
З.Ы. Вчера только занимался изучением и реализацией списков))

@Nadin_ · 16.06.2011, 13:54 **[ТС]**

Ну давай,попытаюсь переделать,хотя что только я не делала уже.

@Aneron · 16.06.2011, 13:59

C++

void spisok_dobavit(pr **ptr)
{
 pr * r,r_2,r_3;
 r=(BASE*)malloc(sizeof(BASE));
 r->next = NULL; 
 printf("\n -  : ");
 scanf("%s",r->name);
 
 printf("\n - Termin: ");
 scanf("%s",r->text); 
r_2 = (*ptr);
while(r_2)
{
r_3 = r_2;
r_2 = r_3 -> next;
}
r_3->next = r;
}

Сообщение от Nadin_

pr r;
*r=(BASE*)malloc(sizeof(BASE));

статической нельзя выделить память.!!!

@Ruu · 16.06.2011, 14:05

C

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    struct node * next;
    int data;
};
struct list {
    struct node * head;
};
 
void push_front(struct list *l, int value){
    struct node * node;
    
    node = (struct node*)malloc(sizeof(*node));
    
    if(l->head != NULL){
        node->next = l->head;
        l->head = node;
    }
    else{
        l->head = node;
    }
    l->head->data = value;
}
void push_back(struct list *l, int value){
    struct node * node;
    struct node * tail;
    
    node = (struct node*)malloc(sizeof(*node));
    
    if(l->head != NULL){
        tail = l->head;
        while(tail->next != NULL)
            tail = tail->next;
        tail->next = node;
        node->next = NULL;
        node->data = value;
    }
    else{
        node->data = value;
        l->head = node;
    }
}
 
void pop_front(struct list *l){
    struct node * node;
    
    if(l->head != NULL){
        node = l->head;
        l->head = node->next;
        free(node);
    }
}
void pop_back(struct list *l){
    struct node * prev;
    struct node * tail;
    
    if(l->head != NULL){
        prev = l->head;
        tail = l->head;
        while(tail->next != NULL){
            prev = tail;
            tail = tail->next;
        }
        if(l->head->next == NULL){
            l->head = NULL;
            free(l->head);
            return;
        }
        prev->next = NULL;
        free(tail);
    }
}
int front(struct list *l){
 
    if(l->head != NULL){
        return l->head->data;
    }
    else{
        return 0;
    }   
}
int back(struct list *l){
    struct node * prev;
    struct node * tail;
    
    if(l->head != NULL){
        tail = l->head;
        while(tail->next != NULL){
            prev = tail;
            tail = tail->next;
        }
        return tail->data;
    }
    else{
        return 0;
    }   
}
 
void insert(struct list *l, int position, int value){
    struct node *cur;
    struct node * newnode;
    struct node * node;
    int i=0;
    
    newnode = (struct node*)malloc(sizeof(*node));
 
    if(l->head != NULL && position > 0){
        cur = l->head;
        node = l->head;
        for(i=0;i<(position-1);++i,cur = cur->next,node = node->next);
        node = node->next;
        newnode->next = node;
        cur->next = newnode;
        
    }
    else{
        newnode->next = l->head;
        l->head = newnode;
    }
    newnode->data = value;
}
void erase(struct list *l, int position){
    struct node *cur;
    struct node * node;
    struct node * prev;
    int i=0;
    
    if(l->head == NULL) return;
    if(l->head != NULL && position > 1){
        cur = l->head;
        prev = l->head;
        for(i=0;i<(position-2);++i,cur = cur->next,prev = prev->next);
        prev = prev->next;
        node = prev->next;
        free(prev);
        cur->next = node;
    }
    else{
        prev = l->head;
        l->head = l->head->next;
        free(prev);
    }
}
void exchange(struct list *l, int first_elem, int second_elem){
    struct node * prev_first = NULL;
    struct node * prev_second =NULL;
    struct node * first = NULL;
    struct node * second = NULL;
    struct node * after_first = NULL;
    struct node * after_second = NULL;
    int i=0;
    
    if(l->head == NULL || l->head->next == NULL) return;
    if(l->head != NULL && first_elem > 0 && second_elem > 0){
        prev_first = l->head;
        for(i=0;i<(first_elem-2);++i,prev_first = prev_first->next);
        first = prev_first->next;
        after_first = first->next;
        
        prev_second = l->head;
        for(i=0;i<(second_elem-2);++i,prev_second = prev_second->next);
        second = prev_second->next;
        after_second = second->next;
        if(first_elem > 1) {
            first->next = after_second;
            prev_first->next = second;      
        }
        else {
            after_first = first;
            first = prev_first;
            first->next = after_second;
            l->head = second;
        }
        if(second_elem-first_elem > 1 || first_elem-second_elem > 1) {
            prev_second->next = first;
            second->next = after_first;
        }
        else
            second->next = first;       
    }
    else{
 
    }
    
}
 
int main() {
    struct list l;
    int i;
    
    for(i=0;i<12;++i)
        push_front(&l, i+1);
    for(i=0;i<12;++i){
        //printf("%d ", back(&l));
        //pop_back(&l);
    }
    printf("\n");
    //insert(&l,3,1);
    //erase(&l,12);
    exchange(&l,1,2);
    for(i=0;i<19;++i){
        printf("%d ", back(&l));
        pop_back(&l);
    }
    return 0;
}

В main() примеры пользования списком) Я его тестировал так)) Не фонтан конечно тесты но помоему и так понятно как юзать функции)

З.Ы. тут реализованы функции:
"положить в начало списка", "положить в конец списка", "достать из начала списка", "достать из конца списка", "Удалить улез из начала списка", "удалить узел из конца списка", "Вставка в любое место списка", "удаление любого элемента списка", "Поменять элементы местами"

@Nadin_ · 16.06.2011, 15:16 **[ТС]**

Выдает ошибку
в 5 строчке

Добавлено через 12 минут

Сообщение от Aneron

статической нельзя выделить память.!!!

а как??

Добавлено через 56 минут

C++

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#include <string.h>
#include <iostream.h>
struct list{
    char name[100];
    char text[100];
    struct list *next;
    };
 
typedef struct list BASE;
typedef BASE *pr;
 
 
void spisok_dobavit (pr *ptr);
void spisok_print   (pr*, int kolichestvo);
void spisok_poisk   (pr*);
 
 
int proverka(pr);
 
 
void main(void)
{
 int tmp_key;
 clrscr();
 
 
           int kolichestvo=0;
           pr sptr = NULL;
           int tmp_key2;
           clrscr();
 
 
           do
         {
         clrscr();
         fflush(stdin);
 
         printf("     (1) dobavit.\n");
         printf("     (2) show.\n");
         printf("     (3) poisk.\n");
         printf("     (4) Exit.\n");
 
         switch(getch()){
 
             case '1':
 
                 {
                 clrscr();
 
                 printf("vvedite termin: \n");
                 kolichestvo++;
                 spisok_dobavit(&sptr);
                 }
             break;
 
 
             case '2':
 
                 {
 
 
 
                 clrscr();
 
                 if(proverka(sptr)){
                  printf("Error:Spisok pyst ! \n ");
 
                // printf("„«п Їа®¤®«¦Ґ*Ёп **¦¬ЁвҐ «оЎго Є«*ўЁиг");
                 getch();
                 }
 
                 else
                 spisok_print(&sptr,kolichestvo);
                 }
 
             break;
 
             case '3':
 
                 {
                 clrscr();
 
                 if(proverka(sptr)){
                  printf("Ћ&#152;?ЃЉЂ: ‹Ёбв Їгбв! \n ");
                 getch();
                 }
 
                 else
                 spisok_poisk(&sptr);
                 }
 
             break;
 
             case '4':
 
                 {
 
                 tmp_key2='Y';
                 }
             break;
 
             default :
 
                 {
                  printf("Ћ&#152;?ЃЉЂ: vvedite(1-5)! \n ");
                  getch();
                 }
             }
         }
 
           while(tmp_key2!='Y');
 
 
           }
 
void spisok_dobavit(pr *ptr)
{
 pr r,r_2,r_3;
 r=(BASE*)malloc(sizeof(BASE));
 r->next = NULL; 
 printf("\n -  : ");
 scanf("%s",r->name);
 
 printf("\n - Termin: ");
 scanf("%s",r->text); 
 
*ptr=r_2;
while(r_2)
{
r_3 = r_2;
r_2 = r_3 -> next;
}
r_3->next = r;
}
 
 
 
 
void spisok_print(pr *ptr, int kolichestvo)
{
 printf("             baza: \n");
 pr r;
 r=*ptr;
 
 printf("%-5s%-15s%-13s\n","No.","Termin","Text");
 
 do
   {
   printf("%-5d%-15s%-13s\n",kolichestvo,r->name,r->text);
   kolichestvo--;
   r=r->next;
   }
 
 while(r != NULL);
 getch();
 free(r);
}
 
 
void spisok_poisk(pr *ptr)
{
 char name[100];
 int poisk;
 
 pr q,p;
 q=*ptr;
 
 printf("\n - Vvedite termin ");
 scanf("%s",&name);
 
 while(q!=NULL && poisk){
     poisk=strcmp(name,q->name);
     p=q;
     q=q->next;
     }
 
 if(poisk!=0){
     printf("\n Sorry no elem \n");
 
     getch();
     }
 
 else{
     q=p;
     printf("%-5s%-15s%-13s%-12s%-10s\n","No.","termin","Text");
     printf("%-5d%-15s%-13s%-12s%-10d\n",1,q->name,q->text);
     getch();
     }
 poisk=1;
}
 
 
 
 
int proverka(pr topptr)
{
 return topptr == NULL;
}

Выводит мусор перед информацией.Что не так?

@Aneron · 16.06.2011, 15:29

Считать данные из файла в динамический массив соответствующего типа
20 пост. изучайте.

@Nadin_ · 16.06.2011, 22:39 **[ТС]**

Люди,ничего не получается

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

Помогите!!!

@lemegeton · 17.06.2011, 21:50

Например вот так.

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct ValueType {
  char *description;
  char *word;
} ValueType;
 
typedef struct Node {
  struct Node *next;
  ValueType value;
} Node;
 
typedef struct List {
  Node *first;
} List;
 
Node* NodeNew(const char *word, const char *description, Node *next) {
  Node *result = (Node*)malloc(sizeof(Node));
  result->next = next;
  result->value.description =
    strcpy((char*)malloc(strlen(description) + 1), description);
  result->value.word =
    strcpy((char*)malloc(strlen(word) + 1), word);
  return result;
}
 
void NodeDelete(Node *node) {
  free(node->value.description);
  free(node->value.word);
  free(node);
}
 
void ListNew(List *list) {
  list->first = NULL;
}
 
int ListIsEmpty(List *list) {
  return (list->first == NULL);
}
 
Node* ListLastNode(List *list) {
  Node* result = list->first;
  while (result != NULL && result->next != NULL)
    result = result->next;
  return result;
}
 
void ListPushBack(List *list, const char *word, const char *description) {
  Node *node = NodeNew(word, description, NULL);
  if (ListIsEmpty(list)) {
    list->first = node;
  } else {
    Node *last_node = ListLastNode(list);
    last_node->next = node;
  }
}
 
int ListSize(List *list) {
  int result = 0;
  Node *node = list->first;
  while (node != NULL) {
    node = node->next;
    ++result;
  }
  return result;
}
 
void ListPrint(List *list) {
  Node *node = list->first;
  while (node != NULL) {
    printf("%s: %s\n", node->value.word, node->value.description);
    node = node->next;
  }
}
 
const char *ListFindByWord(List *list, const char *word) {
  static const char not_found[] = "No help text availiable.";
  Node *node = list->first;
  while (node != NULL) {
    if (strcmp(node->value.word, word) == 0)
      return node->value.description;
    node = node->next;
  }
  return not_found;
}
 
void ListDelete(List *list) {
  while (!ListIsEmpty(list)) {
    Node *next = list->first->next;
    NodeDelete(list->first);
    list->first = next;
  }
}
 
int main(int argc, char *argv[]) {
  // объявление списка
  List list;
  // инициализация списка
  ListNew(&list);
  // добавление элементов
  ListPushBack(&list, "Cow", "Large animal.");
  ListPushBack(&list, "Cat", "Small adorable pet.");
  ListPushBack(&list, "Chair", "A furniture, used for sitting on.");
  // размер списка
  printf("List contains %d element(s):\n", ListSize(&list));
  // вывод списка на экран
  ListPrint(&list);
  // поиск элемента по списку (поиск по слову, возвращает описание)
  printf("Help for 'Cat': %s\n", ListFindByWord(&list, "Cat"));
  printf("Help for 'Wolf': %s\n", ListFindByWord(&list, "Wolf"));
  // удаление списка
  ListDelete(&list);
  return 0;
}

@Ruu 13 / 13 / 1 Регистрация: 20.07.2010 Сообщений: 43
	16.06.2011, 13:49	2
	Сообщение от Nadin_ у меня есть она...но новый элемент она вставляет в начало списка,а нужно в конец. Если реализацию односвязного списка дам, тебе этого хватит чтобы дальше самому доделать? З.Ы. Вчера только занимался изучением и реализацией списков)) 0

@Nadin_ 0 / 0 / 0 Регистрация: 12.01.2011 Сообщений: 13
	16.06.2011, 13:54 [ТС]	3
	Ну давай,попытаюсь переделать,хотя что только я не делала уже. 0

@Aneron 166 / 164 / 27 Регистрация: 20.04.2010 Сообщений: 607
	16.06.2011, 15:29	7
	Считать данные из файла в динамический массив соответствующего типа 20 пост. изучайте. 0

@Nadin_ 0 / 0 / 0 Регистрация: 12.01.2011 Сообщений: 13
	16.06.2011, 22:39 [ТС]	8
	Люди,ничего не получается,видает мусор да и еще пищит,я уже не могу запуталась окончательно. Помогите!!! 0

	17.06.2011, 21:50