【数据结构】单链表的创建、插入、删除及合并

定义一个链表结构的带头结点的结构体

typedef struct lst{
    int data;
    struct lst *next;
} LNode,*LinkList;

本文解决以下问题：

1、编写函数，创建一个带头结点的单链表（数据自拟）；

2、编写函数，在单链表的指定位置插入一个元素；

3、编写函数，在单链表的指定位置删除一个元素；

4、编写函数，将两个有序链表合并成一个新的有序链表；

一、各函数代码如下：

写在前面：由于题目要求无法将链表内的元素显示在控制台上，故预先造一个遍历链表中所含元素的函数——

void myprint(LNode *head)//显示单链表中各数据，以实现用户交互

 

编写函数，创建一个带头结点的单链表（数据自拟）；

LNode *mycreat()//创建单链表
{
	int m=0;
	LNode *head=NULL,*p=NULL,*q=NULL;
	head=new LNode;	//定义头指针并分配内存 
	q=head;
	cout<<"Wonder creating a new list,please input (int)data:(End with -1)"<<endl;
	cin>>m;
	while(m!=-1){
		p=new LNode;	//开辟一个新的内存 
		q->next=p;		//单链表的首元结点指向该地址 
		p->data=m;
		q=p;
		cin>>m;
	}
	q->next=NULL;
	return head;
}

编写函数，在单链表的指定位置插入一个元素；

void myinsert(LNode *head,int i,int m)//插入，i为插入位置，m为待插入元素 
{
	LNode *p=NULL,*s=NULL;
	int j=0;
	p=head;
	while(p!=NULL)
	if(p&&(j<i-1)){
		p=p->next;
        j++;
	}
	else break;
    s=new LNode;
	s->data=m;
	s->next=p->next;
	p->next=s;
}

编写函数，在单链表的指定位置删除一个元素；

int mydelete(LNode *head,int i)//删除
{
	LNode *p=NULL,*q=NULL;
	int j=0;
	p=head;
	while(p!=NULL){
		if((p->next)&&(j<i-1)){
			p=p->next;
			j++;
		}else break;
	}
	if(!(p->next)||(j>i-1))
	   return 0;
	q=p->next;
	p->next=q->next;
	delete q;
	return 1;
}

编写函数，将两个有序链表合并成一个新的有序链表；

                                ↑            ↑                        ↑

再次审题，我们可以看到本题的条件是给出的两个有序链表，考虑到用户输入的链表元素无规则性，我们在“合并”操作前，还需将两个链表进行“排序”~QAQ

void mysort(LNode *head)//排序 
{
	LNode *p=NULL,*q=NULL,*r=NULL,*t=NULL;
	int flag = 1;
	while(flag){
		p = head;
		q = head->next;
		flag = 0;
		while(q != NULL){
			r = q->next;
			if(r == NULL){
				break;
			}else if(q->data > r->data){
				t = r->next;
				q->next = t;
				r->next = q;
				p->next = r;
				p = r;
				q = p->next;
				r = q->next;
				flag = 1;
			}else{
				p = q;
				q = p->next;
			}
		}
	}
}

LNode *MergerLinklist(LNode *L0,LNode *L1,LNode *L2)//有序单链表的合并，生成一个有序的单链表
{
	LNode *pa=NULL,*pb=NULL,*pc=NULL,*p=NULL;
	p=L2;
	pa=L0->next;pb=L1->next;
	L2=pc=L0;
	while(pa&&pb){
		if(pa->data <= pb->data){
			pc->next=pa;
			pc=pa;
			pa=pa->next;
		}
		else{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
		}
	}
	pc->next=pa?pa:pb;
	delete L1;
	cout<<"after mixing the two lists:";
	p=L0->next;
	while(p){
		printf("%5d",p->data);
		p=p->next;
	}
	cout<<endl;
}

二、完整代码（含各函数及main）

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct lst{
    int data;
    struct lst *next;
} LNode,*LinkList;
LNode *mycreat();//创建单链表
void myinsert(LNode *head,int i,int m);//插入
int mydelete(LNode *head,int i);//删除
void mysort(LNode *head);//排序
LNode *MergerLinklist(LNode *L0,LNode *L1,LNode *L2);//有序单链表的合并，生成一个有序的单链表
void myprint(LNode *head);//显示单链表中各数据，以实现用户交互 
int main(void)
{
	LNode *head=NULL,*nhead=NULL;
	int k=0,i=0,m=0,j=0;
	head=mycreat();
	printf("new list:");
	myprint(head);
    cout<<"Want to insert list,please input place:";
	cin>>i;
	cout<<"please input insert data:";
	cin>>m;
	myinsert(head,i,m);
	printf("after inserting:");
	myprint(head);
	cout<<"Want to delete list,please input place:";
	cin>>i;
	k=mydelete(head,i);
	if(k==1){
        cout<<"after deleting:";
        myprint(head);
    }
    else {	
		cout<<"not exist!"<<endl<<"Please reput again!";
    }
    mysort(head);
    cout<<"Sorting the list..."<<endl<<"after that,show the list:";
    myprint(head);
    cout<<endl<<"Plum blooms again!!!"<<endl;
    nhead=mycreat();
    printf("new list:");
	myprint(nhead);
	cout<<"after sorting:";
	mysort(nhead);
	myprint(nhead);
	LNode *mhead;
    MergerLinklist(head,nhead,mhead);
	return 0;
}
LNode *mycreat()//创建单链表
{
	int m=0;
	LNode *head=NULL,*p=NULL,*q=NULL;
	head=new LNode;	//定义头指针并分配内存 
	q=head;
	cout<<"Wonder creating a new list,please input (int)data:(End with -1)"<<endl;
	cin>>m;
	while(m!=-1){
		p=new LNode;	//开辟一个新的内存 
		q->next=p;		//单链表的首元结点指向该地址 
		p->data=m;
		q=p;
		cin>>m;
	}
	q->next=NULL;
	return head;
}
void myinsert(LNode *head,int i,int m)//插入，i为插入位置，m为待插入元素 
{
	LNode *p=NULL,*s=NULL;
	int j=0;
	p=head;
	while(p!=NULL)
	if(p&&(j<i-1)){
		p=p->next;
        j++;
	}
	else break;
    s=new LNode;
	s->data=m;
	s->next=p->next;
	p->next=s;
}
int mydelete(LNode *head,int i)//删除
{
	LNode *p=NULL,*q=NULL;
	int j=0;
	p=head;
	while(p!=NULL){
		if((p->next)&&(j<i-1)){
			p=p->next;
			j++;
		}else break;
	}
	if(!(p->next)||(j>i-1))
	   return 0;
	q=p->next;
	p->next=q->next;
	delete q;
	return 1;
}
void mysort(LNode *head)//排序 
{
	LNode *p=NULL,*q=NULL,*r=NULL,*t=NULL;
	int flag = 1;
	while(flag){
		p = head;
		q = head->next;
		flag = 0;
		while(q != NULL){
			r = q->next;
			if(r == NULL){
				break;
			}else if(q->data > r->data){
				t = r->next;
				q->next = t;
				r->next = q;
				p->next = r;
				p = r;
				q = p->next;
				r = q->next;
				flag = 1;
			}else{
				p = q;
				q = p->next;
			}
		}
	}
}
LNode *MergerLinklist(LNode *L0,LNode *L1,LNode *L2)//有序单链表的合并，生成一个有序的单链表
{
	LNode *pa=NULL,*pb=NULL,*pc=NULL,*p=NULL;
	p=L2;
	pa=L0->next;pb=L1->next;
	L2=pc=L0;
	while(pa&&pb){
		if(pa->data <= pb->data){
			pc->next=pa;
			pc=pa;
			pa=pa->next;
		}
		else{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
		}
	}
	pc->next=pa?pa:pb;
	delete L1;
	cout<<"after mixing the two lists:";
	p=L0->next;
	while(p){
		printf("%5d",p->data);
		p=p->next;
	}
	cout<<endl;
}
void myprint(LNode *head)//显示单链表中各数据，以实现用户交互
{
	LNode *p=NULL;
	p=head->next;
    if(p==NULL)
	cout<<"empty list!";
	else
	do{	
        printf("%5d",p->data);
		p=p->next;
	}while(p!=NULL);
	cout<<endl;
}

执行效果如下：

分享完毕~

欢迎小伙伴们在文下评论和私信喔~