#include<iostream.h>
#include<malloc.h>
typedef char ElemType;
typedef struct LinkNode
{
ElemType elem;
struct LinkNode *next; //指針域
}LinkType;
class LinkList
{
LinkType *head;
public:
LinkList ()
{
head=(LinkType *)malloc(sizeof(LinkList));
head->next=NULL;
}
~LinkList()
{
head=head->next;
free(head);
}
void InsertElement(ElemType e,int x) //這是插入函數
{
LinkType *p=head;
while(x>0) {x--;p=p->next;}
p=(LinkType *)malloc(sizeof(LinkType));
p->elem=e;p->next=head->next;head->next=p;
}
void DisElem(int x)
{
LinkType *p=head;
while(x>0) {x--;p=p->next;}
cout<<p->elem<<endl;
}
int ListLength()
{
int x=0;
LinkType *p=head->next;
while(p!=NULL) {x++;p=p->next;}
return x;
}
void SortList()
{
LinkType *p=head,*s;
p=p->next;
ElemType e;
while(p!=NULL)
{
s=p->next;
while(s!=NULL)
{
if(s->elem<p->elem)
{e=p->elem;p->elem=s->elem;s->elem=e;}
s=s->next;
}
p=p->next;
}
}
int FindElem(ElemType x)
{
LinkType *p=head;
p=p->next; int n=0;
while(p!=NULL)
{n++;if(p->elem==x) return n;p=p->next; }
return 0;
}
void DelElem(int x)
{
LinkType *p=head,*s;
while(x>1) {x--;p=p->next;}
s=p->next;
p->next=s->next;
free(s);
}
void SumList(LinkList *L1,LinkList *L2)
{
int n;
LinkList L3;
LinkType *p=L1->head,*q=L2->head;
p=p->next;q=q->next;
while(p!=NULL)
{
q=L2->head->next;
n=0;
while(q!=NULL)
{
if(q->elem!=p->elem) n++;
q=q->next;
}
if(n==L2->ListLength()) L3.InsertElement(p->elem,1);
p=p->next;
}
q=L2->head->next;
while(q!=NULL)
{L3.InsertElement(q->elem,1);q=q->next;}
cout<<"並集："<<endl;
L3.SortList();
L3.DisplayLink();
}
void AndList(LinkList *L1,LinkList *L2)
{
LinkList L3;
LinkType *p=L1->head,*q=L2->head;
p=p->next;q=q->next;
while(p!=NULL)
{
q=L2->head->next;
while(q!=NULL)
{
if(q->elem==p->elem) L3.InsertElement(p->elem,1);
q=q->next;
}
p=p->next;
}
cout<<"交集："<<endl;
L3.SortList();
L3.DisplayLink();
}
void DisList(LinkList *L1,LinkList *L2)
{
int n;
LinkList L3;
LinkType *p=L1->head,*q=L2->head;
p=p->next;q=q->next;
while(p!=NULL)
{
q=L2->head->next;
n=0;
while(q!=NULL)
{
if(q->elem!=p->elem) n++;
q=q->next;
}
if(n==L2->ListLength()) L3.InsertElement(p->elem,1);
p=p->next;
}
cout<<"L1 - L2 的差集："<<endl;
L3.SortList();
L3.DisplayLink();
}
int ListEmpty()
{
LinkType *p;
p=head;
if(p!=NULL) return 1;
else return 0;
}
void DisplayLink()
{
LinkType *p=head->next;
while(p!=NULL)
{cout<<p->elem<<' '; p=p->next;}
cout<<endl;
}
};
void main()
{
LinkList l1,l2,l3;
l1.InsertElement('e',1);
l1.InsertElement('d',1);
l1.InsertElement('c',1);
l1.InsertElement('s',1);
l1.InsertElement('k',1);
l2.InsertElement('a',1);
l2.InsertElement('s',1);
l2.InsertElement('d',1);
l2.InsertElement('x',1);
l2.InsertElement('w',1);
l1.DisplayLink();
l2.DisplayLink();
cout<<"排序後："<<endl;
l1.SortList();
l2.SortList();
cout<<"L1 : ";
l1.DisplayLink();
cout<<"L2 : ";
l2.DisplayLink();
l3.SumList(&l1,&l2);
l3.AndList(&l1,&l2);
l3.DisList(&l1,&l2);
}
以上是鏈表的基本用法，包括查找，插入，刪除，鏈表的並集和差集