? 此博客所有内容均基于个人对數据结构的理解仅供参考,若发现任何错误希望得到指点衷心希望此内容对您有所帮助!接下来让我们一起来学习数据结构吧!
首先峩们学习之前必须保证具有一点的C语言基础,整个数据结构几乎是基于结构体和指针如果对结构体和指针不是很了解,建议先去对结构體和指针有一定的了解此内容只包括方法实现,并没有线性链表数据结构思想
在解释之前必须清楚一个概念:我们创建了一个数据类型,大家都知道都知道的数据类型有int、double…我们创建的数据类型是Lnode型它包含两种数据类型,也可以说它是这两种数据类型的综合体它总昰“两两”出现的。
typedef是“定义的意思”例如
就是将 int 定义为Elemtype,在编写代码中Elemtype就可以当作int来用,所以代码中的“Elemtype”可以代表任何数据类型
上代码是定义一个结构体Node,此处的Node只是一个结构体的标识结构体真正的名字为Lnode。但标识也有用处例如“struct Node *next;”,就是在我们创建的结构體内部定义一个此结构体类型的指针通俗来讲就是这个指针指向Lnode结构体。
最后一行是说明这个结构体的名称是Lnode(可以理解为创建了一个數据类型为Lnode)*LinkList是指向这个结构体的指针类型,通俗来讲就是LinkList这种类型是指向Lnode的指针例如
意思就是L是指向Lnode的指针变量。
小结:这只是为創建线性链表数据结构(以下称单链表数据结构)做准备创建了一个数据类型,这个数据类型包含数据域(data)和指针域(*next)我们后边會定义一个LinKList类型的变量L作为头指针。
1.2线性链表数据结构的初始化(分配结点空间)
? 这是一个初始化函数所谓初始化就是为单链表数据结构结点分配空间,或者说分配一个结点空间“L =
(LinkList)malloc(sizeof(Lnode));”是分配一个Lnode类型的空间,返回值为地址即“L”为这段空间嘚指针。分配的结点空间可以是头结点也可以是普通结点(这里是头结点)。我们可以利用结点做头结点或者做普通结点用添加数据、暫存数据、转存数据等等也就是我们所操作的最小单元,我们所有的操作都在其之上也可以把它看作普通的数组,就是操作方式比较繁琐
1.3尾插法创建单链表数据结构
printf ( "请输入要插入的值,当输入为-1时停止输入\n" ) ;
? 尾插法是比较简单的操作,有助于链式操作的理解和掌握(Init_Linklist(L);)首先我们分配了一个头结点空间,由于头指针不可丢失,(p = L;)所以操作时用p备份这是添加结点的操作,我们需要创建新结点(Init_Linklist(temp);)temp将偠变量x存入新结点的数据域且将此结点的指针域设为空。(p->next =
temp;)将此指针赋予尾结点的指针域(p = p->next)保证p是尾结点的指针。小结:尾插法操作只涉及到了尾结点较为简单。
1.4关于取地址符“&”的解释(为什么在函数的参数前添加取地址符(&L))
这是关于C++中的一个语法,叫莋引用对于引用,我查阅一些资料虽然也没能彻底搞明白,却也从另一个容易理解的角度获得了自己的一些认识,与大家分享(我們也可以直接百度)下面我做一些解释,帮助大家理解首先我们搞清楚“L”是什么?L是LinkList类型的指针变量LinkList类型的变量纷纷指向Lnode结构体(湔面我们已经知道Lnode是一种数据类型,一种包含两部分的数据类型)下面我们以初始化函数为例对引用进行解释。
此函始中“L = (LinkList)malloc(sizeof(Lnode));”明显改变叻变量L的值。在学习C语言中我们都知道传入函数变量是形参,传入只是具体变量的值在函数中无论值怎么改变,对于此函数外(主函数內)的变量并没有影响在这里也一样,如果不加取地址符“&”也不能改变L的值,那么我们的初始化也是没有意义的
? 对单链表数据结構的基本操作:单链表数据结构的遍历、增删查改以及各种特殊操作。我们下面主要是对各个函数的实现以及解释
单链表数据结构的遍曆没有什么难于理解,主要是清楚我们对单链表数据结构一个一个节点操作的过程还有一点,关于指针越界问题指针越界直接导致程序运行失败,所以我们在操作指针向后移位时最好将它封闭。例如“while§”,当p=NULL时循环里的操作就无法运行(如果p指向空,再进行移位就会造成空指针异常,也就是指针越界)另外为了加深大我们对上述引用的理解,在此多数几句在此函数中,我们并没有对单链表數据结构进行改变所以不需要添加取地址符。没有添加取地址符我们就无法改变变量L的值。那么我们就没必要担心丢失头节点L函数鈳以改成以下。
2.2计算单链表数据结构的长度
? 计算单链表数据结构长度与遍历单链表数据结构差不多只是将打印“ printf("%d ", L->data);”换成了“count++;”,此函數返回值为单链表数据结构长度
2.3单链表数据结构的逆置(头插法)
? 单链表数据结构的逆置主要运用了头插法,前面我们知道尾插法较為简单但是头插法理解起来较为困难。首先我们需要两个指针p和qp为顺寻指针,从第一个节点到最后一个节点保证将全部节点逆置q则指向操作节点。首先“q->next = L->next;”即节点q的指针域指向第一个节点(第一个节点成为q节点的后继)再者“L->next =
q;”即q节点成为头节点的后继(q节点成为单链表數据结构的第一个节点)。
2.4删除为偶数的节点
? 删除节点必定要释放内存最好不要用L变量直接操作,所以所以我们定义了两个变量p和qp仍為循序指针,为的是遍历所有节点q则为操作节点。我用单链表数据结构的长度做封闭(这样做确实有指针越界的风险但是我改良了很玖,也没有成效我承认这个函数写的不怎么样,只能如此了希望大家能有所改进)。主要其实就是一个判断如果此节点是是偶数,则讓此节点的后继成为此节点前驱的后继(p->next =
2.5插入函数和生成非递减单链表数据结构
25.1插入元素函数的实现
? 此函数是“一次性”函数每次可插叺一个元素(默认升序),此函数在生成非递减单链表数据结构函数应用此函数满足空表插入,当L为空表时则循环体不运行(见循环下紸释)。当不为空表时则进入循环体进行判断,如果运行到最后一个节点时仍未找到合适位置则跳出循环体,运行下方语句将此节作為单链表数据结构的尾节点。
2.5.2生成非递减单链表数据结构
printf ( "请输入要插入的值当输入为-1时,停止输入\n" ) ;
? 已有插入函数在创建非递减有序單链表数据结构时,只需初始化一个头结点然后将插入函数放入循环体中,逐个插入
两个非递减有序单链表数据结构La和Lb合并成一个非遞减有序链表数据结构Lc
? 注释较为详尽,而且对于两个非递减有序单链表数据结构合并生成一个非递减有序单链表数据结构还是相对简單的。我们只需比较La中与Lb中元素逐个以尾插法插入Lc中 若La元素小于Lb元素,则让La元素以尾插法插入Lc中La对比元素位置向后移位,Lb对比元素位置不变反之亦然。当La或者Lb任意一个所剩元素(节点)数为零时跳出第一个循环体。剩下的两个循环体则将La或者Lb中剩余元素可直接插入Lc尾
兩个非递减有序单链表数据结构La和Lb合并成一个非递增有序链表数据结构Lc
? 比较两个非递减有序单链表数据结构La和Lb合并成一个非递减有序链表数据结构Lc,我们只需要将尾插法插入改为头插法插入即可(对于头插法我也是花了一定时间才能理解可能人和人不一样,自己领悟吧峩感觉我是够笨的)。
2.7将链表数据结构La按值分解为偶数表和奇数表
* 链表数据结构La按值分解成两个链表数据结构La全部为奇数,Lb全部为偶数* /
此函数也不难理解我们只需判断是否为偶数,然后进行取出操作以及尾插法插入注释较为详尽,可供参考
? 通过这次学习我受益良多,在这里与大家分享一下这次学习使我对数据类型有了更深的理解,无论是什么数据类型只要它是数据类型的一种,那么它所声明的變量也一定遵循普通变量的一般规律就拿C++语法引用为例,LinkList类型的变量L就遵循一般规律。