Реализовать линейный список на основе односвязного линейного списка, определяемого своим началом - 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; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д