如何创建一个空的c语言双向循环链表

Question

如题所述

Answer 1

至少需要一个元素，空的不能能建立数据结构。

1.循环链表
　循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。循环链表的运算与单链表的运算基本一致。所不同的有以下几点：
  1)在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。
  2)在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。

2.双向链表
  双向链表其实是单链表的改进。
  当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。

3.双向循环链表例程:

#include <stdio.h>
#include <stdlib.h>
typedef struct tagDbNode
{
 int data;
 struct tagDbNode * left;
 struct tagDbNode * right;
} DbNode, * pdbNode;
//创建结点
pdbNode CreateNode(int data)
{
 pdbNode pnode = (pdbNode)malloc(sizeof(DbNode));
 pnode->data = data;
 pnode->left = pnode->right = pnode; //创建新结点时，让其前驱和后继指针都指向自身
 
 return pnode;
}
//创建链表
pdbNode CreateList(int head)  //参数给出表头结点数据 （表头结点不作为存放有意义数据的结点）
{
 pdbNode pnode = (pdbNode)malloc(sizeof(DbNode));
 pnode->data = head;
 pnode->left = pnode->right = pnode;
 return pnode;
}
//插入新结点,总是在表尾插入; 返回表头结点
pdbNode InsertNode(pdbNode node, int data) // 参数1是链表的表头结点，参数2是要插入的结点（结
点数据为data）
{
 pdbNode pnode = CreateNode(data);
 
 // 从左到右恢复链接
 node->left->right = pnode;
 pnode->right = node;
 
 // 从右到左恢复链接
 pnode->left = node->left;
 node->left = pnode;
 
 return node;
}
//查找结点，成功则返回满足条件的结点指针，否则返回NULL
pdbNode FindNode(pdbNode node, int data) // 参数1是链表的表头结点，参数2是要查找的结点（其中
结点数据为data）
{
 pdbNode pnode = node->right;
 while (pnode != node && pnode->data != data)
 {
  pnode = pnode->right;
 }
 if (pnode == node)  return NULL;
 return pnode;
}
//删除满足指定条件的结点, 返回表头结点, 删除失败返回NULL（失败的原因是不存在该结点）
pdbNode DeleteNode(pdbNode node, int data) // 参数1是链表的表头结点，参数2是要删除的结点（其
中结点数据为data）
{
 pdbNode pnode = FindNode(node, data);
 if (NULL == pnode) return NULL;
 pnode->left->right=pnode->right;
 pnode->right->left=pnode->left;
 free(pnode);
 return node;
}
//获取链表的长度
int GetLength(pdbNode node) // 参数为链表的表头结点
{
 int nCount = 0;
 pdbNode pnode = node->right;
 while (pnode!= node)
 {
     pnode = pnode->right; 
  nCount++;
 }
 return nCount;
}
//顺序打印整个链表
void PrintList(pdbNode node) // 参数为链表的表头结点
{
 pdbNode pnode;
 if (NULL == node) return;
 pnode= node->right;
 while (pnode != node)
 {
  printf("%d   ", pnode->data);
  pnode = pnode ->right;
 }
 printf("\n");
}
//将链表反序打印
void ReverPrint(pdbNode node) //参数为链表的表头结点
{
 pdbNode pnode;
 if (NULL == node) return;
 pnode= node->left;
 while (pnode != node)
 {
  printf("%d   ", pnode->data);
  pnode = pnode->left;
 }
 printf("\n");
}
//删除链表
void DeleteList(pdbNode node) //参数为链表表头结点
{
 pdbNode pnode = node->right;
 pdbNode ptmp;
 if (NULL == node) return;
 
 while (pnode != node)
 {
  ptmp = pnode->right;
  free(pnode);
  pnode = ptmp;
 }
 free(node);
}
//测试程序
#include <stdio.h>
#include <stdlib.h>
#include "dblist.h"
#define FALSE 0
#define TRUE  1
typedef unsigned int bool;
void main()
{
 int nChoose;
 int data;
 bool bFlag = FALSE;
 pdbNode pnode;
 pdbNode list = CreateList(0);
 
 while(bFlag == FALSE)
 {
  printf("Main Menu\n");
  printf("1.  Insert\n");
  printf("2.  Delete Node\n");
  printf("3.  Find\n");
  printf("4.  Length\n");
  printf("5.  Positive Print\n");
  printf("6.  Negative Print\n");
  printf("7.  Delete List\n");
  printf("0.  quit\n\n");
 
  scanf("%d", &nChoose);
 
  switch(nChoose)
  {
  case 1:
   printf("Input the data to insert:");
   scanf("%d", &data);
   list = InsertNode(list, data);
   PrintList(list);
   printf("\n");
   break;
  case 2:
   printf("Input the data to delete: ");
   scanf("%d", &data);
   DeleteNode(list, data);
   PrintList(list);
   printf("\n");
   break;
  case 3:
   printf("Input the data to find: ");
   scanf("%d", &data);
   pnode = FindNode(list, data);
      if (NULL != pnode)
   {
    printf("Find succeed!\n");
 printf("\n");
   }
   else
   {
    printf("Find failed!\n");
 printf("\n");
   }
   break;
  case 4:
   printf("The list's length is %d\n", GetLength(list));
   printf("\n");
   break;
  case 5:
   PrintList(list);
   printf("\n");
   break;
  case 6:
   ReverPrint(list);
   printf("\n");
   break;
  case 7:
   DeleteList(list);
   printf("\n");
   break;
  case 0:
   DeleteList(list);
   bFlag = TRUE;
  }
 }
}

Answer 2

只是双向给你参考... 加个循环对你应该问题不大吧...

Answer 3

#include <stdio.h>
#include <stdlib.h>typedef struct node
{
int data;
struct node *pri; //前驱
struct node *next; //后驱
}List;
bool Insert(List *list, int index, int value)
{

//查找要插入的位置的前一个
int i = 0;
while( list && i < (index-1) )
{
list = list->next;
i++;
}
if( list==NULL || i > (index-1) )
{
printf("插入位置不正确, insert failed");
return false;
}

node* new_node = (node*)malloc(sizeof(node));
if(new_node == NULL)
{
printf("malloc new node memery fail\n");
return false;
}

new_node->data = value;
new_node->pri = list;
new_node->next = list->next;
list->next = new_node;
list->next->pri = new_node;

return true;
}bool DelNote(List *list, int index)
{
//查找要插入的位置的前一个
int i = 0;
while( list && i < (index-1) )
{
list = list->next;
i++;
}
if( list==NULL || i > (index-1) )
{
printf("删除位置不正确, insert failed");
return false;
}
node* p = list->next;
list->next = list->next->next;
list->next->pri = list;

printf("delete node value:%d \n",p->data);
free(p);
return true;

}
void Print(List *list)
{
if(list->next == NULL)
{
printf("list is empty!\n");
return ;
}

while(list->next)
{
list = list->next;
printf("%d ", list->data);
}
}int main()
{
List list;
//构建头结点
list.data = 0;
list.next = NULL;
list.pri = NULL;

// Print(&list);
int i = 1;
bool flag = false;
while(i<10)
{
flag =Insert(&list, i, i);
if(!flag)
{
printf("insert failed!!\n");
}
i++;
}
Print(&list);
printf("enter delete node index \n");

int index;
scanf("%d", &index);
flag = DelNote(&list, index);
if(flag)
printf("delete note success!!\n");
Print(&list);
return 0;
}