概念：
链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳，复杂度几乎是O(n)
但其还是有很大的重要性
是数据结构的开端
模板：
题目概述：
相信大家对于单链表的操作已经游刃有余了,我们知道,对于一个单链表的能力是否健壮,可以通过它的检错能力来判断,那么现在我们需要设计一个单链表,
来实现一下的全部功能:
功能1:使用头插法在链表中插入一行元素
功能2:使用尾插法在链表中插入一行元素
功能3:按位查找,输入查找的元素位置,输出查找到的元素,如果查找成功,则输出"查找到的元素值为: xxx",反之则输出"位置不合法!!"
功能4:按值查找,输入查找的元素值,并返回查询到的元素位置,如果查找成功,则输出"查找到的元素所在位置为: xxx",反之则输出"未找到该值!!"
功能5:按位序插入,输入插入元素的位置与元素值,如果插入成功,则输出"插入成功!",反之则输出"插入位置不合法!"
功能6:按值插入,输入目标元素的值x与插入的元素值e,并在第一次出现的x值的前面插入e值,如果插入成功,则输出"插入成功!",反之则输出"未找到x!"
功能7:第七步:按位序删除,输入删除的元素的位置,如果删除成功,则输出"删除成功!你所删除的元素为: xxx",反之则输出"删除位置不合法!"
功能8:输出当前链表的长度
功能9:输出链表中的所有元素,以空格分开
创建：
typedef struct Node{
int data;
Node* next;
Node(): data(0),next(NULL){}
Node(int x): data(x),next(NULL){}
}*ListNode;
int len;一个节点包括了数据和指向下一个节点的地址
包含了一个空参构造和有参构造
定义了链表长度变量len
能够快速访问到链表的长度
ListNode head = new Node();在主函数中定义链表的头节点
这个头节点只存下一个节点的地址，不存储数据
这样的操作不容易出现错误而且容易理解
头插：
新建一个节点，使得新建节点的下一个节点指向头节点的下一个节点，然后头节点指向新建节点
//1
void HeadInsert(ListNode &link_list){
int x;
while(cin>>x){
Node *p=new Node(x);
p->next=link_list->next;
link_list->next=p;
len++;
if(cin.get()=='\n')break;
}
}尾插：
尾插就更为简单
遍历到最后一个节点
使得最后一个节点指向新建节点即可
//2
void EndInsert(ListNode &link_list){
int x;
while(cin>>x){
Node *p=link_list;
Node *t=new Node(x);
while(p->next!=NULL)p=p->next;
p->next=t;
len++;
if(cin.get()=='\n')break;
}
}按位查找
实质就是遍历链表
找到第x个位置输出当前节点存储的数据
//3
void IndexFind(ListNode &link_list, int pp){
int id=1;
Node *p = link_list->next;
while(p){
if(id==pp){
cout<<"查找到的元素值为: "<<p->data<<"\n";
return;
}
p=p->next,id++;
}
cout<<"位置不合法!!"<<"\n";
}按值查找
按值查找就是按位查找反过来
找到当前节点的数据跟目标数据x一致
那么就输出当前位置
//4
void ValueFind(ListNode &link_list, int v){
int id=1;
Node *p = link_list->next;
while(p){
if(p->data==v){
cout<<"查找到的元素所在位置为: "<<id<<"\n";
return;
}
p=p->next,id++;
}
cout<<"未找到该值!!"<<'\n';
}按位插入
实质还是遍历链表
找到相应位置
新建节点
使得新建节点的下一个节点指向当前节点的下一个节点
当前节点的下一个节点指向新建节点
//5
void IndexInsert(ListNode &link_list,int index, int val){
int i=1;
Node *p = link_list;
while(p->next!=NULL&&i<index)p=p->next,i++;
if(i!=index){
cout<<"插入位置不合法!"<<'\n';
return;
}
Node *t = new Node(val);
t->next=p->next;
p->next=t;
len++;
cout<<"插入成功!"<<'\n';
}按值插入
和上个原理是一样的
这次是比较节点里的值是否和目标值一致
//6
void ValueInsert(ListNode &link_list,int x, int e){
Node *pf=link_list;
Node *p=link_list->next;
while(p!=NULL&&p->data!=x)pf=p,p=pf->next;
if(p==NULL){
cout<<"未找到x!"<<'\n';
return;
}
Node *t=new Node(e);
pf->next=t;
t->next=p;
len++;
cout<<"插入成功!\n";
}按位删除
遍历链表找到对应位置的节点
当然
这次要定义一个前指针，指向上一个节点
后指针指向当前节点
删除操作就是
把前指针指向的上一个节点的next指向当前节点的next
最后删除当前节点，释放空间
//7
void IndexRemove(ListNode &link_list, int index){
int id=1;
Node *pf = link_list;
Node *p = link_list->next;
while(p){
if(id==index){
cout<<"删除成功!你所删除的元素为: "<<p->data<<"\n";
pf->next=p->next;
delete p;
len--;
return;
}
pf=p,p=p->next,id++;
}
cout <<"删除位置不合法!"<<'\n';
}遍历链表
从头节点开始
不断用next走向下一个节点
输出当前节点的data
//9
void show(ListNode &link_list){
Node* p = link_list->next;
while(p){
cout<<p->data<<" ";
p = p->next;
}
cout<<"\n";
}完整模板
typedef struct Node{
int data;
Node* next;
Node(): data(0),next(NULL){}
Node(int x): data(x),next(NULL){}
}*ListNode;
//8
int len;
//1
void HeadInsert(ListNode &link_list){
int x;
while(cin>>x){
Node *p=new Node(x);
p->next=link_list->next;
link_list->next=p;
len++;
if(cin.get()=='\n')break;
}
}
//2
void EndInsert(ListNode &link_list){
int x;
while(cin>>x){
Node *p=link_list;
Node *t=new Node(x);
while(p->next!=NULL)p=p->next;
p->next=t;
len++;
if(cin.get()=='\n')break;
}
}
//3
void IndexFind(ListNode &link_list, int pp){
int id=1;
Node *p = link_list->next;
while(p){
if(id==pp){
cout<<"查找到的元素值为: "<<p->data<<"\n";
return;
}
p=p->next,id++;
}
cout<<"位置不合法!!"<<"\n";
}
//4
void ValueFind(ListNode &link_list, int v){
int id=1;
Node *p = link_list->next;
while(p){
if(p->data==v){
cout<<"查找到的元素所在位置为: "<<id<<"\n";
return;
}
p=p->next,id++;
}
cout<<"未找到该值!!"<<'\n';
}
//5
void IndexInsert(ListNode &link_list,int index, int val){
int i=1;
Node *p = link_list;
while(p->next!=NULL&&i<index)p=p->next,i++;
if(i!=index){
cout<<"插入位置不合法!"<<'\n';
return;
}
Node *t = new Node(val);
t->next=p->next;
p->next=t;
len++;
cout<<"插入成功!"<<'\n';
}
//6
void ValueInsert(ListNode &link_list,int x, int e){
Node *pf=link_list;
Node *p=link_list->next;
while(p!=NULL&&p->data!=x)pf=p,p=pf->next;
if(p==NULL){
cout<<"未找到x!"<<'\n';
return;
}
Node *t=new Node(e);
pf->next=t;
t->next=p;
len++;
cout<<"插入成功!\n";
}
//7
void IndexRemove(ListNode &link_list, int index){
int id=1;
Node *pf = link_list;
Node *p = link_list->next;
while(p){
if(id==index){
cout<<"删除成功!你所删除的元素为: "<<p->data<<"\n";
pf->next=p->next;
delete p;
len--;
return;
}
pf=p,p=p->next,id++;
}
cout <<"删除位置不合法!"<<'\n';
}
//9
void show(ListNode &link_list){
Node* p = link_list->next;
while(p){
cout<<p->data<<" ";
p = p->next;
}
cout<<"\n";
}
void solve(){
ListNode head = new Node();
int op,x,y;
if(head==NULL)cout<<"true"<<"\n";
while(cin>>op){
if(!op)break;
if(op==1)HeadInsert(head);
if(op==2)EndInsert(head);
if(op==3)cin>>x,IndexFind(head,x);
if(op==4)cin>>x,ValueFind(head,x);
if(op==5)cin>>x>>y,IndexInsert(head,x,y);
if(op==6)cin>>x>>y,ValueInsert(head,x,y);
if(op==7)cin>>x,IndexRemove(head,x);
if(op==8)cout<<len<<"\n";
if(op==9)show(head);
}
}