Двухсвязанный список на Си. - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - Двухсвязанный список на Си. (http://forum.oszone.net/showthread.php?t=64973)

Двухсвязанный список на Си.

1. Постановка вопроса.
- В данную задачу необходимо реализовать средствами языка Си.
- Необходимо организовать двухсвязанный список, т.е. создать его и загрузить в оперативную память, а затем производить
различные манипуляции с элементами этого списка (всё сводится к поиску и сортировке).
- Полностью код выкладывать не буду (считаю будет только загромождать), покажу только, то с чем проблема.

Код:

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

#define TRUE 1

#define FALSE 0

struct expt{int expert;

//char fam[20];

//int mesto;

};

struct record{expt sps; record *prior, *next;};

void main (){

record          *begin=NULL, /*Указатель начала списка*/

                *last=NULL,  /*Указатель на очередную запись*/

                  *list;       /*Указатель на элементы списка*/

char c;

while(1){clrscr();

printf(" 2 - Input data \n3 - View\n  Selection item: ");

scanf("%s",&c);

switch(c){

        

   case '2':{

                      int b=TRUE;

                           while(b!=FALSE){  //цикл ввода данных

                           last=(struct record*)malloc(sizeof(struct record));

                   if(last==NULL){printf("\n Error !\n No find memory\n Press any key...");getch();return;}  /*проверка, выделена ли память?*/

                                clrscr();

                                printf("\n Input namber expert (0-9): ");

                           scanf("%d",&(*last).sps.expert);

            if(begin==NULL){last->prior=NULL;begin=last;last->next=NULL;} //списка ещё нет

            else{list=begin; //cписок уже существует

                  while(list){ /*цикл просмотра списка-поиск места для новой записи*/

                                                  if(list->next==NULL){ /*Включить запись в конец списка*/

                              last->next=NULL;

                              last->prior=list;

                              list->next=last;

                              break;       /*выход из списка просмотра цикла*/

                                                            }

                      list=list->next;

                    } //конец цикла просмотра while

                          } //конец else список уже существует

                           printf("\n Next input? 1 - Yes\\0 - No\n");  //ввод нового эксперта

            scanf("%d",&b);

  

   getch();

                     } //конец цикла ввода данных while(b!=FALSE)

break;}

   case '3':{

            clrscr();

                           printf("\n Out spicok:\n");

            list=begin;

            while(list){

            printf("(list->sps.expert)=%d\n",list->sps.expert);

            list=list->next;

            }

            getch();

            break;}

      default:{printf("\n Error !\n Can't no right selection item\n Press any key...");getch();break;}

}





}

}

- Для двухсвязанного списка используется структуры типа record, который включает в себя две ссылки на структуру
(record *prior, *next;), и структуру (sps) типа expt. Создаем и загружаем в оперативную память список в операторе
switch{case '2':.........}. Здесь, я думаю, что сделал всё верно. Прикреплю блок-схему http://forum.oszone.net/attachment.p...tid=1976&stc=1.

2. Вопрос.
- В операторе switch{case '3':.........} хочу вывести все элементы списка на экран, но не выходит аленький цветочек. Всё компилируется, ошибок никаких не выдается, только одно предупреждение (" 'last' is assigned a value that is never used"),запускаем *.exe файл, ввожу в список записи, затем пытаюсь просмотреть, выползает окошко с ошибкой ("Thread stopped
D:\BC5\bin\cs.c Fault:
access violation at .....
read of address ........"), и всё на этом, программа останавливается.
Убираю цикл while по крайней мере выводит правильно первый элемент.
В чём моя ошибка? Где собака зарыта?

Hemp
а почему не использовать STL-левский шаблон для списков?

Vlad Drakula
Потому, что сессия не за горами, потому, что требуют на языке Си использовать списки, С++ нельзя использовать, шаблоны здесь не пойдут.
Задачу решил следующим образом, функция views() правильно отображает данные из списка.

Код:

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

#define TRUE 1

#define FALSE 0

#define FILE_DB "db1.dat"

struct expt{int expert;char sport[20];int mesto;};

struct record{expt sps; record *prior;record *next;};

void clr (char a[]);

void printmenu(void);

void views(void);

void save(char a[],record *begin);

void load(char a[],record *begin);

void clr (char a[]){

FILE *f;

if((f=fopen(a,"w"))==NULL)printf("\n Error !\nFile could not be create\\opened.\n Press any key...");

else printf(" \n Data base clear successfully!\n Press any key...");

getch();

fclose(f);

}

void printmenu(){

clrscr();

printf("|----------------------------------|\n| Menu:\t\t\t\t   |\n|------------\

----------------------|\n| 1 - Clear file data base \t   |\n| 2 - Input data\t\t   |\n| 3 - View db data\t\t\t   |\n| 4 - Form file \

expert questioning |\n| 5 - Form file best sportsmans    |\n| 0 - Exit\t\t\t   |\n|-------\

---------------------------|\n\n  Selection item: ");

}

void views(record *begin){

                                 clrscr();

                           printf("\n Out spicok bd:\n");

            while(begin){

            printf("(expert%d---%s---mesto-%d\n",begin->sps.expert,begin->sps.sport,begin->sps.mesto);

            begin=begin->next;

            }

            getch();

}

void save(char a[],record *begin){

FILE *f;

if((f=fopen(a,"w"))==NULL){printf("File could not be opened\n Press any key...");

getch();return;}else{

        while(begin!=NULL){

   fprintf(f,"%d",begin->sps.expert);

   fprintf(f,"%s",begin->sps.sport);

   fprintf(f,"%d",begin->sps.mesto);

   begin=begin->next;

   }

   }

fclose(f);

}

void main (){

record          *begin=NULL, /*Указатель начала списка*/

                        *last=NULL,  /*Указатель на очередную запись*/

         *list;       /*Указатель на элементы списка*/

char c;

FILE *f;

if((f=fopen("db1.dat","a+"))==NULL){printf("File could not be opened\n Press any key...");

        getch();return;}else{

   while(fgetc(f)!=EOF){

   last=(struct record*)malloc(sizeof(struct record));

   if(last==NULL){printf("\n Error !\n No find memory\n Press any key...");getch();return;}

   fscanf(f,"%d",&last->sps.expert);

   fscanf(f,"%s",&last->sps.sport);

   fscanf(f,"%d",&last->sps.mesto);

   if(begin==NULL){last->prior=NULL;begin=last;last->next=NULL;}

   else{list=begin;

while(list){

                                       if(list->next==NULL){

                                 last->next=NULL;

                                      last->prior=list;

                                      list->next=last;

                                      break;

                                 }

                                list=list->next;

               }

               }

   }

   }

fclose(f);

while(1){printmenu();

scanf("%s",&c);

switch(c){

        case '1':{clr("db1.dat");break;}

   case '2':{

                      int b=TRUE,extemp,count,c;

            while(b!=FALSE){  //цикл ввода данных

            clrscr();

                                printf("\n Input namber expert (1-10): ");

                           scanf("%d",&extemp);

            for(count=3;count>0;count--){

            last=(struct record*)malloc(sizeof(struct record));

                   if(last==NULL){printf("\n Error !\n No find memory\n Press any key...");getch();return;}  /*проверка, выделена ли память?*/

            (*last).sps.expert=extemp;

            (*last).sps.mesto=count;

            printf("\n Input family srortsmen: ");

                           scanf("%s",&(*last).sps.sport);

                           if(begin==NULL){last->prior=NULL;begin=last;last->next=NULL;} //списка ещё нет

            else{list=begin; /*cписок уже существует*/

                  while(list){ /*цикл просмотра списка-поиск места для новой записи*/

                          if(list->next==NULL){ /*Включить запись в конец списка*/

                              last->next=NULL;

                              last->prior=list;

                              list->next=last;

                              break;       /*выход из списка просмотра цикла*/

                                                            }

                      list=list->next;

                  } 

                  }

                          } 

                                       printf("\n Next input? 1 - Yes \\ 0 - No\n");  //ввод нового эксперта

                                            scanf("%d",&b);

                       } 

           printf("\n Data save? 1 - Yes \\ 0 - No\n");  /*записать данные в db.dat?*/

            scanf("%d",&c);

            if(c==TRUE)save(FILE_DB,begin);

            else ;

            break;}

   case '3':{views(begin);break;}

   case '4':break;

   case '0':return;

   default:{printf("\n Error !\n Can't no right selection item\n Press any key...");getch();break;}

}

}

}

Теперь возник новый вопрос. Данные записываются с помощью функции save(), в файл db1.dat.
При запуске программы, данные из файла db1.dat (конечно, если, они на этот момент существуют), должны
должны загружаться в оперативную память. Вот участок кода:

Код:

FILE *f;

if((f=fopen("db1.dat","a+"))==NULL){printf("File could not be opened\n Press any key...");

        getch();return;}else{

   while(fgetc(f)!=EOF){

   last=(struct record*)malloc(sizeof(struct record));

   if(last==NULL){printf("\n Error !\n No find memory\n Press any key...");getch();return;}

   fscanf(f,"%d",&last->sps.expert);

   fscanf(f,"%s",&last->sps.sport);

   fscanf(f,"%d",&last->sps.mesto);

   if(begin==NULL){last->prior=NULL;begin=last;last->next=NULL;}

   else{list=begin;

while(list){

                                       if(list->next==NULL){

                                 last->next=NULL;

                                      last->prior=list;

                                      list->next=last;

                                      break;

                                 }

                                list=list->next;

               }

               }

   }

   }

fclose(f);

Но просматривая функцией views(), вижу, что данные отображаются неверно. Значит, я их неверно извлекаю из файла.
В чём заключается ошибка? Как это реализовать?

-> fscanf(f,"%s",&last->sps.sport);
По-моему, нужно очень осторожно работать с fscanf. Вот данный конкретный - он считает что? Всё до символа конца строки? Слово до пробела? До некоего разделителя? Или вообще всё до конца файла?

hasherfrog
Всё верно. разделители нужны....
Считать данные из файла в двухсвязанный список получилось.
Функция views() отображает на экран данные из памяти.
Функция save() -- записывает в фаил из списка. Перед каждым элементом структуры record, переходим на новую сторку
(т.е.разграничиваем --- fprintf(f,"\n%1d",list->sps.expert);).
функия load() -- считывает из файла в список.
Вот код:

Код:

......



struct expt{int expert;char sport[20];int mesto;};

struct record{expt sps; record *prior;record *next;}*begin,*last,*list;



.......



void views(){

                                 clrscr();

                           printf("\n Out spicok bd:\n");

            list=begin;

            while(list){

            printf("expert %d: %s -- mesto %d\n",list->sps.expert,list->sps.sport,list->sps.mesto);

            list=list->next;

            }

            getch();

}

void save(char a[]){

FILE *f;

if((f=fopen(a,"w"))==NULL){printf("File could not be opened\n Press any key...");

getch();return;}else{

   list=begin;

   while(list!=NULL){

   fprintf(f,"\n%1d",list->sps.expert);

   fprintf(f,"%20s\n",list->sps.sport);

   fprintf(f,"%1d",list->sps.mesto);

   list=list->next;

   }

   }

fclose(f);

}

void load(char a[])

{

FILE *f;

if((f=fopen(a,"r+"))==NULL){printf("File could not be opened\n Press any key...");

getch();return;}else{

while(1){if((fgetc(f))==EOF)break;

                        else{

        last=(struct record*)malloc(sizeof(struct record));

   if(last==NULL){printf("\n Error !\n No find memory\n Press any key...");getch();return;}

   fscanf(f,"%1d",&last->sps.expert);

   fscanf(f,"%20s",last->sps.sport);

   fscanf(f,"%1d",&last->sps.mesto);

   if(begin==NULL){last->prior=NULL;begin=last;last->next=NULL;}

   else{list=begin;

                                            while(list){

                                       if(list->next==NULL){

                                 last->next=NULL;

                                      last->prior=list;

                                      list->next=last;

                                      break;

                                 }

                                 list=list->next;

                   }

   }

         }



}

}

fclose(f);

}

main()

{



......



}

Ещё вопрос, теперь по сортировке.
Необходимо отсортировать двухсвязанный список в порядке возрастания по элементу sps->expert с помощью функции form1().
Допустим есть изначально следующий список (функция views()):

| expert | family | ochki |
|--------------------------------|
| 7 | krotov | 3 |
| 7 | popov | 2 |
| 7 | sidopov | 1 |
| 2 | semenov | 3 |
| 2 | sidopov | 2 |
| 2 | ivanov | 1 |
| 4 | sidorov | 3 |
| 4 | chein | 2 |
| 4 | petrov | 1 |
|--------------------------------|
Необходимо получить вот такой следующий:

expert | family | ochki |
|--------------------------------|
| 2 | semenov | 3 |
| 2 | sidopov | 2 |
| 2 | ivanov | 1 |
| 4 | sidorov | 3 |
| 4 | chein | 2 |
| 4 | petrov | 1 |
| 7 | krotov | 3 |
| 7 | popov | 2 |
| 7 | sidopov | 1 |
|--------------------------------|
Получается такой:
expert | family | ochki |
|--------------------------------|
| 7 | krotov | 3 |
| 7 | popov | 2 |
| 7 | sidopov | 1 |
|--------------------------------|
В чём моя ошибка? Помогите разобраться.

Код:

#define TRUE 1

#define FALSE 0



......



struct expt{int expert;char sport[20];int mesto;};

struct record{expt sps; record *prior;record *next;}*begin,*last,*list;

.......



void form1()

{

int is_sort=FALSE;  

if(begin==NULL){clrscr();printf("Spisok not avialible.\n Press any key... ");getch();return;} //если списка не существует, выходим

if(begin->next==NULL){clrscr();printf("One element of spisok.\n Press any key... ");getch();return;}//если один элемент списка, 

                                                                                                                                                            //зачем ,сортировать?

while(!is_sort){   //выход из цикла --  is_sort==TRUE. "Пробегаем" в цакле по списку, пока не отсортируем

is_sort=TRUE;      // предпологаем, что список уже отсортирован

for(last=begin;last->next!=NULL;){ //цикл существует, пока есть за указателем last есть следующий элемент

   list=last;

   last=last->next;

   if(list->sps.expert>last->sps.expert){ //если предыдущий элемент списка больше последующего

                                                              // то меняем указатели местами

   list->next=last->next;

   if(last->next==NULL);

   else last->next->prior=list;

   if(list->prior==NULL);

   else list->prior->next=last;

   last->prior=list->prior;

   last->next=list;

   list->prior=last;

   is_sort=FALSE;   // чтобы ещё раз просмотреть список и отсортировать, если, он не отсортирован

        }

}

}

}

.......



void main(){

begin=NULL;

last=NULL;

char c;

load(FILE_DB);

while(1){printmenu();

scanf("%s",&c);

switch(c){

   case '1':{clr("db1.dat");break;}

   case '2':{edit();break;}

   case '3':{views();break;}   //просматриваем содержимое списка в памяти

   case '4':{form1();break;}   //сортируем содержимое списка по элементу expert  структуры expt 

   case '0':return;

   default:{printf("\n Error !\n Can't no right selection item\n Press any key...");getch();break;}

}

}

}

Ух, какой кошмарный swap двух елементов :-E
Затираете где-то указатель, имхо, сразу тут: last->next->prior=list;
Кто такой last->next->prior? Это ведь last? Получаем last = list;
Брррррррррррр... Мозги скрутились... Last, List...
Может last->next.prior?

hasherfrog
если делаем вот так:

Код:

//is_sort=FALSE; // чтобы ещё раз просмотреть список.....

то можно проследить, что происходит после кождой итерации цикла while(!is_sort).
Перед последней итерацией данного цикла список выглядит так:
|--------------------------------|
| expert | family | ochki |
|--------------------------------|
| 7 | krotov | 3 |
| 2 | semenov | 3 |
| 2 | sidopov | 2 |
| 2 | ivanov | 1 |
| 4 | sidorov | 3 |
| 4 | chein | 2 |
| 4 | petrov | 1 |
| 7 | popov | 2 |
| 7 | sidopov | 1 |
|--------------------------------|
т.е. два наибольших элемента переместились в конец списка (значит до этого момента всё работает верно), а при перемещении третьего наибольшего элемента получается вся ерунда. Т.е. иными словами, когда один из замещаемых элементов является началом списка.

Цитата:

Затираете где-то указатель

Вот, в выше описанный момент это и делаем (см. рис.), только не понял, как этого избежать, где ошибка.
------------------------------------------------------------------------------------------------------------

Цитата:

Кто такой last->next->prior?

last->next, это указатель на следующий элемент за указателем last.
last->next->prior -- это указатель prior этого следующего за last элемента, т.е.
last->next->prior=list; указатель prior следующего за last элемента, теперь будет указывать на тот же участок памяти, что и list.

Перестановка двух элементов списка получилась.

Код:

for(last=begin;last->next!=NULL;){

        list=last;

        last=last->next;

        if(list->sps.expert>last->sps.expert){

        list->next=last->next;

           if(last->next==NULL);

                   else last->next->prior=list;

           if(list==begin){last->prior=NULL;begin=last;}           // вот в этих

              else{list->prior->next=last;last->prior=list->prior;} // строках были сделаны изменения

           last->next=list;

           list->prior=last;

   is_sort=FALSE;

          }