今天做数据结构题集，做到此题目，自己将题目全部实现了一遍（很详细的注释），特记此文。（编译环境VC6.0，全部通过，可直接复制运行），题目中涉及到了C的位异或运算，我写了一篇“C语言中的位运算”，可看下。

代码如下：

头文件："common.h"

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <string.h>
#define OVERFLOW 0
#define ERROR 0
#define OK 1
#define FALSE 0
#define TRUE 0
#define INFEASIBLE 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define CHARACTER 'C'
#define INTEGER   'I'
#define FLOAT     'F'
#define LEFT 0
#define RIGHT 1
typedef int Status;
typedef int ElemType;

/--异或指针双向链表--/
typedef struct XorNode
{
 char data;
 struct XorNode *LRPtr;
}XorNode,*XorPointer;
typedef struct     // 无头结点的异或指针双向链表
{
 XorPointer Left,Right;// 分别指向链表的左端和右端
}XorLinkedList;

/------异或链表相关函数------/
XorPointer XorP(XorPointer p,XorPointer q)
{
 //指针异或函数XorP返回指针p和q的异或（XOR）值
 unsigned long x,y,z;
 x=(unsigned long)p;
 y=(unsigned long)q;
 z=x^y;
 return (XorPointer)z;
}

void PrintXorList(XorLinkedList A,int direction)
{
 //按照任一方向依次输出链表中各元素的值，LEFT为左,RIGHT为右
 XorNode *p,*pre=NULL,*q=NULL;
 if(direction==LEFT)
  p=A.Left;//从左边开始遍历
 else
  p=A.Right;//从右边开始遍历
 while(p!=NULL)
 {
  printf("%c",p->data);
  q=XorP(pre,p->LRPtr);
  pre=p;
  p=q;
 }

}

Status InsertXorList(XorLinkedList &A,int i,XorNode *a)
{
 //向链表中第i个结点之前插入一个结点（从1开始，左边算起）
 if(i<=0)
  return ERROR;
 XorNode *p=A.Left,*pre=NULL,*q;
 if(p==NULL)//当链表还为空时比较特殊
 {
  A.Left=a;
  A.Right=a;
  a->LRPtr=NULL;
  return OK;
 }

 if(i==1)//在第一个位置之前插入比较特殊
 {
  q=XorP(pre,p->LRPtr);//找到下一个结点，以便修改
  p->LRPtr=XorP(a,q);
  a->LRPtr=XorP(NULL,p);
  A.Left=a;
  return OK;
 }

 int count=1;

 while(count<i&&p!=NULL)
 {
  q=XorP(pre,p->LRPtr);
  pre=p;
  p=q;
  count++;
 }
 
 if(p==NULL)  //在最后一个位置插入也比较特殊
 {
  q=XorP(pre->LRPtr,NULL);
  pre->LRPtr=XorP(q,a);
  a->LRPtr=XorP(pre,NULL);
  A.Right=a;
 }
 else  //在中间某一位置之前插入
 {
  q=XorP(pre->LRPtr,p);//先修改插入位置之前的结点的指针域
  pre->LRPtr=XorP(q,a);
  q=XorP(pre,p->LRPtr);//修改插入位置的指针域
  p->LRPtr=XorP(a,q);
  a->LRPtr=XorP(pre,p);//修改插入结点的指针域
 }
 
 return OK;
}

Status DeleteXorList(XorLinkedList &A,int i)
{
 //删除链表中第i个结点（从1开始左边开始）
 if(i<=0)
  return ERROR;
 XorNode *p=A.Left,*pre=NULL,*q;
 int count=1;

 if(p->LRPtr==NULL) //如果链表只剩下最后一个结点，直接删除
 {
  free(p);
  A.Left=NULL;
  A.Right=NULL;
  printf("链表为空！");
  return OK;
 }

 if(i==1) //第一个结点的删除比较特殊
 {
  pre=XorP(p->LRPtr,NULL);//第二个结点
  q=XorP(pre->LRPtr,p);//求得第三个结点地址
  free(p);
  pre->LRPtr=XorP(NULL,q);
  A.Left=pre;
  return OK;
 }

 while(count<i&&p!=NULL)
 {
  q=XorP(pre,p->LRPtr);
  pre=p;
  p=q;
  count++;
 }

 if(p==NULL)
 {
  printf("无此结点可被删除\n");
  return ERROR;
 }
 else
 {
  if(XorP(p->LRPtr,pre)==NULL)//删除最后一个节点比较特殊
  {
   q=XorP(pre->LRPtr,p);//倒数第三个结点
   pre->LRPtr=XorP(q,NULL);//修改倒数第二个节点的指针域
   free(p);
   A.Right=pre;
   return OK;
  }
  else
  {
   XorNode *temp1,*temp2;
   q=XorP(p->LRPtr,pre);//要删除结点的下一个结点
   temp1=XorP(pre->LRPtr,p);//要删除结点的前前个结点
   temp2=XorP(q->LRPtr,p);//要删除结点的后后一个结点
   free(p);
   pre->LRPtr=XorP(temp1,q);
   q->LRPtr=XorP(temp2,pre);
   return OK;
  }
 }
}

/------主函数------/

#include "common.h"

void main()
{
 XorLinkedList A;
 A.Right=A.Left=NULL;
 XorNode *a=(XorNode *)malloc(sizeof(XorNode));
 a->data='A';
 InsertXorList(A,1,a);
 
 XorNode *b=(XorNode *)malloc(sizeof(XorNode));
 b->data='B';
 InsertXorList(A,1,b);

 XorNode *c=(XorNode *)malloc(sizeof(XorNode));
 c->data='C';
 InsertXorList(A,2,c);
 
 XorNode *d=(XorNode *)malloc(sizeof(XorNode));
 d->data='D';
 InsertXorList(A,5,d);

 XorNode *f=(XorNode *)malloc(sizeof(XorNode));
 f->data='F';
 InsertXorList(A,3,f);

 PrintXorList(A,RIGHT);//从右遍历输出
 printf("\n");
 PrintXorList(A,LEFT);//从左遍历输出
 printf("\n");

 printf("删除第一个节点\n");
 DeleteXorList(A,1);
 PrintXorList(A,LEFT);printf("\n");

 printf("删除第三个结点\n");
 DeleteXorList(A,3);
 PrintXorList(A,LEFT);printf("\n");

 printf("删除第六个结点\n");
 DeleteXorList(A,6);
 PrintXorList(A,LEFT);printf("\n");
 
 printf("删除第三个结点\n");
 DeleteXorList(A,3);
 PrintXorList(A,LEFT);printf("\n");

 printf("删除第一个结点\n");
 DeleteXorList(A,1);
 PrintXorList(A,LEFT);printf("\n");

 printf("删除最后一个结点\n");
 DeleteXorList(A,1);
 PrintXorList(A,LEFT);printf("\n");

}