1024程序员节|征文

【趣学C语言和数据结构100例】

问题描述

56.设将 n(n>1)个整数存放到区带头结点处单链表乚中，设计算法将L中保存的序列循环石移 k(0<k<n)个位置。例如，若k=1，则将链表(0,1,2,3}变为{3,0,1,2}

57.设有一个带头结点的非循环双链表L，其每个结点中除有 pre、data 和 next 域外,还有一个访问频度域 freq,其值均初始化为零。每当在链表中进行一次 Locate(L,x)运算时，令值为x的结点中 freg 域的值增1，并使此链表中的结点保持按访问频度递减的顺序排列，且最近访问的结点排在频度相同的结点之前，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate(L,x)函数，返回找到结点的地址，类型为指针型。

58.单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是空的)。试编写算法判断单链表是否存在环。

59.设有一个长度 n(n 为偶数)的不带头结点的单链表，且结点值都大于 0，设计算法求这个单链表的最大孪生和。孪生和定义为一个结点值与其孪生结点值之和，对于第i个结点(从开始)，其孪生结点为第 n-i个结点。

60.已知一个带有表头结点的单链表，结点结构为 data,next 假设该链表只给出了头指针 L在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k 为正整数)。若查找成功，算法输出该结点的 data 域的值，并返回 1:否则，只返回 0.

代码分析

==56.将链表向有移动k个位置== 例如：将链表(0,1,2,3}变为{3,0,1,2}

//链表为空：
if(L==NULL || L->next==NULL){
   
    return ;
}

思路：首先遍历链表以计算节点数量 n，然后将链表的最后一个节点指向头节点，形成一个循环。接着，通过移动指针找到新的头节点，并断开循环。时间复杂度为O(n)，空间复杂度为O(1)

具体分析：链表变化,故函数名为void 函数名(LiukList &L,int k)。如果链表为空，直接返回；所以while循环遍历，同时计数n为长度。在最后使p的下一个指向L，即构成循环链表。使用for循环，p一直向后移动n-k个位置，然后令p的下一个指向空，即断链，最后返回。

==57.在双链表中根据访问频度排序==
思路：用于查找值为 x 的节点，并更新其访问频度。若找到节点，则将其移动到合适的位置以保持频度递减的顺序。时间复杂度为O(n)，空间复杂度为O(1)

具体分析： Locate(L,x)函数，返回找到结点的地址，类型为指针型，故函数名为Lnode * Locate(LiukList L,int x)，使用while循环在p不为空且p的data!=x时，一直找到值为x的p。如果p为空，即x不存在，则数据返回p，否则进行下面的操作，先令增加访问频度++，因为是递减，所以如果p是头结点的下一个或p的前一个节点的频度大于p的频度，即（p->pre = = L || p->pre->freq > p->freq），则直接返回p即可。否则，令q记录p的前一个，如果p不是最后一个节点，令p的下一个的前一个指向q，令q指向的下一个指向p的下一个。如果p是最后一个节点，则直接令q指向的下一个指向p的下一个。（==为了跳过目前的p==）使用while遍历，不到==L时且频度域的值大的位置，向前移动，即找到插入位置。然后使用尾插法，插入p到q之后。先令p的下一个指向q的下一个，先和后面的连接。令p的下一个的前一个指向q。即和后边的正式建立连接。然后令p的前一个指向q,令q的下一个指向p,成功插入。最后返回结点的地址p。

==58.单链表是否存在环==
思路：使用快慢指针法判断链表是否存在环。如果快指针和慢指针相遇，则说明存在环。

具体分析：定义两个指针都指向L的部。这样他们的下一个不为0。则进行操作，令慢指针每次移动一步，令快指针每次移动一步，如果他们相等，则返回1。如果出了循环，则返回0。（不循环一定会跳出循环）。

==59.单链表的最大孪生和==
思路：该算法首先找到链表的中点(快慢指针)，然后反转后半部分链表( 头插法)，最后计算每对孪生节点的和并找出最大值。时间复杂度为O(n)，空间复杂度为O(1) 反转用头插 孪生和定义为一个结点值与其孪生结点值之和，对于第i个结点(从开始)，其孪生结点为第 n-i个结点。

具体分析：
1.使用快慢指针先找到链表的中点，使用while循环，条件为当快指针指向NULL结束循环，慢指针每次移动一步，令快指针每次移动一步。此时的慢指针为中点。
2.定义一个头部节点，从慢指针开始，令后面的节点使用头插法到新定义的头部节点。头插法的内容：使用s记录slow的下一个，否则断链。令s指向新的头部。将头部更新为slow，使slow变为r，继续工作。
3.计算每对孪生节点，定义p从L出发，定义q从新的头部（为新链表的头部），max=0，使遍历，如果孪生节点的和更大，则记录，一直进行移动.到结束返回max。

==60.查找链表倒数第k个位置上的结点(==
思路：该算法使用两个指针，p 和 q，在遍历链表时保持 p 比 q 领先 k 个节点。最终，当 p 到达链表末尾时，q 就是倒数第k个节点。时间复杂度为O(n)，空间复杂度为O(1)

具体分析：返回值为int，链表不会改变，故函数名为int 函数名(LiukList L,int k);定义p和q两个指针，定义一个计数，使用while循环遍历，在计数<k时，只进行计数++和，p的移动，在不到最后一个的情况下，进行的两个p和q同时移动。结束循环时，q所指的为倒数第k个。如果结束循环时，计数<k，则长度不够，返回0；否则输出结点的值，并返回1。

代码实现

#include<stdio.h>
int main(){
   

//    56.设将 n(n>1)个整数存放到区带头结点处单链表乚中，设计算法将L中保存的序列循环石移 k(0<k<n)个位置。例如，若k=1，则将链表(0,1,2,3}变为{3,0,1,2}
//    首先遍历链表以计算节点数量 n，然后将链表的最后一个节点指向头节点，形成一个循环。接着，通过移动指针找到新的头节点，并断开循环。时间复杂度为O(n)，空间复杂度为O(1)
void fun(Liuklist &L,int k){
   
    int n=1;
    LNode *p=L; 
    if(L==NULL || L->next==NULL){
   
        return ;
    }
    while(p->next != NULL){
   
        n++;
        p=p>next;
    }
    p->next=L;
    for(int i=1;i<=n-k;i++){
   
        p=p->next;
    }
    L=p->next;
    p->next=NULL;
    return ;
} 

//    57.设有一个带头结点的非循环双链表L，其每个结点中除有 pre、data 和 next 域外,还有一个访问频度域 freq,其值均初始化为零。每当在链表中进行一次 Locate(L,x)运算时，令值为x的结点中 freg 域的值增1，并使此链表中的结点保持按访问频度递减的顺序排列，且最近访问的结点排在频度相同的结点之前，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate(L,x)函数，返回找到结点的地址，类型为指针型。
//用于查找值为 x 的节点，并更新其访问频度。若找到节点，则将其移动到合适的位置以保持频度递减的顺序。时间复杂度为O(n)，空间复杂度为O(1)
DNode* Locate(DNode* L, int x) {
   
    DNode* p = L->next; // 从头结点的下一个开始
    DNode* q;
    // 找到值为x的节点
    while (p && p->data != x) {
   
        p = p->next;
    }
    if (p == NULL) {
    // x不存在
        return p;
    } else {
   
        p->freq++; // 增加访问频度
        // 如果p是头结点的下一个或p的前一个节点的频度大于p的频度
        if (p->pre == L || p->pre->freq > p->freq) {
   
            return p; // 不需要移动
        }
        q = p->pre;
        // 如果p不是最后一个节点
        if (p->next != NULL) {
   
            p->next->pre = q;
            q->next = p->next;
        } else {
   
            q->next = p->next;    //是最后一个节点
        }
        // 找到插入位置
        while (q != L && p->freq <= q->freq) {
   
            q = q->next;
        }
        // 插入p到q之后
        p->next = q->next;
        if (q->next != NULL) {
   
            q->next->pre = p;
        }
        q->next = p;
        p->pre = q;
        return p;
    }
}
//    58.单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是空的)。试编写算法判断单链表是否存在环。
//最优解
//使用快慢指针法判断链表是否存在环。如果快指针和慢指针相遇，则说明存在环。时间复杂度为O(n)，空间复杂度为O(1)
int fun(Linklist L){
   
    LNode *fast=L,*slow=L;
    while(fast->next != NULL && fast != NULL){
   
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast){
   
            return 1;
        }
    }
    return 0;
} 
//暴力解
int fun(Linklist L){
   
    LNode *pre=L,*p=L;
    while(p){
   
        while(pre!=p){
   
            if(p->next == pre){
   
                return 1;
            }
            pre=pre->next;
        }
        p=p->next;
        pre=L;
    }
    return 0;
} 

//    59.设有一个长度 n(n 为偶数)的不带头结点的单链表，且结点值都大于 0，设计算法求这个单链表的最大孪生和。孪生和定义为一个结点值与其孪生结点值之和，对于第i个结点(从开始)，其孪生结点为第 n-i个结点。
//该算法首先找到链表的中点，然后反转后半部分链表，最后计算每对孪生节点的和并找出最大值。时间复杂度为O(n)，空间复杂度为O(1)   反转用头插 
int fun(Linklist L){
   
    LNode *fast=L,*slow=L;
    while(fast->next && fast){
   
        slow=slow->next;
        fast=fast->next->next;
    } 
    Lnode *newhead=NULL,*r;
    while(s){
   
        r=s->next;
        s->next=newhead;
        newhead=s;
        s=r;
    }
    p=L;
    Lnode *Q=newheaf;
    int max=0;
    while(p){
   
        if(p->data+q->data>max){
   
            max=p->data+q->data;
            p=p->next;
            q=q->next;
        }
    }
    return max;
}

//    60.已知一个带有表头结点的单链表，结点结构为 data,next 假设该链表只给出了头指针 L在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k 为正整数)。若查找成功，算法输出该结点的 data 域的值，并返回 1:否则，只返回 0.
//    该算法使用两个指针，p 和 q，在遍历链表时保持 p 比 q 领先 k 个节点。最终，当 p 到达链表末尾时，q 就是倒数第k个节点。时间复杂度为O(n)，空间复杂度为O(1)
int fun(Linklist L,int k){
   
    LNode *p=L->next,*q=L->next;
    int count=0;
    while(p){
   
        if(count<k){
   
            p=p->next;
            count++;
        }
        else{
   
            p=p->next;
            q=q->next;
        }
    }
    if(count<k){
   
        return 0;
    } else{
   
        printf("%d",q->data);
        return 1;
    }
}


    return 0;
}

总结

本文介绍了六个数据结构问题及其C语言实现，这些问题涉及链表操作的多个方面，包括链表的循环位移、基于访问频度的节点排序、检测链表是否有环、计算单链表的最大孪生和、查找链表倒数第k个位置上的节点。这些算法不仅锻炼了我们对链表操作的理解和编程能力，也展示了数据结构在解决实际问题中的应用。

链表的循环位移问题要求我们将链表中的元素循环右移k个位置。这个问题的解决关键在于将链表变成一个循环链表，然后找到新的头节点的位置，最后断开循环。

基于访问频度的节点排序问题要求我们在双链表中查找值为x的节点，并更新其访问频度，同时保持链表中的节点按访问频度递减的顺序排列。这个问题的解决需要我们在找到节点后，根据其频度域的值将其移动到合适的位置。

检测链表是否有环问题要求我们判断单链表是否存在环。这个问题的解决可以通过快慢指针法实现，如果快指针和慢指针相遇，则说明存在环。

计算单链表的最大孪生和问题要求我们求出一个长度为偶数的单链表的最大孪生和。这个问题的解决需要我们找到链表的中点，反转后半部分链表，然后计算每对孪生节点的和并找出最大值。

查找链表倒数第k个位置上的节点问题要求我们在不改变链表的前提下，查找链表中倒数第k个位置上的节点。这个问题的解决可以通过两个指针实现，一个指针比另一个指针领先k个节点，最终当一个指针到达链表末尾时，另一个指针就是倒数第k个节点。

这些算法的实现不仅展示了C语言在处理链表时的能力，也体现了算法设计的基本思想，如指针操作、条件判断和循环控制。通过这些算法的学习，我们可以更好地理解数据结构和算法的基本概念，提高解决实际问题的能力。

总的来说，这些算法问题不仅锻炼了编程能力，也加深了对数据结构和算法的理解。通过这些问题的解决，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。这些算法的掌握对于计算机专业的学生和软件开发人员来说都是非常重要的。通过这些练习，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。