数据结构-删除链表相同元素

怼烎@ 2022-05-17 02:05 193阅读 0赞

***【灰灰考研】***

**2017华科计院**

假设带头结点的单链表A，B为有序递增表，单链表的类型定义如下：

Typeddf struct LNode

\{ Element Type data;

Struct LNode \*next;

\}LNode, \*LinkList;

编写算法voidDelete（LinkList \*A,LinkList \*B）

**从有序表 A 中删除所有和有序表 B 中元素相同的结点。**

#include<iostream>
    #include<cstdlib>
    #include<cstring>
    
    using namespace std;
    
    typedef struct LNode{
    	int data;
    	struct LNode *next;
    }LNode;
    
    LNode *createLinkList(int data[], int n)
    {
    	LNode *head, *p;
    	head = (LNode*)malloc(sizeof(LNode));
    	p = head;
    	for(int i = 0; i < n; i++)
    	{
    		LNode *node = (LNode*)malloc(sizeof(LNode));
    		node->data = data[i];
    		node->next = NULL;
    		
    		p->next = node;
    		p = p->next;
    	}
    	return head;
    }
    
    LNode *deleteSameElement(LNode *A, LNode *B)
    {
    	LNode *p, *s, *t;
    	p = A;
    	t = A->next;
    	s = B->next;
    	while(t != NULL && s != NULL)
    	{
    		if(t->data < s->data)
    		{
    			p = t;
    			t = t->next;
    		}
    		else if(t->data == s->data)
    		{
    			p->next = t->next;
    			free(t);
    			t = p->next;
    		}
    		else
    		{
    			s = s->next;
    		}
    	}
    	return A;
    }
    
    int main()
    {
    	LNode *L1, *L2, *L3;
    	int data1[] = {1,2,4,7,8,9,10};
    	int data2[] = {2,3,4,8,9};
    	L1 = createLinkList(data1, 7);
    	L2 = createLinkList(data2, 5);
    	
    	L3 = deleteSameElement(L1, L2);
    	L3 = L3->next;
    	while(L3)
    	{
    		cout<<L3->data<<" ";
    		L3 = L3->next;
    	}
    	cout<<endl;
    	
    }