(12)王道数据结构-循环链表

循环链表基本操作

循环单链表

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {  //定义单链表节点类型
    int data;           //每个节点存放一个数据
    struct LNode *next; //指针指向下一个节点
} LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool isTail(LinkList L, LNode *p);
LinkList CreatList();
LinkList LListInsert(LinkList L,int i,int x);
int count = 0; 
int main(void) {
    int i; 
    LinkList list, start; 
    InitList(list);
    printf("请输入循环单链表的数据, 以0结束！\n");  
    list = CreatList(); 
    printf("循环单链表的元素有：\n"); 
    for(start = list->next; start != NULL; start = start->next) { 
      if(count== 0) { 
          break; 
      } 
      printf("%d ", start->data); 
      count--; 
    } 
    printf("\n"); 
    return 0;
}

//初始化一个循环链表
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点
    if (L == NULL) {    //内存分配不足，分配失败
        return false;
    }
    L->next = L;        //头结点next指向头结点
    return true;
}

//判断循环单链表表尾节点
bool isTail(LinkList L, LNode *p) {
    if (p->next == L) {
        return true;
    } else {
        return false;
    }
}

//判断循环单链表是否为空
bool Empty(LinkList L) {
    if (L->next == L) {
        return true;
    } else {
        return false;
    }
}

//循环单链表的建立 
LinkList CreatList() { 
  LNode *L; 
  L = (LNode *)malloc(sizeof(LNode));   
  L->next = L;            
  LNode *r; 
  r = L;                 
  int x;              
  while(scanf("%d",&x)) { 
    if(x == 0) {
        break; 
    }
    count++; 
    LNode *p; 
    p = (LNode *)malloc(sizeof(LNode));   
    p->data = x;             
    r->next = p;             
    r = p; 
  } 
  r->next = L;  
  return L;   
} 

//循环单链表的插入，在循环链表的第i个位置插入x的元素 
LinkList LListInsert(LinkList L,int i,int x) { 
  LNode *pre;                     
  pre = L; 
  int tempi = 0; 
  for (tempi = 1; tempi < i; tempi++) {
      pre = pre->next; 
  }
  LNode *p;                      
  p = (LNode *)malloc(sizeof(LNode));  
  p->data = x;  
  p->next = pre->next; 
  pre->next = p; 
  return L;               
}  
 
//循环单链表的删除，在循环链表中删除值为x的元素 
LinkList DelData(LinkList L,int x) { 
  LNode *p,*pre;                  
  p = L->next; 
  while(p->data != x) {   
    pre = p;  
    p = p->next; 
  } 
  pre->next = p->next;               
  free(p); 
  return L; 
}  

循环双链表

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {  //定义单链表节点类型
    int data;           //每个节点存放一个数据
    struct DNode *prior, *next; //指针指向下一个节点
}DNode, *DLinklist;
bool InitDLinkList(DLinklist &L);
bool isTail(DLinklist L, DNode *p);
int main(void) {
    
    return 0;
}

//初始化空的循环双链表
bool InitDLinkList(DLinklist &L) {
    L = (DNode *)malloc(sizeof(DNode));     //分配一个节点
    if (L == NULL) {    //内存不足，分配失败
        return false;
    }
    L->prior = L;       //头结点的prior指向头结点
    L->next = L;        //头结点的next指向头结点
    return true;
}

//判断节点p是否为循环双链表的尾节点
bool isTail(DLinklist L, DNode *p) {
    if (p->next == L) {
        return true;
    } else {
        return false;
    }
}

//在p节点之后插入s节点
bool InsertNextDNode(DNode *p, DNode *s) {
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
}