C++链表的各种操作

题目描述

代码

#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;
}