数据结构 单链表 算法
发布网友
发布时间：2022-05-03 01:37
共4个回答
懂视网
时间：2022-04-24 07:11
前面楼主分别讨论了数据结构栈与队列的实现，当时所用的数据结构都是用的数组来进行实现，但是数组有的时候并不是最佳的数据结构，比如在数组中新增删除元素的时候需要将其他元素进行移动，而在javascript中使用spit()方法不需要访问其他元素。如果你在使用数组的时候发现很慢，就可以考虑使用链表。
链表的概念
链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。链表有一个“头指针”变量，以head表示，它存放一个地址，指向一个元素。每个结点都使用一个对象的引用指标它的后继，指向另一个结点的引用叫做链。
数组元素依靠下标（位置）来进行引用，而链表元素则是靠相互之间的关系来进行引用。因此链表的插入效率很高，下图演示了链表结点d的插入过程：
删除过程：
基于对象的链表
我们定义2个类，Node类与LinkedList类，Node为结点数据，LinkedList保存操作链表的方法。
首先看Node类：
element用来保存结点上的数据，next用来保存指向一下结点的的链接。
LinkedList类:
find()方法，从头结点开始，沿着链表结点一直查找，直到找到与item内容相等的element则返回该结点，没找到则返回空。
Insert方法。通过前面元素插入的演示可以看出，实现插入简单四步：
1、创建结点
2、找到目标结点
3、修改目标结点的next指向链接
4、将目标结点的next值赋值给要插入的结点的next
Remove()方法。删除某一节点需要先找到被删除结点的前结点，为此我们定义方法frontNode()：
简答三步：
1、创建结点
2、找到目标结点的前结点
3、修改前结点的next指向被删除结点的n后一个结点
Show()方法：
测试程序：
输出：
双向链表
从链表的头节点遍历到尾节点很简单，但有的时候，我们需要从后向前遍。此时我们可以通过给 Node 对象增加一个属性，该属性存储指向前驱节点的链接。楼主用下图来双向链表的工作原理。
首先我们先给Node类增加front属性：
当然，对应的insert()方法和remove()方法我们也需要做相应的修改：
反序显示链表：
需要给双向链表增加一个方法，用来查找最后的节点。 findLast() 方法找出了链表中的最后一个节点，可以免除从前往后遍历链。
实现反序输出：
测试程序：
输出：
循环链表
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即：
head.next = head
这种行为会传导至链表中的每个节点，使得每个节点的 next 属性都指向链表的头节点。楼主用下图来表示循环链表：
修改构造方法：
这时需要注意链表的输出方法show()与find()方法，原来的方式在循环链表里会陷入死循环，while循环的循环条件需要修改为当循环到头节点时退出循环。
测试程序：
测试结果：
热心网友
时间：2022-04-24 04:19
// 对于节点的定义
struct Node
{
int data;
struct Node *next;
};
// 合并两个递减有序的链表
struct Node *merge(struct Node *p1, struct Node *p2)
{
struct Node *head = NULL, *p = NULL, *pt;
// 当两链表均不空时的合并逻辑
while(p1 && p2)
{
// 将两链表当前节点中值较大的一个记录下来，
// 并后移指向该链表当前节点的指针
if(p1->data > p2->data)
{
pt = p1;
p1 = p1->next;
}
else
{
pt = p2;
p2 = p2->next;
}
if(p == NULL)
{
// 若当前新链表为空，将p和head指向找到的节点
head = p = pt;
}
else
{
// 将新节点链入当前链表尾部
p->next = pt;
p = pt;
}
}
// 找到隶完成合并的那个链表，将其链接到新链表的尾部
pt = p1 == NULL ? p2 : p1;
if(pt)
{
if(p == NULL)
{
// 如果新链表仍为空，直接指向非空的链表
head = p = pt;
}
else
{
// 将未完成合并的链表链接到新链表的尾部
p->next = pt;
}
}
return head;
}
// 链表倒置
struct Node *reverse(struct Node *head)
{
struct Node *newHead = NULL, *p;
if(!head)
{
return newHead;
}
// 先将新的头指针指向原链表的第一个节点
newHead = head;
head = head->next;
newHead->next = NULL;
// 将原链表中剩下的节点依次加到新链表的头部，以实现倒序
while(head)
{
p = head->next;
head->next = newHead;
newHead = head;
head = p;
}
return newHead;
}
int main()
{
struct Node *h1, *h2, *head;
// 生成原始的两个链表的逻辑请自行编写
// 首先，合并两个链表
head = merge(h1, h2);
// 然后，将合并后的链表倒置
head = reverse(head);
// 输出处理后的链表中的内容
while(head)
{
printf("%d ", head->data);
head = head->next;
}
getchar();
return 0;
}
以上程序是按照 zhangchaoyiay 所说的算法思路编写，其实在合并的过程中，可以直接完成倒序操作，这个楼主自己琢磨一下好了，呵呵
热心网友
时间：2022-04-24 05:37
或者先归并排序 再将一个链表反转追问有没有具体的程序例子
热心网友
时间：2022-04-24 07:11
