双向循环链表程序(C语言版)-白红宇

双向循环链表程序(C语言版)

阅读量：4686 次

发布时间：2019-06-09

本文共 3648 字，大约阅读时间需要 12 分钟。

//dblist.h#include 
     
      #include 
      
       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;}//查找结点，成功则返回满足条件的结点指针，否则返回NULLpdbNode 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 
       
        #include 
        
         #include "dblist.h"#define FALSE 0#define TRUE  1typedef 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;  } }}