数据结构与算法之双链表的操作

/*
实现双链表的构建、初始化、数据添加（在指定位置添加）、数据删除（删除指定元素，并返回该元素的位置）的算法设计；
*/
#include<iostream>
#include<Windows.h>
using namespace std;
typedef struct _DoubleLink {
  int data;
  struct _DoubleLink *pre;  //指向上一节点的指针域
  struct _DoubleLink *next; //指向下一节点的指针域
}DbLinkList, DbLinkNode;
//初始化双链表
bool InitList(DbLinkList* &l) {
  l = new DbLinkList;
  if (!l) return false;
  l->pre = NULL;
  l->next = NULL;
  return true;
}
//前插法添加双向链表元素
bool addLinkFront(DbLinkList* &l, DbLinkNode* s) {
  if (!l || !s) return false;
  if (l->next==NULL) {  //只有头结点
    l->next = s;
    s->pre = l;
    s->next = NULL;
  } else {
    s->next = l->next;
    l->next->pre = s;
    l->next = s;
    s->pre = l;
  }
  return true;
}
//尾插法添加双向链表元素
bool (addLinkLasr(DbLinkList* &l,DbLinkNode* s)) {
  if (!l || !s) return false;
  DbLinkList *last = l;
  while (last->next) last = last->next; //差找到尾结点;
  s->next = NULL;
  last->next = s;
  s->pre = last;
  return true;
}
//打印输出双向链表
void PrintLinkst(DbLinkList* & l) {
  if (!l) return ;
  DbLinkList *p = l;
  while (p->next) {
    cout << p->next->data << " ";
    p = p->next;
  }
  return;
}
//在双向链表中插入指定元素
bool insert(DbLinkList* & l, int i, int x) {
  if (!l) return false;
  DbLinkList *p, *q;
  p = l;
  q = new DbLinkList;
  q->data = x;
  int index = 0;
  while (p->next) {
    if (index < i) {  //找到要插入节点的前一个节点
      index++;
      p = p->next;
    } else {
      p->next->pre = q;
      q->next = p->next;
      p->next = q;
      q->pre = p;
      return true;
    }
  }
  return false;
}
//在双向链表中删除指定元素
bool DeleteList(DbLinkList* &l, int Element, int &index) {
  if (!l||!l->next) return false;
  DbLinkList *p = l;
  while (p->next&&p->next->next) {
    if (p->next->data==Element) {
      p = p->next;
      p->pre->next = p->next;
      p->next->pre = p->pre;
      delete p;
      return true;
    }else{
      p = p->next;
      index++;
    }
  }
  if (p->next->data == Element) {
    p->next = NULL;
    return true;
  }
  return false;
}
int main(void) {
  DbLinkList *l = NULL;
  DbLinkNode *s = NULL;
  if (InitList(l)) {
    cout << "双向链表初始化成功! " << endl;
  } else {
    cout << "双向链表初始化失败! " << endl;
  }
  int chose;  //由用户选择是用前插法还是尾插法插入数据!
  //由用户选择是用前插法还是尾插法
  cout << "请选择使用前插法插入数据还是使用尾插法插入数据!" << endl;
  cout << "若要使用前插法插入数据请输入: 1" << endl;
  cout << "若要使用尾插法插入数据请输入: 2" << endl;
  cin >> chose;
  cout << "请输入要插入的元素个数: " << endl;
  int num = 0;  //用户要插入的元素个数
  cin >> num;
  //由用户选择何种方插入元素
  switch (chose) {
  case 1:
    while (num > 0) {
      cout << "请输入你想要插入的元素的值: ";
      s = new DbLinkNode;
      cin >> s->data;
      //单链表的数据添加 之 前插法
      if (addLinkFront(l, s)) {
        cout << "前插入元素!" << s->data << "成功! " << endl;
      } else {
        cout << "前插入元素失败! " << endl;
      }
      num--;
    }
    break;
  case 2:
    while (num > 0) {
      cout << "请输入你想要插入的元素的值: ";
      s = new DbLinkNode;
      cin >> s->data;
      //单链表的数据添加 之 尾插法
      if (addLinkLasr(l, s)) {
        cout << "尾插入元素!" << s->data << "成功! " << endl;
      } else {
        cout << "尾插入元素失败! " << endl;
      }
      num--;
    }
    break;
  default:
    cout << "输入不合法!!!!, 请重新输入" << endl;
    while (1) {
      cout << "请选择使用前插法插入数据还是使用尾插法插入数据!" << endl;
      cout << "若要使用前插法插入数据请输入: 1" << endl;
      cout << "若要使用尾插法插入数据请输入: 2" << endl;
      cin >> chose;
      if (chose == 1 || chose == 2) 
        break;
    }
    break;
  }
  PrintLinkst(l);
  int i;  //  插入的位置
  int x;//插入的值
  cout << "请输入你想要插入的位置: ";
  cin >> i;
  cout << "请输入你想要插入的元素: ";
  cin >> x;
  //实现双链表的构建、数据添加、数据删除的算法设计；
  if (insert(l, i, x)) {
    cout << "双向链表插入数据 : " << x << "成功,在双向链表的位置是: " << i << endl;
  } else {
    cout << "双向链表插入元素失败! " << endl;
  }
  PrintLinkst(l);
// 实现双链表的构建、数据添加、数据删除的算法设计；
  int Element;  //要删除的元素
  int index = 0;  //要删除的元素的位置
  cout << "请输入要删除的元素的值: ";
  cin >> Element;
  if (DeleteList(l, Element, index)) {
    cout << "双向链表删除数据 : " << Element << "成功,在双向链表的位置是: " << index << endl;
  } else {
    cout << "双向链表删除元素失败! " << endl;
  }
  PrintLinkst(l);
  system("pause");
  return 0;
}