线性表:关于链表(主要以单链表为例)的相关理解和应用

这篇具有很好参考价值的文章主要介绍了线性表:关于链表(主要以单链表为例)的相关理解和应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

多清澈这天空 晴雨相拥 同心逐梦!

坚守我信心  一路出众!!

首先,按照惯例,欢迎大家边听歌边观看本博客

▶ 紫荆花盛开 (163.com)(建议复制链接,浏览器打开,csdn打开太慢了)

2022香港回归祖国25周年主题歌曲,好听!!!

一.单链表

首先 大家肯定知道链表的表达方式,如下

typedef struct LNode
{
    ElemType data;
    struct LNode *next;

}LinkNode;

定义一个LNode,node节点,结点,L是link,表示链接,所以叫做LNode链接结点构成链表

第一个存放元素的信息,链表的特点就是多存了一个节点(指针域)指向后继节点。

0.1稍微浅浅的给大家补充一下结构体的知识点:

1.一个正常的结构体代码编写

struct
{
int num;
char name[20];
char sex;
float score;
}boy1,boy2;

你可以直接在boy2后面打个{ }初始化,在使用boy的时候我们可以具体到一个成员如boy1.num 即为boy1结构体的num成员

然后接下来其实更加常见的定义是这样子的

struct stu
{
int num;
char name[20];
char sex;
float score;
}*boy1,boy2; //boy1是结构体指针,boy2是结构体

这时候我们对指向结构体的指针标表示的成员方式有所不同,可表示为(*boy1).num或者boy1->num(熟悉吧,这里算是补充一下知识点)都可以。一般配合malloc(与free)或者c++中的new(delete)函数使用,主要是结构体指针自创立开始指向的空间就不存在,所以我们得开辟一个空间给他们. 

1.1理解一些易混概念

        本来吧,其实我真想按课本讲一遍,但是感觉有点浪费时间,而且课本那些加深不了我的理解,所以干脆我就直接把我的理解说了,如果有错,希望各位大佬指正!

温馨提示:接下来的话可能有点绕口令!!

第一:节(结)点

我们知道一个节点包括了他的数据域和他的指针域线性表:关于链表(主要以单链表为例)的相关理解和应用,链表,数据结构,c++,学习

数据域存放他的data,指针域存放下一个节点的地址,其中在第一个的叫做头结点,头结点链接的第一个节点叫做首节点,最后一个节点叫做尾结点。经常会出现R指针,我管他叫标记指针,用于记住我们要操作的节点的下一个地址,免得链表丢失,至少现在我知道的就是这点,其中^表示NULL。

ok,接下来,来解决几个知识,保证我们看得到接下来的代码,懂了应该就会写了吧

1.对指针赋值相当于就是让指针指向哪里

1.1:比如Lode *r=L;让r指向头结点L。

1.2:pre=p;(pre和p都是指针),让pre指向p(指向的地址)

1.3:p=p->next p指向下一位(详细一点:p->next在等号后面表示解引用,指的是p指向的结构体的指针域的地址(表示这个结构体的下一个地址))

1.4:r->next=p 这个指的是让r对应的结构体指向p(而非指针r指向p,此时的r相当于标记指针)

1.5:s->next=p->next;p->next=s;像这种我们就推荐画图理解

1.6:p=L->next->next表示p指向L的下下指针域而L->next->next=NULL则指的是L的下一个节点的指针域为空,如下图所示线性表:关于链表(主要以单链表为例)的相关理解和应用,链表,数据结构,c++,学习

 2.链表的基本功能

相信大家已经对链表有了初步的了解,现在我们来一个一个实现他们

2.1链表创建与初始化

typedef char ch
typedef struct LNode
{
    ch data;
    struct LNode* next;
}Linknode;
初始化
void InitLnode(LinkNode *&L){
L=new LinkNode;
L->next=NULL;
}

 2.2插入

这里就不得不讲讲插入的两种方法

2.2.1头插法

思路示意图如下:线性表:关于链表(主要以单链表为例)的相关理解和应用,链表,数据结构,c++,学习

LinkList Headinster(LinkList &L,int n){
    LNode *s;
    int x=1;
	L= (LinkList)malloc(sizeof(LNode));
    L->data=x++;
    L->next=NULL;
    while(x!=n){
        s=(LNode*) malloc(sizeof(LNode));
        s->data=x;
        s->next=L;
        L=s;
        x++;
    }
    return L;
}

核心代码

s->next=L->next;		①
L->next=s;				②

 作用效果就是从头结点和首节点插入新的元素,从而导致先插进来的反而在后面

这里借用一下大佬的动图(侵权删)

线性表:关于链表(主要以单链表为例)的相关理解和应用,链表,数据结构,c++,学习

2.2.2尾插法

顾名思义就是从尾部开始插入由于新的节点插入后成为新的尾部,所以我们需要用一个指针R去更新尾部节点(始终指向尾部)

线性表:关于链表(主要以单链表为例)的相关理解和应用,链表,数据结构,c++,学习

线性表:关于链表(主要以单链表为例)的相关理解和应用,链表,数据结构,c++,学习

大概像这样子

LinkList TailInster(LinkList &L,int n){
	int x=1;
	L= (LinkList)malloc(sizeof(LNode));
	LNode *s,*r=L;
	while(x!=n){
   		s=(LNode*) malloc(sizeof(LNode));
   		s->data=x;
  	 	r->next=s;
   		r=s;
   		x++;
	}
	r->next=NULL;
	return L;
}

核心代码

r->next=s;			//①r的指针域指向S(让新结点插入到链表)
r=s;				//②r指针指向s(保持r指针一直在链表尾端,方便插入新的结点)

 那么 现在我们继续写这个尾插法

//插入(使用尾插法)
void InsertLnode(LinkNode *&L,ch a[],int n)
{
    LinkNode *s,*r;
    r=L;
    for(int i=0;i<n;i++)
    {
        s=new LinkNode;
        s->next=a[i];
        r->next=s;
        r=s;
    }    
    r->next=NULL;
}

2.3链表的展示

void DisplayLinkNode(LinkNode *L)
{
    LinkNode *p=L->next;
    while(p!=NULL)
    {
        cout<<p->data<<"   ";
        p=p->next;
    }
    cout<<endl<<endl;
}

 2.4链表的长度

int LinkNodeLength(LinkNode *L)
{
    LinkNode *p=L;
    int n=0;    
    while(p->next!=NULL)//注意头结点不算我们的链表长度
    {
        n++;
        p=p->next;
    }
    return n; 
}

2.5链表中取值

bool Getlink(LinkNode *L,int n,ch &e)
{
    if(n<=0)
        return false;
    LinkNode *p=L;
    int j=0;
    while(j<n&&p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return false;
    else
    {
        e=p->data;
        return true;
    }
}

记忆方法:创建指针,遍历一下,判断是否为空,否则为可取之值 

 2.6链表中删除

bool DeleteNode(LinkNode *&L,int n,ch &e)
{
   if(n<=0) 
        return false;
    LinkNode *p=L,q;
    int j=0;
    while(j<n-1&&p!=NULL)//注意删除代码停在删除元素的前面
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return false;
     q=p->next;
     if(q==NULL)
        return false
     e=q->data;
     p->next=q->next;
     delete q;
     return true;  

}

记忆方法 建立两个指针,遍历到删除元素的前一个,用p指向删除元素,然后进行交换

2.7新的插入

bool insertnode(LinkNode *&L,int i,ch e)
{
     if(i<=0)
        return false;
    LinkNode *p=L,*s;
    int j=0;
    while(j<n&&p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL||p->next==NULL)
        return false;
    s=new LinkNode;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

记忆方法:创建一个新节点,类似头插法的方式插进去 

小作业 

线性表:关于链表(主要以单链表为例)的相关理解和应用,链表,数据结构,c++,学习线性表:关于链表(主要以单链表为例)的相关理解和应用,链表,数据结构,c++,学习

#include <iostream>
using namespace std;
typedef char ch;
typedef struct LNode {
	ch data;
	struct LNode*next;//指针域:存放下一个节点的地址
} LinkNode;
//初始化
void InitList(LinkNode *&L) {
	L = new LinkNode;
	L->next = NULL;
}
//插入(尾插法)
void Insertlist(LinkNode *&L, ch a[], int n) { //传入想插入的数组(1,2,3,4),则此法插完后亦是(1,2,3,4)
	LinkNode *s, *r; //创建两个指针
	r = L; //r指向首节点L
	for (int i = 0; i < n; i++) {
		s = new LinkNode; //创建空间
		s->data = a[i]; //数据存储(值得注意的是s是指针)
		r->next = s; //r->next表示L的next指针域,其实就是赋值,将s的地址(s本身就是地址)赋给L的next域,相当于是L--s
		r = s; //然后将r指向s
	}
	r->next = NULL; //最后r指向末节,指针域为NULL
}
//输出
void Displaylist(LinkNode *L) {
	LinkNode *p = L->next; //这里注意一下,其实首节点是没有数据的,直接指向下一个节点打印
	while (p != NULL) {
		cout << p->data << "  ";
		p = p->next;
	}
	cout << endl << endl;
}
//输出长度
int Listlength(LinkNode *L) {
	int n = 0;
	LinkNode *p = L;
	while (p->next != NULL) {
		n++;
		p = p->next;
	}
	return n;
}
//判断是否为空
bool emptyelem(LinkNode *L) {
	if (L->next == NULL)
		return false;
	else
		return true;
}
//取值
bool Getelem(LinkNode *L, int n, ch &e) {
	if (n <= 0)
		return false;
	LinkNode *p = L;
	int j = 0;
	while (j < n && p != NULL) {
		j++;
		p = p->next;
	}
	if (p == NULL)
		return false;
	e = p->data;
	return true;
}
//输出位置
int Locelem(LinkNode *L, ch e) {
	LinkNode *p = L->next;
	int j = 1;
	while (p != NULL && p->data != e) {
		p = p->next;
		j++;
	}
	if (p == NULL) {
		return 0;
	}

	return j;
}
//指定位置插入元素
bool insertlist(LinkNode *&L, int n, ch q) {
	if (n <= 0)
		return false;
	int j = 0;
	LinkNode *p = L, *s;
	while (j < n - 1 && p != NULL) {
		j++;
		p = p->next;
	}
	if (p==NULL||p->next == NULL)
		return false;
	else {
		s = new LinkNode;
		s->data = q;
		s->next = p->next;
		p->next = s;
		return true;
	}
}
//删除指定元素
bool Delem(LinkNode *&L, int n, ch &e) {
	if (n <= 0)
		return false;
	int j = 0;
	LinkNode *p = L, *q;
	while (j < n - 1 && p != NULL) {
		j++;
		p = p->next;
	}
	if (p == NULL)
		return false;
	q = p->next;
	if (q == NULL)
		return false;
	e = q->data;
	p->next = q->next;
	delete q;
	return true;
}
//释放
void Destroylist(LinkNode *&L) {
	delete L;
}

int main() {
	LinkNode *L1;
	InitList(L1);
	cout << "1.初始化单链表成功!!!" << endl << endl;
	//插入
	ch a[10] = {'a', 'b', 'c', 'd', 'e'};
	cout << "2.依次插入abcde." << "尾插法" << "    ";
	Insertlist(L1, a, 5);
	cout << "插入成功!!!" << endl << endl;
	//打印
	cout << "3.当前的单链表为:  ";
	Displaylist(L1);
	//输出长度
	int n = Listlength(L1);
	cout << "4.当前单链表的长度为:" << n << endl << endl;
	//判断链表是否为空
	cout << "5.当前链表";
	if (emptyelem(L1))
		cout << "不为空表" << endl << endl;
	else
		cout << "为空表" << endl << endl;
	//取值(输出元素)
	cout << "6.取值操作:";	int l;ch e;
	cout << "请输入您要取哪个位置的值:";cin >> l;
	if (Getelem(L1, l, e))
		cout << "取值成功! " << "单链表第" << l << "位的元素是:" << e << endl << endl;
	else
		cout << "取值失败,您输入的位置" << l << "越界!!!" << endl << endl;
	//查找
	cout << "7.查找操作:";ch find;
	cout << "请输入您要查找的元素:  ";
	cin >> find;
	if (Locelem(L1, find) == 0)
		cout << "对不起,当前单链表中没有您查找的元素!!" ;
	else
		cout << "查找成功,您所查找的元素" << find << "在当前单链表的第" << Locelem(L1, find) << "位" ;
	cout<<endl<<endl;
	cout << "8.插入操作:";int k;ch q;
	cout << "请您输入一个数字和一个字符,代表在第几位插入一个字符:";cin >> k;cin >> q;
	if (!insertlist(L1, k, q))
		cout << "Warning:输入序号越界,插入失败!!!" << endl;
	else
		cout << "插入成功!!!" << endl << endl;
	cout << "9.当前单链表的元素有:";
	Displaylist(L1);
	cout << "10.删除操作:";int y;ch o;
	cout << "请您输入要删除的元素的序号:";cin >> y;
	if (!Delem(L1, y, o))
		cout << "对不起,您的输入的序号有误(越界),删除失败!" << endl << endl;
	else
		cout << "删除成功!成功删除第" << y << "个元素" << o << endl << endl;
	cout << "11.当前单链表的元素有:";Displaylist(L1);
	//释放
	cout << "12.销毁单链表:";Destroylist(L1);
	cout << "销毁成功!!!";
	return 0;
}

 全部失败的样例:9,p,8p,7

线性表:关于链表(主要以单链表为例)的相关理解和应用,链表,数据结构,c++,学习

全部成功的样例:4,c,2p,6

线性表:关于链表(主要以单链表为例)的相关理解和应用,链表,数据结构,c++,学习

所以建议大家自己打吧,看完上面的写这个代码就很轻松 

感谢您今天的捧场,敬请期待下次演出。 See you next  illusion.

线性表:关于链表(主要以单链表为例)的相关理解和应用,链表,数据结构,c++,学习文章来源地址https://www.toymoban.com/news/detail-845967.html

到了这里,关于线性表:关于链表(主要以单链表为例)的相关理解和应用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 使用SQL语句创建实验数据库(以学生表为例)

     (1) 创建数据库stuexpm create database stuexpm   (2) 创建studentinfo表,显示studentinfo表的基本结构 use stuexpm create table studentInfo ( StudentID varchar(6) not null primary key comment \\\'学号, Name varchar(8) not null comment\\\'姓名‘, Sex varchar(2) not null default \\\'男\\\' comment\\\'性别\\\', Birthday date not null comment\\\'出生日期

    2024年02月07日
    浏览(57)
  • 以链表为基础实现链式队列

    以链表为基础实现链式队列 1.思路: 如果打算以链表作为基础来实现队列的操作,可以避免内存浪费以及避免内存成片移动,只需要确定队头和队尾即可,一般把链表头部作为队头,可以实现头删,把链表尾部作为队尾,可以实现尾插。 2.图示: 3.代码: 4.结果验证:

    2024年04月26日
    浏览(45)
  • 线性代数·关于线性相关和线性组合

    我本来对线性相关和线性组合的理解是,如果几个向量线性相关,那么等价于他们可以互相线性表示。但其实这是一个误区。 线性相关是对一组向量之间的关系而言的,这里面会存在极大线性无关组。极大线性无关组确定了一个空间,线性相关表示向量都落在这个空间里,会

    2024年02月12日
    浏览(52)
  • 关于线性结构中的双向链表如何实现?

    在上一篇文章中,主要是给大家介绍了单向链表的特点及其原理,但是我们没有通过代码进行练习。今天我会继续通过一篇文章,来给大家讲解双向链表的内容,尤其是会通过代码来进行链表的操作,希望大家重点关注哦。 全文大约【 3500】 字,不说废话,只讲可以让你学到

    2024年02月09日
    浏览(57)
  • 第1关:单循环链表的实现—链表的添加、遍历任务描述相关知识单循环链表添加操作遍历循环链表编程要求测试说明任务描述在操作单链表时,

    第1关:单循环链表的实现—链表的添加、遍历 200 任务要求 参考答案 评论42 任务描述 相关知识 单循环链表 添加操作 遍历循环链表 编程要求 测试说明 任务描述 在操作单链表时,我们有时希望从单链表中的任一结点出发都能遍历整个链表,但对于单链表来说,只有从头结点

    2024年02月06日
    浏览(47)
  • 关于线性结构中的双向链表如何实现的方法

    在上一篇文章中,主要是给大家介绍了单向链表的特点及其原理,但是我们没有通过代码进行练习。今天我会继续通过一篇文章,来给大家讲解双向链表的内容,尤其是会通过代码来进行链表的操作,希望大家重点关注哦。 全文大约【 3500】 字,不说废话,只讲可以让你学到

    2024年02月16日
    浏览(36)
  • 数据结构上机实验——图的实现(以无向邻接表为例)、图的深度优先搜索(DFS)、图的广度优先搜索(BFS)

      图采用邻接表存储结构,编程实现图的深度优先搜索和广度优先搜索算法。              2.1创建图 2.1.1定义图的顶点、边及类定义   我们定义一个 邻接表类(ALGraph) 。这里实现一些基础的数据结构。要注意结构体的嵌套。    Edge: 用于表示图中的边

    2024年02月04日
    浏览(54)
  • 西工大NOJ数据结构理论——013.以十字链表为存储结构实现矩阵相加(严5.27)

      我第一下拿到这个题目,第一反应就是先 定义好数据结构 ,然后构建好十字链表基础操作的函数,也就是“ 创插遍历 ”这些操作。下面是我的定义和函数操作。 typedef int ElemType; typedef struct OLNode{     int i,j;//行号和列号     ElemType elem;     struct OLNode *right;//右边元素 

    2023年04月26日
    浏览(85)
  • 线性代数的学习和整理20,关于向量/矩阵和正交相关,相似矩阵等

    目录 1 什么是正交 1.1 正交相关名词 1.2 正交的定义 1.3 正交向量 1.4 正交基 1.5 正交矩阵的特点 1.6 正交矩阵的用处 orthogonal set 正交向量组 正交变换 orthogonal matrix 正交矩阵 orthogonal basis 正交基 orthogonal decomposition 正交分解 正交的定义:内积为0 正交一定线性无关 其实不共线也

    2024年02月09日
    浏览(59)
  • 线性代数的学习和整理20,关于向量/矩阵和正交相关,相似矩阵等(草稿)

    目录 1 什么是正交 1.1 正交相关名词 1.2 正交的定义 1.3 正交向量 1.4 正交基 1.5 正交矩阵的特点 1.6 正交矩阵的用处 orthogonal set 正交向量组 正交变换 orthogonal matrix 正交矩阵 orthogonal basis 正交基 orthogonal decomposition 正交分解 正交的定义:内积为0 正交一定线性无关 其实不共线也

    2024年02月09日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包