国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<label id="eobfo"><strong id="eobfo"></strong></label>

【考研復習】24王道數據結構課后習題代碼｜2.3線性表的鏈式表示

2年前作者：Lydia.na分類：Toy博客閱讀(98)違法舉報

這篇具有很好參考價值的文章主要介紹了【考研復習】24王道數據結構課后習題代碼｜2.3線性表的鏈式表示。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

總結

刪除結點：1、2、4
就地逆置：5、
合并鏈表
分解鏈表：10、11、
去除重復元素：12、
并集：14、15
循環(huán)鏈表：17、18、19、20
頭插法、尾插法重點基礎必掌握。
判斷是否有環(huán)：21

01 遞歸刪除結點

用函數遞歸調用刪除結點。

void deletex(linklist &L,int x){
    if(L==NULL) return;
    lnode *p;
    if(L->data==x){
        p=L;
        L=L->next;
        free(p);
        deletex(L,x);
    }
    else deletex(L->next,x);
}

02 刪除結點

注意刪除結點的時候可能斷鏈。

void deletex2(linklist &L,int x){
    lnode *p=L->next,*pre=L,*q;
    while(p){
        if(p->data==x){
            q=p;
            p=p->next;
            pre->next=p;
            free(q);
        }else{
            pre=p;
            p=p->next;
        }
    }
}

03 反向輸出

利用函數調用的特性反向輸出。

void r_print(linklist L){
    if(L!=NULL)
    {
        r_print(L->next);
        cout<<(L->data)<<" ";
    }
    else return;
}
void r_ignore_node(linklist L){
    if(L->next!=NULL){
        r_print(L->next);
    }
}

04 刪除最小值

設置保留最小值的指針和其前驅
每次更新最小值

void delete_min(linklist L){
    lnode *p=L->next,*pre=L;
    lnode *minp=p,*minpre=pre;
    while(p){
        if(p->data<minp->data){
            minp=p;
            minpre=pre;
        }else{
            p=p->next;
            pre=pre->next;
        }
    }
    minpre->next=minp->next; //刪除最小值結點
    free(minp);
}

05 逆置

很重要的基礎：頭插法

void head(linklist &L){
    lnode *p=L->next,*r;
    L->next=NULL;
    while(p){
        r=p->next;      //記錄下一結點
        p->next=L->next;
        L->next=p;
        p=r;
    }
}

06 鏈表遞增排序

使用插入排序的思想，將頭置空之后，掃描最小元素，然后使用尾插法插入頭中。

void insert_sort(linklist &L){
    lnode *p=L->next,*r=p->next,*pre;
    p->next=NULL;
    p=r;
    while(p){
        r=p->next;
        pre=L;
        while(pre->next!=NULL&&pre->next->data<p->data){
            pre=pre->next;
        }
        p->next=pre->next;
        pre->next=p;
        p=r;
    }
}

07 刪除區(qū)間值

見2題的刪除代碼，改下if語句即可。

void delete_x_m_n(linklist &L,int m, int n){
    lnode *p=L->next,*pre=L,*q;
    while(p){
        if(p->data<n&&p->data>m){
            q=p;
            p=p->next;
            pre->next=p;
            free(q);
        }else{
            pre=p;
            p=p->next;
        }
    }
}

08 找公共結點

linklist find_same_dot(linklist L1,linklist L2){
    linklist longlist, shortlist;
    int dist=0;
    int len1=length(L1),len2=length(L2);
    if(len1>len2){
        longlist=L1;
        shortlist=L2;
        dist=len1-len2;
    }else{
        longlist=L2;
        shortlist=L1;
        dist=len2-len1;
    }
    while(dist--) longlist=longlist->next;
    while(longlist){
        if(longlist->data==shortlist->data&&longlist->next->data==shortlist->next->data)
            return longlist;
        else{
            longlist=longlist->next;
            shortlist=shortlist->next;
        }
    }
    return NULL;
}

09 增序輸出鏈表

見6題

void min_output(linklist L){
    while(L->next){
        lnode *pre=L,*p=L->next;
        lnode *minpre=pre, *minp=p;
        while(p){
            if(p->data<minp->data){
                minp=p;
                minpre=pre;
            }
            p=p->next;
            pre=pre->next;
        }
        cout<<minp->data<<" ";
        minpre->next=minp->next;
        free(minp);
    }
}

10 拆分鏈表–尾插

第一種方法是在A中直接刪除。

linklist split_1_1(linklist &A){
    linklist B = (linklist)malloc(sizeof(lnode));
    B->next=NULL;
    lnode *p=A->next,*ra=A;
    lnode *rb=B,*q;
    while(p){
        //向后移一個
        ra=p;
        p=p->next;
        //從A中刪除結點
        q=p;
        ra->next=p->next;
        p=p->next;
        //利用尾插法將結點插入B中
        rb->next=q;
        rb=rb->next;
    }
    ra->next=NULL;
    rb->next=NULL;
    return B;
}

第二種方法是把A的頭拿下來，再選最小的排在A后。=尾插==

linklist split_1_2(linklist &A){
    linklist B = (linklist)malloc(sizeof(lnode));
    B->next=NULL;
    lnode *p=A->next,*ra=A;
    lnode *rb=B;
    //把表頭摘下來
    A->next=NULL;
    while(p){
        //結點給A
        ra->next=p;
        ra=ra->next;
        p=p->next;
        //結點給B
        rb->next=p;
        rb=rb->next;
        p=p->next;
    }
    ra->next=NULL;
    rb->next=NULL;
    return B;
}

11 拆分鏈表–頭插

第一種方法同上

linklist split_1_1(linklist &A){
    linklist B = (linklist)malloc(sizeof(lnode));
    B->next=NULL;
    lnode *p=A->next,*ra=A;
    lnode *rb=B,*q;
    while(p){
        //向后移一個
        ra=p;
        p=p->next;
        //從A中刪除結點
        q=p;
        ra->next=p->next;
        p=p->next;
        //利用頭插法將結點插入B中
        q=p->next;
        p->next=rb->next;
        rb->next=p;
        p=q;
    }
    ra->next=NULL;
    return B;
}

第二種方法同上

linklist split_2_1(linklist &A){
    linklist B = (linklist)malloc(sizeof(lnode));
    B->next=NULL;
    lnode *p=A->next,*ra=A;
    lnode *rb=B,*q;
    //把表頭摘下來
    A->next=NULL;
    while(p){
        //結點給A
        ra->next=p;
        ra=ra->next;
        p=p->next;
        //結點給B
        if(p){
            q=p->next;
            p->next=rb->next;
            rb->next=p;
            p=q;
        }
    }
    ra->next=NULL;
    //b是頭插法所以最后指向是為NULL
    return B;
}

12 刪除相同元素

簡單代碼，只不過要注意的p是要刪除結點的前一個結點，判斷的時候別判斷錯了。

void del_same(linklist &L){
    lnode *p=L->next,*q;
    if(p==NULL) return;
    while(p->next){
        q=p->next;
        if(p->data==q->data){
            p->next=q->next;
            free(q);
        }else{
            p=p->next;
        }
    }
}

13 合并鏈表

void merge(linklist &L1,linklist &L2)
{
    lnode *p1=L1->next,*p2=L2->next,*r;
    L1->next=NULL;
    while(p1&&p2)
    {
        if(p1->data<=p2->data)
        {
            r=p1->next;
            p1->next=L1->next;
            L1->next=p1;
            p1=r;
        }
        else
        {
            r=p2->next;
            p2->next=L1->next;
            L1->next=p2;
            p2=r;
        }
    }
    if(p1) p2=p1;
    while(p2)
    {
        r=p2->next;
        p2->next=L1->next;
        L1->next=p2;
        p2=r;
    }
    free(L2);
}

14 生成含有公共元素的鏈表C

兩個鏈表分別遍歷，比較值頭插入C中

linklist merge_same(linklist &A,linklist &B){
    lnode *p=A->next,*q=B->next;
    lnode *r,*s;
    linklist C = (linklist)malloc(sizeof(lnode));
    r=C;
    while(p&&q){
        if(p->data<q->data){
            p=p->next;
        }
        else if(p->data>q->data){
            q=q->next;
        }else{
            s=(lnode *)malloc(sizeof(lnode *));
            s->data=p->data;
            r->next=s;
            r=r->next;
            p=p->next;
            q=q->next;
        }
    }
    r->next=NULL;
    return C;
}

15 求并集

值不相同時分別刪除A和B中的值
相同時刪除B中的值
基礎就是刪除代碼

void intersection(linklist &A,linklist &B){
    lnode *p=A->next,*q=B->next;
    lnode *r=A,*temp;
    while(p&&q){
        if(p->data<q->data){
            temp=p;
            p=p->next;
            free(temp);
        }else if(p->data>q->data){
            temp=q;
            q=q->next;
            free(temp);
        }else{
            //相等的時候保留A中相同元素
            r->next=p;
            r=r->next;
            p=p->next;
            //刪除B中相同的元素
            temp=q;
            q=q->next;
            free(temp);
        }
    }
    while(p){
        temp=p;
        p=p->next;
        free(temp);
    }
    while(q){
        temp=q;
        q=q->next;
        free(temp);
    }
    r->next=NULL;
}

16 判斷子序列

樸素kmp，也有所說bf的

bool simple_kmp(linklist &A,linklist &B){
    lnode *p=A->next,*q=B->next,*r=A->next;
    while(p&&q){
        if(p->data!=q->data){
            r=r->next;
            p=r;
            q=A->next;
        }else{
            p=p->next;
            q=q->next;
        }
    }
    if(q) return false;
    else return true;
}

17 判斷循環(huán)鏈表是否對稱

循環(huán)鏈表就方便了，能找前驅和后繼，兩個指針同時移動判斷值即可。

bool symmetry(linklist L)
{
    lnode *p=L->next,*q=L->prior;
    while(p!=q&&q->next!=p)
    {
        if(p->data==q->data)
        {
            p=p->next;
            q=q->prior;
        }
        else return false;
    }
    return true;
}

18 兩個循環(huán)鏈表鏈接

注意頭尾即可

void add(linklist &h1,linklist &h2)
{
    lnode *p=h1->next,*q=h2->next;
    while(p->next!=h1)
    {
        p=p->next;
    }
    while(q->next!=h2){
        q=q->next;
    }
    p->next=h2->next;//初始化的鏈表帶頭結點，若不帶h2即可
    q->next=h1;
}

19 找最小結點并刪除

遍歷鏈表每次輸出最小結點然后刪除即可
相同代碼見9題

void find_min(linklist &L){
    while(L->next!=L){
        lnode *pre=L,*p=L->next;
        lnode *minpre=pre, *minp=p;
        while(p!=L){
            if(p->data<minp->data){
                minp=p;
                minpre=pre;
            }
            p=p->next;
            pre=pre->next;
        }
        cout<<minp->data<<" ";
        minpre->next=minp->next;
        free(minp);
    }
    free(L);
}

21 判斷單鏈表是否有環(huán)

兩步走總能相遇，按照這個作為遇到的條件找相遇點和入環(huán)結點。
25題也是兩步走。

lnode* findd(lnode *L)
{
    lnode *f=L,*s=L;
    while(s!=NULL&&f->next!=NULL)
    {
        s=s->next;
        f=f->next->next;
        if(s->data==f->data) break; //可以直接設置指針，但是我初始化的有單鏈表為int a[15]={1,2,3,4,5,6,7,8,9,4,5,6,7,8,9};故用這種方法
    }
    if(s==NULL||f->next==NULL) return NULL;
    lnode *p=L,*q=s;
    while(p->data!=q->data)
    {
        p=p->next;
        q=q->next;
    }
    return p;
}

22 【2009真題】找倒數第k個元素

相當于用長度為k的尺子比著找，最右端到尾部的時候，最左端就是倒數第k個元素。

int findk(linklist &L, int k){
    lnode *p=L,*q=L;
    int count=0;
    while(p){
        if(count<k) count++;
        else q=q->next;
        p=p->next;
    }
    if(count<k) return 0;
    else cout<<"kth to last position: "<<q->data;
    return 1;
}

23 【2012真題】相同后綴找起始位置

把尾部排齊：兩個指針遍歷鏈表，長度相同時找到相同時尾部對齊了
排齊之后遍歷兩個鏈表找第一個不相同的位置，該位置的下一個位置就是相同后綴的位置

typedef struct lnode{
    int data;
    struct lnode *next;
}lnode,*linklist;
lnode * find_addr(linklist str1, linklist str2){
    lnode *p,*q;
    int m=length(str1);
    int n=length(str1);
    for(p=str1;m>n;m--) p=p->next;
    for(q=str2;m<n;n--) q=q->next;
    while (p->next!=NULL&&q->next!=NULL)
    {
        p=p->next;
        q=q->next;
    }
    return p->next;
}

24 【2015真題】刪除絕對值相同

要求時間復雜度盡可能高??空間換時間文章來源地址http://www.zghlxwxcb.cn/news/detail-635119.html

數組存查找狀態(tài)：0表示絕對值未找到，1表示找到，第二次找到的同時刪除該結點
注意動態(tài)分配數組的使用（靜態(tài)數組試了試內存超出，不知道是不是這個問題）

void same(linklist &L,int n)
{
    lnode *p=L;
    int *q;
    q=(int *)malloc(sizeof(int)*(n+1));
    for(int i=0;i<n+1;i++) *(q+i)=0;
    int s;
    lnode *f;
    while(p->next!=NULL)
    {
        s=abs(p->next->data);
        if(*(q+s)==0) 
        {
            *(q+s)=1;
            p=p->next;
        }
        else
        {
            f=p->next;
            p->next=f->next;
            free(f);
        }
    }
    free(q);
}

25 【2019真題】重新排列鏈表

兩步走找中間結點
逆置后邊鏈表：使用頭插法
看成兩個鏈表進行插入
21也是兩步走

void change(linklist &L){
    lnode *p,*q,*r,*s;
    p=q=L;
    while (q->next)
    {
        p=p->next;
        q=q->next;
        if(q->next) q=q->next;
    }
    q=p->next;  //p現(xiàn)在在中間結點
    p->next=NULL;  //把后半段摘下來，逆置之后分別遍歷兩個鏈表插入指定位置
    while (q)  //頭插法實現(xiàn)原地逆置
    {
        r=q->next;  //暫存后繼結點
        q->next=p->next;  //將q結點放在頭結點p之后
        p->next=q;
        q=r;
    }
    s=L->next;  //插入點
    q=p->next;  //后半段數據點
    p->next=NULL;  
    while(q){
        r=q->next;
        q->next=s->next;
        s->next=q;
        s=q->next;
        q=r;
    }
}

到了這里，關于【考研復習】24王道數據結構課后習題代碼｜2.3線性表的鏈式表示的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！

本文來自互聯(lián)網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。如若轉載，請注明出處：如若內容造成侵權/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經查實，立即刪除！

分享到：

領支付寶紅包贊助服務器費用

【數據結構】24王道考研筆記——樹與二叉樹
樹是n個結點的有限集合，n=0時，稱為空樹。非空樹滿足：除了根節(jié)點外，任何一個結點都有且僅有一個前驅結點的層次（深度）：從上往下數結點的高度：從下往上數樹的高度（深度）：總共有多少層結點的度：有幾個孩子（分支）樹的度：各節(jié)點的度的最大值森林：
2024年02月13日
瀏覽(28)
王道考研數據結構——鏈表
找到頭節(jié)點就相當于找到了整個鏈表 Linklist Lnode*是一個東西大部分使用的帶頭結點，比較方便！帶頭結點只維護指針域，不維護數據域找前驅節(jié)點+插入節(jié)點(可以單獨封裝成一個函數)? 如果不帶頭節(jié)點的話，那么插入和刪除頭節(jié)點的話都需要特殊處理，即重新修改頭指針的
2024年02月16日
瀏覽(91)
【王道考研】王道數據結構與算法詳細筆記（全）
目錄第一章數據結構緒論? 1.1 數據結構的基本概念 1.2 數據結構的三要素 1.2.1. 數據的邏輯結構 1.2.2. 數據的存儲結構（物理結構） 1.2.3. 數據的運算 1.2.4. 數據類型和抽線數據類型 1.3 算法的基本概念 1.4?算法的時間復雜度 1.5?算法的空間復雜度第二章線性表 2.1 線性表的定
2024年02月08日
瀏覽(29)
王道考研數據結構--2.單鏈表
1.前言 2.難點 2.1c和c++的引用轉換 2.2引入頭結點的好處 2.3頭插法和尾插法 3.代碼段 3.1C語言自定義bool操作 3.2單鏈表結構體定義 3.3創(chuàng)建新節(jié)點 3.4頭插法和尾插法 3.5查找 3.6按位序插入 3.7后插和前插 3.8刪除 3.9求表長 3.10遍歷輸出單鏈表 4.完整代碼日期：2023.6.21 書籍：2024年數據
2024年02月09日
瀏覽(26)
王道考研數據結構--4.2循環(huán)隊列
目錄前言? 1.循環(huán)隊列的定義 2.循環(huán)隊列的結構 3.循環(huán)隊列的操作 3.1定義循環(huán)隊列 3.2初始化 3.3入隊 3.4出隊 3.5遍歷，求表長 3.6清空銷毀 4.完整代碼日期：2023.7.25 書籍：2024年數據結構考研復習指導（王道考研系列）內容：實現(xiàn)順序隊列的基本實現(xiàn)，主要功能如下： 1.循環(huán)隊
2024年02月15日
瀏覽(29)
數據結構筆記（王道考研）第一章：緒論
大部分內容基于中國大學MOOC的2021考研數據結構課程所做的筆記，該課屬于付費課程（不過盜版網盤資源也不難找。。。）。后續(xù)又根據23年考研的大綱對內容做了一些調整，將二叉排序樹和平衡二叉樹的內容挪到了查找一章，并增加了并查集、平衡二叉樹的刪除、紅黑樹的內
2024年02月14日
瀏覽(25)
【數據結構】| 王道考研——樹的前世今生
根據王道考研數據結構總結出的知識點，以下是文章整體大綱： 1.1 概念樹是n個結點的有限集合，n = 0時稱為空樹，這是一種特殊情況。任意一棵非空樹中應滿足：有且僅有一個特定的稱為根的節(jié)點當n1時，其余結點可分為m個互不相交的有限集合T1、T2、T3……Tm；每個集合又
2024年02月15日
瀏覽(25)
【2023王道數據結構】王道數據結構課后代碼題匯總答案C、C++代碼實現(xiàn)完整版大全（可直接運行）
本文章為 2023王道數據結構專欄導航貼，正在積極更新中！本專欄文章將王道一些課后算法設計題目的全部實現(xiàn)（答案解析全部都是偽碼或者函數的部分實現(xiàn)，不可調試運行），同時包含各個章節(jié)的經典算法數據結構的實現(xiàn)以及一些經典的算法本專欄使用人群：復習數據
2024年02月16日
瀏覽(20)
一篇學完：王道考研408數據結構（全）
PDF版本附在 ?lengyueling.cn?對應文章結尾，歡迎下載訪問交流數據結構在學什么如何用程序代碼把現(xiàn)實世界的問題信息化如何用計算機高效地處理這些信息從而創(chuàng)造價值數據結構的基本概念什么是數據：數據是信息的載體，是描述客觀事物屬性的數、字符及所有能輸入到
2023年04月08日
瀏覽(24)
王道考研數據結構第五章知識點
5.1.1 樹的定義和基本術語 ? 祖先節(jié)點：(對于你來說),父親和爺爺都是祖先節(jié)點子孫節(jié)點：對于父親來說，父親下面所有的節(jié)點都叫子孫節(jié)點雙親節(jié)點(父節(jié)點)：一個節(jié)點的直接前驅就是它的父節(jié)點? 兄弟節(jié)點：例如二叔，三叔都是父親的兄弟節(jié)點堂兄弟節(jié)點：對于你來說，
2024年02月15日
瀏覽(30)

<kbd id="rryi8"><pre id="rryi8"></pre></kbd>

<mark id="rryi8"><em id="rryi8"><kbd id="rryi8"></kbd></em></mark>

<ruby id="rryi8"></ruby>