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

[toc]

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

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

_H意思是 _head,即帶頭結(jié)點(diǎn)的

其中,getValue忘記加_H了

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

演示代碼如下

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

初始化

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

注意分配失敗的情況

bool initList_H(LinkList &l){
    l=(LNode *)malloc(sizeof(LNode));
    if(l==NULL){ //分配失敗
        return false;
    }
    l->next=NULL;
    return true;
}

按位序刪除

先判斷位序異常的情況

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

注意釋放空間

bool deleteListByOrder_H(LinkList &l,int num,int &e){
    if(num<1){
        return false;
    }
    int i=0;
    //指向頭節(jié)點(diǎn)的p指針,用來后移
    LNode *p=l;
    //找到第num-1個(gè)
    while(i<num-1&&p!=NULL){
        p=p->next;
        i++;
    }
    //沒有那么多節(jié)點(diǎn)
    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;
}

按位序插入

bool insertListByOrder_H(LinkList &l,int num,int e){
   /*  頭節(jié)點(diǎn)不插入值 所以插入位置只能從1開始
        if (num==0){
        l->data=e;
    } */
    if(num<1){
        cout<<"位序有誤"<<endl;
        return false;
    }
    /* 第一個(gè)節(jié)點(diǎn) 應(yīng)該位序是0
    int i=1;
    LNode *p=l; */
    int i=0;
    LNode *p =l;
    //找到第i-1個(gè)位置,好來插入 
    //插入第一個(gè)節(jié)點(diǎn) 可以直接找到第0個(gè)位置
    while(i<(num-1)&&p!=NULL){
        p=p->next;
        i++;
    }
    //注意別忘了這個(gè) 插入了不存在的位置 num大于長(zhǎng)度
    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<<"個(gè)值是:"<<p->data<<endl;
        p=p->next;

    }
}

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

演示代碼

 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<<"邊界測(cè)試,返回第0個(gè)位置"<<endl;
    if(getValueByOrder_H(l,0)){
        //返回的是頭節(jié)點(diǎn)無意義的值
        cout<<getValueByOrder_H(l,0)->data<<endl;
    }
    else{
        cout<<"查找失敗"<<endl;
    }
    cout<<"邊界測(cè)試,返回第8個(gè)位置"<<endl;
    if(getValueByOrder_H(l,8)){
        cout<<getValueByOrder_H(l,8)->data<<endl;
    }
    else{
        cout<<"查找失敗"<<endl;
    }
    cout<<"正常測(cè)試,返回第2個(gè)位置"<<endl;
    if(!getValueByOrder_H(l,2)){
        cout<<getValueByOrder_H(l,2)->data<<endl;
    }
    int n=2;
    if(getValue(l,n)){
        cout<<"找到了值為"<<n<<"的數(shù)"<<endl;
    }
    cout<<"表長(zhǎng)為"<<length_H(l)<<endl;
    if(!isEmpty_H(l)){
        cout<<"表長(zhǎng)不空"<<endl;
    }

結(jié)果

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

按位序查找

位序?yàn)?的時(shí)候,返回頭節(jié)點(diǎn)

LNode* getValueByOrder_H(LinkList &l,int num){
    if(num<0){
        return NULL;
    }
    int i=0;
    LNode *p =l;
    //如果num=0,不滿足0<0,返回頭節(jié)點(diǎn)
    //如果num 很大,不滿足p!=NULL;返回空節(jié)點(diǎn)
    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);
}

求表長(zhǎng)

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

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

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

演示代碼

LinkList l;
    if(initList_H(l)){
        cout<<"初始化成功"<<endl;
    }
    insertNextNode(l,1);
    cout<<"先查找值為1的節(jié)點(diǎn),再后插"<<endl;
    insertNextNode(getValue(l,1),2);
    printList_H(l);
    cout<<"先查找值為0的節(jié)點(diǎn),再前插"<<endl;
    //為空,不進(jìn)行
    if(getValue(l,0)){
         insertNextNode(getValue(l,0),-1);
    }
    cout<<"先查找值為1的節(jié)點(diǎn),再前插0"<<endl;
    insertPriorNode(getValue(l,1),0);
    printList_H(l);
    int e;
    cout<<"指定節(jié)點(diǎn),值為0的刪除"<<endl;
    deleteNode(getValue(l,0),e);
    printList_H(l);
    cout<<"刪除最后一個(gè)節(jié)點(diǎn)"<<endl;
    deleteNode(getValue(l,2),e);
    //方法失效
    printList_H(l);

結(jié)果

初始化成功
先查找值為1的節(jié)點(diǎn),再后插
單鏈表的第1個(gè)值是:1
單鏈表的第2個(gè)值是:2
先查找值為0的節(jié)點(diǎn),再前插
先查找值為1的節(jié)點(diǎn),再前插0
單鏈表的第1個(gè)值是:0
單鏈表的第2個(gè)值是:1
單鏈表的第3個(gè)值是:2
指定節(jié)點(diǎn),值為0的刪除
單鏈表的第1個(gè)值是:1
單鏈表的第2個(gè)值是:2
刪除最后一個(gè)節(jié)點(diǎn)
單鏈表的第1個(gè)值是:1
單鏈表的第2個(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)的按位序插入,刪除

和第一的測(cè)試代碼差不多,只不過變成了封裝后的,運(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_H(l);
    printList_H(l);
    LinkList l2;
    cout<<"頭插法生成單鏈表,手動(dòng)輸入 ,輸入999結(jié)束"<<endl;
    headInsertList_H(l2);
    printList_H(l2);
    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
頭插法生成單鏈表,逆序
單鏈表的第1個(gè)值是:1
單鏈表的第2個(gè)值是:2
單鏈表的第3個(gè)值是:3

尾插法

/*
每次取數(shù)據(jù),設(shè)置一個(gè)長(zhǎng)度,然后遍歷插入到最后,是o(n)
不如設(shè)置一個(gè)尾指針,每次在尾指針之后插入
利用后插操作 
 */
LinkList tailInsertList_H(LinkList &l){
    l=(LinkList)malloc(sizeof(LNode));
    LNode *p ,*q=l;
    int a;
    scanf("%d",&a);
    while(a!=999){
        //插入的節(jié)點(diǎn),由p指示
        p=(LinkList)malloc(sizeof(LNode));
        p->data=a;
        //尾節(jié)點(diǎn) 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;
}

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

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){
        //新節(jié)點(diǎn)r
        r=(LNode*)malloc(sizeof(LNode));
        r->data=p->data;
        p=p->next;
        r->next=q->next;
        q->next=r;
    }
    return q;
}

報(bào)錯(cuò)

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

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

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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

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

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