[数据结构与算法]数据结构之单链表基本操作

#include <iostream>
using namespace std;

//单链表定义
typedef struct LinkNode{
    int data;
    struct LinkNode *next;
}LNode,*LinkedList;




void HeadInsert(LNode* &head)
{
    int x;
    //创建一个头结点
    head=(LNode *) malloc(sizeof (LNode));
    head->next=NULL;
    cin>>x;
    while(x!=9999){
        LNode* node=(LNode *) malloc(sizeof (LNode));
        node->data=x;
        node->next=head->next;
        head->next=node;
        cin>>x;
    }

}

/**
 * 尾插法
 * @param head
 */
void TailInsert(LNode* &head){
    cout<<"开始创建单链表……"<<endl;
    int x;
    head=(LNode *) malloc(sizeof (LNode));
    head->next=NULL;
    LNode *tail=head;
    cin>>x;
    while(x!=-1){
        LNode* node=(LNode *) malloc(sizeof (LNode));
        node->data=x;
        node->next=NULL;
        tail->next=node;
        tail=node;
        cin>>x;
    }
}

LNode* getElemByOrder(LNode *head,int position){
    LNode *p=head->next;int i=1;
    if(position<1)return NULL;
    while(p!=NULL){
        if(position==i)
        return p;
        else {
            p=p->next;++i;
        }
    }
    return NULL;
}



/**
 * 单链表按值找结点
 * @param head
 * @param value
 * @return
 */
LNode* LocateElem(LNode* head,int value){
    LNode *p=head->next;
    while(p!=NULL){
        if(p->data==value)return p;
        p=p->next;
    }
    return NULL;

}

int getLength(LNode* head){
    int num=0;
    LNode *p=head;
    while(p->next!=NULL){
        ++num;
        p=p->next;
    }
    return num;
}

/**
 * 后插法，先找到前一个位置的结点
 * 时间复杂度O(n),主要时间消耗在于找到position-1的结点
 * @param head
 * @param position
 * @return
 */
bool BehindInsert(LNode *head,int position){
    if(position>getLength(head)+1||position<1)return false;
    LNode *s=(LNode*) malloc(sizeof (LNode));
    int data;
    cout<<"请输入插入结点的值：";cin>>data;
    s->data=data;
    LNode *p= getElemByOrder(head,position-1);
    s->next=p->next;
    p->next=s;
    return true;
}

/**
 * 删除结点，时间复杂度同样为O(n)
 * @param head
 * @param position
 * @return
 */
bool DeleteNode(LNode* head,int position){
    if(position>getLength(head)+1||position<1)return false;
    LNode *p= getElemByOrder(head,position-1);
    LNode *q=p->next;
    p->next=q->next;
    free(q);
}


/**
 * 打印链表
 * @param list
 */
void print(LNode *list){
    LNode *p=list;
    while(p->next!=NULL){
        p=p->next;
        cout<<p->data<<" ";

    }
    cout<<endl;
}



int main (){
    LNode *list,*list2;int position;int value;
//    HeadInsert(list);
//    print(list);
    TailInsert(list2);
    cout<<"链表创建成功：";
    print(list2);

//    cout<<"输入要查找结点的序号：";cin>>position;
//    cout<<"该节点值为:"<<getElemByOrder(list2,position)->data<<endl;

    cout<<"请输入要插入结点的位置:";cin>>position;
    BehindInsert(list2,position);
    print(list2);

    cout<<"请输入要删除结点的位置:";cin>>position;
    DeleteNode(list2,position);
    print(list2);

    return 0;
};