#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*************************************************************************************/
/* 第一版博主 原文地址 http://www.cnblogs.com/renyuan/archive/2013/05/21/3091506.html */
/* 第二版博主 原文地址 http://www.cnblogs.com/wireless-dragon/p/5170565.html */
/* 2.創(chuàng)建線性表，此函數(shù)輸入不為正時終止讀取數(shù)據(jù)*/
/* 3.打印鏈表，鏈表的遍歷 */
/* 4.查詢鏈表結點數(shù)并返回長度 */
/* 5.檢查單鏈表是否為空 */
/* 6.將線性表進行冒泡排序 */
/* 7.查找單鏈表中第n個結點中的元素 */
/* 8.從單鏈表中查找具有給定值number的第一個元素，返回該結點的地址 */
/* 9.把單鏈表中第n個結點的值修改為number的值 */
/* 10.向單鏈表的表頭插入一個元素 */
/* 11.向單鏈表的末尾添加一個元素 */
/* 12.向單鏈表中第n個結點位置插入元素為x的結點 */
/* 13.向有序單鏈表中插入元素x結點，使得插入后仍然有序 */
/* 14.從單鏈表中刪除表頭結點 */
/* 15.從單鏈表中刪除表尾結點 */
/* 16.從單鏈表中刪除第n個結點 */
/* 17.從單鏈表中刪除值為x的第一個結點 */
/* 18.交換2個元素的位置 */
/* 19.刪除列表 */
/*************************************************************************************/
typedef int elemType;
typedef struct NODE
{
  elemType element;
  struct NODE *next;
} Node;
/* 2.創(chuàng)建線性表，此函數(shù)輸入不為正時終止讀取數(shù)據(jù)*/
void creatList(Node **pHead)
{
  printf("Please enter the list:\n");
  Node *p1, *p2;
  p1 = p2 = (Node *)malloc(sizeof(Node));
  if (p1 == NULL || p2 == NULL)
    exit(0);
  memset(p1, 0, sizeof(Node));
  scanf("%d", &p1->element);
  p1->next = NULL;
  while(p1->element > 0)
  {
    if (*pHead == NULL)
      (*pHead) = p1;
    else
      p2->next = p1;
    p2 = p1;
    p1 = (Node *)malloc(sizeof(Node));
    if (p1 == NULL)
      exit(0);
    memset(p1, 0, sizeof(Node));
    scanf("%d", &p1->element);
    p1->next = NULL;
  }
}
/* 3.打印鏈表，鏈表的遍歷 */
void printList(Node *pHead)
{
  if (NULL == pHead)
    printf("The list is empty\n");
  else
    while(NULL != pHead)
    {
      printf("%d ", pHead->element);
      pHead = pHead->next;
    }
  printf("\n");
}
/* 4.查詢鏈表結點數(shù)并返回長度 */
int sizeList(Node *pHead)
{
  int size = 0;
  while(pHead != NULL)
  {
    size ++;
    pHead = pHead->next;
  }
  return size;
}
/* 5. 檢查單鏈表是否為空 */
void isEmptyList(Node *pHead)
{
  if (pHead == NULL)
  {
    printf("The list is empty\n");
    exit(0);
  }
}
/* 7.查找單鏈表中第n個結點中的元素 */
void getElement(Node *pHead, int num)
{
  for (int i = 1; i < num; ++i)
    pHead = pHead->next;
  printf("The value of the %dth element is:%d\n", num, pHead->element);
}
/* 8.從單鏈表中查找具有給定值number的第一個元素，返回該結點的地址 */
int getElemAddr(Node *pHead, int number)
{
  int i = 1;
  while(pHead != NULL)
  {
    if (pHead->element == number)
      return i;
    i++;
    pHead = pHead->next;
  }
  return 0;
}
/* 9.把單鏈表中第n個結點的值修改為number的值 */
void modifyElem(Node **pList, int addr, int number)
{
  Node *pHead; //在此處如果直接更改pList指向的話，主函數(shù)中調(diào)用printList就會從addr處開始打印
  int i = 1;
  pHead = *pList;
  while(pHead != NULL)
  {
    if (i == addr)
      break;
    pHead = pHead->next;
    i++;
  }
  pHead->element = number;
}
/* 10.向單鏈表的表頭插入一個元素 */
void insertHeadList(Node **pHead)
{
  Node *p1;
  p1 = (Node *)malloc(sizeof(Node));
  if (p1 == NULL)
    exit(0);
  memset(p1, 0, sizeof(Node));
  printf("Please enter a number to be inserted:");
  scanf("%d", &p1->element);
  p1->next = (*pHead);// 此時pHead指向的是第一個結點(有數(shù)據(jù)域的)，所以新的結點要插入到頭結點前
  (*pHead) = p1; // pHead指向第一個結點
}
/* 11.向單鏈表的末尾添加一個元素 */
void insertLastList(Node **pHead, int n)
{
  Node *p1, *p2;
  p2 = (*pHead);
  int i;
  for (i = 1; i < n; ++i)
    p2 = p2->next;
  p1 = (Node *)malloc(sizeof(Node));
  if (p1 == NULL)
    exit(0);
  memset(p1, 0, sizeof(Node));
  printf("Please enter a number to be inserted:");
  scanf("%d", &p1->element);
  p1->next = NULL;
  p2->next = p1;
}
/* 12.向單鏈表中第n個結點位置插入元素為x的結點 */
void isAddPos(Node **pHead, int length)
{
  Node *p1, *p2;
  int position, i;
  printf("Please enter the insert position:");
  scanf("%d", &position);
  if (position > length || position <= 0)
  {
    printf("Input error, the program ends\n");
    exit(0);
  }
  p1 = (Node *)malloc(sizeof(Node));
  p2 = (*pHead);
  if (p1 == NULL)
    exit(0);
  memset(p1, 0, sizeof(Node));
  printf("Please enter a number to be inserted:");
  scanf("%d", &p1->element);
  for (i = 1; i < position - 1; ++i)
    p2 = p2->next;
  p1->next = p2->next;
  p2->next = p1;
}
/* 6.將線性表進行冒泡排序 */
void Arrange(Node **pHead, int length)
{
  Node *p1;
  p1 = (*pHead);
  int i, j, temp;
  for (i = length; i > 0; --i)
  {
    for(j = i - 1; j > 0; --j)
    {
      if ((p1->element) > (p1->next->element))
      {
        temp = p1->element;
        p1->element = p1->next->element;
        p1->next->element = temp;
      }
      p1 = p1->next;
    }
    p1 = (*pHead);
  }
}
int OrrderList(Node **pHead, int length)
{
  Node *p1, *p2;
  p1 = (*pHead);
  p2 = (Node *)malloc(sizeof(Node));
  if (p2 == NULL)
    exit(0);
  memset(p2, 0, sizeof(Node));
  printf("Enter the value of the element to be inserted:");
  scanf("%d", &p2->element);
  if (p2->element < p1->element)
  {
    p2->next = p1;
    (*pHead) = p2;
    return 1;
  }
  while(p1->next != NULL && p2->element > (p1->next->element))
    p1 = p1->next;
  if (p1->next == NULL)
  {
    p2->next = NULL;
    p1->next = p2;
    return 1;
  }
  else
  {
    p2->next = p1->next;
    p1->next = p2;
    return 1;
  }
}
/* 14.從單鏈表中刪除表頭結點 */
void DelHeadList(Node **pHead)
{
  Node *p1;
  p1 = (*pHead);
  (*pHead) = (*pHead)->next;
  free(p1);
}
/* 15.從單鏈表中刪除表尾結點 */
void DelLastList(Node **pHead)
{
  Node *p1, *p2;
  p1 = (*pHead);
  p2 = p1->next;
  while(p2->next != NULL)
  {
    p2 = p2->next;
    p1 = p1->next;
  }
  p1->next = NULL;
  free(p2);
}
/* 16.從單鏈表中刪除第n個結點 */
void DelPos(Node **pHead, int length)
{
  int n, i;
  Node *p1, *p2;
  p1 = (*pHead);
  p2 = p1->next;
  printf("Please enter the serial number number to delete:");
  scanf("%d", &n);
  if (n < 1 || n > length)
    exit(0);
  for (i = 1; i < n - 1; ++i)
  {
    p2 = p2->next;
    p1 = p1->next;
  }
  p1->next = p2->next;
  free(p2);
}
/* 17.從單鏈表中刪除值為x的第一個結點 */
int Delx(Node **pHead)
{
  Node *p1, *p2;
  p1 = (*pHead);
  p2 = p1->next;
  int number;
  printf("Please input is going to be deleted the value of x:");
  scanf("%d", &number);
  if (number == (*pHead)->element)
  {
    (*pHead) = (*pHead)->next;
    free(p1);
    return 1;
  }
  while(p2 != NULL)
  {
    if (p2->element == number)
    {
      break;
    }
    p2 = p2->next;
    p1 = p1->next;
  }
  if (p2 == NULL)
  {
    printf("X does not exist in the list\n");
    return 1;
  }
  else
  {
    p1->next = p2->next;
    free(p2);
    return 1;
  }
}
/* 18.交換2個元素的位置 */
void exchange2pos(Node **pHead, int length)
{
  Node *p1, *p2;
  int n1, n2, i, j, temp;
  printf("Please enter the first number:");
  scanf("%d", &n1);
  printf("Please enter the second number:");
  scanf("%d", &n2);
  if (n1 < 1 || n1 > length || n2 < 1 || n2 > length)
    exit(0);
  p1 = p2 = (*pHead);
  for (i = 1; i < n1; ++i)
  {
    p1 = p1->next;
  }
  for (j = 1; j < n2; ++j)
  {
    p2 = p2->next;
  }
  temp = p1->element;
  p1->element = p2->element;
  p2->element = temp;
}
/* 刪除列表 */
void clearList(Node **pHead)
{
  Node *p1;
  p1 = (*pHead);
  while(p1 != NULL)
  {
    p1 = p1->next;
    free((*pHead));
    (*pHead) = p1;
  }
}
int main(int argc, char const *argv[])
{
  /* 1.初始化線性表，即置單鏈表的表頭指針為空 */
  Node *pList = NULL;
  int length = 0, n, addr, number;
  /* 2.創(chuàng)建線性表，此函數(shù)輸入不為正時終止讀取數(shù)據(jù)*/
  printf("- - - - - - - - - 2 - - - - - - - -\n");
  creatList(&pList);
  /* 5. 檢查單鏈表是否為空 */
  isEmptyList(pList);
  printList(pList);
  /* 4.查詢鏈表結點數(shù)并返回長度 */
  printf("- - - - - - - - - 4 - - - - - - - -\n");
  length = sizeList(pList);
  printf("the Node length is:%d\n", length);
  /* 7.查找單鏈表中第n個結點中的元素 */
  printf("- - - - - - - - - 7 - - - - - - - -\n");
  printf("Please input node number (n):");
  scanf("%d", &n);
  if (n > length || n < 1)
  {
    printf("N is not within the scope of\n");
    exit(0);
  }
  getElement(pList, n);
  /* 8.從單鏈表中查找具有給定值number的第一個元素，返回該結點的地址 */
  printf("- - - - - - - - - 8 - - - - - - - -\n");
  addr = 0;
  number;
  printf("Please enter to find element value (number):");
  scanf("%d", &number);
  addr = getElemAddr(pList, number);
  if (addr == 0)
    printf("List the element\n");
  else
    printf("The location of the number is:%d\n", addr);
  /* 9.把單鏈表中第n個結點的值修改為number的值 */
  printf("- - - - - - - - - 9 - - - - - - - -\n");
  addr = 0;
  number = 0;
  printf("Please input to replace the serial number (n):");
  scanf("%d", &addr);
  if (addr > length || addr < 0)
  {
    printf("N is not within the scope of\n");
    exit(0);
  }
  printf("Please input to replace the contents of the (number):");
  scanf("%d", &number);
  modifyElem(&pList, addr, number);
  printf("The revised list is:\n");
  printList(pList);
  /* 10.向單鏈表的表頭插入一個元素 */
  printf("- - - - - - - - - 10 - - - - - - - -\n");
  insertHeadList(&pList);
  printList(pList);
  /* 11.向單鏈表的末尾添加一個元素 */
  printf("- - - - - - - - - 11 - - - - - - - -\n");
  insertLastList(&pList, length);
  printList(pList);
  /* 12.向單鏈表中第n個結點位置插入元素值為x的結點 */
  printf("- - - - - - - - - 12 - - - - - - - -\n");
  isAddPos(&pList, length);
  printList(pList);
  /* 6.將線性表進行冒泡排序 */
  printf("- - - - - - - - - 6 - - - - - - - -\n");
  Arrange(&pList, length);
  printList(pList);
  /* 13.向有序單鏈表中插入元素x結點，使得插入后仍然有序 */
  printf("- - - - - - - - - 13 - - - - - - - -\n");
  OrrderList(&pList, length);
  printList(pList);
  /* 14.從單鏈表中刪除表頭結點 */
  printf("- - - - - - - - - 14 - - - - - - - -\n");
  DelHeadList(&pList);
  printList(pList);
  /* 15.從單鏈表中刪除表尾結點 */
  printf("- - - - - - - - - 15 - - - - - - - -\n");
  DelLastList(&pList);
  printList(pList);
  /* 16.從單鏈表中刪除第n個結點 */
  printf("- - - - - - - - - 16 - - - - - - - -\n");
  DelPos(&pList, length);
  printList(pList);
  /* 17.從單鏈表中刪除值為x的第一個結點 */
  printf("- - - - - - - - - 17 - - - - - - - -\n");
  Delx(&pList);
  printList(pList);
  /* 18.交換2個元素的位置 */
  printf("- - - - - - - - - 18 - - - - - - - -\n");
  exchange2pos(&pList, length);
  printList(pList);
  /* 19.刪除列表 */
  printf("- - - - - - - - - 19 - - - - - - - -\n");
  clearList(&pList);
  printList(pList);
  return 0;
}