精华内容
下载资源
问答
  • 线性表练习

    2013-04-16 20:33:37
    线性表练习 1.下述哪一条是顺序存储结构的优点?( ) A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示
  • 线性表练习

    2020-04-16 15:37:59
    线性表算法练习题题目(1):有序链表的合并题目(2):两个链表的交集题目(3):链表“原地旋转”题目(4):删除链表指定范围的元素题目(5):链表的指定范围元素的逆置题目(6):找主元素(攻山头)题目(7)...

    题目(1):有序链表的合并

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

    算法思想:
    (1)假设待合并的链表为La和Lb,合并后的新表使用头指针Lc(Lc的表头结点设为La的表头结点)指向. Pa 和 Pb 分别是La,Lb的工作指针.初始化为相应链表的首元结点
    (2)从首元结点开始比较, 当两个链表La 和Lb 均未到达表尾结点时,依次摘取其中较小值重新链表在Lc表的最后.
    (3)如果两个表中的元素相等,只摘取La表中的元素,删除Lb表中的元素,这样确保合并后表中无重复的元素;
    (4)当一个表达到表尾结点为空时,非空表的剩余元素直接链接在Lc表最后.
    (5)最后释放链表Lb的头结点;

    void MergeList(LinkList *La, LinkList *Lb, LinkList *Lc){
        //目标:将2个递增的有序链表La,Lb 合并为一个递增的有序链表Lc
        
        LinkList pa,pb,pc,temp;
        //pa 是链表La的工作指针,pb 是链表Lb的工作指针, 初始化为首元结点;
        pa = (*La)->next;
        pb = (*Lb)->next;
        
        *Lc = pc = *La;
        while (pa && pb) {
            if (pa->data < pb->data) {
                //取较小者La中的元素,将pa链接在pc的后面,pa指针后移
                pc->next = pa;
                pc = pa;
                pa = pa->next;
            }else if(pa->data > pb->data){
                //取较小者Lb的元素,将pb链接在pc后面, pb指针后移
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }else
            {
                //相等时取La中的元素,删除Lb的元素;
                pc->next = pa;
                pc = pa;
                pa = pa ->next;
                temp = pb->next;
                free(pb);
                pb = temp;
            }
        }
        
        //将非空表的剩余元素之间链接在Lc表的最后
        pc->next = pa?pa:pb;
        
        //释放Lb的头结点
        free(*Lb);
        
    }
    
    题目(2):两个链表的交集

    已知两个链表A和B分别表示两个集合.其元素递增排列列. 设计⼀一个算法,⽤用于求出A与B的交集,并
    存储在A链表中; 例例如 : La = {2,4,6,8}; Lb = {4,6,8,10}; Lc = {4,6,8}。

    算法思想:
    (1)假设待合并的链表为La和Lb,合并后的新表使用头指针Lc(Lc的表头结点设为La的表头结点)指向. Pa 和 Pb 分别是La,Lb的工作指针.初始化为相应链表的首元结点
    (2)从首元结点开始比较, 当两个链表La 和Lb 均未到达表尾结点时.
    (3)如果两个表中的元素相等,只摘取La表中的元素,删除Lb表中的元素;
    (4)如果其中一个表中的元素较小,删除此表中较小的元素. 此表的工作指针后移;
    (5)当链表La和Lb有一个先到达表尾结点为空时,依次删除另一个非空表中的所有元素,最后释放链表lb;

    void Intersection(LinkList *La, LinkList *Lb, LinkList *Lc){
        
        //目标: 求2个递增的有序链表La,Lb的交集, 使用头指针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);
            }
        }
        
        //Lb为空,删除非空表La中的所有元素
        while (pa) {
           
            temp = pa;
            pa = pa->next;
            free(temp);
        }
        
        //La为空,删除非空表Lb中的所有元素
        while (pb) {
            temp = pb;
            pb = pb->next;
            free(temp);
        }
        
        
        pc->next = NULL;
        free(*Lb);
    }
    
    题目(3):链表“原地旋转”

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

    算法思想:
    (1)利用原有的头结点*L,p为工作指针, 初始时p指向首元结点. 因为摘取的结点依次向前插入,为确保链表尾部为空,初始时将头结点的指针域置空;
    (2)从前向后遍历链表,依次摘取结点,在摘取结点前需要用指针q记录后继结点,以防止链接后丢失后继结点;
    (3)将摘取的结点插入到头结点之后,最后p指向新的待处理节点q(p=q);

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

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

    算法思想:
    (1)查找第一个值大于mink的结点,用q指向该结点,pre 指向该结点的前驱结点;
    (2)继续向下遍历链表, 查找第一个值大于等于maxk的结点,用p指向该结点;
    (3)修改下边界前驱结点的指针域, 是其指向上边界(pre->next = p);
    (4)依次释放待删除结点的空间(介于pre和p之间的所有结点);

    void DeleteMinMax(LinkList *L, int mink, int maxk){
        //目标: 删除递增有序链表L中值大于等于mink 和小于等于maxk的所有元素
        
        LinkList p,q,pre;
        pre = *L;
        LinkList temp;
        
        //p指向首元结点
        p = (*L)->next;
        
        //1.查找第一值大于mink的结点
        while (p && p->data < mink) {
            //指向前驱结点
            pre = p;
            p = p->next;
        }
        
        //2.查找第一个值大于等于maxk的结点
        while (p && p->data<=maxk) {
            p = p->next;
        }
        
        //3.修改待删除的结点指针
        q = pre->next;
        pre->next = p;
        
        while (q != p) {
            temp = q->next;
            free(q);
            q = temp;
        }
    }
    
    题目(5):链表的指定范围元素的逆置

    设将n(n>1)个整数存放到⼀一维数组R中, 试设计⼀一个在时间和空间两⽅方⾯面都尽可能⾼高效的算法;将R
    中保存的序列列循环左移p个位置(0<p<n)个位置, 即将R中的数据由(x0,x1,…,xn-1)变换为 (xp,xp+1,…,xn-1,x0,x1,…,xp-1).
    例例如: pre[10] = {0,1,2,3,4,5,6,7,8,9}, n = 10,p = 3; pre[10] = {3,4,5,6,7,8,9,0,1,2}

    算法思路:

    1. 先将n个数据原地逆置 9,8,7,6,5,4,3,2,1,0;
    2. 将n个数据拆解成[9,8,7,6,5,4,3] [2,1,0]
    3. 将前n-p个数据和后p个数据分别原地逆置; [3,4,5,6,7,8,9] [0,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;
        
        //交换pre[i] 和 pre[j] 的值
        while (i < 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);
            
        }
    }
    
    题目(6):找主元素(攻山头)

    已知⼀一个整数序列列A = (a0,a1,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.

    算法思路:

    1. 选取候选主元素, 从前向后依次扫描数组中的每个整数, 假定第一个整数为主元素,将其保存在Key中,计数为1. 若遇到下一个整数仍然等于key,则计数加1. 否则计数减1. 当计数减到0时, 将遇到的下一个整数保存到key中, 计数重新记为1. 开始新一轮计数. 即可从当前位置开始重上述过程,直到将全部数组元素扫描一遍;
    2. 判断key中的元素是否是真正的主元素, 再次扫描数组, 统计key中元素出现的次数,若大于n/2,则为主元素,否则,序列中不存在主元素;

    算法分析:
    时间复杂度: O(n)
    空间复杂度: O(1)

    int MainElement(int *A, int n){
        
        //目标: 求整数序列A中的主元素;
        //count 用来计数
        int count = 1;
        //key 用来保存候选主元素, 初始A[0]
        int key = A[0];
        
        //(1) 扫描数组,选取候选主元素
        for (int i = 1; i < n; i++) {
            
            //(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;
        else return -1; //不存在主元素
    
    }
    
    题目(7):删除绝对值相等的结点,仅保留第一个

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

    算法思路:

    1. 申请大小为n+1的辅助数组t并赋值初值为0;
    2. 从首元结点开始遍历链表,依次检查t[|data|]的值, 若[|data|]为0,即结点首次出现,则保留该结点,并置t[|data|] = 1,若t[|data|]不为0,则将该结点从链表中删除.

    复杂度分析:
    时间复杂度: O(m),对长度为m的链表进行一趟遍历,则算法时间复杂度为O(m);
    空间复杂度: O(n)

    void DeleteEqualNode(LinkList *L,int n){
        
        //目标: 删除单链表中绝对值相等的结点;
        //1. 开辟辅助数组p.
        int *p = alloca(sizeof(int)*n);
        LinkList r = *L;
       
        //2.数组元素初始值置空
        for (int i = 0; i < n; i++) {
            *(p+i) = 0;
        }
        
        //3.指针temp 指向首元结点
        LinkList temp = (*L)->next;
        
        //4.遍历链表,直到temp = NULL;
        while (temp!= NULL) {
            
            //5.如果该绝对值已经在结点上出现过,则删除该结点
            if (p[abs(temp->data)] == 1) {
                
                //临时指针指向temp->next
                r->next = temp->next;
                //删除temp指向的结点
                free(temp);
                //temp 指向删除结点下一个结点
                temp = r->next;
            }else
            {
                //6. 未出现过的结点,则将数组中对应位置置为1;
                p[abs(temp->data)] = 1;
                r = temp;
                //继续向后遍历结点
                temp = temp->next;
            }
        }
        
    }
    
    展开全文
  • PTA 线性表练习 7-1 求链式线性表的倒数第K项 (50point(s)) 题目描述 给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。 输入格式 输入首先给出一个正整数K,随后是若干非负整数,最后以...

    PTA 线性表练习

    7-1 求链式线性表的倒数第K项 (50point(s))

    题目描述

    给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。

    输入格式

    输入首先给出一个正整数K,随后是若干非负整数,最后以一个负整数表示结尾(该负数不算在序列内,不要处理)。

    输出格式

    输出倒数第K个位置上的数据。如果这个位置不存在,输出错误信息NULL。

    输入样例

    4 1 2 3 4 5 6 7 8 9 0 -1
    

    输出样例

    7
    

    Code

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <cstdlib>
    #include <cmath>
    #define LL long long
    #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define MP pair<int,int>
    
    /*** 
        Author : @JokerNoCry
        Time : 2020:10:26  20:17:04
     ***/
    using namespace std;
    const int maxn=1e5+10;
    const int mod=1e9+7;
    
    struct node
    {
        int data;
        node * next;
    };  // 定义节点
    struct node * head = new node;  // 创建头节点
    int main()
    {
        int k;
        cin>>k;
        int tmp,cnt=0;
        node *now;
        now = head;   // 当前节点
        while(cin>>tmp)    // 添加节点
        {
            if(tmp < 0 ) break;
            cnt++;
            node *newnode = new node;
            newnode->data = tmp;
            newnode->next = nullptr;
            now->next = newnode;
            now = newnode;
        }
        int cc = cnt - k + 1;    // 倒数第k个就是正数第cc个
        now = head;
        if(cc<=0)     // 位置不存在输出NULL
        {
            cout<<"NULL"<<endl;
            return 0;
        }
        while(cc--)   // 遍历到第cc个 输出
        {
            now = now->next;
        }
        cout<<now->data<<endl;
        return 0;
    }
    

    7-2 一元多项式的乘法与加法运算 (50point(s))

    题目描述

    设计函数分别求两个一元多项式的乘积与和。

    输入格式

    输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。

    输出格式

    输出分2行,分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔,但结尾不能有多余空格。零多项式应输出0 0。

    输入样例

    4 3 4 -5 2  6 1  -2 0
    3 5 20  -7 4  3 1
    

    输出样例

    15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
    5 20 -4 4 -5 2 9 1 -2 0
    

    Code

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <cstdlib>
    #include <cmath>
    #define LL long long
    #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define MP pair<int,int>
    
    /*** 
        Author : @JokerNoCry
        Time : 2020:10:26  19:44:35
     ***/
    using namespace std;
    const int maxn=2e3+10;
    const int mod=1e9+7;
    
    int maxexp_a,maxexp_b;   //a,b两个多项式的最大指数
    int a[maxn];
    int b[maxn];
    int add[maxn];   // 加法结果
    int mul[maxn];   // 乘法结果
    
    int main()
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(mul,0,sizeof(mul));
        int a_num,b_num;
        int temp1,temp2;        
        scanf("%d",&a_num);
        for(int i=0;i<a_num;i++)
        {
            scanf("%d%d",&temp1,&temp2);
            a[temp2] = temp1;
            if(i == 0) maxexp_a = temp2; 
        }
        scanf("%d",&b_num);
        for(int i=0;i<b_num;i++)
        {
            scanf("%d%d",&temp1,&temp2);
            b[temp2] = temp1;
            if(i == 0) maxexp_b = temp2; 
        }
        int maxexp_add = max(maxexp_a,maxexp_b);    // 加完之后 最大指数
        for(int i=maxexp_add;i>=0;i--) add[i] = a[i]+b[i];  // 加法操作
        int maxexp_mul = maxexp_a+maxexp_b;   // 乘完后 的 最大指数
        for(int i=0;i<=maxexp_a;i++)     // 乘法操作
        {
            for(int j=0;j<=maxexp_b;j++)
            {
                mul[i+j] += a[i]*b[j];
            }
        }
        // 按格式输出
        bool flag=false;
        for(int i=maxexp_mul;i>=0;i--)
        {
            if(mul[i]!=0)
            {
                if(flag) printf(" ");
                printf("%d %d",mul[i],i);
                flag = true;
            }
        }
        if(!flag) printf("0 0\n");
        else printf("\n");
        flag = false;
        for(int i=maxexp_add;i>=0;i--)
        {
            if(add[i]!=0)
            {
                if(flag) printf(" ");
                printf("%d %d",add[i],i);
                flag = true;
            }
        }
        if(!flag) printf("0 0\n");
        else printf("\n");
        return 0;
    }
    
    展开全文
  • 三写一个算法合并两个已排序的线性表用两种方法数组表示的线性表顺序表和指针表示的线性表链表 要求1定义线性表节点的结构并定义节点的型和位置的型 2定义线性表的基本操作 3在12的基础上完成本题 4在main函数中进行...
  • 数据结构 线性表 练习题 试卷及答案.doc
  • 数据结构
  • 题目描述 已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出两个集合A和B 的差集(即仅由在A中出现而不在B中出现的元素所构成的集合),并以同样的形式存储,同时返回该集合的元素个数。...

    题目描述

    已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出两个集合A和B 的差集(即仅由在A中出现而不在B中出现的元素所构成的集合),并以同样的形式存储,同时返回该集合的元素个数。

    代码

    #include <bits/stdc++.h>
    using namespace std;
    typedef int Elemtype;
    typedef struct LNode
    {
        Elemtype data;
        struct LNode *next;
    } LNode, *LinkList;                      //LNode为结构体类型 LinkList为指针类型
    void creatlist_head(LinkList &a, int n); //头插法
    void print(LinkList &a);                 //输出链表
    void creatlist_end(LinkList &a, int n);  //尾插法
    void difference(LinkList &la, LinkList &lb, int &n);
    int main()
    {
        int f, m;
        cin >> f >> m;
        LinkList la, lb;
        creatlist_end(la, f);
        creatlist_end(lb, m);
        int n = 0;
        difference(la, lb, n);
        cout << n << endl;
        print(la);
        return 0;
    }
    void creatlist_head(LinkList &a, int n) //头插法
    {
        a = new LNode;
        a->next = NULL;
        for (int i = 0; i < n; i++)
        {
            LinkList p = new LNode;
            cin >> p->data;
            p->next = a->next;
            a->next = p;
        }
    }
    void print(LinkList &a) //输出链表
    {
        LinkList p = a->next;
        while (p)
        {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }
    void creatlist_end(LinkList &a, int n) //尾插法
    {
        a = new LNode;
        a->next = NULL;
        LinkList p1, p2 = a;
        for (int i = 0; i < n; i++)
        {
            p1 = new LNode;
            cin >> p1->data;
            p1->next = p2->next;
            p2->next = p1;
            p2 = p1;
        }
    }
    void difference(LinkList &la, LinkList &lb, int &n)
    {
        LinkList pa = la->next, pb = lb->next;
        LinkList per = la;
        while (pa && pb)
        {
            if (pa->data < pb->data)
            {
                per = pa;
                pa = pa->next;
                n++;
            }
            else if (pa->data > pb->data)
                pb = pb->next;
            else
            {
                per->next = pa->next;
                LinkList q = pa;
                pa = pa->next;
                delete q;
            }
        }
    }
    
    展开全文
  • 练习题及解题思路 #include <stdio.h> #include "string.h" #include "ctype.h" #include "stdlib.h" #include "math.h" #include "time.h" #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OK...

    练习题及解题思路

     

    #include <stdio.h>
    #include "string.h"
    #include "ctype.h"
    #include "stdlib.h"
    #include "math.h"
    #include "time.h"
        
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define OK 1
        
    #define MAXSIZE 20 //存储空间初始分配量
        
        typedef int Status;//Status 是函数的类型,其值是函数结果状态代码l,如OK等
        typedef int ElemType;//ElemType 类型根据实际情况而定,这里假设为int
        
        //定义结点
        typedef struct Node{
            ElemType data;
            struct Node *prior;
            struct Node *next;
        }Node;
        
        //类型重定义
        typedef struct Node * LinkList;
    //初始化链表
        Status InitList(LinkList *L){
            *L = (LinkList)malloc(sizeof(Node));
            if (*L == NULL) return ERROR;
            (*L)->next = NULL;
            return OK;
        }
        
        //链表插入
        Status ListInsert(LinkList *L, int i, ElemType e){
            if (i<1) return ERROR;
            LinkList p,temp;
            p = *L;
            
            for (int j=1; j<i; j++) {
                p = p->next;
            }
            
            if (p == NULL) return ERROR;
            
            temp = malloc(sizeof(Node));
            temp->data = e;
            temp->next = p->next;
            p->next = temp;
            
            return OK;
        }
        
        //遍历
        Status ListTraverse(LinkList L)
        {
            LinkList p = L->next;
            while(p)
            {
                printf("%d  ",p->data);
                p = p->next;
            }
            printf("\n");
            return OK;
        }

    题目验证:

     int main(int argc, const char * argv[]) {
    
         Status iStatus;
         LinkList La,Lb,Lc,L;
         InitList(&La);
         InitList(&Lb); 

    题目1:

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


     分析:
     关键词:递增有序链表,不允许有重复数据,保留递增关系(后插法),不占用额外的存储空间意思不能开辟新结点
     
     思路:
     (1)、假设合并的链表为La 和 Lb,合并后的新表使用头指针Lc(Lc的表头结点设为La的表头结点)指向。pa 和 pb分别是La 和 Lb的工作指针,初始化为相应链表的首原结点
     (2)、从首元结点开始,当连个链表La 和 Lb均未到达表尾结点时,依次摘取其中值较小的结点(哪个链表中的小取哪个保证递增顺序),并将其插入Lc 后面。
     (3)、如果两个表中的值相等的时候,只摘取La 表中的元素,删除Lb 中的元素(防止出现野指针,同时防止出现相同的数据)。
     (4)、当一个表达到表尾结点为空时,非空表的剩余元素直接连接在 Lc 表最后(也就是其中一个表遍历并取完值了之后,另一个还没完,就直接把非空的链表剩下的元素全部连接到Lc后面)。
     (5)、最后释放链表lb 的头结点(将Lb释放,防止出现野指针,此时的Lb已经不完整同时留着也无意义)。

    void MergeList(LinkList *La, LinkList *Lb, LinkList *Lc){
    //    1、
        LinkList pa = (*La)->next;
        LinkList pb = (*Lb)->next;
        LinkList pc = *Lc = *La;
        LinkList temp;
        
        while (pa && pb ) {
    //        取较小者(相同的取La的,释放Lb的)链接到pc 后面,对应指针后移,pc也后移
            if (pa->data > pb->data) {
                pc->next = pb;
                pc = pc->next;
                pb = pb->next;
            }else if(pa->data == pb->data){
                pc->next = pa;
                pc = pc->next;
                pa = pa->next;
                temp = pb;
                pb = pb->next;
                free(temp);
                
            }else{
                pc->next = pa;
                pc = pc->next;
                pa = pa->next;
            }
        }
    //    4、将非空的链表剩余元素全部连接到Lc表的最后
        pc->next = pa?pa:pb;
        free(*Lb);
    }

    验证:

        printf("******题目1:********\n");
        //设计2个递增链表La,Lb
        for(int j = 10;j>=0;j-=2)
        {
            iStatus = ListInsert(&La, 1, j);
        }
        printf("La:\n");
        ListTraverse(La);
    
        for(int j = 11;j>0;j-=2)
        {
            iStatus = ListInsert(&Lb, 1, j);
        }
        printf("Lb:\n");
        ListTraverse(Lb);
    
        MergeList(&La, &Lb, &Lc);
        printf("Lc:\n");
        ListTraverse(Lc);
    
    //**************************************************
    La:
    0  2  4  6  8  10  
    Lb:
    1  3  5  7  9  11  
    Lc:
    0  1  2  3  4  5  6  7  8  9  10  11
    

    题目2:

     2、已知连个链表A和B分别标识两个集合。设计一个算法,用于求出A与B的交集,并存储在A链表中;
     例如:
     La = {2,4,6,8}; Lb = {4,6,8,10};
     Lc = {4,6,8}


     分析:
     依次摘取2个表中相等的元素重新进行链接,删除其他不相等的元素。


     思路:
     (1)、假设待合并的链表为La 和 Lb,合并后的新表使用头指针Lc (Lc的表头结点设为La的表头结点)指向。pa 和 pb 分别是La,Lb 的工作指针。初始化为相应链表的首元结点
     (2)、从首元结点开始比较,当两个链表La 表 和Lb 均为到达表尾结点时
     (3)、如果两个表的数据相等,只摘取La 表中的元素,连接到Lc 表的后面,删除Lb 表中的元素。同时pa、pb、pc指针均向后移。
     (4)、如果两个表的数据不相等,判断哪个表中的数据小删除那个表中的数据同时对应表的指针向后移
     (5)、当链表La 和 Lb有一个先到达表尾结点为空时,依次删除非空表中的所有元素。
     (6)、最后释放链表 Lb的头结点

    void Intersection(LinkList *La, LinkList *Lb, LinkList *Lc){
     
        //    pc 指向Lc 的头结点,用La的头结点作为Lc的头结点
        LinkList pa,pb,pc,temp;
        pa = (*La)->next;
        pb = (*Lb)->next;
        pc = *Lc = *La;
     
        while (pa && pb) {
            //        相等,将La中的元素连接到Lc中,然后删除Lb中对应的元素,同时pa、pb、pc都向后移
            if (pa->data == pb->data) {
                pc->next = pa;
                pc = pc->next;
                pa = pa->next;
                temp = pb;
                pb = pb->next;
                free(temp);
            }else if (pa->data < pb->data){
                temp = pa;
                pa = pa->next;
                free(temp);
            }else{
                //删除较小值Lb中的元素
                temp = pb;
                pb = pb->next;
                free(temp);
            }
        }
     
        //    依次删除非空链表中剩余的所有元素
        while (pa) {
            temp = pa;
            pa = pa->next;
            free(temp);
        }
     
        while (pb) {
            temp = pb;
            pb = pb->next;
            free(temp);
        }
     
        //    Lc的尾结点的 next指向NULL
        pc->next = NULL;
        free(*Lb);
    }

    验证

        printf("******题目2:********\n");
        ListInsert(&La, 1, 8);
        ListInsert(&La, 1, 6);
        ListInsert(&La, 1, 4);
        ListInsert(&La, 1, 2);
        printf("La:\n");
        ListTraverse(La);
    
    
        ListInsert(&Lb, 1, 10);
        ListInsert(&Lb, 1, 8);
        ListInsert(&Lb, 1, 6);
        ListInsert(&Lb, 1, 4);
        printf("Lb:\n");
        ListTraverse(Lb);
    
        Intersection(&La, &Lb, &Lc);
        printf("Lc:\n");
        ListTraverse(Lc);
    
    //****************************************
    La:
    2  4  6  8  
    Lb:
    4  6  8  10  
    Lc:
    4  6  8  

     

    题目3:

     3、设计一个算法,将链表中d所有的连接方向“原地旋转”,即要求仅仅利用原表的存储空间。换句话说,要求算法空间复杂度为O(1);
     例如:L = {0,2,4,6,8,10},L逆转后:L = {10,8,6,4,2};


     分析:
     (1)、不能开辟新的空间,只能改变指针的指向。
     (2)、可以考虑逐个摘取结点,利用前插法创建链表的思想,将结点依次插到头结点的后面。
     (3)、因为先插入的结点为表尾,最后插入的结点为表头,即可实现链表的逆转;
     
     思路:
     (1)、利用原有的头结点*L,p为工作指针,初始时p 指向首元结点。
     (2)、因为摘取的结点依次向前插入,为确保链表尾部为空,初始时将头结点的指针域置空
     (3)、从前向后遍历链表,依次摘取结点,在摘取接结点前需要用指针temp 记录后继结点,以防止链接后丢失后继结点;
     (4)、将摘取的结点插入到头结点之后,最后p指向新的待处理结点temp(p=temp);

    void Inverse(LinkList *L){
        LinkList p,temp;
        p = (*L)->next;
        (*L)->next = NULL;
     
        while (p) {
            //        temp指向p的后继结点,防止丢失
            temp = p->next;
            //        p 指向的结点 后继为之前的首元结点,前驱是头结点(也就是插入到头结点之后,头插法)
            p->next = (*L)->next;
            (*L)->next = p;
            //        p向后移动 p = p->next;
            p = temp;
        }
    }


    题目4:

     4、设计一个算法,删除递增有序链表中值大于等于mink 且小于等于maxk(mink,maxk是给定的连个参数,其值可以和表中的元素相同,也可以不同)的所有元素;


     分析:
     递增有序链表,找到对应的上下边界,将其中的值全部删除掉即可。
     
     思路:
     (1)、用指针p 指向链表头结点,temp 用来指向要删除的结点。
     (2)、遍历去查看p 的后继结点,通过p 的后继结点的值判断是否是要删除的结点。
     (3)、如果是要删除的结点,就把p 的后继结点删除,后继指向下下一个结点。不移动p(以后后继已经变了)继续遍历。
     (4)、如果p 后继结点不是要删除的结点,将p 后移。继续遍历

    void DeleteMinMax(LinkList *L, int mink, int maxk){
        LinkList p,temp;
        p = (*L);
     
        //    遍历是用p->next完成
        while (p->next) {
            temp = p->next;
            if (temp->data >= mink && temp->data <= maxk) {
                p->next = temp->next;
                free(temp);
            }else
                p = p->next;
        }
    }

    验证

        printf("******题目3:********\n");
        InitList(&L);
        for(int j = 10;j>=0;j-=2)
        {
            iStatus = ListInsert(&L, 1, j);
        }
        printf("L逆转前:\n");
        ListTraverse(L);
    
        Inverse(&L);
        printf("L逆转后:\n");
        ListTraverse(L);
    
    //******************************************
    L逆转前:
    0  2  4  6  8  10  
    L逆转后:
    10  8  6  4  2  0  

    题目5:

     5、设将n(n>1)个整数存放到一维数组R 中,试设计一个在时间和空间复杂度都尽可能高效的算法;将R 中保存的序列循环左移p 个位置(0<p<n)个位置,即将R 中的数据由(x0,x1,...,xn-1)变换成(xp,xp+1,...,xn-1,x0,x1,...,xp-1);
     例如:pre[10] = {0,1,2,3,4,5,6,7,8,9},
     n = 10,p = 3;
     pre[10] = {3,4,5,6,7,8,9,0,1,2}


    思路:
     (1)、先将n个数据原地逆置 (9,8,7,6,5,4,3,2,1,0)
     (2)、将n个数据拆解成 [9,8,7,6,5,4,3] [2,1,0];
     (3)、将前n-p 个数据和后p 个数据分别原地逆置;[3,4,5,6,7,8,9] [0,1,2]
     
    复杂度分析:
     时间复杂度:O(n);
     空间复杂度:O(1);

    void Reverse(int *pre,int left ,int right){
        
        int i=left,j=right,temp;
        //    数组逆置
        while (i < j) {
            temp = pre[i];
            pre[i] = pre[j];
            pre[j] = temp;
            
            i++;
            j--;
        }
    }
    
    void LeftShift(int *pre,int n,int p){
        
        if (p>0 && p<n) {
            Reverse(pre, 0, n-1);
            Reverse(pre, 0, n-p-1);
            Reverse(pre, n-p, n-1);
        }
    }

    验证

        printf("******题目4:********\n");
        InitList(&L);
        for(int j = 10;j>=0;j-=2)
        {
            iStatus = ListInsert(&L, 1, j);
        }
        printf("L链表:\n");
        ListTraverse(L);
    
        DeleteMinMax(&L, 4, 10);
        printf("删除链表mink与maxk之间结点的链表:\n");
        ListTraverse(L);
    
    //*************************************
    L链表:
    0  2  4  6  8  10  
    删除链表mink与maxk之间结点的链表:
    0  2 

    验证

        int pre[10] = {0,1,2,3,4,5,6,7,8,9};
        LeftShift(pre, 10, 3);
        for (int i=0; i < 10; i++) {
            printf("%d ",pre[i]);
        }
        printf("\n");
    
    //******************************************
    3 4 5 6 7 8 9 0 1 2 

    题目6:

    6、已知一个整数序列A= (a0,a1,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),则B中没有主元素。假设A 中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否者输出-1。


     分析:
     主元素,是数组中的出现次数超过一半的元素。
     当数组中存在主元素时,所有非主元素的个数和必然少于数组总数的一半。
     用主元素的总数 - 非主元素的总数 > 1;
     
     思路:
     (1)、选取候选主元素,从前向后依次扫描数组中的每个整数。假定第一个整数位主元素,将其保存在key 中,计数为1,若遇到下一个整数仍然等于key,则计数加1.否者计数减1,当计数减到0时,将遇到的下一个整数保存到key中,计数重新标记为1。开始新一轮计数(继续向后依次比较,直到全部数组元素扫码完毕)。
     (2)、判断key中的元素是否是真正的主元素,再次扫描数组。统计key中元素出现的次数,若大于n/2。则是主元素,z否则序列中没有主元素。


    复杂度分析:
     时间复杂度O(n);
     空间复杂度O(1);

    int MainElement(int *A, int n){
        
        //目标: 求整数序列A中的主元素;
        //count 用来计数
        int count = 1;
        //key 用来保存候选主元素, 初始A[0]
        int key = A[0];
        
        //(1) 扫描数组,选取候选主元素
        for (int i = 1; i < n; i++) {
            //(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;
        else return -1; //不存在主元素
    }

     验证

        printf("******题目6:********\n");
        int  A[] = {0,5,5,3,5,7,5,5};
        int  B[] = {0,5,5,3,5,1,5,7};
        int  C[] = {0,1,2,3,4,5,6,7};
    
        int value = MainElement(A, 8);
        printf("数组A 主元素为: %d\n",value);
        value = MainElement(B, 8);
        printf("数组B 主元素为(-1表示数组没有主元素): %d\n",value);
        value = MainElement(C, 8);
        printf("数组C 主元素为(-1表示数组没有主元素): %d\n",value);
    
    //*************************************************************
    数组A 主元素为: 5
    数组B 主元素为(-1表示数组没有主元素): -1
    数组C 主元素为(-1表示数组没有主元素): -1

     

    题目7:

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


     分析
     要求设计的是时间复杂度尽量高效,所以可以考虑用空间换时间的方法。
     申请一个空间大小为n+1(0 号单元不使用)的辅助数组。
     保存链表中已出现的数值,通过对链表进行一趟扫描来完成删除


     思路:
     (1)、申请大小为n+1的辅助数组t 并赋值初值为0;
     (2)、从首元结点开始遍历链表,依次检查t[abs(data)] 也就是t[|data|] 的值,若[|data|] 为0,即结点首次出现,则保留该结点,并置t[|data|] = 1,若t[|data|] 不为0,则将该结点从链表中删除
     
    复杂度分析:
     时间复杂度: O(m),对长度为m的链表进行一趟遍历,则算法时间复杂度为O(m);
     空间复杂度: O(n)

    void DeleteEqualNode(LinkList *L,int n){
        
        //目标: 删除单链表中绝对值相等的结点;
        //1. 开辟辅助数组p.
        int *p = alloca(sizeof(int)*n);
        LinkList r = *L;
        
        //2.数组元素初始值置空
        for (int i = 0; i < n; i++) {
            *(p+i) = 0;
        }
        
        //3.指针temp 指向首元结点
        LinkList temp = (*L)->next;
        
        //4.遍历链表,直到temp = NULL;
        while (temp!= NULL) {
            
            //5.如果该绝对值已经在结点上出现过,则删除该结点
            if (p[abs(temp->data)] == 1) {
                
                //临时指针指向temp->next
                r->next = temp->next;
                //删除temp指向的结点
                free(temp);
                //temp 指向删除结点下一个结点
                temp = r->next;
            }else
            {
                //6. 未出现过的结点,则将数组中对应位置置为1;
                p[abs(temp->data)] = 1;
                r = temp;
                //继续向后遍历结点
                temp = temp->next;
            }
        }
    }

    验证

        //21,-15,15,-7,15
        printf("******题目7:********\n");
        InitList(&L);
        ListInsert(&L, 1, 21);
        ListInsert(&L, 1, -15);
        ListInsert(&L, 1, 15);
        ListInsert(&L, 1, -7);
        ListInsert(&L, 1, 15);
    
        DeleteEqualNode(&L, 21);
        ListTraverse(L);
    
    //***************************************
    15  -7  21 

     

    展开全文
  • 线性表练习题2

    千次阅读 2014-03-21 16:41:35
    长度为n的顺序表L,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为x的数据元素。 算法分析: 设置两个计数器,一个为i,记录扫描过的元素的个数;一个为j,记录扫描过的非x...
  • OpenJudge 数据结构与算法MOOC / 第二章 线性表 练习题:多项式加法题目我的解答想法 题目 题目链接 我的解答 #include <iostream> using namespace std; class Link { public: int coef; int ...
  • 线性表练习题4

    千次阅读 2014-04-02 10:19:33
    这个题目的解决方法和线性表练习题2的解题思路基本一样,可以解决方法有两个,都很容易理解,并且时间复杂度和空间复杂度都不大。 “线性表练习题2”是要求删除值等于x的元素,而该题目要求的是删除介于s和t之间的...
  • 线性表练习题答案

    2020-12-28 19:13:37
    线性表的逻辑顺序与存储顺序总是一致的。(FALSE)2.顺序存储的线性表可以按序号随机存取。(TRUE)3.顺序表的插入和删除一个数据元素,每次操作平均只有近一半的元素需要移动。(TRUE)4.线性表中的元素可以是各种各样...
  • 线性表练习作业

    千次阅读 2019-10-29 22:16:56
    线性表练习 1-1对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。T 作者: DS课程组单位: 浙江大学1-1答案正确(2 分) 1-2对于顺序存储的长度为N的线性表,删除第一个元素和插入...
  • 顺序表、线性表练习

    2021-09-01 14:04:29
    if(L.length==01|s>=t)//线性表为空或s、t不合法,返回 return false; for(i=0 ;i;i++){ if(L.data[i] >=s& &L.data[i]) k++; else L.data[i-k]=L.data[i];//当前元素前移k个位置 } L.length-=k; //长度减小 ...
  • 线性表练习之Josephus

    2020-04-03 00:14:04
    线性表练习之Josephus 利用循环链表实现约瑟夫问题。约瑟夫问题如下:已知n个人(n>=1)围坐一圆桌周围,从1开始顺序编号。从序号为1的人开始报数,顺时针数到m的那个人出列;他的下一个人又从1开始报数,数到m的...
  • 作业 线性表练习

    2019-10-29 20:27:05
    线性表练习 1-1对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。(2分) T 1-2对于顺序存储的长度为N的线性表,删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)...
  • 线性表练习(5)

    2021-04-05 16:39:55
    if (L.length == 0 || s >= t) {//线性表为空或者s,t不合法,返回 return false; } for (i = 0; i ; i++) { if (L.data[i] >= s && L.data[i] ) { k++; } else { L.data[i - k] = L.data[i];//...
  • 线性表练习----线性表的就地逆置

    千次阅读 2018-12-31 20:43:04
    题目:设元素值为整型的线性表L,采用顺序结构存储,编写程序,实现线性表的就地逆置 算法思想:已知表长length,经过length/2次循环,将位序为i(1&lt;=i&lt;=length/2)的数据元素与位序为length+1-i的数据...
  • 一道线性表练习题,有点麻烦,题目描述如下: 实验内容:实现一元多项式的加法、减法、乘法和求导。即: C(x)= A(x)+B(x);C(x)= A(x)-B(x) C(x)= A(x)*B(x) C(x)= A’(x) 菜单: 1)C :分别创建两个多项式A(x)...
  • 题目描述 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。 程序 #include <bits/stdc++.h>...
  • 线性表练习题1

    2021-08-06 17:05:08
    题目 从顺序表中具有最小值的元素(假设唯一)并由函数返回被删元素的值,空出的位置由最后一个元素填补,若顺序表为空,则显示出错信息并退出运行。 代码 #include <stdio.h> #define MaxSize 10 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,062
精华内容 2,024
关键字:

线性表练习