C语言单链表-19个功能函数

论坛 › 期权论坛 › 编程之家     
选择匿名的用户   2021-5-22 19:39   32   0

线性表链接存储（单链表）操作

刚开始学习数据结构，找点题目练手，题目和部分源码参考 http://www.cnblogs.com/lifuqing/archive/2011/08/20/list.html

注意问题：

1. 采用vs2012开发，由于vs不支持C99标准，因此申明变量必须位于运算语句之前

2. 链表没有设置头结点（第一个结点包含元素值）

3. 对链表指针的编写有些混乱（如有的 Node* L, 有的用Node** ），注意区分

4. 链表的排序没能编写成功，（后续应多联系链表，并着重学习一下排序）

/************************************************************************/
/*             以下是关于线性表链接存储（单链表）操作的18种算法        */
 
/* 1.初始化线性表，即置单链表的表头指针为空 */
/* 2.创建线性表，此函数输入负数终止读取数据*/
/* 3.打印链表，链表的遍历*/
/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
/* 5.返回单链表的长度 */
/* 6.检查单链表是否为空，若为空则返回１，否则返回０ */
/* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
/* 8.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
/* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
/* 10.向单链表的表头插入一个元素 */
/* 11.向单链表的末尾添加一个元素 */
/* 12.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */
/* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */
/* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */
/* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */
/* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */
/* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
/* 18.交换2个元素的位置 */
/* 19.将线性表进行快速排序 */


list_link.h 
#ifndef LINK_LIST_H
#define LINK_LIST_H
#include<stdlib.h>
#include <string.h>
#include <stdio.h>
typedef int elemType;
typedef struct Node
    {
     elemType element;
      struct Node *next;
    } Node;

void init_list(Node *L);
Node * creat_list();
int print_list(Node *L);
Node * clear_list(Node *L);
int length_list(Node *L);
int isEmpty_list(Node *L);
elemType get_pos_element(Node *L, int pos);
Node* get_pos_prev_address(Node *L, int pos);
Node *get_element_position(Node* L, elemType x);
Node *get_element_prev_position(Node* L, elemType x);
int modify_element(Node* L, int pos, elemType x);
void insert_head_node(Node **L, elemType x);
void insert_end_node(Node **L, elemType x);
int insert_pos_list(Node **L, int pos, elemType x);
int insert_element_to_sorted_list(Node **L, elemType x);
elemType delete_head_node(Node **L);
elemType delete_end_node(Node **L);
elemType delete_pos_node(Node **L, int pos);
int delete_element_node(Node **L, elemType x);
void swap_element_position(Node**L, elemType x, elemType y);
int sort_list(Node **L);
#endif // LINK_LIST_H

link_list.c 
#include "link_list.h"
/* 1.初始化线性表，即置单链表的表头指针为空 */
void init_list(Node * L)
{
 L = NULL;
 printf("初始化链表成功！\n");

}

/* 2.创建线性表，此函数输入负数终止读取数据*/
Node * creat_list()
{
 Node * L = NULL;
 Node *p1, *p2;
 p1 = ( Node *)malloc(sizeof(struct Node));
 p2 = ( Node *)malloc(sizeof(struct Node));
 if(p1 == NULL || p2 == NULL)
 {
  printf("内存分配失败！\n");
  exit(0);
  system("pause");
 }
 memset(p1, 0, sizeof(struct  Node));
 printf("请输入链表元素的值：");
 scanf("%d",&(p1->element));
 p1->next = NULL;
 //while(p1->element > 0)
 while(p1->element > 0)
 {
  if( L == NULL)
  {
   L = p1;
  }
  else
  {
   p2->next = p1;
  }

  p2 = p1;

  p1 = ( Node *)malloc(sizeof(struct Node));
  if(p1 == NULL || p2 == NULL)
  {
   printf("内存分配失败！\n");
   exit(0);
   system("pause");
  }
  memset(p1, 0, sizeof(struct  Node));
  printf("请输入链表元素的值：");
  scanf("%d",&(p1->element));
  p1->next = NULL;
 }
 printf("创建链表成功！\n");
 return L;

}

/* 3.打印链表，链表的遍历*/
int print_list(Node * L)
{
 Node *p = L;
 if (NULL == p)
 {
  printf("print_list:链表为空!\n");
  return 0;
 }
 printf("打印链表如下：\n ");
 while (p != NULL)
 {
  printf("%d, ",p->element);
  p = p->next;
 }
 printf("\n");
 return 0;
}

/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
Node* clear_list(Node *L)
{
 Node *p = L;
 Node *temp = NULL;
 printf("clear_list运行成功！\n");
 if (p == NULL)
 {
  printf("链表为空，不需清空\n");
  exit(0);
 }
 while (p != NULL)
 {
  temp = p->next;
  free(p);
  p = temp;
 }
 L =NULL;
 printf("已清空链表！\n");
 return L;
}

/* 5.返回单链表的长度 */
int length_list(Node *L)
{
 int count = 0;
 printf("length_list运行成功！\n");
 if (L == NULL)
 {
  printf("链表为空,长度为0\n");
  return 0;
 }
 while( L != NULL)
 {
  ++count;
  L = L->next;
 }
 return count;
}

/* 6.检查单链表是否为空，若为空则返回１，否则返回０ */
int isEmpty_list(Node *L)
{
 printf("isEmpty_list运行成功！\n");
 if (L == NULL)
 {
  printf("链表为空！\n");
  return 1;
 }
 else
 {
  printf("链表非空！\n");
  return 0;
 }
}

/* 7.1 返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
elemType get_pos_element( Node *L, int pos )
{
 int i = 1;
 if (L == NULL)
 {
  printf("get_pos_element()运行成功，链表为空, 获取元素失败！\n");
  system("pause");
  exit(0);
 }
 if (pos < 1)
 {
  printf("get_pos_element()运行成功，给定节点数非法！\n");
  system("pause");
  exit(0);
 }
 while(L != NULL)
 {
  if ( i == pos)
  {
   printf("get_pos_element()运行成功，第%d个节点元素为%d！\n", pos, L->element);
   return L->element;
  }
  L = L->next;
  ++i;
 }
 printf("get_pos_element()运行成功，超出查找范围！\n");
 system("pause");
 exit(0);
}
/* 7.2 返回单链表中第pos个结点的前一个地址，方便在pos位置上插入元素，若pos超出范围，则停止程序运行 */
Node* get_pos_prev_address(Node *L, int pos)
{
 Node *prev = NULL;
 int i = 1;
 if (L == NULL)
 {
  printf("get_pos_address()运行成功，链表为空, 获取元素失败！\n");
  system("pause");
  return NULL;
 }
 if (pos < 1)
 {
  printf("get_pos_address()运行成功，给定节点数非法, 获取元素失败！\n");
  system("pause");
  return NULL;
 }
 while(L != NULL)
 {
  if ( i == pos)
  {
   printf("get_pos_address()运行成功，第%d个节点元素前一结点的地址为0x%x！\n", pos, L);
   //return L;  //若返回L，则方便在pos的后一个位置插入元素
   return prev; //返回pos的前一个地址，方便在pos位置上插入元素
  }
  prev = L;
  L = L->next;
  ++i;
 }
 printf("get_pos_address()运行成功，超出查找范围！\n");
 system("pause");
 return NULL;
}

/* 8.1 从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
Node * get_element_position( Node* L, elemType x )
{
 if (L == NULL)
 {
  printf("get_element_position运行成功，链表为空, 获取元素失败！\n");
  system("pause");
  exit(0);
 }
 while (L != NULL)
 {
  if ( L->element == x)
  {
   printf("get_element_position运行成功，该链表中元素%d的地址为0x%x\n", x, L);
   return L;
  }
  L = L->next;
 }
 printf("get_element_position运行成功，该链表不含有元素%d\n",x);
 return NULL;
}

/* 8.2 从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点前一结点data域的存储地址，否则返回NULL */
Node * get_element_prev_position( Node* L, elemType x ) //和8.2程序只有返回值的不同
{
 Node *prev = NULL;
 if (L == NULL)
 {
  printf("get_element_prev_position运行成功，链表为空, 获取元素失败！\n");
  system("pause");
  exit(0);
 }
 while (L != NULL)
 {
  if ( L->element == x)
  {
   printf("get_element_prev_position运行成功，该链表中元素%d前一结点的地址为0x%x\n", x, L);
   return prev;
  }
  prev = L;
  L = L->next;
 }
 printf("get_element_prev_position运行成功，该链表不含有元素%d\n",x);
 return NULL;
}

/* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
int modify_element(Node* L, int pos, elemType x)
{
 int i = 1;
 if (L == NULL)
 {
  printf("modify_element函数运行成功，链表为空, 修改失败！\n");
  system("pause");
  return 0;
 }
 if (pos < 1)
 {
  printf("modify_element函数运行成功，给定节点非法！\n");
  system("pause");
  return 0;
 }
 while(L != NULL)
 {
  if ( i == pos)
  {
   L->element = x;
   printf("modify_element函数运行成功，已更换第%d个节点为 %d！\n", pos, x);
   return 1;
  }
  L = L->next;
  ++i;
 }
 printf("modify_element函数运行成功，超出查找范围！\n");
 system("pause");
 return 0;
}

/* 10.向单链表的表头插入一个元素 */
void insert_head_node( Node **L, elemType x )
{
 Node *insert_node;
 insert_node = (Node*)malloc(sizeof(Node));
 insert_node->element = x;
 insert_node->next = *L;
 *L = insert_node;
 printf("insert_head_list运行成功,向表头添加元素%d！\n", x);
}
/* 11.向单链表的末尾添加一个元素 */
void insert_end_node(Node **L, elemType x)
{
 Node *insert_node, *last = NULL;
 Node *p = (*L);
 insert_node = (Node*)malloc(sizeof(Node));

 while (p != NULL)
 {
  last = p;
  p = p->next;
 }
 last->next = insert_node;
 insert_node->element = x;
 insert_node->next = NULL;
 printf("insert_end_list运行成功,向末尾添加元素%d！\n", x);
}
/* 12.向单链表中第pos个结点位置插入元素为x的结点，成功返回1， 失败返回0 */
int insert_pos_list(Node **L, int pos, elemType x)
{
 Node *insert_node = (Node *)malloc(sizeof(Node));
 Node *pos_node = get_pos_prev_address(*L, pos);
 if (pos_node == NULL)
 {
  printf("insert_pos_list已运行，但向第%d个节点处添加元素%d时失败，请查看上述提示\n",pos, x);
  return 0;
 }

 insert_node->element = x;
 insert_node->next = pos_node->next;
 pos_node->next = insert_node;

 printf("insert_pos_list运行,向第%d个节点处添加元素%d 成功！\n", pos, x);
 return 1;
}

/* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */
int insert_element_to_sorted_list(Node **L, elemType x)
{
 int sort_type = 0; //升序排列为1，降序为0
 int ret = 1; //标志位，判断是否为异常情况
 elemType first;
 Node *p = *L;
 Node *left = NULL, *right = NULL, *temp = NULL;
 Node *insert_node = (Node *)malloc(sizeof(Node));
 insert_node->element = x;
 if (p == NULL)
 {
  printf("insert_element_to_sorted_list运行，链表为空，插入失败\n");
  return 0;
 }
 if ( p->next == NULL) //只有一个元素时
 {
  printf("insert_element_to_sorted_list运行，链表只有一个元素，插入成功\n");
  insert_head_node(L, x);
  return 1;
 }

 first = p->element;
 if (p->element >= p->next->element) //根据1st >= 2nd 降序
 {
  sort_type = 1;
 }

 //降序时x>=max, 升序时x <= min 应该将x插入表头
 if (sort_type && (x >= first))
 {
  insert_head_node(L, x);
  ret = 0; //标志位置0，跳过while
 }
 if ( (!sort_type) &&  x <= first)
 {
  insert_head_node(L, x);
  ret = 0; //标志位置0，跳过while
 }

 while(ret && p != NULL)
 {
  //升序排列时，right首先非0
  if(x < p->element ) 
   right = p;
  else
   left = p;

  // x 左右一大一小时，插入x
  if (left != NULL && right != NULL)
  {
   if (sort_type) //降序，right在insert_node前面，left在后；
   {
    insert_node->next = right->next;
    right->next = insert_node;
   }
   else //升序，left在前，right在后
   {
    insert_node->next = left->next;
    left->next = insert_node;
   }

   break;//插入成功，跳出循环
  }
  p = p->next;

 } //while

 //降序时x<min, 升序时x > max 应该将x插入表尾
 if (p == NULL)
 {
  insert_end_node(L, x);
 }

 printf("insert_element_to_sorted_list运行，插入元素%d成功\n",x);
 return 1;
}

/* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */
elemType delete_head_node(Node **L)
{
 elemType head_element;
 Node *head = NULL;
 if(*L == NULL)
 {
  printf("delete_head_node执行，此链表为空，删除失败, 程序将终止运行\n");
  system("pause");
  exit(0);
 }
 head = *L;
 head_element = head->element;
 *L = head->next;
 free(head);
 printf("delete_head_node执行，删除表头结点元素%d 成功\n",head_element);
 return head_element;
}

/* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */
elemType delete_end_node(Node **L)
{
 elemType end_element;
 Node *p = *L, *prev = NULL;
 if(p == NULL)
 {
  printf("delete_end_node执行，此链表为空，删除失败, 程序将终止运行\n");
  system("pause");
  exit(0);
 }
 while(p->next != NULL)
 {
  prev = p;
  p = p->next;
 }
 end_element = p->element;

 if ( prev != NULL)//链表只有一个元素时，prev == NULL
 {
  prev->next = NULL;
 }
 else 
  *L = NULL; //只有一个元素，将表头置空

 free(p);
 printf("delete_end_node执行，删除表尾结点元素%d 成功\n",end_element);
 return end_element;
}

/* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */
elemType delete_pos_node(Node **L, int pos)
{
 elemType delete_node_element;
 Node *delete_node = NULL;
 Node *pos_prev_node = NULL;

 if(*L == NULL)
 {
  printf("delete_pos_node执行，此链表为空，删除失败, 程序将终止运行\n");
  system("pause");
  exit(0);
 }
 pos_prev_node = get_pos_prev_address(*L, pos);
 if(pos_prev_node == NULL)
 {
  printf("delete_pos_node执行，查找第%d个结点失败，删除失败, 程序将终止运行\n", pos);
  exit(0);
 }
 delete_node = pos_prev_node->next;
 pos_prev_node->next = delete_node->next;
 delete_node_element = delete_node->element;
 free(delete_node);
 printf("delete_pos_node执行，删除第%d个结点（其元素值为%d）成功, 程序将终止运行\n", pos, delete_node_element);
 return delete_node_element;

}

/* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
int delete_element_node(Node **L, elemType x)
{
 Node *delete_node = NULL;
 Node *x_prev_node = NULL;
 if(*L == NULL)
 {
  printf("delete_pos_node执行，此链表为空，删除失败\n");
  return 0;
 }
 x_prev_node = get_element_prev_position(*L, x);
 if(x_prev_node == NULL)
 {
  printf("delete_element_node执行，查找结点元素%d失败，删除失败\n", x);
  return 0;
 }
 delete_node = x_prev_node->next;
 x_prev_node->next = delete_node->next;
 free(delete_node);
 printf("delete_element_node执行，删除元素值为%d的结点成功, 程序将终止运行\n", x);
 return 1;
}

/* 18.交换2个元素的位置 */
void swap_element_position(Node**L, elemType x, elemType y)
{
 Node *x_prev_node = NULL, *y_prev_node = NULL, *x_node = NULL, *y_node = NULL, *temp = NULL;
 Node *head = NULL;
 elemType first = (*L)->element;
 if ( *L ==NULL )
 {
  printf("swap_element_position运行，链表为空，终止运行\n");
 }
 /*===由于采用返回查找元素前一结点的地址，因此表头节点需要单独考虑===*/
 if ( first ==x )
 {

  y_prev_node = get_element_prev_position(*L, y);

  y_node = y_prev_node->next;
  x_node = *L;
  temp = y_node->next;

  y_prev_node->next = x_node;
  y_node->next =  x_node->next;

  *L = y_node;
  x_node->next = temp;

 }
 else if( first == y)
 {

  x_prev_node = get_element_prev_position(*L, x);

  x_node = x_prev_node->next;
  y_node = *L;
  temp = x_node->next;

  x_prev_node->next = y_node;
  x_node->next =  y_node->next;

  *L = x_node;
  y_node->next = temp;
 }
 else //一般情况，x, y 都不在表头
 {
  x_prev_node = get_element_prev_position(*L, x);
  y_prev_node = get_element_prev_position(*L, y);
  if (x_prev_node != NULL && y_prev_node != NULL) //画出结点连接图，易懂
  {
   y_node = y_prev_node->next;
   x_node = x_prev_node->next;
   temp = y_node->next;

   y_prev_node->next = x_node;
   y_node->next =  x_node->next;

   x_prev_node->next = y_node;
   x_node->next = temp;
  }
 }

 printf("交换元素%d和%d成功！\n", x, y);
}

/* 19.将线性表进行快速排序 */
int sort_list(Node **L) //有错误，仍需修改
{
 Node *x = NULL, *y = NULL;
 Node *p = NULL, *f = NULL, *head = *L;
 if ( p == NULL || p->next == NULL)
 {
  
 }

 f = NULL;  
 //判断是否只有一个元素或者没有元素  
 if(head == NULL || head  -> next == NULL)  
 {  
  printf("sort_list运行，链表为空or只有一个元素，终止运行\n");
  return;  
 }  

 while(f != head->next)  
 {  
  for(p = head; p -> next -> next != f; p = p -> next)  
  {  
   if(p -> next -> element > p -> next -> next ->element)  
   {  
    x = p -> next;  
    y = p -> next -> next;  
    p -> next = y;  
    x -> next = y -> next;  
    y -> next = x;  
   }  
  }  
  f = p -> next;  
 }  
 //*L = p;
 printf("升序排列完成\n");
}
main.c 
#include "link_list.h"

int main()
{
 int n;
 Node * L = NULL;
 Node *p = NULL;
 init_list(L);
 length_list(L);
 isEmpty_list(L);
 L = creat_list();
 length_list(L);
 insert_element_to_sorted_list(&L, 5);
 print_list(L);
 swap_element_position(&L, 2, 5);
 print_list(L);
 sort_list(&L);
 print_list(L);
 delete_element_node(&L, 3);
 print_list(L);
 delete_pos_node(&L, 2);
 print_list(L);
 delete_head_node(&L);
 print_list(L);
 delete_end_node(&L);
 print_list(L);
 insert_head_node(&L, 200);
 insert_end_node(&L, 400);
 print_list(L);
 insert_pos_list(&L, 2, 50);
 insert_pos_list(&L, 6, 40);
 print_list(L);
 n = get_pos_element(L, 3);
 printf("第3个元素为%d\n",n);
 modify_element(L, 3, 100);
 print_list(L);
 modify_element(L, 5, 100);
 print_list(L);
 modify_element(L, 0, 100);
 print_list(L);
 p = get_element_position(L, 3);
 printf("元素3的地址：%x\n",p);
 p = get_element_position(L, 10);
 printf("元素10的地址：%x\n",p);

 isEmpty_list(L);
 n = length_list(L);
 printf("链表长度为：%d\n", n);
 print_list(L);
 L = clear_list(L);
 system("pause");
 return 0;
}



回复
分享到 :
0 人收藏
返回列表
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

16级独孤
选择匿名的用户

积分:3875789
帖子:775174
精华:0
+ 关注 私信
期权论坛 期权论坛
期权网络科技版权所有
关于我们
联系我们
加入我们
反馈问题
免责声明
积分充值
统一社会信用代码
积分规则
网站地图
爱文库
下属网站
官方
新浪微博
微信公众号
◆
下载
表情包
App下载
期权论坛 期权论坛

QQ咨询|关于我们|Archiver|手机版|小黑屋|( 辽ICP备15012455号-4 ) Powered by 期权论坛 X3.2 © 2001-2016 期权工具网&期权论坛 Inc.

发布
内容

下载期权论坛手机APP