数据结构—链表-建立单链表

时间:2024-04-13 11:34:44

数据结构—链表-建立单链表
我们这里的单链表定义为char型,其他类型是一样的做法

数据结构—链表-建立单链表
s->next=p->next;
s这个指针指向的节点就和p的下一个节点连接起来了。
p->next=s;
注意:这两个语句不能交换
然后p->next是一个指针 s也是一个指针
s是一个指向某一个节点的指针。
p->next=s;
代表p->next指向了s指向的节点。不代表p->next和s等价
当s指向其他区域后,p->next就和s指向的区域就不同了

数据结构—链表-建立单链表

为了实现删除操作
是将p->next=b->next(p->next->next);
此时p就不指向b了 b相当于在这个链表之外了
但是一般我们使用一个额外的q指针=p->next 即p=b 即p指向了b指向这块位置,注意此时的b并不是实际存在的而是p->next的方式存在的,我们使用q代表我们可以释放p->next这块区域的内存,而直接p->next=b->next我们就丢失了。

建表:头插法,尾插法
数据结构—链表-建立单链表
数据结构—链表-建立单链表

头插法逻辑位序和物理顺序是不一样的,是刚好相反的。
明确算法
L是头指针,指向头节点。
用对指针的引用,这样才能反馈给实际指针
首先我们应该分配头节点的空间,然后L即头节点的L->next指向NULL
进入一个循环,
首先为s指针分配一块空间,他是我们期望得到的类型的空间。
然后让s->data存储数据,再让s->next=L->next即让s->next指向空,然后让L->next指向s,注意L L->next s s->next都是指针
这其实是插入节点的操作,这样我们就得到了n个节点。形成了一个链表。
数据结构—链表-建立单链表
尾插法和头插法差不多,但是在算法(函数内)定义了两个指针
r指针和s指针
r指针等于L指向头节点
然后进入循环,首先还是为s指针赋予一片空间,此时这片空间就是节点,然后输入数据域,s->data=a[] 此时的a[i]是数据域,当然数据域也可以是其他任何东西。
然后r现在是头指针(L此时也是头指针)注意指针和内存的关系。
r->next即头节点的next指针,指向s,r->next=s;这是头节点连接到了下一个节点。
然后,r=s;此时r不再指向头节点,但是头节点依然存在,L指向着头节点,头节点没有丢失。
r=s的意义在于r和s此时指向的是同一个节点。
再次循环时,r相当于又一个头节点,s又被重新赋予一片空间(即节点),再次重复这个过程,但是这个过程是顺序的,他的物理位序和逻辑位序是一致的。

最后退出循环时,r->next指向NULL。