萌新学习数据结构与算法的笔记

/*单链表的实现
 *
 * */
#include <iostream>;
using namespace std;

class IntNode{
    public:
        IntNode *next;
        int info;

        IntNode(int i,IntNode *p){
            info = i;
            next = p;
        }
        //只有一个节点时候
        IntNode(int i){
            next = 0;
            info = i;
        }
};

class IntSimpleChain{
    private:
        IntNode *head;
        IntNode *tail;

    public:
        void addToHead(int element){
            if(isEmpty()){
                head = tail = new IntNode(element);
            }
            else {
                head = new IntNode(element,head);
            }
        }

        void addToTail(int element){
            if(isEmpty()){
                head = new IntNode(element);
                tail = head;
            }
            else {
                tail -> next = new IntNode(element);
                tail = tail -> next;
            }
        }

        void removeFromHead(){
            if(!isEmpty()){
                IntNode *tmp = head;
                head = head ->next;
                delete tmp;
                *tmp = 0;
            }
        }

        void deleteFromTail(){
            if(!isEmpty()){
                IntNode *tmp = head;
                for (;tmp->next != tail; tmp = tmp->next);
                delete tail;
                tail = tmp;
            }
        }

        void deleteElement(int element){
            if(!isEmpty()){
                //一个节点
                if(head->info == element&&head->next ==0){
                    delete head;
                    head = 0;
                    tail = 0;
                }
                else
                //有两个节点以及以上时候
                if(head->next !=0){
                    if(head->info == element){
                        removeFromHead();
                    }
                    else if (tail ->info == element){
                        deleteFromTail();
                    }
                    else {
                        IntNode *prev,*current;
                        for(prev=head,current=head->next;current!=0&&current->info!=element;prev = prev->next,current=current->next);
                        prev->next = current ->next;
                        delete current;
                        *current = 0;
                    }
                }

            }
        }

        bool isEmpty(){
            //0在C++ 可以代表null
            return head == nullptr;
        }
};

int main(){
    IntSimpleChain myChain;

    for (int i=0;i<4;i++){
        myChain.addToTail(i);
    }

    myChain.deleteElement(1);

    return 0;
}
分类: C++数据结构

1 条评论

sudo · 2017年11月10日 下午11:46

不错哦!

发表评论

电子邮件地址不会被公开。