一个完整的双向链表程序(C语言版)

#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);

pdbNode ptmp = node->left;

// 从左到右恢复链接

node->left->right = pnode;

pnode->right = node;

// 从右到左恢复链接

node->left = pnode;

pnode->left = ptmp;

return node;

}

//查找结点,成功则返回满足条件的结点指针,否则返回NULL

pdbNode FindNode(pdbNode node, int data) // 参数1是链表的表头结点,参数2是要查找的结点(其中结点数据为data)

{

pdbNode pnode = node->right;

while (pnode->right != node && pnode->data != data)

{

  pnode = pnode->right;

}

if (pnode->right == node) return NULL;

return pnode;

}

//删除满足指定条件的结点, 返回表头结点, 删除失败返回NULL(失败的原因是不存在该结点)

pdbNode DeleteNode(pdbNode node, int data) // 参数1是链表的表头结点,参数2是要删除的结点(其中结点数据为data)

{

pdbNode ptmp;

pdbNode pnode = FindNode(node, data);

if (NULL == pnode) return NULL;

ptmp = pnode->left;

ptmp->right = pnode->right;

pnode->right->left = ptmp;

free(pnode);

return node;

}

//获取链表的长度

int GetLength(pdbNode node) // 参数为链表的表头结点

{

int nCount = 0;

pdbNode pnode = node->right;

while (pnode->right != node)

{

  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;

//int length;

bool bFlag = FALSE;

pdbNode pnode;

pdbNode list = CreateList(0);

while(FALSE == bFlag)

{

  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);

   break;

  case 2:

   printf("Input the data to delete:");

   scanf("%d", &data);

   DeleteNode(list, data);

   break;

  case 3:

   printf("Input the data to find:");

   scanf("%d", &data);

   pnode = FindNode(list, data);

 

   if (NULL != pnode)

   {

    printf("Find succeed!\n");

   }

   else

   {

    printf("Find failed!\n");

   }

   break;

  case 4:

   printf("The list's length is %d", GetLength(list));

   break;

  case 5:

   PrintList(list);

   break;

  case 6:

   ReverPrint(list);

   break;

  case 7:

   DeleteList(list);

   break;

  case 0:

   DeleteList(list);

   bFlag = TRUE;

  }

}

}

分享到:

发表评论

昵称

沙发空缺中,还不快抢~