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

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

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

Есть модуль, реализующий линейный список на основе односвязного линейного списка, определяемого своим началом. Завершить его реализацию.
/* owlist.h
  АТД  LinList,
  реализованный через односвязный (однонаправленный) список
  (One-Way List)
*/
#ifndef OWLIST_H
#define OWLIST_H
 
#if !defined(CORELIST_H)
#include "corelist.h"                 /* определяет TypeItem      */
#endif
 
  struct TypeNode {TypeItem item;
           struct TypeNode *next;};
 
  typedef struct TypeNode **LinList;  /* линейный список          */
  typedef struct TypeNode *Node;      /* узел списка              */
 
  LinList initlist(void);             /* Инициализация списка     */
 
  Node makenode   (TypeItem item );   /* Создание узла            */
 
  void addtofront (LinList list,      /* Добавление узла в начало */
           Node newnode);     /*                   списка */
  void addtorear  (LinList list,      /* Добавление узла в конец  */
           Node newNode);     /*                   списка */
  void insafter   (LinList list,      /* Вставка узла в список    */
           Node newnode,      /*             за указанным */
           Node p);
  void insbefore  (LinList list,      /* Вставка узла в список    */
           Node newnode,      /*          перед указанным */
           Node s);
 
  Node deletenode (LinList list,      /* Удаление узла            */
           Node delnode);
 
  Node succ (LinList list,            /* Следующий узел           */
         Node node);
  Node prec (LinList list,            /* Предыдущий узел          */
         Node node);
 
  TypeItem item (Node node);          /* Элемент узла             */
 
  Node first (LinList list);          /* Первый узел списка       */
  Node last  (LinList list);          /* Последний узел списка    */
 
  int empty (LinList list);           /* Список пуст ?            */
 
  int destroynode (Node node);        /* Уничтожение
                          изолированного узла */
  void destroylist (LinList list) ;   /* Уничтожение списка       */
 
#endif
/* owlist.c
  Односвязный (однонаправленный) линейный список (One-Way list)
*/
 
#if !defined(OWLIST_H)
#include "owlist.h"
#endif
 
#if !defined(__STDLIB_H)
#include <stdlib.h>
#endif

LinList initlist(void)              /* Инициализация списка */
{
  LinList list;
  list=malloc(sizeof list);
  if (list) *list=NULL;
  return (list);
}
 
Node makenode (TypeItem item)       /* Создание узла */
{
  Node node;
  node=malloc(sizeof(struct TypeNode));
  if (node) { node->item=item;
          node->next=NULL;
  }
  return (node);
}
 
void addtofront (LinList list,      /* Добавление узла в начало */
         Node newnode)      /*                   списка */
{
/* самостоятельно */
}
 
void addtorear (LinList list,       /* Добавление узла в конец */
        Node newnode)       /*                  списка */
{
  if (list &&                       /* список существует */
      newnode && newnode->next==NULL) { /* узел существует и изолирован */
    if (*list){    
      Node p=*list;
      while (p->next) p=p->next;
      p->next=newnode;}
    else addtofront (list, newnode);
}
 
void insafter (LinList list,        /* Вставка узла в список */
           Node newnode,        /*          за указанным */
           Node p)
{
/* самостоятельно */
}
 
void insbefore (LinList list,       /* Вставка узла в список */
        Node newnode,       /*       перед указанным */
        Node s)
{
  if (list && *list && s &&         /* список существует и не пуст, узлы */
      newnode && newnode->next==NULL) /* существуют и newnode изолирован */
    if (s == *list) { /* s - первый узел списка */
      newnode->next=s;
      *list=newnode;}
    else {
      TypeItem temp=s->item;
      s->item=newnode->item;
      newnode->item=temp;
 
      newnode->next=s->next;
      s->next=newnode;
    }
}
 
Node deletenode (LinList list,      /* Удаление узла */
         Node delnode)
{
  Node p;
  if (list && *list && delnode){   /* список существует и не пуст,
                         и указанный узел есть */
    if (delnode->next){ /* если удаляемый узел не последний */
      TypeItem temp;
      p=delnode;
      delnode=p->next;
      temp=p->item;
      p->item=delnode->item;
      delnode->item=temp;
      p->next=delnode->next;
      delnode->next=NULL;
    }
    else if (delnode==*list) /* если удаляемый узел единственный в списке */
       *list=NULL;
     else { p=prec(list,delnode);
        p->next=NULL;}
    return(delnode);
  }
  else return (NULL);
}
 
Node succ (LinList list,            /* Следующий узел */
       Node node)
{
/* самостоятельно */
}
 
Node prec (LinList list,            /* Предыдущий узел */
       Node node)
{
  if (list && *list && node && node != *list) {
                                    /* список существует и не пуст,
                                       и указанный узел есть и не первый */
    Node p=*list;
    while (p->next!=node && p->next!=NULL) p=p->next;
    if (p->next==node) return (p);
  }
  return (NULL); /* список list пуст, узел node первый
            или не содержится в указанном списке */
}
 
TypeItem item (Node node)           /* Элемент узла */
{
/* самостоятельно */
}
 
Node first (LinList list)           /* Первый узел списка */
{
/* самостоятельно */
}
 
Node last (LinList list)            /* Последний узел списка */
{
/* самостоятельно */
}
 
int empty (LinList list)            /* Список пуст ? */
{
/* самостоятельно */
}
 
int destroynode (Node node)        /* Уничтожение изолированного узла */
{
  if (node!=NULL && node->next==NULL){/* если node указывает на узел,
                     который никуда не указывает
                     (он может быть и последним
                     узлом некоторого списка!) */
    free(node);
    return (0);}
  return (1); /* node указывает на неизолированный узел */
}
 
void destroylist (LinList list)     /* Уничтожение списка */
{
  if (list){
    Node n=*list, s;
    free(list);
    while (n) {
      s=n->next;
      free(n);
      n=s;
    }
  }
}

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

textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
 
typedef struct _node {
    void* ptr;
    struct _node* next;
} node;
 
typedef struct {
    node* head;
    node* tail;
    size_t cnt;
} slist;
 
static node* _prev_node(slist* lst, node* pos);
static node* _new_node(slist* lst, node* pos, void* ptr);
static node* _del_node(slist* lst, node* pos);
 
inline void   slist_init(slist* lst);
inline size_t slist_size(slist* lst);
inline int    slist_empty(slist* lst);
int   slist_add_front(slist* lst, void* ptr);
int   slist_add_back(slist* lst, void* ptr);
node* slist_insert(slist* lst, node* pos, void* ptr);
node* slist_delete(slist* lst, node* pos);
void  slist_clear(slist* lst);
 
 
int main(void){
    int   i;
    node* p;
    slist lst;
    slist_init(&lst);
    for(i = 0; i < 20; ++i)
        slist_add_back(&lst, (void*)(rand() % 10));
    slist_add_front(&lst, (void*)4);
 
    for(p = lst.head; p != NULL; p = p->next)
        printf("%d ", (int)p->ptr);
    putchar('\n');
 
    //удалить все чётные числа
    p = lst.head;
    while(p != NULL){
        if(!((int)p->ptr & 1)){
            p = slist_delete(&lst, p);
            continue;
        }
        p = p->next;
    }
 
    for(p = lst.head; p != NULL; p = p->next)
        printf("%d ", (int)p->ptr);
    putchar('\n');
 
    //вставить -1 перед числом x < 6
    p = lst.head;
    while(p != NULL){
        if((int)p->ptr < 6)
            p = slist_insert(&lst, p, (void*)-1);
        p = p->next;
    }
 
    for(p = lst.head; p != NULL; p = p->next)
        printf("%d ", (int)p->ptr);
    slist_clear(&lst);
    return 0;
}
 
 
//инициализация
inline void slist_init(slist* lst){
    lst->head = lst->tail = NULL;
    lst->cnt  = 0;
}
 
//кол-во
inline size_t slist_size(slist* lst){
    return lst->cnt;
}
 
//проверка на валидность
inline int slist_empty(slist* lst){
    return (lst->head == NULL);
}
 
//вставка в голову
int slist_add_front(slist* lst, void* ptr){
    return (_new_node(lst, lst->head, ptr) != NULL);
}
 
//вставка в хвост
int slist_add_back(slist* lst, void* ptr){
    return (_new_node(lst, NULL, ptr) != NULL); 
}
 
//вставка в произвольное место
node* slist_insert(slist* lst, node* pos, void* ptr){
    return _new_node(lst, pos, ptr);
}
 
//произвольное удаление
node* slist_delete(slist* lst, node* pos){
    return _del_node(lst, pos);
}
 
//удаление всех
void slist_clear(slist* lst){
    node* t;
    while(lst->head != NULL){
        t = lst->head;
        lst->head = lst->head->next;
        free(t);
    }
    lst->tail = NULL;
    lst->cnt  = 0;
}
 
 
//предыдущий узел
static node* _prev_node(slist* lst, node* pos){
    node* p = lst->head, *i = lst->head;
    while((i != NULL) && (i != pos)){
        p = i;
        i = i->next;
    }
    return p;
}
 
//создание элемента
static node* _new_node(slist* lst, node* pos, void* ptr){
    node* i, *p = (node*)malloc(sizeof(node));
    if(p != NULL){
        p->ptr  = ptr;
        p->next = NULL;
 
        if(lst->head == NULL)
            lst->head = lst->tail = p;
        else {
            if(pos == lst->head){
                p->next   = lst->head;
                lst->head = p;
            } else if(pos == NULL)
                lst->tail = lst->tail->next = p;
            else {
                i = _prev_node(lst, pos);
                i->next = p;
                p->next = pos;
            }
        }
        ++(lst->cnt);
    }
    return p->next;
}
 
//удаление элемента
static node* _del_node(slist* lst, node* pos){
    node* t, *p = NULL;
    if(pos == lst->head)
        p = lst->head = lst->head->next;
    else {
        p = _prev_node(lst, pos);
        t = p->next = pos->next;
        if(pos == lst->tail)
            lst->tail = p;
        p = t;
    }
    --(lst->cnt);
    free(pos);
 
    if(lst->head == NULL)
        lst->tail = NULL;
    return p;
}

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


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

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

5   голосов , оценка 3.8 из 5
Похожие ответы