实现在单向链表中,返回某个节点的前驱.
原理说明
单向链表的特点是链表只有一个方向,即只有从前驱结点指向后继结点的指针,而没有后继节点指向前驱结点的指针,结构图大致如下:
linklist1.png
从图可以看出,如果我们要访问第三个结点,我们只能从头指针依次便利每个后继结点,直至访问到第三个结点,因此在单向链表中,我们查找某个元素的时间复杂度
linklist2.png
-
在上图中,cur=1,不是我们要找的结点3,因此pre和cur向前移动,即pre=cur, cur=next;
linklist3.png
-
此时,cur=2,不符合我们的条件,我们继续执行上面的操作;
linklist4.png
现在cur=3,满足我们的条件,此时pre就是他的前驱,返回该节点即可.
下面是实现代码,仅供参考
c语言
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
// 数据类型
typedef int ElementType;
// 链表数据结构
typedef struct ListNode
{
ElementType data;
struct ListNode* next;
}Node, *Linklist;
// 创建链表
Linklist createList()
{
int len;
printf("请输入链表长度:");
scanf("%d", &len);
Linklist head = (Linklist)malloc(sizeof(Node));
Linklist tail = head;
tail->next = NULL;
for (int i=0; i<len; ++i)
{
int val;
printf("第%d个节点内容:", (i+1));
scanf("%d", &val);
Linklist node = (Linklist)malloc(sizeof(Node));
node->data = val;
node->next = tail->next;
tail->next = node;
tail = node;
}
return head;
}
// 查找给定节点的前驱
Node* preNodeOf(Linklist list, Node* node)
{
Node* cur = list->next;
Node* pre = list;
while (cur != NULL && cur->data != node->data)
{
pre = cur;
cur = cur->next;
}
if (pre != list)
return pre;
else
return NULL;
}
// 根据索引查找指定节点,index 从1开始
Node* getNode(Linklist list, int index)
{
Node* node = list;
for (int i=0; i<index; ++i)
{
node = node->next;
if (node == NULL)
return NULL;
}
return node;
}
// 显示链表内容
void showLinklist(Linklist list)
{
Node* node = list->next;
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
int length(Linklist list)
{
int len = 0;
Node* node = list->next;
while (node != NULL)
{
++len;
node = node->next;
}
return len;
}
int main()
{
Linklist list = createList();
printf("链表内容:");
showLinklist(list);
int len = length(list);
int index;
printf("\n输入需要查找前驱的节点的索引(0< n <=%d):", len);
scanf("%d", &index);
Node* node = getNode(list, index);
printf("第%d个节点的内容:%d\n", index, node->data);
node = preNodeOf(list, node);
if (node != NULL)
printf("%d\n", node->data);
else
printf("该节点为第一个节点,无前驱节点!");
return 0;
}
C++代码:这里使用了模板类
#include <iostream>
using namespace std;
// 节点类, 使用了模板类,方便数据类型
template<class T>
class Node
{
public:
T data;
Node<T>* next;
public:
Node(){}
Node(T v, Node<T>* node)
{
this->data = v;
this->next = node;
}
};
template<class T>
class LinkList
{
private:
Node<T>* head;
Node<T>* tail;
int count;
public:
LinkList();
~LinkList();
int size();
Node<T>* getNode(int);
void print();
void append(T data);
Node<T>* preNodeOf(Node<T>*);
};
// 初始化链表
template<class T>
LinkList<T>::LinkList(): count(0)
{
head = new Node<T>;
head->next = NULL;
tail = head;
int length;
cout << "请输入链表初始长度:";
cin >> length;
for (int i = 0; i < length; ++i)
{
T data;
cout << "第" << (i+1) << "个节点的内容:";
cin >> data;
append(data);
}
}
template<class T>
LinkList<T>::~LinkList()
{
Node<T>* node = head->next;
Node<T>* tmp;
while (node != NULL)
{
tmp = node;
node = node->next;
delete tmp;
}
delete head;
head = NULL;
tail = NULL;
}
// 返回链表的长度
template<class T>
int LinkList<T>::size()
{
return count;
}
template <class T>
Node<T>* LinkList<T>::getNode(int index)
{
if (index > count || index <= 0)
{
cout<< "Index Error!"<<endl;
}
Node<T>* node = head;
for(int i=0; i<index && node->next; ++i)
{
node = node->next;
}
return node;
}
template <class T>
void LinkList<T>::print()
{
Node<T>* node = head->next;
while (node)
{
cout << node->data << " ";
node = node->next;
}
cout<<endl;
}
template <class T>
void LinkList<T>::append(T data)
{
Node<T>* node = new Node<T>();
node->data = data;
node->next = NULL;
tail->next = node;
tail = node;
++count;
}
template <class T>
Node<T>* LinkList<T>::preNodeOf(Node<T>* node)
{
Node<T>* pre = head;
Node<T>* cur = head->next;
while (cur->data != node->data)
{
pre = cur;
cur = cur->next;
}
if (pre == head)
{
return NULL;
}
else
{
return pre;
}
}
int main()
{
LinkList<int> list = LinkList<int>();
cout << "链表内容:";
list.print();
int size = list.size();
int index;
cout << "输入需要查找前驱的节点的索引(1 <= n <=" << size << "):";
cin >> index;
Node<int>* node = list.getNode(index);
cout << "第" << index << "个节点的内容:" << node->data << endl;
Node<int>* pre = list.preNodeOf(node);
if (pre)
cout << "第" << index << "个节点的前驱:" << pre->data << endl;
else
cout << "该节点为第一个节点,无前驱" << endl;
return 0;
}
下面的代码仅供学习使用,课程要求为C/C++变成语言.
Python3
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class LinkList:
def __init__(self):
self._head = Node(0)
self._tail = self._head
self._count = 0
def append(self, data):
node = Node(data, None)
self._tail.next = node
self._tail = node
self._count += 1
def size(self):
return self._count
def show(self):
node = self._head.next
while (node):
print(node.data, end=" ")
node = node.next
def add_n_elems(self, n):
for i in range(n):
data = int(input("请输入第%d个节点的内容:" % (i+1)))
self.append(data)
def pre_node_of(self, node):
pre = self._head
cur = pre.next
while(cur.data != node.data):
pre = cur
cur = cur.next
if (pre == self._head):
return None
else:
return pre
def get_node(self, index):
if not (1 <= index <= self.size() ):
raise Exception("Index Error!")
node = self._head
for _ in range(index):
node = node.next
return node
if __name__ == "__main__":
linklist = LinkList()
length = int(input("请输入链表长度:"))
linklist.add_n_elems(length)
print("链表内容:", end="")
linklist.show()
index = int(input("\n输入需要查找前驱的节点的索引(0< n <=%d):" % linklist.size()))
node = linklist.get_node(index)
pre_node = linklist.pre_node_of(node)
print("第%d个节点的内容:%d" % (index, node.data))
if pre_node is not None:
print("第%d个节点的前驱的内容内容:%d" % (index, pre_node.data))
else:
print("该节点无前驱节点")
Java
import java.util.Scanner;
class Node<T> {
public T data;
public Node<T> next;
public Node(){}
public Node(T data) {
this.data = data;
this.next = null;
}
}
class Linklist<T> {
private Node<T> head;
private Node<T> tail;
private int count;
public Linklist() {
head = new Node<T>();
tail = head;
count = 0;
}
public void append(T data)
{
Node<T> node = new Node(data);
tail.next = node;
tail = node;
count++;
}
public int size() {
return count;
}
public Node<T> getNode(int index) throws Exception{
if (index < 1 || index > count)
throw new Exception("Index Error!");
Node<T> node = head;
for (int i=0; i<index; ++i) {
node = node.next;
}
return node;
}
public Node<T> preNodeOf(Node<T> node) {
Node<T> pre = head;
Node<T> cur = pre.next;
while (cur.data != node.data) {
pre = cur;
cur = cur.next;
}
if (pre == head)
return null;
else
return pre;
}
public void show() {
Node<T> node = head.next;
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
}
public class Demo {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
Linklist<Integer> list = new Linklist<Integer>();
int length;
System.out.print("请输入链表长度:");
length = scan.nextInt();
for (int i=0; i<length; ++i) {
System.out.print("请输入第" + (i+1) + "个节点的内容:");
int data = scan.nextInt();
list.append(data);
}
System.out.print("链表内容:");
list.show();
System.out.print("\n输入需要查找前驱的节点的索引(1<= n <=" + list.size() + ")");
int index = scan.nextInt();
Node<Integer> node;
try {
node = list.getNode(index);
} catch (Exception e) {
// e.printStack();
node = null;
}
Node<Integer> pre_node = list.preNodeOf(node);
System.out.println("第" + index + "个节点的内容:" + node.data);
if (pre_node != null)
System.out.println("第" + index + "个节点的前驱的内容内容:" + pre_node.data);
else
System.out.println("该节点无前驱节点");
}
}
网友评论