/*已知一个有序链表类LinkSortList及main函数的部分代码如下,
请完成LinkSortList类的成员函数,得到对应的运行结果,勿改动main函数。*/
//有序表类
#include <iostream>
using namespace std;
template <class T>
struct Node
{
T data;
Node<T> *next;
};
template <class T>
class LinkSortList
{
public:
LinkSortList( ); //建立只有头结点的空链表
~LinkSortList(); //析构函数
void Insert(T x); //在有序单链表中插入元素x使序列仍有序
int Length(); //求表长
int DeleteOdd(); //在单链表中删除所有奇数,返回值为奇数个数
void DispList( ); //遍历有序单链表,按序号依次输出各元素
private:
Node<T> *first; //单链表的头指针
};
template <class T>
LinkSortList<T>::LinkSortList( )//建立只有头结点的空链表
{
first = new Node<T>;
first->next = nullptr;
}
template <class T>
LinkSortList<T>::~LinkSortList() //析构函数
{
Node<T> *p;
p = first;
while(p!=nullptr)
{
first = first->next;
delete p;
p = first;
}
}
template <class T>
void LinkSortList<T>::Insert(T x) //在有序单链表中插入元素x使序列仍有序
{
//cout<<x<<" ";// 离谱
Node<T> *p = first;
Node<T> *s;
s = new Node<T>;
s->data = x;
if(p->next!=nullptr)
{
while(p->next ->data <= x )
{
p = p->next;
}
s->next = p->next;
p->next = s;
}
else
{
p->next = s ;
}
}
template <class T>
int LinkSortList<T>::Length() //求表长
{
Node<T> *p;
p=first;
int count = 0 ;
while(p!=nullptr)
{
p = p->next;
count ++;
}
return count ;
}
template <class T>
int LinkSortList<T>::DeleteOdd() //在单链表中删除所有奇数,返回值为奇数个数
{
Node<T>*p;
p=first;
int count = 0;
while(p!=nullptr)
{
p=p->next;
if(p->next->data % 2 != 0)
{
p->next->next = p->next;
count ++;
}
}
return count;
}
template <class T>
void LinkSortList<T>::DispList( ) //遍历有序单链表,按序号依次输出各元素
{
Node<T> *p =first;
while(p!=nullptr)
{
p = p->next;
cout << p->data<<" ";
}
cout <<Length();
}
int main( ){
LinkSortList<int> sa;
int x;
while(1)
{
cin>>x;
if(!x)break;//
sa.Insert(x);//cout <<x;
}
sa.DispList();
int count=sa.DeleteOdd();
cout<<"Count of deleted odds:"<<count<<endl;
sa.DispList();
return 0;
}
/*
Input
Output
Sample Input
42 5 32 56 34 7 233 1 0
Sample Output
The length:8
The elements:1 5 7 32 34 42 56 233
Count of deleted odds:4
The length:4
The elements:32 34 42 56 */