实验三 线性表操作

一、 实验目的
1、 掌握线性表的基本操作：插入、删除、查找。
2、 掌握链表遍历器的使用方法。
二、实验内容
1、 创建线性表类。线性表的存储结构使用链表。
2、 提供操作:自表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。
3、 接收键盘录入的一系列整数（例10,25,8,33,60）作为节点的元素值，创建链表。输出链表内容。
4、 输入一个整数（例33），在链表中进行搜索，输出其在链表中的位置。如果不存在输出0。
5、 使用链表遍历器实现链表的反序输出。
6、 创建两个有序链表，使用链表遍历器实现链表的合并。

#include<iostream>
using namespace std;

class ChainNode{
friend class Chain;
public:
int data ;
ChainNode *link;
};

class Chain{
friend class ChainIterator;
public:
Chain(){first=0;}
~Chain();
bool isEmpty() const {return first==0;}
int length() const;
bool find(int k,int x) const;
int search(int x) const;
Chain& Delete(int k,int x);
Chain& insert(int k,const int x);
void output(ostream& out) const;
private:
ChainNode *first ;
};

Chain::~Chain(){
ChainNode *next;
while(first){
next=first->link;
delete first;
first=next;
}
}

int Chain::length() const{
ChainNode *current=first;
int len=0;
while(current){
len++;
current=current->link;
}
return len;
}

bool Chain::find(int k,int x) const{
if(k<1) return false;
ChainNode *current=first;
int index=1;
while(index<k&&current){
current=current->link;
index++;
}
if(current){
x=current->data;
return true;
}
return false;
}
int Chain::search(int x) const{
ChainNode *current=first;
int index=1;
while(current&&current->data!=x){
current =current->link;
index++;
}
if(current)
return index;
else return 0;
}

void Chain::output(ostream& out) const{
ChainNode *current;
for(current=first;current;current=current->link)
out<<current->data<<" ";
}

ostream operator<<(ostream& out,const Chain& x){
x.output(out);
return out;
}

Chain& Chain::Delete(int k,int x){
if(k<1||!first)
{}//throw OutOfBounds();
ChainNode *p =first;
if(k==1)
{first=first->link;}
else{
ChainNode *q=first;
for(int index=1;index<k-1&&q;index++)
{ q=q->link;}
if(!q||!q->link){}//
p =q->link;
q->link=p->link;
x=p->data;
delete p;
return *this;
}
}

Chain& Chain::insert(int k, const int x){
if(k<0){}// throw OutOfBounds();
ChainNode *p=first;
for(int index=1;index<k&&p;index++)
p=p->link;
if(k>0&&!p){}// throw OutOfBounds();
ChainNode* y=new ChainNode;
y->data=x;
if(k){
y->link=p->link;
p->link=y;
}
else{
y ->link=first;
first=y;
}
return *this;
}

class ChainIterator{
public:

int* Initialize(const Chain& c){
location=c.first;
if(location) return (&location->data);
else return 0;
}
int* Next(){
if(!location) return 0;
location =location->link;
if(location)
return &location->data;
else return 0;}
private:
ChainNode *location;
};

void main(){
Chain w;
int i;
cout<<"输入数据，并在输入完成后输入数字‘00’表示输入完成:"<<endl;
while(i!=00){

cin>>i;
if(i==00) break;
w.insert(0,i);
}
cout<<"你输入的数据是: ";
cout<<w<<endl;
cout <<"输入你要查找的数据 :"<<endl;
cin>>i;
if(w.search(i)){
cout <<"你输入数据的index是 : ";
cout<<w.search(i)<<endl;
}
else{ cout<<"0"<<" "<<"你输入的数据不存在。"<<endl;}

int *x,*y,t;

ChainIterator c,d;
x=c.Initialize(w);
cout<<"使用遍历器倒排后，链表的数据是: ";
for ( t=w.length();t>=1;t--){
for (int j=t;j>=2;j--){
x=c.Next();
}
cout<<*x<<" ";
x=c.Initialize(w);
}

cout<<endl;
cout<<"再输入两个有序链表,注意链表的长度为5."<<endl;
Chain q;
for (int k=0;k<5;k++){
cout<<"请输入第"<<k+1<<"个数据"<<endl;
int n;
cin>>n;
q.insert(k,n);

}
cout <<"输入的链表是: ";
cout<<q<<endl;

Chain p;
for (int j=0;j<5;j++){
cout<<"请输入第"<<j+1<<"个数据"<<endl;
int m;
cin>>m;
p.insert(j,m);

}
cout <<"输入的链表是: ";
cout<<p<<endl;

x=c.Initialize(p);
y=d.Initialize(q);
Chain newChain;

while(x&&y)
{
if(*x>=*y) { newChain.insert(newChain.length(),*y); y=d.Next();}
else {newChain.insert(newChain.length(),*x); x=c.Next(); }
}

while(x){
newChain.insert(newChain.length(),*x);

x=c.Next();
}

while(y){
newChain.insert(newChain.length(),*y);
y=d.Next();
}

cout<<"合并后的链表是 : "<<newChain<<endl;

}