#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

#define ElemType int
#define MAX 15

#define HEAD_NODE
 
typedef enum { OK = 1, ERROR = 0 } Status;
typedef enum { YES = 1, NO = 0 } Bool;

typedef struct Node {
  struct Node *next;
  ElemType value;
} Node;

#ifdef NO_HEAD_NODE
// Status InitList(Node **ppList);
Status DestroyList(Node **ppList);
Bool IsListEmpty(Node **ppList);
unsigned ListLength(Node **ppList);
Status DisplayList(Node **ppList);
Bool GetElem(Node **ppList, int i, ElemType *e);
int LocateElem(Node **ppList, ElemType e);
Status ListInsert(Node **ppList, ElemType value);
Status ListDelete(Node **ppList, ElemType e);

Status DestroyList(Node **ppList) {
  Node *cur = *ppList, *pre = NULL;
  while (cur != NULL) {
    pre = cur;
    cur = cur->next;
    free(pre);
    pre = NULL;
  }
  return OK;
}

/*
Status DestroyList(Node **pList){//递归销毁链表法
    if(*pList!=NULL){
        DestroyList((*pList)->next);
        free(*pList);
    }
    return OK;
}
*/

Bool IsListEmpty(Node **ppList) {
  if (*ppList == NULL) {
    return YES;
  } else {
    return NO;
  }
}

unsigned ListLength(Node **ppList) {
  Node *cur = *ppList;
  unsigned len = 0;
  while (cur != NULL) {
    len++;
    cur = cur->next;
  }
  return len;
}

Status DisplayList(Node **ppList) {
  Node *cur = *ppList;
  while (cur != NULL) {
    cout << cur->value << " ";
    cur = cur->next;
  }

  cout << endl;
  return OK;
}

Bool GetElem(Node **ppList, int i, ElemType *e) {
  Node *cur = *ppList;
  int j = 0;
  if (i <= 0) {
    return NO;
  }
  while (j < i && cur != NULL) {
    j++;
    cur = cur->next;
  }
  if (cur == NULL) {
    return NO;
  } else {
    *e = cur->value;
    return YES;
  }
}

int LocateElem(Node **ppList, ElemType e) {
  Node *cur = *ppList;
  int i = 0;
  while (cur != NULL) {
    i++;
    if (cur->value == e) {
      return i;
    }
    cur = cur->next;
  }
  return 0;
}

Status ListInsert(Node **ppList,
                  ElemType value) { 
  Node *cur, *newNode;

  newNode = (Node *)malloc(sizeof(Node));
  if (newNode == NULL) {
    return ERROR;
  }

  newNode->value = value;

  while (
      cur = *ppList,
      cur != NULL &&
          cur->value <
              value) { 
    ppList = &cur->next;
  }

  *ppList = newNode;
  newNode->next = cur;

  return OK;
}

Status ListDelete(Node **ppList, ElemType e) {
  Node *cur;
  while (cur = *ppList, cur != NULL && cur->value != e) {
    ppList = &cur->next;
  }
  if (cur == NULL) {
    return ERROR;
  } else {
    *ppList = cur->next;
    free(cur);
  }
  return OK;
}

int main(void) {
  Node *LinkedList = NULL;
  int n = MAX;
  ElemType radElem, e;

  srand((unsigned)time(NULL));
  while (n--) {
    radElem = rand() % 101;
    ListInsert(&LinkedList, radElem);
  }

  DisplayList(&LinkedList);

  if (IsListEmpty(&LinkedList)) {
    cout << "The LinkedList is empty" << endl;
  } else {
    unsigned len = ListLength(&LinkedList);
    cout << "The length of LinkedList is " << len << endl;
  }

  if (GetElem(&LinkedList, 20, &e) == YES) {
    cout << "The number in 20th position is " << e << endl;
  } else {
    cout << "The length of LinkedList is shortter than 20" << endl;
  }

  int i = LocateElem(&LinkedList, 20);
  if (i > 0) {
    cout << "The 20 is already exist in the LinkedList and it is in " << i
         << "th position." << endl;
  } else {
    cout << "The 20 isn`t exist in the LinkedList" << endl;
  }

  ListInsert(&LinkedList, 30);
  DisplayList(&LinkedList);

  ListDelete(&LinkedList, 30);
  DisplayList(&LinkedList);

  return 0;
}
#endif

#ifdef HEAD_NODE
Status InitList(Node *&pList);
Status DestroyList(Node *pList);
Bool IsListEmpty(Node *pList);
unsigned ListLength(Node *pList);
Status DisplayList(Node *pList);
Bool GetElem(Node *pList, int i, ElemType *e);
int LocateElem(Node *pList, ElemType e);
Status ListInsert(Node *pList, ElemType value);
Status ListDelete(Node *pList, ElemType e);

Status InitList(Node *&pList){
    pList=(Node *)malloc(sizeof(Node));
    if(pList==NULL){
      return ERROR;
    }
    pList->next = NULL;
    return OK;
}

Status DestroyList(Node *pList) {
  Node *cur = pList, *pre = NULL;
  while (cur != NULL) {
    pre = cur;
    cur = cur->next;
    free(pre);
    pre = NULL;
  }
  return OK;
}

/*
Status DestroyList(Node *pList){//递归销毁链表法
    if(pList!=NULL){
        DestroyList(pList->next);
        free(pList);
    }
    return OK;
}
*/

Bool IsListEmpty(Node *pList) {
  pList = pList->next;
  if (pList == NULL) {
    return YES;
  } else {
    return NO;
  }
}

unsigned ListLength(Node *pList) {
  pList = pList->next;
  Node *cur = pList;
  unsigned len = 0;
  while (cur != NULL) {
    len++;
    cur = cur->next;
  }
  return len;
}

Status DisplayList(Node *pList) {
  pList = pList->next;
  Node *cur = pList;
  while (cur != NULL) {
    cout << cur->value << " ";
    cur = cur->next;
  }

  cout << endl;
  return OK;
}

Bool GetElem(Node *pList, int i, ElemType *e) {
  pList = pList->next;
  Node *cur = pList;
  int j = 0;
  if (i <= 0) {
    return NO;
  }
  while (j < i && cur != NULL) {
    j++;
    cur = cur->next;
  }
  if (cur == NULL) {
    return NO;
  } else {
    *e = cur->value;
    return YES;
  }
}

int LocateElem(Node *pList, ElemType e) {
  pList = pList->next;
  Node *cur = pList;
  int i = 0;
  while (cur != NULL) {
    i++;
    if (cur->value == e) {
      return i;
    }
    cur = cur->next;
  }
  return 0;
}

Status ListInsert(Node *pList,ElemType value) {

  Node *cur,*pre=pList, *newNode;
  pList = pList->next;

  newNode = (Node *)malloc(sizeof(Node));
  if (newNode == NULL) {
    return ERROR;
  }

  newNode->value = value;

  for (cur = pList; cur != NULL && cur->value < value;pre=cur,cur=cur->next)
    ;
  pre->next = newNode;
  newNode->next = cur;

  return OK;
}

Status ListDelete(Node *pList, ElemType e) {
  Node *cur,*pre=pList;
  pList = pList->next;
  for (cur = pList; cur != NULL && cur->value != e;pre=cur,cur=cur->next)
    ;
  if (cur == NULL) {
    return ERROR;
  } else {
    pre = cur->next;
    free(cur);
  }
  return OK;
}

int main(void) {
  Node *LinkedList = NULL;
  InitList(LinkedList);
  int n = MAX;
  ElemType radElem, e;

  srand((unsigned)time(NULL));
  while (n--) {
    radElem = rand() % 101;
    ListInsert(LinkedList, radElem);
  }

  DisplayList(LinkedList);

  if (IsListEmpty(LinkedList)) {
    cout << "The LinkedList is empty" << endl;
  } else {
    unsigned len = ListLength(LinkedList);
    cout << "The length of LinkedList is " << len << endl;
  }

  if (GetElem(LinkedList, 20, &e) == YES) {
    cout << "The number in 20th position is " << e << endl;
  } else {
    cout << "The length of LinkedList is shortter than 20" << endl;
  }

  int i = LocateElem(LinkedList, 20);
  if (i > 0) {
    cout << "The 20 is already exist in the LinkedList and it is in " << i
         << "th position." << endl;
  } else {
    cout << "The 20 isn`t exist in the LinkedList" << endl;
  }

  ListInsert(LinkedList, 30);
  DisplayList(LinkedList);

  ListDelete(LinkedList, 30);
  DisplayList(LinkedList);

  return 0;
}
#endif