数据结构：双向链表1

************************************************************************/

/* 数据结构：双向链表                                                                               */ /* 挑灯看剑[email protected] 2010-10                                                             */ /* 云歌国际（Cloud Singers International） www.cocoral.com                          */ /************************************************************************/   #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include "core.h"   typedef struct NODE {        int data; //数据域        struct NODE* next; //后继结点        struct NODE* prior; //前驱结点 }Node, * NodePointer;   //描述线性链表的头结点 typedef struct {        int len; //记录结点长度        struct NODE* head; //记录第一个结点        struct NODE* tail;//记录最后一个结点 }NodeHead;   void main() {        /***************函数原型【开始】*************************/        void NodeInsert(NodeHead* H, int i, int e);        void NodePrint(NodeHead H, char tag);        void autoList(NodeHead* H, int n);        Status NodeDelete(NodeHead* H, int i, Node* N);        /***************函数原型【结束】*************************/          //初始化线性链表头元        NodeHead H =        {               0, NULL, NULL        };        Node N =        {               0, NULL, NULL        };          int i = 0, j = 0, e = 0;        char tag = 'Y';          NodePrint(H, 'H');        autoList(&H, 10); //自动化链表        NodePrint(H, 'h'); //正向打印测试        NodePrint(H, 't'); //反向打印测试          /*        //动态创建双向链表        puts("请输入插入元素位置和元素值！");        scanf("%d %d %c", &i, &e, &tag);        while (tag == 'Y')        {               NodeInsert(&H, i, e);               NodePrint(H,'H');                  NodePrint(H,'T');               puts("请输入插入元素位置和元素值！");               scanf("%d %d %c", &i, &e, &tag);        }        */          //执行删除操作        for (j = 0; j < 5; j++)        {               puts("请输入要删除结点的位置：");               scanf("%d", &i);               if (NodeDelete(&H, i, &N))               {                      puts("删除成功！");                      if (N.next && N.prior)                      {                             printf("删除当前结点值：%d，其前驱结点值：%d，后继结点值：%d\n",                                    N.data, N.prior->data, N.next->data);                      }                      else                      {                             printf("删除当前结点值：%d\n", N.data);                      }                      NodePrint(H, 'H');                      NodePrint(H, 't');               }        } }     //在线性链表的第i个位置前面插入元素e void NodeInsert(NodeHead* H, int i, int e) {        static       Status NodeIsEmpty(NodeHead H); //函数原型          NodePointer p = NULL, q = NULL;//遍历指针        COUNT j = 0; //计数器          NodePointer s = (NodePointer) malloc(sizeof(Node));//为新结点分配存储空间        s->data = e;        //插入前预检查        if (!NodeIsEmpty(*H)) //如果链表非空        {               if (i == 1) //如果i等于1               {                      p = H->head;//p指向第一个结点，在p的前面插入，只需处理p前面的指针                      p->prior = s; //p的后继结点保持不变                        s->next = p;                      s->prior = NULL;                        H->head = s;                      //+++++++++++链表的尾结点重设指向次尾结点++++++++++                      //查找次尾结点                      for (p = H->head,j = 1; j <= H->len - 2; j++)                             p = p->next;                      //重设尾结点前驱指针                      H->tail->prior = p;                      //+++++++++++++++++++++++++++++++++++++++++++++++++                      H->len += 1; //长度加1                      puts("插入成功！");               }               else if (i >= 2 && i <= H->len) //如果i在2-Len区间               {                      //查找第i-1个结点                      p = H->head;//p指向第一个结点                      //q = H->tail;//q指向最后一个结点                      for (j = 2;                             j <= i - 1;                             j++) //p初始化指向第1个元素，因此循环次数为i-1次                             p = p->next; //p前进一位，直到指向第i-1个结点                      //执行插入操作                      s->next = p->next;                      s->prior = p;                      p->next = s; //在p的后面插入，其前驱指针不变                      H->len += 1;//长度加1                      //-----------处理头元-尾结点-----------------------                      for (p = H->head; p != NULL; p = p->next)                             H->tail = p;                      //-------------------------------------------------                      //+++++++++++链表的尾结点重设指向次尾结点++++++++++                      //查找次尾结点                      for (p = H->head,j = 1; j <= H->len - 2; j++)                             p = p->next;                      //重设尾结点前驱指针                      H->tail->prior = p;                      //+++++++++++++++++++++++++++++++++++++++++++++++++                      puts("插入成功！");                      //NodePrint(*H, 'H');               }               else               {                      printf("当前区间：1-%d，插入位置为：%d\n", H->len, i);                      puts("插入位置越界，默认为链表中的第一个结点！");                      p = H->head;//p指向第一个结点，在p的前面插入，只需处理p前面的指针                      p->prior = s; //p的后继结点保持不变                        s->next = p;                      s->prior = NULL;                        H->head = s; //链表的尾结点保持不变                      H->len += 1; //长度加1                      //-----------处理头元-尾结点-----------------------                      for (p = H->head; p != NULL; p = p->next)                             H->tail = p;                      //-------------------------------------------------                      //+++++++++++链表的尾结点重设指向次尾结点++++++++++                      //查找次尾结点                      for (p = H->head,j = 1; j <= H->len - 2; j++)                             p = p->next;                      //重设尾结点前驱指针                      H->tail->prior = p;                      //+++++++++++++++++++++++++++++++++++++++++++++++++                      puts("插入成功！");               }        }        else        {               printf("插入前链表为空，插入元素 e=%d 默认为第一个结点！\n", s->data);               H->head = H->tail = s; //头指针和尾指针均指向新插入结点               H->len = 1;               s->next = s->prior = NULL; //后继结点和前驱结点均为NULL               puts("插入成功！");        } }   /* * 判断结点是否为空 */ static Status NodeIsEmpty(NodeHead H) {        if (H.len == 0 || H.head == NULL || H.tail == NULL)               return TRUE;        else               return FALSE; }