c语言链表

[highlight lanaguage="c语言"]

#include <stdio.h>
#include <string.h>
#include <strlib.h>

typedef struct LNode {
	int data;
	struct LNode* next;
}LNode;
typedef struct LNode* LinkList;      //将指向结点结构体的指针命名为LinkList



//构造一个空线性表L,创建成功返回OK
struct LNode* InputData(struct LNode* head, int n);
//求两个递增的有序列表la和lb的交集，使用头指针lc指向
void Intersection(LinkList la, LinkList lb);
//输出链表
void output(struct LNode* head);


//对链表进行赋值
struct LNode* InputData(struct LNode* head, int n)
{
	struct LNode* p = NULL, * q = NULL;
	int data;
	p = (struct LNode*)malloc(sizeof(struct LNode));
	head = p;
	q = p;
	while (n--)
	{
		scanf_s("%d", &data);
		p = (struct LNode*)malloc(sizeof(struct LNode));
		p->data = data;
		q->next = p;
		q = p;
	}
	p->next = NULL;
	return head;
}

//进行求交集
void Intersection(LinkList la, LinkList lb)
{
	struct LNode * pa , * pb , * pc , *u;//三个结点指针
	pa = (struct LNode*)malloc(sizeof(struct LNode));
	pb = (struct LNode*)malloc(sizeof(struct LNode));
	pa = la->next;
	pb = lb->next;
	pc = la;   //使用la的头结点作为lc的头节点

	while (pa && pb)
	{
		if (pa->data == pb->data)  //相等，交集并存入结果表中
		{
			pc->next = pa;  //取la中的元素，将pa链接在pc的后面
			pc = pc; //pc = pc ->next
			pa = pa->next; //pa指针后移
			u = pb;
			pb = pb->next; //pb指针后移
			free(u);  //删除lb对应的相等元素
		}
		else if (pa->data < pb->data) //删除较小者la中的元素
		{
			u = pa;
			pa = pa->next;
			free(u);
		}
		else   //删除较小者lb中的元素
		{
			u = pb;
			pb = pb->next;
			free(u);
		}
	}
	while (pa)  //lb为空，则删除非空表la中所有元素
	{
		u = pa;
		pa = pa->next;
		free(u);

	}
	while (pb)  //la为空，则删除非空表lb中所有元素
	{
		u = pb;
		pb = pb->next;
		free(u);
	}
	pc->next = NULL;   //置链表lc尾标记
	free(lb);  //释放lb的头节点
}

//输出链表
void output(struct LNode* head)
{
	struct LNode* h = head->next;//跳过头节点
	if (h == NULL) {//判空
		printf("The Link is null");
		return;
	}
	while (h != NULL) {
		printf("%d ", h->data);
		h = h->next;
	}
	free(h);
}


int main(void)
{
	struct LNode* L1 = NULL, * L2 = NULL;
	int n, m;
	printf("输入第一条链表的长度和第二条链表的长度:");
	scanf_s("%d,%d", &n, &m);
	//链表赋值
	L1 = InputData(L1, n);
	L2 = InputData(L2,m);
	//output(L1);
	//printf("\n");
	//output(L2);
	//printf("\n");

	//求交集
	Intersection(L1, L2);
	output(L1);

}

[/highlight]