单链表中，结点相同是什么含义?

来源：千锋教育

发布人：xqq

时间： 2023-10-19 22:55:28

一、单链表中，结点相同

单链表中，结点相同是指遍历链表1的节点和链表2的节点是否有相等。判断单向链表有相同节点：

1、直观法：遍历链表1的节点和链表2的节点是否有相等；

2、找结尾相同法：判断两个链表的尾部节点是否相同。

3、构造法：将链表1的尾部指向链表2的尾部，看链表1或链表2是否存在环

#include

typedef int dt_type;

//定义链表1结构

typedef struct test{

dt_type data;

struct test *next;

}list,*list_p;

//开辟链表空间

list_p do_malloc()

{

list_p L = NULL;

if((L = (list_p)malloc(sizeof(list))) == NULL){

printf(“fail malloc-1\n”);

return NULL;

}

else{

L->next = NULL;

return L;

}

//链表插入数据

int do_insert(list_p L1,list_p L2,dt_type val)

{

list_p P = NULL;

if((P = (list_p)malloc(sizeof(list))) == NULL){

printf(“fail malloc-2\n”);

return -1;

}

P->data = val;

if(val >=0 && val < 10){ //val<10时把数据插入链表1

P->next = L1->next;

L1->next = P;

}

else if(val >= 10 && val <20){ //val>10 val<20时数据插入链表2

P->next = L2->next;

L2->next = P;

}

else{

P->next = L2->next;

L2->next = P;

}

if(val == 20){ //当val==20的时候，让链表1接到链表2中，得到“Y”形链表

list_p S = L1;

while(S->next != NULL){

S = S->next;

}

S->next = L2->next; //链表1链接到链表2

}

return 0;

}

//打印函数

void do_show(list_p L,char *tepy)

{

list_p P=L->next;

printf(“%s:\n”,tepy);

while(P != NULL){

printf(“%d “,P->data);

P = P->next;

}

putchar(10);

}

//方法1：直观遍历法，遍历两个链表是否有相等的节点

int do_visual(list_p L1,list_p L2)

{

list_p S1 = L1;

list_p S2 = L2;

while(S1->next != NULL){

while(S2->next != NULL){

if(S1->next == S2->next){

printf(“方法1：have same node\n”);

printf(“start val:%d\n”,S2->next->data);

return 0;

}

S2 = S2->next;

}

S2 = L2; //S2重新还原，接着下次遍历

S1 = S1->next;

}

printf(“方法1：no same\n”);

return 0;

}

//方法2：尾部相同法，遍历两个链表尾部是否有相等的节点

int do_tailSame(list_p L1,list_p L2)

{

list_p S1 = L1;

list_p S2 = L2;

list_p TEMP1 = L1;

list_p TEMP2 = L2;

while(S1->next != NULL){

TEMP1->next = S1->next; //如果while循环退出，此时TEMP1就是尾节点地址

S1 = S1->next;

}

while(S2->next != NULL){

TEMP2->next = S2->next; //同TEMP1

S2 = S2->next;

}

if(TEMP1->next == TEMP2->next){ //比较两个尾节点是否相等

printf(“方法2：have same node!\n”);

printf(“tail same memory address:%p\n”,TEMP1->next);

return 0;

}else{

printf(“方法2：no same!\n”);

}

return 0;

}

//方法3：尾部构造法，将链表1尾部指向链表二的头部，再判断链表二是否为环链表

int do_tailStruct(list_p L1,list_p L2)

{

list_p S1 = L1;

list_p S2 = L2;

list_p TEMP1 = L1;

list_p TEMP2 = L2;

while(S1->next != NULL){

S1 = S1->next;

}

S1->next = S2->next;

while(S2->next != NULL){ //运用快慢指针法判断是否为环链表

if(S2->next == TEMP2->next){ //快慢指针如果存在相同，说明是环

printf(“方法3：have same node!\n”);

return 0;

}

S2 = S2->next; //指针1走一步

TEMP2 = TEMP2->next->next; //指针2走二步

}

printf(“方法3：no same!\n”);

return 0;

}

//释放函数

void do_free(list_p L1,list_p L2)

{

free(L1);

free(L2);

}

int main(int argc, const char *argv[])

{

//创建链表1

list_p L1;

if((L1 = do_malloc()) == NULL){

printf(“call malloc fail\n”);

return 0;

}

//创建链表2

list_p L2;

if((L2 = do_malloc()) == NULL){

printf(“call malloc fail\n”);

return 0;

}

//把数据插入链表，（“Y”形链表）

int i=0;

for(i=0;i<30;i++){

do_insert(L1,L2,i);

}

//打印链表

do_show(L1,”list_1″);

do_show(L2,”list_2″);

//判断是否存在相同节点，三种方法

do_visual(L1,L2);

do_tailSame(L1,L2);

do_tailStruct(L1,L2);

//释放内存

do_free(L1,L2);

return 0;

}

延伸阅读：

二、链表是什么

链表是动态分配存储空间的链式存储结构。

其包括一个“头指针”变量，其中第0个结点称为整个链表的头结点，头结点中存放一个地址，该地址指向一个元素，头结点一般不存放具体数据，只是存放名列前茅个结点的地址。

链表中每一个元素称为“结点”，每个结点都由两部分组成：存放数据元素的数据域和存储直接后继存储位置的指针域。指针域中存储的即是链表的下一个结点存储位置，是一个指针。多个结点链接成一个链表。

最后一个结点的指针域设置为空(NULL)，作为链表的结束标志，表示它没有后继结点。

使用结构体变量作为链表中的结点，因为结构体变量成员可以是数值类型，字符类型，数组类型，也可以是指针类型，这样就可以使用指针类型成员来存放下一个结点的地址，使其它类型成员存放数据信息。

声明：本站稿件版权均属千锋教育所有，未经许可不得擅自转载。

C数据结构与算法是什么?

计算机组成原理、数据结构、编译原理都是什么?

猜你喜欢LIKE

行业资讯 更多>>

西安如何选择Java培训机构

西安怎么选择靠谱的Java培训机构

西安如何选择靠谱的Java培训机构

西安怎样选择java培训机构

技术干货

c语言链表初始化是什么意思?

计算机组成原理、数据结构、编译原理都是什么?