重排链表（重排链表的实验目的）

本篇文章给大家谈谈重排链表，以及重排链表的实验目的对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、ArrayList 和LinkedList各自的特点是什么？
• 2、算法思路整理-链表
• 3、已知链表h中的结点按绝对值排列，写出一高效的过程Sort(h)将其排序。
• 4、一个链表问题，请教C高手
• 5、常用的数据排序算法有哪些,各有什么特点?举例结合一种排序算法并应用数组进行数据排序。

ArrayList 和LinkedList各自的特点是什么？

1、ArrayList：动态数组。

用MSDN中的说法，就是Array的复杂版本，它提供了动态的让档增加和减少元素，实现了ICollection和IList接坦孙乱口，灵活的设置数组的大小等好处。

2、LinkedList：双向列表。

列表中的每个节点都包含了对前一个和后一个元素的引用。

List 接口的大小可变数组的实现，位于API文档的java.util.ArrayList凯缓E。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间 运行，也就是说，添加 n 个元素需要 O(n) 时间。其他所有操作都以线性时间运行（大体上讲）。

与用于 LinkedList 实现的常数因子相比，此实现的常数因子较低。

每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。并未指定增长策略的细节，因为这不只是添加元素会带来分摊固定时间开销那样简单。

扩展资料

常用方法：

1、boolean add(E e)：将指定的元素添加到此列表的尾部。

2、void add(int index, E element)：将指定的元素插入此列表中的指定位置。

3、boolean addAll(Collection? extends E c)：按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。

4、boolean addAll(int index, Collection? extends E c)：从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。

5、void clear()：移除此列表中的所有元素。

6、Object clone()：返回此 ArrayList 实例的浅表副本。

参考资料来源：百度百科-arraylist

[img]

算法思路整理-链表

1. 1. 链表

     a. 常用工具函数

         i. Collection.sort(list, new comparator())

     b. 单链表的选择排序

         i. 方法1，递归

         大毕   1. 1. 找到最小的，为头，头的next等于对剩余链表排序，返回头

            2. 2. 时间复杂度 n^2

         ii. 方法2，借助数组

            1. 1. ListNode放到数组里

            2. 2. Array.sort()

            3. 3. 将ListNode串联取来

            4. 4. 时间复杂度nlog(n),空间复杂度n

     c. 反转链表

         i. 方法1递归，

            1. 1. 当前链表的尾就头，尾之前的节点的next置空

            2. 2. 返回tail.next=递归剩余链表

            3. 3. 时间复杂度n^2

         ii. 方法2 

            1. 1. 找到当前尾为头滚颂芹，倒数第二个节点next置空

            2. 2. 从樱高头开始遍历，往当前的新头上追加

            3. 3. 时间复杂度为n

     d. 链表指定区间反转

         i. 找到要翻转的区域之前的节点，之后的节点，以及反转区域的头尾

         ii. 此时尾为新的头，从头开始往尾遍历，不断往新的头后面追加

         iii. 时间复杂度n

     e. 判断链表中是否有环

         i. 步长1，步长2，分别遍历链表

         ii. 如果没结束，或者重叠，则有环

         iii. 复杂度n

     f. 链表中环的入口

         i. 先判断是否有环，如果没有环，返回null

         ii. 停在重叠的点，然后从头和重叠点一起走，返回再次相碰的点

         iii. 复杂度n

     g. 数组链表，区间合并

         i. 根据数组头元素的大小排序

         ii. 遍历列表，如果相邻的两个存在重叠，合并，注意尾部是两个尾部的最大值

         iii. 复杂度nlog(n)

     h. 合并K个已经排序的链表

         i. 如果链表个数奇数，加入空链表

         ii. 合并成一个新的list

         iii. 继续合并，如果链表中个数为1，返回

     i. 数组中的逆序数

     j. 删除有序链表中重复的元素并保留一个

         i. 从头遍历，如果下一个等于他自己，删除下一个

         ii. 如果下一个不等于他自己，往后走一个，直到null

         iii. 时间复杂度n

     k. 删除有序链表中重复出现的元素

         i. 从头遍历，找到第一个不重复的元素

         ii. 从第一个不重复的元素开始，如果当前下一个等于下下一个，继续往后遍历，直到不等于，全部删除

         iii. 时间复杂度n

     l. 判断一个链表是否是回文结构

         i. 求链表长度

         ii. 栈n/2, 考虑奇数偶数情形

         iii. 时间复杂度n, 空间复杂度n/2

     m. 重排链表

         i.

         ii. 递归

         iii. 找到倒数第二个节点

         iv. 倒数第一个节点跟到头的后面，倒数第二个节点next置空

         v. 当前位是倒数第一个节点，倒数第一个节点.next=递归剩余list

         vi. 时间复杂度n^2

     n. 链表的奇数偶数位置重新排列，原来奇数位置的放到前面

         i. 从左到右遍历，找第一个下一个是偶数的节点n1,第一个偶数节点就是n2

         ii. 从n2开始循环往后遍历，找下一个是奇数的节点n3

         iii. N1.next=n3.next; n3.next=n3.next.next; n1=n1.next; 

         iv. 继续从n3开始遍历直到null，n1.next=n2

         v. 时间复杂度n

     o. 划分链表，给一个数，大于这个数的节点都在链表前部

         i. 找到第一个下一个大于等于k的节点n1为前半部分的队尾，下一个节点n2为后半部分的队首

         ii. 遍历后半部分，如果value小于K, 跟到前半部分的队尾，直到null

         iii. 前半部分的队尾.next=n2

         iv. 时间复杂度n

     p. 环形链表的约瑟夫问题

         i. 构建环形链表，尾部指向头

         ii. 循环删除编号为k的节点，直到只剩一个节点，返回节点val

         iii. 时间复杂度为kn, 空间复杂度为n

     q. 合并有序链表

         i. 如果一个为空，返回另一个

         ii. 递归，比较两个链表的头，小的是头，然后头.next=合并剩余列表,返回头

         iii. 时间复杂度n+m;

     r. 删除链表的倒数第n个节点

         i. 双指针，考虑临界点的情形，比如头尾

         ii. 位置落在要删除节点前的一个位置上

         iii. 复杂度n

     s. 链表中倒数第k个节点

         i. 双指针，一个先走k步，另一个开始一起走

         ii. 第一个走到尾部，停住，第二个指针指向的就是要求的

         iii. 时间复杂度n

     t. 链表中的节点每K个一组反转，剩余不满K的保持原样

         i. 递归，截取前K个，反转前K个，tail.next=反转剩余的

         ii. 前k个也通过递归方式进行反转

         iii. 时间复杂度n^2

     u. 两个链表生成相加链表

         i. 压栈，构建进位C

         ii. 当有栈空了之后，非空栈和进位C一起计算

         iii. 最后检查一下C是否0

         iv. 时间复杂度max(N,M)，空间复杂度N+M

     v. 两个链表的第一个公共节点

         i. 先分别遍历到尾

         ii. 计算长度，长的链表先开始遍历l1-l2步，然后大家一起开始

         iii. 返回第一个重叠的节点

         iv. 时间复杂度max(N,M)

已知链表h中的结点按绝对值排列，写出一高效的过程Sort(h)将其排序。

排序问题的输入是一个线性表，该线性表的元素属于一个偏序集；要求对该线性表的元素做某种重排，使得线性表中除表尾外的每个元素都小于等于（或大于等于）它的后继。

设R为非空纤渗集合A上的二元关系，如果R满足自反性(对于每一个x∈A，(x,x)∈R )，反对称性毁仔脊((x,y)∈R∧(y,x)∈R→x=y )和传递性((x,y)∈R∧(y,x)∈R→(x,z)∈R)，则称R为A上的偏序关系，记作≤。如果(x,y)∈R，则记作x≤y，读作“x小于等于y”。存在偏序关系的集合A称为偏序集。

注意，这里的≤不是指数的大小，而是指在偏序关系中的顺序性。x≤y的含义是：按照这个序，x排在y前面。根据不同的偏序定义，≤有不同的解释。例如整除关系是偏序关系≤，3≤6的含义是3整除6。大于或等于关系也是偏序关系，针对这个关系5≤4是指戚纳在大于或等于关系中5排在4的前面，也就是说5比4大。

在实际应用中，经常遇到的偏序关系是定义在一个记录类型的数据集合上的。在该记录类型中有一个主键域key，key域的类型是某一个偏序集，记录的其他域称为卫星数据。比较线性表中的两个元素Li和Lj的大小，实际上是比较Li.key和Lj.key的大小（这种比较当然也是偏序集中的比较）。举例而言，某公司的数据库里记 录了员工的数据，每一项纪录包括姓名，编号，年龄，工资等几个域，如果以编号为key域对员工记录排序，则是将员工记录按照编号排序；如果以工资为key域对员工记录排序，则是将员工记录按照工资高低排序；如果以姓名为key域对员工记录排序，则是以员工姓名的汉语拼音按照字典顺序排序。

关于偏序集的具体概念和应用，请参见离散数学的相关资料。

如果一个排序算法利用输入的线性表在原地重排其中元素，而没有额外的内存开销，这种排序算法叫做原地置换排序算法(in place sort)；如果排序后并不改变表中相同的元素原来的相对位置，那么这种排序算法叫做稳定排序算法(stable sort)。

排序问题一般分为内排序( internal sorting )和外排序( external sorting )两类：

内排序：待排序的表中记录个数较少，整个排序过程中所有的记录都可以保留在内存中；

外排序：待排序的记录个数足够多，以至于他们必须存储在磁带、磁盘上组成外部文件，排序过程中需要多次访问外存。

一个链表问题，请教C高手

#include "stdio.h"

#include malloc.h

struct Student

{

char name[20];

int BirthOfYear;

int BirthOfMonth;

}student[5] = {{"钱达",1983,3},{"钱亮",1984,5},{"孙立为",1980,1},{"王胜利",1983,10},{"周学立",1981,6}};

struct List

{

struct Student stu;

struct List *next;

};

struct List* Creat(struct List* head,struct List* p0)//建立链表

{

struct List *p1,*p2;

p1 = head;

if (head == NULL)

{

head = p0;

p0-next = NULL;

}

else

{

/*比较后进行插入*/

while ( (p1-next != NULL) (p0-stu.BirthOfYear p1-stu.BirthOfYear || ( (p0-stu.BirthOfYear == p1-stu.BirthOfYear) (p0-stu.BirthOfMonth p1-stu.BirthOfMonth))) )

{

p2 = p1;

p1 = p1-next;

}

if (p0-stu.BirthOfYear = p1-stu.BirthOfYear || ( (p0-stu.BirthOfYear == p1-stu.BirthOfYear) (p0-stu.BirthOfMonth = p1-stu.BirthOfMonth)) )

{

if (head == p1)

{

head = p0;

p0-next = p1;

}

else

{

p2-next = p0;

p0-next = p1;

}

}

else

{

p1-next = p0;

p0-仔差行next = NULL;

}

}

return head;

}

void Print(struct List *head)//输出庆蠢并释放空间

{

struct List* p;

struct List* q;

p = head;

while (p != NULL)

{

printf("%s %d %d\n",p-stu.name,p-stu.BirthOfYear,p-stu.BirthOfMonth);

q = p-next;

free(p);

p = q;

}

}

main()

{

struct List *temp;

struct List *p = NULL;

int i;

for (i = 0; i 5; i++)

{

temp= (struct List*)malloc(sizeof(struct List));

temp-念哗stu = student[i];

p = Creat(p,temp);

}

Print(p);

}

常用的数据排序算法有哪些,各有什么特点?举例结合一种排序算法并应用数组进行数据排序。

排序简介

排序是数据处理中经常使用的一种重要运算,在计算机及其应用系统中,花费在排序上的时间在系统运行时间中占有很大比重;并且排序本身对推动算法分析的发展也起很大作用。目前已有上百种排序方法，但尚未有一个最理想的尽如人意的方法，本章介绍常用的如下排序方法，并对它们进行分析和比较。

1、插入排序（直接插入排序、折半插入排序、希尔排序）；

2、交换排序（起泡排序、快速排序）；

3、选择排序（直接选择排序、堆排序）；

4、归并排序；

5、基数排序；

学习重点

1、掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用；

2、掌握插入排序(直接插入排序、折半插入排序、希尔排序)、交换排序（起泡排序、快速排序）、选择排序（直接选择排序、堆排序）、二路归并排序的方法及其性能分析方法；

3、了解基数排序方法及其性能分析方法。

排序（sort）或分类

　所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：

输入：n个记录R1，R2，…，此旦Rn，其相应的关键字分别为K1，K2，…，Kn。

输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

1．被排序对象--文件

被排序的对象--文件由一组记录组成。

记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字(Key)。

注意：

　 在不易产生混淆时，将关键字项简称为关键字。

2．排序运算的依据--关键字

　用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。

　 关键字的选取应根据问题的要求而定。

【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用"准考证号"作为关键字。若要按照考生的总分数排名次，则需用"总分数"作为关键字。

排序的稳定性

　 当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。

　在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。

注意：

　 排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

排序方法的分类

1．按是否涉及数据的内、外存交换分

　在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内排序)；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。

注意：

　 ① 内排序适用于记录个数不很多的小文件

　② 外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。

2．按策略划分内部排序方法

　可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。

排序算法分析

1．排序算法的基本操作

　大多数排序算法都有两个基本的操作：

(1) 比较两个关键字的大小；

(2) 改变指向记录的指针或移动记录本身。

注意：

　 第(2)种基本操作的实现依赖于待排序记录的存储方式。

2．待排文件的常用存储方式

（1） 以顺序表(或直接用向量)作为存储结构

排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置）

（2） 以链表作为存储结构

排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表(或链式)排序；

（3） 用顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指向记录位置的指空弊针组成的索引表)

排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不斗扒族移动记录本身）。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。

3．排序算法性能评价

（1） 评价排序算法好坏的标准

评价排序算法好坏的标准主要有两条：

　① 执行时间和所需的辅助空间

　② 算法本身的复杂程度

（2） 排序算法的空间复杂度

若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。

非就地排序一般要求的辅助空间为O(n)。

（3） 排序算法的时间开销

大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。

文件的顺序存储结构表示

#define n l00 //假设的文件长度，即待排序的记录数目

typedef int KeyType； //假设的关键字类型

typedef struct{ //记录类型

KeyType key； //关键字项

InfoType otherinfo；//其它数据项，类型InfoType依赖于具体应用而定义

}RecType；

typedef RecType SeqList[n+1]；//SeqList为顺序表类型，表中第0个单元一般用作哨兵

注意：

　若关键字类型没有比较算符，则可事先定义宏或函数来表示比较运算。

【例】关键字为字符串时，可定义宏"#define LT(a，b)(Stromp((a)，(b))0)"。那么算法中"ab"可用"LT(a，b)"取代。若使用C++，则定义重载的算符""更为方便。

按平均时间将排序分为四类：

（1）平方阶(O(n2))排序

　一般称为简单排序，例如直接插入、直接选择和冒泡排序；

（2）线性对数阶(O(nlgn))排序

　如快速、堆和归并排序；

（3）O(n1+￡)阶排序

　￡是介于0和1之间的常数，即0￡1，如希尔排序；

（4）线性阶(O(n))排序

　如桶、箱和基数排序。

各种排序方法比较

简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。

影响排序效果的因素

　因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：

①待排序的记录数目n；

②记录的大小(规模)；

③关键字的结构及其初始状态；

④对稳定性的要求；

⑤语言工具的条件；

⑥存储结构；

⑦时间和辅助空间复杂度等。

不同条件下，排序方法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。

　当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；

(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。

　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

　若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

4)在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。

　当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlgn)的时间。

　箱排序和基数排序只需一步就会引起m种可能的转移，即把一个记录装入m个箱子之一，因此在一般情况下，箱排序和基数排序可能在O(n)时间内完成对n个记录的排序。但是，箱排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合(例如实数型关键字)时，无法使用箱排序和基数排序，这时只有借助于"比较"的方法来排序。

　若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。虽然桶排序对关键字的结构无要求，但它也只有在关键字是随机分布时才能使平均时间达到线性阶，否则为平方阶。同时要注意，箱、桶、基数这三种分配排序均假定了关键字若为数字时，则其值均是非负的，否则将其映射到箱(桶)号时，又要增加相应的时间。

(5)有的语言(如Fortran，Cobol或Basic等)没有提供指针及递归，导致实现归并、快速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其它排序。

(6)本章给出的排序算法，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量t作为辅助表，排序前令t[i]=i(0≤in)，若排序算法中要求交换R[i]和R[j]，则只需交换t[i]和t[j]即可；排序结束后，向量t就指示了记录之间的顺序关系：

R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key

若要求最终结果是：

R[0].key≤R[1].key≤…≤R[n-1].key

则可以在排序结束后，再按辅助表所规定的次序重排各记录，完成这种重排的时间是O(n)。

关于重排链表和重排链表的实验目的的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。