C++中链表操作实例分析_c++定一个无序链表，通过插入排序算法，生成有序链表资源-CSDN文库

printf

73 浏览量 2021-01-20 05:58:04 上传评论收藏 123KB PDF 举报

资源推荐

资源详情

资源评论

C++中链表操作实例分析中链表操作实例分析

链表概述

　　链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一

个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两

个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元

素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链

表到此结束。

链表的各类操作包括：学习单向链表的创建、删除、插入（无序、有序）、输出、排序（选择、插入、冒泡）、反序等

等。

单向链表的图示：

—->[NULL] head

图1：空链表

—->[p1]—->[p2]…—->[pn]—->[NULL] head p1->next p2->next pn->next

图2：有N个节点的链表

创建n个节点的链表的函数为：

#include “stdlib.h”

#include “stdio.h”

#define NULL 0

#define LEN sizeof(struct student)

struct student

{

int num; //学号

float score; //分数，其他信息可以继续在下面增加字段

struct student *next; //指向下一节点的指针

};

int n; //节点总数

==========================

功能：创建n个节点的链表

返回：指向链表表头的指针

==========================

struct student *Create()

{

struct student *head; //头节点

struct student *p1 = NULL; //p1保存创建的新节点的地址

struct student *p2 = NULL; //p2保存原链表最后一个节点的地址

n = 0; //创建前链表的节点总数为0：空链表

p1 = (struct student *) malloc (LEN); //开辟一个新节点

p2 = p1; //如果节点开辟成功，则p2先把它的指针保存下来以备后用

if(p1==NULL) //节点开辟不成功

{

printf (“Cann’t create it, try it again in a moment!”);

return NULL;

}

else //节点开辟成功

{

head = NULL; //开始head指向NULL

printf (“Please input %d node — num,score: “, n + 1);

scanf (“%d %f”, &(p1->num), &(p1->score)); //录入数据

}

while(p1->num != 0) //只要学号不为0，就继续录入下一个节点

{

n += 1; //节点总数增加1个

if(n == 1) //如果节点总数是1，则head指向刚创建的节点p1

{

head = p1;

p2->next = NULL; //此时的p2就是p1,也就是p1->next指向NULL。

}

else

{

p2->next = p1; //指向上次下面刚刚开辟的新节点

}

p2 = p1; //把p1的地址给p2保留，然后p1产生新的节点

p1 = (struct student *) malloc (LEN);

printf (“Please input %d node — num,score: “, n + 1);

scanf (“%d %f”, &(p1->num), &(p1->score));

}

p2->next = NULL; //此句就是根据单向链表的最后一个节点要指向NULL

free(p1); //p1->num为0的时候跳出了while循环，并且释放p1

p1 = NULL; //特别不要忘记把释放的变量清空置为NULL,否则就变成”野指针”，即地址不确定的指针

return head; //返回创建链表的头指针

}

输出链表中节点的函数为：

===========================

功能：输出节点

返回： void

===========================

void Print(struct student *head)

{

struct student *p;

printf (“\nNow , These %d records are:\n”, n);

p = head;

if(head != NULL) //只要不是空链表，就输出链表中所有节点

{

printf(“head is %o\n”, head); //输出头指针指向的地址

{

输出相应的值：当前节点地址、各字段值、当前节点的下一节点地址。

这样输出便于读者形象看到一个单向链表在计算机中的存储结构，和我们

设计的图示是一模一样的。

printf (“%o %d %5.1f %o\n”, p, p->num, p->score, p->next);

p = p->next; //移到下一个节点

}

while (p != NULL);

}

}/*

===========================

功能：输出节点

返回： void

===========================

void Print(struct student *head)

{

struct student *p;

printf (“\nNow , These %d records are:\n”, n);

p = head;

if(head != NULL) //只要不是空链表，就输出链表中所有节点

{

printf(“head is %o\n”, head); //输出头指针指向的地址

{

输出相应的值：当前节点地址、各字段值、当前节点的下一节点地址。

这样输出便于读者形象看到一个单向链表在计算机中的存储结构，和我们

设计的图示是一模一样的。

printf (“%o %d %5.1f %o\n”, p, p->num, p->score, p->next);

p = p->next; //移到下一个节点

}

while (p != NULL);

}

单向链表的删除图示：

—->[NULL] head

图3：空链表

从图3可知，空链表显然不能删除

—->[1]—->[2]…—->[n]—->[NULL]（原链表）

head 1->next 2->next n->next

—->[2]…—->[n]—->[NULL]（删除后链表）

head 2->next n->next

图4：有N个节点的链表，删除第一个节点

结合原链表和删除后的链表，就很容易写出相应的代码。操作方法如下：

1、你要明白head就是第1个节点，head->next就是第2个节点；

2、删除后head指向第2个节点，就是让head=head->next,OK这样就行了。

—->[1]—->[2]—->[3]…—->[n]—->[NULL]（原链表）

head 1->next 2->next 3->next n->next

—->[1]—->[3]…—->[n]—->[NULL]（删除后链表）

head 1->next 3->next n->next

图5：有N个节点的链表，删除中间一个（这里图示删除第2个）

结合原链表和删除后的链表，就很容易写出相应的代码。操作方法如下：

1、你要明白head就是第1个节点，1->next就是第2个节点，2->next就是第3个节点；

2、删除后2，1指向第3个节点，就是让1->next=2->next。

删除指定学号的节点的函数为：

==========================

功能：删除指定节点

(此例中是删除指定学号的节点)

返回：指向链表表头的指针

==========================

struct student *Del (struct student *head, int num)

{

struct student *p1; //p1保存当前需要检查的节点的地址

struct student *p2; //p2保存当前检查过的节点的地址

if (head == NULL) //是空链表（结合图3理解）

{

printf (“\nList is null!\n”);

return head;

}

//定位要删除的节点

p1 = head;

while (p1->num != num && p1->next != NULL) //p1指向的节点不是所要查找的，并且它不是最后一个节点，就继续往下

找

{

p2 = p1; //保存当前节点的地址

p1 = p1->next; //后移一个节点

}

if(p1->num==num) //找到了。（结合图4、5理解）

{

if (p1 == head) //如果要删除的节点是第一个节点

{

head = p1->next; //头指针指向第一个节点的后一个节点，也就是第二个节点。这样第一个节点就不在链表中，即删

除

剩余15页未读，继续阅读

评论收藏

内容反馈

weixin_38697659

粉丝: 1
资源: 898

C++中链表操作实例分析

C++实现的链表类实例

C++语言实现线性表之链表实例

C++之数据结构链表分类与实例分析[参照].pdf

C++实现接两个链表实例代码

单向链表排序，排序完成后返回链表头

基于C++的链表操作

C语言链表的操作实例

链表操作实例

c语言链表实例

c++链表操作程序

C++ 实现双向链表的实例

C++ 链表操作（建立、添加、删除、查找、排序、索引等）

链表C++程序

c++编写的链表等的各种操作

C++实现链表和顺序表并比较他们的效率

数据结构单双链表c++版

Linux内核双向链表简单分析

C++ Builder6编程实例精解

用C++实现链表的操作

C++ 实现 链表的操作

C++ 链表操作大全

C/C++链表操作doc

C语言链表基本操作

简单的关于c++链表问题

c++链表结构

C++链表的具体实现，很详细

链表的运用对c++初学者很有用的

最新资源

C++ 实现链表的操作