#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í)終止讀取數(shù)據(jù)*//* 3.打印鏈表，鏈表的遍歷 *//* 4.查詢鏈表結(jié)點(diǎn)數(shù)并返回長(zhǎng)度 *//* 5.檢查單鏈表是否為空 *//* 6.將線性表進(jìn)行冒泡排序 *//* 7.查找單鏈表中第n個(gè)結(jié)點(diǎn)中的元素 *//* 8.從單鏈表中查找具有給定值number的第一個(gè)元素，返回該結(jié)點(diǎn)的地址 *//* 9.把單鏈表中第n個(gè)結(jié)點(diǎn)的值修改為number的值 *//* 10.向單鏈表的表頭插入一個(gè)元素 *//* 11.向單鏈表的末尾添加一個(gè)元素 *//* 12.向單鏈表中第n個(gè)結(jié)點(diǎn)位置插入元素為x的結(jié)點(diǎn) *//* 13.向有序單鏈表中插入元素x結(jié)點(diǎn)，使得插入后仍然有序 *//* 14.從單鏈表中刪除表頭結(jié)點(diǎn) *//* 15.從單鏈表中刪除表尾結(jié)點(diǎn) *//* 16.從單鏈表中刪除第n個(gè)結(jié)點(diǎn) *//* 17.從單鏈表中刪除值為x的第一個(gè)結(jié)點(diǎn) *//* 18.交換2個(gè)元素的位置 *//* 19.刪除列表 *//*************************************************************************************/typedef int elemType;typedef struct NODE{  elemType element;  struct NODE *next;} Node;/* 2.創(chuàng)建線性表，此函數(shù)輸入不為正時(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.查詢鏈表結(jié)點(diǎn)數(shù)并返回長(zhǎng)度 */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個(gè)結(jié)點(diǎ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的第一個(gè)元素，返回該結(jié)點(diǎn)的地址 */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個(gè)結(jié)點(diǎn)的值修改為number的值 */void modifyElem(Node **pList, int addr, int number){  Node *pHead; //在此處如果直接更改pList指向的話，主函數(shù)中調(diào)用printList就會(huì)從addr處開(kāi)始打印  int i = 1;  pHead = *pList;  while(pHead != NULL)  {    if (i == addr)      break;    pHead = pHead->next;    i++;  }  pHead->element = number;}/* 10.向單鏈表的表頭插入一個(gè)元素 */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);// 此時(shí)pHead指向的是第一個(gè)結(jié)點(diǎn)(有數(shù)據(jù)域的)，所以新的結(jié)點(diǎn)要插入到頭結(jié)點(diǎn)前  (*pHead) = p1; // pHead指向第一個(gè)結(jié)點(diǎn)}/* 11.向單鏈表的末尾添加一個(gè)元素 */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個(gè)結(jié)點(diǎn)位置插入元素為x的結(jié)點(diǎn) */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.將線性表進(jìn)行冒泡排序 */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.從單鏈表中刪除表頭結(jié)點(diǎn) */void DelHeadList(Node **pHead){  Node *p1;  p1 = (*pHead);  (*pHead) = (*pHead)->next;  free(p1);}/* 15.從單鏈表中刪除表尾結(jié)點(diǎn) */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個(gè)結(jié)點(diǎ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的第一個(gè)結(jié)點(diǎn) */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個(gè)元素的位置 */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í)終止讀取數(shù)據(jù)*/  printf("- - - - - - - - - 2 - - - - - - - -/n");  creatList(&pList);  /* 5. 檢查單鏈表是否為空 */  isEmptyList(pList);  printList(pList);  /* 4.查詢鏈表結(jié)點(diǎn)數(shù)并返回長(zhǎng)度 */  printf("- - - - - - - - - 4 - - - - - - - -/n");  length = sizeList(pList);  printf("the Node length is:%d/n", length);  /* 7.查找單鏈表中第n個(gè)結(jié)點(diǎ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的第一個(gè)元素，返回該結(jié)點(diǎn)的地址 */  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個(gè)結(jié)點(diǎ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.向單鏈表的表頭插入一個(gè)元素 */  printf("- - - - - - - - - 10 - - - - - - - -/n");  insertHeadList(&pList);  printList(pList);  /* 11.向單鏈表的末尾添加一個(gè)元素 */  printf("- - - - - - - - - 11 - - - - - - - -/n");  insertLastList(&pList, length);  printList(pList);  /* 12.向單鏈表中第n個(gè)結(jié)點(diǎn)位置插入元素值為x的結(jié)點(diǎn) */  printf("- - - - - - - - - 12 - - - - - - - -/n");  isAddPos(&pList, length);  printList(pList);  /* 6.將線性表進(jìn)行冒泡排序 */  printf("- - - - - - - - - 6 - - - - - - - -/n");  Arrange(&pList, length);  printList(pList);  /* 13.向有序單鏈表中插入元素x結(jié)點(diǎn)，使得插入后仍然有序 */  printf("- - - - - - - - - 13 - - - - - - - -/n");  OrrderList(&pList, length);  printList(pList);  /* 14.從單鏈表中刪除表頭結(jié)點(diǎn) */  printf("- - - - - - - - - 14 - - - - - - - -/n");  DelHeadList(&pList);  printList(pList);  /* 15.從單鏈表中刪除表尾結(jié)點(diǎn) */  printf("- - - - - - - - - 15 - - - - - - - -/n");  DelLastList(&pList);  printList(pList);  /* 16.從單鏈表中刪除第n個(gè)結(jié)點(diǎn) */  printf("- - - - - - - - - 16 - - - - - - - -/n");  DelPos(&pList, length);  printList(pList);  /* 17.從單鏈表中刪除值為x的第一個(gè)結(jié)點(diǎn) */  printf("- - - - - - - - - 17 - - - - - - - -/n");  Delx(&pList);  printList(pList);  /* 18.交換2個(gè)元素的位置 */  printf("- - - - - - - - - 18 - - - - - - - -/n");  exchange2pos(&pList, length);  printList(pList);  /* 19.刪除列表 */  printf("- - - - - - - - - 19 - - - - - - - -/n");  clearList(&pList);  printList(pList);  return 0;}