■ 线性表ADT实现
假设线性表ADT的数据元素类型为正整数，采用带头结点的单链式存储结构。线性表ADT实现的大部分代码已经给出，请补充写出类的两个成员函数insert和reverse。 注意：只需提交需要补充的函数代码，其他代码不能自己重写和修改。
insert函数：在元素值从小到大有序的线性表中插入一个元素，仍然保持有序。
reverse函数：实现线性表元素的倒置，即将线性表中数据元素的顺序反转。
线性表元素输入时，以 endTag 作为结束标志。
例如输入： 3 8 7 2 4 9 1 6 5 0
则输出：9 8 7 6 5 4 3 2 1
预置代码如下： （其中/* */ 部分是要补充的insert和reverse函数）
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef int ElemType; //数据元素类型
class List; //前视定义,否则友元无法定义
//结点类定义
class LinkNode
{ friend class List;
private:
LinkNode *link;
ElemType data;
public:
LinkNode (LinkNode *ptr = NULL) {link=ptr;}
LinkNode(const ElemType & item, LinkNode *ptr = NULL){ data=item;link=ptr;}
~LinkNode(){};
};
//单链表类定义
class List
{ private:
LinkNode *first; //指向链表头结点的指针
public:
List (ElemType x) { first = new LinkNode (x);} // 带头结点
~List (){ MakeEmpty();} //析构函数
void MakeEmpty ( ); //线性表置空
void insert(ElemType val); //在有序线性表中插入元素val
void reverse(); //线性表的倒置
void output(); //线性表的输出
};
void List:: MakeEmpty ( )
{ LinkNode *q;
while ( first->link != NULL )
{ q = first->link; //指向别摘下结点
first->link = q->link;//从链中摘下结点
delete q; //释放摘下的结点
}
};
void List ::output ( )
{ LinkNode *p=first->link;
while(p!=NULL)
{ if(p==first->link) cout<<p->data;
else cout<<" "<<p->data;
p=p->link;
}
cout<<endl;
}
/*
**************************************************
请写出 insert 成员函数
**************************************************
**************************************************
请写出 reverse 成员函数
**************************************************
*/
int main()
{ List list(0);
ElemType endTag=0;
ElemType val;
//下面通过不断读入元素，插入到有序单链表中，建立从小到大的有序单链表
cin>>val;
while(val!=endTag)
{ list.insert(val); //在有序表中插入一个元素
cin>>val;
}
list.reverse (); //线性表倒置
cout<<"The result is:"<<endl;
list.output ();
return 0;
}
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef int ElemType; //数据元素类型
class List; //前视定义,否则友元无法定义
//结点类定义
class LinkNode {
friend class List;
private:
LinkNode *link;
ElemType data;
public:
LinkNode(LinkNode *ptr = NULL) { link = ptr; }
LinkNode(const ElemType &item, LinkNode *ptr = NULL) {
data = item;
link = ptr;
}
~LinkNode() {};
};
//单链表类定义
class List {
private:
LinkNode *first; //指向链表头结点的指针
public:
List(ElemType x) { first = new LinkNode(x); } // 带头结点
~List() { MakeEmpty(); } //析构函数
void MakeEmpty(); //线性表置空
void insert(ElemType val); //在有序线性表中插入元素val
void reverse(); //线性表的倒置
void output(); //线性表的输出
int Length() const;
LinkNode *Search(ElemType x);
LinkNode *Locate(int i);
void Delete(int i,ElemType &x);
};
void List::Delete(int i,ElemType &x) {
LinkNode *p = Locate(i - 1), *q;
q = p->link;
p->link = q->link;
x = q->data;
delete q;
}
LinkNode *List::Locate(int i) {
LinkNode *p = first;
int j = 0;
while (p != NULL && j < i) {
p = p->link;
j++;
}
return p;
}
LinkNode *List::Search(ElemType x) {
LinkNode *p = first->link;
while (p != NULL && p->data != x) {
p = p->link;
}
return p;
}
void List:: MakeEmpty ( ) {
LinkNode *q;
while (first->link != NULL) {
q = first->link; //指向别摘下结点
first->link = q->link;//从链中摘下结点
delete q; //释放摘下的结点
}
};
int List::Length()const {
LinkNode *p = first;
int cnt = 0;
while (p->link != NULL) {
cnt++;
p = p->link;
}
return cnt;
}
void List ::output ( ) {
LinkNode *p = first->link;
while (p != NULL) {
if (p == first->link) cout << p->data;
else cout << " " << p->data;
p = p->link;
}
cout << endl;
}
void List ::insert(ElemType val) {
LinkNode *q = new LinkNode(val);//将要插入的元素
LinkNode *pre = first;
LinkNode *p = first->link;//first是头节点，p是除头节点外的第一个节点
while (p != NULL && p->data < val) {
pre = p;
p = p->link;
}
pre->link = q;
q->link = p;
}
void List ::reverse() {
LinkNode *t, *p;
t = p = first->link;
first->link = NULL;
while (p != NULL) {
t = t->link;
p->link = first->link;
first->link = p;
p = t;
}
}
int main() {
List list(0);
ElemType endTag = 0;
ElemType val;
//下面通过不断读入元素，插入到有序单链表中，建立从小到大的有序单链表
cin >> val;
while (val != endTag) {
list.insert(val); //在有序表中插入一个元素
cin >> val;
}
list.reverse(); //线性表倒置
cout << "The result is:" << endl;
list.output();
return 0;
}