huffman.cpp

声明定义链表结构,创建线性表,打印链表元素

#include <iostream>
using namespace std;

struct LNode    //声明定义链表结构
{ 
float data;
LNode * next;
};

LNode *createlist(char a)      //创建线性表a
{
	LNode *l,*p,*head;
	float c;
	int n;
	l=new LNode;
	l->next=NULL;
	head=l;
	cout<<"请输入线性表"<<a<<"中元素个数:";
	cin>>n;
	cout<<"递增输入线性表"<<a<<"中元素:"<<endl;
    for(int i=n;i>0;--i)        //循环递增输入n个元素
	{
		p=new LNode;
		cin>>c;
		p->data=c;
		l->next=p;
		l=p;
		p->next=NULL;
	}
	return head;
}

void printlist(LNode *l)    //打印链表元素
{
	LNode *p=l->next;
	cout<<"删除B,C相同元素后线性表A中元素为:";
	while(p!=NULL)
	{
		cout<<p->data<<' ';
		p=p->next;
	}
}

LNode *comparelist(LNode *a,LNode *b)  //比较两个链表中相同元素并返回
                                       //一个用来存储这些相同元素的新链表
{
	LNode *p=a->next;
	LNode *q=b->next;
	LNode *r,*n,*same;
	r=new LNode;
	r->next=NULL;
	same=r;
	while(p&&q)
	{
		if(p->data<q->data)
		{
			p=p->next;
		}
		else if(p->data>q->data){
			q=q->next;}
		else {                        //找到data相同的结点加入到新链表中
			n=new LNode;
			n->data=p->data;
			r->next=n;
			r=n;
			n->next=NULL;
			p=p->next;
		}
	}
	return same;
}

LNode *ListDelete(LNode *a,LNode *b)  //从a表中删除在b表中存在的元素
{
	LNode *p=a->next;
	LNode *q=b->next;
	LNode *l;
	l=a;
    while(p&&q)
	{
		if(p->data<q->data)
		{
			l=l->next;
			p=l->next;
		}
		else if(p->data>q->data)
		{
			q=q->next;
		}
		else {                        //删除data相同的结点
			l->next=p->next;
			p=l->next;
		}
	}
	return a;
}

int main()
{
	char a,b,c;
	a='A';b='B';c='C';
	LNode *ListA,*ListB,*ListC,*CMP,*NewListA;
	ListA=createlist(a);  //创建A表
	ListB=createlist(b);  //创建B表
	ListC=createlist(c);  //创建C表
	CMP=comparelist(ListB,ListC);    //找出B，C表中相同的元素，并新建一链表CMP存放这些元素
    NewListA=ListDelete(ListA,CMP);  //从A表中删除在CMP中出现的元素，得到新表NewListA
	printlist(NewListA);  //打印结果
	return 0;
}