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

1，为什么要用到链表

数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。

我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。

链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。

2，单向链表

单链表有一个头节点head，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。

如图所示：

上图还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。

3，单向链表程序的实现
（1），链表节点的数据结构定义

struct node
{
  int num;
  struct node *p;
} ;

在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。

在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。

（2），链表的创建、输出步骤
单链表的创建过程有以下几步：

1 ) 定义链表的数据结构;

2 ) 创建一个空表;

3 ) 利用malloc ( )函数向系统申请分配一个节点;

4 ) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新

节点接到表尾;

5 ) 判断一下是否有后续节点要接入链表，若有转到3 )，否则结束;

单链表的输出过程有以下几步

1) 找到表头;

2) 若是非空表，输出节点的值成员，是空表则退出;

3 ) 跟踪链表的增长，即找到下一个节点的地址;

4) 转到2 ).

（3），程序代码例子：
创建一个存放正整数单链表，输入0或小于0的数，结束创建链表，并打印出链表中的值，程序如下：

#include <stdlib.h> /*含ma l l o c ( ) 的头文件*/
#include <stdio.h>
 //①定义链表数据结构
struct node
{
  int num;
  struct node *next;
};
//函数声明
struct node *creat();
void print();
main( )
{ 

  struct node *head;
  head=NULL;  //②建一个空表
  head=creat(head);/*创建单链表*/
  print(head);/*打印单链表*/
}
/******************************************/
struct node*creat(struct node *head)/*返回的是与节点相同类型的指针*/
{
  struct node*p1,*p2;
  int i=1;
//③利用malloc ( )函数向系统申请分配一个节点
  p1=p2=(struct node*)malloc(sizeof(struct node));/*新节点*/
  printf("请输入值，值小于等于0结束，值存放地址为：p1_ADDR= %d\n",p1);
  scanf("%d",&p1->num);/*输入节点的值*/
  p1->next=NULL;/*将新节点的指针置为空*/
  while(p1->num>0)/*输入节点的数值大于0*/
  {
//④将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点接到表尾;
    if(head==NULL)
      head=p1;/*空表，接入表头*/
    else
      p2->next=p1;/*非空表，接到表尾*/
    p2=p1; 

    p1=(struct node*)malloc(sizeof(struct node));/*下一个新节点*/
    i=i+1;
    printf("请输入值，值小于等于0结束，值存放地址为：p%d_ADDR= %d\n",i,p2);
    scanf("%d",&p1->num);/*输入节点的值*/
//⑤判断一下是否有后续节点要接入链表，若有转到3 )，否则结束;
  }
//==============原来程序更正部分：（多谢@daling_datou提醒）================================
  free(p1); //申请到的没录入，所以释放掉
  p1=NULL;  //使指向空
  p2->next = NULL; //到表尾了，指向空
  printf("链表输入结束（END）\n");
//==============================================
  return head;/*返回链表的头指针*/
}
/*******************************************/
void print(struct node*head)/*出以head为头的链表各节点的值*/
{
  struct node *temp;
  temp=head;/*取得链表的头指针*/ 

  printf("\n\n\n链表存入的值为：\n");
  while(temp!=NULL)/*只要是非空表*/
  {
    printf("%6d\n",temp->num);/*输出链表节点的值*/
    temp=temp->next;/*跟踪链表增长*/
  }
  printf("链表打印结束!!");
}

在链表的创建过程中，链表的头指针是非常重要的参数。因为对链表的输出和查找都要从链表的头开始，所以链表创建成功后，要返回一个链表头节点的地址，即头指针。

程序执行流程：

4，单链表操作基础示例

#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(NODE) 

typedef struct _NODE//节点声明
{
  int val;
  struct _NODE* next;
} NODE, *PNODE; 

void print(PNODE head){//打印所有节点
  while (head)
  {
    printf("%3d",head->val);
    head = head->next;
  }
  printf("\n");
} 

void insertHead(PNODE *pHead, int val){//头插法
  PNODE n = (PNODE)malloc(LEN);
  n->val = val;
  n->next = *pHead;
  *pHead = n;
} 

void insertTail(PNODE *pHead, int val){//尾插法
  PNODE t = *pHead;
  PNODE n = (PNODE)malloc(LEN);
  n->val = val;
  n->next = NULL;
  if (*pHead == NULL)
  {
    n->next = *pHead;
    *pHead = n;
  }else{
    while (t->next)
    {
      t = t->next;
    }
    t->next = n;
  }
} 

void deleteHead(PNODE *pHead){//删除头
  if (*pHead == NULL)
  {
    return;
  }
  else
  {
    PNODE t = *pHead;
    *pHead = (*pHead)->next;
    free(t);
  }
} 

void deleteTail(PNODE *pHead){//删除尾
  PNODE t = *pHead;
  if (t == NULL)
  {
    return;
  }
  else if (t->next == NULL)
  {
    free(t);
    *pHead = NULL;
  }
  else{
    while (t->next->next != NULL)
    {
      t = t->next;
    }
    free(t->next);
    t->next = NULL;
  }
} 

PNODE findByVal(PNODE head, int val){//根据值找到满足条件的第一个节点
  while (head != NULL && head->val != val)
  {
    head = head->next;
  }
  return head;
} 

PNODE findByIndex(PNODE head, int index){//根据索引找节点
  if (index == 1)
  {
    return head;
  }
  else
  {
    int c = 1;
    while (head != NULL && index != c)
    {
      head = head->next;
      c++;
    }
  }
  return head;
} 

void insertByIndex(PNODE *pHead, int index, int val){//根据索引插入节点
  if (index == 1)
  {
    insertHead(pHead, val);
  }
  else
  {
    PNODE t = findByIndex(*pHead,index - 1);
    if (t == NULL)
    {
      return;
    }
    else
    {
      PNODE n = t->next;
      t->next = (PNODE)malloc(LEN);
      t->next->next = n;
      t->next->val = val;
    }
  }
} 

void deleteByIndex(PNODE *pHead, int index)//根据结点索引删除结点
{
  if (index == 1)
  {
    deleteHead(pHead);
  }
  else
  {
    PNODE t= findByIndex(*pHead, index - 1);
    if (t == NULL || t->next == NULL)
    {
      return;
    }else{
      PNODE n = t->next->next;
      free(t->next);
      t->next = n;
    }
  }
} 

void deleteByVal(PNODE *pHead, int val)//根据值删掉第一个满足条件的
{
  if (*pHead == NULL)//如果空表退出
  {
    return;
  }
  else
  {
    if ((*pHead)->val == val)//如果第一个就是，删头
    {
      deleteHead(pHead);
    }
    else
    {
      PNODE t = *pHead;
      while (t->next != NULL && t->next->val != val)//遍历，若t的next为空或者next是要找的节点则退出
      {
        t = t->next;
      }
      if (t->next)//如果t指向要找的结点的上一个节点
      {
        PNODE n = t->next->next;//删除要找的结点
        free(t->next);
        t->next = n;
      }
    }
  }
} 

void clear(PNODE *pHead)//清除链表
{
  while ((*pHead) != NULL)
  {
    deleteHead(pHead);//从头删除
  }
} 

void main()
{
  PNODE head = NULL; 

  insertTail(&head,1);
  deleteHead(&head);
  insertTail(&head,2);
  insertTail(&head,3);
  insertTail(&head,4);
  insertTail(&head,5);
  insertTail(&head,6); 

  print(head);
  insertByIndex(&head, 6, 9);
  print(head);
  //deleteByIndex(&head,3);
  deleteByVal(&head, 2);
  print(head);
  clear(&head);
  print(head);
  insertByIndex(&head,1,12);
  print(head);
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索c语言
， 数据结构
单链表
c语言单链表的创建、c语言创建单链表、c语言单链表、c语言建立单链表、c语言单链表程序代码，以便于您获取更多的相关知识。

时间： 2025-01-02 20:18:19

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

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

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

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

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

C#模拟链表数据结构的实例解析_C#教程

写在前面 模块化编程是大多数初学者必经之路,然后可能你走向了结构化编程,链表是一种典型结构模式,它的出现克服了数组必须预先知道大小的缺陷,听不懂?你只需要记住,链表结构非常牛叉就可以了,学习这种结构对我们的逻辑思维有很大提升. 什么是链表结构呢? 链表是一种物理存储单元上非连续.非顺序的存储结构.比如A->B->C,这种结构,我们可以理解为A连接着B,B连接C,像这种结构我们就叫做链表结构.对了,火车的车厢,其实就是链表的结构的最好说明 为什么要有链表结构呢? 学过计算机的都知道数组(Arra

C语言 文件操作解析详解及实例代码_C 语言

C语言文件操作解析         在文件操作中除了打开操作以及读写操作,还有几种比较常见的操作.下面介绍一下这些操作中涉及到的函数. 一.移动位置指针的函数    rewind函数和fseek函数,这两个函数的原型是:    void rewind(FILE *fp);     将位置指针移动到文件首   int fseek(FILE *fp,long int offset,int origin);   将位置指针移动到距离origin的offset字节数的位置   其中对于fseek函数中的

C语言泛型编程实例教程_C 语言

本文实例讲述了C语言泛型编程的方法,分享给大家供大家参考之用.具体分析如下: 首先,泛型编程让你编写完全一般化并可重复使用的算法,其效率与针对某特定数据类型而设计的算法相同.在C语言中,可以通过一些手段实现这样的泛型编程.这里介绍一种方法--通过无类型指针void* 看下面的一个实现交换两个元素内容的函数swap,以整型int为例: void swap(int* i1,int* i2){ int temp; temp = *i1; *i1 = *i2; *i2 = temp; } 当你想交换两个

C语言之实现控制台光标随意移动的实例代码_C 语言

原理引入windows.h,首先是要获得输入的东西,然后通过判断: 1.方向键:执行上下左右的移动功能 2 .回车键:执行换行的功能. 3.普通键:输入功能. 终点就是要获取到屏幕上的坐标,当按下了方向键以后,坐标值+1,或者减一,从而实现了光标的自由移动. //C语言实现控制台中光标随意移动 #include <stdio.h> #include <windows.h> #include <conio.h> HANDLE hout; //获得输入 char getIn

C语言循环结构与时间函数用法实例教程_C 语言

本文实例展示了C语言循环结构与时间函数用法,对于C语言的学习来说是非常不错的参考借鉴材料.分享给大家供大家参考之用.具体如下: 完整实例代码如下: /********************************************** ** <Beginning C 4th Edition> Notes codes ** Created by Goopand ** Compiler: gcc 4.7.0 *****************************************

使用单链表实现多项式计算示例_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

Linux中使用C语言的fork()函数创建子进程的实例教程_C 语言

一.fork入门知识一个进程,包括代码.数据和分配给进程的资源.fork()函数通过系统调用创建一个与原来进程几乎完全相同的进程,也就是两个进程可以做完全相同的事,但如果初始参数或者传入的变量不同,两个进程也可以做不同的事. 一个进程调用fork()函数后,系统先给新的进程分配资源,例如存储数据和代码的空间.然后把原来的进程的所有值都复制到新的新进程中,只有少数值与原来的进程的值不同.相当于克隆了一个自己.   我们来看一个例子: #include <unistd.h> #include &l