链表实现（学习版） LinkedList Study代码,C/C++代码库,德仔网

代码语言

代码分类

【C/C++】链表实现（学习版） LinkedList Study

作者:智睿 / 发布于2016/6/27/ 467

本代码是一个演示链表(Linkedlist)基本原理的小程序，仅仅为了说明LinkedList的工作原理以及实现时需要考虑的问题。至于性能……呵呵，由于指针太多性能实在不咋的。正式的链表实现过两天会跟一个List总结一起PO出来的，届时也能解答各位网友的留言。谢谢关注！备注：输出严格遵循用户在特定位置插入元素顺序。

#include "SingleLinkedList.h"
#include<stdlib.h>
#include<stdio.h>
 
using namespace std;
 
int main()
{
    SingleLinkList<int> sll;
    int n, i;
    printf("Enter the Number of nodes(n > 5): ");
    scanf("%d", &n);
 
    //Node<int> *q = new Node<int>(0);
    //sll.insert(q, 0);
 
    for (i = 1; i <= n; i++)
    {
        Node<int> *p = new Node<int>(i);
        sll.insertAt(p, 0);
        //sll.append(p);
    }
    printf("The length of list = %d\n", sll.getSize());
    sll.printList();
 
    printf("Value at 3: ", sll.getValAt(3));
    cout << "List contains element 4? " << sll.contains(4) << endl;
 
    /*delete the first node */
    sll.removeEle(1);
    printf("The length of list = %d\n", sll.getSize());
    sll.printList();
 
    sll.removeAt(0);
    printf("The length of list = %d\n", sll.getSize());
    sll.printList();
 
    /*delete the last node*/
    sll.removeEle(sll.lastNode()->element);
    printf("The length of list = %d\n", sll.getSize());
    sll.printList();
 
    for (i = 10; i <= 15; i++)
    {
        Node<int> * newPtr = new Node<int>(i);
        sll.append(newPtr);
    }
    printf("The length of list = %d\n", sll.getSize());
    sll.printList();
 
    system("pause");
    return 0;
}



#pragma once
 
#include<iostream>
 
using namespace std;
 
template<typename T>
class Node
{
public:
    T element;
    Node * next;
 
    Node(Node * nextNode = NULL)
    {
        next = nextNode
    }
 
    Node(T ele, Node * nextNode = NULL)
    {
        element = ele;
        next = nextNode;
    }
};//end class: The node class
 
template<typename T>
class SingleLinkList
{
private:
    Node<T> * head;
    int size;
 
public:
    SingleLinkList()
    {
        head = NULL;
        size = 0;
    }//end constructor
 
    ~SingleLinkList()
    {
        clear();
        //cout << "The testing is finished" << endl;
        //system("pause");
    }//end destructor
 
    Node<T> * lastNode()
    {
        Node<T> * p = head;
        while (p->next != NULL)
            p = p->next;
 
        return p;
    }//end method: Return the lastNodePtr
 
    void append(Node<T> * node)
    {
        if (node == NULL)
            return;
 
        if (head == NULL)
        {
            head = node;
            size = 1;
            return;
        }//end if: Currently no element
 
        Node<T> * tail = lastNode();
        tail->next = node;
 
        size++;
    }//end function
 
    void insertAt(Node<T> * node, int pos)
    {
        if (head == NULL)
        {
            head = node;
            size = 1;
            /*cout << "Element: " << node->element << " inserted " << endl;*/
            return;
        }//end if: Currently no element
 
        if (node == NULL || pos > size)
        {
            cout << "Postion out of index!!" << endl;
            return;
        }//end if
 
        //find the right place
        Node<T> *tracer = head;
 
        /*
            The insertion plan to keep nodes in order
            is that first a node is inserted at the exact postion
            user want to and then switch value with the front node
            to keep the nodes in the exact order they are 
            inserted even user wants to insert into head node.
        */
        for (int index = 0; index < pos; index++)
        {
            /*
            Those codes are ensure that when elements are always inserted
            at last, the list is in the order according to inserting.
            Instead of Node(0) goes no where with list grows.
            */
            if (tracer->next == NULL)
            {
                append(node);
                return;
            }//end if
 
            tracer = tracer->next;
        }//end loop         
 
        /*cout << "Element: " << node->element << " inserted " << endl;*/
 
        T value = tracer->element;
        tracer->element = node->element;
        node->element = value;
 
        node->next = tracer->next;
        tracer->next = node;
 
        size++;
    }//end function
 
    int getSize()
    {
        return size;
    }//end method: Get size of this linkedlist.
 
    Node<T> * createNode(T val)
    {
        Node<T> * newNode = new Node<T>(val);
        return newNode;
    }//end method: Return value of a certain node.
 
    void clear()
    {
        Node<T> *tracer = head;
        while (head->next != NULL)
        {
            tracer = head->next;
            head->next = tracer->next;
            delete tracer;
        }
 
        delete head;
        size = 0;
    }//end function: Delete all nodes.
 
    bool contains(const T value)
    {
        Node<T> *tracer = head;
        while (tracer != NULL && tracer->element != value)
        {
            if (value == tracer->element)
                return true;
            tracer = tracer->next;
        }
        return false;
    };//Check whether the list has certain element.
 
    void printList()
    {
        Node<T> *p = head;
 
        for (int index = 0; index < size; index++)
        {
            cout << "Node " << index << " value: " << p->element << endl;
            if (p->next != NULL)             
                p = p->next;
            else
            {
                cout << "Finish printing " << endl;
                return;
            }//end if-else
        }//end loop.
    };//end function
 
    T getValAt(int pos)
    {
        int index = 0;
        Node<T> *p = head;
        for (int index = 0; index < pos; index++)
            if (p->next != NULL)
                p = p->next;
 
        return p->element;
    }//end function: Find element at given index.
 
    void removeAt(int pos)
    {
        if (pos >= size)
        {
            cout << "Index out of bound!" << endl;
            return;
        }
         
        Node<T> *p2 = head;
        Node<T> *p1 = p2;
 
        for (int index = 0; index < pos; index++)
        {
            p1 = p2;
            p2 = p2->next;
        }//end koop
 
        if (p2 == NULL)
            return;
        if (p2 == head)/* first node */
            head = p2->next;
        else /* other node, including the last node */
            p1->next = p2->next;
 
        delete p2;
 
        size--;
        cout << "Remove element at: " << pos << endl;
    }//end function: Remove element at certain postion.
 
    void removeEle(T ele)
    {
        Node<T> *p2 = head;
        Node<T> *p1 = p2;
        while (p2 != NULL && p2->element != ele)
        {
            p1 = p2;
            p2 = p2->next;
        }//end koop
 
        if (p2 == NULL)
            return;
        if (p2 == head)
            head = p2->next;
        else
            p1->next = p2->next;
 
        delete p2;
 
        cout << "Remove element: " << ele << endl;
        size--;
    }//end function
 
};//end class

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　链表　

同语言下

可能有用的

智睿贡献的其它代码(10)