C语言创建和操作单链表数据结构的实例教程
作者：xubin341719
字体：[ ] 类型：转载 时间：
这篇文章主要介绍了C语言创建和操作单链表数据结构的实例教程,讲解使用C语言实现链表结构时指针的使用,需要的朋友可以参考下
1，为什么要用到链表
数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。
我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。
链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。
2，单向链表
单链表有一个头节点head，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。
如图所示：
上图还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。
3，单向链表程序的实现
（1），链表节点的数据结构定义
struct node
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
struct node *
//函数声明
struct node *creat();
void print();
struct node *
head=NULL;
//②建一个空表
head=creat(head);/*创建单链表*/
print(head);/*打印单链表*/
/******************************************/
struct node*creat(struct node *head)/*返回的是与节点相同类型的指针*/
struct node*p1,*p2;
//③利用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;/*空表，接入表头*/
p2-&next=p1;/*非空表，接到表尾*/
p1=(struct node*)malloc(sizeof(struct node));/*下一个新节点*/
printf("请输入值，值小于等于0结束，值存放地址为：p%d_ADDR= %d\n",i,p2);
scanf("%d",&p1-&num);/*输入节点的值*/
//⑤判断一下是否有后续节点要接入链表，若有转到3 )，否则结束;
//==============原来程序更正部分：（多谢@daling_datou提醒）================================
free(p1); //申请到的没录入，所以释放掉
//使指向空
p2-&next = NULL; //到表尾了，指向空
printf("链表输入结束（END）\n");
//==============================================
/*返回链表的头指针*/
/*******************************************/
void print(struct node*head)/*出以head为头的链表各节点的值*/
struct node *
temp=/*取得链表的头指针*/
printf("\n\n\n链表存入的值为：\n");
while(temp!=NULL)/*只要是非空表*/
printf("%6d\n",temp-&num);/*输出链表节点的值*/
temp=temp-&/*跟踪链表增长*/
printf("链表打印结束!!");
在链表的创建过程中，链表的头指针是非常重要的参数。因为对链表的输出和查找都要从链表的头开始，所以链表创建成功后，要返回一个链表头节点的地址，即头指针。
程序执行流程：
4，单链表操作基础示例
#include &stdio.h&
#include &malloc.h&
#define LEN sizeof(NODE)
typedef struct _NODE//节点声明
struct _NODE*
} NODE, *PNODE;
void print(PNODE head){//打印所有节点
while (head)
printf("%3d",head-&val);
head = head-&
printf("\n");
void insertHead(PNODE *pHead, int val){//头插法
PNODE n = (PNODE)malloc(LEN);
n-&next = *pH
void insertTail(PNODE *pHead, int val){//尾插法
PNODE t = *pH
PNODE n = (PNODE)malloc(LEN);
n-&next = NULL;
if (*pHead == NULL)
n-&next = *pH
while (t-&next)
void deleteHead(PNODE *pHead){//删除头
if (*pHead == NULL)
PNODE t = *pH
*pHead = (*pHead)-&
void deleteTail(PNODE *pHead){//删除尾
PNODE t = *pH
if (t == NULL)
else if (t-&next == NULL)
*pHead = NULL;
while (t-&next-&next != NULL)
free(t-&next);
t-&next = NULL;
PNODE findByVal(PNODE head, int val){//根据值找到满足条件的第一个节点
while (head != NULL && head-&val != val)
head = head-&
PNODE findByIndex(PNODE head, int index){//根据索引找节点
if (index == 1)
int c = 1;
while (head != NULL && index != c)
head = head-&
void insertByIndex(PNODE *pHead, int index, int val){//根据索引插入节点
if (index == 1)
insertHead(pHead, val);
PNODE t = findByIndex(*pHead,index - 1);
if (t == NULL)
PNODE n = t-&
t-&next = (PNODE)malloc(LEN);
t-&next-&next =
t-&next-&val =
void deleteByIndex(PNODE *pHead, int index)//根据结点索引删除结点
if (index == 1)
deleteHead(pHead);
PNODE t= findByIndex(*pHead, index - 1);
if (t == NULL || t-&next == NULL)
PNODE n = t-&next-&
free(t-&next);
void deleteByVal(PNODE *pHead, int val)//根据值删掉第一个满足条件的
if (*pHead == NULL)//如果空表退出
if ((*pHead)-&val == val)//如果第一个就是，删头
deleteHead(pHead);
PNODE t = *pH
while (t-&next != NULL && t-&next-&val != val)//遍历，若t的next为空或者next是要找的节点则退出
if (t-&next)//如果t指向要找的结点的上一个节点
PNODE n = t-&next-&//删除要找的结点
free(t-&next);
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);
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具在线提问问题标题：问题描述：(简陋的描述会导致问题被最后回答、没有针对性回答甚至无法解答。请确保问题描述的足够清楚。)C++技术网群幕群聊弹幕今天看啥 热点：
04.线性表(三)链式存储结构.单链表2，链式单链
链式存储结构.单链表2
& &&顺序存储结构的创建实质是一个数组的初始化，存储空间连续且其大小和类型已经固定；单链表存储空间不连续，是一种动态结构且它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。
一.单链表的整表创建
& & 创建单链表的过程就是一个动态生成链表的过程，即从“空表”的初始化起，依次建立各元素结点，并逐个插入链表。
1.算法思路
(1)声明一个结点p和计数器变量i;
(2)初始化一空链表L
(3)让链表L的头结点的指针指向NULL,即建立一个带头结点的单链表
&*L=(LinkList)malloc(sizeof(Node));
& (*L)-&next=NULL;
& & a.生成一个新结点赋值给p;
& & b.随机生成一个数字赋值给p的数据域p-&
& & c.将p插入到头结点之前与一新结点之间
2.源码实现
(1)头插法:始终让新结点在第一的位置
/*随机产生n个元素的值，建立带头结点的单链线性表L(头插法)*/
typedef struct Node *LinkL & &//定义LinkList
void CreateListHead(LinkList *L,int n)
& & srand(time(0)); & &//初始化随机数种子
& & /*1.建立一个带头结点的单链表*/
& & *L=(LinkList)malloc(sizeof(Node)); & &//初始化一空链表L
& & &(*L)-&next=NULL; & &//让链表L的头结点的指针指向NULL
& & /*2.循环插入新结点到单链表中*/
& & for(i=0;i&n;i++)
& & & & p=(LinkList)malloc(sizeof(Node)); & &//生成一个新结点
& & & & p-&data=rand()%100+1; & &//设置新结点的数据域
& & & & p-&next=(*L)-& & &//设置新结点的指针域：使p结点的后继结点为头指针之前指向的结点
& & & & (*L)-&next=p; & & & & & & &//更改头结点的后继结点为新结点p
(2)后插法：把每次新结点都插在终端结点的后面
/*随机产生n个元素的值，建立带头结点的单链线性表L(尾插法)*/
typedef struct Node *LinkL & &//定义LinkList
void CreateListTail(LinkList *L,int n)
& & LinkList p,r;
& & srand(time(0)); & &//初始化随机数种子
& & /*1.建立一个带头结点的单链表并设置尾结点*/
& & *L=(LinkList)malloc(sizeof(Node)); & &//初始化一空链表L,L指整个单链表
& & &r=*L; & &//r为指向尾部的结点
& & /*2.循环插入新结点到单链表中*/
& & for(i=0;i&n;i++)
& & & & p=(LinkList)malloc(sizeof(Node)); & &//生成一个新结点
& & & & p-&data=rand()%100+1; & &//设置新结点的数据域
& & & &r-&next=p; & &//将表尾终端结点的指针指向新结点
& & & &r=p; & &//将当前的新结点定义为表尾终端结点
& & r-&next=NULL; & &//此时的尾结点为p，相当于p-&next=null,，表示当前链表结束
注释：注意L与r的关系，L是指整个单链表，而r是指向尾结点的变量；r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。
1.如何创建一个带头结点的单链表？
(1)初始化一空链表L
(2)让链表L的头结点的指针指向NULL
&源码实现： &&LinkList *L;
& & & & & & & & & & &*L=(LinkList)malloc(sizeof(Node)); &&
& & & & & & & & & & &(*L)-&next=NULL;&
2.头插法如何实现插入新结点？
(1)生成一个新结点
(2)设置新结点的数据域
(3)设置新结点的指针域
(4)将新结点作为上一个结点的后继结点
&源码实现：p=(LinkList)malloc(sizeof(Node)); & &
& & & & & & & & & &p-&data=e; & &//e为数据
& & & & & & & & & &p-&next=(*L)-& & &//设置新结点的指针域：使p结点的后继结点为头指针之前指向的结点
& & & & & & & & & &(*L)-&next=p; & & & & & & &//更改头结点的后继结点为新结点p
3.尾差法如何实现插入新结点？
(1)声明一个结点r，并将其设置为链表L的尾部结点
(2)生成一个新结点p
(3)设置新结点的数据域
(4)将表尾终端结点的指针指向新结点,并将新结点设置为尾部结点
(5)设置新的表位结点指针指向NULL，表示当前链表结束
&&源码实现：LinkList *L,p;
& & & & & & & & & &*L=(LinkList)malloc(sizeof(Node)); &
& & & & & & & & & & r=*L;
& & & & & & && & & &p=(LinkList)malloc(sizeof(Node));&
& & & & & & & & & & p-&data=rand()%100+1; &
& & & & & & & & & & r-&next=p; &&
& & & & & & & & & & r=p; &&
二.单链表的整表删除
1.算法思路
(1)声明一个结点p和q;
(2)将单链表的第一个结点赋值给p
& & a.将下一结点赋值给q
& & b.释放p
& & c.将q赋值给p
2.源码实现：
/*初始化条件：单链式线性表L已存在，操作结果：将单链表L重置为空表*/
struct Node *LinkL & &//定义LinkList
ClearList(LinkList *L)
& & LinkList
& & p=(*L)-&
& &//将单链表的第一个结点赋值给结点p
& & while(p)
q=p-& & &//将p的下一个结点设置为q
free(p); & & & &//释放结点p
p=q; & & & & & &//p指向下一结点q
& & (*L)-&next=NULL;
& &//最后，单链表头结点指针域为空
& & returm
三.单链表结构与顺序存储结构的优缺点
1.存储分配方式
(1)顺序存储结构用一段联系的存储单元依次存储线性表的数据元素
(2)单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
2.时间性能
(1)查找：顺序存储结构O(1);单链表O(n)
(2)删除和插入：顺序存储结构需要平均移动表长一半的元素，时间为O(n);单链表在指出某位置的指针后，插入和删除时间仅为O(1)
3.空间性能
(1)顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生溢出；
(2)单链表不需要分配存储空间，只要有就可以分配，元素个数不受限制
相关搜索：
相关阅读：
相关频道：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&
数据库前沿最近更新以下试题来自：
问答题给定程序中,函数fun的功能是将不带头节点的单向链表结点数据域中的数据从小到大排序。即若原链表结点数据域从头至尾的数据为：10、4、2、8、6，排序后链表结点数据域从头至尾的数据为：2、4、6、8、10。
请在程序的下划线处填入正确的内容并把下划线删除, 使程序得出正确的结果。
注意：源程序存放在考生文件夹下的BLANK1.C中。不得增行或删行，也不得更改程序的结构！
给定源程序：
#define N 6
typedef struct node {
struct node *
void fun(NODE *h)
{ NODE *p, *q;
while (p) {
q = __1__ ;
while (__2__)
{ if (p->data > q->data)
{ t = p-> p->data = q-> q->data = }
p = __3__ ;
NODE *creatlist(int a[])
{ NODE *h,*p,*q;
for(i=0; idata=a[i];
q->next = NULL;
if (h == NULL) h = p =
else { p->next = p = }
void outlist(NODE *h)
{ NODE *p;
if (p==NULL) printf("The list is NULL!\n");
{ printf("\nHead ");
{ printf("->%d", p->data); p=p-> }
while(p!=NULL);
printf("->End\n");
int a[N]= {0, 10, 4, 2, 8, 6 };
head=creatlist(a);
printf("\nThe original list:\n");
outlist(head);
fun(head);
printf("\nThe list after inverting :\n");
outlist(head);
为您推荐的考试题库
你可能感兴趣的试题
热门相关试卷
最新相关试卷怎样把两个链表的数据存入一个链表当中
怎样把两个链表的数据存入一个链表当中
09-03-01 &匿名提问
存储方式的分类：顺序存储结构和链式存储结构；顺序存储结构：在（子）程序的说明部分就必须加以说明，以便分配固定大小的存储单元，直到（子）程序结束，才释放空间。因此，这种存储方式又称为静态存储。所定义的变量相应的称为静态变量。它的优缺点如下：　　1． 优点：可以通过一个简单的公式随机存取表中的任一元素，逻辑关系上相邻的两个元素在物理位置上也是相邻的，且很容易找到前趋与后继元素；　　2． 缺点：在线性表的长度不确定时，必须分配最大存储空间，使存储空间得不 到充分利用，浪费了宝贵的存储资源；线性表的容量一经定义就难以扩充；在插入和删除线性表的元素时，需要移动大量的元素，浪费了时间； 链式存储结构：在程序的执行过程中，通过两个命令向计算机随时申请存储空间或随时释放存储空间，以达到动态管理、使用计算机的存储空间，保证存储资源的充分利用。这样的存储方式称为动态存储。所定义的变量称为动态变量。它的优点如下：　　1． 优点：可以用一组任意的存储单元（这些存储单元可以是连续的，也可以不连续的）存储线性表的数据元素，这样就可以充分利用存储器的零碎空间；　　2． 概念1：为了表示任意存储单元之间的逻辑关系，对于每个数据元素来说，除了要存储它本身的信息（数据域、data）外，还要存储它的直接后继元素的存储位置（指针域、link或next）。我们把这两部分信息合在一起称为一个“结点node”。 　　3． 概念2：N个结点链接在一起就构成了一个链表。N=0时，称为空链表。　　4． 概念3：为了按照逻辑顺序对链表中的元素进行各种操作，我们需要定义一个变量用来存储整个链表的第一个结点的物理位置，这个变量称为“头指针、H或head”。也可以把头指针定义成一个结点，称为“头结点”，头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息，头结点的指针域（头指针）存储指向第一个结点的指针，若线性表为空表，则头结点的指针域为空（NIL）。由于最后一个元素没有后继，所以线性表中最后一个结点的指针域为空（NIL）。　　5． 概念4：由于此链表中的每个结点都只包含一个指针域，故称为“线性链表或单链表”。 （一）指针类型和指针变量的说明、使用、操作1．类型和变量的说明　type 指针类型标识符= ^基类型名； {基类型不能为文件类型}　var 指针变量名：指针类型标识符；2．申请存储单元 {动态申请、空间大小由指针变量的基类型决定}　new(指针变量名)； {PASCAL标准过程}3．指针变量的赋值　指针变量名：=NIL； {初始化，暂时不指向任何存储单元}　如何表示和操作指针变量？不同于简单变量（如A：=0；），PASCAL规定用“指针变量名^”的形式引用指针变量（如P^：=0；）。如下图：4．相同基类型的指针变量之间可以进行相互赋值
请登录后再发表评论!
线性表的链式表示和实现 线性表的顺序存储结构的特点是逻辑关系相邻的两元素在物理位置上也是相邻的。因此可以随机存取表中任一元素。然而，这个特点也铸成了这种存储结构的弱点，在做插入或删除操作时，需移动大量元素。于是我们接下来将讨论一下线性表的链式存储结构。它不要求逻辑上相邻的元素在物理位置上也相邻，因此没有顺序存储结构的弱点，但同时也失去了线性存储结构的优点。 线性表的链式存储结构的特点是用任意的存储单元存储线性表的数据元素。因此，为了表示每个元素ai与其直接后继a(i+1)之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息外，还需要存储一个指示其直接后继的信息。这两部分信息组成数据元素的映象，称为结点。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继位置信息的域称为指针域。指针域中存储的信息称做指针域。指针域中的信息称做指针或链。n个结点链结成一个链表，即为线性表（a1,a2,a3,....,an）的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。 用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间逻辑关系的映象，因此逻辑上相邻的两个数据元素其存储的物理位置不要求相邻。 线性表的结点可用结构来描述，如下所示： typedef struct _LNode  {   ElemT   struct _LNode *  }LNode,*LNodeP 有时，我们在单链表的第一个节点之前附设一个结点，称为头节点。头节点的数据域可以不存储信息，也可存储如线性表的长度等类似的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个结点的存储位置）。 在单链表中，任何两个元素的存储位置之间没有固定的联系。而每个元素的存储位置在其直接前驱结点的信息中。假设p是指向线性表中第i个数据元素（结点ai）的指针，则p-&next是指向第i+1个数据元素（结点a(i+1)）指针。因此取得第i个数据元素必须从头指针出发寻找，因为单链表是非随机存取的存储结构。 现对单链表做出如下定义：  class LinkList{LNodePtr LinkH//指向链表的头结点        int      Lpublic: status GetElem(int i,ElemType &e); status ListInsert(int i,ElemType &e); status ListDelete(int i,ElemType &e);...//同线性表顺序存储结构} 下面是GetElem在单链表中的实现： status LinkList::GetElem(int i,ElemType &e);{//本例为带头结点的链表。当第i个元素存在时，其值赋给e，并返回OK，否则返回ERRORElemType *p=LinkHead-&int j=1;while(p&&j&i){ p=p-& ++j;}if(!p||j&i) return ERROR;//系i个元素不存在e=p-&return OK;} 若第i个元素不存，while循环结束后j&=i。当链表中有(i-1)个元素时j=i;p=NULL;当元素个数小于（i-1）个时，j&i且p=NULL。若第i元素存在，while结束后，j=i,p指向第i个元素所在的结点。故j&i的情是不会出现的。所以我认为完全可以将“if(!p||j) return ERROR;”改为“if(!p) return ERROR;”。 假设我们要在线性表的两个元素a和b之间插入数据元素X，首先要生成一个数据域为X的结点，然后插入在单链表中的相应位置。根据插入操作的逻辑定义，只需要修改结点a中的指针域，令其指向结点X，而结点X中的指针域应指向结点b，从而实现三个元素a,b,x之间逻辑关系的变化。假设S为指向结点X指针，P为指向结点a的指针，则上述指针修改用语句描述即为：  s-&next=p-&p-&next=s; 反之，当在线性表中删除元素b时，为在单链表中实现元素a、b、c之间逻辑关系的变化公需要修改结点中的指针域即可。假设P为指向结点a的指针，则修改指针的语句为：  p-&next=p-&next-& 可见，在已知链表中元素插入或删除的确切位置的情况下，在单链表中插入或删除一个结点时，仅需要修改指针而不需要移动元素。 插入和删除元素的算法如下： status LinkList::ListInsert(int i,ElemType e){//在带头结点的单链表中，在第i个元素之前插入元素eLNodePtr p=LinkHint     j=0;while(p&&j&i-1){ p=p-& ++j;}if(!p||j&i-1) return ERROR;s=(LNodePtr)malloc(sizeof(LNode));s-&data=e;s-&next=p-&Length++;p-&next=s;return OK;}status LinkList::ListDelete(int i,ElemType &e) {//在带头结点的单链表中，删除第i个元素，并用e返回其值LNodePtr p=LinkHint j=0;while(p&&j&i-1){ p=p-& ++j;}if(!p||j&i-1) return ERROR;q=p-&//q指向要删除的结点p-&next=q-&//从链表中将指定元素删除e=q-&//返回删除的元素free(q);//释放被删除元素所占用的空间Length--;return OK;}
请登录后再发表评论!