Question

用C++方法实现顺序表线性表的建立、插入、删除和逆转操作。并用主函数验证并上机实现。

Answer 1

#include<iostream>
using
namespace
std;
typedef
int
ElemType;
struct
NodeType
{
ElemType
data;
NodeType
*next;
};
class
LinkList
{
private:
NodeType
*Head;
public:
LinkList();//构造
~LinkList();//析构
void
create();//建表
void
insert();
//插入
ElemType
delet();
void
display();
void
inverse();//逆转函数
};
//创建空链表
LinkList::LinkList()
{
Head=new
NodeType;
Head->next=NULL;
Head->data=0;
}
LinkList::~LinkList()
{
NodeType
*p=Head->next;
//使指针p指向链表的第一个节点
while(p!=NULL)
{
Head->next=p->next;
//使头指针指向p的下一个节点
delete
p;
p=Head->next;
//使p节点指向头指针向的那个节点
}
delete
Head;
//最后将头节点也删除
cout<<"已经删除链表!"<<endl;
}
void
LinkList::display()
{
NodeType
*p;
p=Head->next;
while(p!=NULL)
{
cout<<p->data<<"
";
p=p->next;
}
cout<<endl;
}
void
LinkList::create()
//逆转链表元素
{
NodeType
*s;
ElemType
x;
cout<<"请输入一组数据并且以-10结束。"<<endl;
cin>>x;
//输入数据元素。
while(x!=-10)
{
s=new
NodeType;
//动态的申请一个节点
s->data=x;
//给节点的数据域赋值
s->next=Head->next;
//使s指向第一个节点
Head->next=s;
//使头节点指向新申请的s节点
cout<<"输入的元素："<<endl;
cin>>x;
}
cout<<"链表插入结束链表建成!"<<endl;
}
void
LinkList::insert()
{
cout<<"要插入元素的位置："<<endl;
int
i;
cin>>i;
cout<<"要插入的元素："<<endl;
ElemType
x;
cin>>x;
NodeType
*p,*q,*s;
//定义结构体类型指针
int
k=1;
p=Head;
//让p指向Head节点
q=p->next;
//让q指向第一个节点
while(k<i
&&
q!=NULL)
{
p=q;
q=q->next;
k++;
}
if(k==i)
//实现插入
{
s=new
NodeType;
s->data=x;
p->next=s;
s->next=q;
cout<<"记录成功插入!"<<endl;
}
else
cout<<"插入记录失败！";
}
ElemType
LinkList::delet()
{
cout<<"输入要删除的元素："<<endl;
int
x;
cin>>x;
NodeType
*p,*q;
ElemType
y;
int
k=1;
p=Head;
q=p->next;
while(q!=NULL
&&
q->data!=x)
{
p=q;
q=q->next;
}
if(q->data==x)
{
y=q->data;
p->next=q->next;
delete
q;
cout<<"记录成功删除!"<<endl;
}
else
{
cout<<"x不存在"<<endl;
y=-1;
}
return
y;
}
void
LinkList::inverse()
//
链表的逆置
{
NodeType
*p,*q;
p=Head->next;
//让p指向第一个元素
Head->next=NULL;
//让Head的指针域为空
while(p!=NULL)
{
q=p->next;
//让q指向第二个元素
p->next=Head->next;
//让p的指针域为空
Head->next=p;
p=q;
}
}
void
main()
{
LinkList
h;
h.create();
h.display();
h.delet();
h.display();
h.insert();
h.display();
cout<<"进行链表元素逆置"<<endl;
h.inverse();
h.display();
}