[数据结构]单链表及其基本操作

/*
 * @Author: 
 * @data: 2019-12-02 14:49:03
 * @Last Modified by: 
 * @Last Modified time: 2019-12-02 15:54:49
 */

#include <iostream>
#include <cstdio>

using namespace std;

typedef int Status;
typedef int Elem;

typedef struct LNode
{
  /* data */
  Elem data;
  struct LNode *next; //想起 (数据结构是递归的 LNode 结点 由 data  next 组成，而next本身是一种指向LNode 的指针 即LNode定义中调用了自身， 所以连表示一种递归的数据结构 这句台词在栈里 你说操蛋不操蛋
} LNode, *LinkList; //理解成 LNode头 *LinkList 除了头以外的？ 大概

//初始化
Status InitList(LinkList &L)
{
  L = new LNode; //申请一手内存 指向一片空空如也
  L->next = NULL;
  return 1;
}

//取值
Status GetElemList(LinkList &L, int i, Elem &e) //提一提这个e 很蛋疼 说老实话我不明白为什么要返回它出来看看你丢了啥
{
  LNode *p = L->next; //你好 头节点
  int j = 1;

  while (p && j < i)
  {
    p = p->next; //常规遍历
    ++j;
  }
  if (!p || j > i)
    return -1;
  e = p->data;
  return 1;
}

//插入
Status InsertList(LinkList &L, int i, Elem e)
{
  LNode *p = L;
  int j = 0;

  while (p && j < i - 1)
  {
    p = p->next;
    j++;
  }
  if (!p || j > i - 1)
    return -1;

  LNode *s = new LNode;
  s->data = e;
  s->next = p->next; //指向头节点指向的 看视频比较好理解
  p->next = s; //头节点又指向这个新的

  return 1;
}

//长度
Status LenList(LinkList &L, Elem &e)
{
  LNode *p = L->next;
  int j = 0;

  while (p)
  {
    p = p->next;
    ++j;
  }

  if (p)
    return -1;

  e = j; //有一说一 遍历计数

  return 1;
}

//删除
Status DelList(LinkList &L, int i)
{
  LNode *p = L->next;
  int j = 0;

  while ((p->next) && (j < i - 1))
  {
    p = p->next;
    ++j;
  }

  if (!p->next || j > i - 1)
    return -1;

  LNode *q = p->next;
  p->next = q->next;
  delete q;//其实这里 q才是目标 因为之前循环都只到i-1  P直接指向下下个 删了Q Q太难了

  return 1;
}

//排序
Status SortList(LinkList &L)
{
  LNode *p = L->next;
  LNode *TmpNode;
  int tmp = 0;

  while (p)
  {
    TmpNode = p;
    while (TmpNode) //有一说一 我正常冒泡不知道为什么挂球了 
    {
      if (p->data > TmpNode->data)
      {
        tmp = p->data;
        p->data = TmpNode->data;
        TmpNode->data = tmp;
      }
      TmpNode = TmpNode->next;
    }
    p = p->next;
  }

  return 1;
}

//遍历
Status ShowList(LinkList &L)
{
  LNode *p = L->next;
  while (p)
  {
    cout << p->data << " ";
    p = p->next; //直接遍历
  }

  return 1;
}

//头插
Status CreatList_H(LinkList &L, int num)
{
  L = new LNode;
  L->next = NULL;

  for (int i = 0; i < num; i++)
  {
    LNode *p = new LNode;
    cin >> p->data;

    p->next = L->next; //上面我写了
    L->next = p;
  }

  return 1;
}

//尾插
Status CreatList_L(LinkList &L, int num)
{
  L = new LNode;
  L->next = NULL;
  LNode *r = L;

  for (int i = 0; i < num; i++)
  {
    LNode *p = new LNode;
    cin >> p->data;

    p->next = NULL;
    r->next = p;
    r = p;//重点就是这个啊 r指向了P 一直走下去
  }

  return 1;
}

int main()
{
  LinkList L;

  //1
  InitList(L);
  //1
  int num;
  cin >> num;
  //CreatList_H(L, num);

  //1
  CreatList_L(L, num);
  //1
  //cout << InsertList(L, 1, 1);

  //1
  int e;
  GetElemList(L, 1, e);
  cout << "Elem 1 " << e << " ";

  //1
  int len;
  LenList(L, len);
  cout << "len:" << len << " ";

  //1
  int len2;
  //DelList(L, 1);
  //LenList(L, len2);
  //cout << "AfterDellen " << len2<<" ";

  //1
  SortList(L);

  //cout<<L->next->data;
  //1
  ShowList(L);
}