数据结构之双向循环链表

[jyzwf]

之前讲了单链表，双向循环链表，链表的每个结点中较单链表多一个指针域。所以总共有两个指针域，一个指向直接后继，一个指向直接前趋，还有一个数据域。链表的最后一个结点的右指针指向第一个结点，头节点的左指针指向最后一个结点。
链表的基本操作有：

1. initDuList 初始化双向循环列表
2. createDuList 创建双向循环列表
3. printDuList 输出双向循环链表的每一个结点
4. getEle 查找插入的位置，返回结点的指针，否则返回NULL
5. insertDuList 在双向循环链表的第i个位置插入元素 e

主文件：

#include <stdio.h>
#include <stdlib.h>

#include "DuLinkList.h"


int main()
{
       DuLinkList h;
       int n,pos;
       char e;

       initDuList(&h);
       printf("输入元素的个数: ");
       scanf("%d",&n);
       getchar();
       createDuList(h,n);
       printf("链表中的元素: ");
       printDuList(h);

       printf("\n");
       printf("请输入插入的元素和位置：");
       scanf("%c",&e);
       getchar();
       scanf("%d",&pos);

       insertDuList(h,pos,e);

       printf("插入新元素后的链表中的元素: ");
       printDuList(h);
       return 0;
}

头文件：

#ifndef DULINKLIST_H_INCLUDED
#define DULINKLIST_H_INCLUDED

struct Node
{
       char data;
       struct Node *left;
       struct Node *right;
};

typedef struct Node DuListNode,*DuLinkList;

// 初始化双向循环列表
int initDuList(DuLinkList *head)
{
       *head = (DuLinkList)malloc(sizeof(DuListNode));  // 分配存储空间
       (*head)->right = *head;
       (*head)->left = *head;
       return 1;
}

// 创建双向循环列表
int createDuList(DuLinkList head,int n)
{
       DuListNode *p,*q;    // q指向最后一个结点
       int i;
       char e;
       q = head;

       for(i=1;i<=n;i++)
       {
              printf("输入第%d个结点的值：",i);
              e = getchar();
              p = (DuLinkList)malloc(sizeof(DuListNode));
              p->data = e;
              p->right = q->right;
              q->right = p;
              p->left = q;
              head->left = p;
              q=p;
              getchar();
       }

       return 1;
}


void printDuList(DuLinkList head)  // 输出双向循环链表的每一个结点
{
       DuListNode *p;
       p=head->right;

       while(p!=head)
       {
              printf("%c ",p->data);
              p=p->right;
       }
       printf("\n");
}


DuLinkList getEle(DuLinkList head,int i)  // 查找插入的位置，返回结点的指针，否则返回NULL
{
       DuLinkList p;
       int j=1;
       p=head->right;
       while(p!=head && j<i){
              p=p->right;
              j++;
       }
       if(p==head || j>i){
              return NULL;
       }

       return p;
}

int insertDuList(DuLinkList head,int i,char e)   // 在双向循环链表的第i个位置插入元素 e
{
       DuLinkList p,s;
       p = getEle(head,i);
       if(!p){
             return -1;
       }


       s = (DuLinkList) malloc(sizeof(DuListNode));
       s->data = e;
       s->left = p->left;
       p->left->right = s;
       s->right = p;
       p->left = s;

       return 1;
}


#endif // DULINKLIST_H_INCLUDED

结果：