[toc]

不带头结点的单链表

这次我尝试按照代码演示的顺序做笔记

和带节点的单链表差不多,只不过要对第一个节点做特殊的处理

初始化,按位序删除,插入,遍历

按位序查找,按值查找,判空,求表长

初始化,按位序删除,按位序插入,遍历

演示代码如下

//初始化
    LinkList l;
    initList(l);     
    cout<<"边界测试,插入0号位置"<<endl;
    if(!insertListByOrder(l, 0,1)){
        cout<<"插入失败"<<endl;
    }
    cout<<"边界测试,插入8号位置"<<endl;
    if(!insertListByOrder(l, 8,1)){
        cout<<"插入失败"<<endl;

    }
    cout<<"正常插入 1,2,3"<<endl;
    for(int i=1;i<4;i++){
        insertListByOrder(l, i,i);
    }
    printList(l);
    cout<<"边界测试,删除第0个位置"<<endl;
    int e;
    if(!deleteListByOrder(l,0,e)){
        cout<<"删除0号失败"<<endl;
    }
    cout<<"边界测试,删除第8个位置"<<endl;
    if(!deleteListByOrder(l,8,e)){
        cout<<"删除8号失败"<<endl;
    }
    cout<<"正常删除,删除第2个位置"<<endl;
    deleteListByOrder(l,2,e);
    cout<<"删除的值是"<<e<<endl;
    printList(l);

结果

边界测试,插入0号位置
插入失败
边界测试,插入8号位置
插入失败
正常插入 1,2,3
单链表的第1个值是:1
单链表的第2个值是:2
单链表的第3个值是:3
边界测试,删除第0个位置
删除0号失败
边界测试,删除第8个位置
删除8号失败
正常删除,删除第2个位置
删除的值是2
单链表的第1个值是:1
单链表的第2个值是:3

初始化

由于是不带头结点的,不用分配一个节点

void initList(LinkList &l){
    l=NULL;
}

按位序删除

先判断位序异常的情况

删除第i个位置,要先找到第i-1个的位置,假如找到第i个节点,不能找到前面的节点

注意释放空间

注意第一个节点特殊处理

bool deleteListByOrder(LinkList &l,int num,int &e){
    if(num<1){
        return false;
    }
    if(num==1){
        LNode *p=l;
        e=p->data;
        l->next=NULL;
        free(p);
        return true;
    }
    int i=1;
    LNode *p=l;
    while(i<num-1&&p!=NULL){
        p=p->next;
        i++;
    }
    if(p==NULL){
        return false;
    }
    if(p->next==NULL){
        return false;
    }
    LNode *q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;
}

按位序插入

bool insertListByOrder(LinkList &l,int num,int e){
    if(num<1){
        return false;
    }
    //没有0节点,第一个位置特殊处理
    if(num==1){
        LNode *q=(LNode *)malloc(sizeof(LNode));
        q->data=e;
        l=q;
        q->next=NULL;
        return true;
    }
    
    LNode *p=l;
    int i=1; //当前p指针指向的节点
    //插入第2个位置之后
    while(i<num-1&&p!=NULL){
        p=p->next;
        i++;
    }
    if(p==NULL){
        return false;
    }
    LNode *q=(LNode *)malloc(sizeof(LNode));
    q->data=e;
    q->next=p->next;
    p->next=q;

    return true;

}

遍历

void printList(LinkList l){
    LNode *p=l;
    int i=0;
    while(p){
        cout<<"单链表的第"<<++i<<"个值是:"<<p->data<<endl;
        p=p->next;
    }

按位序查找,按值查找,判空,求表长

演示代码

 LinkList l;
    initList(l);
      
    cout<<"正常插入 1,2,3"<<endl;
    for(int i=1;i<4;i++){
        insertListByOrder(l, i,i);
    }
    printList(l);
    getValueByOrder(l,8)->data;
    cout<<"边界测试,返回第0个位置"<<endl;
    if(getValueByOrder(l,0)){
        cout<<getValueByOrder(l,0)->data<<endl;
    }
    else{
        cout<<"查找失败"<<endl;
    }
    cout<<"边界测试,返回第8个位置"<<endl;
    if(getValueByOrder(l,8)){
        cout<<getValueByOrder(l,8)->data<<endl;
    }
    else{
        cout<<"查找失败"<<endl;
    }
    cout<<"正常测试,返回第2个位置"<<endl;
    if(!getValueByOrder(l,2)){
        cout<<getValueByOrder(l,2)->data<<endl;
    }
    int n=1;
    if(getValue_noH(l,n)){
        cout<<"找到了值为"<<n<<"的数"<<endl;
    }
    cout<<"表长为"<<length(l)<<endl;
    if(!isEmpty(l)){
        cout<<"表长不空"<<endl;
    }

结果

正常插入 1,2,3
单链表的第1个值是:1
单链表的第2个值是:2
单链表的第3个值是:3
边界测试,返回第0个位置
查找失败
边界测试,返回第8个位置
查找失败
正常测试,返回第2个位置
找到了值为1的数
表长为3
表长不空

按位序查找

位序为0的时候,找不到,返回NULL

LNode* getValueByOrder(LinkList &l,int num){
    if(num<1){
        return NULL;
    }
    if(num==1){
        return l;
    }
    int i=1;
    LNode *p=l;
    while(i<num&&p!=NULL){
        p=p->next;
        i++;
    }   
    return p;
    
}

按值查找

LNode* getValue_noH(LinkList l,int e){
    LNode *p=l;
    while(p&&p->data!=e){
        p=p->next;


    }
        return p;

}

判空

bool isEmpty(LinkList l){
    return (l==NULL);
}

求表长

如果为空表,p为空,len不变返回0

int length(LinkList l){
    int len=0;
    LNode *p=l;
    while(p!=NULL){
        p=p->next;
        len++;
    }
    return len;
}

指定节点后插,指定节点前插,指定节点的删除(有无头节点相同)

演示代码

 LinkList l;
    initList(l);
    insertListByOrder(l,1,9999);
    //必须先有一个节点,不然为空,无法在空节点后面插入.
    cout<<"头节点插入9999"<<endl;
    cout<<"头节点后面插入1"<<endl;
    insertNextNode(l,1);
    printList(l);
    cout<<"先查找值为1的节点,再后插2"<<endl;
    insertNextNode(getValue_noH(l,1),2);
    printList(l);
    cout<<"先查找值为0的节点,再前插-1,由于没有,不执行"<<endl;
    //为空,不进行
    if(getValue_noH(l,0)){
         insertNextNode(getValue_noH(l,0),-1);
    }
    cout<<"先查找值为1的节点,再前插0"<<endl;
    insertPriorNode(getValue_noH(l,1),0);
    printList(l);
    int e;
    cout<<"指定节点,值为0的删除"<<endl;
    deleteNode(getValue_noH(l,0),e);
    printList(l);
    
    cout<<"删除最后一个节点,方法失效"<<endl;
    deleteNode(getValue_noH(l,2),e);
    //方法失效
    printList(l);

结果

头节点插入9999
头节点后面插入1
单链表的第1个值是:9999
单链表的第2个值是:1
先查找值为1的节点,再后插2
单链表的第1个值是:9999
单链表的第2个值是:1
单链表的第3个值是:2
先查找值为0的节点,再前插-1,由于没有,不执行
先查找值为1的节点,再前插0
单链表的第1个值是:9999
单链表的第2个值是:0
单链表的第3个值是:1
单链表的第4个值是:2
指定节点,值为0的删除
单链表的第1个值是:9999
单链表的第2个值是:1
单链表的第3个值是:2
删除最后一个节点,方法失效
单链表的第1个值是:9999
单链表的第2个值是:1
单链表的第3个值是:2

指定节点后插

bool insertNextNode(LNode *p ,int e){
    if(p==NULL){ 
        //空指针
        return false;
    }
    LNode *q=(LNode *)malloc(sizeof(LNode));
    if(q==NULL){
        //分配失败
        return false;
    }
    q->data=e;
    q->next=p->next;
    p->next=q;
    return true;
}

指定节点前插

//并非给头节点,一个个找指定节点的前一个结点.而是偷天换日
bool insertPriorNode(LNode *p,int e){
    if(p==NULL){
        return false;
    }
    LNode *q =(LNode *)malloc(sizeof(LNode));
    if(q==NULL){
        return false;
    }
    q->data=p->data;
    q->next=p->next;;
    p->next=q;
    p->data=e;
    return true;

}

指定节点的删除

//给头节点遍历找到要删除节点的前一个结点
//偷天换日限制性->当要删除的节点是最后一个时候,方法失效
bool deleteNode(LNode *p,int &e){
    if(p==NULL){
        return false;
    }
    e=p->data;
    LNode *q=p->next;
    //如果后面的不是空节点,即不是最后一个,
    //否则会空指针赋值,异常
    if(q){
        p->data=q->data;
        p->next=q->next;
        free(q);
        return true;
    }
    return false;   
}

封装实现的按位序插入,删除(未实现)

和第一的测试代码差不多,只不过变成了封装后的,运行结果也一样

演示

 LinkList l;
    if(initList_H(l)){
        cout<<"初始化成功"<<endl;
    }
    cout<<"边界测试,插入0号位置"<<endl;
    insertListByOrder_H_fg(l, 0,1);
    cout<<"边界测试,插入8号位置"<<endl;
    insertListByOrder_H_fg(l, 8,1);
    cout<<"正常插入 1,2,3"<<endl;
    for(int i=1;i<4;i++){
        insertListByOrder_H_fg(l, i,i);
    }
    printList_H(l);
    cout<<"边界测试,删除第0个位置"<<endl;
    int e;
    if(!deleteListByOrder_H_fg(l,0,e)){
        cout<<"删除0号失败"<<endl;
    }
    cout<<"边界测试,删除第8个位置"<<endl;
    if(!deleteListByOrder_H_fg(l,8,e)){
        cout<<"删除8号失败"<<endl;
    }
    cout<<"正常删除,删除第2个位置"<<endl;
    deleteListByOrder_H_fg(l,2,e);
    cout<<"删除的值是"<<e<<endl;
    printList_H(l);

结果

初始化成功
边界测试,插入0号位置
边界测试,插入8号位置
正常插入 1,2,3
单链表的第1个值是:1
单链表的第2个值是:2
单链表的第3个值是:3
边界测试,删除第0个位置
删除0号失败
边界测试,删除第8个位置
删除8号失败
正常删除,删除第2个位置
删除的值是2
单链表的第1个值是:1
单链表的第2个值是:3

封装实现的按位序插入

//封装方法实现的按位序插入
bool insertListByOrder_H_fg(LinkList &l,int num,int e){
    if(num<1){
        return false;
    }
    //得到前一个节点
    LNode* p=getValueByOrder_H(l,num-1);
    //后插
    return insertNextNode(p,e);
}

封装实现的按位序删除

bool deleteListByOrder_H_fg(LinkList &l,int num,int &e){
    if(num<1){
        return false;
    }
    LNode *p=getValueByOrder_H(l,num-1);
     if(p==NULL){
        return false;
    }
    //第num个节点为空
    if(p->next==NULL){
        return false;
    }
    LNode *q=p->next; //用于释放删除的节点
    p->next=q->next;
    e=q->data;
    free(q);
    return true;
}

头插法与尾插法建立单链表

演示

LinkList l;
    cout<<"尾插法生成单链表,手动输入 ,输入999结束"<<endl;
    tailInsertList(l);
    printList(l);
    LinkList l2;
    cout<<"头插法生成单链表,手动输入 ,输入999结束"<<endl;
    headInsertList(l2);
    printList(l2);
    //有兴趣的可以实现
    //LinkList l3=headInsertList_H_nx(l2);
    //cout<<"头插法生成单链表,逆序"<<endl;
    //printList_H(l3);

结果

尾插法生成单链表,手动输入 ,输入999结束
1
2
3
999
单链表的第1个值是:1
单链表的第2个值是:2
单链表的第3个值是:3
头插法生成单链表,手动输入 ,输入999结束
1
2
3
999
单链表的第1个值是:3
单链表的第2个值是:2
单链表的第3个值是:1

尾插法

LinkList tailInsertList(LinkList &l){
    l=NULL;
    LNode *p,*q=l;
    int a;
    scanf("%d",&a);
    while(a!=999){
        p=(LNode*)malloc(sizeof(LNode)); //新节点
        p->data=a;
        //第一个节点的特殊处理,要让第一个节点等于新生成的节点
        if(!l){
            l=p;
            q=p;
            

        }
        else{
            q->next=p;
            q=p;

            
        }
        
        scanf("%d",&a);
    }
    //如果上来输入999 那q为空->next空指针 
    if(q){
        q->next=NULL;
    }
    
    return l;

}

头插法

LinkList headInsertList(LinkList &l){
    l=NULL;
    LNode *p;
    int a;
    scanf("%d",&a);
     //a=1;
    while(a!=999){
        p=(LNode *)malloc(sizeof(LNode));
        p->data=a;
        if(!l){
            l=p;
            p->next=NULL;

        }else{
             p->next=l;
             l=p;
        }
        scanf("%d",&a);
       

    }
    return l;
    
}

头插法实现逆序

保留

报错

不能将 "LNode *" 类型的值分配到 "LNode *" 类型的实体

定义结构体的时候出现问题

typedef struct { //这里没有说结构体的名字 typedef struct LNode
int data;
struct Lnode next;
}Lnode,LinkList;