数据结构与算法 p45-09
已知两个元素按值递增有序排列的线性表A和B，且同一表中的元素值各不相同。
试构造一个线性表C，其为A和B中的元素的交集，且表C中的元素也按值递增有序排列
A，B，C都是顺序表时
http://blog.csdn.net/weimengnvbianba/article/details/15028171
A，B，C都是单链表表时
#include<iostream.h>
typedef int T; template<class T>
struct Node
{ T data;//数据域，存放表元素 Node *next;//指针域，指向下一个结点
}; template <class T>
class LinkList
{ private: Node<T> *Head;// 链表头指针 public: LinkList() ;~LinkList();void CreateList(int n);//创建具有n个元素的线性链表 void createlist(int n,int a[]);//创建合并的线性链表 void Delete(int i); T GetElem(int i); int Length(); void ListDisplay();
};
template<class T>
LinkList<T>::LinkList()
{ Head=new Node<T>; Head->next=NULL;
} template<class T>
LinkList<T>::~LinkList()
{ Node<T> *p; while(Head)//从头结点开始，依次释放结点 { p=Head; Head=Head->next; delete p; } Head=NULL;//头结点指向空
} template<class T>
void LinkList<T>::CreateList(int n)
{ Node<T> *p,*s;//设置工作指针。p指向尾结点 int start,step; p=Head; cout<<"请依次输入初始值和步长："<<endl; cin>>start>>step; for(int i=1;i<=n;i++) { s=new Node<T>; s->data=start+(i-1)*step; s->next=p->next; p->next=s; p=s; }
} template<class T>
void LinkList<T>::createlist(int k,int a[])
{ Node<T> *p,*s; p=Head; for(int i=1;i<=k;i++) { s=new Node<T>; s->data=a[i-1];//输入新建数据元素值 s->next=p->next; p->next=s; p=s; }
} template <class T>
void LinkList<T>::Delete (int i)
{//删除指定位置元素 Node<T> *p,*q;//设置工作指针 p=Head;//查找从头结点开始 int j=0;//计数器初始化 while(p->next && j<i-1)//p定位到删除点的前驱 { p=p->next;// j++; } if(!p->next||j>i-1) //删除位置不合理 throw"位置异常"; else //删除位置合理 { q=p->next;// 暂存删除结点位置 p->next=q->next;//从链表中摘除删除结点 delete q;// 释放删除点 }
} template<class T>
T LinkList<T>::GetElem(int i)
{//获取第i个元素的值 Node<T> *p;//设置工作指针 p=Head->next;//从首结点开始 int j=1;//计数器初始化 while(p&&j<i)//定位到第i个元素结点 { p=p->next;j++; } if(!p||j>i)//定位位置不合理：空表或i小于0或i大于表长 throw "位置"; else //位置合理 return p->data;
} template <class T>
int LinkList<T>::Length()
{ int len=0;//计数器初始化 Node<T> *p;//设置工作指针 p=Head;//指向头结点 while(p->next) { len++;p=p->next; } return len;
} template <class T>
void LinkList<T>::ListDisplay()
{//遍历显示链表 Node<T> *p;//设置工作指针 p=Head->next;//从首元结点开始遍历 int i=1;//元素位序 while(p) { cout<<p->data<<" "; p=p->next; i++; } cout<<endl;
} int main()
{ int t=0,la_len,lb_len,a,b,array[100],i,j; LinkList<int> La,Lb,Lc; cout<<"请输入要创建A集合中元素个数:"; cin>>la_len; La.CreateList(la_len); cout<<endl<<"La:"<<"\t"; La.ListDisplay(); cout<<endl<<"请输入要创建的B集合中元素个数:"; cin>>lb_len; Lb.CreateList(lb_len); cout<<endl<<"Lb:"<<"\t"; Lb.ListDisplay(); int a_length=La.Length(); int b_length=Lb.Length(); for(i=1;i<a_length;i++) { a=La.GetElem(i); for(j=1;j<=b_length;j++) { b=Lb.GetElem(j);if(a<b)break;if(a==b) { array[t]=b; t++;break;} } } cout<<endl<<"A集合和B集合的交集C的元素如下:"; Lc.createlist(t,array); cout<<endl<<"Lc:"<<"\t"; Lc.ListDisplay(); cout<<endl; return 0;
}
