C语言实现的循环单链表功能示例

时间:2021-05-20

本文实例讲述了C语言实现的循环单链表功能。分享给大家供大家参考,具体如下:

SClist.h

#ifndef __SCLIST_H__#define __SCLIST_H__#include<cstdio>#include<malloc.h>#include<assert.h>typedef int ElemType;typedef struct Node { ElemType data; struct Node *next;}Node,*PNode;typedef struct List { PNode first; PNode last; size_t size;}List;void InitSClist(List *list);//初始化循环单链表void push_back(List *list, ElemType x);//在循环单链表的末尾插入元素void push_front(List *list, ElemType x);//在循环单链表的头部插入元素void show_list(List *list);//打印循环单链表void pop_back(List *list);//删除循环单链表的最后一个元素void pop_front(List *list);//删除循环单链表的第一个元素void insert_val(List *list, ElemType val);//将数据元素插入到循环单链表中(要求此时循环单链表中的数据元素顺序排列)Node* find(List *list, ElemType x);//查找循环单链表中数据值为x的结点int length(List *list);//求循环单链表的长度void delete_val(List *list, ElemType x);//按值删除循环单链表中的某个数据元素void sort(List *list);//对循环单链表进行排序void reverse(List *list);//逆置循环单链表void clear(List *list);//清除循环单链表void destroy(List *list);//摧毁循环单链表//优化Node* _buynode(ElemType x);//创建结点#endif

SClist.cpp

#include"SClist.h"Node* _buynode(ElemType x) { Node *s = (Node*)malloc(sizeof(Node)); assert(s != NULL); s->data = x; s->next = NULL; return s;}void InitSClist(List *list) { Node *s = (Node*)malloc(sizeof(Node)); assert(s != NULL); list->first = list->last = s; list->last->next = list->first;//让链表最后一个结点的指针域指向头结点,从而时链表循环 list->size = 0;}void push_back(List *list, ElemType x) { Node *s = _buynode(x); list->last->next = s; list->last = s; list->last->next = list->first; list->size++;}void push_front(List *list, ElemType x) { Node *s = _buynode(x); s->next = list->first->next; list->first->next = s; if (list->last == list->first) list->last = s; list->size++;}void show_list(List *list) { Node *p = list->first->next; while (p != list->first) { printf("%d->", p->data); p = p->next; } printf("Nul.\n");}void pop_back(List *list) { if (list->size == 0) return; Node *p = list->first; while (p->next != list->last) p = p->next; free(list->last); list->last = p; list->last->next = list->first; list->size--;}void pop_front(List *list) { if (list->size == 0) return; Node *p = list->first->next; list->first->next = p->next; if (list->size == 1) list->last = list->first; free(p); list->size--;}void insert_val(List *list, ElemType x) { Node *p = list->first; while (p->next != list->last && p->next->data < x) p = p->next; if (p->next == list->last && p->next->data < x) push_back(list, x); else { Node *s = _buynode(x); s->next = p->next; p->next = s; list->size++; }}Node* find(List *list, ElemType key) { if (list->size == 0) return NULL; Node *p = list->first->next; while(p != list->first && p->data != key) p = p->next; if (p == list->first) return NULL; return p;}int length(List *list) { return list->size;}void delete_val(List *list, ElemType x) { if (list->size == 0) return; Node *p = find(list, x); if (p == NULL) { printf("没有要删除的数据!\n"); return; } if (p == list->last) pop_back(list); else { Node *q = p->next; p->data = q->data; p->next = q->next; free(q); list->size--; }}void sort(List *list) { if (list->size == 0 || list->size == 1) return; Node *s = list->first->next; Node *q = s->next; list->last->next = NULL; list->last = s; list->last->next = list->first; while (q != NULL) { s = q; q = q->next; Node *p = list->first; while (p->next != list->last && p->next->data < s->data) p = p->next; if (p->next == list->last &&p->next->data < s->data) { list->last->next = s; list->last = s; list->last->next = list->first; } else { s->next = p->next; p->next = s; } }}void reverse(List *list) { if (list->size == 0 || list->size == 1) return; Node *p = list->first->next; Node *q = p->next; list->last->next = NULL; list->last = p; list->last->next = list->first; while (q != NULL) { p = q; q = q->next; p->next = list->first->next; list->first->next = p; }}void clear(List *list) { Node *p = list->first->next; while (p != list->first) { list->first->next = p->next; free(p); p = list->first->next; } list->last = list->first; list->last->next = list->first; list->size = 0;}void destroy(List *list) { clear(list); free(list->first); list->first = list->last = NULL;}

main.cpp

#include"SClist.h"void main() { List mylist; InitSClist(&mylist); ElemType item; Node *p = NULL; int select = 1; while (select) { printf("*******************************************\n"); printf("*[1] push_back [2] push_front *\n"); printf("*[3] show_list [4] pop_back *\n"); printf("*[5] pop_front [6] insert_val *\n"); printf("*[7] find [8] length *\n"); printf("*[9] delete_val [10] sort *\n"); printf("*[11] reverse [12] clear *\n"); printf("*[13*] destroy [0] quit_system *\n"); printf("*******************************************\n"); printf("请选择:>>"); scanf("%d", &select); if (select == 0) break; switch (select) { case 1: printf("请输入要插入的数据(-1结束):>"); while (scanf("%d", &item), item != -1) { push_back(&mylist, item); } break; case 2: printf("请输入要插入的数据(-1结束):>"); while (scanf("%d", &item), item != -1) { push_front(&mylist, item); } break; case 3: show_list(&mylist); break; case 4: pop_back(&mylist); break; case 5: pop_front(&mylist); break; case 6: printf("请输入要插入的数据:>"); scanf("%d", &item); insert_val(&mylist, item); break; case 7: printf("请输入要查找的数据:>"); scanf("%d", &item); p = find(&mylist, item); if (p == NULL) printf("要查找的数据在单链表中不存在!\n"); break; case 8: printf("单链表的长度为%d\n", length(&mylist)); break; case 9: printf("请输入要删除的值:>"); scanf("%d", &item); delete_val(&mylist, item); break; case 10: sort(&mylist); break; case 11: reverse(&mylist); break; case 12: clear(&mylist); break; //case 13: //destroy(&mylist); //break; default: printf("选择错误,请重新选择!\n"); break; } } destroy(&mylist);}

希望本文所述对大家C语言程序设计有所帮助。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章