[toc]

带头结点的单链表

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

_H意思是 _head,即带头结点的

其中,getValue忘记加_H了

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

演示代码如下

void test_H(){
    //初始化
    LinkList l;
    if(initList_H(l)){
        cout<<"初始化成功"<<endl;
    }
    cout<<"边界测试,插入0号位置"<<endl;
    insertListByOrder_H(l, 0,1);
    cout<<"边界测试,插入8号位置"<<endl;
    insertListByOrder_H(l, 8,1);
    cout<<"正常插入 1,2,3"<<endl;
    for(int i=1;i<4;i++){
        insertListByOrder_H(l, i,i);
    }
    printList_H(l);
    cout<<"边界测试,删除第0个位置"<<endl;
    int e;
    if(!deleteListByOrder_H(l,0,e)){
        cout<<"删除0号失败"<<endl;
    }
    cout<<"边界测试,删除第8个位置"<<endl;
    if(!deleteListByOrder_H(l,8,e)){
        cout<<"删除8号失败"<<endl;
    }
    cout<<"正常删除,删除第2个位置"<<endl;
    deleteListByOrder_H(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 initList_H(LinkList &l){
    l=(LNode *)malloc(sizeof(LNode));
    if(l==NULL){ //分配失败
        return false;
    }
    l->next=NULL;
    return true;
}

按位序删除

先判断位序异常的情况

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

注意释放空间

bool deleteListByOrder_H(LinkList &l,int num,int &e){
    if(num<1){
        return false;
    }
    int i=0;
    //指向头节点的p指针,用来后移
    LNode *p=l;
    //找到第num-1个
    while(i<num-1&&p!=NULL){
        p=p->next;
        i++;
    }
    //没有那么多节点
    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;
}

按位序插入

bool insertListByOrder_H(LinkList &l,int num,int e){
   /*  头节点不插入值 所以插入位置只能从1开始
        if (num==0){
        l->data=e;
    } */
    if(num<1){
        cout<<"位序有误"<<endl;
        return false;
    }
    /* 第一个节点 应该位序是0
    int i=1;
    LNode *p=l; */
    int i=0;
    LNode *p =l;
    //找到第i-1个位置,好来插入 
    //插入第一个节点 可以直接找到第0个位置
    while(i<(num-1)&&p!=NULL){
        p=p->next;
        i++;
    }
    //注意别忘了这个 插入了不存在的位置 num大于长度
    if(p==NULL){
        cout<<"位序有误"<<endl;
        return false;
    }
    LNode *q=(LNode *)malloc(sizeof(LNode));
    q->data=e;
    q->next=p->next;
    p->next=q;
    return true;

}

遍历

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

    }
}

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

演示代码

 LinkList l;
    if(initList_H(l)){
        cout<<"初始化成功"<<endl;
    }
    cout<<"正常插入 1,2,3"<<endl;
    for(int i=1;i<4;i++){
        insertListByOrder_H(l, i,i);
    }
    printList_H(l);
    cout<<"边界测试,返回第0个位置"<<endl;
    if(getValueByOrder_H(l,0)){
        //返回的是头节点无意义的值
        cout<<getValueByOrder_H(l,0)->data<<endl;
    }
    else{
        cout<<"查找失败"<<endl;
    }
    cout<<"边界测试,返回第8个位置"<<endl;
    if(getValueByOrder_H(l,8)){
        cout<<getValueByOrder_H(l,8)->data<<endl;
    }
    else{
        cout<<"查找失败"<<endl;
    }
    cout<<"正常测试,返回第2个位置"<<endl;
    if(!getValueByOrder_H(l,2)){
        cout<<getValueByOrder_H(l,2)->data<<endl;
    }
    int n=2;
    if(getValue(l,n)){
        cout<<"找到了值为"<<n<<"的数"<<endl;
    }
    cout<<"表长为"<<length_H(l)<<endl;
    if(!isEmpty_H(l)){
        cout<<"表长不空"<<endl;
    }

结果

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

按位序查找

位序为0的时候,返回头节点

LNode* getValueByOrder_H(LinkList &l,int num){
    if(num<0){
        return NULL;
    }
    int i=0;
    LNode *p =l;
    //如果num=0,不满足0<0,返回头节点
    //如果num 很大,不满足p!=NULL;返回空节点
    while(i<num&&p!=NULL){
        p=p->next;
        i++;
    }
    return p;
}

按值查找

LNode* getValue(LinkList l,int e){
    LNode *p =l->next;
    while(p!=NULL&&p->data!=e){
        p=p->next;
    }
    //是空就返回空
    return p;
}

c

判空

bool isEmpty_H(LinkList l){
    return((l->next)==NULL);
}

求表长

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

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

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

演示代码

LinkList l;
    if(initList_H(l)){
        cout<<"初始化成功"<<endl;
    }
    insertNextNode(l,1);
    cout<<"先查找值为1的节点,再后插"<<endl;
    insertNextNode(getValue(l,1),2);
    printList_H(l);
    cout<<"先查找值为0的节点,再前插"<<endl;
    //为空,不进行
    if(getValue(l,0)){
         insertNextNode(getValue(l,0),-1);
    }
    cout<<"先查找值为1的节点,再前插0"<<endl;
    insertPriorNode(getValue(l,1),0);
    printList_H(l);
    int e;
    cout<<"指定节点,值为0的删除"<<endl;
    deleteNode(getValue(l,0),e);
    printList_H(l);
    cout<<"删除最后一个节点"<<endl;
    deleteNode(getValue(l,2),e);
    //方法失效
    printList_H(l);

结果

初始化成功
先查找值为1的节点,再后插
单链表的第1个值是:1
单链表的第2个值是:2
先查找值为0的节点,再前插
先查找值为1的节点,再前插0
单链表的第1个值是:0
单链表的第2个值是:1
单链表的第3个值是:2
指定节点,值为0的删除
单链表的第1个值是:1
单链表的第2个值是:2
删除最后一个节点
单链表的第1个值是:1
单链表的第2个值是: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_H(l);
    printList_H(l);
    LinkList l2;
    cout<<"头插法生成单链表,手动输入 ,输入999结束"<<endl;
    headInsertList_H(l2);
    printList_H(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
头插法生成单链表,逆序
单链表的第1个值是:1
单链表的第2个值是:2
单链表的第3个值是:3

尾插法

/*
每次取数据,设置一个长度,然后遍历插入到最后,是o(n)
不如设置一个尾指针,每次在尾指针之后插入
利用后插操作 
 */
LinkList tailInsertList_H(LinkList &l){
    l=(LinkList)malloc(sizeof(LNode));
    LNode *p ,*q=l;
    int a;
    scanf("%d",&a);
    while(a!=999){
        //插入的节点,由p指示
        p=(LinkList)malloc(sizeof(LNode));
        p->data=a;
        //尾节点 q指示
        q->next=p;
        q=p;
        scanf("%d",&a);
    }
    q->next=NULL;
    return l;


}

头插法

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

头插法实现逆序

LinkList headInsertList_H_nx(LinkList l){
    //新生成的单链表
    LinkList q=(LinkList)malloc(sizeof(LNode));
    q->next=NULL;
    //指向原单链表的元素
    LNode *p=l->next;
    LNode *r;
    //int a;
    //scanf("%d",&a);
    while(p){
        //新节点r
        r=(LNode*)malloc(sizeof(LNode));
        r->data=p->data;
        p=p->next;
        r->next=q->next;
        q->next=r;
    }
    return q;
}

报错

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

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

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