双向循环单链表
//函数声明:#include"cirtwowaylinklist.h" #define _CRT_SECURE_NO_WARNINGS 1 #include#include typedef int ElemType; typedef struct CirDulNode { struct CirDulNode *prior; ElemType data; struct CirDulNode *next; }DulNode; void judgement_NULL(DulNode *head); DulNode * creat(); //创建链表 void insert(DulNode *head, int i, ElemType x); //插入结点 void delete_element(DulNode *head, ElemType x); //删除链表中所有值为X的结点 void delete_place(DulNode *head, int i); //删除链表中第i个结点 void find_place(DulNode *head, ElemType x); //寻找链表中所有x,所在的结点位置 void find_element(DulNode *head, int i); //寻找第i个结点上的值 void length(DulNode *head); void initslinklist(DulNode *head); //释放整个链表 void sortrank(DulNode *head); //对链表进行排序 void output_order(DulNode *head); //正序打印 void output_back(DulNode *head); //逆序打印 int means(); //选择方式 //函数实现:#include"cirtwowaylinklist.c" #include"cirtwowaylinklist.h" void judgement_NULL(DulNode *head) //判断动态内存是否开辟成功 { if (head == NULL) { perror("out of memory\n"); exit(EXIT_FAILURE); } } DulNode * creat() { DulNode *head, *p, *r; ElemType x; head = (DulNode *)malloc(sizeof(DulNode)); judgement_NULL(head); r = head; printf("开始建立:"); while (1) { scanf("%d", &x); if (x != 0) //建立链表,以0作为结束标志 { p = (DulNode *)malloc(sizeof(DulNode)); judgement_NULL(p); p->data = x; r->next = p; p->prior = r; r = p; } else break; } head->prior = r; //将链表首尾链接 r->next = head; printf("创建成功\n"); return head; } void insert(DulNode *head, int i, ElemType x) //在i位置上插入一个X,因为链表循环,所以i>1就一定能找到一个位置 { DulNode *p, *r; p = (DulNode *)malloc(sizeof(DulNode)); judgement_NULL(p); p->data = x; r = head; while (1) { if (i <= 1) break; r = r->next; i--; } if (i < 1) printf("没有该结点\n"); else { p->next = r->next; //在头结点之前,之后都可以插入 p->prior = r; r->next = p; p->next->prior = p; } } void delete_element(DulNode *head, ElemType x) //删除链表中所有的x元素所在的结点 { DulNode *p, *r; int count = 0; p = head->next; while (p != head) { if (p->data == x) { count++; r = p; p = p->next; r->prior->next = r->next; r->next->prior = r->prior; free(r); r = NULL; } else p = p->next; } if (count == 0) printf("链表中没有此元素\n"); else printf("共删除%d个\n", count); } void delete_place(DulNode *head, int i) //删除一个指定位置的结点,结点位置i>0 { DulNode *p; p = head; while (1) { if (i <= 1) break; p = p->next; i--; } if (i < 1) printf("没有该结点\n"); else { if (p->next = head) //如果要删除的结点是头结点则跳过删除头结点之后的结点 { p = head->next; head->next = p->next; p->next->prior = head; } else { p->prior->next = p->next; p->next->prior = p->prior; free(p); } } } void find_place(DulNode *head, ElemType x) //找到链表中所有的x元素所在的结点位置 { int count = 0; int flag = 0; DulNode *p; p = head->next; while (p != head) { count++; if (p->data == x) { flag++; printf("此元素结点位置:%d\n", count); } p = p->next; } if (flag == 0) printf("链表中没有此元素\n"); } void find_element(DulNode *head, int i) //找到i结点上的元素,并输出 { DulNode *p; p = head->next; while (p != head) { if (i <= 1) break; p = p->next; i--; } if (p == head || i != 1) printf("没有该结点\n"); else printf("此结点元素:%d\n", p->data); } void length(DulNode *head) { int len = 0; DulNode *p; p = head->next; while (p != head) { len++; p = p->next; } printf("链表长度:%d\n", len); } void initslinklist(DulNode *head) //释放整个链表 { DulNode *p; p = head->next; while (p != head) { p = p->next; free(p->prior); p->prior = NULL; } free(head); head = NULL; p = NULL; } void sortrank(DulNode *head) //对整个链表进行排序 { DulNode *p, *r; ElemType tmp; p = head->next; while (p->next!= head) { r = head->next; while (r->next!= head) { if ((r->data) >(r->next->data)) { tmp = r->data; r->data = r->next->data; r->next->data = tmp; } r = r->next; } p=p->next; } printf("排序成功\n"); } void output_order(DulNode *head) //正向打印整个链表 { DulNode *p; p = head; if (head->next == head) printf("链表为空\n"); else { printf("正序打印链表:"); p = p->next; while (p != head) { printf("%d ", p->data); p = p->next; } printf("\n"); } } void output_back(DulNode *head) //反向打印整个链表 { DulNode *p; p = head->prior; if (head->next == head) printf("链表为空\n"); else { printf("反向打印链表:"); while (p != head) { printf("%d ", p->data); p = p->prior; } printf("\n"); } } int means() //选择以哪种方式进行操作 { int m = 0; while (1) { printf("请选择方式:"); scanf("%d", &m); if (m == 1 || m == 2) break; printf("选择无效,请重新选择\n"); } return m; } //函数测试: #include"cirtwowaylinklist.h" int main() { DulNode *ret = NULL; int n = 0; int i = 0; ElemType x; printf("*********************************************\n"); printf("*********************************************\n"); printf("*1.CreatLinkList 2.Insert **********\n"); printf("*3.Delete 4.Find **********\n"); printf("*5.Length 6.Output **********\n"); printf("*7.InitsLinkLinst 8.Sortrank ********\n"); printf("*0.Exit *******************\n\n\n"); while (1) { printf("请选择功能:"); scanf("%d", &n); if (n == 0) //选择0直接退出 { free(ret); //退出前先释放列表 exit(1); } if (ret == NULL) //如果ret为空,则首先建立链表 { if (n == 1) { printf("创建链表以0作为结束标志\n"); ret = creat(); } else printf("请先建立链表\n"); } else { switch (n) //选择剩下的功能 { case 1: //当ret不为空时不能建立链表 printf("当前链表未结束,请先初始化链表\n"); break; case 2: printf("请输入要插入的元素和位置:"); scanf("%d", &x); scanf("%d", &i); insert(ret, i, x); break; case 3: printf("*1.delete_element 2.delete_place*\n"); if (means() == 1) { printf("请输入要删除的元素:"); scanf("%d", &x); delete_element(ret, x); } else { printf("请输入要删除的结点:"); scanf("%d", &i); delete_place(ret, i); } break; case 4: printf("*1.find_place 2.find_element*\n"); if (means() == 1) { printf("请输入要查找的元素:"); scanf("%d", &x); find_place(ret, x); } else { printf("请输入要查找的位置:"); scanf("%d", &i); find_element(ret, i); } break; case 5: length(ret); break; case 6: printf("*1.output_order 2.output_back*\n"); if (means() == 1) output_order(ret); else output_back(ret); break; case 7: //将当前链表释放 initslinklist(ret); ret = NULL; break; case 8: sortrank(ret); break; default: printf("选择无效,请重新选择\n"); break; } //switch()语句结束 } n = 0; } //循环结束 system("pause"); return 0; }
创新互联建站主要从事成都网站建设、成都网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务尖草坪,10余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220
本文标题:双向循环单链表
浏览地址:http://pwwzsj.com/article/phopjp.html