數(shù)據(jù)結(jié)構(gòu)第二次作業(yè)

實(shí)現(xiàn)在單向鏈表中,返回某個(gè)節(jié)點(diǎn)的前驅(qū).

原理說(shuō)明

單向鏈表的特點(diǎn)是鏈表只有一個(gè)方向,即只有從前驅(qū)結(jié)點(diǎn)指向后繼結(jié)點(diǎn)的指針,而沒(méi)有后繼節(jié)點(diǎn)指向前驅(qū)結(jié)點(diǎn)的指針,結(jié)構(gòu)圖大致如下:

linklist1.png

從圖可以看出,如果我們要訪問(wèn)第三個(gè)結(jié)點(diǎn),我們只能從頭指針依次便利每個(gè)后繼結(jié)點(diǎn),直至訪問(wèn)到第三個(gè)結(jié)點(diǎn),因此在單向鏈表中,我們查找某個(gè)元素的時(shí)間復(fù)雜度
O(n)
.

基于鏈表的單向特點(diǎn),因此我們必須從頭開(kāi)始遍歷才能找到某個(gè)節(jié)點(diǎn)的前驅(qū).以上圖為例進(jìn)行講解,假如我們要尋找第三個(gè)結(jié)點(diǎn)的前驅(qū),我們?nèi)绾螌?shí)現(xiàn)呢?

  1. 首先我們需要申明兩個(gè)臨時(shí)變量pre 和 cur,分別指向Head 頭結(jié)點(diǎn)和Head->next(為null或?yàn)榈谝粋€(gè)結(jié)點(diǎn)),這樣pre和cur就構(gòu)成一個(gè)相關(guān)的對(duì),pre表示cur的前驅(qū),當(dāng)cur到達(dá)第三個(gè)結(jié)點(diǎn)時(shí),此時(shí)pre就是我們要找的前驅(qū).


    linklist2.png
  2. 再循環(huán)中,我們依次把pre和cur向前同時(shí)推進(jìn),直至cur到達(dá)事先定義的結(jié)點(diǎn).

  • 在上圖中,cur=1,不是我們要找的結(jié)點(diǎn)3,因此pre和cur向前移動(dòng),即pre=cur, cur=next;


    linklist3.png

  • 此時(shí),cur=2,不符合我們的條件,我們繼續(xù)執(zhí)行上面的操作;


    linklist4.png

    現(xiàn)在cur=3,滿足我們的條件,此時(shí)pre就是他的前驅(qū),返回該節(jié)點(diǎn)即可.

下面是實(shí)現(xiàn)代碼,僅供參考

c語(yǔ)言

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

// 數(shù)據(jù)類型
typedef int ElementType;

// 鏈表數(shù)據(jù)結(jié)構(gòu)
typedef struct ListNode
{
    ElementType data;
    struct ListNode* next;
}Node, *Linklist;

// 創(chuàng)建鏈表
Linklist createList()
{
    int len;
    printf("請(qǐng)輸入鏈表長(zhǎng)度:");
    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個(gè)節(jié)點(diǎn)內(nèi)容:", (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;
}

// 查找給定節(jié)點(diǎn)的前驅(qū)
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;
}

// 根據(jù)索引查找指定節(jié)點(diǎn),index 從1開(kāi)始
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;
}
// 顯示鏈表內(nèi)容
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("鏈表內(nèi)容:");
    showLinklist(list);

    int len = length(list);
    int index;
    printf("\n輸入需要查找前驅(qū)的節(jié)點(diǎn)的索引(0< n <=%d):", len);
    scanf("%d", &index);
    Node* node = getNode(list, index);
    printf("第%d個(gè)節(jié)點(diǎn)的內(nèi)容:%d\n", index, node->data);


    node = preNodeOf(list, node);
    if (node != NULL)
        printf("%d\n", node->data);
    else
        printf("該節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn),無(wú)前驅(qū)節(jié)點(diǎn)!");
    return 0;
}

C++代碼:這里使用了模板類

#include <iostream>
using namespace std;


// 節(jié)點(diǎn)類, 使用了模板類,方便數(shù)據(jù)類型
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 << "請(qǐng)輸入鏈表初始長(zhǎng)度:";
    cin >> length;
    for (int i = 0; i < length; ++i)
    {
        T data;
        cout << "第" << (i+1) << "個(gè)節(jié)點(diǎn)的內(nèi)容:";
        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;
}

// 返回鏈表的長(zhǎng)度
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 << "鏈表內(nèi)容:";
    list.print();

    int size = list.size();
    int index;
    cout << "輸入需要查找前驅(qū)的節(jié)點(diǎn)的索引(1 <= n <=" << size << "):";
    cin >> index;
    Node<int>* node = list.getNode(index);
    cout << "第" << index << "個(gè)節(jié)點(diǎn)的內(nèi)容:" << node->data << endl;

    Node<int>* pre = list.preNodeOf(node);
    if (pre)
        cout << "第" << index << "個(gè)節(jié)點(diǎn)的前驅(qū):" << pre->data << endl;
    else
        cout << "該節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn),無(wú)前驅(qū)" << endl;
    return 0;
}

下面的代碼僅供學(xué)習(xí)使用,課程要求為C/C++變成語(yǔ)言.

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("請(qǐng)輸入第%d個(gè)節(jié)點(diǎn)的內(nèi)容:" % (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("請(qǐng)輸入鏈表長(zhǎng)度:"))
    linklist.add_n_elems(length)
    print("鏈表內(nèi)容:", end="")
    linklist.show()

    index = int(input("\n輸入需要查找前驅(qū)的節(jié)點(diǎn)的索引(0< n <=%d):" % linklist.size()))
    node = linklist.get_node(index)
    pre_node = linklist.pre_node_of(node)
    print("第%d個(gè)節(jié)點(diǎn)的內(nèi)容:%d" % (index, node.data))
    if pre_node is not None:
        print("第%d個(gè)節(jié)點(diǎn)的前驅(qū)的內(nèi)容內(nèi)容:%d" % (index, pre_node.data))
    else:
        print("該節(jié)點(diǎn)無(wú)前驅(qū)節(jié)點(diǎn)")

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("請(qǐng)輸入鏈表長(zhǎng)度:");
        length = scan.nextInt();
        for (int i=0; i<length; ++i) {
            System.out.print("請(qǐng)輸入第" + (i+1) + "個(gè)節(jié)點(diǎn)的內(nèi)容:");
            int data = scan.nextInt();
            list.append(data);
        }
        System.out.print("鏈表內(nèi)容:");
        list.show();

        System.out.print("\n輸入需要查找前驅(qū)的節(jié)點(diǎ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 + "個(gè)節(jié)點(diǎn)的內(nèi)容:" + node.data);
        if (pre_node != null)
            System.out.println("第" + index + "個(gè)節(jié)點(diǎn)的前驅(qū)的內(nèi)容內(nèi)容:"  + pre_node.data);
        else
            System.out.println("該節(jié)點(diǎn)無(wú)前驅(qū)節(jié)點(diǎn)");


    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 一些概念 數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，而且確保經(jīng)過(guò)這...
    Winterfell_Z閱讀 6,573評(píng)論 0贊 13
  • 轉(zhuǎn)自：http://blog.csdn.net/oreo_go/article/details/52116214 ...
    YYT1992閱讀 1,267評(píng)論 0贊 4
  • 目錄 1、屬性 2、鏈表和數(shù)組的區(qū)別 2.1、數(shù)組概述 2.2、數(shù)組和鏈表優(yōu)缺點(diǎn) 2.3、鏈表和數(shù)組的比較 3、單...
    我哈啊哈啊哈閱讀 2,935評(píng)論 1贊 41
  • （一）睡眠 如果睡眠不足，就會(huì)精神恍惚，暈頭轉(zhuǎn)向；如果耐心不足，就會(huì)心浮氣躁，多做后悔之事。 年關(guān)將至，午休時(shí)間、...
    邢姑娘閱讀 338評(píng)論 0贊 1
  • 桐婳問(wèn)：“爸爸是不是做了什么壞事被警察叔叔抓起來(lái)了?。俊薄盀槭裁催@么說(shuō)”我不解。桐婳一本正經(jīng)地說(shuō)，“因?yàn)樗?..
    桐婳媽媽閱讀 412評(píng)論 1贊 0

友情鏈接更多精彩內(nèi)容