数据结构日常刷题

由 XuanVI 发布

算法

1.已知一个带有表头结点的单链表,结点结构为 |data|link| 假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置的结点(k位正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0.要求:
1)描述算法的基本设计思想。
2)描述算法的详细实现步骤。
3)根据设计思想和实现步骤,采用程序设计语言描述算法,关键之处请给出简要注释。
typedef int Elemtype;
typedef struct LNode {
    Elemtype      data;  //结点数据
    struct LNode* link;  //结点链表指针
} LNode, *LinkList;

int Search_k( LinkList list, int k ) {
    LNode *p = list->link, *q = list->link;  //指针p、q指向首元结点
    int    count = 0;
    while ( p != NULL ) {  //遍历链表直到最后一个结点
        if ( count < k )
            count++;  //计数,若count<k只移动p
        else
            q = q->link;
        p = p->link;  //让p、q同步移动
    }
    if ( count > k )
        return 0;
    else {
        printf( "%d", q->data );
        return 1;
    }
}
设置了两个距离为k-1的指针p和q,p超前q的结点数为k-1,当p遍历到链表末尾时,则q指向的就是倒数第k个结点。
2.一个长度为L(L>=1)的升序序列S,处在第L/2个位置的数称为中位数。例如,若序列S1=(11,13,15,17,19),则S1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数,例如,若S2=(2,4,6,8,20),则S1和S2的中位数是11.现在两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。 分别求两个升序序列A、B的中位数,设为a和b。 1)若a=b,则a或b即为所求中位数,算法结束。 2)若ab,则舍弃序列A中较大的一半,同时舍弃序列B中较小的一半,要求两次舍弃的长度相等。 在保留的两个升序序列中,重复1)、2)、3),直到两个序列中均只含有一个元素时为止,较小者即为所求的中位数。
#include <stdio.h>

int Search_mid( int A[], int B[], int n ) {
    int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
    while ( s1 != d1 || s2 != d2 ) {
        m1 = ( s1 + d1 ) / 2;
        m2 = ( s2 + d2 ) / 2;
        if ( A[ m1 ] == B[ m2 ] )
            return A[ m1 ];                //满足条件1
        if ( A[ m1 ] < B[ m2 ] ) {         //满足条件2
            if ( ( s1 + d1 ) % 2 == 0 ) {  //若元素个数为奇数
                s1 = m1;                   //舍弃A中间点以前的部分且保留中间点
                d2 = m2;                   //舍弃B中间点以后的部分且保留中间点
            }
            else {            //元素个数为偶数
                s1 = m1 + 1;  //舍弃A中间点及中间点以前部分
                d2 = m2;      //舍弃B中间点以后部分且保留中间点
            }
        }
        else {                             //满足条件3
            if ( ( s2 + d2 ) % 2 == 0 ) {  //若元素个数为奇数
                d1 = m1;                   //舍弃A中间点以后部分且保留中间点
                s2 = m2;                   //舍弃B中间点及中间点以前部分
            }
            else {            //元素个数为偶数
                d1 = m1;      //舍弃A中间点以后部分且保留中间点
                s2 = m2 + 1;  //舍弃B中间点及中间点以前部分
            }
        }
    }
    return A[ s1 ] < B[ s2 ] ? A[ s1 ] : B[ s2 ];
}

void main() {
    int A[] = { 11, 13, 15, 17, 19 };
    int B[] = { 2, 4, 6, 8, 20 };
    printf( "%d", Search_mid( A, B, 5 ) );
}

LeeCode算法题

234.回文链表

判断一个链表是否为回文链表
实例1: 输入: 1->2
输出: false
实例2: 输入: 1->2->2->1
输出: true
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


bool isPalindrome(struct ListNode* head){
    struct ListNode *fast = head,*slow = head,*prev = NULL;
    while(fast){
        slow = slow->next;
        fast = fast->next ? fast->next->next:fast->next;
    }
    while(slow){
        struct ListNode * temp = slow->next;
        slow->next = prev;
        prev = slow;
        slow = temp;
    }
    while(head && prev){
        if(head->val != prev->val){
            return false;
        }
        head = head->next;
        prev = prev->next;
    }
    return true;
}

暂无评论

发表评论


`, "text/html").getElementsByTagName("script") var script for(var i = 0; i