#include <iostream>
using namespace std;
#define LENGTH1 6
#define LENGTH2 10
typedef struct node{
int data;
node* next;
} *List;
//typedef node* List;
List mergeList(List &list1,List &list2)
{
List list,temp;
List tempList=new node;
list=tempList;
List pList1 = list1;
List pList2 = list2;
List pCurNode = NULL;
while(pList1 && pList2)
{
if (pList1->data <= pList2->data)
{
pCurNode = pList1;
pList1 = pList1->next;
}
else if (pList1->data > pList2->data)
{
pCurNode = pList2;
pList2 = pList2->next;
}
tempList->data=pCurNode->data;
temp=tempList;
tempList->next=new node;
tempList=tempList->next;
}
tempList=temp;
if (pList1 == NULL && pList2 == NULL)
{
tempList->next=NULL;
return list;
}
List rest = (pList1 != NULL) ? pList1 : pList2;
tempList->next=rest;
return list;
}
//若第K大的值存在则返回第K大的值,否则返回-1;
int findK(List &list1, List &list2, int k)
{
List pList1 = list1;
List pList2 = list2;
List pCurNode = NULL;
int count = 0;
while(pList1 && pList2)
{
if (pList1->data <pList2->data)
{
pCurNode = pList1;
int temp = pList1->data;
pList1= pList1->next;
while(pList1)
{
if (pList1->data != temp)
{
break;
}
pList1= pList1->next;
}
count++;
}
else if (pList1->data > pList2->data)
{
pCurNode = pList2;
int temp = pList2->data;
pList2= pList2->next;
while(pList2)
{
if (pList2->data != temp)
{
break;
}
pList2= pList2->next;
}
count++;
}
else///相等的时候不计算count值;
{
pCurNode = pList1;
pList1=pList1->next;
}
if (count == k)
{
return pCurNode->data;
}
}
List rest = (pList1 != NULL) ? pList1 : pList2;
while(rest)
{
count++;
if (count == k)
{
return rest->data;
}
int temp = rest->data;
rest= rest->next;
while(rest)
{
if (rest->data != temp)
{
break;
}
rest = rest->next;
}
}
return -1;
}
void display(List &list)
{
List tempList=list;
int cnt=0;
while(tempList)
{
if(cnt==0)
cout<<tempList->data;
else
cout<<","<<tempList->data;
tempList=tempList->next;
cnt++;
}
cout<<endl;
}
void main()
{
int a[LENGTH1]={1,2,3,3,3,5};
int b[LENGTH2]={2,3,3,4,6,7,7,8,8,9};
List list1,tempList1,list2,tempList2,temp;
int i,j,k=4,kLargest;
list1=tempList1=new node;
list2=tempList2=(List)malloc(sizeof(node));
tempList1->data=a[0];
if(LENGTH1==1)
{
tempList1->next=NULL;
}
for(i=1;i<LENGTH1;i++)
{
tempList1->next=new node;
tempList1=tempList1->next;
tempList1->data=a[i];
tempList1->next=NULL;
}
for(j=0;j<LENGTH2;j++)
{
tempList2->data=b[j];
temp=tempList2;
tempList2->next=(List)malloc(sizeof(node));
tempList2=tempList2->next;
}
temp->next=NULL;
List list=mergeList(list1,list2);
cout<<"list1:";
display(list1);
cout<<"list2:";
display(list2);
cout<<"list:";
display(list);
cout<<"请输入K值:";
cin>>k;
kLargest=findK(list1, list2, k);
cout<<"第"<<k<<"大的值为:"<<kLargest<<endl;
}
分享到:
相关推荐
(2)将两个链表合并成一个新的有序表(升序排列),显示链表. 五)单循环链表 (1)建两个带头结点的循环单链表LA,LB单循环链表, (2)将两个循环单链表合并为一个循环单链表,其头指针为LA。 六)单链表应用 建立...
1、 创建线性表类。线性表的存储结构使用链表。 2、 提供操作:自表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。 3、 接收键盘录入的一系列...6、 创建两个有序链表,使用链表遍历器实现链表的合并。
一、实验目的 1、掌握线性表的基本操作:插入、删除、查找。 2、掌握链表遍历器的使用方法。 二、实验内容 1、创建线性表类。线性表的存储结构使用链表。...6、创建两个有序链表,使用链表遍历器实现链表的合并。
主要介绍了JS实现的合并两个有序链表算法,结合实例形式分析了JavaScript链表的定义、节点插入、删除、查找等相关算法实现技巧,需要的朋友可以参考下
基于平行数组与二分查找的有序符号表是《算法》中的经典查找算法,本程序使用 Python 语言,实现有序符号表。 ST.py 包含两个类,ST 和 OrderedST。 ST是无序的符号表,基于链表实现。按照顺序将键值对插入链表。 ...
提高要求:链表合并,将两个递增有序的单链表合并为一个新的单链表。(提示:可以通过建立单链表的方式建立两个递增有序的单链表A和B,然后再将它们合并为一个新的单链表) 编程实现单链表数据结构,包括: 单链表...
## 链表* 实现单链表、循环链表、双向链表,支持增删操作* 实现单链表反转* 实现两个有序的链表合并为一个有序链表* 实现求链表的中间结点 ## 栈* 用数组实现一个顺序栈* 用链表实现一个链式栈* 编程模拟实现一个...
2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。 二 、实验要求 1.预习C语言中结构体的定义与基本操作方法。 2.对单链表的每个基本操作用单独的函数实现。 3.编写完整程序完成下面的实验内容并...
问题:编程实现O(n)时间复杂度内找到一组数据的第K大元素 二分查找、散列表、字符串处理、二叉树、堆、图、回溯、分治、动态回归等。 资源中包括常用语言:c、java、python、go等实现源码,方便参考学习。
slist.dat中存放学生成绩记录,记录之间的逻辑结构是单链表,记录包含学生姓名和成绩两个域。开始时slist.dat为空,通过逐条插入学生记录,建立有序的学生成绩记录,并存放在slist.dat中。 /* 单链表建立、插入、...
3、假设有两个按元素值递增有序的线性表A和B,均以单链表作存储结构,试编写算法将A表和B表归并成一个按元素值递减有序的线性表C,并要求利用原表的空间存放C。 要求:熟练掌握线性表的单链式链接存储结构及在其上...
单链表的各种操作,适合于初学,也适合于复习 单链表操作介绍 1. 创建头节点 2. 创建有数据节点 3. 判断链表是否为空 ...13. 已知两个链表head1和head2各自有序,请把它们合并成一个链表依然有序,要求用递归方法
linked-list C for single linked list and double linked list single_list 结点结构体 创建结点 创建链表 显示链表的数据 获取链表长度 ...合并两个有序链表 查找倒数第K个结点 删除重复结点 查找中间结点
链表中每一个元素称为“结点”,每个结点都应包括两个部分:一为用户需要用的实际数据,二为下一个结点的地址。因此,head指向第一个元素:第一个元素又指向第二个元素;……,直到最后一个元素,该元素不再指向其它...
6.2 合并两个有序链表 6.3 合并K个有序链表 6.4 使用插入排序来排序链表 6.5 归并排序排序链表 6.6 第一个缺少的正数 6.7 排序颜色 7. 查找 7.1 在排序数组中查找数出现的范围 7.2 在排序数组中查找给定值的插入位置...
在某些应用中,对线性链表中的每个结点设置两个指针,一个称为左指针,用以指向其前件结点;另一个称为右指针,用以指向其后件结点。这样的表称为双向链表。 在线性链表中,各数据元素结点的存储空间可以是不连续的...
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 给定一个...
(6)两个有序链表求交(ListIntersection_L) (7)两个有序链表求差(SubList_L) 3. 栈和队列 (1)计算阿克曼函数(AckMan) (2)栈的输出序列(Gen、Perform) (3)递归算法的演示 汉诺塔的算法(Hanoi) ...
将这两个有序单链表合并成一个有序单链表,要求使用两个单链表的原有空间进行 合并,将生成的有序单链表输出显示。 2. 程序中使用的数据结构及符号说明 class Node 表示结点类 class LinkList 表示单链表类 LinkList...
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 给定一个...