8.2 Линейный двухсвязный список для хранения строк символов

1. Описание типа элемента списка

   typedef struct ListElTag
   {
         struct ListElTag *left; //связь влево
         struct ListElTag *right; //связь вправо
         char *name; //хранимый указатель на строку символов
   } LISTEL;

2. Описание типа списка

   typedef struct ListTag
   {
         LISTEL *head; //указатель на голову
         LISTEL *tail; //указатель на хвост
         int size; //количество элементов
   } LIST;

3. Функция инициализации списка

   void InitList(LIST *list)
   {
         printf("инициализация списка\n");
         list->head=list->tail=NULL;
         list->size=0;
   }

4. Функция добавления новой строки в список

   void AddList(LIST *list,char *name)
   {
         int len=strlen(name);
         //выделение памяти
         LISTEL *listel=(LISTEL*)malloc(sizeof(listel));
         //выделение памяти под новый элемент
         if(listel==NULL) return;
         listel->name=(char*)malloc(len+1);
         //выделение памяти по строку
         if(listel->name==NULL) return;
         strcpy(listel->name,name); //копировать строку
         listel->left=NULL;
         listel->right=NULL;
         printf("добавление элемента\n");
         //организация связи
         if(list->head==NULL) //список пуст
         {
               list->head=list->tail=listel;
         }
         else //добавление элемента в конец списка
         {
               list->tail->left=listel;
               listel->right=list->tail;
               list->tail=listel;
         }
         list->size++;
   }

5. Удаление строки из списка

   void DeleteEl(LIST *list)
   {
         LISTEL *ptr;
         printf("удаление элемента\n");
         if(list->head==NULL) return; //список пуст
         ptr=list->head;
         if(ptr==list->tail) //в списке один элемент
         {
               list->head=list->tail=NULL;
         }
         else //в списке несколько элементов
         {
               list->head=ptr->left;
               list->head->right=NULL;
         }
         list->size--;
         free(ptr);
   }

6. Печать всех строк списка

   void OutList(LIST *list)
   {
         LISTEL *ptr;
         printf("вывод списка\n");
         for(ptr=list->head; ptr!=NULL; ptr=ptr->left)
         printf("%s\n",ptr->name);
   }

7. Функция удаления всех элементов списка

   void DeleteAll(LIST *list)
   {
         LISTEL *ptr, *tmp;
         printf("удаление списка\n");
         for(ptr=list->head; ptr!=NULL;)
         {
               tmp=ptr->left;
               free(ptr->name);
               free(ptr);
               ptr=tmp;
         }
   }

8. Механизм перечисления элементов списка

   Просмотр списка можно сделать универсальным. Для этого в функцию перечисления списка можно передать указатель на функцию обработки данных. Как правило, такие функции имеют название ForEach и имеют такой параметр, как указатель на функцию - обработчик. В качестве простейшего примера можно рассмотреть организацию печати элементов списка. Для этого записывается функция вывода строки (Out).

   void Out(char *str)
   {
         printf("++++%s ++++\n",str);
   }
   void ForEach(LISTEL *beg, LISTEL *end, void (*func)(char*))
   {
         LISTEL *ptr;
         for(ptr=beg; ptr!=end; ptr=ptr->left)
               func(ptr->name);
   }

   Тогда, передавая два указателя beg и end и функцию Out, можно отпечатать фрагмент списка. Например,

   List Names;
   . . . //инициализация и добавление
   ForEach(Names->head,NULL,Out);//печать содержимого списка

   В некоторых случаях полезна функция, которая принимает указатель на функцию с двумя параметрами, первый параметр - содержит указатель на данные, которые будут переданы из элемента списка. Другой параметр необходим для накопления некоторой информации. Например, необходимо подсчитать число строк, размер которых превышает size. Ниже записан пример.

   typedef struct //описание типа второго параметра
   {
         int size; //задает длину сравнения
         int count; //число строк , превышающих size
   } Param;

   Функция подсчета

   void CoutString(char *str, void *param)
   {
         Param *p=(Param *)param; //преобразование void* в тип Param
         if (strlen(str)>=p->size)
               p->count++;
   }

   Функция перечисления

   void ForEachParam(LISTEL *beg, LISTEL *end, void(*func)(char *, void*param), void*param)
   {
         LISTEL *ptr;
         for(ptr=beg; ptr!=end; ptr=ptr->left)
               func(ptr->name,param);
   }

   Пример использования

   List Enimals;
   Param NameGre5; //структура для подсчета
   NameGre5->size=5; //установка значения границы
   NameGre5->count=0; //обнуление счетчика
   . . . //инициализация и добавление в список
   ForEach(Enimals ->head,NULL,CountString, (void*)&NameGre5);
   //подсчет количества строк >= 5.
   printf(“%d”, NameGre5->count);
   . . . .

9. Поиск в списке

   Поиск в списке можно сделать на основе механизма ForEach. Однако этот механизм неэффективен из-за того, что нельзя прервать просмотр, если найден элемент. Ниже предлагается функция нахождения заданной строки. Если строка найдена, то возвращается адрес элемента списка, содержащего эту строку. В противном случае возвращается значение NULL.

   LISTEL* FindName(LIST *list, char *name)
   {
         LISTEL *ptr;
         printf("поиск имени\n");
         for(ptr=list->head; ptr!=NULL; ptr=ptr->left)
               if (strcmp(name,ptr->name)==0)
                     return ptr;
         return NULL;
   }

10. Удаление элемента списка, содержащего искомую строку.

    int DeleteName(LIST *list, char *name)
    {
          LISTEL *ptr;
          printf("удаление имени %s\n",name);
          if((ptr=FindName(list,name))==NULL) //указанное имя не найдено
                return 0;
          if(ptr==list->head&& ptr==list->tail) //удаление единственного элемента
          {
                list->head=list->tail=NULL;
          }
          else
                if(ptr==list->tail) //удаление хвоста
                {
                      list->tail=list->tail->right;
                      list->tail->left=NULL;
                }
                else
                      if(ptr==list->head)//удаление головы
                      {
                            list->head=list->head->left;
                            list->head->right=NULL;
                      }
                      else //удаление из середины
                      {
                            ptr->left->right=ptr->right;
                            ptr->right->left=ptr->left;
                      }
          free(ptr);
    }

11. Функция сортировки элементов списка в лексикографическом порядке

    void SortName(LIST *list)
    {
          int key=1; //ключ сортировки
          char *tmp;
          LISTEL *ptr;
          printf("сортировка\n");
          while(key) //сортируем , пока есть хотя бы одна перестановка
          {
                key=0; //сбрасывает ключ сортировки
                for(ptr=list->head; ptr!=list->tail; ptr=ptr->left)
                {
                      if(strcmp(ptr->name,ptr->left->name)<0)
                      //сравниваем строки двух соседних элементов
                      {
                            tmp=ptr->name; //переставляем местами указатели на строки
                            ptr->name=ptr->left->name;
                            ptr->left->name=tmp;
                            key=1; //перестановка есть, сортировка не окончена!
                      }
                }//конец for
          } //конец while
    } //конец SortName

12. Функция построения списка слов из строки символов

    void MakeListWord(char *exp,LIST *list)
    {
          char *begword, *word;
          int len;
          int i;
          while(1)
          {
                while(*exp==’ ’) exp++; //пропустить пробелы
                begword=exp;//устанавливаем указатель на начало слова
                len=0;
                while(*exp) //определение длины слова
                {
                      if(*exp!=’ ’) //пока не пробел, смещаем указатели
                      {
                            len++;
                            exp++;
                      }
                      else break; //выход, если конец строки или пробел
                } //конец while
                if(len==0) return; //завершение формирования списка
                //выделение слова
                word=(char*)malloc(len+1);
                for(i=0; i<len; i++) word[i]=begword[i];
                word[len]=’\0’;
                //запись слова в список
                AddList(list,word);
                free(word);
          }
    }

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

    void main()
    {
          LIST list;
          InitList(&list); //проинициализировать список
          AddList(&list,"Mike"); //добавить несколько строк
          AddList(&list,"Peter");
          AddList(&list,"John");
          AddList(&list,"Kate");
          OutList(&list); //вывести список
          SortName(&list); //отсортировать список
          OutList(&list);//вывести список
          DeleteName(&list,"Mike"); //удалить несколько строк
          DeleteName(&list,"Peter");
          OutList(&list); //вывести список
          ForEach(list.head,list.head->left,Out); //вывод списка, используя механизм ForEach
          DeleteAll(&list); //удалить список строк
          InitList(&list); //проинициализировать список
          MakeListWord("Привет Всем Вам !!!",&list); //создать список слов из строки
          OutList(&list); //вывести список
          DeleteAll(&list); //удалить список строк
          getch(); //ожидать ввода символа
    }