作者 by aigle / 2022-01-18 / 暂无评论
生成链表a
A>>0-->1-->2-->3-->4-->5-->6-->7-->8-->9-->10-->11-->12-->13-->14-->15-->16-->17-->18-->19-->Null.
生成链表b
B>>0-->2-->4-->6-->8-->10-->12-->14-->16-->18-->20-->22-->24-->26-->28-->30-->32-->34-->36-->38-->Null.
生成链表c
C>>0-->3-->6-->9-->12-->15-->18-->21-->24-->27-->30-->33-->36-->39-->42-->45-->48-->51-->54-->57-->Null.
取B,C交集后的链表TEMP
0-->6-->12-->18-->24-->30-->36-->Null.
取A,TEMP交集后的链表
0-->6-->12-->18-->Null.
最终输出的A链表
A--》1-->2-->3-->4-->5-->7-->8-->9-->10-->11-->13-->14-->15-->16-->17-->19-->Null.
Process finished with exit code 1
#include<stdio.h>
#include<assert.h>
#include<malloc.h>
#define Elemtype int
typedef struct SList
{
Elemtype data;
struct SList *next;
}Node;
Node* setnode(Elemtype x);//设置节点
void initial(Node **head);//初始化单链表并创建头指针
void push_back(Node **head,Elemtype x);//尾插法
void show(Node *head);//打印列表
Node* intersec(Node *ha,Node *hb);//两两重复对比 取交集
Node* deletem(Node* L, int m);//删除指定链表 指定值
void renode(Node *sour,Node *head);//删除指定链表 输入另一链表所有值int main()
{
Node *ha,*hb,*ht,*hc;
initial(&ha);
initial(&hb);
initial(&hc);
printf("生成链表a\n");
for (int i = 0; i < 20; i++) {
push_back(&ha,i);
}
printf("A>>");
show(ha);
printf("生成链表b\n");
for (int i = 0; i < 20; i++) {
push_back(&hb,2*i);
}
printf("B>>");
show(hb);
printf("生成链表c\n");
for (int i = 0; i < 20; i++) {
push_back(&hc,(3*i));
}
printf("C>>");
show(hc);
printf("取B,C交集后的链表TEMP\n");
ht=intersec(hb,hc);
show(ht);
printf("取A,TEMP交集后的链表\n");
ht=intersec(ha,ht);
show(ht);
printf("最终输出的A链表\nA--》");
renode(ha,ht);
show(ha);
return(1);
}Node* setnode(Elemtype x)
{//创建节点赋值并返回指针
Node *s=(Node*)malloc(sizeof(Node));
assert(s!=NULL);
s->data=x;
s->next=NULL;
return(s);
}void push_back(Node **head,Elemtype x)
{//尾插法插入节点
Node *p=*head;
while(p->next!=NULL)
{
p=p->next;
}//p指向尾节点
Node *s=setnode(x);
s->next=p->next;
p->next=s;
(*head)->data++;//表长加一
}void initial(Node **head)
{//初始化单链表并创建头指针
(*head)=(Node*)malloc(sizeof(Node));
assert((*head)!=NULL);
(*head)->data=0;//表长为0
(*head)->next=NULL;
}void show(Node *head)
{//遍历输入表并输入元素值
if(head->data==0)
return;//判断非空表
Node *p=head->next;
while(p!=NULL)
{
printf("%d-->",p->data);
p=p->next;
}
printf("Null.\n");}
Node* intersec(Node *ha,Node *hb)
{//有序递增列表求交集并返回交集新链表
Node *ht,*pa,*pb;
initial(&ht);
pa=ha->next;
pb=hb->next;
while(pb!=NULL)//遍历B
{
while(pa!=NULL && pa->data<pb->data)
pa=pa->next;
if(pa!=NULL && pa->data==pb->data)
{
Node *s=setnode(pb->data);
Node *p=ht;
while(p->next!=NULL)
p=p->next;//寻找ht尾
s->next=p->next;
p->next=s;//尾部插入
ht->data++;//表长加一
}
pb=pb->next;
pa=ha->next;
}
return(ht);
}Node* deletem(Node* L, int m){
//删除函数,输入链表地址和要删除的值
Node* p = L, * q = NULL;
while(p) { //判断是否到达链尾
if (p->data == m) { //若节点的值等于 m
if (q) { //判断 q 是否为空
q->next = p->next;//保存 p 指向下一节点的指针 其实就是把 p->next 指向的节点和 q 节点链起来
free(p); //释放内存
p = q->next; //因为释放内存后 p的指向改变了 需要重新设置 不能直接让p指向下一个节点
}
else {
L = p->next; // q为空 代表链表的第一个节点的值等于m 是要删除的节点 。需要移动链表的头结点,不然的话 L 将指向一个奇怪的地方。
free(p); //释放内存
p = L; //释放内存后 p的指向改变了 让 p 指向新的链表头
}
}
else {
q = p; //移动节点
p = p->next;
}
}
return L; //返回链表的头节点
}void renode(Node *sour,Node *head)
{//将ht表节点的值作为删除ha表的输入,调用删除函数deletem
if(head->data==0)
return;//判断非空表
Node *p=head->next;
while(p!=NULL)
{
deletem(sour,p->data);
p=p->next;
}
}void show(Node *head)
{//遍历输入表并输入元素值
if(head->data==0)
return;//判断非空表
Node *p=head->next;
while(p!=NULL)
{
printf("%d-->",p->data);
p=p->next;
}
printf("Null.\n");
}
评论已关闭