学链表也学了有一段时间了，在这里先总结一下
1.链表的中头结点相当重要，判断是否有值或为空相当重要，建议头结点一般设置为不赋值
2.每次操作一般都是从移动元素的上一个结点来操作，这也是头结点为建议不赋值的原因
3.链表的每次指向变化最好还是画图更加清晰易懂
删除两条链表重复的数
我的思路就是用较长链表遍历较短链表，再创一条链表把不重复的数存储起来。。。
#include <stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}NODE;
NODE *createa()
{
NODE *head,*p,*q;
int i,j,k;
k=0;
head=NULL;
for(i=0;i<10;i++)
{
p=(NODE *)malloc(sizeof(NODE));
p->data=k+2;
p->next=NULL;
if(head==NULL)
{
head=p;
}
else
{
q->next=p;
}
q=p;
k+=2;
}
return head;
}
NODE *createb()
{
NODE *head,*p,*q,*t;
int i,j,k;
k=0;
head=NULL;
for(i=0;i<5;i++)
{
p=(NODE *)malloc(sizeof(NODE));
p->data=k+2;
p->next=NULL;
if(head==NULL)
{
head=p;
}
else
{
q->next=p;
}
q=p;
k+=4;
}
return head;
}
void shuchu(NODE *head)
{
while(head!=NULL)
{
printf("%d ",head->data);
head=head->next;
}
}
NODE *shanchu(NODE* la,NODE *lb)//这篇代码的核心
{
NODE *q,*p,*t,*head;
int i,flag;
q=la;
p=lb;
head=(NODE *)malloc(sizeof(NODE));//为下面存储不同数做准备
head->next=NULL;
for(i=0;i<10;i++)
{
flag=0;
while(p!=NULL)
{
if(q->data==p->data)//较长链遍历较短链
{
flag=1;
break;
}
p=p->next;
}
if(flag==0)
{
t=(NODE *)malloc(sizeof(NODE));//头插法创建新链存储不重复数
t->data=q->data;
t->next=head->next;
head->next=t;
}
q=q->next;// 判断下一个结点
p=lb;//新的遍历还是从较短链开始
}
return t;//注意不要返回head；
}
int main(void)
{
NODE *la,*lb,*q;
la=createa();
lb=createb();
shuchu(la);
printf("\n");
shuchu(lb);
printf("\n");
q=shanchu(la,lb);
while(q!=NULL)
{
printf("%d ",q->data);
q=q->next;
}
}
冒泡排序//交换结点
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}NODE;
NODE *create(int n)
{
int a;
NODE *head,*p,*q,*t;
t=(NODE *)malloc(sizeof(NODE));
head=NULL;
while(n--)
{
scanf("%d",&a);
p=(NODE *)malloc(sizeof(NODE));
p->data=a;
p->next=NULL;
if(head==NULL)
{
head=p;
}
else
{
q->next=p;
}
q=p;
}
t->next=head;//设立一个空的表头，为下面结点交换做准备
return t;
}
int paixu(NODE *head)//设链表为2，1，5，3，4
{
NODE *pre,*p,*tail;
tail=NULL;
pre=head;
while((head->next)!=tail)
{
p=head->next;
pre=head;
while(p->next!=tail)
{
if((p->data)<(p->next->data))
{
pre->next=p->next; //pre->next=1...
p->next = p->next->next;// p->next=5;确定了后面三个结点的连接
pre->next->next = p; //pre->next->next=2;
p = pre->next; //p=1;
} //则pre->1,2,5,3,4,p->1,2,5,3,4,
p=p->next;
pre=pre->next;
}
tail=p;
}
return 0 ;
}
int main(void)
{
int n;
NODE *p,*q,*t;
scanf("%d",&n);
p=create(n);
paixu(p);
while(p->next!=NULL)
{
printf("%d ",p->next->data);
p=p->next;
}
return 0;
}
头指针不变，后面的结点进行交换，需要注意的是除了两个比较的数之外后面结点的正确连接。。。
链表的逆置
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct node
{
int data;
struct node *next;
};
struct node *create(int count)
{
struct node *phead,*pend,*pnew;
int i;
phead=pend=(struct node *)malloc(sizeof(struct node));/////
srand((unsigned)time(NULL));
for(i=0;i<count;i++)
{
pnew=(struct node *)malloc(sizeof(struct node));
pnew->data=rand()%100;
pend->next=pnew;
pend=pnew;
}
pnew->next=NULL;
return phead;
}
void output(struct node * phead)
{
phead=phead->next;//为什么要指向下一个呢?因为phead->pend;此时Pend为空，
while(phead)//相当于b=a;a=3;无论a后来怎么变，b总等于最初的a。。。。
{
printf("%d ",phead->data);
phead=phead->next;
}
printf("\n");
}
void contrary(struct node *phead)
{
struct node *ptemp1=phead->next,*ptemp2=phead->next;
phead->next=NULL;
while(ptemp2)//以下代码分成两部分来看
{
ptemp1=ptemp2;//p2永远指向p1的下一个
ptemp2=ptemp1->next;
ptemp1->next=phead->next;//妥妥的头插法啊
phead->next=ptemp1;
}
}
int main(void)
{
struct node *phead;
int count=10;
phead=create(count);
output(phead);
contrary(phead);
output(phead);
}
将两个有序链表合并再进行逆置
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct node
{
int data;
struct node *next;
};
struct node *create(int icount,int num)
{
struct node *phead=NULL,*pend,*pnew;
int i,j;
phead=pend=(struct node*)malloc(sizeof(struct node));
for(i=0,j=0;i<icount;i++)
{
pnew=(struct node *)malloc(sizeof(struct node));
pnew->data=j;
j+=num;
pend->next=pnew;
pend=pnew;
}
pnew->next=NULL;
return phead;
}
void output(struct node *phead)
{
phead=phead->next;
while(phead)
{
printf("%-5d",phead->data);
phead=phead->next;
}
printf("\n");
}
void merge(struct node *phead_a,struct node *phead_b)
{
struct node *la,*lb,*lc,*la_t,*lb_t;//a指向la当前结点，b指向lb当前结点
la=phead_a->next;//la_t,lb_t可看作链表的备份
lb=phead_b->next;
phead_a->next=NULL;
while(la&&lb)
{
if((la->data)<(lb->data))
{//备份移动
la_t=la->next;//la_t备份比较数的下一个结点
//头插法
la->next=phead_a->next;
phead_a->next=la;
//跟前面链表的逆置一样、、
la=la_t;//a移动到下一个结点
}
else
{
lb_t=lb->next;
lb->next=phead_a->next;
phead_a->next=lb;
lb=lb_t;
}
}
while(la)//接下来思路都跟上面一样，只是将较长链再头插进去而已
{
la_t=la->next;
la->next=phead_a->next;
phead_a->next=la;
la=la_t;
}
while(lb)
{
lb_t=lb->next;
lb->next=phead_a->next;
phead_a->next=lb;
lb=lb_t;
}
}
int main(void)
{
struct node *phead_a,*phead_b;
srand((unsigned)time(NULL));
int icount_a=rand()%20+1,icount_b=rand()%20+1;
int a=rand()%4+1,b=rand()%4+1;
phead_a=create(icount_a,a);
phead_b=create(icount_b,b);
output(phead_a);
output(phead_b);
merge(phead_a,phead_b);
output(phead_a);
return 0;
}
链表的交叉合并
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct node
{
int data;
struct node *next;
};
struct node*create(int icount)
{
struct node *phead,*pend,*pnew;
int i;
pend=phead=(struct node*)malloc(sizeof(struct node));
for(i=0;i<icount;i++)
{
pnew=(struct node*)malloc(sizeof(struct node));
pnew->data=rand()%100;
pend->next=pnew;//尾插法
pend=pnew;
}
pnew->next=NULL;
return phead;
}
void output(struct node *phead)
{
phead=phead->next;
while(phead)
{
printf("%d ",phead->data);
phead=phead->next;
}
printf("\n");
}
void merge(struct node *phead_x,struct node *phead_y)
{
struct node *lx,*lx_h,*ly,*lz;
lx=phead_x->next;
ly=phead_y->next;
lz=phead_x;
while(lx)//lx短链表，ly长链表,lz指向已排好序链表的尾部
{ //会不会感到很奇怪为什么直接输出phead_x就可以，答案应该就是下一句lz=phead_x
lz->next=lx;//连接lz和短链表的当前节点 //则lz->next=phead_x->next,接下来的操作都可以看作phead_x已经作为头节点
lx_h=lx->next;//备份lx的指针域
lx->next=ly;//连接lx当前节点和ly当前节点
lz=ly;//移动lz，使lz成为当前已排好节点尾部
lx=lx_h;//移动lx，使lx成为短链表未排好序的第一个
ly=ly->next;//移动ly，使ly成为长链表未排好序的第一个
}
lz->next=ly;//连接剩下的长链表
}
int main(void)
{
struct node *phead_a,*phead_b;
srand((unsigned)time(NULL));
int icount_a=rand()%20+1,icount_b=rand()%20+1;
phead_a=create(icount_a);
phead_b=create(icount_b);
output(phead_a);
output(phead_b);
if(icount_a<=icount_b)
{
merge(phead_a,phead_b);
output(phead_a);
free(phead_b);
}
else
{
merge(phead_b,phead_a);
output(phead_b);
free(phead_a);
}
}
循环单链表的创建//尾节点指向头节点时退出
#include<stdio.h>
#include<stdlib.h>
typedef struct n{
int data;
struct n *next;
}node;
node *create(int count)
{
int i;
node *phead,*q,*p;
phead=(node *)malloc(sizeof(node));
q=phead;
for(i=0;i<count;i++){
p=(node *)malloc(sizeof(node));
scanf("%d",&p->data);
phead->next=p;
phead=p;
}
phead=q;// head恢复开始时的位置
p->next=phead;//尾节点指向头节点
return phead;
}
void output(node *head){
node *pt;
pt=head->next;//head本身没有赋值
while(pt!=head)//当尾节点走到头节点时退出循环
{
printf("%d ",pt->data);
pt=pt->next;
}
}
int main(void){
int count;
node *head;
scanf("%d",&count);
head=create(count);
output(head);
}
双向单链表的创建//插入//删除
#include<stdio.h>//不难理解，建议画图所谓的删除与添加只是多考虑了一个指针域而已
#include<stdlib.h>
typedef struct n
{
int data;
struct n *pre,*next;
}node;
node *create(int count)
{
int i;
node *phead,*p,*q;
phead=(node *)malloc(sizeof(node));
q=phead;//phead数据域未给赋值
for(i=0;i<count;i++)
{
p=(node *)malloc(sizeof(node));
printf("输入数据：\n");
scanf("%d",&p->data);
p->pre=phead;//其实就是尾插法加上这个
phead->next=p;
phead=p;
}
p->next=q;//完成头尾节点的互相指向
phead=q;
phead->pre=p;
return phead;
}
void output(node *head)
{
node *p,*s;
p=head->next;
while(p!=head)//从左至右
{
printf("%d ",p->data);
p=p->next;
}
s=head->pre;
printf("\n");
while(s!=head)//从右至左
{
printf("%d ",s->data);
s=s->pre;
}
printf("\n");
}
void charu(node *head,int n)//链表的插入
{
int i;
node *p,*q,*s;
p=head;
for(i=1;i<n;i++)//i=1
{
p=p->next;
}
s=(node *)malloc(sizeof(node));
printf("输入待插入数：\n");
scanf("%d",&s->data);
s->next=p->next;
p->next=s;
s->pre=p;
(s->next)->pre=s;
output(head);
}
void shanchu(node *head,int n)
{
int i;
node *p;
p=head;
for(i=0;i<n;i++)//注意这里和删除的不同 i=0
{
p=p->next;
}
(p->next)->pre=p->pre;
(p->pre)->next=p->next;
output(head);
free(p);
}
int main(void)
{
int n;
node *head;
printf("请输入链表数\n");
scanf("%d",&n);
head=create(n);
output(head);
printf("输入待插入节点位置：\n");
scanf("%d",&n);
charu(head,n);
printf("输入待删除节点位置：\n");
scanf("%d",&n);
shanchu(head,n);
}
链表学到这里再将前面的知识再过了一遍，多了一些该注意的点
struct node* shanchu(struct node *head)//链表的删除//没什么难度，就是得注意下循环中的break;
{//可以尝试下取掉break删除最后一个数就懂了
int a;
scanf("%d",&a);
struct node *begin,*end,*p;
begin=(struct node *)malloc(sizeof(struct node));
begin=head;
while(head->next!=NULL)
{
if(a==head->next->data)
{
p=(struct node *)malloc(sizeof(struct node));
p=head->next->next;
head->next=p;
break;//////
}
head=head->next;
}
void paixu(struct node *head)//冒泡排序节点交换核心
{//基本没什么问题
struct node *begin,*end,*pre,*p;
end=NULL;
while(head->next!=end)//设计的很巧妙
{
begin=head->next;
pre=head;
while(begin->next!=end)
{
if(begin->data<begin->next->data)
{
pre->next=begin->next;
begin->next=begin->next->next;
pre->next->next=begin;
begin=pre->next;//这个东西不能忘，相当于后退一步再前进一步
}
begin=begin->next;
pre=pre->next;
}
end=begin;
}
}
void nizhi(struct node *head)//链表的逆置，，这之间的逻辑关系还是有点没理清
{
struct node *begin,*end;
begin=head->next;end=head->next;
head->next=NULL;
while(end)
{
begin=end;
end=begin->next;
begin->next=head->next;
head->next=begin;
}}
void shanchu(qnode *p1,qnode *p2)//链表的交叉合并
{
qnode *la,*lb,*la_t,*lc;
la=p1->next;lb=p2->next;
lc=p1;
while(la){
lc->next=la;
la_t=la->next;
la->next=lb;//我写的是lc=lc->next;lc->next=lb,明显错了
lc=lb;//上面已经有lc->next=la,则la->next=lb可看成lc-la-lb
la=la_t;
lb=lb->next;
}
lc->next=lb;
}
链表学到这里就先告一段落，接下来会继续深入的