文章目录

一、前言二、单链表就地逆置三、单链表按位查找3.1 正序按位查找3.2 逆序按位查找 四、单链表取差集4.1 单链表取差集(第一种方式)4.2 单链表取差集(第二种方式) 五、单链表取交集5.1 单链表取交集(第一种方式)5.2 单链表取交集(第二种方式) 六、单链表取并集七、小结

一、前言

二、单链表就地逆置

#include <iostream> #include<stdio.h> #include<stdlib.h> using namespace std; typedef struct node{ int data; struct node *next; }Node,*Linklist; void myr(Linklist str1){ Linklist p=str1->next; str1->next=NULL; while(p){//就地逆置 不需要新建节点 Linklist u=p->next; p->next=str1->next; str1->next=p; p=u; } } int main() { int a[5]; for (int i=0;i<5;i++) cin>>a[i]; Linklist first=new Node; Linklist r=first; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=a[i]; r->next=s; r=s; } r->next=NULL; Linklist p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; myr(first); p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; return 0; }

运行结果：

三、单链表按位查找

单链表按位查找，通过自己定义count变量的方式，包括正序按位查找和逆序按位查找两种方式。

3.1 正序按位查找

#include <iostream> #include<stdlib.h> #include<stdio.h> using namespace std; typedef struct node { int data; struct node *next; }Node,*Linklist; int myfind_zhengshu(Linklist str1,int k){ Linklist p=str1->next,q=str1->next; int mycount=1;//正向按位查找mycount从1开始 逆向按位查找mycount从0开始 while(p&&mycount<k){ p=p->next; mycount++; } if(mycount<k) return -1; cout<<p->data<<endl; return 1; } int main() { int a[5]; for(int i=0;i<5;i++) cin>>a[i]; Linklist first=new Node; Linklist r=first; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=a[i]; r->next=s; r=s; } r->next=NULL; Linklist p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; while(true){ int k; cin>>k; myfind_zhengshu(first,k); } return 0; }

运行结果：

​​ ​​

3.2 逆序按位查找

#include <iostream> #include<stdlib.h> #include<stdio.h> using namespace std; typedef struct node { int data; struct node *next; }Node,*Linklist; int myfind_daoshu(Linklist str1,int k){//倒数 Linklist p=str1->next,q=str1->next;//两个指向相同 int mycount=0; while(p){ if(mycount<k) mycount++; else q=q->next; p=p->next; } if(mycount<k) return 0; else { cout<<q->data<<endl; return 1; } } int main() { int a[5]; for(int i=0;i<5;i++) cin>>a[i]; Linklist first=new Node; Linklist r=first; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=a[i]; r->next=s; r=s; } r->next=NULL; Linklist p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; while(true){ int k; cin>>k; myfind_daoshu(first,k); } return 0; }

运行结果：

四、单链表取差集

4.1 单链表取差集(第一种方式)

#include <iostream> #include<stdio.h> #include<stdlib.h> using namespace std; typedef struct node{ int data; struct node* next; }Node,*Linklist; //取差集合 void getchaji(Linklist str1,Linklist str2){// 12345 13579 24 Linklist pre=str1; Linklist pa=pre->next,pb=str2->next; while(pa&&pb){ if(pa->data==pb->data){//为什么删除的时候pb没有移动 Linklist u=pa; pre->next=pa->next; pa=pa->next; free(u); }else if(pa->data<pb->data){ pre=pa;//删除的时候凡是pa移动的pre不能少移动 pa=pa->next; }else { pb=pb->next; } } } int main() { int a[5]; for (int i=0;i<5;i++) cin>>a[i]; Linklist first=new Node; Linklist r=first; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=a[i]; r->next=s; r=s; } r->next=NULL; Linklist p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; int b[5]; for (int i=0;i<5;i++) cin>>b[i]; Linklist first2=new Node; Linklist r2=first2; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=b[i]; r2->next=s; r2=s; } r2->next=NULL; p=first2->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; getchaji(first,first2); p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; p=first2->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; return 0; }

运行结果：

4.2 单链表取差集(第二种方式)

#include <iostream> #include<stdio.h> #include<stdlib.h> using namespace std; typedef struct node{ int data; struct node* next; }Node,*Linklist; //取差集 不删除 用尾插 两个相等的时候删除a 或者 不用说删除pa是尾插 void getchaji2(Linklist str1,Linklist str2){// 12345 13579 Linklist pa=str1->next,pb=str2->next; Linklist ra=str1; while(pa&&pb){ if(pa->data<pb->data){ ra->next=pa; ra=pa; pa=pa->next; }else if(pa->data>pb->data){ pb=pb->next; }else {//尾插的时候pb移动 pa=pa->next; pb=pb->next; } } ra->next=NULL; } int main() { int a[5]; for (int i=0;i<5;i++) cin>>a[i]; Linklist first=new Node; Linklist r=first; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=a[i]; r->next=s; r=s; } r->next=NULL; Linklist p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; int b[5]; for (int i=0;i<5;i++) cin>>b[i]; Linklist first2=new Node; Linklist r2=first2; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=b[i]; r2->next=s; r2=s; } r2->next=NULL; p=first2->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; getchaji2(first,first2); p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; p=first2->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; return 0; }

运行结果：

五、单链表取交集

5.1 单链表取交集(第一种方式)

#include <iostream> #include<stdio.h> #include<stdlib.h> using namespace std; typedef struct node{ int data; struct node* next; }Node,*Linklist; //取交集不需要删除 尾插相同 ra 删除不同pa pre void getjiaoji(Linklist str1,Linklist str2){ Linklist pa=str1->next,pb=str2->next; Linklist ra=str1;//交集 while(pa&&pb){ if(pa->data==pb->data){//尾插的时候pb移动 ra->next=pa; ra=pa; pa=pa->next; pb=pb->next; }else if(pa->data<pb->data){ pa=pa->next; }else if(pa->data>pb->data){ pb=pb->next; } } ra->next=NULL; } int main() { int a[5]; for (int i=0;i<5;i++) cin>>a[i]; Linklist first=new Node; Linklist r=first; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=a[i]; r->next=s; r=s; } r->next=NULL; Linklist p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; int b[5]; for (int i=0;i<5;i++) cin>>b[i]; Linklist first2=new Node; Linklist r2=first2; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=b[i]; r2->next=s; r2=s; } r2->next=NULL; p=first2->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; getjiaoji(first,first2); p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; p=first2->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; return 0; }

运行结果：

5.2 单链表取交集(第二种方式)

#include <iostream> #include<stdio.h> #include<stdlib.h> using namespace std; typedef struct node{ int data; struct node* next; }Node,*Linklist; void getjiaoji2(Linklist str1,Linklist str2){ Linklist pb=str2->next; Linklist pre=str1; Linklist pa=pre->next; while(pa&&pb){ if(pa->data<pb->data){//删除的时候pa移动 Linklist u=pa; pre->next=pa->next; pa=pa->next; free(u); }else if(pa->data>pb->data){ pb=pb->next; }else { pre=pa;//删除的时候凡是pa移动的pre不能少移动 pa=pa->next; pb=pb->next; } } } int main() { int a[5]; for (int i=0;i<5;i++) cin>>a[i]; Linklist first=new Node; Linklist r=first; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=a[i]; r->next=s; r=s; } r->next=NULL; Linklist p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; int b[5]; for (int i=0;i<5;i++) cin>>b[i]; Linklist first2=new Node; Linklist r2=first2; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=b[i]; r2->next=s; r2=s; } r2->next=NULL; p=first2->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; getjiaoji2(first,first2); p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; p=first2->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; return 0; }

运行结果：

六、单链表取并集

代码：

#include <iostream> #include<stdio.h> #include<stdlib.h> using namespace std; typedef struct node{ int data; struct node* next; }Node,*Linklist; //取并集合放到A中 pa和相同尾插ra 无法删除 void getbingji(Linklist str1,Linklist str2){ Linklist pa=str1->next,pb=str2->next; Linklist ra=str1; while(pa&&pb){ if(pa->data==pb->data){//保证相同的只有一次 ra->next=pa; ra=pa; pa=pa->next; pb=pb->next; }else if(pa->data<pb->data){//保证取到小的 ra->next=pa; ra=pa; pa=pa->next; }else {//保证取到小的 ra->next=pb; ra=pb; pb=pb->next; } } //保证取到剩余的 if(pa) pb=pa; while(pb){ ra->next=pb; ra=pb; pb=pb->next; } ra->next=NULL; } int main() { int a[5]; for (int i=0;i<5;i++) cin>>a[i]; Linklist first=new Node; Linklist r=first; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=a[i]; r->next=s; r=s; } r->next=NULL; Linklist p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; int b[5]; for (int i=0;i<5;i++) cin>>b[i]; Linklist first2=new Node; Linklist r2=first2; for (int i=0;i<5;i++){ Linklist s=new Node; s->data=b[i]; r2->next=s; r2=s; } r2->next=NULL; p=first2->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; getbingji(first,first2); p=first->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; p=first2->next; while(p){ cout<<p->data; p=p->next; } cout<<endl; return 0; }

七、小结

单链表第一篇，完成了。

天天打码，天天进步！！！