C++实现单链表按k值重新排序的方法
本文实例讲述了C++实现单链表按k值重新排序的方法。分享给大家供大家参考，具体如下：
题目要求：
给定一链表头节点，节点值类型是整型。
现给一整数k，根据k将链表排序为小于k，等于k，大于k的一个链表。
对某部分内的节点顺序不做要求。
算法思路分析及代码(C)
思路：将链表分为小于k、等于k、大于k的三个链表，然后再合并。
链表结点定义：
typedef struct Node
{
int data;
struct Node* next;
}node, *pNode;
算法代码：
pNode sortLinkedList(pNode head, int k)
{
pNode sHead = NULL;//小头
pNode sTail = NULL;//小尾
pNode eHead = NULL;//等头
pNode eTail = NULL;//等尾
pNode bHead = NULL;//大头
pNode bTail = NULL;//大尾
pNode temp = NULL;
//拆分链表
while (head != NULL)
{
temp = head->next;
head->next = NULL;
if (head->data < k)
{
if (!sHead){
sHead = head;
sTail = head;
}
else{
sTail->next = head;
sTail = head;
}
}
else if (head->data == k)
{
if (!eHead){
eHead = head;
eTail = head;
}
else{
eTail->next = head;
eTail = head;
}
}
else
{
if (!bHead){
bHead = head;
bTail = head;
}
else{
bTail->next = head;
bTail = head;
}
}
head = temp;
}
//合并链表
if (sTail)
{
sTail->next = eHead;
eTail = (eTail == NULL ? sTail : eTail);
}
if (eTail)
{
eTail->next = bHead;
}
return sHead != NULL ? sHead : (eHead != NULL ? eHead : bHead);
}
希望本文所述对大家C++程序设计有所帮助。
相关推荐
-
C++实现顺序表的方法
废话不多说了,直接给大家上关键代码了. #pragma once #include <assert.h> template<class T> class SeqList { public: SeqList() :_a(NULL) ,_size(1) ,_capacity(1) {} SeqList(T* a, size_t size) :_a(new T[size]) ,_size(size) ,_capacity(size) { for (size_t i = 0; i <
-
浅析C++中单链表的增、删、改、减
首先是是一个简单的例子,单链表的建立和输出.程序1.1 复制代码 代码如下: #include<iostream>#include<string>using namespace std;struct Student{ string name; string score; Student *next;//定义了指向Candidate类型变量的指针};int main(){ int n;// cout<<"请输入学生的总数:"; cin>>n
-
C++ 单链表的基本操作(详解)
链表一直是面试的高频题,今天先总结一下单链表的使用,下节再总结双向链表的.本文主要有单链表的创建.插入.删除节点等. 1.概念 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素. 链表中的数据是以结点来表示的,每个结点的构成:元素 + 指针,元素就是存储数据的存储单元,指针就是连接每个结点的地址数据.如下图: 2.链表的基本操作 SingleList.cpp: #include "stdafx.h" #include "SingleList.h&
-
C++ 实现静态单链表的实例
C++ 实现静态单链表的实例 利用数组实现的静态单链表,与严蔚敏书实现略有不同,不另设回收空间.有任何BUG或错误,希望各位朋友多多反馈~~感激不尽 /* Author : Moyiii * Mail: lc09@vip.qq.com * 静态链表实现,仅作学习之用,当然如果 * 你想拿去用,随你好啦. */ #include <iostream> using namespace std; #define MAX_LIST_SIZE 100 class Node { public: int d
-
C++实现顺序表的常用操作(插入删出查找输出)
实现顺序表的插入,删除,查找,输出操作在C语言中经常用到.下面小编给大家整理实现代码,一起看下吧 代码如下所示: #include<iostream> using namespace std; #define MAXSIZE 15 typedef int DataType; typedef struct { DataType data[MAXSIZE]; //通常用一位数组来描述顺序表的数据存储 int SeqLength; /*线性表长度*/ } SeqList; SeqList *Init
-
如何在C++中建立一个顺序表
准备数据 复制代码 代码如下: #define MAXLEN 100 //定义顺序表的最大长度struct DATA{ char key[10]; //结点的关键字 char name[20]; int age;};struct SLType //定义顺序表结构 { DATA ListData[MAXLEN+1];//保存顺序表的结构数组 int ListLen; //顺序表已存结点的数量 }; 定义了顺序表的最大长度MAXLEN.顺序表数据元素的类型DATA以及顺序表的数据结构SLTyp
-
C++中单链表的建立与基本操作
准备数据 准备在链表操作中需要用到的变量及数据结构 示例代码如下: 复制代码 代码如下: struct Data //数据结点类型 { string key; //关键字 string name; int age;};struct CLType //定义链表结构 { Data nodeData; Data *nextNode;}; 定义了链表数据元素的类型Data以及链表的数据结构CLType.结点的具体数据保存在一个结构Data中,而指针nextNode用来指向下一个结点. 我们可以
-
利用C++简单实现顺序表和单链表的示例代码
本文主要给大家介绍了关于C++实现顺序表和单链表的相关内容,分享出来供大家参考学习,话不多说,来一起看看详细的介绍: 一.顺序表示例代码: #include <assert.h> #include <iostream> using namespace std; typedef int Datatype; class SeqList { public: SeqList() :_array(NULL) ,_size(0) ,_capacity(0) { } SeqList(const
-
C++实现单链表删除倒数第k个节点的方法
本文实例讲述了C++实现单链表删除倒数第k个节点的方法.分享给大家供大家参考,具体如下: 题目: 删除单链表中倒数第k个节点 解题思路及算法代码: 标尺法,定义两个指针指向链表头结点,先让一个走k步,然后两个指针同时开始走,当先走的指针走到末尾时,后走的指针指向的结点就是需要删除的结点. 单链表结构定义: typedef struct Node { int data; struct Node* next; }node, *pLinkedList; 删除倒数第K结点操作代码: //head表示头结
-
C++实现单链表按k值重新排序的方法
本文实例讲述了C++实现单链表按k值重新排序的方法.分享给大家供大家参考,具体如下: 题目要求: 给定一链表头节点,节点值类型是整型. 现给一整数k,根据k将链表排序为小于k,等于k,大于k的一个链表. 对某部分内的节点顺序不做要求. 算法思路分析及代码(C) 思路:将链表分为小于k.等于k.大于k的三个链表,然后再合并. 链表结点定义: typedef struct Node { int data; struct Node* next; }node, *pNode; 算法代码: pNode s
-
单链表实现反转的3种方法示例代码
前言 单链表的操作是面试中经常会遇到的问题,今天总结一下反转的几种方案: 1 ,两两对换 2, 放入数组,倒置数组 3, 递归实现 代码如下: #include<stdio.h> #include<malloc.h> typedef struct Node { int data; struct Node *pnext; } Node,*pnode; pnode CreateNode() { pnode phead=(pnode)malloc(sizeof(Node)); if(ph
-
java实现单链表中是否有环的方法详解
这是一道微软经典笔试题,就是两个指针h1,h2都从头开始遍历单链表,h1每次向前走1步,h2每次向前走2步,如果h2碰到了NULL,说明环不存在:如果h2碰到本应在身后的h1说明环存在(也就是发生了套圈). 如果环不存在,一定是h2先碰到NULL: 如果环存在,h2与h1一定会相遇,而且相遇的点在环内:h2比h1遍历的速度快,一定不会在开始的那段非环的链表部分相遇,所以当h1,h2都进入环后,h2每次移动都会使h2与h1之间在前进方向上的差距缩小1,最后,会使得h1和h2差距减少为0,也即相遇
-
C语言单链表实现方法详解
本文实例讲述了C语言单链表实现方法.分享给大家供大家参考,具体如下: slist.h #ifndef __SLIST_H__ #define __SLIST_H__ #include<cstdio> #include<malloc.h> #include<assert.h> typedef int ElemType; typedef struct Node { //定义单链表中的结点信息 ElemType data; //结点的数据域 struct Node *next
-
详解go语言单链表及其常用方法的实现
目的 在刷算法题中经常遇到关于链表的操作,在使用go语言去操作链表时不熟悉其实现原理,目的是为了重温链表这一基础且关键的数据结构. 1.链表的特点和初始化 1.1.链表的特点 用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的) 1.2.结点 结点(node) 数据域 => 存储元素信息 指针域 => 存储结点的直接后继,也称作指针或链 首元结点 是指链表中存储的第一个数据元素的结点 头结点 是在首元结点之前附设的一个结点,其指针域指向首元结点(非必须) 头指
-
C++数据结构之单链表的实现
目录 一.单链表的定义 二.单链表的基本操作的实现 1.初始化 2.取值 3.查找 4.插入 5.删除 三.完整代码 四.测试一下代码 一.单链表的定义 线性表的链式存储又称为单链表,它是指通过一组任意的存储单元来存储线性表中的数据元素.为了建立数据元素之间的线性关系,对每个链表结点,除存放元素自身的信息外,还需要存放一个指向其后继的指针. 单链表中结点类型的描述如下: typedef struct LNode{ // 定义单链表节点类型 ElemType data; // 数据域 struct
-
C++详解如何实现单链表
目录 单链表 单链表的基本操作 1.初始化 2.取值 3.查找 4.插入 5.删除 示例代码 开发环境 运行结果 单链表 链表内存空间不一定连续,其扩展性较好.多余的不多说了.该文主要记录单链表的实现,该单链表含有一个非空的头节点.链表的操作实际上是对其指针域与数据域的操作. 线性表的链式存储又称为单链表,它是指通过一组任意的存储单元来存储线性表中的数据元素.为了建立数据元素之间的线性关系,对每个链表结点,除存放元素自身的信息外,还需要存放一个指向其后继的指针. 单链表中结点类型的描述如下: t
-
C/C++实现线性单链表的示例代码
目录 线性单链表简介 C语言实现代码 C++语言实现代码 线性单链表简介 使用链存储结构的线性存储结构为线性单链表,线性存储结构是元素逻辑结构一对一,链存储结构是元素物理结构不连续,线性单链表操作没有限制,线性单链表优点是可以直接插入和删除元素,线性单链表缺点是不可以使用下标获取和修改元素. C语言实现代码 #include<stdio.h>//包含标准输入输出文件 #include<stdlib.h>//包含标准库文件 typedef struct element//元素 { i
-
python实现单链表中删除倒数第K个节点的方法
本文实例为大家分享了python实现单链表中删除倒数第K个节点的具体代码,供大家参考,具体内容如下 题目: 给定一个链表,删除其中倒数第k个节点. 代码: class LinkedListAlgorithms(object): def __init__(self): pass def rm_last_kth_node(self, k, linked_list): # 删除倒数第 K 个节点,针对单链表的 if linked_list.is_empty(): print 'The given li