数据结构与算法之单链表

//链表的实现
/*
 实现单链表的  构建、数据添加、数据删除(返回元素所在位置)、数据查找(返回元素所在的位置)的算法设计；
*/
//链表的实现
/*
 实现单链表的  构建、数据添加、数据删除(返回元素所在位置)、数据查找(返回元素所在的位置)的算法设计；
*/
#include<iostream>
#include<Windows.h>
using namespace std;
typedef struct _LinkList {
  int data; //指针域
  struct _LinkList *next; //指针域
}LinkList, LinkNode;
//初始化链表
bool InitLink(LinkList* &L) {
  L = new LinkList;
  if (!L) return false;
  L->data = -1;
  L->next = NULL;
}
//添加链表元素之前插法
bool addLinkFront(LinkList* & L, LinkNode *node) {
  if (!L || !node) return false;
  node->next = L->next;
  L->next = node;
  return true;
}
//添加链表元素之尾插法
bool addLinkLasr(LinkList* &L, LinkNode * node) {
  if (!L || !node) return false;
  LinkList * last;
  last = L;
  while (last->next) last = last->next; //找到尾结点
  node->next = NULL;
  last->next = node;
  return true;
}
//再顶顶位置插入元素
bool insert(LinkList* & L, int i, int x) {
  if (!L) return false;
  LinkList *p = L;
  LinkList *s=new LinkList;
  s->data = x;
  s->next = NULL;
  int index = 0;
  while (p->next) {
    if (index < i) {  //找到要插入的结点位置的前一个结点
      index++;
      p = p->next;
    } else {
      s->next = p->next;
      p->next = s;
      s->data = x;
      return true;
    } 
  }
  return false;
}
//销毁链表
void Destroy(LinkList * &L) {
  LinkList *p = L;
  cout << "销毁链表..." << endl;
  while (p) {
    L = L->next;
    delete p;
    p = L;
  }
}
//输出链表元素
void PrintList(LinkList* &L) {
  if (!L) return;
  cout << "现在单链表里面的元素依次是: ";
  LinkList *P;
  P = L->next;
  while (P) {
    cout << " " << P->data;
    P = P->next;
  }
  cout << endl;
}
//查找链表元素
bool FindList(LinkList* &L, int Element, int &index) {
  if (!L) return false;
  LinkList *P = L->next;
  while (P) {
    if (P->data == Element) return true;
    P = P->next;
    index++;
  }
  return false;
}
//删除链表元素
bool DeleteList(LinkList* &L, int &Element, int &index) {
  if (!L) return false;
  LinkList *p, *s;
  p = L;
  s = p->next;
  while (s) {
    if (s->data == Element) {
      p->next = s->next;
      delete s;
      return true;
    } else {
      p = p->next;
      s = s->next;
      index++;
    }
  }
  return false;
}
int main(void) {
  LinkList *L;    //链表
  LinkNode *node = NULL;  //要插入的结点
  int chose;  //由用户选择是用前插法还是尾插法插入数据!
  //链表的初始化
  if (InitLink(L)) {
    cout << "链表初始化成功!" << endl;
  } else {
    cout << "链表初始化失败!" << endl;
  }
  //由用户选择是用前插法还是尾插法
  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 << "请输入你想要插入的元素的值: ";
      node = new LinkNode;
      cin >> node->data;
      //单链表的数据添加 之 前插法
      if (addLinkFront(L, node)) {
        cout << "前插入元素!" << node->data << "成功! " << endl;
      } else {
        cout << "前插入元素失败! " << endl;
      }
      num--;
    }
    break;
  case 2:
    while (num > 0) {
      cout << "请输入你想要插入的元素的值: ";
      node = new LinkNode;
      cin >> node->data;
      //单链表的数据添加 之 尾插法
      if (addLinkLasr(L, node)) {
        cout << "尾插入元素!" << node->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;
  }
  //输出用户选择的 前/尾 插入的元素
  PrintList(L);
  int i;  //插入的位置
  int x;  //插入的元素值
  cout << "请输入你想要插入的元素值: ";
  cin >> x;
  cout << "请输入你想要插入元素的位置从0开始: ";
  cin >> i;
  //用户插入数据
  if (insert(L, i, x)) {
    cout << "插入元素 " << x << " 成功! " << "所在的链表的位置是: " << i << endl;
  } else {
    cout << "插入失败! " << endl;
  }
  cout << "插入数据后的链表是: ";
  PrintList(L);
  //数据查找功能
  int Element;
  int index = 0;  //  被查询或被删除的元素所在的位置
  cout << "请输入你要查询的元素: ";
  cin >> Element;
  if (FindList(L, Element, index)) {
    cout << "成功查找到该元素! " << endl;
    cout << endl;
    cout << "该元素在链表中的位置是: " << index << endl;
  } else {
    cout << "链表里面没有该元素! " << endl;
  }
  PrintList(L);
  cout << "请输入你要删除的元素: ";
  cin >> Element;
  //数据删除
  index = 0;  //  将索引置为0
  if (DeleteList(L, Element, index)) {
    cout << endl;
    cout << "该元素在链表中的位置是: " << index << endl;
    cout << "在链表中删除" << Element << "元素成功! " << endl;
  } else {
    cout << "链表内没有" << Element << "删除失败!" << endl;
  }
  PrintList(L);
  Destroy(L);
  cout << "现在的链表元素是: " << endl;
  PrintList(L);
  system("pause");
  return 0;
}