单循环链表(C语言实现)
程序员文章站
2022-07-02 20:37:57
//clist.h
//结构体定义以及函数声明
#ifndef clist_h
#define clist_h
#include
#include
#include...
//clist.h
//结构体定义以及函数声明
#ifndef clist_h #define clist_h #include #include #include #include typedef int elemtype; typedef struct node { elemtype data; struct node *next; }node, *pnode; typedef struct list { pnode head; pnode tail; int size; }list,*plist; bool initlist(plist list); void create_t(plist list,elemtype x); //尾插 void create_h(plist list,elemtype x); //头插 void del_back(plist list); //尾删 void del_front(plist list); //头删 void sortlist(plist list); //排序 void insert_val(plist list,elemtype x); //按值插 pnode find(plist list,elemtype x); void del_val(plist list,elemtype x); void modify(plist list,elemtype x1,elemtype x2); void clear(plist list); void destroy(plist list); void reserve(plist list); int length(plist list); void menu(); void showlist(plist list); void show_tail(plist list); elemtype next(plist list,elemtype x); elemtype prio(plist list,elemtype x); pnode prev(plist list,pnode p); #endif
//clist.cpp
//函数实现
#include"clist.h" void menu() //提供选项的菜单函数 { printf("***************************************************************\n"); printf("* [0] quit_system [1] create_t [2] create_h [3] showlist *\n"); printf("* [4] del_back [5] del_front [6] insert_val [7] show_tail*\n"); printf("* [8] find [9] del_val [10] sortlist [11] modify *\n"); printf("* [12]clear [13]destroy [14] resver [15]length *\n"); printf("* [16] next [17]prio *\n"); printf("***************************************************************\n"); } bool initlist(plist list) { list->head = (pnode)malloc(sizeof(node)); /初始化一个头结点 assert(list->head != null); //断言,表达式为真,接着往下执行 list->head->next = list->head; //初始化head和tail指针,使其都指向头节点 list->tail = list->head; list->size = 0; //长度初始化为0 return true; } void create_t(plist list,elemtype x) //尾插法 { pnode s = (pnode)malloc(sizeof(node)); assert(s != null); s->data = x; //填充数据域 list->tail->next = s; //tail指向最后一个节点,把新建立的节点链接到链表的最后 s->next = list->head; //单循环链表,新节点的next指向头结点 list->tail = s; //改变尾指针的指向 list->size++; } void showlist(plist list) //链表显示函数 { if(1>list->size) { printf("--链表为空\n"); return ; } pnode p = list->head->next; while(list->head != p) //逐个遍历链表 { printf("%d ",p->data); p=p->next; } printf("\n"); } void create_h(plist list,elemtype x) //头插法 { pnode s = (pnode)malloc(sizeof(node)); assert(s != null); s->data = x; //填充数据域 s->next = list->head->next; //新节点指向第一个节点 list->head->next = s; //头节点的next指向新节点s if(list->size == 0) //如果是第一次头插,需改变尾指针和尾节点的next指向,之后都不改变 { list->tail = s; list->tail->next = list->head; } list->size++; //插入一个,长度加1 } void del_back(plist list) //尾删 { if(0==list->size) return; pnode p = list->head; while(list->head != p->next->next) //找到倒数第二个节点 { p = p->next; } p->next = list->head; //把最后一个节点分离 free(list->tail); //释放最后一个节点 list->tail = p; //尾指针指向原来的倒数第二个节点(现在倒数第一) printf("--尾节点已删除\n"); list->size--; } void del_front(plist list) //头删 { if(0==list->size) return; else { pnode p = list->head->next; if(1==list->size) { //只有一个节点,若删去,需改变尾指针 list->tail = list->head; list->head->next = list->head; } else { list->head->next = p->next; //头指针指向第二个节点 } free(p); //释放第一个节点 } printf("--头节点已删除\n"); list->size--; } void show_tail(plist list) //为测试尾指针是否正确改变,需显示最后一个节点 { printf("--链表的尾节点是:》%d \n",list->tail->data); } void sortlist(plist list) // 对无序链表进行从小到大排序 { if(2>list->size) return ; pnode p = list->head->next; pnode q = p->next; for(int i = 0;isize-1;i++,p = list->head->next,q = p->next) //n个数比较n-1趟 { for(int j = 0;jsize-1-i;j++,p=q,q=q->next) //第i趟比较n-i次 { if(p->data > q->data) //如果前面的数大于后面,则交换 { p->data = p->data + q->data; q->data = p->data - q->data; p->data = p->data - q->data; } } } } void insert_val(plist list,elemtype x) //链表有序的前提下,给一个值插入 { pnode p = list->head->next,q = list->head; while(list->head != p) //找到能插入的位置,会在p、q之间 { if(xdata) break; q = p; p = p->next; } pnode s = (pnode)malloc(sizeof(node)); //初始化新节点 s->data = x; q->next = s; //把新节点插入到链表中(在p,q之间插入) s->next = p; if(list->head == p) //如果新节点的值最大,即尾插,需改变尾指针和尾节点的next指向 { list->tail = s; list->tail->next=list->head; } list->size++; } pnode find(plist list,elemtype x) //返回要查找元素的前面一个的地址 { pnode p = list->head; while(list->tail != p && list->head != p->next && x != p->next->data) { p = p->next; //循环结束,p指向x的前面一个元素 } if(list->head == p->next) //如果p指向最后一个元素,说明没有找到 { printf("--没找到!\n"); return null; } return p; } void del_val(plist list,elemtype x) //删除指定的值x { if(0 == list->size) return ; pnode p = find(list,x); pnode q = null; if(null != p) { q = p->next; //q指向要删除的节点 if(q == list->tail) //若删除最后一个节点,需改变尾指针 { p->next = list->head; list->tail = p; } else { p->next = q->next; } free(q); //释放要删除的节点 list->size--; printf("--%d已删除!\n",x); } return ; } void modify(plist list,elemtype x1,elemtype x2) //把原有的x1修改成x2 { pnode p = find(list,x1); if(null != p) p->next->data = x2; else return ; } void clear(plist list) //删除链表的所有节点,但不删除头结点 { pnode p = list->head->next; pnode q = p; while(list->head != p) { p = p->next; //p依次后移,跟屁虫q依次释放节点 free(q); q = p; } list->tail = list->head; //修改尾指针和链表长度 list->head->next = list->head; list->size = 0; printf("--链表已被清空!\n"); } void destroy(plist list) //摧毁链表,包括所有节点和头结点 { clear(list); free(list->head); list->head = null; list->tail = null; printf("--链表已被摧毁!\n"); } pnode prev(plist list,pnode p) //返回p指向的前面一个节点 { if(p != list->head) { pnode q = list->head->next; while(q != list->head && q->next != p) //依次往后移,知道尾指针的前面一个节点 q=q->next; if(q->next == p) return q; } return null; } void reserve(plist list) //逆置链表 { pnode s = (pnode)malloc(sizeof(node)); //建立一个节点 s->next = list->tail; pnode p = list->tail; while(list->tail != list->head->next) //把原链表的尾节点到第一个节点依次连接到新节点上 { list->tail = prev(list,list->tail); list->tail->next = list->head; p->next = list->tail; p=p->next; } p->next = s; //p指向第一个节点,即新链表的最后一个节点,尾指针的next指向头结点s,链表结束 free(list->head); //释放原来的头结点 list->head = s; //把s变成新的头指针 } int length(plist list) //求链表的长度 { return list->size; } elemtype next(plist list,elemtype x) //返回x的后继 { pnode p = find(list,x); if(null == p) return -1; if(p->next == list->tail) //因为是单循环链表,尾节点的下一个元素是第一个节点 { return list->head->next->data; } p=p->next; return p->next->data; } elemtype prio(plist list,elemtype x) //返回x的前驱 { pnode p = find(list,x); if(null != p) { if(p == list->head || p == list->tail) { return list->tail->data; } return p->data; } return -1; }
//main.cpp
//测试函数
#include "clist.h" int main() { list mylist; initlist(&mylist); elemtype item = 0; int pos = 0; int chose = 1; pnode p = null; while(chose) { menu(); printf("给出想要操作的序号:\n"); scanf("%d",&chose); switch(chose) { case 0: destroy(&mylist); chose = 0; break; case 1: printf("输入要尾插的数据[-1结束]:\n"); while(scanf("%d",&item),item!=-1) { create_t(&mylist,item); } break; case 2: printf("输入要头插的数据:\n"); while(scanf("%d",&item),item!=-1) { create_h(&mylist,item); } break; case 3: showlist(&mylist); break; case 4: del_back(&mylist); break; case 5: del_front(&mylist); break; case 6: printf("给出要插入的数:\n"); scanf("%d",&item); insert_val(&mylist,item); break; case 7: show_tail(&mylist); break; case 8: printf("输入要查找的数:\n"); scanf("%d",&item); p = find(&mylist,item); if(null!=p) printf("%d\n",p->next->data); break; case 9: printf("输入要删除的数:\n"); scanf("%d",&item); del_val(&mylist,item); break; case 10: sortlist(&mylist); break; case 11: printf("输入要修改的数和修改后的数\n"); scanf("%d %d",&item,&pos); modify(&mylist,item,pos); break; case 12: clear(&mylist); break; case 13: destroy(&mylist); break; case 14: reserve(&mylist); break; case 15: printf("链表长度为:%d\n",length(&mylist)); break; case 16: printf("输入想要找哪个一数的后继:\n"); scanf("%d",&item); printf("%d 的后继是:%d\n",item,next(&mylist,item)); break; case 17: printf("输入想要找哪个一数的前驱:\n"); scanf("%d",&item); printf("%d 的前驱是:%d\n",item,prio(&mylist,item)); break; default: printf("重新输入\n"); break; } } return 0; }