資料結構-連結清單基本操作

代碼寫的比較水，為了解決超過表長的資料輸進去發生的空指針問題，代碼備援太多了，但是基本功能都實作了。雖然我之前學過資料結構，但是其實跟沒學過一樣，算得上是重新學習了一遍。

代碼

#include <iostream>
#include <cstdlib>
using namespace std;

typedef struct LNode{
    int data;
    struct LNode * next;
}*LinkList;

//求連結清單表長
int getLength(LinkList L){
    LinkList p;
    p = L->next;
    int i = 1;
    while(p){
        i++;
        p = p->next;
    }
    return i - 1;
}

//頭插法建立單連結清單,也就是倒序輸出,但是我更喜歡尾插法，因為他是按照順序來的，
//是以這裡隻是把頭插的方法寫了出來,并沒有調用
LinkList List_HeadInsert(LinkList &L){
    LinkList s;
    int x;
    L = (LinkList)malloc (sizeof(struct LNode));
    L->next = NULL;
    cout << "請輸入要插入的資料,輸入-9999結束輸入：";
    cin >> x;
    while(x != -9999){
        s = (LinkList)malloc(sizeof (struct LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        cin >> x;
    }
    return L;
}

//尾插法建立連結清單,即正序輸出
LinkList List_TailInsert(LinkList &L){
    int x;
    L = (LinkList)malloc(sizeof(struct LNode));
    LinkList cur,r = L;//這裡面的r代表連結清單的尾結點，且必須始終保證他是尾結點，友善結點s接傳入連結表
    cout << "請輸入要插傳入連結表中的元素，輸入-9999結束輸入：";
    cin >> x;
    while(x != -9999){
        cur = (LinkList)malloc(sizeof(struct LNode));
        cur->data = x;
        r->next = cur;
        r = cur;
        cin >> x;
    }
    r->next = NULL;
    return L;
}

//按值查找傳回對應序号位置(連結清單中沒有重複的元素)
int byValue_getIndex(LinkList L,int e){
    int num = 1;
    LinkList p;

    p = L->next;
    while((p->data != e) && (p != NULL)){
        num++;
        if(p->next != NULL)
            p = p->next;
        else
            return 0;
    }
    return num;
}

//按位置查找對應元素值
LinkList byIndex_getValue(LinkList L,int n){
    int length = getLength(L);
    //cout << length;
    int i = 1;
    if(n < 1 || n > length){
        cout << "您輸入的資料不合法，超過表長或者小于1：" << endl;
        return NULL;
    }else{
        LinkList p;
        p = L->next;
        //這裡如果不先判斷n跟表長length的關系會出現空指針異常，也就是當你輸入一個超過表長的資料的時候
        while(p && (i < n)){
            p = p->next;
            i++;
        }
        return p;
    }


}

//按照給定位置後插結點
LinkList byIndex_behindInsert(LinkList L,int j,int x){
    LinkList p = byIndex_getValue(L,j);
    if(p != NULL){
        LinkList s;
        s = (LinkList)malloc(sizeof(struct LNode));
        s->data = x;
        s->next = p->next;
        p->next = s;
        return L;
    }else return NULL;

}

//按給定位置前插結點
LinkList byIndex_beforeInsert(LinkList L,int j,int x){
    int temp;
    if(j == 1){
        LinkList s;
        s = (LinkList)malloc(sizeof(struct LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        return L;
    }else{
        LinkList p = byIndex_getValue(L,j);
        if(p != NULL){
            LinkList s;
            s = (LinkList)malloc(sizeof(struct LNode));
            s->data = x;
            s->next = p->next;
            p->next = s;
            temp = s->data;
            s->data = p->data;
            p->data = temp;
            return L;
        }else return NULL;
    }

}

//按值删除結點（假設表中沒有重複結點）
LinkList deleteNode(LinkList L,int x){
    LinkList p;
    LinkList q = L;
    p = L->next;
    while(p->data != x){
        if(p->next == NULL){
            cout << "查找失敗，連結清單中沒有對應元素" << endl;
            return NULL;
        }else{
            p = p->next;
            q = q->next;
        }
    }
    q->next = p->next;
    free(p);
    return L;
}

//按位置删除結點
LinkList deleteNode_index(LinkList L,int n){
    if(n < 1){
        cout << "您輸入的資料不合法，請輸入一個大于1的數！" << endl;
        return NULL;
    }
    int i = 1;
    LinkList p,q;
    q = L;
    p = L->next;
    while(p != NULL && i < n){
        if(p->next != NULL){
            p = p->next;
            i++;
            q = q->next;
        }else{
            cout << "您輸入的資料不合法,已經超過表長範圍！" << endl;
            return NULL;
        }
    }
    cout << "您删除的結點是：" << p->data << endl;
    q->next = p->next;
    free(p);
    return L;
}

//按位置更改元素
LinkList byLocation_changeValue(LinkList L,int n,int e){
    if(n < 1){
        cout << "您輸入的資料不合法，請輸入一個大于1的數！" << endl;
        return NULL;
    }
    int i = 1;
    LinkList p;
    p = L->next;
    while(i < n && p != NULL){
        if(p->next != NULL){
            p = p->next;
            i++;
        }else{
            cout << "您輸入的資料不合法，輸入的資料已經大于表長！" << endl;
            return NULL;
        }
    }
    p->data = e;
    return L;
}

//按值更改元素
LinkList byValue_changeValue(LinkList L,int e,int changeE){
    LinkList p;
    p = L->next;
    while(p->data != e){
        if(p->next != NULL) p = p->next;
        else {
            cout << "您要更改的值在連結清單中不存在！" << endl;
            return NULL;
        }
    }
    p->data = changeE;
    return L;
}

//列印連結清單
void print(LinkList L){
    LinkList p = L->next;
    while(p != NULL){
        int x = p->data;
        cout << x << " ";
        p = p->next;
    }
    cout << endl;
}
int main()
{
    LinkList L;
    LinkList b;
    int sel;
    int byValue_search;
    int getIndex;
    int small_sel;
    int search_index;
    int behindInsertIndex,behindInsertValue;
    int beforeInsertIndex,beforeInsertValue;
    int deleteValue;
    int deleteIndex;
    int changeIndex,index_changeValue;
    int primerValue,value_choiceValue;
    cout << "功能如下："<< endl;
    cout << "--------1.尾插法建立連結清單--------" << endl;
    cout << "--------2.列印連結清單--------" << endl;
    cout << "--------3.按值查找元素，傳回位置序号--------" << endl;
    cout << "--------4.按位置查找元素，傳回值--------" << endl;
    cout << "--------5.按位置後插元素--------" << endl;
    cout << "--------6.按位置前插元素--------" << endl;
    cout << "--------7.按值删除結點--------" << endl;
    cout << "--------8.按位置删除結點--------" << endl;
    cout << "--------9.按位置更改元素--------" << endl;
    cout << "--------10.按值更改元素--------" << endl;

    while(true){
        cout << "請輸入選擇的功能：";
        cin >> sel;
        switch(sel){
        case 1:
            List_TailInsert(L);
            break;
        case 2:
            print(L);
            break;
        case 3:
            cout << "請輸入要查找的值：";
            cin >> byValue_search;
            getIndex = byValue_getIndex(L,byValue_search);
            if(getIndex == 0){
                cout << "您要查找的值不在連結清單内！" << endl;
            }else{
                cout << "值" << byValue_search << "在第" << getIndex << "位" << endl;
            }
            break;
        case 4:
            cout << "請輸入要查找的位置索引：";
            cin >> search_index;
            b = byIndex_getValue(L,search_index);
            if(b)
                cout << search_index << "位置對應的元素為：" << b->data <<endl;
            break;
        case 5:
            cout << "請輸入要插入元素的位置和插入的元素：";
            cin >> behindInsertIndex;
            cin >> behindInsertValue;
            byIndex_behindInsert(L,behindInsertIndex,behindInsertValue);
            break;
        case 6:
            cout << "請輸入要插入元素的位置和插入的元素：";
            cin >> beforeInsertIndex;
            cin >> beforeInsertValue;
            byIndex_beforeInsert(L,beforeInsertIndex,beforeInsertValue);
            break;
        case 7:
            cout <<"請輸入要删除結點的值：";
            cin >> deleteValue;
            deleteNode(L,deleteValue);
            break;
        case 8:
            cout << "請輸入要删除結點的位置：";
            cin >> deleteIndex;
            deleteNode_index(L,deleteIndex);
            break;
        case 9:
            cout << "請輸入您要更改的位置和元素：";
            cin >> changeIndex >> index_changeValue;
            byLocation_changeValue(L,changeIndex,index_changeValue);
            break;
        case 10:
            cout << "請輸入原本的值，和您想要更改的值：";
            cin >> primerValue >> value_choiceValue;
            byValue_changeValue(L,primerValue,value_choiceValue);
            break;
        }
    }
    return 0;
}

資料結構-連結清單基本操作

繼續閱讀

2021-08-13c++——類之操作符重載

[轉]ISUP信令的IAM消息詳細内容

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

Linux裝置模型（中）之上層容器