数据结构中双向链表和双向循环链表C语言实现

#include <stdio.h> #include <stdlib.h> #define FLAG -1 //停止输入的标志 typedef struct Node { struct Node * prior; int data; struct Node * next; }LNode,*LinkList; void CreateDoubleLinkedList(LinkList L); void CreateDoubleCircularLinkedList(LinkList L); void ShowDoubleLinkedList(LinkList L); void InsertDoubleLinkedList(LinkList L,int num,int local);//local是插入的位置 void DeleteDoubleLinkedList(LinkList L,int local);//local是删除的位置 LinkList GetLinkList(LinkList L,int local); void CreateDoubleCircularLinkedList(L); void ShowDoubleCircularLinkedList(LinkList L); void InsertDoubleCircularLinkedList(LinkList L,int num,int local); void DeleteDoubleCircularLinkedList(LinkList L,int local); void main() { LinkList L = (LinkList)malloc(sizeof(LNode)); /*printf("创建双向链表：\n"); CreateDoubleLinkedList(L); printf("遍历双向链表：\n"); ShowDoubleLinkedList(L); InsertDoubleLinkedList(L,100,3); printf("插入元素后的双向链表：\n"); ShowDoubleLinkedList(L); printf("删除元素后的双向链表：\n"); DeleteDoubleLinkedList(L,3); ShowDoubleLinkedList(L);*/ printf("创建双向循环链表：\n"); CreateDoubleCircularLinkedList(L); printf("遍历双向链表：\n"); ShowDoubleCircularLinkedList(L); printf("插入元素后的链表：\n"); InsertDoubleCircularLinkedList(L,100,3); ShowDoubleCircularLinkedList(L); printf("删除元素后的链表：\n"); DeleteDoubleCircularLinkedList(L,3); ShowDoubleCircularLinkedList(L); } void CreateDoubleLinkedList(LinkList L)//尾插法创建双向链表 { LinkList r,s;//s用于生成新的结点 int x = 0; r = L; scanf("%d",&x); while(x != FLAG)//尾插法 { s = (LinkList)malloc(sizeof(LNode)); s->data = x; r->next = s; s->prior = r; r = r->next; scanf("%d",&x); } r->next = NULL; } void ShowDoubleLinkedList(LinkList L)//遍历停止的标志是什么 游标e->next != L; { /*LinkList e = L->next; printf("%d",e->data); while(e) { e = e->next; printf("->%d",e->data); } printf("\n");*/ LinkList p = L->next; printf("%d",p->data); p = p ->next; while(p != NULL)//先输出再后移 { printf("->%d",p->data); p = p->next; } printf("\n"); } void InsertDoubleLinkedList(LinkList L,int num,int local) { LinkList p; int i;//i是插入的下标 i = local - 1; p = GetLinkList(L,local - 1); if(p == NULL) //假设链表的长度是2 插入位置是3 没问题 但是插入位置如果是4及以上 就会出现p == NULL的情况 { printf("插入位置不合法！\n"); exit(1); } /*else if(p->next == NULL) // 说明此时是在最后插入元素 { LinkList s = (LinkList)malloc(sizeof(LNode)); s->data = num; s->next = p->next; //p->next->prior = s; p->next = s; s->prior = p; } else { LinkList s = (LinkList)malloc(sizeof(LNode)); s->data = num; s->next = p->next; p->next->prior = s; //NULL->prior = s 的情况是什么意思 p->next = s; s->prior = p; }*/ //简化写法 else { LinkList s = (LinkList)malloc(sizeof(LNode)); s->data = num; s->next = p->next; if(p->next)p->next->prior = s; // 存在后继结点的情况 p->next = s; s->prior = p; } } void DeleteDoubleLinkedList(LinkList L,int local) { LinkList p,q; p = GetLinkList(L,local - 1); if(p == NULL) { printf("删除位置不合法！"); exit(1); } else { if(p->next == NULL) { printf("删除位置不合法！"); exit(1); } else { q = p->next; p->next = q->next; if(q->next)//为NULL说明删除的是最后一个结点 不是NULL说明不是最后一个结点 q->next->prior = p; free(q); } } } LinkList GetLinkList(LinkList L,int local) { LinkList p = L; int j = 0;//计数器 while(p != NULL && j < local) { p = p->next; j++; } return p; } //双向循环链表 void CreateDoubleCircularLinkedList(LinkList L)//尾插法创建循环双向链表 { LinkList r,s;//s用于生成新的结点 int x = 0; r = L; scanf("%d",&x); while(x != FLAG)//尾插法 { s = (LinkList)malloc(sizeof(LNode)); s->data = x; r->next = s; s->prior = r; r = r->next; scanf("%d",&x); } //不同点在于首尾相连 r->next = L; L->prior = r; } void ShowDoubleCircularLinkedList(LinkList L) { LinkList p = L->next; printf("%d",p->data); p = p->next; while(p != L) { printf("->%d",p->data); p = p->next; } printf("\n"); } void InsertDoubleCircularLinkedList(LinkList L,int num,int local) { LinkList p; int i;//i是插入的下标 i = local - 1; p = GetLinkList(L,local - 1); if(p == L) //假设链表的长度是2 插入位置是3 没问题 但是插入位置如果是4及以上 就会出现p == NULL的情况 { printf("插入位置不合法！\n"); exit(1); } /*else if(p->next == NULL) // 说明此时是在最后插入元素 { LinkList s = (LinkList)malloc(sizeof(LNode)); s->data = num; s->next = p->next; //p->next->prior = s; p->next = s; s->prior = p; } else { LinkList s = (LinkList)malloc(sizeof(LNode)); s->data = num; s->next = p->next; p->next->prior = s; //NULL->prior = s 的情况是什么意思 p->next = s; s->prior = p; }*/ //简化写法 else { LinkList s = (LinkList)malloc(sizeof(LNode)); s->data = num; s->next = p->next; //if(p->next)p->next->prior = s; 不需要判断这一步 因为双向循环链表一定是存在后继的 纵使在最后一个插入 他的后继是第一个元素 p->next = s; s->prior = p; } } void DeleteDoubleCircularLinkedList(LinkList L,int local) { LinkList p,q; p = GetLinkList(L,local - 1); if(p == L) { printf("删除位置不合法！"); exit(1); } else { if(p->next == L)//不同点 { printf("删除位置不合法！"); exit(1); } else { q = p->next; p->next = q->next; /*if(q->next)//为NULL说明删除的是最后一个结点 不是NULL说明不是最后一个结点 q->next->prior = p;*/ free(q); } } }