数据结构初解之单链表分析篇

只看该作者 · 2019-4-27 20:35

一、头文件

例：#include<stdio.h>

#include<stdlib.h>

分析：

1、stdio.h可以说是最基本的头文件，scanf和printf函数都在里面。

2、stdlib.h中包含malloc()函数。

只看该作者 · 2019-4-27 20:35

二、宏定义

例：#define QUIT -1

分析:

1、QUIT是自定义的在链表中输入数据的结束符号。

2、宏定义和类型定义符的功能很相似。但是宏定义是由预处理完成的，所以它带有预处理指令符#，而类型定义符typedef就没有。但是typedef语句后面要有“；”。

3、关于#define更详细的知识可以查找其他资料。

只看该作者 · 2019-4-27 20:35

三、使用类型定义符typedef将int转换成elemtype

例：typedef int elemtype;

分析：

1、定义不同的数据类型是为了程序的可读性，比如其他程序员一看到elemtype x；就知道x是结构体里面的数据。这样可以与普通的int型数据区分开。

2、便于修改，比如结构体需要的数据不再是int型，而是double型，则只需要将typedef int elemtype;修改为typedef double elemtype;就行了，不用再一个一个去修改。

注：其实使用typedef的好处基本上就是这两个方面：增强程序的可读性和便于程序修改。

有事也可以用宏定义来代替typedef的功能，但是宏定义是由预处理完成的，而typedef则是在编译时完成的，后者更为灵活方便。

只看该作者 · 2019-4-27 20:36

四、使用类型定义符typedef定义结构体

例：

typedef struct LNode

{

elemtype data;

struct LNode *next;

}LNode,*LinkList;

分析：

1、第一个typedef struct LNode{}LNode;第一个LNode是结构体名，这个LNode可以去掉，因为在C语言中无名结构体是合法的。这组语句的编译过程是这样的：先编译struct LNode{}从struct开始到“}”结束，表明定义了一个结构体。然后，编译结构体中的内容，因为这个时候结构体struct LNode已经呗编译定义了，所以结构体里面可以使用struct LNode来定义新的变量，但是，typedef还没有编译，所以struct LNode还不能简写成LNode，也就不能用LNode来定义变量了。最后，编译typedef struct LNode{}LNode，*LinkList；这一步是将struct LNode简化成LNode，将struct LNode *简化成LinkList；所以struct LNode x；=LNode x； struct LNode *p；=LinkList p；。当然，LNode *p；=LinkList p；等效。同时，因为结构体的编译是最先开始的，而类型定义符是最后开始编译的，所以结构体名和简化成的名字可以相同，当然第一个LNode是可以去掉的。

2、结构体的全称应该是struct LNode，如果没有用typedef简化的话，struct是不能省略的，因为这样在C语言中是不合法的，但是在C++语言中却可以省略struct。

对于在结构体struct LNode中还可以使用struct LNode定义变量还有一种解释：“对于非完全类型，此时能够使用使用其引用或者指针，而不能使用对象，因为对象会分配空间，而此时它的类型都不存在，谈何对象？

而指针和引用则可以使用，因为它并非一定指向了某一实例。”。这种解释较难理解，可以参考资料http://docs.oracle.com/cd/E27071_01/html/E26437/bjals.html#bjalt

总之，在括号外面定义的是结构体，意思就是我要定义一个结构体了，里面有什么什么数据，而在里面定义的*next结构体类型的指针，意思是，我定义的结构体每个结点里面有个指针指向的是结构体类型的数据，不是重新定义，一个指针类型的成员是可以指向自己所在结构体类型的数据的。所以“在结构体struct LNode中还可以使用struct LNode定义变量”是合法的。

3、从例子中可以看出，next和LinkList的定义相同（struct LNode *next；struct LNode *LinkList），但是为什么一个成了指向下一个节点的指针，一个成了链表指针。其实，next和LinkList的类型、用法什么的都是一样的，只是因为放的位置不同，造成作用有所差别，但是本质没改变，都是指向结构体的指针。打个比方来理解一下：原高一（一）班的学生在高二的时候要分文理科，一部分学生去了文科，学习语数外政史地；一部分学生去了理科，学习语数外理化生。但是他们每一个都是原高一（一）班的学生，本质上没有区别。文科里面的学生你不能说他没有学习理化生的能力，理科生你同样不能说他没有学习政史地的能力。同理，next是指向下一个节点的指针，但它同样有做链表指针的能力，LinkList也可以做节点指针。next指向的是节点，但节点就是结构体，所以它指向的还是结构体，LinkList是链表指针，但链表是结构体组成的，所以LinkList还是指向结构体的指针，本质都没有发生改变。

那么，next和LinkList因为放置的位置不同而作用又分别是什么呢？

*next在结构体里面，也就是每个节点里面，它的作用是链接本节点和下一个节点，因为*next包含在每一个节点里面（结构体里面），所以我们通常都是通过对next的操作来寻找、插入、删除某个节点。所以我们经常看到xxx->next=xxx；等。

*LinkList定义在结构体的外面，所以它不包含在每一个节点里面，所以它只具有指向作用，不具备查找、插入、删除这些功能。我们一般用它来定义新的结构体指针变量。所以我们经常看到LinkList L，p，q；等。（很有意思的是：L我们习惯上作为头指针，而p和q就是后妈的孩子，随便多了。但是，L、p和q本质又都是都一样的，这一点和*next与*LinkList的差异异曲同工。）

总之，*LinkList相当于一个数组的头指针，只不过这个数组的元素是结构体罢了。*next是数组元素（结构体）里面的一个指针，用来指向下一个数组元素，只不过这个数组元素是结构体罢了。*LinkList是指定了可以申请的节点空间（结构体空间）在内存中的位置。而*next则是对所有的节点（结构体变量）进行一定的排序。

八个字总结一下：大家默认，习惯使然。大家默认的都这么用，我们就随大流一样用，所以，不必过分纠结。

4、LNode和LinkList之间为什么可以用逗号链接？如果我们定义两个整形变量a和b，我们可以写成int a；int b；也可以写成int a，b；同样的道理，typedef struct LNode LNode，*LinkList相当于typedef struct LNode Lnode；和typedef struct LNode *LinkList；。

数据结构初解之单链表分析篇

相关下载

相关帖子