题目描述
代码
#include<iostream>
#include<algorithm>
using namespace std;
struct sqList{
int data;
sqList *next;
};
sqList* ListInitNodata(int len); //根据指定的长度初始化链表，不需要输入数值，全部初始化为0
sqList* ListInit(int len); //根据指定的长度和数值初始化链表，需要自己输入数值
void dsiPlay(sqList *head); //展示链表的相关信息
void insertList(sqList *head, int k, int value); //在链表head第k个元素之前插入一个数值value
void findElement(sqList *head, int value); //在链表head中查询指定的数值
void deleList(sqList *head, int k); //将链表head第k个元素删除
void sortList(sqList *head); //对链表head进行排序
sqList* mergeList(sqList *headA, sqList *headB); //将两个递增链表合并为一个递增列表
int main()
{
int length, lengthA, lengthB;
cout<<"请输入链表的长度：";
cin>>length;
sqList* head = ListInit(length); //初始化列表
cout<<endl<<"初始化后的链表"<<endl;
dsiPlay(head); //展示初始化列表
insertList(head, 3, 100); //在指定位置插入值
cout<<endl<<"插入值后的链表"<<endl;
dsiPlay(head); //展示插入值后的链表
cout<<endl;
findElement(head, 100); //在链表中查询指定值
deleList(head, 3);
cout<<endl<<"删除值后的链表"<<endl;
dsiPlay(head);
cout<<endl<<"请输入链表A和链表B的长度：";
cin>>lengthA>>lengthB;
sqList* headA = ListInit(lengthA); //初始化列表A
sqList* headB = ListInit(lengthB); //初始化列表B
sortList(headA);
cout<<endl<<"排序后的链表A"<<endl;
dsiPlay(headA);
sortList(headB);
cout<<endl<<"排序后的链表A"<<endl;
dsiPlay(headB);
head = mergeList(headA, headB);
cout<<endl<<"排序后的合并链表"<<endl;
dsiPlay(head);
return 0;
}
sqList* ListInitNodata(int len) //根据指定的长度初始化链表，不需要输入数值，全部初始化为0
{
sqList *head = new sqList;
head->data = len; //将链表的长度放置在头节点中
head->next = NULL;
sqList *p = head;
for(int i=0; i<len; i++){
sqList *q = new sqList;
q->next = NULL;
q->data = 0;
p->next = q;
p = q;
}
return head;
}
sqList* ListInit(int len) //根据指定的长度和数值初始化链表，需要自己输入数值
{
sqList *head = new sqList;
head->data = len; //将链表的长度放置在头节点中
head->next = NULL;
sqList *p = head;
cout<<"请输入顺序表中的值："<<endl;
for(int i=0; i<len; i++){
sqList *q = new sqList;
q->next = NULL;
cin>>q->data;
p->next = q;
p = q;
}
return head;
}
void dsiPlay(sqList *head) //展示链表的相关信息
{
int len = head->data;
cout<<"链表当前长度为："<<len<<endl;
sqList *p = head->next;
cout<<"链表内有效数值为："<<endl;
for(int i=0; i<len; i++)
{
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
}
void insertList(sqList *head, int k, int value) //在链表head第k个元素之前插入一个数值value
{
if( k>head->data ){
cout<<"所选择位置超出链表长度，插入位置无效"<<endl;
return;
}
sqList *p = head;
for(int i=1; i<k; i++){
p = p->next;
}
sqList *q = new sqList;
q->data = value;
q->next = p->next;
p->next = q;
head->data++;
}
void findElement(sqList *head, int value) //在链表head中查询指定的数值
{
int len = head->data;
sqList *p = head->next;
for(int i=0; i<len; i++){
if( value==p->data ){
cout<<"所查询数值"<<value<<"在链表中所在位置为："<< i+1<<endl;
return;
}
p = p->next;
}
cout<<"未在链表中查询到指定值"<<endl;
}
void deleList(sqList *head, int k) //将链表head第k个元素删除
{
if( k>head->data ){
cout<<"所选择位置超出链表长度，删除位置无效"<<endl;
return;
}
sqList *p = head;
for(int i=1; i<k; i++){
p = p->next;
}
sqList *q = p->next;
p->next = p->next->next;
delete(q);
head->data--;
}
void sortList(sqList *head) //对链表head进行排序
{
int len = head->data;
int *l = (int*)malloc(len*sizeof(int));
sqList *p = head->next;
for(int i=0; i<len; i++){
l[i] = p->data;
p = p->next;
}
sort(l, l+len);
p = head->next;
for(int i=0; i<len; i++){
p->data = l[i];
p = p->next;
}
}
sqList* mergeList(sqList *headA, sqList *headB) //将两个递增链表合并为一个递增列表
{
int lenA = headA->data;
int lenB = headB->data;
int len = lenA + lenB;
sqList *head = ListInitNodata(len);
int *l = (int*)malloc(len*sizeof(int));
sqList *p = headA->next;
for(int i=0; i<lenA; i++){
l[i] = p->data;
p = p->next;
}
sqList *q = headB->next;
for(int i=0; i<lenB; i++){
l[i+lenA] = q->data;
q = q->next;
}
sort(l, l+len);
p = head->next;
for(int i=0; i<len; i++){
p->data = l[i];
p = p->next;
}
return head;
}
