1 #include "iostream"  2 #include "stdlib.h"  3   4 /*宏函数*/  5 #define log(data) std::cout<<data<<std::endl  6   7 #define isNull(ptr);  8 {  9     if(ptr==nullptr){ 10         log("链表为空"); 11         return; } 12 } 13  14 typedef struct _node_ 15 { 16     int data; 17     struct _node_ *pre; 18     struct _node_ *next; 19 }node; 20  21 /*在尾部加入新节点*/ 22 void addToTail(node *&head,node *&tail, int data) 23 { 24     node *p = (node *)malloc(sizeof(node)); 25     p->data =http://www.mamicode.com/ data; 26     p->pre = nullptr; 27     p->next= nullptr; 28     if (tail == nullptr) 29     { 30         head = p; 31         tail = p; 32     } 33     else 34     { 35         p->pre = tail; 36         tail->next = p; 37         tail = p; 38     } 39 } 40  41 /*指定位置插入*/ 42 void insertByIndex(node *&head, node *&tail, int index, int data) 43 { 44     node *tmp,*bak = head;/*备份头部*/ 45  46     int num = 1; 47  48     node *p = (node *)malloc(sizeof(node)); 49     p->data =http://www.mamicode.com/ data; 50     p->pre = nullptr; 51     p->next = nullptr; 52  53     if (head == nullptr) 54     { 55         if (index == 1) 56         { 57             head = tail = p; 58         } 59         else 60         { 61             free(p); 62             std::cout << "链表为空，仅支持从索引 1 处插入数据" << std::endl; 63         } 64         return; 65     } 66  67     while (head != tail && index != num) 68     { 69         head = head->next; 70         ++num; 71     } 72  73     if (index != num) 74     { 75         std::cout << "索引越界" << std::endl; 76         free(p); 77         head = bak; 78         return; 79     } 80  81     p->pre = head->pre; 82     p->next = head; 83     head->pre->next = p; 84     head->pre = p; 85  86     head = bak; 87 } 88  89 /*前序遍历*/ 90 void forDisplay(node *head,node *tail) 91 { 92     isNull(head); 93     while (head != tail) 94     {  95         std::cout << head->data << std::endl; 96         head=head->next; 97     } 98     std::cout << head->data << std::endl; 99     std::cout << "==END==" << std::endl;100 }101 102 /*倒序遍历*/103 void backDisplay(node *head, node *tail)104 {105     isNull(head);106     while (tail!=head)107     {108         std::cout << tail->data << std::endl;109         tail = tail->pre;110     }111     std::cout << tail->data << std::endl;112     std::cout << "==END==" << std::endl;113 }114 115 /*删除第一个匹配的节点*/116 void deleteData(node *&head, node *&tail,int data)117 {118     isNull(head);119     node *tmp, *bak = head;120     if (head->data =http://www.mamicode.com/= data)121     {122         tmp = head;123         head = head->next;124         free(tmp);125         return;126     }127     head = head->next;128     while (head != tail && head->data!=data)129     {130         head = head->next;131     }132 133     if (head->next==nullptr)134     {135         tmp = tail;136         tail = tail->pre;137         tail->next = nullptr;138         free(tmp);139     }140     else141     {142         head->pre->next = head->next;143         head->next->pre = head->pre;144         free(head);145     }146     head = bak;147 }148 149 /*删除指定位置的节点*/150 void deleteByIndex(node *&head, node *&tail, int index)151 {152     isNull(head);153     node *tmp, *bak = head;154     int num = 2;155     if (index == 1)156     {157         tmp = head;158         head = head->next;159         free(tmp);160         return;161     }162     head = head->next;163     while (head != tail && index != num)164     {165         ++num;166         head = head->next;167     }168 169     if (index != num)170     {171         std::cout << "索引越界，最大应为"<< num << std::endl;172         head = bak;173         return;174     }175 176     if (head->next == nullptr)177     {178         tail = tail->pre;179         tail->next = nullptr;180         free(head);181         head = bak;182         return;183     }184 185     head->pre->next = head->next;186     head->next->pre = head->pre;187     free(head);188     head = bak;189 }190 191 int main(void)192 {193     node *head=nullptr;194     node *tail = nullptr;195 196     addToTail(head, tail, 1);197     addToTail(head, tail, 2);198     addToTail(head, tail, 3);199     addToTail(head, tail, 4);200     addToTail(head, tail, 5);201 202     insertByIndex(head, tail, 2, 123);203     forDisplay(head, tail);204 205     deleteByIndex(head, tail, 3);206     forDisplay(head, tail);207     system("pause");208     return 0;209 }