这是卡尼慕的第n篇文章
小知识
OK!今天来复习一下数据结构中最最最基础的链表。
首先一定要区别一下两个概念:线性存储结构和非线性存储结构。
线性存储结构
像我们排队吃饭等叫号一样,一个接着一个,1号后面是2号,2号后面是3号,如此类推。
线性结构有唯一的首元素(第一个元素),
线性结构有唯一的尾元素(最后一个元素)。
除首元素外,所有的元素都有唯一的“前驱”,
除尾元素外,所有的元素都有唯一的“后继”。
那么线性结构有什么经典的例子呢?
队列、线性表、堆、栈。
非线性存储结构
相比于线性结构,一个元素的后面可能排着不止一个人,也就是数据元素之间是一对多,或者是多对一的关系。
例如:树(层次结构)、图(群结构)、多维数组。
一维数组与链表
OK,那开始我们的正题,假如我这里有4个数:2,3,5,8。我希望将数存储起来,那可能你的第一反应是:很简单啊,使用一个数组就行了呀,array[4]。没错的,确实可以使用一维数组直接存储,那么我现在又想在这四个数后面再加四个数呢?你可能会说:也很简单啊,重新定义数组,改成array[8],就行了啊。
那假如我们在测试程序前并不知道我们需要多少个数怎么办呢,我们不可能说这个程序不停地根据用户的需求去更改吧,所以这里我们需要另外一个数据结构——链表来存储。
相比于普通的一维数组,链表看起来更加灵活,链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。从内存上看, 链表从堆中分配空间, 自由度大但是申请管理比较麻烦.。
百度是这么说的:链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
更好的理解,请看图:
如上图,head是头指针,指向链表的首节点(节点的地址:1200),在这个1200的地址上,我们存储了一个数据(12),同时也存储了下一个节点的地址(2000),接着在地址为2000的节点上存储着下个节点的地址和数据,如此类推,直到最后一个节点(注意:最后一个节点存储的指针必须指向NULL,否则该链表将会指向未知的随机地址上)
节点的组成
那么现在来看看我们代码是怎么实现的吧!
首先我们要考虑,链表由一个一个的节点连接起来,节点又是由一个数据域(用于存储数据)和指针域(用于指向下一个节点)组成,因此我们需要一个结构体来描述一个节点。
节点包括:
1、数据域,一种类型的数据,可以是int,可以是double等。
2、指针域,指向结构体(节点)的类型的指针。
typedef int ElemType; //指定元素类型为整型
//定义结点类型
typedef struct Node {
ElemType data; //单链表中的数据域
struct Node *next; //单链表的指针域
}Node,*LinkedList;
单链表初始化
接下来,就是使用节点来初始化一个链表!怎么做呢?请看!
首先这个函数(方法)的返回值必须是一个节点类型的指针,因为我们需要该指针来访问链表。
然后创建一个指针参数,并且指向一个malloc / new(申请节点空间)的节点(这个节点是首节点,我们一般称为头节点)。
接着我们要判断是否申请空间成功(也就是创建头节点成功),我们使用一个if条件句来判断。并且使指针指向NULL,这样保证尾指针始终为NULL(这个很重要,不要忘了!)。
最后返回我们创建的指针参数就好了!那个指针参数就是我们需要的头指针。
LinkedList LinkedListInit()
{
Node *L;
L = (Node *)malloc(sizeof(Node)); //申请结点空间
if(L == NULL) //判断是否有足够的内存空间
{
printf("申请内存空间失败\n");
}
L->next = NULL; //将next设置为NULL,初始长度为0的单链表
return L; //返回头指针以便我们使用
}
单链表的建立
单链表的节点创建常用的方法有两种:尾插法,头插法。不同的方法的选择就取决于个人的需求,没有说哪一种方法一定比另外一个好,总体的思路是一样的,无非一个是变动尾指针,而另一个是变动头指针。
那我就讲讲尾插法。思路一样,不难。
老样子,跟初始化单链表一样。先设定一个指针指向一个新分配的内存空间,并使新的节点的指针指向NULL,并且给数据域赋值。
接着,我们怎么才能把这个已经赋值完成的节点接到链表的尾部呢?
很简单,首先遍历原来已有的链表(已知头节点,很方便),然后把尾节点的尾指针指向新节点的地址就完全OK了!很简单吧!
void InsertList(PNode List, int pos, int val) {
int position = 0;
PNode P = List; // 定义节点p指向头节点
// 寻找pos节点的前驱结点
while (P != NULL && position<pos - 1)
{
P = P->Next;
++position;
}
PNode Tmp = (PNode)malloc(sizeof(Node)); // 分配一个临时节点用来存储要插入的数据
if (Tmp == NULL)
{
printf("内存分配失败!");
exit(-1);
}
// 插入节点
Tmp->Element = val;
Tmp->Next = P->Next;
P->Next = Tmp;
}
单链表节点的删除
那怎么移除一个节点呢?
同理啦!有指针都好办事,只要把要删除的节点的内存free掉,并且使前节点的指针指向后一个节点的地址,就完成了删除。
int Deletelist(node *head,int dn)
{
if(dn>0&&dn<=n){
n--;
node *p,*pre;
pre=head;
p=head->next;
int count=1;
while(p){
if(count==dn){
pre->next=p->next;
delete(p);
p=NULL;
return 1;
}
count++;
pre=pre->next;
p=p->next;
}
}
return 0;
}
单链表的查询
单链表的不好的一点就是没有索引,没办法一下子确认某个数所在的节点的位置。
思路也很简单,先读取被查询的数据,才从头节点开始遍历,一边next一边比对数据域中的数据是否一致,如果正常循环到NULL,就说明被查询的数据不在链表中,反之就可以找到该数据。
PNode FindList(PNode List) {
PNode P = List->Next; // 定义临时指针P指向首节点的地址
int num = 0; // 用于记录链表节点位置
int val = 0; // 用于存放要查询的值
printf("请输入要查询的数:");
scanf_s("%d", &val); // 输入要查询的数值
while (P != NULL&&P->Element != val) {
P = P->Next;
++num;
}
if (P != NULL)
printf("找到的节点为:%d", num + 1);
else
printf("找不到该节点");
printf("\n");
return P;
}
删除整个单链表
删除整个链表比删除单个节点要稍微简单点,具体思路就是一遍遍历链表,一边free节点,直到遇到NULL。
void DeleteTheList(PNode List) {
PNode P, Tmp;
P = List->Next; //定义指针P指向链表要删除的链表List的第一个点节点
List->Next = NULL;
while (P != NULL) {
Tmp = P->Next; //临时Tmp指向要删除的节点的下个节点
free(P); //释放指针P指向的节点
P = Tmp; //重新赋值
}
printf("删除链表成功!\n");
}
循环链表 与 单链表 与 双向链表
循环链表很好理解,听名字就是了,循环,把一条直线头尾相连,成了一环状,就是循环链表,也就是把尾指针从NULL变成指向头节点。
双向链表呢也很简单,就是在结构体中多添加一个指针指向前驱,方便查询,但是在添加和删除操作就需要多加一步。
一般就看需求来选择使用怎样的链表,可以巧妙地变换数据结构为自己所用。
总结
1、链表不难。
2、链表相比与一维数组更加灵活,随意添加随意删除,只要内存够,随意数量。但是失去快速定位能力(索引)。
3、基本操作:初始化,增删查改。
4、单链表与双向链表与循环链表的区别了解一下。
5、源码看我的GitHub,欢迎批评,你批评我会改。