目录
创建文件:
具体实现:
首先是头插。
注意:一定要注意:再定义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就是当前链表的其中一个的元素