用C语言实现单链表的各种操作(二)_C 语言

上一篇文章<用C语言实现单链表的各种操作(一)>主要是单链表的一些最基本的操作，下面，主要是一些其他的典型的算法和测试程序。

复制代码 代码如下:

/* 对单链表进行排序处理*/
struct LNode *sort(struct LNode *head)
{
  LinkList *p;
  int n,i,j;
  int temp;
  n = ListLength(head);
  if(head == NULL || head->next == NULL)
    return head;
  p = head->next;
  for(j =1;j<n;++j)
  {
    p = head->next;
    for( i =0;i<n-j;++i)
    {
      if(p->data > p->next->data)
      {
        temp = p->data;
        p->data = p->next->data;
        p->next->data = temp;
      }
      p = p->next;
    }
  }
  return head;
}
/*对单链表进行逆置*/
LinkList *reverse(LinkList *head)
{
  LinkList *p1,*p2 = NULL,*p3 = NULL;
  if(head == NULL || head->next == NULL)
    return head;
  p1 = head->next;
  while(p1!=NULL)
  {
    p3 = p1->next;
    p1->next = p2;
    p2 = p1;
    p1 = p3;
 }
 head->next = p2;
  // head = p2;
  return head;
}
Status equal(ElemType c1,ElemType c2)
{
  if(c1== c2)
    return TRUE;
  else
    return FALSE;
}
/*将所有在线性表Lb中但不在La中的数据元素插入到La 中*/
void Union(LinkList *La,LinkList *Lb)
{
  ElemType *e;
  int La_len,Lb_len;
  int i;
  La_len = ListLength(La);
  Lb_len = ListLength(Lb);
  for(i=1;i<=Lb_len;i++)
  {
    GetElem(Lb,i,e); //取Lb中第i个元素赋给e
    if(!LocateElem(La,*e,equal))//La中不存在和e相同的元素，则插入
      ListInsert(La,++La_len,*e);
  }
}
void print(ElemType c)
{
  printf("%4d",c);
}
/* 合并两个单链表，La和Lb中的数据是按非递减排列，归并后的Lc还是安非递减排列*/
void MergeList(LinkList *La,LinkList *Lb,LinkList **Lc)
{
  int i =1,j=1,k=0;
  int La_len,Lb_len;
  ElemType *ai,*bj;
  ai = (ElemType *)malloc(sizeof(ElemType));
  bj = (ElemType *)malloc(sizeof(ElemType));

  InitList(Lc);
  La_len = ListLength(La);
  Lb_len = ListLength(Lb);
  while(i<=La_len && j<=Lb_len)
  {
    GetElem(La,i,ai);
    GetElem(Lb,j,bj);
    if(*ai<*bj)
    {
      ListInsert(*Lc,++k,*ai);
      ++i;
    }
    else
    {
      ListInsert(*Lc,++k,*bj);
      ++j;
    }
  }
  while(i<=La_len)
  {
    GetElem(La,i++,ai);
    ListInsert(*Lc,++k,*ai);
  }
  while(j<=Lb_len)
  {
    GetElem(Lb,j++,bj);
    ListInsert(*Lc,++k,*bj);
  }
}
/*只遍历一次，找到单链表中的中间节点
 1 定义两个指针，一个指针每次移动两个步长（快指针），另一个指针每次移动一个数据（慢指针）
 2. 当快指针到达链表尾部的时候，慢指针就到了链表的中间节点
在程序中也可以判断一个单链表是否有环，如果快指针一定能够追赶上慢指针，否则就会以NULL结束*/
LinkList *Searchmid(LinkList * head)
{
  if(NULL == head)
    return NULL;
  if(head->next == NULL)
    return head;
  if(head->next->next == NULL)
    return head;

  LinkList *mid= head;
  LinkList *p = mid->next;

  while((p != NULL) && (NULL !=p->next))
  {
    mid = mid->next;
    p = p->next->next;
  }
  return mid;
}

下面主要是单链表的一个测试的程序。

复制代码 代码如下:

Status comp(ElemType c1,ElemType c2)
{
  if(c1==c2)
    return TRUE;
  else
    return FALSE;
}
void visit(ElemType c)
{
  printf("%4d",c);
}
void main()
{
  LinkList *L;
  LinkList *mid;
  mid = (struct LNode *)malloc(sizeof(struct LNode));

  ElemType *e,e0,*e1;
  Status i;
  int j,k;
  e = (ElemType *)malloc(sizeof(ElemType));
  e1 = (ElemType *)malloc(sizeof(ElemType));

  i = InitList(&L);
  for(j=1;j<=6;j++)
  {
    i = ListInsert(L,1,j);
  }
  printf("在L的表头依次插入1～6后：L=");
    ListTraverse(L,visit);
    printf("L中间节点的值为mid=：");
    mid = Searchmid(L);
     printf("%d\n",mid->data);

      printf("L逆置后的输出：L=");
      ListTraverse(reverse(L),visit);
    printf("L排序后依次为：L=");
    ListTraverse(sort(L),visit);

   
  i = ListEmpty(L);
  printf("L 是否为空：i=%d(1:是，0:否)\n",i);
  i = ClearList(L);
  printf("清空L后：L=");
  ListTraverse(L,visit);
  i = ListEmpty(L);
  printf("L是否为空：i=%d\n",i);
  for(j=1;j<=10;j++)
  {
    ListInsert(L,j,j);
  }
  printf("在L的表尾依次插入1~10后：L=");
  ListTraverse(L,visit);
  GetElem(L,5,e);
  printf("第5个元素的值为：%d\n",*e);
  for(j=0;j<=1;j++)
  {
    k = LocateElem(L,j,comp);
    if(k)
      printf("第%d个元素的值为%d\n",k,j);
    else
      printf("没有值为%d的元素\n",j);
  }
  for(j=1;j<=2;j++)
  {
    GetElem(L,j,e1);
    i = PriorElem(L,*e1,e);
    if(i== INFEASIBLE)
      printf("元素%d无前驱\n",*e1);
    else
      printf("元素%d的前驱为：%d\n",*e1,*e);
  }
  for(j=ListLength(L) -1;j<=ListLength(L);j++)
  {
    GetElem(L,j,e1);
    i = NextElem(L,*e1,e);
    if(i==INFEASIBLE)
      printf("元素%d无后继\n",*e1);
    else
      printf("元素%d的后继为：%d\n",*e1,*e);
  }
   k = ListLength(L);
  for(j=k+1;j>=k;j--)
  {
    i = ListDelete(L,j,e);
    if(i==ERROR)
      printf("删除第%d个数据失败\n",j);
    else
      printf("删除的元素为：%d\n",*e);
  }
  printf("依次输出L的元素：");
    ListTraverse(L,visit);
  DestroyList(L);
  printf("销毁L后：L=%u\n",L);
  printf("*************************************************\n");
  LinkList *La,*Lb;
  i = InitList(&La);
  if(i==1)
    for(j=1;j<=5;j++)
      i= ListInsert(La,j,j);
  printf("La=");
  ListTraverse(La,print);
  InitList(&Lb);
  for(j=1;j<=5;j++)
    i = ListInsert(Lb,j,2*j);
  printf("Lb = ");
  ListTraverse(Lb,print);
  Union(La,Lb);
  printf("new La=");
  ListTraverse(La,print);
  printf("*************************************************\n");
  LinkList *La_1,*Lb_1,*Lc_1;
  int a[4]={3,5,8,11},b[7]= {2,6,8,9,11,15,20};
  InitList(&La_1);
  for(j=1;j<=4;j++)
    ListInsert(La_1,j,a[j-1]);
  printf("La_1=");
  ListTraverse(La_1,print);
  InitList(&Lb_1);
  for(j=1;j<=7;j++)
    ListInsert(Lb_1,j,b[j-1]);
  printf("Lb_1=");
  ListTraverse(Lb_1,print);
  MergeList(La_1,Lb_1,&Lc_1);
  printf("Lc_1=");
  ListTraverse(Lc_1,print);
}

下面是在Linux下的部分运行结果：

复制代码 代码如下:

在L的表头依次插入1～6后：L= 6 5 4 3 2 1
L中间节点的值为mid=：4
L逆置后的输出：L= 1 2 3 4 5 6
L排序后依次为：L= 1 2 3 4 5 6
L 是否为空：i=0(1:是，0:否)
清空L后：L=
L是否为空：i=1
在L的表尾依次插入1~10后：L= 1 2 3 4 5 6 7 8 9 10
第5个元素的值为：5
没有值为0的元素
第1个元素的值为1
元素1无前驱
元素2的前驱为：1
元素9的后继为：10
元素10无后继
删除第11个数据失败
删除的元素为：10
依次输出L的元素： 1 2 3 4 5 6 7 8 9
销毁L后：L=7954544
*************************************************
La= 1 2 3 4 5
Lb = 2 4 6 8 10
new La= 1 2 3 4 5 6 8 10
*************************************************
La_1= 3 5 8 11
Lb_1= 2 6 8 9 11 15 20
Lc_1= 2 3 5 6 8 8 9 11 11 15 20

时间： 2024-09-14 08:10:05

用C语言实现单链表的各种操作(二)_C 语言的相关文章

用C语言实现单链表的各种操作(一)_C 语言

最近,从新复习了一下数据结构中比较重要的几个部分,现在把自己的成果记录下来,主要就是仿照严蔚敏的<数据结构>(C 语言版),中的例子和后面的习题进行改编的.首先,是单链表的各种实现,其中,包含了一些常考的知识点.例如,单链表的逆置,单链表的合并,找到单链表的中间节点等的算法实现.下面这个是单链表的结构体的定义: 复制代码 代码如下: typedef struct LNode{ ElemType data; struct LNode *next;}LinkList; 下面的基本的单链表的操作:其

C语言创建和操作单链表数据结构的实例教程_C 语言

1,为什么要用到链表 数组作为存放同类数据的集合,给我们在程序设计时带来很多的方便,增加了灵活性.但数组也同样存在一些弊病.如数组的大小在定义时要事先规定,不能在程序中进行调整,这样一来,在程序设计中针对不同问题有时需要3 0个大小的数组,有时需要5 0个数组的大小,难于统一.我们只能够根据可能的最大需求来定义数组,常常会造成一定存储空间的浪费. 我们希望构造动态的数组,随时可以调整数组的大小,以满足不同问题的需要.链表就是我们需要的动态数组.它是在程序的执行过程中根据需要有数据存储就向系统要求

C++ 单链表的基本操作(详解)_C 语言

链表一直是面试的高频题,今天先总结一下单链表的使用,下节再总结双向链表的.本文主要有单链表的创建.插入.删除节点等. 1.概念 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素. 链表中的数据是以结点来表示的,每个结点的构成:元素 + 指针,元素就是存储数据的存储单元,指针就是连接每个结点的地址数据.如下图: 2.链表的基本操作 SingleList.cpp: #include "stdafx.h" #include "SingleList.h&

深入单链表的快速排序详解_C 语言

单链表的快排序和数组的快排序基本思想相同,同样是基于划分,但是又有很大的不同:单链表不支持基于下标的访问.故书中把待排序的链表拆分为2个子链表.为了简单起见,选择链表的第一个节点作为基准,然后进行比较,比基准小得节点放入左面的子链表,比基准大的放入右边的子链表.在对待排序链表扫描一遍之后,左边子链表的节点值都小于基准的值,右边子链表的值都大于基准的值,然后把基准插入到链表中,并作为连接两个子链表的桥梁.然后分别对左.右两个子链表进行递归快速排序,以提高性能.但是,由于单链表不能像数组那样随机存储

使用单链表实现多项式计算示例_C 语言

复制代码 代码如下: #include <stdio.h>#include <stdlib.h> //比较函数返回值#define A_EQUAL_B  0#define A_LARGE_B  1#define A_LOWER_B -1 //错误返回之集合#define SUCCESS            0#define POINT_ARG_IS_NULL -1#define LINKLIST_IS_NULL  -2#define NOT_FOUND         -3 ty

c语言-C语言建立单链表的问题

问题描述 C语言建立单链表的问题 #include<stdio.h> #include<stdlib.h> struct node { int num; int L; struct node *next; }; typedef struct node LN; typedef struct { int num1[100]; int L1; }S; void Creat1(S &p); void Creat(LN *p); void main() { S p; LN *h; p

C语言之单链表的插入、删除与查找_C 语言

单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素.要实现对单链表中节点的插入.删除与查找的功能,就要先进行的单链表的初始化.创建和遍历,进而实现各功能,以下是对单链表节点的插入.删除.查找功能的具体实现: #include<stdio.h> #include<stdlib.h> #include<string.h> typedef int ElemType; /** *链表通用类型 *ElemType 代表自定义的数据类型 *struct

C语言单链表常见操作汇总_C 语言

C语言的单链表是常用的数据结构之一,本文总结了单链表的常见操作,实例如下: #include<stdio.h> #include<stdlib.h> //定义单链表结构体 typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; }LNode,*LinkList; //创建单链表 void Build(LinkList L) { int n; LinkList p,q; p=L; pr

C语言数据结构单链表之温故而知新

抛弃繁杂的定义,以实用,实战的角度来学习数据结构,这将使得数据结构的学习非常的简单. 前面已经学习了单链表的创建操作:http://blog.csdn.net/morixinguan/article/details/68951912 这节,将单链表温习的笔记共享出来,然后写一个例子,以防自己忘记. 1.单链表的数据结构的定义: 创建节点函数原型可定义如下: struct list *create_node(int data) ; 如何创建单链表的节点,主要分以下步骤: (1)给当前的每个节点的数