Реализовать линейный список на основе односвязного линейного списка, определяемого своим началом - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Есть модуль, реализующий линейный список на основе односвязного линейного списка, определяемого своим началом. Завершить его реализацию.
Листинг программы 
  1. /* owlist.h
  2.   АТД  LinList,
  3.   реализованный через односвязный (однонаправленный) список
  4.   (One-Way List)
  5. */
  6. #ifndef OWLIST_H
  7. #define OWLIST_H
  8.  
  9. #if !defined(CORELIST_H)
  10. #include "corelist.h"                 /* определяет TypeItem      */
  11. #endif
  12.  
  13.   struct TypeNode {TypeItem item;
  14.            struct TypeNode *next;};
  15.  
  16.   typedef struct TypeNode **LinList;  /* линейный список          */
  17.   typedef struct TypeNode *Node;      /* узел списка              */
  18.  
  19.   LinList initlist(void);             /* Инициализация списка     */
  20.  
  21.   Node makenode   (TypeItem item );   /* Создание узла            */
  22.  
  23.   void addtofront (LinList list,      /* Добавление узла в начало */
  24.            Node newnode);     /*                   списка */
  25.   void addtorear  (LinList list,      /* Добавление узла в конец  */
  26.            Node newNode);     /*                   списка */
  27.   void insafter   (LinList list,      /* Вставка узла в список    */
  28.            Node newnode,      /*             за указанным */
  29.            Node p);
  30.   void insbefore  (LinList list,      /* Вставка узла в список    */
  31.            Node newnode,      /*          перед указанным */
  32.            Node s);
  33.  
  34.   Node deletenode (LinList list,      /* Удаление узла            */
  35.            Node delnode);
  36.  
  37.   Node succ (LinList list,            /* Следующий узел           */
  38.          Node node);
  39.   Node prec (LinList list,            /* Предыдущий узел          */
  40.          Node node);
  41.  
  42.   TypeItem item (Node node);          /* Элемент узла             */
  43.  
  44.   Node first (LinList list);          /* Первый узел списка       */
  45.   Node last  (LinList list);          /* Последний узел списка    */
  46.  
  47.   int empty (LinList list);           /* Список пуст ?            */
  48.  
  49.   int destroynode (Node node);        /* Уничтожение
  50.                           изолированного узла */
  51.   void destroylist (LinList list) ;   /* Уничтожение списка       */
  52.  
  53. #endif
Листинг программы 
  1. /* owlist.c
  2.   Односвязный (однонаправленный) линейный список (One-Way list)
  3. */
  4.  
  5. #if !defined(OWLIST_H)
  6. #include "owlist.h"
  7. #endif
  8.  
  9. #if !defined(__STDLIB_H)
  10. #include <stdlib.h>
  11. #endif
  12.  
  13. LinList initlist(void)              /* Инициализация списка */
  14. {
  15.   LinList list;
  16.   list=malloc(sizeof list);
  17.   if (list) *list=NULL;
  18.   return (list);
  19. }
  20.  
  21. Node makenode (TypeItem item)       /* Создание узла */
  22. {
  23.   Node node;
  24.   node=malloc(sizeof(struct TypeNode));
  25.   if (node) { node->item=item;
  26.           node->next=NULL;
  27.   }
  28.   return (node);
  29. }
  30.  
  31. void addtofront (LinList list,      /* Добавление узла в начало */
  32.          Node newnode)      /*                   списка */
  33. {
  34. /* самостоятельно */
  35. }
  36.  
  37. void addtorear (LinList list,       /* Добавление узла в конец */
  38.         Node newnode)       /*                  списка */
  39. {
  40.   if (list &&                       /* список существует */
  41.       newnode && newnode->next==NULL) { /* узел существует и изолирован */
  42.     if (*list){    
  43.       Node p=*list;
  44.       while (p->next) p=p->next;
  45.       p->next=newnode;}
  46.     else addtofront (list, newnode);
  47. }
  48.  
  49. void insafter (LinList list,        /* Вставка узла в список */
  50.            Node newnode,        /*          за указанным */
  51.            Node p)
  52. {
  53. /* самостоятельно */
  54. }
  55.  
  56. void insbefore (LinList list,       /* Вставка узла в список */
  57.         Node newnode,       /*       перед указанным */
  58.         Node s)
  59. {
  60.   if (list && *list && s &&         /* список существует и не пуст, узлы */
  61.       newnode && newnode->next==NULL) /* существуют и newnode изолирован */
  62.     if (s == *list) { /* s - первый узел списка */
  63.       newnode->next=s;
  64.       *list=newnode;}
  65.     else {
  66.       TypeItem temp=s->item;
  67.       s->item=newnode->item;
  68.       newnode->item=temp;
  69.  
  70.       newnode->next=s->next;
  71.       s->next=newnode;
  72.     }
  73. }
  74.  
  75. Node deletenode (LinList list,      /* Удаление узла */
  76.          Node delnode)
  77. {
  78.   Node p;
  79.   if (list && *list && delnode){   /* список существует и не пуст,
  80.                          и указанный узел есть */
  81.     if (delnode->next){ /* если удаляемый узел не последний */
  82.       TypeItem temp;
  83.       p=delnode;
  84.       delnode=p->next;
  85.       temp=p->item;
  86.       p->item=delnode->item;
  87.       delnode->item=temp;
  88.       p->next=delnode->next;
  89.       delnode->next=NULL;
  90.     }
  91.     else if (delnode==*list) /* если удаляемый узел единственный в списке */
  92.        *list=NULL;
  93.      else { p=prec(list,delnode);
  94.         p->next=NULL;}
  95.     return(delnode);
  96.   }
  97.   else return (NULL);
  98. }
  99.  
  100. Node succ (LinList list,            /* Следующий узел */
  101.        Node node)
  102. {
  103. /* самостоятельно */
  104. }
  105.  
  106. Node prec (LinList list,            /* Предыдущий узел */
  107.        Node node)
  108. {
  109.   if (list && *list && node && node != *list) {
  110.                                     /* список существует и не пуст,
  111.                                        и указанный узел есть и не первый */
  112.     Node p=*list;
  113.     while (p->next!=node && p->next!=NULL) p=p->next;
  114.     if (p->next==node) return (p);
  115.   }
  116.   return (NULL); /* список list пуст, узел node первый
  117.             или не содержится в указанном списке */
  118. }
  119.  
  120. TypeItem item (Node node)           /* Элемент узла */
  121. {
  122. /* самостоятельно */
  123. }
  124.  
  125. Node first (LinList list)           /* Первый узел списка */
  126. {
  127. /* самостоятельно */
  128. }
  129.  
  130. Node last (LinList list)            /* Последний узел списка */
  131. {
  132. /* самостоятельно */
  133. }
  134.  
  135. int empty (LinList list)            /* Список пуст ? */
  136. {
  137. /* самостоятельно */
  138. }
  139.  
  140. int destroynode (Node node)        /* Уничтожение изолированного узла */
  141. {
  142.   if (node!=NULL && node->next==NULL){/* если node указывает на узел,
  143.                      который никуда не указывает
  144.                      (он может быть и последним
  145.                      узлом некоторого списка!) */
  146.     free(node);
  147.     return (0);}
  148.   return (1); /* node указывает на неизолированный узел */
  149. }
  150.  
  151. void destroylist (LinList list)     /* Уничтожение списка */
  152. {
  153.   if (list){
  154.     Node n=*list, s;
  155.     free(list);
  156.     while (n) {
  157.       s=n->next;
  158.       free(n);
  159.       n=s;
  160.     }
  161.   }
  162. }

Решение задачи: «Реализовать линейный список на основе односвязного линейного списка, определяемого своим началом»

textual
Листинг программы 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  4.  
  5. typedef struct _node {
  6.     void* ptr;
  7.     struct _node* next;
  8. } node;
  9.  
  10. typedef struct {
  11.     node* head;
  12.     node* tail;
  13.     size_t cnt;
  14. } slist;
  15.  
  16. static node* _prev_node(slist* lst, node* pos);
  17. static node* _new_node(slist* lst, node* pos, void* ptr);
  18. static node* _del_node(slist* lst, node* pos);
  19.  
  20. inline void   slist_init(slist* lst);
  21. inline size_t slist_size(slist* lst);
  22. inline int    slist_empty(slist* lst);
  23. int   slist_add_front(slist* lst, void* ptr);
  24. int   slist_add_back(slist* lst, void* ptr);
  25. node* slist_insert(slist* lst, node* pos, void* ptr);
  26. node* slist_delete(slist* lst, node* pos);
  27. void  slist_clear(slist* lst);
  28.  
  29.  
  30. int main(void){
  31.     int   i;
  32.     node* p;
  33.     slist lst;
  34.     slist_init(&lst);
  35.     for(i = 0; i < 20; ++i)
  36.         slist_add_back(&lst, (void*)(rand() % 10));
  37.     slist_add_front(&lst, (void*)4);
  38.  
  39.     for(p = lst.head; p != NULL; p = p->next)
  40.         printf("%d ", (int)p->ptr);
  41.     putchar('\n');
  42.  
  43.     //удалить все чётные числа
  44.     p = lst.head;
  45.     while(p != NULL){
  46.         if(!((int)p->ptr & 1)){
  47.             p = slist_delete(&lst, p);
  48.             continue;
  49.         }
  50.         p = p->next;
  51.     }
  52.  
  53.     for(p = lst.head; p != NULL; p = p->next)
  54.         printf("%d ", (int)p->ptr);
  55.     putchar('\n');
  56.  
  57.     //вставить -1 перед числом x < 6
  58.     p = lst.head;
  59.     while(p != NULL){
  60.         if((int)p->ptr < 6)
  61.             p = slist_insert(&lst, p, (void*)-1);
  62.         p = p->next;
  63.     }
  64.  
  65.     for(p = lst.head; p != NULL; p = p->next)
  66.         printf("%d ", (int)p->ptr);
  67.     slist_clear(&lst);
  68.     return 0;
  69. }
  70.  
  71.  
  72. //инициализация
  73. inline void slist_init(slist* lst){
  74.     lst->head = lst->tail = NULL;
  75.     lst->cnt  = 0;
  76. }
  77.  
  78. //кол-во
  79. inline size_t slist_size(slist* lst){
  80.     return lst->cnt;
  81. }
  82.  
  83. //проверка на валидность
  84. inline int slist_empty(slist* lst){
  85.     return (lst->head == NULL);
  86. }
  87.  
  88. //вставка в голову
  89. int slist_add_front(slist* lst, void* ptr){
  90.     return (_new_node(lst, lst->head, ptr) != NULL);
  91. }
  92.  
  93. //вставка в хвост
  94. int slist_add_back(slist* lst, void* ptr){
  95.     return (_new_node(lst, NULL, ptr) != NULL); 
  96. }
  97.  
  98. //вставка в произвольное место
  99. node* slist_insert(slist* lst, node* pos, void* ptr){
  100.     return _new_node(lst, pos, ptr);
  101. }
  102.  
  103. //произвольное удаление
  104. node* slist_delete(slist* lst, node* pos){
  105.     return _del_node(lst, pos);
  106. }
  107.  
  108. //удаление всех
  109. void slist_clear(slist* lst){
  110.     node* t;
  111.     while(lst->head != NULL){
  112.         t = lst->head;
  113.         lst->head = lst->head->next;
  114.         free(t);
  115.     }
  116.     lst->tail = NULL;
  117.     lst->cnt  = 0;
  118. }
  119.  
  120.  
  121. //предыдущий узел
  122. static node* _prev_node(slist* lst, node* pos){
  123.     node* p = lst->head, *i = lst->head;
  124.     while((i != NULL) && (i != pos)){
  125.         p = i;
  126.         i = i->next;
  127.     }
  128.     return p;
  129. }
  130.  
  131. //создание элемента
  132. static node* _new_node(slist* lst, node* pos, void* ptr){
  133.     node* i, *p = (node*)malloc(sizeof(node));
  134.     if(p != NULL){
  135.         p->ptr  = ptr;
  136.         p->next = NULL;
  137.  
  138.         if(lst->head == NULL)
  139.             lst->head = lst->tail = p;
  140.         else {
  141.             if(pos == lst->head){
  142.                 p->next   = lst->head;
  143.                 lst->head = p;
  144.             } else if(pos == NULL)
  145.                 lst->tail = lst->tail->next = p;
  146.             else {
  147.                 i = _prev_node(lst, pos);
  148.                 i->next = p;
  149.                 p->next = pos;
  150.             }
  151.         }
  152.         ++(lst->cnt);
  153.     }
  154.     return p->next;
  155. }
  156.  
  157. //удаление элемента
  158. static node* _del_node(slist* lst, node* pos){
  159.     node* t, *p = NULL;
  160.     if(pos == lst->head)
  161.         p = lst->head = lst->head->next;
  162.     else {
  163.         p = _prev_node(lst, pos);
  164.         t = p->next = pos->next;
  165.         if(pos == lst->tail)
  166.             lst->tail = p;
  167.         p = t;
  168.     }
  169.     --(lst->cnt);
  170.     free(pos);
  171.  
  172.     if(lst->head == NULL)
  173.         lst->tail = NULL;
  174.     return p;
  175. }

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 3.8 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы