链式表示的线性表之一——单链表2

利用单链表的基本运算，求A-B，即A中的元素在B中出现删除。(上海大学考研试题)

LinkList.h

#pragma once
#include <iostream>
typedef int DataType;
using namespace std;

/*02_01——存储结构*/
typedef struct Node
{
	DataType data;
	struct Node *next;
}ListNode, *LinkList;/*ListNode是链表的结点类型，LinkList是指向链表结点的指针类型*/
/*02——基本运算*/
/*02_01——初始化单链表*/
void InitList(LinkList *head)
{
	if ((*head=(LinkList)malloc(sizeof(ListNode)))==NULL)
	{
		/*02_01为头结点分配一个存储单元*/
		exit(-1);
	}
	(*head)->next = NULL;/*02_01将单链表的头结点指针域置为空 */

}
/*02_02判断单链表是否为空*/
int ListEmpty(LinkList head)
{
	if (head->next==NULL)/*02_02如果单链表头结点的指针域为空*/
	{
		return 1;        /*02_02返回1*/
	}
	else
	{
		
		return 0;        /*02_02返回1*/
	}
}

/*02_03按照序号查找*/
ListNode *Get(LinkList head, int i)
/*02_03按照序号查找单链表中第i个结点，查找成功返回该结点的指针表示成功；否则返回NULL表示失败*/
{
	ListNode *p;
	int j;
	if (ListEmpty(head))
	{
		return NULL;
	}
	if (i<1)
	{
		return NULL;
	}
	j = 0;
	p = head;
	while (p->next!=NULL&&j<i)
	{
		p = p->next;
		j++;

	}
	if (j==i)
	{
		return p;

	}
	else
	{
		return NULL;
	}

}

/*02_04查找元素值为e的结点的元素，若查找成功则返回对应元素的结点指针，否则返回NULL表示失败*/
ListNode *LocateElem(LinkList head, DataType e)
{
	ListNode *p;
	p = head->next;
	while (p)
	{
		if (p->data!=e)
		{
			p = p->next;
		}
		else
		{
			break;
		}
	}
	return p;
}

/*02_05定位操作，确定元素所在单链表中的序号*/
/*02_05从头指针出发依次访问每个结点，并将结点的值与e比较，如果相等，则返回该结点序号表示成功*/
/*02_05如果没有与e相等的元素则返回0表示失败*/

int LocatePos(LinkList head, DataType e)
{
	ListNode *p;
	int i;
	if (ListEmpty(head))/*02_05在查找第i个元素之前，判断链表是否为空*/
	{
		return 0;
	}
	p = head->next;    /*02_05指针指向第一个结点*/
	i = 1;
	while (p)
	{
		if (p->data==e) /*02_05找到与e相等的元素*/
		{
			return i;   /*02_05返回该序号*/
		} 
		else
		{
			p = p->next;
			i++;
		}
	}
	if (!p)       /*02_05如果没有找到与e相等的元素*/
	{
		return 0; /*返回0*/
	}
}

/*02_06在第i个位置插入元素e*/

int InsertList(LinkList head, int i, DataType e)
/*02_06在单链表中的第i个位置插入一个结点，结点的元素值为e。插入成功返回1，失败返回0.*/
{
	ListNode *pre, *p;/*02_06定义第i个元素的前驱结点指向pre，指针p指向新生成的结点*/
	int j;
	pre = head;/*02_06指针p指向头结点*/
	j = 0;
	while (pre->next != NULL&&j < i - 1)
		/*02_06找到第i-1个结点，即第i个结点的前驱结点*/
	{
		pre = pre->next;
		j++;
	}
	if (j!=i-1)/*02_06如果没有找到说明插入位置错误*/
	{
		cout << "02_06插入位置错误！" << endl;
		return 0;
	}
	/*02_06新生成一个结点，并将e赋值给该结点的数据域*/
	if ((p=(ListNode*)malloc(sizeof(ListNode)))==NULL)
	{
		exit(-1);
	}
	p->data = e;
	/*02_06插入结点操作*/
	p->next = pre->next;
	pre->next = p;
	return 1;

}
/*02_07删除第i个结点*/

int DeleteList(LinkList head, int i, DataType *e)
/*02_07删除单链表中的第i个结点；删除成功返回1，失败返回0。*/
{
	ListNode *pre, *p;
	int j;
	pre = head;
	j = 0;
	while (pre->next!=NULL&&pre->next->next!=NULL&&j<i-1)
	/*02_07判断是否找到前驱结点*/
	{
		pre = pre->next;
		j++;

	}
	if (j!=i-1)/*02_07如果没有找到要删除的节点位置，说明删除有误*/
	{
		cout << "02_07删除位置有误" << endl;
		return 0;
	}
	/*02_07指针p指向单链表中的第i个结点，并将该结点的数据域赋值给e*/
	p = pre->next;
	*e = p->data;
	/*02_07将前驱结点的指针域指向要删除结点的下一个结点，也就是将p指向的结点与单链表断开*/
	pre->next = p->next;
	free(p); /*02_07释放p指向的结点*/
	return 1;

}
/*02_08求表长的操作*/
int ListLength(LinkList head)
{
	ListNode *p;
	int count = 0;
	p = head;
	while (p->next!=NULL)
	{
		p = p->next;
		count++;

	}
	return count;
}

/*02_09销毁链表操作*/

void DestoryList(LinkList head)
{
	ListNode *p, *q;
	p = head;
	while (p!=NULL)
	{
		q = p;
		p = p->next;
		free(q);
	}
}

main.cpp

/*求单链表的差集*/
#include <malloc.h>
#include <stdlib.h>
#include "LinkList.h"


void SortList(LinkList S);
ListNode *Append(ListNode *last, DataType e);
ListNode *Difference(ListNode *A, ListNode *B);

void main()
{
	int i;
	DataType a[] = { 22, 7, 15, 56, 89, 38, 44, 65, 109, 83 };
	DataType b[] = { 15,9,22,89,33,65,90,83 };
	LinkList A, B, C; /*声明单链表A，B，C*/
	ListNode *p;
	InitList(&A);     /*初始化单链表A*/
	InitList(&B);     /*初始化单链表B*/
    /*将数组a中的元素插入单链表A中*/
	for (i = 1; i <= sizeof(a) / sizeof(a[0]);i++)
	{
		if (InsertList(A,i,a[i-1])==0)
		{
			cout << "位置不合法！" << endl;
			return;

		}
	}
    /*将数组b中的元素插入单链表B中*/
	for (i = 1; i <= sizeof(b) / sizeof(b[0]);i++)
	{
		if (InsertList(B,i,b[i-1])==0)
		{
			cout << "位置不合法！" << endl;
			return;
		}
	}
	cout << "单链表A中有元素" << ListLength(A)<< "个" <<endl;
	p = A->next;
    /*输出单链表A中的每一个元素*/
	while (p!=NULL)
	{
		cout << p->data <<" ";
		p = p->next;
	}
	cout << endl;
	cout << "单链表B中有元素" <<ListLength(B)<< "个" << endl;
	p = B->next;
	/*输出单链表B中的每一个元素*/
	while (p!=NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
	/*将两个两个单链表中的元素从小到大重新排序*/
	SortList(A);
	SortList(B);
	cout << "排序后单链表A中有元素" << ListLength(A) << "个" << endl;
	p = A->next;
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
	cout << "排序后单链表B中有元素" << ListLength(B) << "个" << endl;
	p = B->next;
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
	/*将在单链表A中出现的B的元素删除，即A-B*/
	C = Difference(A, B);

	cout << "C中的元素(A-B)：" << endl;
	p = C;
	while (p!=NULL)
	{
		cout << p->data <<" ";
		p = p->next;
	}
	cout << endl;
	system("pause");
}
/*利用选择排序法对链表进行从小到大排序*/
void SortList(LinkList S)
{
	ListNode *p, *q, *r;
	DataType  t;
	p = S->next;
	while (p->next)
	{
		r = p;
		q = p->next;
		while (q)
		{
			if (r->data>q->data)
			{
				r = q;
			}
			q = q->next;
		}
		if (p!=r)
		{
			t = p->data;
			p->data = r->data;
			r->data = t;
		}
		p = p->next;
	}
}

ListNode *Append(ListNode *last, DataType e)
//释放头结点
{
	last->next = (ListNode*)malloc(sizeof(ListNode));
	last->next->data = e;
	return last->next;
}


ListNode *Difference(ListNode *A, ListNode *B)
//求A-B将结果存放在C中
{
	ListNode *C, *last;
	C = last = (ListNode*)malloc(sizeof(ListNode));
	while (A!=NULL&&B!=NULL)
	{
		if (A->data<B->data)
		{
			last = Append(last, A->data);
			
			A = A->next;
		}
		else if (A->data==B->data)
		{
			A = A->next;
			B = B->next;

		}
		else
		{
			B = B->next;
		}
	}
	while (A != NULL)/*如果A中还有剩余元素，把剩下的元素追加到C中*/
	{
		last = Append(last, A->data);
		
		A = A->next;
	}
	last->next = NULL;/*最后一个结点的指针域置为空*/
	last = C;         
	C = C->next;      /*指向第一个结点*/
	free(last);       /*释放头结点*/
	return C;
}

结果：

这个问题还可以通过删除的方法处理：

/*求单链表的差集*/
#include <malloc.h>
#include <stdlib.h>
#include "LinkList.h"

void DelElem(LinkList A,LinkList B);

void main()
{
	int i;
	DataType a[] = { 22, 7, 15, 56, 89, 38, 44, 65, 109, 83 };
	DataType b[] = { 15,9,22,89,33,65,90,83 };
	LinkList A, B, C; /*声明单链表A，B，C*/
	ListNode *p;
	InitList(&A);     /*初始化单链表A*/
	InitList(&B);     /*初始化单链表B*/
					  /*将数组a中的元素插入单链表A中*/
	for (i = 1; i <= sizeof(a) / sizeof(a[0]); i++)
	{
		if (InsertList(A, i, a[i - 1]) == 0)
		{
			cout << "位置不合法！" << endl;
			return;

		}
	}
	/*将数组b中的元素插入单链表B中*/
	for (i = 1; i <= sizeof(b) / sizeof(b[0]); i++)
	{
		if (InsertList(B, i, b[i - 1]) == 0)
		{
			cout << "位置不合法！" << endl;
			return;
		}
	}
	cout << "单链表A中有元素" << ListLength(A) << "个" << endl;
	p = A->next;
	/*输出单链表A中的每一个元素*/
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
	cout << "单链表B中有元素" << ListLength(B) << "个" << endl;
	p = B->next;
	/*输出单链表B中的每一个元素*/
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
	DelElem(A, B);
	cout << "删除后的单链表A中有元素" << ListLength(A) << "个" << endl;
	p = A->next;
	/*输出删除后单链表A中的每一个元素*/
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
	system("pause");
}

void DelElem(LinkList A, LinkList B)
{
	int i, pos;
	DataType e;
	ListNode *p;
	for (i = 1; i <= ListLength(B);i++)
	{
		p = Get(B, i);
		if (p)
		{
			pos = LocatePos(A, p->data);
			if (pos>0)
			{
				DeleteList(A, pos, &e);
			}
		}
	}
}

结果：