求C语言大作业一份(是链表最佳,其他亦可)
发布网友
发布时间：2022-04-29 19:09
共2个回答
热心网友
时间：2022-06-20 08:54
using namespace std;
struct node
{
int data;
node *next;
};
class list{
public:
list();
~list();
int length();
void input_elem(const int n);//创建长度为n的链表
void insert_elem(const int i,int data);//在某个位置插入元素
void get_elem (const int i);//按序号取元素
int end_point (node *p);//判断是否为最后一个结点
void delete_elem (const int i);//删除元素
void print();//输出链表
node *get_locate(int i);
node *get_head();//取头结点
void set_insert(node *L,int data);//保持递增序列插入节点
void copy_list(node *P,node *Q,node *R);//奇数项和偶数项结点分解开
void same_quality(node *A,node *B,node *C);//求两个递增有序链表的公共元素
private:
int count;
node *head;
};
int list::end_point (node *p)
{
if(p->next==NULL)
return 1;
else return 0;
}
list::list()
{
head=new node;
head->next=NULL;
count=0;
}
list::~list()//从头结点开始一个一个的删除结点
{
node *p,*q;
p = head->next;
while(p!=NULL)
{
q = p;
p = p->next;
delete q;
}
}
int list::length()
{
int n=0;
node *p=head->next;
while(p!=NULL)
{
n++;
p=p->next;
}
return n;
}
void list::input_elem(const int n)
{
node *p,*pre;
pre = head;
for(int i=0;i<n;i++)
{
p=new node;
cin>>p->data;
pre->next=p;
pre=p;
count++;
}
pre->next=NULL;
}
void list ::insert_elem(const int i,int data)
{
node *p,*s;
p=head;
int k=0;
if(i<1||i>count)
{
cout<<"序号错误！"<<endl;
}
else{
while(k!=i-1)
{
p=p->next;
k++;
}
s=new node;
s->data=data;
s->next=p->next;
p->next=s;
count++;
}
}
void list::get_elem (const int i)
{
node *p;
p=head->next;
int k=1;
if (i<1||i>count)
{
cout<<"序号错误！"<<endl;
}
else
{
while (k!=i)
{
p=p->next;
k++;
}
cout<<"该链表的的第"<<i<<"个元素为"<<p->data<<endl;
}
}
void list::delete_elem (const int i)//删除元素
{
node *p,*q;
p=head;
if (i<1||i>count)
{
cout<<"序号错误！"<<endl;
}
else
{
for (int k=1;k<=i-1;k++)
{
p=p->next;
}
q=p->next;
if (end_point(q))
{
delete q;
}
else
{
p->next=q->next;
delete q;
}
count--;
}
}
void list::print()//输出链表
{
node *p;
p=head;
p=p->next;
while (p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
node *list::get_locate(int i)
{
node*u=head;
int m=0;
if(i>count)
return NULL;
while(m<i&&u!=NULL)
{
u=u->next;
m++;
}
if(m==i)
return u;
else return NULL;
}
node *list::get_head()
{
return head;
}
void list::set_insert(node *L,int data)
{
node *p=L,*q;
while (p->next!=NULL&&p->next->data<data)
{
p=p->next;
}
if (p->next==NULL||p->next->data>data)
{
q=new node;
q->data=data;
q->next=p->next;
p->next=q;
}
}
void list::copy_list(node *P,node *Q,node *R)//奇数项和偶数项结点分解开
{
node *q1;
node *r1;
node *p = P;
p = p->next;
node *q = Q;
node *r = R;
while(p!=NULL)
{
q1 = new node;
q1->data = p->data;
q->next = q1;
q = q1;
p = p->next;
if(p!=NULL)
{
r1 = new node;
r1->data = p->data;
r->next = r1;
r = r1;
p = p->next;
}
}
q1->next = NULL;
r1->next = NULL;
}
void list::same_quality(node *A,node *B,node *C)//求两个递增有序链表的公共元素
{
node *Pa ;
node *Pb ;
node *Pc ;
node *u;
Pc=C;
Pa=A->next;
Pb=B->next;
while(Pa!=NULL&&Pb!=NULL)
if (Pa->data<Pb->data)
Pa=Pa->next;
else if(Pa->data>Pb->data)
Pb=Pb->next;
else
{
u=new node;
u->data=Pa->data;
Pc->next=u;
Pc=u;
Pa=Pa->next;
Pb=Pb->next;
}
Pc->next=NULL;
}
int main()
{
list A;
list B;
list C;
int m;
int n;
int i;
int data;
cout<<"创建一个链表A其长度n，请输入n "<<endl;
cin>>n;
cout<<"输入链表的各结点"<<endl;
A.input_elem (n);
while(1)
{
cout<<endl<<endl;
cout<<"1 求链表中第i个结点的指针"<<endl;
cout<<"2 在i之前插入一个数"<<endl;
cout<<"3 删除链表中第i个元素结点"<<endl;
cout<<"4 在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性"<<endl;
cout<<"5 将单链表中的奇数项和偶数项结点分解开 "<<endl;
cout<<"6 求两个递增有序链表L1和L2中的公共元素"<<endl;
cout<<"请输入你的选择:"<<endl;
cin>>m;
cout<<endl;
cout<<endl;
switch(m)
{
case 1:
{
cout<<"******************************************"<<endl;
cout<<"求链表中第i个结点的指针，请输入i："<<endl;
cin>>i;
cout<<"结点i的指针为："<<endl;
cout<<A.get_locate(i)<<endl;
cout<<"******************************************"<<endl;
break;
}
case 2:
{
cout<<"******************************************"<<endl;
cout<<"在i之前插入一个数 ，请输入i:";
cin>>i;
cout<<"请输入要插入的数X:";
cin>>data;
A.insert_elem (i,data);
A.print();
cout<<"******************************************"<<endl;
cout<<endl;
cout<<endl;
break;
}
case 3:
{
cout<<"******************************************"<<endl;
cout<<"删除链表中第i个元素结点:"<<endl;
cin>>i;
A.delete_elem (i);
A.print();
cout<<"******************************************"<<endl;
cout<<endl;
cout<<endl;
break;
}
case 4:
{
cout<<"******************************************"<<endl;
cout<<"创建一个递增的链表长度为n，请输入n:";
cin>>n;
A.input_elem(n);
cout<<"插入一个值为data的元素，并保持其递增有序特性:";
cin>>data;
A.set_insert(A.get_head(),data);
cout<<"******************************************"<<endl;
cout<<endl;
cout<<endl;
break;
}
case 5:
{
cout<<"******************************************"<<endl;
cout<<"创建一个链表长度为n，请输入n: ";
cin>>n;
A.input_elem (n);
A.copy_list (A.get_head(),B.get_head(),C.get_head());
cout<<"链表奇数项的元素为：";
B.print ();
cout<<"链表偶数项的元素为：";
C.print ();
cout<<"******************************************"<<endl;
cout<<endl;
cout<<endl;
break;
}
case 6:
{
cout<<"创建一个链表L1长度为n，请输入n:"<<endl;
cin>>n;
cout<<"输入链表的各结点"<<endl;
A.input_elem (n);
cout<<"创建一个链表L2长度为n，请输入n:"<<endl;
cin>>n;
cout<<"输入链表的各结点"<<endl;
B.input_elem (n);
C.same_quality (A.get_head(),B.get_head(),C.get_head());
cout<<"含有L1和L2相同元素的链表L3为："<<endl;
C.print ();
cout<<"******************************************"<<endl;
cout<<endl;
cout<<endl;
break;
}
}
}
cout<<endl;
return 0;
}
这是一个单链表
热心网友
时间：2022-06-20 08:55
