线性表--顺序表--双向链表(六)

typedef struct Node
{
 int data;
 struct Node * prior;
 struct Node * next;
}Node;

Node * InitListHead()
{
 Node * Head = (Node *)malloc(sizeof(Node));
 Head->data = 0;
 Head->next = NULL;
 Head->prior = NULL;
 return Head;
}
Node * InitListEnd()
{
 Node * End = (Node *)malloc(sizeof(Node));
 End->data = 0;
 End->next = NULL;
 End->prior = NULL;
 return End;
}

void CreateCLinkList(Node ** Head,Node ** End,int a)//创建节点
{
 //尾插法 
 Node * P = (Node *)malloc(sizeof(Node));
 P->data = a;
 if ((*Head)->next == NULL)
 {
  (*Head)->next = P;
  P->prior = (*Head);
 }
 else
 {
  (*End)->prior->next = P;
  P->prior = (*End)->prior;
 }
 P->next = (*End);
 (*End)->prior = P;
 (*Head)->data++;
}

int InsertList(Node ** Head, Node ** End,int i,int num)//i为插入位置
{
 //我们可以在头结点的数据存储链表长度，来判断插入位置是否合法，这里假定输入的i合法
 //因为有首尾链表，我们可还以判断输入位置在前半部分，还是后半部分，从而选择使用头节点还是尾节点,这里就不做示范了
 j = 0;
 Node *Phead = (*Head);
 Node *Pend = (*End);
 Node * P = (Node *)malloc(sizeof(Node));
 P->data = num;
 if (i > (*Head)->data)
  return 0;
 //正向操作
 //while (Phead != NULL)
 //{
 // if (i == j+1)
 // {
 //  Phead->next->prior = P;
 //  P->next = Phead->next;
 //  Phead->next = P;
 //  P->prior = Phead;
 //  (*Head)->data++;
 // }
 // Phead = Phead->next;
 // j++;
 //}
 //这不是我们今天的重点 今天的重点是 双向链表的逆向操作：
  while (Pend->prior != NULL)
 {
  if (Phead->data - i == j)
  {
   P->prior = Pend->prior;
   Pend->prior->next = P;
   P->next = Pend;
   Pend->prior = P;
   (*Head)->data++;
   return 0;
  }
  Pend = Pend->prior;
  j++;
 }
 return 0;
}

void printList(Node * Head, Node * End)
{
 //双向链表的遍历条件是头指针是否等于尾节点，或者是指针是否为空
 Node * Phead = Head->next;
 Node * Pend = End->prior;

 //正向操作
 //while (Phead->next != NULL)
 //{
 // printf("第一种 %d\n", Phead->data);
 // Phead = Phead->next;
 //}
 //printf("\n");
 //Node * Phead_1 = Head->next;
 //while (Phead_1 != Pend)
 //{
 // printf("第二种 %d\n", Phead_1->data);
 // Phead_1 = Phead_1->next;
 //}
 //同样这也是正向操作，下面来看逆向操作
  while (Pend->prior != NULL)
 {
  printf("第一种 %d\n", Pend->data);
  Pend = Pend->prior;
 }
 printf("\n");
}

int DelList(Node ** Head, Node ** End, int i)
{
 j = 0;
 Node *Phead = (*Head);
 Node *Pend = (*End);
 Node * P = NULL;
 if (i > (*Head)->data)
  return 0;

 //正向操作
 //while (Phead->next != NULL)
 //{
 // if (i == j + 1)
 // {
 //  P = Phead->next;
 //  Phead->next = Phead->next->next;
 //  Phead->next->prior = Phead;
 //  P->next = NULL;
 //  P->prior = NULL;
 //  free(P);
 //  (*Head)->data--;
 // }
 // Phead = Phead->next;
 // j++;
 //}
 //同样，我们来看逆向操作：
  while (Pend->prior != NULL)
 {
  if (Phead->data - i == j+1 )
  {
   P = Pend->prior;
   Pend->prior->next = Pend;
   Pend->prior = Pend->prior->prior;
   P->next = NULL;
   P->prior = NULL;
   free(P);
   (*Head)->data--;
  }
  Pend = Pend->prior;
  j++;
 }
 return 0;
}

int main()
{
int j=0;
 Node * Head = InitListHead();
 Node * End = InitListEnd();
 Node ** PH = &Head;
 Node ** PE = &End;
 for (int i = 1; i <= 10; i++)
 {
  CreateCLinkList(PH, PE, i);
 }
 printList(Head, End);
 InsertList(PH, PE, 3, 99);
 printList(Head, End);
 DelList(PH, PE, 3);
 printList(Head, End);
 return 0;
}