当前位置： 代码迷 >> 综合 >> 山东理工大学 顺序表练习题答案
  详细解决方案

山东理工大学 顺序表练习题答案

热度：84   发布时间：2023-10-23 08:52:00.0

使用需明白，我提供的代码并不是给大家抄的，而是给大家一个思路来做题。如果你一开始就会意错了的话（只会抄的话），你的水平永远不会得到大的飞跃，如果你还对自己有严格的要求的话，就可以略微参考一下。代码有什么不好或不对的地方欢迎提出。有什么不懂的地方可以尽可能的提出来，我会做解答。可以当面叫我解答（提供给我小组的成员）。(天啊！说的好官方啊！快被自己唬住了！)


顺序表应用1：多余元素删除之移位算法

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;const int MAX = 10005;
typedef struct
{int *elem;int length;
}Sq;void inti(Sq *L, int m)
{L->elem = (int *)malloc(MAX*4); //int类型代表的是4个字节，这里也可以写成sizeof(int)if ( !L->elem )exit(-1);                   //如果空间不足,这一步可以删除L->length = m;
}void create(Sq *L, int m)
{int i;for ( i = 0;i < m; i++ ){scanf ( "%d", &L->elem[i] );}
}void del(Sq *L,int m)
{int *p;for ( p = &L->elem[m]; p < L->elem + L->length-1 ; p++ ){*p = *(p+1);}L->length--;
}void ioc(Sq *L)
{int *p, *q;                     //建立两个指针q = L->elem;                    //让q指针指向第一个L串的位置坐标while ( q != L->elem+L->length )        //当q为L串中的最后一个元素时退出{p = q+1;                    //p指针代表的永远是q的前面的元素while ( p != L->elem+L->length ){if ( *p == *q ){del (L, (p-L->elem));   //(p-L->elem)代表的是一个数，相当于L串中的数组下标，以便准确找到该元素p--;                   //p在该时刻往前进了一个格这里需减去}p++;                       //千万不要忘了++}q++;}
}void display(Sq *L)
{int i;for ( i = 0;i < L->length; i++ ){printf (i != L->length-1 ? "%d " : "%d\n", L->elem[i]);}
}int main()
{int n, m;Sq L;scanf ( "%d", &n );while ( n-- ){scanf ( "%d", &m );inti(&L, m);create(&L, m);ioc(&L);display(&L);}return 0;
}

顺序表应用2：多余元素删除之建表算法 

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;const int MAX = 10005;
typedef struct
{int *elem;int length;
}Sq;void inti(Sq *L)
{L->elem = (int *)malloc(MAX*4);if ( !L->elem )exit(-1);L->length = 1;
}void create(Sq *L, int m)
{int i;for ( i = 0;i < m; i++ ){scanf ( "%d", &L->elem[i] );}
}void del(Sq *L, int h)
{L->elem[L->length] = L->elem[h];L->length++;
}void ioc(Sq *L, int m)
{int *p, *q;p = L->elem+1;while ( p < L->elem+m ){q = L->elem;int ok = 1;while ( q < p ){if ( *q == *p ){ok = 0;break;}q++;}if ( ok ){del(L, (p-L->elem));}p++;}
}void display(Sq *L)
{int i;for(i = 0;i < L->length; i++){printf(i != L->length-1 ? "%d " : "%d\n", L->elem[i]);}
}int main()
{int n, m;Sq L;scanf ( "%d", &n );while ( n-- ){scanf ( "%d", &m );inti(&L);create(&L, m);ioc(&L, m);display(&L);}return 0;
}


顺序表应用3：元素位置互换之移位算法 

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;const int MAX = 1000005;
typedef struct
{int *elem;int length;
}Sq;void inti(Sq *L, int n)
{L->elem = (int *)malloc(4*MAX);if ( !L->elem )exit(-1);L->length = n;
}void create(Sq *L, int n)
{int i;for ( i = 0;i < n; i++ ){scanf ( "%d", &L->elem[i] );}
}void ioc(Sq *L,int n, int m)
{int i, j, temp;for ( i = 0;i < m; i++ ){temp = L->elem[0];for ( j = 1;j < n; j++ ){L->elem[j-1] = L->elem[j];}L->elem[n-1] = temp;}
}void display(Sq *L)
{int i;for ( i = 0;i < L->length; i++ ){printf ( i == L->length-1 ? "%d\n" : "%d ", L->elem[i] );}
}int main()
{int T;int n, m;Sq L;scanf ( "%d", &T );while ( T-- ){scanf ( "%d %d", &n, &m );inti(&L, n);create(&L, n);ioc(&L, n, m);display(&L);}return 0;
}



顺序表应用4：元素位置互换之逆置算法 

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;const int MAX = 1000005;
typedef struct
{int *elem;int length;
}Sq;void inti(Sq *L, int n)
{L->elem = (int *)malloc(4*MAX);if ( !L->elem )exit(-1);L->length = n;
}void create(Sq *L, int n)
{int i;for ( i = 0;i < n; i++ ){scanf ( "%d", &L->elem[i] );}
}void rever(Sq *L, int be, int en)
{int i;int num = (en-be+1)/2;for ( i = 0;i < num; i++ ){int temp = L->elem[be];L->elem[be] = L->elem[en];L->elem[en] = temp;be++;en--;}
}void ioc(Sq *L,int n, int m)
{rever(L, 0, m-1);rever(L, m, n-1);rever(L, 0, n-1);
}void display(Sq *L)
{int i;for ( i = 0;i < L->length; i++ ){printf ( i == L->length-1 ? "%d\n" : "%d ", L->elem[i] );}
}int main()
{int T;int n, m;Sq L;scanf ( "%d", &T );while ( T-- ){scanf ( "%d %d", &n, &m );inti(&L, n);create(&L, n);ioc(&L, n, m);display(&L);}return 0;
}



顺序表应用5：有序顺序表归并 

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;const int MAX = 10005;
typedef struct
{int *elem;int length;
}Sq;void inti(Sq *L, Sq *M, Sq *S, int n, int m)
{L->elem = (int *)malloc(4*MAX);M->elem = (int *)malloc(4*MAX);S->elem = (int *)malloc(2*4*MAX);L->length = n;M->length = m;S->length = n+m;
}void create(Sq *L, Sq *M, int n, int m)
{int i;for ( i = 0;i < n; i++ ){scanf ( "%d", &L->elem[i] );}L->elem[i] = (1 << 30);for ( i = 0;i < m; i++ ){scanf ( "%d", &M->elem[i] );}M->elem[i] = (1 << 30);
}void ioc(Sq *L, Sq *M, Sq *S, int n, int m)
{int i, j, k;i = j = 0;for ( k = 0;k < S->length; k++ ){if(L->elem[i] < M->elem[j]){S->elem[k] = L->elem[i];i++;}else{S->elem[k] = M->elem[j];j++;}}
}void display(Sq *S)
{int i;for ( i = 0;i < S->length; i++ ){printf ( i == S->length-1 ? "%d\n" : "%d ", S->elem[i] );}
}int main()
{int n, m;Sq L, M, S;scanf ( "%d %d", &n, &m );inti(&L, &M, &S , n, m);create(&L, &M , n, m);ioc(&L, &M, &S , n, m);display(&S);return 0;
}



顺序表应用6：有序顺序表查询 

#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
using namespace std;const int MAX = 10005;
typedef struct
{int *elen;int length;
}Sq;void create(Sq *L, int m)
{int i;L->elen = (int *)malloc(MAX*4);for( i = 0;i < m; i++ ){scanf ( "%d", &L->elen[i] );}L->length = m;
}int locList(Sq *L, int num)
{int left = 0;int right = L->length-1;while(left <= right){int mid = (right+left)/2;if(L->elen[mid] == num){return mid+1;}else if(L->elen[mid] < num){left = mid+1;}else if(L->elen[mid] > num){right = mid-1;}}return -1;
}int main()
{Sq L;int n,m,i,h;scanf("%d",&n);create(&L, n);scanf("%d",&m);for(i = 0;i < m; i++){scanf ( "%d", &h );int flag = locList(&L,h);if ( flag == -1 )printf ( "No Found!\n" );elseprintf ( "%d\n", flag );}return 0;
}



顺序表应用4-2：元素位置互换之逆置算法(数据改进） 

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;const int MAX = 1000005;
typedef struct
{int *elem;int length;
}Sq;void inti(Sq *L, int n)
{L->elem = (int *)malloc(4*MAX);if ( !L->elem )exit(-1);L->length = n;
}void create(Sq *L, int n)
{int i;for ( i = 0;i < n; i++ ){scanf ( "%d", &L->elem[i] );}
}void rever(Sq *L, int be, int en)
{int i;int num = (en-be+1)/2;for ( i = 0;i < num; i++ ){int temp = L->elem[be];L->elem[be] = L->elem[en];L->elem[en] = temp;be++;en--;}
}void ioc(Sq *L,int n, int m)
{rever(L, 0, m-1);rever(L, m, n-1);rever(L, 0, n-1);
}void display(Sq *L)
{int i;for ( i = 0;i < L->length; i++ ){printf ( i == L->length-1 ? "%d\n" : "%d ", L->elem[i] );}
}int main()
{int T;int n, m;Sq L;scanf ( "%d", &n );inti(&L, n);create(&L, n);scanf ( "%d", &T );while ( T-- ){scanf ( "%d", &m );ioc(&L, n, m);display(&L);}return 0;
}



顺序表应用7：最大子段和之分治递归法

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;const int MAX = 50005;
typedef struct
{int *elem;int length;
}Sq;
int ant, max1;void inti(Sq *L, int n)
{L->elem = (int *)malloc(4*MAX);if ( !L->elem )exit(-1);L->length = n;
}void create(Sq *L, int n)
{int i;for ( i = 0;i < n; i++ ){scanf ( "%d", &L->elem[i] );}
}void comput(Sq *L, int be, int mid, int en)
{int i;int left_size = 0, right_size = 0;int sum = 0;for ( i = mid;i >= be; i-- ){sum = sum+L->elem[i];if ( left_size < sum )left_size = sum;}sum = 0;for ( i = mid+1;i <= en; i++ ){sum = sum+L->elem[i];if ( right_size < sum )right_size = sum;}int max_size = left_size+right_size;if (max_size > max1)max1 = max_size;
}void ioc(Sq *L, int be, int en)
{ant++;if ( be != en ){int mid = (be+en)/2;ioc(L, be, mid);ioc(L, mid+1, en);comput(L, be, mid, en);}return ;
}int main()
{int n;Sq L;ant = max1 = 0;scanf ( "%d", &n );inti(&L, n);create(&L, n);ioc(&L, 0, n-1);printf ( "%d %d\n", max1, ant);return 0;
}



顺序表应用8：最大子段和之动态规划法
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;const int MAX = 100005;
typedef struct
{int *elem;int length;
}Sq;void inti(Sq *L, int n)
{L->elem = (int *)malloc(4*MAX);
}void create(Sq *L, int n)
{int i, k;for ( i = 0;i < n; i++ ){scanf ( "%d", &k );if ( i != 0 ){if (L->elem[i-1] < 0)L->elem[i] = k;elseL->elem[i] = L->elem[i-1]+k;}elseL->elem[0] = k;}
}int ioc(Sq *L, int n)
{int i;int max1 = 0;for ( i = 0;i < n; i++ ){if (max1 < L->elem[i])max1 = L->elem[i];}return max1;
}int main()
{int n;Sq L;scanf ( "%d", &n );inti(&L, n);create(&L, n);int max1 = ioc(&L, n);printf ( "%d\n", max1 );return 0;
}



代码菜鸟，如有错误，请多包涵！！！

如有帮助记得支持我一下，谢谢！！！

  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.