C语言实现循环双链表

本文为大家分享了C语言实现循环双链表的具体代码,供大家参考,具体内容如下

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h> 
typedef int DataType;
typedef struct Node
{
  DataType data;            //    数据域 
  struct Node * prior;      //    前趋指针 
  struct Node * next;       //    后继指针 
      
}LinkList;

LinkList* Init_List();                                //    初始化循环双链表 
bool Creat_List(LinkList * L);                        //    创建链表 
int Length_List(LinkList * L);                        //    链表长度 
bool Empty_List(LinkList * L);                        //    判空 
bool Insert_List(LinkList * L, int pos, DataType x);  //    插入 
bool Delete_List(LinkList * L, int pos, DataType * x);//    删除 
bool Destroy_List(LinkList * L);                      //    销毁链表
bool Traverse_List(LinkList * L);                     //    遍历链表 
int Prior_Value(LinkList * L, int pos);               //    前趋结点的值 

int main()
{
  DataType x;
  int pos;
  
  LinkList * L = Init_List();
  if(Creat_List(L))
      printf("链表构造成功!\n");
  else
      printf("链表构造失败!\n");
  printf("遍历链表:");
  Traverse_List(L);
  
  printf("链表结点个数:%d\n\n", Length_List(L));
  
  printf("输入要求前趋结点的结点:");
  scanf("%d",&pos); 
  printf("第%d个结点的前趋结点:%d\n\n",pos,Prior_Value(L, pos));
  
  Insert_List(L, 2, 5);
  printf("插入结点:第2个结点\n");
  printf("插入元素:5\n");
  printf("遍历链表:");
  Traverse_List(L);
  
  Delete_List(L, 3, &x);
  printf("删除结点:第3个结点\n");
  printf("被删除元素:%d\n",x);
  printf("遍历链表:");
  Traverse_List(L);
  
  if(Destroy_List(L))
      printf("销毁成功!\n");
  else
      printf("销毁失败!\n");
   
  return 0; 
} 

LinkList* Init_List()
{
  LinkList * L = (LinkList *)malloc(sizeof(LinkList));    //    创建头结点 
  if(!L)
  {
      printf("申请空间失败!\n");
      exit(-1);
  }
  
  L->next = L->prior = L;    //    空表,前趋指针和后继指针均指向其自身
  return L;                 //    返回头结点的地址 
}

bool Creat_List(LinkList * L)
{
  int i,n,val;
  LinkList * p = L;    //    保证L始终指向头结点 
  
  printf("请输入循环双链表的结点个数:");
  scanf("%d",&n);
  
  for(i=0; i<n; ++i)
  {
      printf("第%d个结点:",i+1);
      scanf("%d",&val);
      
      LinkList * q = (LinkList*)malloc(sizeof(LinkList));
      q->data = val;
      p->next = q;
      q->prior = p;
      p = q;
  }
  
  p->next = L;    //    保证最后一个结点的后继指针指向头结点 
  L->prior = p;    //    保证头结点的前趋指针指向最后一个结点 
  return true;
}

int Length_List(LinkList * L)
{
  int len = 0;
  LinkList * p = L->next;    
   
  while(p!=L)    //    最后一个结点也要加上 
  {
      len++;
      p = p->next;
  }
  
  return len;
}

bool Empty_List(LinkList * L)
{
  if(L->next==L&&L->prior==L)
      return true;
  else
      return false;
}

bool Insert_List(LinkList * L, int pos, DataType x)
{
  int i = 1;
  LinkList * p = L->next;
  
  if(pos<1||pos>Length_List(L))
      return false;
  
  while(i<pos-1&&L!=p)    //    指针移动到被插入结点的前一个结点 
  {
      i++;
      p = p->next;
  }
  
  LinkList * q = (LinkList*)malloc(sizeof(LinkList));
  q->data = x;
  q->next = p->next;
  q->prior = p;
  p->next->prior = q;
  p->next = q;
  return true;
}

bool Delete_List(LinkList * L, int pos, DataType * x)
{
  int i = 1;
  LinkList * p = L->next;
  
  if(pos<1||pos>Length_List(L))
      return false;
  
  while(i<pos-1&&L!=p)
  {
      i++;
      p = p->next;
  }
  
  LinkList * q = p->next;
  *x = q->data;
  p->next = q->next;
  q->next->prior = p;
  free(q);
  return true;
}

bool Destroy_List(LinkList * L)
{
//    将循环双链表变成单链表 
  LinkList * p = L->next;
  L->next = NULL;        //    空表时, 头结点的前趋指针、后继指针都是指向其自身 
  L->prior = NULL;    //    销毁时,头结点前趋指针、后继指针指向空 
  
  while(p)
  {
      LinkList * q = p->next;
      free(p);
      p = q;
  }
  
  L = p = NULL; 
  return true;
}

bool Traverse_List(LinkList * L)
{
  if(Empty_List(L))
      return false;
       
  LinkList * p = L->next;
  
  while(p!=L)
  {
      printf("%3d",p->data);
      p = p->next;
  }
  
  printf("\n\n");
  
}

int Prior_Value(LinkList * L, int pos)
{
  int i = 1;
  LinkList * p = L->next;
  
  if(pos<1||pos>Length_List(L))
      return false;
  
  while(i<pos&&L!=p)    //    指向pos要求的结点 
  {
      i++;
      p = p->next;
  }
  
  return p->prior->data;
  
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程宝库

fgets()函数fgets()函数和gets()函数一样,都是读取字符串,不过gets()函数通常用来从键盘读取输入的字符串,fgets()函数可以通过文件来读取字符串。下面通一个例子来演 ...