美文网首页
线性表-算法练习

线性表-算法练习

作者: 土豆骑士 | 来源:发表于2020-04-18 22:25 被阅读0次

题目一

将2个递增的有序链表合并为一个链表的有序链表;要求结果链表仍然使用两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。

解析:
所需结果:L1 {1,2,3,4}; L2 {3,5,6,7,8,9} ==> L3 {1,2,3,4,5,6,7,8,9}。

要求:1:使用L1,L2现有存储空间,不占用其他存储空间,即空间复杂度为 O(1)。
2:表中不允许有重复数据。需要释放重复的节点数据。

思路:使用 单链表结构
1:L3 指向L1,遍历L1 L2,取较小元素存储在L3;
2:相等的元素,释放掉L2的元素;
3:未遍历到的元素,拼接到L3后,返回L3;

void MergeList(LinkList *La, LinkList *Lb, LinkList *Lc) {
    LinkList pa,pb,pc;
    //pa 是链表La的工作指针,pb 是链表Lb的工作指针, 初始化为首元结点;
    pa = (*La)->next;
    pb = (*Lb)->next;
    
    *Lc = pc = *La;
    while (pa && pb) {
        if (pa->data < pb->data) { 
            pc->next = pa;//取较小者La中的元素
            pc = pa;    //,将pa链接在pc的后面
            pa = pa->next;//,pa指针后移
        } else if(pa->data > pb->data){ 
            pc->next = pb;//取较小者Lb的元素
            pc = pb;      //将pb链接在pc后面
            pb = pb->next;// pb指针后移
        } else { 
            pc->next = pa;//相等时取La中的元素
            pc = pa;
            pa = pa ->next;

            LinkList temp = pb->next;
            free(pb);//,删除Lb的元素;
            pb = temp;
        }
    }
    //将非空表的剩余元素之间链接在Lc表的最后
    pc->next = pa?pa:pb;
    
    //释放Lb的头结点
    free(*Lb);
} 

题目二

已知两个链表A B 分别表示两个集合,其内元素递增,设计一个算法,求出AB的交集,并存储到A链表中。

解析:
所需结果:LA {1,2 ,3,4}; LB {2,3,4,6,7,8,9} ==> LC {2,3,4}。

要求:1:交集存到A中,即空间复杂度为 O(1)。

思路:使用单链表结构
1:LC指向LA,遍历LA LB(不为空);
2:元素相等,LA节点连接到LC,LB节点释放,元素较小者,删除;
3:未遍历到的元素,释放。

void Intersection(LinkList *La, LinkList *Lb, LinkList *Lc) {

    LinkList pa,pb,pc,temp;
  
    //pa 是链表La的工作指针,pb 是链表Lb的工作指针, 初始化为首元结点;La的头结点作为Lc的头结点;
    pa = (*La)->next;
    pb = (*Lb)->next;
    *Lc = pc = *La;
    
    while (pa && pb) {
        
        if (pa->data == pb->data) {
            //相等,交集并入结果链表中;
            //(1).取La中的元素,将pa链接到pc的后面,pa指针后移;
            pc->next = pa;
            pc = pa;
            pa = pa->next;
            //(2)删除Lb中对应相等的元素
            temp = pb;
            pb = pb->next;
            free(temp);
        }else if(pa->data < pb->data){
            
            //删除较小值La的元素;
            temp = pa;
            pa = pa->next;
            free(temp);
        }else{
            //删除较小值Lb中的元素
            temp = pb;
            pb = pb->next;
            free(temp);
        }
    }
    pc->next = NULL;//以上代码交集取全了,尾节点next 置为NULL
   
    while (pa) { //Lb为空,删除非空表La中的所有元素
        temp = pa;
        pa = pa->next;
        free(temp);
    }
  
    while (pb) {//La为空,删除非空表Lb中的所有元素
        temp = pb;
        pb = pb->next;
        free(temp);
    }
    free(*Lb);
}

题目三

设计一个算法,将链表中的所有节点的链接方向原地旋转,及要求仅仅利用原表的存储空间,即要求空间复杂度为O(1)。
例如:L= {0,2,4,6,8,10}, 逆转后:L = {10,8,6,4,2,0}

要求:链表逆转,空间复杂度 O(1)。

思路:使用单链表 头插法 可逆转链表。(头插法生成的列表,为逆序的)

void Inverse(LinkList *L){//目的: 逆转带头结点单链表L;
    
    LinkList p,q;
   
    p = (*L)->next; //p指向首元结点;
   
    (*L)->next = NULL; //头结点的指针域置空
    
    //遍历链表
    while (p!=NULL) {//头插法
        
        q = p->next;//q执行p的后继
        
        p->next = (*L)->next;//p->next = (*L)->next
       
        (*L)->next = p; //*p 插入到头结点之后;
       
        p = q; //处理下一个结点
    }
}

题目四

设计一个算法,删除递增有序链表中值 >= mink 且 <= maxk(mink,maxk是给定的两个参数,其值可以和表中的元素相同,也可以不同)的所有元素;

La={0,2,4,6,8,10},mink = 2,maxk = 8 ==> La={0,10};

思路:1:遍历链表,找到第一个大于mink的节点,用pre保存;
2:遍历链表,找到第一个大于maxk的节点,用p指向;
3:删除元素,修改指针指向,pre->next = p;
4:介于pre 和 p 之间的节点释放;

时间复杂度O(n) 空间复杂度 O(1)

void DeleteMinMax1(LinkList *L, int mink, int maxk){
    
    if (*L == NULL || mink > maxk) {
        return;
    }
    
    LinkList p,pre = NULL,temp;
    
    p = (*L)->next;
    
    while (p) {
        if (p->data < mink) {//找到小于mink最近的节点pre
            pre = p;
        }
        
        if (p->data > maxk) {//p指向maxk后一个节点
            break;
        }
        p = p->next;
    }
    
    LinkList q = pre->next;//3.修改待删除的结点指针
    pre->next = p;//删除元素,修改指针指向
    
    while (q != p) {//释放mink——maxk之间的元素
        temp = q->next;
        free(q);
        q = temp;
    }
}

题目五

设将n(n>1)个整数存放到一位数组R中,试设计一个在时间空间上都高效的算法,将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据由(x0,x1...,xn-1)变换为(xp,xp+1,...xn-1,x0,x1,...xp-1)。

所需结果:La={1,2,3,4,5} 左移p=2个位置 ==> La={3,4,5,1,2}。

思路:1:n个数据逆序 5,4,3,2,1;
2:拆解成[5,4,3] [2,1];
3:n-p数据/p个数据,再次逆序[3,4,5][1,2] ==>[3,4,5,1,2]

时间复杂度 O(n) 空间复杂度O(1)

void Reverse(int *pre,int left ,int right) { //将数组R中的数据原地逆置
    
    //i等于左边界left,j等于右边界right;
    int i = left,j = right;
    int temp;
    
    while (i < j) { //交换pre[i] 和 pre[j] 的值
        
        //交换
        temp = pre[i];
        pre[i] = pre[j];
        pre[j] = temp;
        
        //i右移,j左移
        i++;
        j--;
    }
}

void LeftShift(int *pre,int n,int p){ //将长度为n的数组pre 中的数据循环左移p个位置
    
    if (p>0 && p<n) {
        //1. 将数组中所有元素全部逆置
        Reverse(pre, 0, n-1);
        //2. 将前n-p个数据逆置
        Reverse(pre, 0, n-p-1);
        //3. 将后p个数据逆置
        Reverse(pre, n-p, n-1);
        
    }
}

题目六

已知一个整数序列A={a0,a2,...an-1},其中(0<=ai <= n),(0<= i <= n)。若存在ap1=ap2=...apm = x,且m>n/2 (0<= pk<n,1<=k<=m),则称x为A的主元素,例如A=(0,5,5,3,5,7,5,5),则5是主元素;若B=(0,5,5,3,5,1,5,7),则A中没有主元素,假设A中的N个元素保存在一个一位数组中,请设计一个尽可能高效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否则输出-1.

解析:要求找出主元素,主元素出现的次数> n/2;

思路:1:选出首元素A[0]作为候选主元素key,遍历计数count 遇到下一个元素相同则++,不同则--,count<0则,更换key,count置为1,继续遍历选出候选的key。
2:若count>0 ,再次遍历出Key出现的次数count;
3:若 count > n/2 则返回 key值,否则 返回-1;

时间复杂度O(n); 空间复杂度O(1)。

int MainElement(int *A, int n){ //目标: 求整数序列A中的主元素;
   
    int count = 1;  //count 用来计数
   
    int key = A[0]; //key 用来保存候选主元素, 初始A[0]
    
    for (int i = 1; i < n; i++) {//(1) 扫描数组,选取候选主元素
        
        //(2) 如果A[i]元素值 == key ,则候选主元素计数加1;
        if (A[i] == key) {
            count++;
        }else{
            //(3) 当前元素A[i] 非候选主元素,计数减1;
            if(count >0){
                count--;
            }else{
               //(4) 如果count 等于0,则更换候选主元素,重新计数
                key = A[i];
                count = 1;
            }
        }
    }
    //如果count >0
    if (count >0){
        //(5)统计候选主元素的实际出现次数
        for (int i = count = 0; i < n; i++)
            if (A[i] == key) count++;
    }
    //(6)判断count>n/2, 确认key是不是主元素
    if (count > n/2) return key;
  
     return -1; //不存在主元素
}

题目七

用单链表保存m个整数,节点的结构为(data,link)且 |data|<=n (n为正整数)。现在要去设计一个时间复杂度尽可能高效的算法。对于链表中的data 绝对值相等的节点,仅保留第一次出现的节点,而删除其余绝对值相等的节点。
例如,链表A= {21,-15,15,-7,15},删除后的链表A={21,-15,-7};

思路:可以用空间换取时间,定义一个n大小的数组;
1:申请大小为n的辅助数组a,并赋值初值为0;
2: 从首元结点开始遍历链表,依次检查a[|data|]的值, 若[|data|]为0,即结点首次出现,则保留该结点,并置a[|data|] = 1,若t[|data|]不为0,则将该结点从链表中删除.

时间复杂度O(m)(m链表的长度) 空间复杂度O(n)。

void DeleteEqualNode1(LinkList *L,int n) {
    
    int *a = alloca(sizeof(int)*n);//1. 开辟辅助数组a.
    
    for (int i = 0; i < n; i++) {
        *(a+i) = 0;//赋值0
    }
    
    LinkList r = *L;

    LinkList p = r->next;

    //{21,-15,15,-7,15}, 删除后的链表A={21,-15,-7};
    while (p != NULL) {
        
        if (a[abs(p->data)] == 1) {//如果该绝对值已经在结点上出现过,则删除该结点
            r->next = p->next;
            free(p);
            p = r->next;
        } else {
            a[abs(p->data)] = 1;//未出现过的结点,则将数组中对应位置置为1;
            r = p;
            p = p->next;
        }
    }
} 

相关文章

网友评论

      本文标题:线性表-算法练习

      本文链接:https://www.haomeiwen.com/subject/safevhtx.html