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

问题描述

61.假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，例如，loading 和 being 的存储映像如下图所示,设 strl 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 data next。请设计个时间上尽可能高效的算法，找出由 st1 和 str2 所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置 P)。

62.用单链表保存m 个整数，结点的结构为[data][link]，且|data|<n(n 为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第欠出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下

63.设线性表L=(a1.a.a3.…,an2,an1.am)采用带头结点的单链表保存，链表中的结点定义如下

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

请设计一个空间复杂度为o(1)且时间上尽可能高效的算法，重新排列工中的各结点，得到线性表L'=(a1,an,a2,an-1,a3,an2.…)

64.将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表

65.设线性表L=(X1,X2,…,Xn-2,Xn-1,Xn)中存储整型数据，采用带头结点的单链表保存。中奇数位序的数据元素按升序存放，偶数位序的数据元素按降序存放。请设计一个空间复杂度为 0(1)且时间上尽可能高效的算法，将链表中的元素按从小到大的顺序排序

代码分析

==61.带头结点的单链表，共同后缀的起始位置==
分析：返回节点+对AB不操作，故函数名为Lnode * 函数名(LiukList str1,LiukList str2).。使用while(p)循环遍历，先记录并计算，str1和str2的长度，先使长度小的先移动他们的差，然后再不到最后的情况下，同时移动，找到相同节点。返回该位置。

==62.单链表中删除绝对值一样的节点==
分析：传入一个数组和n,故函数名为void 函数名(LiukList L,int n)。创建一个动态数组存储（n+1大小）并初始化为0，然后开始遍历，使用三目运算符，使负的变为正，即（m=p->next->data > 0 ?p->next->data:-p->next->data;），如果再数组中为0，则记录，并继续，如果不为0，则使跳过其。知道循环结束。

==63.重新排列，a1,an,a2,an-1,a3,an2.…==
思路：1.找到链表的中点 2.反转链表的后半部分，使用头插法 3.交替合并链表的前半部分和反转后的后半部分，使用尾插法。

具体分析：找到链表的中间节点：使用两个指针 p 和 q。p 每次移动一步，q 每次移动两步。当 q 到达链表末尾时，p 刚好位于中间节点。分割链表:q 现在指向后半部分的头节点,将 p 的 next 指向 NULL，以断开链表。 反转后半部分链表：使用指针 r 来保存当前节点的下一个节点。然后将当前节点 q 的 next 指向前半部分的头节点 p 的 next，并将 p 的 next 更新为 q。继续这个过程，直到后半部分的所有节点都被反转并插入到前半部分的开头。使用指针 p 指向前半部分的头节点，指针 q 指向反转后的后半部分的头节点。交替地将 q 的节点插入到 p 的后面，直到 q 的所有节点都被合并。

==64.两个值有序非空线性链表合并一个按值有序的链表==
分析：返回为一个链表，传入的只要A会改变，故函数名为Linklist func(Linklist A,Linklist B)，定义p和q分别指向A和B，先创造C的头部，令A，B中小的赋值，使用while循环一起遍历，使值小的在C的后面，并更新C的尾部，在结束循环时，在C的尾部加入指向NULL。返回C即可。

==65.奇数位序的数据元素按升序存放，偶数位序的数据元素按降序存放->原地条件下->按从小到大的顺序排序==
分析：传入链表对其操作并返回。故函数名为：Linklist func(Linklist &L)。定义p并使其指向头节点的下一个的下一个，p 指向链表中第三个节点。使后面的断链即，指向NULL。从p开始使用while循环遍历，定义一个pre指向L从头开始遍历，知道插入位置，使用尾插法插入，并更新p的位置，一直找到其对于的位置。

代码实现

#include<stdio.h>
int main(){
   
//    61.假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，例如，loading 和 being 的存储映像如下图所示,设 strl 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 data next。请设计个时间上尽可能高效的算法，找出由 st1 和 str2 所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置 P)。
Lnode* func(Linklist str1,Linklist L2){
   
    int m=0,n=0;
    Lnode* p=str1->next,q=str2->next;
    while(p){
   
        m++;
        p=p->next;
    }
    while(q){
   
        n++;
        q=q->next;
    }
    p=str1;
    q=str2;
    while(m>n){
   
        p=p->next;
        m--;
    }
    while(m<n){
   
        q=q->next;
        n--;
    }
    while(p){
   
        if(p==q){
   
            return p;
        }
        p=p->next;
        q=q->next;
    }
    retrun p;
}

//62.用单链表保存m 个整数，结点的结构为[data][link]，且|data|<n(n 为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第欠出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下
void func(Linklist &L,int n){
   
    int *q;
    q = malloc(sizeof(int) * (n + 1));
    for(int i=0;i<n;n++){
   
        *(q+i)=0;
    }
    Lnode* p=L,*r;
    while(p->next !=NULL){
   
        m=p->next->data > 0 ?p->next->data:-p->next->data;
        if(*(q+m)==0){
   
            *(q+m)=1;
            p=p->next;
        }else{
   
            r=p->nrxt;
            p->next=r->next;
            free(r);
        }
    }
    free(q);
}

//63.设线性表L=(a1.a.a3.…,an2,an1.am)采用带头结点的单链表保存，链表中的结点定义如下typedef struct LNode{int data;struct node*next;}LNode, *LinkL ist:请设计一个空间复杂度为o(1)且时间上尽可能高效的算法，重新排列工中的各结点，得到线性表L'=(a1,an,a2,an-1,a3,an2.…)
Lnode* fun(Linklist &L){
   
    Lnode *p=L,*q=L,*r;
//    找到链表的中间节点：使用两个指针 p 和 q。p 每次移动一步，q 每次移动两步。当 q 到达链表末尾时，p 刚好位于中间节点。
    while(p->next!=NULL){
   
        p=p->next;
        q=q->next;
        if(q->next!=NULL){
    
            q=q->next; 
        }
    }
//    分割链表:q 现在指向后半部分的头节点,将 p 的 next 指向 NULL，以断开链表。 
    q=p->next;
    p->next=NULL;
//    反转后半部分链表：使用指针 r 来保存当前节点的下一个节点。
//    然后将当前节点 q 的 next 指向前半部分的头节点 p 的 next，并将 p 的 next 更新为 q。
//    继续这个过程，直到后半部分的所有节点都被反转并插入到前半部分的开头。
    while(q){
   
        r=q->next;
        q->next=p->next;
        p->next=q;
        q=r;
    }
//    使用指针 p 指向前半部分的头节点，指针 q 指向反转后的后半部分的头节点。
//    交替地将 q 的节点插入到 p 的后面，直到 q 的所有节点都被合并。
    q=p->next;
    p=L->next;
    while(q){
   
        r=q->next;
        q->next=p->next;
        p->next=q;
        p=p->next;
        q=r;
    }
}

//    64.将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表
Linklist func(Linklist A,Linklist B){
   
    Linklist C;
    Lnode *p=A,*q=B,*r;
    if(p->data < q->data){
   
        C=A;
        r=A;
        p=p->next;
    }else{
   
        C=B;
        r=B;
        q=q->next;
    }
    while(p&&q){
   
        if(p->data < q->data){
   
            r->next=p;
            r=p;
            p=p->next;
        }else{
   
            r->next=q;
            r=q;
            q=q->next;
        }
    }
    r->next=(p!=NULL)?p:q;
    return C;
}

//    65.设线性表L=(X1,X2,…,Xn-2,Xn-1,Xn)中存储整型数据，采用带头结点的单链表保存。中奇数位序的数据元素按升序存放，偶数位序的数据元素按降序存放。请设计一个空间复杂度为 0(1)且时间上尽可能高效的算法，将链表中的元素按从小到大的顺序排序
Linklist func(Linklist &L){
   
    Lnode *p=L->next->next;        //p 指向链表中第三个节点
    L->next->next=NULL;        //断链  

    Lnode *pre,*q;
    while(p){
   
        q=p->next;        
        pre=L;        //从头开始 
        while(p->next->data < pre->data && p->next!=NULL){
   
            pre=pre->next;
        }        //找到插入位置 
        p->next=pre->next;
        pre->next=p;
        p=q;
    }    
}

    return 0;
}

总结

本文介绍了五个数据结构问题及其C语言实现，这些问题涵盖了链表操作的多个方面，包括查找共同后缀、删除重复节点、重新排列链表元素、合并有序链表以及对特定条件下的链表元素进行排序。这些算法不仅锻炼了我们对链表操作的理解和编程能力，也展示了数据结构在解决实际问题中的应用。

查找共同后缀的问题要求我们找出两个单词单链表的共同后缀起始位置。这个问题的解决关键在于计算两个链表的长度，并从后向前比较节点，找到共同的起始节点。

删除重复节点的问题要求我们删除链表中绝对值相同的节点，只保留第一次出现的节点。这个问题可以通过使用一个额外的数组来记录已经出现过的绝对值，从而实现高效的删除操作。

重新排列链表元素的问题要求我们将链表中的元素重新排列，使得奇数位置的元素和偶数位置的元素交替出现。这个问题的解决需要我们找到链表的中点，反转后半部分链表，然后交替合并前后两部分。

合并有序链表的问题要求我们将两个有序链表合并为一个有序链表。这个问题可以通过比较两个链表的头节点，将较小的节点依次加入新链表，直到两个链表都遍历完毕。

对特定条件下的链表元素进行排序的问题要求我们将奇数位序的元素按升序存放，偶数位序的元素按降序存放的链表重新排序。这个问题的解决需要我们重新调整链表节点的连接顺序，使得所有元素按从小到大的顺序排列。

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

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