原创 双向链表

/*//////////////////////////////////////////////////////////////////////////////
文件名:循环链表
功能实现:
时间:2011年10月6日
修改时间:2011年10月9日
//////////////////////////////////////////////////////////////////////////////*/

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

typedef char DataType;

typedef struct Node
{
 DataType data;
 struct Node *prior;
 struct Node *next;
}DListNode, *DLinkList;

////////////////////////////////////////////////////////////////////////////////
int InitDList(DLinkList *head);
int CreateDList(DLinkList head, int n);/*创建具有n个结点的循环链表*/
int InsertDList(DLinkList haed, int i, DataType e);
DListNode *GetElem(DLinkList head, int i);
void PrintDList(DLinkList head);
////////////////////////////////////////////////////////////////////////////////

/*//////////////////////////////////////////////////////////////////////////////
函数名:       InitDList
函数功能:   初始化双向循环链表
入口参数: *head
出口参数: 
//////////////////////////////////////////////////////////////////////////////*/
int InitDList(DLinkList *head)
{
 *head = (DLinkList)malloc(sizeof(DListNode));
 if(! head)
  return -1;
 (*head)->next = *head;/*使头结点的prior和next指向自己*/
 (*head)->prior = *head;
 return 1;
}

/*//////////////////////////////////////////////////////////////////////////////
函数名:       CreateDList
函数功能:   创建双向循环链表
入口参数: DLinkList head, int n
出口参数: 
//////////////////////////////////////////////////////////////////////////////*/
int CreateDList(DLinkList head, int n)/*创建具有n个结点的循环链表*/
{
 DListNode *s, *q;
 int i;
 DataType e;
 
 q=head;/*指针q指向头结点*/
 
 for( i=1; i<=n; i++ )
  {
   printf("输入第%d个元素", i );
   e = getchar();/*输入第i个元素的值*/
   s = (DListNode *)malloc(sizeof(DListNode));
   s->data = e;/*给新生成的结点赋值*/
   
   /*将所生成的结点插入到双向循环链表中*/
   s->next = q->next;
   q->next = s;
   s->prior = q;
   head->prior = s; /*这里要要注意头结点的prior指向新插入
   的结点*/
   q=s;  /*  q始终指向最后一个结点*/

   getchar();/*此处的getchar()是为了清掉Enter按键*/
  }
 return 1;
}

/*//////////////////////////////////////////////////////////////////////////////
函数名:       InsertDList

函数功能:   在双向循环链表的第i个位置插入元素e，插入成功
返回1，否则返回0

入口参数: DLinkList haed, int i, DataType e
出口参数: 
//////////////////////////////////////////////////////////////////////////////*/
int InsertDList(DLinkList head, int i, DataType e)
{
 DListNode *p, *s;
 /*指针p指向第i 个元素位置*/
 p=GetElem(head,i);
 
 if( !p )/*没获取成功则返回NULL直接退出返回0*/
  return 0;
 
 s = (DListNode *)malloc(sizeof(DListNode));
 
 if( !s )/*如果分配内存不成功则返回-1退出*/
  return -1;
 
 s->data = e;/*新生成的结点数据域赋值e*/
 
 /*将s结点插入到双向循环链表*/
 s->prior = p->prior;
 p->prior->next = s;
 s->next = p;
 p->prior = s;
 return 1;
}

/*//////////////////////////////////////////////////////////////////////////////
函数名:       *GetElem
函数功能:  查找插入的位置，找到返回该结点的指针，否则
返回NULL
入口参数: DLinkList head, int i
出口参数: 
//////////////////////////////////////////////////////////////////////////////*/
DListNode *GetElem(DLinkList head, int i)
{
 DListNode *p;
 int j;
 p=head->next;/*p指向第一个结点*/
 j=1;
 while( p != head && j<i )
  {
   p=p->next;
   j++;
  }
 if( p==head || j>i )
  return NULL;
 return p;
}

/*//////////////////////////////////////////////////////////////////////////////
函数名:       main()
函数功能:  主函数
入口参数:
出口参数: 
//////////////////////////////////////////////////////////////////////////////*/
void PrintDList(DLinkList head)
{
 DListNode *p;
 p=head->next;
 while(p != head)
  {
   printf( "%c" , p->data );
   p=p->next;
  }
 printf("\n");
}

/*//////////////////////////////////////////////////////////////////////////////
函数名:       main()
函数功能:  主函数
入口参数:
出口参数: 
//////////////////////////////////////////////////////////////////////////////*/
void main()
{
 DLinkList h;
 int n;
 int pos;
 char e;
 InitDList(&h);
 printf("输入元素个数:");
 scanf("%d",&n);
 getchar();
 CreateDList(h, n);
 printf("输入元素个数：");
 PrintDList(h);
 printf("请输入插入的元素及位置:");
 scanf( "%c" , &e );
 getchar();
 scanf( "%d", &pos);
 InsertDList(h, pos, e);
 printf("插入元素后链表中的元素");
 PrintDList(h);
}