假设有两个按元素值非递减有序排列的正整数序列，请以单链表存储结构构造线性表A和B，然后再把A表和B表归并成一个按元素值非递增有序排列的线性表C。同时在C表中实现如下两个功能：1、查找是否存在值为x的元素；2、删除值为y的元素。
要求：
1、单链表A、B和C都不含头结点。
2、首先根据两个非递减序列建立单链表A和B，然后再构造单链表C。
3、创建单链表A和B时，直接从键盘输入两个非递减的序列，0为输入结束的标志。
4、不能利用原表（即A表和B表）的结点空间，即构造的C表中每个结点空间要重新申请。
供参考：
//假设有两个按元素值非递减有序排列的正整数序列，请以单链表存储结构构造线性表A和B，
//然后再把A表和B表归并成一个按元素值非递增有序排列的线性表C。
//同时在C表中实现如下两个功能：1、查找是否存在值为x的元素；2、删除值为y的元素。
//要求：
//1、单链表A、B和C都不含头结点。
//2、首先根据两个非递减序列建立单链表A和B，然后再构造单链表C。
//3、创建单链表A和B时，直接从键盘输入两个非递减的序列，0为输入结束的标志。
//4、不能利用原表（即A表和B表）的结点空间，即构造的C表中每个结点空间要重新申请。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node* next;
}LNode, * LinkList;
//创建不含头结点的单链表
void CreLinkListTail(LinkList* L)
{
LNode* s = NULL, * r = NULL;
ElemType x;
while (1)
{
scanf("%d", &x);
if (x == 0) break; //0 为输入结束
s = (LNode*)malloc(sizeof(LNode));
s->next = NULL;
s->data = x;
if ((*L) == NULL)
(*L) = s;
else
r->next = s;
r = s;
}
}
//输出链表
void OutPut(LinkList L)
{
LNode* p = L;
while (p != NULL)
{
printf(p == L ? "%d" : " %d", p->data);
p = p->next;
}
printf("\n");
}
//A表和B表归并成一个按元素值非递增有序排列的线性表C
LinkList MergeList(LNode* La, LNode* Lb, LNode* Lc)
{
LNode* pa = La, *pb = Lb;
while (pa && pb)
{
LNode* pc = (LNode*)malloc(sizeof(LNode));//Lc 的新结点
pc->next = NULL;
if (pa->data<= pb->data){
pc->data = pa->data;
pa = pa->next;
}
else{
pc->data = pb->data;
pb = pb->next;
}
pc->next = Lc;
Lc = pc;
}
if (pa){
while(pa){
LNode* pc = (LNode*)malloc(sizeof(LNode));
pc->next =NULL;
pc->data = pa->data;
pc->next = Lc;
Lc = pc;
pa = pa->next;
}
}
else{
while(pb){
LNode* pc = (LNode*)malloc(sizeof(LNode));
pc->next =NULL;
pc->data = pb->data;
pc->next = Lc;
Lc = pc;
pb = pb->next;
}
}
return Lc;
}
//查找是否存在值为x的元素
LNode* FindNode(LinkList L, ElemType x)
{
LinkList p = L;
while (p){
if (p->data == x)
return p;
p = p->next;
}
if (!p)
return NULL;
}
//删除值为y的元素
LinkList DeleteNode(LinkList L, ElemType x)
{
LinkList p = L, pr = NULL;
while (p){
if (p->data == x)
{
if (p == L){
LNode *q = p;
L = p->next;
free(q);
p = L;
}
else{
LNode *q = p;
pr->next = p->next;
free(q);
p = pr;
}
}
else{
pr = p;
p = p->next;
}
}
return L;
}
int main()
{
int x;
LinkList La = NULL ,Lb = NULL ,Lc = NULL;
printf("请输入链表La的非递减的序列元素，0 为输入结束的标志:\n");
CreLinkListTail(&La);
printf("输出建立后的La单链表:\n");
OutPut(La);
printf("请输入链表Lb的非递减的序列元素，0 为输入结束的标志:\n");
CreLinkListTail(&Lb);
printf("输出建立后的Lb单链表:\n");
OutPut(Lb);
printf("输出归并后的Lc单链表:\n");
Lc = MergeList(La, Lb, Lc);
OutPut(Lc);
printf("请输入查找的元素值:\n");
scanf("%d", &x);
if (FindNode(Lc, x))
printf("链表存在值为%d的元素\n", x);
else
printf("链表不存在值为%d的元素\n", x);
printf("请输入待删除的元素值:\n");
scanf("%d", &x);
Lc = DeleteNode(Lc,x);
printf("输出删除元素%d后的Lc单链表:\n",x);
OutPut(Lc);
return 0;
}
void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc)// 算法2.17
{ // 已知单链线性表La和Lb的元素按值非递减排列。
// 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列
LinkList pa = La->next, pb = Lb->next, pc;
Lc = pc = La; // 用La的头结点作为Lc的头结点
while (pa && pb)//循环条件
{
if (pa->data <= pb->data)//摘取pa所指结点
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
else { //摘取pb所取结点
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb;// 将非空表的剩余段插入pc后
free(Lb);//deletd Lb; 释放Lb的头结点
Lb = NULL;
}
#include<iostream>
using namespace std;
#include <ctime>
typedef int ElemType;
//节点定义
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//手动方式创建链表
LinkList Manual_Create_LinkList(int n)
{ cout<<"采用手动方式创建链表："<<endl;
LinkList _LinkList = new LNode();
if(_LinkList)
{_LinkList->next = NULL;}
for(int i = 0 ; i < n ; i++)
{ LinkList p = new LNode();
cout<<"输入第"<<(i+1)<<"个元素：";
cin>>p->data;
p->next = _LinkList->next;
_LinkList->next = p;
}return _LinkList;}
//自动方式创建链表
LinkList Auto_Create_LinkList(int n)
{ cout<<"采用自动随机数方式创建链表："<<endl;
LinkList _LinkList = new LNode();
if(_LinkList)
{_LinkList->next = NULL;}
srand(time(0)); //seed
for(int i = n; i > 0 ; i--)
{
LinkList p = new LNode();
p->data = rand() % 100+ 1;
p->next = _LinkList->next;
_LinkList->next = p;
}
return _LinkList;
}
/*插入非递减有序单向链表*/
void Insert_Sort_LinkList(LinkList &_LinkList,ElemType _Var)
{
LinkList _LinkList1,_LinkList2;
_LinkList1 = new LNode();
_LinkList1->data = _Var;
_LinkList2=_LinkList;
while(_LinkList2->next && _LinkList2->next->data <=_Var)
{_LinkList2 = _LinkList2->next;}
_LinkList1->next = _LinkList2->next;
_LinkList2->next = _LinkList1;
}
//建立非递减有序单向链表
LinkList Manual_Create_Ordered_LinkList(int _int)
{
cout<<"采用手动方式建立非递减有序单向链表："<<endl;
LinkList _LinkList = new LNode();
if(_LinkList)
{_LinkList->next = NULL;}
int i = 0;int j = 0;int k = 0;ElemType _Var;
for(i=0;i<_int;i++)
{
cout<<"输入第"<<(i+1)<<"个元素：";
cin>>_Var;
Insert_Sort_LinkList(_LinkList,_Var);
}
return _LinkList;
}
//销毁链表
void Destroy_LinkList(LinkList *myLinkList)
{
LinkList _LinkList1,_LinkList2;
if(!(*myLinkList))
{cout<<"链表不存在！"<<endl;return;}
_LinkList1 = *myLinkList;
while(_LinkList1 != NULL)
{
_LinkList2 = _LinkList1;
_LinkList1 = _LinkList1->next;
delete(_LinkList2);
}
*myLinkList = NULL;
}
//遍历链表
void Traveral_LinkList(LinkList myLinkList)
{
cout<<"------------------------------"<<endl;
cout<<"遍历链表中的元素："<<endl;
int i = 0;
/*第一种遍历方式*/
LinkList _LinkList = myLinkList->next;
while(_LinkList)
{
cout<<"输出第"<<(i+1)<<"个元素："<<_LinkList->data<<endl;
_LinkList = _LinkList->next;
i++;
}
/*第二种遍历方式*/
/*
LinkList _LinkList;
for(_LinkList = myLinkList->next;_LinkList;_LinkList=_LinkList->next)
{
cout<<"输出第"<<i<<"个元素："<<_LinkList->data<<endl;
i++;
}
*/
cout<<"------------------------------"<<endl;
}
//查找元素
LinkList Locate_LinkList(LinkList myLinkList,ElemType x)
{ while(myLinkList && myLinkList->data != x)
{
myLinkList = myLinkList->next;
}
return myLinkList;
}//反转链表
void Reverse_LinkList(LinkList &myLinkList)
{
LinkList TempLinkList = NULL;
LinkList _LinkList = myLinkList->next; //指向第一个元素
myLinkList->next = NULL; //指向最后一个元素
while(_LinkList)
{
TempLinkList = _LinkList;
_LinkList = _LinkList->next; //下移
TempLinkList->next = myLinkList->next;
myLinkList->next = TempLinkList;
}
}
/*删除指定元素*/
void Delete_LinkList(LinkList myLinkList,ElemType x)
{
int i = 0;
if(!myLinkList)
{cout<<"链表不存在！"<<endl;return;}
/*[Begin]第一种方法*/
/*
LinkList _LinkList1 = myLinkList;
LinkList _LinkList2 = myLinkList->next;
while(_LinkList2 && _LinkList2->data != x)
{ _LinkList1 = _LinkList2;
_LinkList2 = _LinkList2->next;
} if(!_LinkList2)
{cout<<"值没有找到！"<<endl;return;}
else
{ _LinkList1->next = _LinkList2->next;
delete(_LinkList2);
}
*/
/*[End]第一种方法*/
/*[Begin]第二种方法*/
/**/
LinkList _LinkList = myLinkList;
//循环条件：下个结点不为NULL，并且下个结点不为x
while(_LinkList->next != NULL && _LinkList->next->data != x)
{_LinkList = _LinkList->next;}
//判断是否已经循环到最后一个结点
if(_LinkList->next == NULL)
{cout<<"值没有找到！"<<endl;return;}
LinkList TempLinkList = _LinkList->next;
_LinkList->next = TempLinkList->next;
delete(TempLinkList);
/*[End]第二种方法*/
}
void main()
{ LinkList myLinkList;
int i=0;int num = 0;
/*[Begin]手动创建链表－－－－－－－－－－－－－－－－－－－－*/
cout<<"使用手动输入创建链表，输入要创建的链表的元素个数：";
cin>>num;
myLinkList = Manual_Create_LinkList(num);
Traveral_LinkList(myLinkList); //遍历链表
/*[End]手动创建链表－－－－－－－－－－－－－－－－－－－－－*/
/*[Begin]删除元素值－－－－－－－－－－－－－－－－－－－－－*/
cout<<"输入要删除的元素值：";
cin>>num;
Delete_LinkList(myLinkList,num);
Traveral_LinkList(myLinkList); //遍历链表
/*[End]删除元素值－－－－－－－－－－－－－－－－－－－－－－*/
Destroy_LinkList(&myLinkList); //销毁链表
/*[Begin]随机数创建链表－－－－－－－－－－－－－－－－－－－－－*/
num = 0;
cout<<"使用随机数创建链表，输入要创建的链表的元素个数：";
cin>>num;
myLinkList = Auto_Create_LinkList(num);
Traveral_LinkList(myLinkList); //遍历链表
/*[End]随机数创建链表－－－－－－－－－－－－－－－－－－－－－－*/
/*[Begin]链表元素反转－－－－－－－－－－－－－－－－－－－－－*/
cout<<"将随机数创建的链表元素反转：";
Reverse_LinkList(myLinkList);
Traveral_LinkList(myLinkList); //遍历链表
/*[End]链表元素反转－－－－－－－－－－－－－－－－－－－－－－*/
Destroy_LinkList(&myLinkList); //销毁链表
/*[Begin]建立非递减有序单向链表－－－－－－－－－－－－－－－－－－－－－*/
cout<<"使用手动输入建立非递减有序单向链表，输入要创建的链表的元素个数：";
cin>>num;
myLinkList = Manual_Create_Ordered_LinkList(num);
Traveral_LinkList(myLinkList); //遍历链表
/*[End]建立非递减有序单向链表－－－－－－－－－－－－－－－－－－－－－－*/
}
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std;
typedef char ElemType;
typedef struct Node{
ElemType data;
struct Node *next;
}Node, *LinkList;
LinkList CreateList()
{
LinkList L;
ElemType c;
L = (LinkList)malloc(sizeof(Node));
L->next = NULL;
Node *p , *tail;
tail = L;
c = getchar();
while(c != '#')
{
p = (Node *)malloc(sizeof(Node));
p->data = c;
tail->next = p;
tail = p;
c = getchar();
}
tail->next = NULL;
return L;
}
void ShowList(LinkList L)
{
Node *p;
p = L->next;
while(p != NULL)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
LinkList MergeList(LinkList LA, LinkList LB)
{
LinkList LC;
Node *pa, *pb, *r;
pa = LA->next;
pb = LB->next;
LC = LA;
LC->next = NULL;
r = LC;
while(pa != NULL && pb != NULL)
{
if(pa->data <= pb->data)
{
r->next = pa;
r = pa;
pa = pa->next;
}
else
{
r->next = pb;
r = pb;
pb = pb->next;
}
if(pa)
{
r->next = pa;
}
else
{
r->next = pb;
}
}
return LC;
}
int main()
{
LinkList LA;
LA = CreateList();
getchar();
LinkList LB;
LB = CreateList();
cout << "LA:" << endl;
ShowList(LA);
cout << "LB:" << endl;
ShowList(LB);
LinkList LC;
LC = MergeList(LA, LB);
cout << "MergeList:" << endl;
ShowList(LC);
return 0;
}
运行报错的那个，稍微改一下即可。
这道题，看起来好难，我尽然写到一半