本文共 4835 字，大约阅读时间需要 16 分钟。
描述
创建线性表类：线性表的存储结构使用单链表；提供操作: 自表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。
输入一个整数，在 表首插入 该元素。
输入一个整数（例33），在链表中进行搜索，输出元素第一次出现位置的索引（ 从0开始 )。如果不存在输出-1。
给出链表中的一个元素，删除该元素（元素可能重复，只删除从前往后遍历 第一次出现 的该元素）。
设计实现链表迭代器，使用链表迭代器实现链表的 反序输出 。
创建两个有序链表，使用 链表迭代器 实现链表的合并。
格式
输入格式
插入操作：1 插入数
删除操作：2 删除数
查找操作：3 查找数
输出操作：4
逆序输出操作：5
合并链表操作：
6
链表一元素数 [链表一所有元素]
链表二元素数 [链表二所有元素]
输出格式
查找操作: 若是找到该元素，输出该元素第一次出现位置的索引（从0开始），若是没找到，输出-1
输出链表操作：从表头开始输出链表所有元素，元素间用空格隔开
逆序输出操作：逆序输出链表的所有元素，元素间用空格隔开
合并链表操作：输出两条有序链表合并后的有序序列，序列各元素间用空格分隔
输入
第一行一个n(1<=n<=25000)代表操作个数，接下来n行是各个操作。保证合并链表操作只出现一次，且待合并的链表长度不超过1000000。
输出
当遇到查找，输出链表，逆序输出，合并链表时输出。
Sample 1
Input
9
1 3
2 3
1 1
1 2
3 4
3 2
4
5
6
3 1 3 5
4 4 7 8 10
Output
-1
0
2 1
1 2
1 3 4 5 7 8 10
限制
1s, 16MB for each test case.
#include using namespace std;//链表节点定义template struct chainNode{ T element; chainNode *next; chainNode() { } chainNode(const T& element) { this->element=element;} chainNode(const T& element,chainNode * next) { this->element=element; this->next=next; } } ;template class chain{ public: chain(int initialCapacity=10); chain(const chain &); ~chain(); //函数方法 bool empty() const { return listSize==0;} int size() const { return listSize;} //T& get(int theIndex) const; int indexOf(const T& theElement) const;//查找3 int erase(const T& theElement);//删除2 void insert(const T& theElement);//插入1 void output() ;//输出4 void reverse();//逆序输出5 void combin(chain &l2);//合并6 //创建迭代器 class iterator; iterator start() { return iterator(firstNode);} iterator end() { return iterator(NULL);} class iterator { public: //向前迭代器所需要的typedef语句 //构造函数 iterator(chainNode * theNode=NULL) { node=theNode;} //解引用操作符 T& operator*() const{ return node->element;} T* operator->() const{ return &node->element;} //迭代器加法 iterator& operator++() { node=node->next;return *this;} iterator operator++(int) { iterator old=*this; node=node->next; return old;} //相等检验 bool operator!=(const iterator right) const { return node != right.node;} bool operator==(const iterator right) const { return node == right.node;} protected: chainNode * node; }; private: chainNode * firstNode; int listSize;};//构造函数和复制构造函数template chain ::chain(int initialCapacity){ firstNode=NULL; listSize=0;}template chain ::chain(const chain & theList){ listSize=theList.listSize; if(listSize==0) { firstNode==NULL; return; } chainNode * sourceNode=theList.firstNode; firstNode=new chainNode (sourceNode->element); sourceNode=sourceNode->next; chainNode * targetNode=firstNode; while(sourceNode != NULL) { targetNode->next= new chainNode (sourceNode->element); targetNode=targetNode->next; sourceNode=sourceNode->next; } targetNode->next=NULL;}//析构函数template chain ::~chain(){ while(firstNode!=NULL) { chainNode * nextNode=firstNode->next; delete firstNode; firstNode=nextNode; } } //查找操作 3template int chain ::indexOf(const T& theElement) const{ chainNode * currentNode=firstNode; int index=0; while(currentNode!=NULL && currentNode->element!=theElement) { currentNode=currentNode->next; index++; } if(currentNode==NULL) return -1; else return index;}//删除操作 2template int chain ::erase(const T& theElement){ int decision; decision=indexOf(theElement); chainNode * deleteNode; if(decision==-1) return -1; else if(decision==0) { deleteNode=firstNode; firstNode=firstNode->next; } else{ chainNode * p=firstNode; for(int i=0;i next; deleteNode=p->next; p->next=p->next->next; } listSize--; delete deleteNode;}//插入操作 1template void chain ::insert(const T& theElement){ firstNode= new chainNode (theElement,firstNode); listSize++;}//输出操作4template void chain ::output(){ for (chainNode * currentNode=firstNode; currentNode!=NULL; currentNode=currentNode->next) cout< element<<" ";}/*template ostream& operator<<(ostream& out,const chain & x){x.output(out);return out;}*///迭代器逆序输出操作5template void chain ::reverse(){ chain list;//建立一个新链表 chain ::iterator is=(*this).start(); chain ::iterator ie=(*this).end(); while(is!=ie) { list.insert(*is); is++; } list.output();}//使用迭代器合并链表6template void chain ::combin(chain &l2){ chain l3; chain ::iterator is1=(*this).start(); chain ::iterator ie1=(*this).end(); chain ::iterator is2=l2.start(); chain ::iterator ie2=l2.end(); while(is1 != ie1 && is2 != ie2) { if(*is1>*is2){ l3.insert(*is1);is1++;} else if(*is1<*is2){ l3.insert(*is2);is2++;} else{ l3.insert(*is2);l3.insert(*is1);is1++;is2++;} } while(is1 != ie1) { l3.insert(*is1); is1++; } while(is2 != ie2) { l3.insert(*is2); is2++; } l3.output();}int main(){ chain c; int n,x,elem,num1,num2,l1,l2; cin>>n; for(int i=0;i >x; switch(x){ case 1: cin>>elem; c.insert(elem); break; case 2: cin>>elem; c.erase(elem); break; case 3: cin>>elem; cout< <
list1,list2; cin>>num1; for(int k=0;k