[数据结构与算法]数据结构：双链表

本题以尾插法从字符串建立字符型双链表并进行反转、插入、删除单个字符为例，讲解双链表的基本操作

#include <iostream>
#include <cassert>
#include <cstring>

using namespace std;

template<class T> struct DNode {
    T data;
    DNode *prior, *nxt;
};

template<class T> void CreateList(DNode<T> *&h, T a[], int n, bool hot) {
    DNode<T> *s,*r;
    h = new DNode<T>;
    if(hot) { // Insert at the head
        h->prior = h->nxt = NULL;
        for(int i = 0; i < n; i++) {
            s = new DNode<T>;
            s->data = a[i];
            s->nxt = h->nxt;
            if(h->nxt != NULL) h->nxt->prior = s;
            h->nxt = s;
            s->prior = h;
        }
    } else { // Insert at tail
        r = h;
        for(int i = 0; i < n; i++) {
            s = new DNode<T>;
            s->data = a[i];
            r->nxt = s;
            s->prior = r;
            r = s;
        }
        r->nxt = NULL;
    }
}

template<class T> void ListInsert(DNode<T> *&h, int pos, T ele) {
    DNode<T> *p = h, *s;
    int i = 0;
    assert(pos > 0);
    while(i < pos - 1 && p != NULL) {
        i++;
        p = p->nxt;
    }
    assert(p != NULL);
    s = new DNode<T>;
    s->data = ele;
    s->nxt = p->nxt;
    if(p->nxt != NULL) p->nxt->prior = s;
    s->prior = p;
    p->nxt = s;
}

template<class T> void ListDel(DNode<T> *&h, int pos) {
    DNode<T> *p = h, *q;
    int i = 0;
    assert(pos > 0);
    while(i < pos - 1 && p != NULL) {
        i++;
        p = p->nxt;
    }
    assert(p != NULL);
    q=p->nxt;
    assert(q != NULL);
    p->nxt = q->nxt;
    if(q->nxt != NULL) q->nxt->prior = p;
    delete q;
}

template<class T> void Reverse(DNode<T> *&h) {
    DNode<T> *p = h->nxt, *q; // p is each element which is ready to insert at the head in order to reverse
    h->nxt = NULL;
    while(p != NULL) {
        q = p->nxt;
        p->nxt = h->nxt;
        if(h->nxt != NULL) h->nxt->prior = p;
        h->nxt = p;
        p->prior = h;
        p = q;
    }
}

template<class T> ostream & operator << (ostream &os, DNode<T> *h) {
    DNode<T> *p = h->nxt;
    while(p != NULL) {
        os << p->data << ' ';
        p = p->nxt;
    }
    return os;
}

int main() {
    char str[50], ch;
    int pos1, pos2;
    DNode<char> *root;
    cout << "Position and char to insert, remove: " << endl;
    cin >> pos1 >> pos2 >> ch;
    cout << "Input a string:" << endl;
    cin >> str;
    CreateList(root, str, strlen(str), false);
    Reverse(root);
    cout << "The reversed result is: " << endl << root << endl;
    ListInsert(root, pos1, ch);
    cout << "Result 1: " << endl << root << endl;
    ListDel(root, pos2);
    cout << "Result 2: " << endl << root << endl;
    return 0;
}