25考研计算机机试复试-王道《数据结构》课后代码题C语言实现（第二章）

POLar_cube

1037人浏览 · 2025-03-08 22:20:02

POLar_cube · 2025-03-08 22:20:02 发布

第二章2.3链表部分的课后代码题，题目难度适中，有助于计算机复试机试学习和数据结构小白学习，希望本文能帮到你。（部分题目代码可能与25版王道数据结构答案不一致）

一窝Q~

（另外这里不展示原题干，只做简单叙述）

1. 删除指定含指定节点值的节点（这种节点不唯一）

代码如下：

#include <stdio.h>
#include <stdlib.h>

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

//初始化链表
LinkList initList(){
    LinkList L = (LinkList)malloc(sizeof(LNode));
    //头节点的数据域存放链表的长度
    L->data = 0;
    L->next = NULL;
    return L;
}

//尾插
LinkList tailInsert(LinkList L){
    LNode *r = L;
    int data;
    //以输入-1作为结束标志
    while(scanf("%d",&data)==1 && data!=-1){
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        newNode->data = data;
        newNode->next = NULL;
        r->next = newNode;
        r = newNode;
        L->data+=1;
    }
    return L;
}

//删除值为x的节点
LinkList deleteNode(LinkList L,int x){
    LNode *p = L,*r = p->next;
    while(r){
        if(r->data == x){
            p->next = r->next;
            free(r);
            r = p->next;
        }else{
            p = r;
            r = r->next;
        }
    }
    return L;
}

//打印
void printList(LinkList L){
    LNode *p = L->next;
    while(p){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

int main()
{
    int x;
    LinkList L = initList();
    L = tailInsert(L);
    printList(L);
    scanf("%d",&x);
    L = deleteNode(L,x);
    printList(L);
    return 0;
}

2.删除一个最小值结点

//删除最小值
LinkList deleteMinNode(LinkList L){
    int min = 0x3f3f3f3f;
    LNode *p = L, *r = p->next;
    LNode *minNode = L->next, *minpre = L;
    while(r){
        if(r->data < min){
            //更新最小值节点位置
            min = r->data;
            minpre = p;
            minNode = r;
            //遍历指针后滚
            p = r;
            r = r->next;
        }else{
            //遍历指针直接后滚
            p = r;
            r = r->next;
        }
    }
    minpre->next = minNode->next;
    free(minNode);
    return L;
}

3.链表就地逆置 ❤❤❤(必做经典题)

LinkList reverseList(LinkList L){
    // 最常见的头插法逆置
    LNode *p = L->next,*r = NULL;
    L->next = NULL;
    while(p!=NULL){
        r = p->next;
        p->next = L->next;
        L->next = p;
        p = r;
    }
    return L;
}

这里更推荐王道书上的另一种解法

LinkList reverseList(LinkList L){
    //王道书上的另一种三指针法
    LNode *pre,*p = L->next,*r = p->next;
    p->next = NULL;
    while(r){
        pre = p;
        p = r;
        r = r->next;
        p->next = pre;
    }
    //p是r的前驱，r此时指向null
    L->next = p;
    return L;
}

4.链表中元素无序，删除值介于给定的两个数之间的结点

LinkList deleteNode(LinkList L,int min, int max){
    LNode *p = L,*r = p->next;
    while(r){
        if(r->data > min && r->data < max){
            p->next = r->next;
            free(r);
            r = p->next;
        }else{
            p = r;
            r = r->next;
        }
    }
    return L;
}

5.找出两个链表的公共结点(这里我们把这些公共结点找出来并且链接起来，最后输出公共结点链Lc)

#include <stdio.h>
#include <stdlib.h>

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

//初始化链表
LinkList initList(){
    LinkList L = (LinkList)malloc(sizeof(LNode));
    //头节点的数据域存放链表的长度
    L->data = 0;
    L->next = NULL;
    return L;
}

//尾插
LinkList tailInsert(LinkList L){
    LNode *r = L;
    int data;
    //以输入-1作为结束标志
    while(scanf("%d",&data)==1 && data!=-1){
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        newNode->data = data;
        newNode->next = NULL;
        r->next = newNode;
        r = newNode;
        L->data+=1;
    }
    return L;
}

//注意这里是找公共结点（即结点地址相同）而不是值相同的结点
LinkList mergeList(LinkList La,LinkList Lb){
    int len_La = La->data,len_Lb = Lb->data;
    LNode *p = La->next,*q = Lb->next;
    //较长的先遍历
    if(len_La > len_Lb){
        int step= len_La-len_Lb;
        while(step != 0){
            p = p->next;
            step --;
        }
    }else if(len_La < len_Lb){
        int step= len_Lb-len_La;
        while(step != 0){
            q = q->next;
            step --;
        }
    }
    while(p&&q){
        if(p==q){
            return p;
        }else{
            p = p->next;
            q = q->next;
        }
    }
    return NULL;
}

//打印
void printList(LinkList L){
    LNode *p = L->next;
    while(p){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

int main()
{
    LinkList L = initList();
    L = tailInsert(L);
    printList(L);

    //测试寻找公共点
    //L->next作为公共结点
    //而front1作为La的独有序列，front2作为Lb的独有序列
    LinkList front1 = initList();
    front1 = tailInsert(front1);

    LinkList front2 = initList();
    front2 = tailInsert(front2);

    //序列拼接
    LNode *r = front1;
    while(r->next) r = r->next;
    r->next = L->next;

    r = front2;
    while(r->next) r = r->next;
    r->next = L->next;

    L->next = NULL;
    free(L);

    LNode *sameNode = mergeList(front1,front2);
    while(sameNode){
        printf("%d ",sameNode->data);
        sameNode = sameNode->next;
    }
    printf("\n");

    return 0;
}

6. Lc = {a1,b1,a2,b2......}，将Lc拆为La = {a1,a2......}和Lb = {b1,b2........}，就地算法。修改了题干，这样简单一些。

LinkList getResult(LinkList Lc) {
    if (Lc == NULL || Lc->next == NULL) return NULL;

    // La 的头指针
    LinkList La = Lc->next;
    LNode *p = Lc, *r = La;
    LNode *ra = La;

    while (r != NULL && r->next != NULL) {
        p->next = r->next;  // b节点链接到 Lb
        r = r->next;        // 移动到下一个节点
        ra->next = r->next; // 将下一个a节点链接到 La
        ra = ra->next;      // 尾插
        p = r;              // 更新p指针
        r = r->next;        // 移动到下一个节点
    }

    if (ra != NULL) {
        ra->next = NULL; // 确保La的最后一个节点指向 NULL
    }
    if (p != NULL) {
        p->next = NULL; // 确保Lb的最后一个节点指向 NULL
    }

    return La;
}

原题为：将Lc拆为La = {a(1),a(2)......}和Lb = {b(n),b(n-1)........}，就地算法

遍历Lc，将a结点尾插，将b结点头插

LinkList getResult(LinkList Lc){
   LinkList Lb = initList();
   Lb->next = NULL;
   LNode *p = Lc->next, *q = NULL;
   //ra为La的尾指针，因为要对La进行尾插，对Lb进行头插
   LNode *ra = Lc;
   while(p != NULL){
       //尾插
       ra->next = p;
       ra = p;
       p = p->next;
       //头插
       if(p!=NULL){
           q = p->next;
           p->next = Lb->next;
           Lb->next = p;
           p = q;
       }
   }
   //安置La尾结点后继
   ra->next = NULL;
   return Lb;

}

7.删除递增有序的链表中重复元素的结点

LinkList deleteSameNode(LinkList L){
    if(L->data <= 1) return L;
    LNode *p = L->next,*r = p->next;
    while(r!=NULL){
        if(p->data != r->data){
            p = r;
            r = r->next;
        }else{
            p->next = r->next;
            free(r);
            r = p->next;
        }
    }
    return L;
}

8.A、B两个单链表，元素递增有序，找AB的交集C，不破坏AB结点

LinkList getSameNode(LinkList La,LinkList Lb){
    //La和Lb均可以有重复值，但在Lc中只保留唯一值
    LNode *p = La->next,*q = Lb->next;
    LinkList Lc = initList();
    LNode *r = Lc;
    while(p!=NULL && q!=NULL){
        if(p->data == q->data){
            int current_value = p->data;
            LNode *newNode = (LNode*)malloc(sizeof(LNode));
            newNode->data = current_value;
            newNode->next = NULL;
            r->next = newNode;
            r = newNode;
            while(p!=NULL&&p->data <= current_value) p = p->next; //p后滚至下一个值
            while(q!=NULL&&q->data <= current_value) q = q->next; //q也后滚
        }else if(p->data > q->data){
            q = q->next;
        }else{
            p = p->next;
        }
    }
    return Lc;
}

9.求AB的交集，要求存放在A链表中

LinkList getSameNode(LinkList La,LinkList Lb){
   LNode *p = La->next,*q = Lb->next,*r = La;
   //对La进行尾插
   while(p!=NULL && q!=NULL){
       if(p->data == q->data){
            r->next = p;
            r = p;
            int current_value = p->data;
            while(p!= NULL && p->data <= current_value) p = p->next;
            while(q!=NULL && q->data <= current_value) q = q->next;
       }else if(p->data > q->data){
           q = q->next;
       }else{
           p = p->next;
       }
   }
   return La;

}

10.判断B序列是否是A序列的连续子序列

在链表为单链的情况下，这道题暂时没想到好办法，暴力出来的，请见谅（数据量不大的情况下，可以拿到大部分普通情况的分数，另外由于时间仓促这里可能没有考虑一些小数据量下的极端情况，见谅）

void checkList(LinkList La,LinkList Lb){
    //La或Lb元素随机排列
    //暴力匹配
    LNode *p = La->next,*q = Lb->next;
    int La_len = La->data,Lb_len = Lb->data;
    if(La_len < Lb_len){
        printf("No!");
        return;
    }else{
        while(p!=NULL){
            //尝试匹配
            //先记录当前p的位置
            LNode *current = p;
            if(p->data == q->data){
                while(q!=NULL){
                    if(p->data != q->data) break;
                    p = p->next;
                    q = q->next;
                }
                //Lb已经全部匹配完毕
                if(q == NULL) {
                    printf("Yes!");
                    return;
                }else{
                    //重新匹配
                    p = current->next;
                    q = Lb->next;
                }
            }else{
                p = p->next;
            }
        }
        printf("No!");
        return;
    }
}

11.设计一个算法判断带头节点的的循环双链表是否对称

先写一个主函数，测试一下

#include <stdio.h>
#include <stdlib.h>

//循环双链表
typedef struct LNode{
    int data;
    struct LNode* next;
    struct LNode* prior;
}LNode,*LinkList;


LinkList initLinkList(){
    LinkList L = (LinkList)malloc(sizeof(LNode));
    L->data = 0;
    L->next = L;
    L->prior= L;
    return L;
}


LinkList tailInsert(LinkList L){
    int num;
    LNode *r = L;
    while(scanf("%d",&num) && num!=-1){
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        newNode->data = num;
        r->next = newNode;
        newNode->prior = r;
        r = newNode;
        L->prior = r;
        r->next = L;
    }
    return L;
}

void printLinkList(LinkList L){
    LNode *p = L->next;
    while(p!=L){
        printf("%d-> ",p->data);
        p = p->next;
    }
}


int main(){
    LinkList L = initLinkList();
    L = tailInsert(L);
    printLinkList(L);

    return 0;
}

这里建议代码量少或缺少编程经验的新手可以像这样先写一部分功能函数，测试一下有没有问题，在很多比赛和研究生复试的机试中没有很好用的IDE给你用。在函数很多，调用复杂的情况下排错很困难，这样慢慢调试能确保你的代码正确，也不会很费时间

接下来写我们需要的函数：

void checkLinkList(LinkList L){
    if(L->data == 0){
        printf("Yes!\n");
        return;
    }
    LNode *p = L->next,*r = L->prior;
    int L_len = L->data;
    if(L_len%2==0){
        //长度为偶数的情况
        int step = L_len/2;
        while(step != 0){
            if(p->data == r->data){
                p = p->next;
                r = r->prior;
                step--;
            }else{
                printf("No!\n");
                return;
            }
        }
    }else{
        while(p!=r){
            if(p->data == r->data){
                p = p->next;
                r = r->prior;
            }else{
                printf("No!\n");
                return;
            }
        }
        printf("Yes!\n");
    }

}

12.两个循环单链表h1与h2，将h2连接到h1之后仍保持循环链表的形式

LinkList linkList(LinkList h1,LinkList h2){
    if(h1 == NULL) return h2;
    if(h2 == NULL) return h1;

    LNode *r1 = h1,*r2 = h2;
    while(r1->next != h1) r1 = r1->next;
    while(r2->next != h2) r2 = r2->next;

    r1->next = h2->next;
    h2->next = NULL;
    free(h2);
    r2->next = h1;
    return h1;
}

13.双链非循环链表L，结点中额外包括一个freq频度域，编写一个Locate(L,x)函数，要求每次定位一个值为x的结点时，都将链表中的结点按访问频度递减排序，最近访问的结点要排在频次相同的结点之前。

LNode* Locate(LinkList L, int x){
    //这里假定x值是唯一的
    //L已经被排好序
    LNode *p = L->next, *q;
    while(p && p->data != x){
        p = p->next;
    }
    if(p == NULL){
        return NULL;
    }else{
        p->freq++;
        if(p->prior == L || p->prior->freq > p->freq){
            return p;
        }
        if(p->next != NULL) p->next->prior = p->prior;
        //取下p
        p->prior->next = p->next;
        q = p->prior;
        while(q->prior!=L && q->freq <= p->freq){
            q = q->prior;
        }
        p->next = q->next;
        if(q->next != NULL) q->next->prior = p;
        p->prior = q;
        q->next = p;
    }
    return p;
}

14.单链表循环右移，{0,1,2,3} 右移一个单位->{3,0,1,2}

注意无头节点的链表插值操作

#include <stdio.h>
#include <stdlib.h>

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


LinkList tailInsert(){
    int num;
    LNode *head = (LNode*)malloc(sizeof(LNode));
    scanf("%d",&num);
    head->data = num;
    head->next = head;
    LNode *r = head;
    while(scanf("%d",&num) == 1 && num!=-1){
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        newNode->data = num;
        r->next = newNode;
        r = newNode;
        r->next = head;
    }
    return head;
}


void printLinkList(LinkList L){
    LNode *p = L;
    while(p->next != L){
        printf("%d->",p->data);
        p = p->next;
    }
    printf("%d ",p->data);
}

LinkList moveNode(LinkList L,int x){
    int len=0,num;
    LNode *p = L;
    while(p->next != L){
        len ++;
        p = p->next;
    }
    len++;
    num = len - x;
    while(num != 0){
        num --;
        p = p->next;
    }
    L = p->next;
    p->next = NULL;
    return L;
}


int main(){
    LinkList L =tailInsert();
    printLinkList(L);
    printf("\n");
    L = moveNode(L,3);
    printLinkList(L);

    return 0;
}

15.判断一个单链表是否有环

这道题有点难，很容易可以想到暴力方法，即从某点出发向后遍历，若有环则最终还是会回到此点，但时间复杂度过高了。王道书上的方法实际上是数学推理，推理过程需要好好理解

LNode* judgeLinkList(LinkList L){
    LNode *fast = head, *slow = head;
    while(fast!=NULL && fast ->next !=NULL){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) break;
    }
    if(fast == NULL || fast->next == NULL){
        return NULL;
    }
    LNode *p = L, *q = slow;
    while(p!=q){
        p = p->next;
        q = q->next;
    }
    return p;
}

16. 求最大的孪生结点和

（测试链表没有头结点）

int getMaxSum(LinkList L){
    //同样是快慢指针法
    //注意这里的链表没有头结点
    LNode *fast = L->next,*slow = L;
    while(fast!=NULL && fast->next!=NULL){
        fast = fast->next->next;
        slow = slow->next;
    }
    LNode *newHead = NULL, *p = slow->next, *temp;
    //反转链表
    while(p!=NULL){
        temp = p->next;
        p->next = newHead;
        newHead = p;
        p = temp;
    }
    int max = 0;
    p = L;
    LNode *q = newHead;
    while(p!=NULL && q!=NULL){
        int sum = p->data+q->data;
        if(sum>max){
            max = sum;
        }
        p = p->next;
        q = q->next;
    }
    if(max == 0) return 0;
    return max;
}

17.找到单链表的倒数第K个位置

#include <stdio.h>
#include <stdlib.h>

//带头结点的倒数第k个位置

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


LinkList initLinkList(){
    LinkList L = (LinkList)malloc(sizeof(LNode));
    L->data = 0;
    L->next = NULL;
    return L;
}


LinkList tailInsert(LinkList L){
    int num;
    LNode *r = L;
    while(scanf("%d",&num)==1 && num != -1){
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        newNode->data = num;
        newNode->next = NULL;
        r->next = newNode;
        r = newNode;
    }
    return L;
}

void printList(LinkList L){
    LNode *p = L->next;
    while(p!=NULL){
        printf("%d-> ",p->data);
        p = p->next;
    }
}


LNode* getKvalue(LinkList L, int k){
    int list_len = 0;
    LNode *p = L->next;
    while(p!=NULL){
        list_len++;
        p = p->next;
    }
    int step = list_len - k;
    p = L->next;
    while(step > 0){
        p = p->next;
        step --;
    }
    return p;
}


int main(){
    LinkList L = initLinkList();
    L = tailInsert(L);
    printList(L);
    printf("\n");
    printf("----------------分割线----------------------\n");
    printf("K_value:%d",getKvalue(L,2)->data);
    return 0;
}

18.有相同后缀的单词，从相同后缀的起始位置开始共享存储空间，单词以单链表形式存储，请给出两个单词共同后缀的起始位置

这是12年408真题，也是前面的第5题源题，解题思路一样，不重复了

19.删除len = m的单链表中绝对值（绝对值<=n）相同的结点，仅保留第一次出现的结点（要求时间复杂度优良）

其实此题给出了提示，因为题目仅要求时间复杂度优良，并未对空间复杂度做限制。而最容易想到的方法就是利用数组可以随机存取的特性，可以设置一个辅助数组arr[n]，遍历链表的每一个元素data，遍历时检查arr[|data|]是否为0，若不为0则绝对值相同的节点已经访问过，直接删除即可；反之，可以令arr[|data|]++

void deleteSameNode(LinkList L){
    int arr[MAXSIZE] = {0};
    //工作指针和它的前驱，方便结点删除
    LNode *p = L,*r = p->next;
    while(r!=NULL){
        int abs_data = abs(r->data);
        if(arr[abs_data] == 0){
            arr[abs_data]++;
            p = p->next;
            r = r->next;
        }else{
            p->next = r->next;
            r->next = NULL;
            free(r);
            r = p->next;
        }
    }
}

20.带头结点的单链表L = {a1,a2,a3.....}重新排列 -> L' = {a1,an,a2,an-1,a3.......}，要求原地算法

这道题也是一道统考真题，前面已经用到了类似的思想，即头插法会改变链表的结点顺序。另外需要注意此题的边界条件，避免空指针访问！

LNode* nodeReverse(LinkList L){
    //可以尝试举几个例子
    //1 2 3 4 5 6 7 -> 1 7 2 6 3 5 4
    //L从中间断开->L1+L2，然后L2逆置，间隔插入L1中即可
    int len_list = 0;
    LNode *p = L->next;
    while(p!=NULL){
        len_list ++;
        p = p->next;
    }
    int mid = (len_list+1)/2;
    p = L;
    while(mid != 0){
        p = p->next;
        mid --;
    }

    LNode *L2 = p->next,*r = L2;
    p->next = NULL;
    p = L2;
    L2 = NULL;
    while(p!=NULL){
        r = p->next;
        p->next = L2;
        L2 = p;
        p = r;
    }

    //L2逆置完毕，注意这里的L2是无头结点的
    //间隔插入
    p = L->next;
    r = p->next;
    LNode *q = L2,*s = q->next;
    //把L2插入到L中去
    while(q!=NULL){
        //逐个取下L2的结点
        q->next = r;
        p->next = q;
        p = r;
        if(p!=NULL){
            r = p->next;
        }
        q = s;
        s = q?q->next:NULL;
    }
    return L;
}

本人水平有限，加之时间仓促，纰漏之处敬请斧正！

⭐本章节完，谢谢你看到这里！⭐

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能