[toc]

不帶頭結(jié)點(diǎn)的單鏈表

這次我嘗試按照代碼演示的順序做筆記

和帶節(jié)點(diǎn)的單鏈表差不多,只不過(guò)要對(duì)第一個(gè)節(jié)點(diǎn)做特殊的處理

初始化,按位序刪除,插入,遍歷

按位序查找,按值查找,判空,求表長(zhǎng)

初始化,按位序刪除,按位序插入,遍歷

演示代碼如下

//初始化
    LinkList l;
    initList(l);     
    cout<<"邊界測(cè)試,插入0號(hào)位置"<<endl;
    if(!insertListByOrder(l, 0,1)){
        cout<<"插入失敗"<<endl;
    }
    cout<<"邊界測(cè)試,插入8號(hào)位置"<<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<<"邊界測(cè)試,刪除第0個(gè)位置"<<endl;
    int e;
    if(!deleteListByOrder(l,0,e)){
        cout<<"刪除0號(hào)失敗"<<endl;
    }
    cout<<"邊界測(cè)試,刪除第8個(gè)位置"<<endl;
    if(!deleteListByOrder(l,8,e)){
        cout<<"刪除8號(hào)失敗"<<endl;
    }
    cout<<"正常刪除,刪除第2個(gè)位置"<<endl;
    deleteListByOrder(l,2,e);
    cout<<"刪除的值是"<<e<<endl;
    printList(l);

結(jié)果

邊界測(cè)試,插入0號(hào)位置
插入失敗
邊界測(cè)試,插入8號(hào)位置
插入失敗
正常插入 1,2,3
單鏈表的第1個(gè)值是:1
單鏈表的第2個(gè)值是:2
單鏈表的第3個(gè)值是:3
邊界測(cè)試,刪除第0個(gè)位置
刪除0號(hào)失敗
邊界測(cè)試,刪除第8個(gè)位置
刪除8號(hào)失敗
正常刪除,刪除第2個(gè)位置
刪除的值是2
單鏈表的第1個(gè)值是:1
單鏈表的第2個(gè)值是:3

初始化

由于是不帶頭結(jié)點(diǎn)的,不用分配一個(gè)節(jié)點(diǎn)

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

按位序刪除

先判斷位序異常的情況

刪除第i個(gè)位置,要先找到第i-1個(gè)的位置,假如找到第i個(gè)節(jié)點(diǎn),不能找到前面的節(jié)點(diǎn)

注意釋放空間

注意第一個(gè)節(jié)點(diǎn)特殊處理

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;
    }
    //沒(méi)有0節(jié)點(diǎn),第一個(gè)位置特殊處理
    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; //當(dāng)前p指針指向的節(jié)點(diǎn)
    //插入第2個(gè)位置之后
    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<<"個(gè)值是:"<<p->data<<endl;
        p=p->next;
    }

按位序查找,按值查找,判空,求表長(zhǎng)

演示代碼

 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<<"邊界測(cè)試,返回第0個(gè)位置"<<endl;
    if(getValueByOrder(l,0)){
        cout<<getValueByOrder(l,0)->data<<endl;
    }
    else{
        cout<<"查找失敗"<<endl;
    }
    cout<<"邊界測(cè)試,返回第8個(gè)位置"<<endl;
    if(getValueByOrder(l,8)){
        cout<<getValueByOrder(l,8)->data<<endl;
    }
    else{
        cout<<"查找失敗"<<endl;
    }
    cout<<"正常測(cè)試,返回第2個(gè)位置"<<endl;
    if(!getValueByOrder(l,2)){
        cout<<getValueByOrder(l,2)->data<<endl;
    }
    int n=1;
    if(getValue_noH(l,n)){
        cout<<"找到了值為"<<n<<"的數(shù)"<<endl;
    }
    cout<<"表長(zhǎng)為"<<length(l)<<endl;
    if(!isEmpty(l)){
        cout<<"表長(zhǎng)不空"<<endl;
    }

結(jié)果

正常插入 1,2,3
單鏈表的第1個(gè)值是:1
單鏈表的第2個(gè)值是:2
單鏈表的第3個(gè)值是:3
邊界測(cè)試,返回第0個(gè)位置
查找失敗
邊界測(cè)試,返回第8個(gè)位置
查找失敗
正常測(cè)試,返回第2個(gè)位置
找到了值為1的數(shù)
表長(zhǎng)為3
表長(zhǎng)不空

按位序查找

位序?yàn)?的時(shí)候,找不到,返回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);
}

求表長(zhǎng)

如果為空表,p為空,len不變返回0

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

指定節(jié)點(diǎn)后插,指定節(jié)點(diǎn)前插,指定節(jié)點(diǎn)的刪除(有無(wú)頭節(jié)點(diǎn)相同)

演示代碼

 LinkList l;
    initList(l);
    insertListByOrder(l,1,9999);
    //必須先有一個(gè)節(jié)點(diǎn),不然為空,無(wú)法在空節(jié)點(diǎn)后面插入.
    cout<<"頭節(jié)點(diǎn)插入9999"<<endl;
    cout<<"頭節(jié)點(diǎn)后面插入1"<<endl;
    insertNextNode(l,1);
    printList(l);
    cout<<"先查找值為1的節(jié)點(diǎn),再后插2"<<endl;
    insertNextNode(getValue_noH(l,1),2);
    printList(l);
    cout<<"先查找值為0的節(jié)點(diǎn),再前插-1,由于沒(méi)有,不執(zhí)行"<<endl;
    //為空,不進(jìn)行
    if(getValue_noH(l,0)){
         insertNextNode(getValue_noH(l,0),-1);
    }
    cout<<"先查找值為1的節(jié)點(diǎn),再前插0"<<endl;
    insertPriorNode(getValue_noH(l,1),0);
    printList(l);
    int e;
    cout<<"指定節(jié)點(diǎn),值為0的刪除"<<endl;
    deleteNode(getValue_noH(l,0),e);
    printList(l);
    
    cout<<"刪除最后一個(gè)節(jié)點(diǎn),方法失效"<<endl;
    deleteNode(getValue_noH(l,2),e);
    //方法失效
    printList(l);

結(jié)果

頭節(jié)點(diǎn)插入9999
頭節(jié)點(diǎn)后面插入1
單鏈表的第1個(gè)值是:9999
單鏈表的第2個(gè)值是:1
先查找值為1的節(jié)點(diǎn),再后插2
單鏈表的第1個(gè)值是:9999
單鏈表的第2個(gè)值是:1
單鏈表的第3個(gè)值是:2
先查找值為0的節(jié)點(diǎn),再前插-1,由于沒(méi)有,不執(zhí)行
先查找值為1的節(jié)點(diǎn),再前插0
單鏈表的第1個(gè)值是:9999
單鏈表的第2個(gè)值是:0
單鏈表的第3個(gè)值是:1
單鏈表的第4個(gè)值是:2
指定節(jié)點(diǎn),值為0的刪除
單鏈表的第1個(gè)值是:9999
單鏈表的第2個(gè)值是:1
單鏈表的第3個(gè)值是:2
刪除最后一個(gè)節(jié)點(diǎn),方法失效
單鏈表的第1個(gè)值是:9999
單鏈表的第2個(gè)值是:1
單鏈表的第3個(gè)值是:2

指定節(jié)點(diǎn)后插

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;
}

指定節(jié)點(diǎn)前插

//并非給頭節(jié)點(diǎn),一個(gè)個(gè)找指定節(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn).而是偷天換日
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;

}

指定節(jié)點(diǎn)的刪除

//給頭節(jié)點(diǎn)遍歷找到要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
//偷天換日限制性->當(dāng)要?jiǎng)h除的節(jié)點(diǎn)是最后一個(gè)時(shí)候,方法失效
bool deleteNode(LNode *p,int &e){
    if(p==NULL){
        return false;
    }
    e=p->data;
    LNode *q=p->next;
    //如果后面的不是空節(jié)點(diǎn),即不是最后一個(gè),
    //否則會(huì)空指針賦值,異常
    if(q){
        p->data=q->data;
        p->next=q->next;
        free(q);
        return true;
    }
    return false;   
}

封裝實(shí)現(xiàn)的按位序插入,刪除(未實(shí)現(xiàn))

和第一的測(cè)試代碼差不多,只不過(guò)變成了封裝后的,運(yùn)行結(jié)果也一樣

演示

 LinkList l;
    if(initList_H(l)){
        cout<<"初始化成功"<<endl;
    }
    cout<<"邊界測(cè)試,插入0號(hào)位置"<<endl;
    insertListByOrder_H_fg(l, 0,1);
    cout<<"邊界測(cè)試,插入8號(hào)位置"<<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<<"邊界測(cè)試,刪除第0個(gè)位置"<<endl;
    int e;
    if(!deleteListByOrder_H_fg(l,0,e)){
        cout<<"刪除0號(hào)失敗"<<endl;
    }
    cout<<"邊界測(cè)試,刪除第8個(gè)位置"<<endl;
    if(!deleteListByOrder_H_fg(l,8,e)){
        cout<<"刪除8號(hào)失敗"<<endl;
    }
    cout<<"正常刪除,刪除第2個(gè)位置"<<endl;
    deleteListByOrder_H_fg(l,2,e);
    cout<<"刪除的值是"<<e<<endl;
    printList_H(l);

結(jié)果

初始化成功
邊界測(cè)試,插入0號(hào)位置
邊界測(cè)試,插入8號(hào)位置
正常插入 1,2,3
單鏈表的第1個(gè)值是:1
單鏈表的第2個(gè)值是:2
單鏈表的第3個(gè)值是:3
邊界測(cè)試,刪除第0個(gè)位置
刪除0號(hào)失敗
邊界測(cè)試,刪除第8個(gè)位置
刪除8號(hào)失敗
正常刪除,刪除第2個(gè)位置
刪除的值是2
單鏈表的第1個(gè)值是:1
單鏈表的第2個(gè)值是:3

封裝實(shí)現(xiàn)的按位序插入

//封裝方法實(shí)現(xiàn)的按位序插入
bool insertListByOrder_H_fg(LinkList &l,int num,int e){
    if(num<1){
        return false;
    }
    //得到前一個(gè)節(jié)點(diǎn)
    LNode* p=getValueByOrder_H(l,num-1);
    //后插
    return insertNextNode(p,e);
}

封裝實(shí)現(xiàn)的按位序刪除

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個(gè)節(jié)點(diǎn)為空
    if(p->next==NULL){
        return false;
    }
    LNode *q=p->next; //用于釋放刪除的節(jié)點(diǎn)
    p->next=q->next;
    e=q->data;
    free(q);
    return true;
}

頭插法與尾插法建立單鏈表

演示

LinkList l;
    cout<<"尾插法生成單鏈表,手動(dòng)輸入 ,輸入999結(jié)束"<<endl;
    tailInsertList(l);
    printList(l);
    LinkList l2;
    cout<<"頭插法生成單鏈表,手動(dòng)輸入 ,輸入999結(jié)束"<<endl;
    headInsertList(l2);
    printList(l2);
    //有興趣的可以實(shí)現(xiàn)
    //LinkList l3=headInsertList_H_nx(l2);
    //cout<<"頭插法生成單鏈表,逆序"<<endl;
    //printList_H(l3);

結(jié)果

尾插法生成單鏈表,手動(dòng)輸入 ,輸入999結(jié)束
1
2
3
999
單鏈表的第1個(gè)值是:1
單鏈表的第2個(gè)值是:2
單鏈表的第3個(gè)值是:3
頭插法生成單鏈表,手動(dòng)輸入 ,輸入999結(jié)束
1
2
3
999
單鏈表的第1個(gè)值是:3
單鏈表的第2個(gè)值是:2
單鏈表的第3個(gè)值是:1

尾插法

LinkList tailInsertList(LinkList &l){
    l=NULL;
    LNode *p,*q=l;
    int a;
    scanf("%d",&a);
    while(a!=999){
        p=(LNode*)malloc(sizeof(LNode)); //新節(jié)點(diǎn)
        p->data=a;
        //第一個(gè)節(jié)點(diǎn)的特殊處理,要讓第一個(gè)節(jié)點(diǎn)等于新生成的節(jié)點(diǎn)
        if(!l){
            l=p;
            q=p;
            

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

            
        }
        
        scanf("%d",&a);
    }
    //如果上來(lái)輸入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;
    
}

頭插法實(shí)現(xiàn)逆序

保留

報(bào)錯(cuò)

不能將 "LNode *" 類型的值分配到 "LNode *" 類型的實(shí)體

定義結(jié)構(gòu)體的時(shí)候出現(xiàn)問(wèn)題

typedef struct { //這里沒(méi)有說(shuō)結(jié)構(gòu)體的名字 typedef struct LNode
int data;
struct Lnode next;
}Lnode,LinkList;

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一.單鏈表(2)不帶頭結(jié)點(diǎn)的

一.單鏈表(2)不帶頭結(jié)點(diǎn)的

不帶頭結(jié)點(diǎn)的單鏈表

初始化,按位序刪除,按位序插入,遍歷

初始化

按位序刪除

按位序插入

遍歷

按位序查找,按值查找,判空,求表長(zhǎng)

按位序查找

按值查找

判空

求表長(zhǎng)

指定節(jié)點(diǎn)后插,指定節(jié)點(diǎn)前插,指定節(jié)點(diǎn)的刪除(有無(wú)頭節(jié)點(diǎn)相同)

指定節(jié)點(diǎn)后插

指定節(jié)點(diǎn)前插

指定節(jié)點(diǎn)的刪除

封裝實(shí)現(xiàn)的按位序插入,刪除(未實(shí)現(xiàn))

封裝實(shí)現(xiàn)的按位序插入

封裝實(shí)現(xiàn)的按位序刪除

頭插法與尾插法建立單鏈表

尾插法

頭插法

頭插法實(shí)現(xiàn)逆序

報(bào)錯(cuò)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

一.單鏈表(2)不帶頭結(jié)點(diǎn)的

不帶頭結(jié)點(diǎn)的單鏈表

初始化,按位序刪除,按位序插入,遍歷

初始化

按位序刪除

按位序插入

遍歷

按位序查找,按值查找,判空,求表長(zhǎng)

按位序查找

按值查找

判空

求表長(zhǎng)

指定節(jié)點(diǎn)后插,指定節(jié)點(diǎn)前插,指定節(jié)點(diǎn)的刪除(有無(wú)頭節(jié)點(diǎn)相同)

指定節(jié)點(diǎn)后插

指定節(jié)點(diǎn)前插

指定節(jié)點(diǎn)的刪除

封裝實(shí)現(xiàn)的按位序插入,刪除(未實(shí)現(xiàn))

封裝實(shí)現(xiàn)的按位序插入

封裝實(shí)現(xiàn)的按位序刪除

頭插法與尾插法建立單鏈表

尾插法

頭插法

頭插法實(shí)現(xiàn)逆序

報(bào)錯(cuò)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av