基于链表的两个非递减有序序列的合并(精修版本，完美版本)

2018-10-22

#数据结构

描述
给定两个非递减的整数序列A和B，利用链表表示序列A和B，将A和B合并为一个非递增的有序序列C，序列C允许有重复的数据。要求空间复杂度为O(1)。

输入
多组数据，每组数据有三行，第一行为序列A和B的长度n和m，第二行为序列A的n个元素，第三行为序列B的m个元素（元素之间用空格分隔）。n=0且m=0时输入结束。

输出
对于每组数据输出一行，为合并后的序列，每个数据之间用空格分隔。

样例输入1 复制
5 5
1 3 5 7 9
2 4 6 8 10
5 6
1 2 2 3 5
2 4 6 8 10 12
0 0
样例输出1
10 9 8 7 6 5 4 3 2 1
12 10 8 6 5 4 3 2 2 2 1

#include<iostream>
#define OK 1
using namespace std;
typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
bool InintList(LinkList &L)
{
	L=new LNode;
	L->next=NULL;
	return OK;
}
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)
{
	LNode *pa;
	LNode *pb;
	LNode *q;//暂时存储指针 
	pa=La->next;
	pb=Lb->next;
	Lc=La;
	Lc->next=NULL;//不可以省略，pa已经保存了La->next,没有关系了 
	while(pa||pb)
	{
		if(!pa)  //La表为空，对Lb表处理 
		{
			q=pb->next; 
			pb->next=Lc->next;
			Lc->next=pb;
			pb=q;
		}
		else if(!pb)
		{
			q=pa->next;
			pa->next=Lc->next;
			Lc->next=pa;
			pa=q;
		}
		else if(pa->data<=pb->data)
		{    
			q=pa->next; 
			pa->next=Lc->next;
			Lc->next=pa;
			pa=q;
		}
		else
		{
			q=pb->next;
			pb->next=Lc->next;
			Lc->next=pb;
			pb=q; 
		} 
	}
	delete Lb;
}
int main()
{
	int num1,num2; 
	while(cin>>num1>>num2&&!(num1==0&&num2==0))
	{ 
	LinkList L;
	LinkList S;
	LinkList T;
	InintList(L);
	InintList(S);
	LNode *p;
	LNode *r;
	r=L;
	for(int i=1;i<=num1;i++)
	{
		p=new LNode;
		cin>>p->data;
		p->next=NULL;
		r->next=p;
		r=p;
	}
	r=S;
	for(int i=1;i<=num2;i++)
	{
		p=new LNode;
		cin>>p->data;
		p->next=NULL;
		r->next=p;
		r=p;
	}
	MergeList(L,S,T);
	p=T->next;
	cout<<p->data;
	p=p->next;
	while(p)
	{
		cout<<" "<<p->data;
		p=p->next;
	}
	cout<<endl;} 
	return 0;
}

将两个递增链表合并为一个递增链表（最终版，利用所有已有链表空间，且释放掉其他空间，且用后插法创建链表）

2018-10-22

#数据结构

#include<iostream>
#define OK 1
using namespace std;
typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
bool InintList(LinkList &L)
{
	L=new LNode;
	L->next=NULL;
	return OK;
}
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)
{
	LNode *pa,*pb,*pc,*q;//q是暂时中间体指针 
	pa=La->next;
	pb=Lb->next;
	Lc=La;//用La的节点做Lc的节点，不再创建新的节点。（为了不开辟新的空间来放Lc的头节点）
	pc=Lc; 
	while(pa&&pb)
	{
		if(pa->data<pb->data)
		{
			pc->next=pa;
			pc=pa;
			pa=pa->next;
		}
		else if(pa->data>pb->data)
		{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
		}
		else  //相等时,取一个，删除掉一个 ,也就是delete 
		{
			pc->next=pa;
			pc=pa;
			pa=pa->next;
			q=pb->next;
			delete pb; 
			pb=q;
		}
	}
	pc->next=pa?pa:pb;//之后一段直接继承。
	delete Lb;//释放掉Lb的头节点占用的空间，最后利用全部的空间，没有浪费。 
} 
int main()
{
	int num1,num2;
	cin>>num1>>num2;
	LNode *p1,*p2;
	LNode *r1,*r2;
	LinkList L;//创建头指针，没有创建头节点 
	LinkList S;
	LinkList T; 
	InintList(L);//创建需要用的头节点 ，T不需要 
	InintList(S);
	r1=L;
	r2=S;
	LNode *p;
	for(int i=1;i<=num1;i++)//后插法创立链表 
	{
		 p=new LNode;
		 cin>>p->data;
		 p->next=NULL;
		 r1->next=p;
		 r1=p;
	}
	for(int i=1;i<=num2;i++)
	{
		p=new LNode;
		cin>>p->data;
		p->next=NULL;
		r2->next=p;
		r2=p;
	}
	MergeList(L,S,T);
	p=T->next;
	while(p)
	{
		cout<<p->data<<" ";
		p=p->next;
	}
	return 0;
}

继续练习后插法建立链表（比自己的pre指针创建链表好吗？）

2018-10-22

#数据结构

#include<iostream>
#define OK 1
using namespace std;
typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
bool InintList(LinkList &L)
{
	L=new LNode;
	L->next=NULL;
	return OK;
}
int main()
{
	LinkList L;
	InintList(L);
	int num;
	cin>>num;
	LNode *r;//尾指针
	LNode *p;//输入指针 
	r=L;
	for(int i=1;i<=num;i++)//后插法创建指针 
	{
		p=new LNode;
		cin>>p->data;
		p->next=NULL;
		r->next=p;
		r=p;
	}
	p=L->next;//指向头结点 
	while(p)
	{
		cout<<p->data<<" ";
		p=p->next;
	}
	return 0;
}

查找链表中的最大值

2018-10-22

#数据结构

描述
利用单链表表示一个整数序列，通过一趟遍历在单链表中确定值最大的结点。

输入
多组数据，每组数据有两行，第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔）。当n=0时输入结束。

输出
对于每组数据分别输出一行，输出每个链表的最大值。

样例输入1 复制
5
2 1 3 5 4
6
2 3 10 4 5 1
4
-1 -2 -3 -4
0
样例输出1
5
10
-1

#include<iostream>
#include<cstdio>
#define OK 1
using namespace std;
typedef struct LNode   //这个LNode不能省略 
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
bool InitList(LinkList &L)
{
	L=new LNode;
	L->next=NULL;
	return OK; 
} 
int main()
{
	int num;
	while(cin>>num&&num!=0)
	{
		LinkList L;
		InitList(L);
		L->next=new LNode;//没有会报错 
		LNode *p=L->next;
		LNode *pre=L;
		for(int i=1;i<=num;i++)
		{
			cin>>p->data;
			p->next=new LNode;
			p=p->next;
			pre=pre->next;
		}
		pre->next=NULL;
		LNode *max=L->next;
		p=L->next;
		while(p)
		{
			
			if(max->data<p->data)
				max=p; 
			p=p->next;
		}
		cout<<max->data<<endl;
	}
}

基于链表的两个非递减有序序列的合并

2018-10-22

#数据结构

注意：这道题利用了之前的逆序存储（链表）的方法
注意细节，p3指针的应用

描述
给定两个非递减的整数序列A和B，利用链表表示序列A和B，将A和B合并为一个非递增的有序序列C，序列C允许有重复的数据。要求空间复杂度为O(1)。

输入
多组数据，每组数据有三行，第一行为序列A和B的长度n和m，第二行为序列A的n个元素，第三行为序列B的m个元素（元素之间用空格分隔）。n=0且m=0时输入结束。

输出
对于每组数据输出一行，为合并后的序列，每个数据之间用空格分隔。

样例输入1 复制
5 5
1 3 5 7 9
2 4 6 8 10
5 6
1 2 2 3 5
2 4 6 8 10 12
0 0
样例输出1
10 9 8 7 6 5 4 3 2 1
12 10 8 6 5 4 3 2 2 2 1

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#define OK 1
using namespace std;
typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
bool InintList(LinkList &L)
{
	L=new LNode;
	L->next=NULL;
	return OK;
}
void mergelist(LinkList &L,LinkList &S,LinkList &T)
{
	LNode *p1=L->next;
	LNode *p2=S->next;
	LNode *p3;
	while(p1&&p2)
	{
		if(p1->data<p2->data)
		{
			p3=p1->next;
			p1->next=T->next;
			T->next=p1;
			p1=p3; 
		}
		else if(p1->data>p2->data)
		{
			p3=p2->next;
			p2->next=T->next;
			T->next=p2;
			p2=p3;
	
		}
		else
		{
			p3=p1->next;
			p1->next=T->next;
			T->next=p1;
			p1=p3;
			p3=p2->next;
			p2->next=T->next;
			T->next=p2;
			p2=p3;
		}
	}
	while(p1)
	{
		p3=p1->next;
		p1->next=T->next;
		T->next=p1;
		p1=p3;
	}
	while(p2)
	{
		p3=p2->next;
		p2->next=T->next;
		T->next=p2;
		p2=p3;
	}
}
int main()
{
	LNode *p1;
	LNode *p2;
	int num1,num2;
	while(cin>>num1>>num2&&!(num1==0&&num2==0))
	{
		LinkList L;
		LinkList S;
		LinkList T;
		InintList(L);
		InintList(S);
		InintList(T); 
		L->next=new LNode;
		S->next=new LNode;
		LNode *p1=L->next;
		LNode *pre1=L;
		LNode *p2=S->next;
		LNode *pre2=S;
		for(int i=1;i<=num1;i++)
		{
			cin>>p1->data;
			p1->next=new LNode;
			p1=p1->next;
			pre1=pre1->next;
		}
		pre1->next=NULL;
		for(int i=1;i<=num2;i++)
		{
			cin>>p2->data;
			p2->next=new LNode;
			p2=p2->next;
			pre2=pre2->next;
		}
		pre2->next=NULL;
		mergelist(L,S,T);
		LNode *p=T->next;
		cout<<p->data;
		p=p->next;
		while(p)
		{
			cout<<" "<<p->data;
			p=p->next;
		}
		cout<<endl;
	}
	return 0;
}

查找链表中倒数第k个结点

2018-10-21

#数据结构

注意；技巧题，也就是双指针问题。
描述
利用单链表表示一个整数序列，请实现一个时间复杂度为O(n)、空间复杂度为O(1)的算法，通过一趟遍历在单链表中确定倒数第k个结点。

输入
多组数据，每组数据有三行，第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔），第三行为k。当n=0时输入结束。

输出
对于每组数据分别输出一行，输出每个链表的倒数第k个结点对应的数值。

样例输入1 复制
7
5 2 3 4 50 100 70
3
5
20 30 10 4 5
5
0
样例输出1
50
20

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define OK 1
using namespace std;
typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
LNode *first;
LNode *second;
bool InintList(LinkList &L)
{
	L=new LNode;
	L->next=NULL;
	return OK;
}
int main()
{	
	int num;
	while(cin>>num&&num!=0)
	{
		LinkList L;
		InintList(L);
		L->next=new LNode;
		LNode *p=L->next;
		LNode *pre=L;
		for(int i=1;i<=num;i++)
		{
			cin>>p->data;
			p->next=new LNode;
			p=p->next;
			pre=pre->next;
		}
		pre->next=NULL;
		int position;
		cin>>position;
		first=L->next;
		second=L->next;
		for(int i=1;i<=position;i++)
		{
			first=first->next;
		} 
		while(first)
		{
			first=first->next;
			second=second->next;
		}
		cout<<second->data<<endl; 
	}
	return 0;
}

基于链表的两个递增有序序列的合并

2018-10-21

#数据结构

注意,这题我一直由于没搞清指针和地址的差别而出问题

描述
给定两个递增的整数序列A和B，利用链表表示序列A和B，将A和B合并为一个递增的有序序列C，序列C不允许有重复的数据。要求空间复杂度为O(1)。

输入
多组数据，每组数据有三行，第一行为序列A和B的长度n和m，第二行为序列A的n个元素，第三行为序列B的m个元素（元素之间用空格分隔）。n=0且m=0时输入结束。

输出
对于每组数据输出一行，为合并后的序列，每个数据之间用空格分隔。

样例输入1 复制
5 5
1 3 5 7 9
2 4 6 8 10
3 4
1 5 9
1 2 5 9
0 0
样例输出1
1 2 3 4 5 6 7 8 9 10
1 2 5 9

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#define OK 1
using namespace std;
typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
bool InintList(LinkList &L)
{
	L=new LNode;
	L->next=NULL;
	return OK;
}
void mergelist(LinkList &L,LinkList &S,LinkList &T)
{
	LNode *p1=L->next;
	LNode *p2=S->next;
	//LNode *p3=T->next;//误区 
	LNode *p3=T;//因为要用next来串联 
	LNode *p4;
	while(p1&&p2)
	{
		if(p1->data<p2->data)
		{
			/*p3=p1;
			p3=p3->next;
			p1=p1->next;*///始终要记住p3是一个指针，指向可以变，而每个指针的next才是真正不会变的 
			p3->next=p1;
			p3=p1;
			p1=p1->next; 
		}
		else if(p1->data>p2->data)
		{
			p3->next=p2;
			p3=p2;
			p2=p2->next;
	
		}
		else
		{
			p3->next=p1;
			p3=p1;
			p1=p1->next;
			p4=p2;
			p2=p2->next;
			delete p4;
		}
	}
	p3->next=p1?p1:p2;
	delete S;
}
int main()
{
	LNode *p1;
	LNode *p2;
	int num1,num2;
	while(cin>>num1>>num2&&!(num1==0&&num2==0))
	{
		LinkList L;
		LinkList S;
		LinkList T;
		InintList(L);
		InintList(S);
		InintList(T); 
		L->next=new LNode;
		S->next=new LNode;
		LNode *p1=L->next;
		LNode *pre1=L;
		LNode *p2=S->next;
		LNode *pre2=S;
		for(int i=1;i<=num1;i++)
		{
			cin>>p1->data;
			p1->next=new LNode;
			p1=p1->next;
			pre1=pre1->next;
		}
		pre1->next=NULL;
		for(int i=1;i<=num2;i++)
		{
			cin>>p2->data;
			p2->next=new LNode;
			p2=p2->next;
			pre2=pre2->next;
		}
		pre2->next=NULL;
		mergelist(L,S,T);
		LNode *p=T->next;
		cout<<p->data;
		p=p->next;
		while(p)
		{
			cout<<" "<<p->data;
			p=p->next;
		}
		cout<<endl;
	}
	return 0;
}

后插法创建单链表（顺序存储）

2018-10-14

#数据结构

#include<iostream>
#include<cstdio>
#define OK 1
using namespace std;
typedef struct LNode   //这个LNode不能省略 
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
bool InitList(LinkList &L)
{
	L=new LNode;
	L->next=NULL;
	return OK; 
} 
int main()
{
	LinkList L;
	InitList(L);
	LNode *p;
	LNode *last=L; //尾指针 
	for(int i=0;i<5;i++)
	{
		p=new LNode;
		cin>>p->data;
		p->next=NULL;   
		last->next=p;   //尾指针指向它 
		last=p; 
	}
	p=L->next;
	while(p)
	{
		cout<<p->data<<endl;
		p=p->next;
	}
	return 0;
}

前插法创建单链表(逆序存储)

2018-10-14

#数据结构

#include<iostream>
#include<cstdio>
#define OK 1
using namespace std;
typedef struct LNode   //这个LNode不能省略 
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
bool InitList(LinkList &L)
{
	L=new LNode;
	L->next=NULL;
	return OK; 
} 
int main()
{
	LinkList L;
	InitList(L);
	LNode *p;
	for(int i=0;i<5;i++)
	{
		p=new LNode;
		cin>>p->data;
		p->next=L->next;
		L->next=p;
	}
	p=L->next;
	while(p)
	{
		cout<<p->data<<endl;
		p=p->next;
	}
	return 0;
}

数据结构栈的实现（顺序表）

2018-10-14

#数据结构

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#define MAXSIZE 100
#define OK 1
using namespace std;
typedef struct
{
	char no[20];
	char name[50];
	double price;
}BOOK;
typedef struct
{
	BOOK *base;
	BOOK *top;
	int stacksize;
}SqStack;
bool InitStack(SqStack &S)
{
	S.base=new BOOK[MAXSIZE];
	if(!S.base) exit(0);
	S.top=S.base;
	S.stacksize=MAXSIZE;
	return OK; 
}
bool Push(SqStack &S,BOOK e)
{
	if((S.top-S.base)==S.stacksize) return 0;
	*S.top++=e;
	return OK;
}
bool Pop(SqStack &S,BOOK &e)
{
	if(S.top==S.base) return 0;
	e=*(--S.top);     //栈顶元素出栈 
	return OK;
}
BOOK GetTop(SqStack &S)
{
	if(S.top!=S.base)
	return *(--S.top);
} 
int main()
{
	SqStack S;
	InitStack(S);
	BOOK p;
	while(cin>>p.no>>p.name>>p.price)
	{
		if(p.no[0]=='0'&&p.name[0]=='0'&&fabs(p.price-0.0)<1e-6)
		 break;
		Push(S,p);
	}
	p=GetTop(S);
	cout<<"栈的最高的元素"<<p.no<<" "<<p.name<<" "<<p.price<<endl;
	S.top++;
	BOOK pp;
	cout<<"栈的每个元素"<<endl; 
	while(Pop(S,pp))
	{
		cout<<pp.no<<" "<<pp.name<<" "<<pp.price<<endl;
	}
	return 0;
}