C语言 数据结构链表的实例（十九种操作）

#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.创建线性表，此函数输入不为正时终止读取数据*//* 3.打印链表，链表的遍历 *//* 4.查询链表结点数并返回长度 *//* 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.创建线性表，此函数输入不为正时终止读取数据*/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.查询链表结点数并返回长度 */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指向的话，主函数中调用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指向的是第一个结点(有数据域的)，所以新的结点要插入到头结点前  (*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.创建线性表，此函数输入不为正时终止读取数据*/  printf("- - - - - - - - - 2 - - - - - - - -/n");  creatList(&pList);  /* 5. 检查单链表是否为空 */  isEmptyList(pList);  printList(pList);  /* 4.查询链表结点数并返回长度 */  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;}