c++单链表的一些操作链表的合并，单链表的一些操作,由于一些操作很类似,名字不好区分,现单列出来,可以直接在上篇文章的单链表中使用，VS2005调试通过
操作一：链表的合并
1、要求：两个单链表A和B，AB增C非增，C=A+B
注意：利用原表A和B，允许有相同元素
思想：
1、每次都插小的，大的留下继续比较
2、AB增C非增，则使用逆序插入
3、不能连续插入（每次要插入的结点总是要从原链表中截断，插入到C中）
代码：
[cpp] view plaincopy
- template<class Type>
- void LinkList<Type>::Merge(LinkList<Type>& A,LinkList<Type>& B)
- {
- Node<Type>* currentA = A.Head->next;//currentA指向第一个结点
- Node<Type>* currentB = B.Head->next;//currentB指向第一个结点
- Node<Type>* currentC = A.Head;
- len = A.len + B.len;
- //处理C的头结点,利用A的头结点
- this->Head = A.Head;
- this->Head->next = NULL;
- delete B.Head;
- //处理之后的元素
- while(currentA!=NULL && currentB!=NULL)//
- {
- Node<Type>* temp;
- if (currentA->data > currentB->data)
- {
- temp = currentB;
- currentB = currentB->next;
- temp->next = currentC->next;
- currentC->next = temp;
- }
- else
- {
- temp = currentA;
- currentA = currentA->next;
- temp->next = currentC->next;
- currentC->next=temp;
- }
- }
- while (currentA!=NULL)
- {
- Node<Type>* temp;
- temp = currentA;
- currentA=currentA->next;
- temp->next = currentC->next;
- currentC->next = temp;
- }
- while (currentB!=NULL)
- {
- Node<Type>* temp;
- temp = currentB;
- currentB=currentB->next;
- temp->next = currentC->next;
- currentC->next = temp;
- }
- }
2、要求：两个单链表A和B，AB增C增，C=A+B
注意：利用原表A和B的空间，允许有相同元素
思想：
1、每次都插小的，大的留下继续比较
2、AB增C增，则使用正序插入
3、可以连续插入（每次要插入的结点可以先不从原链表中截断，直到遇到一个大数，不指向插入操作时，才从原链表中截断）
代码：
[cpp] view plaincopy
- template<class Type>
- void LinkList<Type>::merge(LinkList<Type>& A,LinkList<Type>& B)
- {
- Node<Type>* currentA = A.Head->next;//currentA指向第一个结点
- Node<Type>* currentB = B.Head->next;//currentB指向第一个结点
- Node<Type>* currentC = A.Head;
- len = A.len + B.len;
- //处理C的头结点,利用A的头结点
- this->Head = A.Head;
- this->Head->next = NULL;
- delete B.Head;
- //处理之后的元素
- while(currentA!=NULL && currentB!=NULL)
- {
- if (currentA->data > currentB->data)
- {
- currentC->next = currentB;
- currentC = currentC->next;
- currentB = currentB->next;
- }
- else
- {
- currentC->next = currentA;
- currentC = currentC->next;
- currentA = currentA->next;
- }
- }
- if (currentA!=NULL)
- {
- currentC->next = currentA;
- }
- else
- {
- currentC->next = currentB;
- }
- }
3、要求：两个单链表A和B，AB增C增，C=A交B
注意：
1、不能破坏原来空间(不利用原表A和B的空间)
2、AB中元素均无重复元素，但A和B中可能有相同元素 =》C中元素各不相同
思想：
1、每次都先抛弃小的，大的留下继续比较，找到相等的插入
2、AB增C增，则使用正序插入
代码：
[cpp] view plaincopy
- template<class Type>
- void LinkList<Type>::Intersect(const LinkList<Type>& A,const LinkList<Type>& B)
- {
- Head = new Node<Type>;//为链表建立头结点
- Head->next = NULL;
- last = NULL;
- len =0;
- //定义处理指针，C指向最后一个元素，AB指向待处理的元素
- Node<Type>* currentA = A.Head->next;//currentA指向第一个结点
- Node<Type>* currentB = B.Head->next;//currentB指向第一个结点
- Node<Type>* currentC = Head;
- //处理之后的元素
- while(currentA!=NULL && currentB!=NULL) //每次都是先抛弃小的，找到相等的，就使用正序插入.
- {
- if (currentA->data > currentB->data)
- {
- currentB = currentB->next;
- }
- else if(currentA->data < currentB->data)
- {
- currentA = currentA->next;
- }
- else
- {
- Node<int>* newNode = new Node<int>;
- newNode->data = currentA->data;
- currentC->next=newNode;
- currentC = currentC->next;
- currentA = currentA->next;
- currentB = currentB->next;
- len++;
- }
- }
- currentC->next = NULL;
- }
4、要求：两个单链表A和B，AB增C增，C=A交B，C中元素各不相同
注意：
1、不能破坏原来空间(不利用原表A和B)
2、AB中元素 可能有 重复元素，但要求C中元素各不相同
思想：
1、每次都先抛弃小的，大的留下继续比较，找到相等的插入
2、元素相等插入时，必须还要比较之前插入元素是不是和即将插入的元素相等
3、AB增C增，则使用正序插入
代码：
[cpp] view plaincopy
- template<class Type>
- void LinkList<Type>::Intersect(const LinkList<Type>& A,const LinkList<Type>& B)
- {
- bool isFirst = true;//标志位，是不是第一次插入
- //为链表建立头结点
- Head = new Node<Type>;
- Head->next = NULL;
- last = NULL;
- len =0;
- //定义处理指针，C指向最后一个元素，AB指向待处理的元素
- Node<Type>* currentA = A.Head->next;//currentA指向第一个结点
- Node<Type>* currentB = B.Head->next;//currentB指向第一个结点
- Node<Type>* currentC = Head;
- //处理之后的元素
- while(currentA!=NULL && currentB!=NULL) //每次都是先抛弃小的，找到相等的，就使用正序插入.
- {
- if (currentA->data > currentB->data)
- {
- currentB = currentB->next;
- }
- else if(currentA->data < currentB->data)
- {
- currentA = currentA->next;
- }
- else
- {
- if (isFirst)
- {
- Node<int>* newNode = new Node<int>;
- newNode->data = currentA->data;
- currentC->next=newNode;
- currentC = currentC->next;
- isFirst=false;
- len++;
- }
- else
- {
- if (currentC->data != currentA->data)
- {
- Node<int>* newNode = new Node<int>;
- newNode->data = currentA->data;
- currentC->next=newNode;
- currentC = currentC->next;
- len++;
- }
- }
- currentA = currentA->next;
- currentB = currentB->next;
- }
- }
- currentC->next = NULL;
- }
5、要求：两个单链表A和B，AB增C增，B=B-A，A中无重复，B中无重复
注意：
1、不能破坏A空间(不利用A)，但是直接在B表中修改
思想：
1、每次都先抛弃小的，大的留下继续比较，找到相等的，则直接在原表删除
代码：
[cpp] view plaincopy
- template<class Type>
- void LinkList<Type>::Difference(const LinkList<Type>& A)//元素可以有重复的 B-A —没有设置尾指针
- {
- //定义处理指针，C指向最后一个元素，AB指向待处理的元素
- Node<Type>* currentA = A.Head->next;//currentA指向第一个结点
- Node<Type>* currentC = Head->next;
- Node<Type>* trailCurrent = Head;
- //处理之后的元素
- while(currentA!=NULL && currentC!=NULL) //每次都是先抛弃小的，找到相等的，则直接在原表删除
- {
- if (currentA->data > currentC->data)
- {
- trailCurrent = currentC;
- currentC = currentC->next;
- }
- else if(currentA->data < currentC->data)
- {
- currentA = currentA->next;
- }
- else
- {
- trailCurrent->next = currentC->next;
- delete currentC;
- currentC = trailCurrent->next;
- len–;
- }
- }
- if (currentC==NULL)
- {
- trailCurrent->next = NULL;
- }
- }