数据结构第二次作业

实现在单向链表中,返回某个节点的前驱.

原理说明

单向链表的特点是链表只有一个方向,即只有从前驱结点指向后继结点的指针,而没有后继节点指向前驱结点的指针,结构图大致如下:

linklist1.png

从图可以看出,如果我们要访问第三个结点,我们只能从头指针依次便利每个后继结点,直至访问到第三个结点,因此在单向链表中,我们查找某个元素的时间复杂度
O(n)
.

基于链表的单向特点,因此我们必须从头开始遍历才能找到某个节点的前驱.以上图为例进行讲解,假如我们要寻找第三个结点的前驱,我们如何实现呢?

  1. 首先我们需要申明两个临时变量pre 和 cur,分别指向Head 头结点和Head->next(为null或为第一个结点),这样pre和cur就构成一个相关的对,pre表示cur的前驱,当cur到达第三个结点时,此时pre就是我们要找的前驱.


    linklist2.png
  2. 再循环中,我们依次把pre和cur向前同时推进,直至cur到达事先定义的结点.

  • 在上图中,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("该节点无前驱节点");


    }
}
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 数据结构基础概念篇
    一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这...
    Winterfell_Z阅读 11,398评论 0赞 13
  • 2018之线性表的基本概念
    转自：http://blog.csdn.net/oreo_go/article/details/52116214 ...
    YYT1992阅读 4,874评论 0赞 4
  • 数据结构——链表
    目录 1、属性 2、链表和数组的区别 2.1、数组概述 2.2、数组和链表优缺点 2.3、链表和数组的比较 3、单...
    我哈啊哈啊哈阅读 7,841评论 1赞 41
  • 杂谈
    （一）睡眠 如果睡眠不足，就会精神恍惚，晕头转向；如果耐心不足，就会心浮气躁，多做后悔之事。 年关将至，午休时间、...
    邢姑娘阅读 1,859评论 0赞 1
  • 慢下来
    桐婳问：“爸爸是不是做了什么坏事被警察叔叔抓起来了啊？”“为什么这么说”我不解。桐婳一本正经地说，“因为他...
    桐婳妈妈阅读 2,885评论 1赞 0