目录

创建文件:

具体实现:

首先是头插。

注意:一定要注意:再定义tmp时,要给它赋一个初始值(推荐使用 new list_next)

接着是尾插:

随后是中间插:

然后是最简单的改值:

随后是删头:

一定要注意(size–)

删中间:

末尾:

oh,对了:


我们知道单链表,今天博主(也就是我)自己手写了一个单链表(用指针写的)现在我来分享一下。

创建文件:

我用三个来写(list.h,listfun.h,run.cpp)(run.cpp)用来调试

具体实现:

list.h

#include#include#include#includestruct list_next{//链表的一个值int value;struct list_next *next;};struct list_make{//一条链表的结构list_next *head;list_next *tail;int size;};//void head_add(list_next* &head,int v,int &size);//头插 //void tail_add(list_next* &tail,int v,int &size);//尾插 //void add_node(list_next* head,int p,int v,list_next* tail,int &size);//插入 //void change(list_next* head,int p,int v);//改值 //void head_del(list_next* &head,int &size);//头删 //void del_node(list_next* head,int p,list_next* &tail,int &size);//删除//void init(list_make &p,int v) //初始化 

接下来就是核心的listfun.h

首先是头插。

函数定义:

void head_add(list_next* &head,int v,int &size)

(这里用了引用,不会的童鞋们请看->引用教程

先用图来演示:(左边是值,右边是next域)

​​​​​​​

上图是原来的样子,tmp是要插入的数。

list_next* tmp=new list_next;tmp->value=v;

接着把tmp的next改成head。

tmp->next=head;

再把头换成tmp。

head = tmp;

最后,size+1(因为长度增加了)

size++;

所以头插代码就是:

void head_add(list_next* &head,int v,int &size){list_next* tmp=new list_next;tmp->value=v;tmp->next=head;head = tmp;size++;}

注意:一定要注意:再定义tmp时,要给它赋一个初始值(推荐使用 new list_next)

接着是尾插:

函数定义:

void tail_add(list_next* &tail,int v,int &size)

还是回到那张图:

把tmp初始化:

​​list_next* tmp=new list_next;tmp->value=v;tmp->next=NULL;

把尾的next变成tmp。

tail -> next=tmp;

把tmp变成尾:

tail = tmp;

最后size++;

整理后代码:

void tail_add(list_next* &tail,int v,int &size){list_next* tmp=new list_next;tmp->value=v;tmp->next=NULL;tail -> next=tmp;tail = tmp;size++;}

随后是中间插:

函数定义:

void add_node(list_next* head,int p,int v,list_next* &tail,int &size)

几句可以加快速度的代码:

if(p == 0){head_add(head,v,size);} if(p == size){tail_add(tail,v,size);return ;}

来正式的:

首先找到第p个:

list_next* tmp=new list_next;//初始化tmp->value = v;int x=1;//第几个for(list_next* i=head;i!=NULL;i=i->next,x++){if(x == p){...}}

将第tmp的next=第p个的next:

​​​​​​​

将第p个的next变为tmp:

​​​​​​​就好了:

tmp->next = i->next;i->next=tmp;break;//省时

最后是size++;

void add_node(list_next* head,int p,int v,list_next* &tail,int &size){if(p == 0){head_add(head,v,size); } if(p == size){tail_add(tail,v,size);return ;}list_next* tmp=new list_next;tmp->value = v;int x=1;for(list_next* i=head;i!=NULL;i=i->next,x++){if(x == p){tmp->next = i->next;i->next=tmp;break;}}size++;}

然后是最简单的改值:

没啥好说:

void change(list_next* head,int p,int v){int x=1;for(list_next* i=head;i!=NULL;x++,i=i->next){if(x == p)//找到第p个值 {i->value=v;//改值 break;}}}

随后是删头:

永恒的那张图:

​​​​​​​

我们可以直接把头变成头的next。

void head_del(list_next* &head,int &size){head = head->next;size--;}

一定要注意(size–)

删中间:

函数定义:

void del_node(list_next* &head,int p,list_next* &tail,int &size)

加速代码:

if(p == 1){head_del(head,size);return ;}

永恒之图:

先找到第p-1个,再把第p-1个的next变为第p个的next(也就是第p-1的next的next)。

但是,如果删尾部的话要有个特判,把第p-1个的next设为NULL,tail = 第p-1个。

然后:

就ok了。

void del_node(list_next* &head,int p,list_next* &tail,int &size){if(p == 1){head_del(head,size);return ;}int x=1;for(list_next* i=head;i!=NULL;i=i->next,x++){if(x == p-1){if(p == size)//如果删尾巴的话 {i->next = NULL;//那么这个就是尾巴,next是NULL tail = i;//尾巴变成i break;}i->next = i->next->next;break;}}size--;}

这时所有的链表操作都好了,上总体代码。

#include"list.h"using namespace std; void head_add(list_next* &head,int v,int &size){list_next* tmp=new list_next;tmp->value=v;tmp->next=head;head = tmp;size++;}void tail_add(list_next* &tail,int v,int &size){list_next* tmp=new list_next;tmp->value=v;tmp->next=NULL;tail -> next=tmp;tail = tmp;size++;}void add_node(list_next* head,int p,int v,list_next* &tail,int &size){if(p == 0){head_add(head,v,size); } if(p == size){tail_add(tail,v,size);return ;}list_next* tmp=new list_next;tmp->value = v;int x=1;for(list_next* i=head;i!=NULL;i=i->next,x++){if(x == p){tmp->next = i->next;i->next=tmp;break;}}size++;}void change(list_next* head,int p,int v){int x=1;for(list_next* i=head;i!=NULL;x++,i=i->next){if(x == p)//找到第p个值 {i->value=v;//改值 break;}}}void head_del(list_next* &head,int &size){head = head->next;size--;}void del_node(list_next* &head,int p,list_next* &tail,int &size){if(p == 1){head_del(head,size);return ;}int x=1;for(list_next* i=head;i!=NULL;i=i->next,x++){if(x == p-1){if(p == size)//如果删尾巴的话 {i->next = NULL;//那么这个就是尾巴,next是NULL tail = i;//尾巴变成i break;}i->next = i->next->next;break;}}size--;}

末尾:

细心的小朋友会发现:我再list.h还写了一个struct,make_list,这个结构体包含了一条链表所要的基本属性(头,尾,长度)所以我写了一个初始化函数:

void init(list_make &p,int v){p.head=new list_next;p.tail=new list_next;p.head->value = v;p.head->next = NULL;p.tail = p.head;p.size = 1;}

最后:listfun.h的代码应是:

#include"list.h"using namespace std; void head_add(list_next* &head,int v,int &size){list_next* tmp=new list_next;tmp->value=v;tmp->next=head;head = tmp;size++;}void tail_add(list_next* &tail,int v,int &size){list_next* tmp=new list_next;tmp->value=v;tmp->next=NULL;tail -> next=tmp;tail = tmp;size++;}void add_node(list_next* head,int p,int v,list_next* &tail,int &size){if(p == 0){head_add(head,v,size); } if(p == size){tail_add(tail,v,size);return ;}list_next* tmp=new list_next;tmp->value = v;int x=1;for(list_next* i=head;i!=NULL;i=i->next,x++){if(x == p){tmp->next = i->next;i->next=tmp;break;}}size++;}void change(list_next* head,int p,int v){int x=1;for(list_next* i=head;i!=NULL;x++,i=i->next){if(x == p)//找到第p个值 {i->value=v;//改值 break;}}}void head_del(list_next* &head,int &size){head = head->next;size--;}void del_node(list_next* &head,int p,list_next* &tail,int &size){if(p == 1){head_del(head,size);return ;}int x=1;for(list_next* i=head;i!=NULL;i=i->next,x++){if(x == p-1){if(p == size)//如果删尾巴的话 {i->next = NULL;//那么这个就是尾巴,next是NULL tail = i;//尾巴变成i break;}i->next = i->next->next;break;}}size--;}void init(list_make &p,int v){p.head=new list_next;p.tail=new list_next;p.head->value = v;p.head->next = NULL;p.tail = p.head;p.size = 1;}

oh,对了:

附上一句话和代码:遍历链表元素时:

for(list_next* i=head;i!=NULL;i=i->next)

i就是当前链表的其中一个的元素