精华内容
下载资源
问答
  • PTA1.9 有序数组插入

    2021-07-24 20:28:52
    PTA1.9

    题目

    本题要求将任一给定元素插入从大到小排好序的数组中合适的位置,以保持结果依然有序。

    L是用户传入的一个线性表,其中ElementType元素可以通过>、==、<进行比较,并且题目保证传入的数据是递减有序的。函数Insert要将X插入Data[]中合适的位置,以保持结果依然有序(注意:元素从下标0开始存储)。
    但如果X已经在Data[]中了,就不要插入,返回失败的标记false;如果插入成功,则返回true。
    另外,因为Data[]中最多只能存MAXSIZE个元素,所以如果插入新元素之前已经满了,也不要插入,而是返回失败的标记false。

    测试程序:

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 10 typedef enum {false, true} bool; typedef int ElementType;
    
    typedef int Position; typedef struct LNode *List; struct LNode {
        ElementType Data[MAXSIZE];
        Position Last; /* 保存线性表中最后一个元素的位置 */ };
    
    List ReadInput(); /* 裁判实现,细节不表。元素从下标0开始存储 */ void PrintList( List L );
    /* 裁判实现,细节不表 */ bool Insert( List L, ElementType X );
    
    int main() {
        List L;
        ElementType X;
    
        L = ReadInput();
        scanf("%d", &X);
        if ( Insert( L, X ) == false )
            printf("Insertion failed.\n");
        PrintList( L );
    
        return 0; }
    
    /* 你的代码将被嵌在这里 */ ```
    

    代码1

    bool Insert(List L, ElementType X)
    {
        int i;
    	if (L->Last >= MAXSIZE - 1) return false;//用MAXSIZE-1作为判断条件
        for (i = L->Last; i >= 0; i --)
            if (L->Data[i] == X) return false;//判断是否有与X相同的元素
    	for (i = L->Last; i >= 0; i --)
    	{
    		if (L->Data[i] < X) L->Data[i + 1] = L->Data[i];
    		else break;
    	}
    	L->Data[i + 1] = X;//插在任意位置均适用
    	L->Last ++;
    	return true;
    }
    

    代码2

    bool Insert(List L, ElementType X)
    { 
    	int i = 0;
    	if (L->Last == MAXSIZE - 1) return false;
    	while (X < L->Data[i]) i ++;//先找到最后一个比x大的再判断下个数是否=x 
    	if (L->Data[i] == X) return false;
    	int temp = i;
    	for (i = L->Last; i >= temp; i --) L->Data[i + 1] = L->Data[i];//先后移
        L->Data[temp] = X;
        L->Last ++;     //别忘了+1                   
    	return true;
    }
    
    展开全文
  • 本题要求将任一给定元素插入从大到小排好序的数组中合适的位置,以保持结果依然有序。 /*函数接口定义:*/ bool Insert( List L, ElementType X ); /*其中List结构定义如下:*/ typedef int Position; typedef ...

    题目描述

    本题要求将任一给定元素插入从大到小排好序的数组中合适的位置,以保持结果依然有序。

    /*函数接口定义:*/
    bool Insert( List L, ElementType X );
    
    /*其中List结构定义如下:*/
    typedef int Position;
    typedef struct LNode *List;
    struct LNode {
        ElementType Data[MAXSIZE];
        Position Last; /* 保存线性表中最后一个元素的位置 */
    };
    

    L是用户传入的一个线性表,其中ElementType元素可以通过>、==、<进行比较,并且题目保证传入的数据是递减有序的。函数Insert要将X插入Data[]中合适的位置,以保持结果依然有序(注意:元素从下标0开始存储)。但如果X已经在Data[]中了,就不要插入,返回失败的标记false;如果插入成功,则返回true。另外,因为Data[]中最多只能存MAXSIZE个元素,所以如果插入新元素之前已经满了,也不要插入,而是返回失败的标记false。

    分析:
    因为数据是递减有序的,所以我们需要遍历线性表找到线性表中第一个小于我们要插入的数据的数的下标值,再将该下标值之后的数据都向后移一位,然后将要插入的值赋给该下标就可以了。

    完整代码:

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 10
    typedef enum {false, true} bool;
    typedef int ElementType;
    
    typedef int Position;
    typedef struct LNode *List;
    struct LNode {
        ElementType Data[MAXSIZE];
        Position Last; /* 保存线性表中最后一个元素的位置 */
    };
    
    List ReadInput(); /* 初始化线性表,输入数据,元素从下标0开始存储 */
    void PrintList( List L ); /* 打印线性表 */
    bool Insert( List L, ElementType X );/* 插入数据 */
    
    int main()
    {
        List L;
        ElementType X;
    
        L = ReadInput();
        scanf("%d", &X);///输入要插入的值
        if ( Insert( L, X ) == false )
            printf("Insertion failed.\n");
        PrintList( L );
    
        return 0;
    }
    
    /*初始化线性表具体实现*/
    List ReadInput(){
        List L;
        int i;
        int num;
        L=(List)malloc(sizeof(struct LNode));///为线性表申请空间
        L->Last=-1;
        scanf("%d",&num);
        getchar();
        for(i=0;i<num;i++){
            scanf("%d",&L->Data[i]);
            L->Last++;
        }
        return L;
    
    }
    
    /* 插入数据具体实现 */
    bool Insert( List L, ElementType X ){
        int i,j;
        if(L->Last==MAXSIZE-1){ 
            return false;///如果未插入前线性表已满,返回false
        }
        for(i=0;i<=L->Last;i++){
            if(X==L->Data[i]){
                return false;///如果线性表中已有要插入的数据,返回false
            }else if(X>L->Data[i]){
                break;///找到了要插入的数据的下标,退出循环
            }
        }
        for(j=L->Last;j>=i;j--){
            L->Data[j+1]=L->Data[j];///将要插入的下标之后的数据都向后移一位
        }
        L->Data[j+1]=X;///插入数据到下标位置
        L->Last++;
        return true;
    }
    
    /*打印线性表具体实现*/
    void PrintList( List L ){
        int i;
        for(i=0;i<=L->Last;i++){
            printf("%d ",L->Data[i]);
        }
    }
    
    展开全文
  • 本题要求将任一给定元素插入从大到小排好序的数组中合适的位置,以保持结果依然有序。 函数接口定义: bool Insert( List L, ElementType X ); 其中List结构定义如下: typedef int Position; typedef struct LNode...

    本题要求将任一给定元素插入从大到小排好序的数组中合适的位置,以保持结果依然有序。

    函数接口定义:

    bool Insert( List L, ElementType X );
    

    其中List结构定义如下:

    typedef int Position;
    typedef struct LNode *List;
    struct LNode {
        ElementType Data[MAXSIZE];
        Position Last; /* 保存线性表中最后一个元素的位置 */
    };
    

    L是用户传入的一个线性表,其中ElementType元素可以通过>、==、<进行比较,并且题目保证传入的数据是递减有序的。函数Insert要将X插入Data[]中合适的位置,以保持结果依然有序(注意:元素从下标0开始存储)。但如果X已经在Data[]中了,就不要插入,返回失败的标记false;如果插入成功,则返回true。另外,因为Data[]中最多只能存MAXSIZE个元素,所以如果插入新元素之前已经满了,也不要插入,而是返回失败的标记false。

    裁判测试程序样例:

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 10
    typedef enum {false, true} bool;
    typedef int ElementType;
    
    typedef int Position;
    typedef struct LNode *List;
    struct LNode {
        ElementType Data[MAXSIZE];
        Position Last; /* 保存线性表中最后一个元素的位置 */
    };
    
    List ReadInput(); /* 裁判实现,细节不表。元素从下标0开始存储 */
    void PrintList( List L ); /* 裁判实现,细节不表 */
    bool Insert( List L, ElementType X );
    
    int main()
    {
        List L;
        ElementType X;
    
        L = ReadInput();
        scanf("%d", &X);
        if ( Insert( L, X ) == false )
            printf("Insertion failed.\n");
        PrintList( L );
    
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    

    输入样例1:

    5
    35 12 8 7 3
    10
    

    输出样例1:

    35 12 10 8 7 3
    Last = 5
    

    输入样例2:

    6
    35 12 10 8 7 3
    8
    

    输出样例2:

    Insertion failed.
    35 12 10 8 7 3
    Last = 5
    
    bool Insert( List L, ElementType X ){//插入先判断是否装满 
    	int i=0,j;
    	if(L->Last==MAXSIZE-1)
    		return false;
    	while(X<L->Data[i])//先找到最后一个比x大的再判断下个数是否=x 
           i++;
    	if((L->Data[i])==X)
    		return false;
    	j=i;
    	for(i=L->Last;i>=j;i--)//先后移 
    		L->Data[i+1]=L->Data[i];
        L->Data[j]=X;
        L->Last++;     //别忘了+1                   
    	return true;
    }
    
    展开全文
  • 6-3 有序数组插入 (20分) 本题要求将任一给定元素插入从大到小排好序的数组中合适的位置,以保持结果依然有序。 函数接口定义: bool Insert( List L, ElementType X ); 其中List结构定义如下: typedef int ...

    6-3 有序数组的插入 (20分)
    本题要求将任一给定元素插入从大到小排好序的数组中合适的位置,以保持结果依然有序。

    函数接口定义:

    bool Insert( List L, ElementType X );
    

    其中List结构定义如下:

    typedef int Position;
    typedef struct LNode *List;
    struct LNode {
        ElementType Data[MAXSIZE];
        Position Last; /* 保存线性表中最后一个元素的位置 */
    };
    

    L是用户传入的一个线性表,其中ElementType元素可以通过>、==、<进行比较,并且题目保证传入的数据是递减有序的。函数Insert要将X插入Data[]中合适的位置,以保持结果依然有序(注意:元素从下标0开始存储)。但如果X已经在Data[]中了,就不要插入,返回失败的标记false;如果插入成功,则返回true。另外,因为Data[]中最多只能存MAXSIZE个元素,所以如果插入新元素之前已经满了,也不要插入,而是返回失败的标记false。

    裁判测试程序样例:

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 10
    typedef enum {false, true} bool;
    typedef int ElementType;
    
    typedef int Position;
    typedef struct LNode *List;
    struct LNode {
        ElementType Data[MAXSIZE];
        Position Last; /* 保存线性表中最后一个元素的位置 */
    };
    
    List ReadInput(); /* 裁判实现,细节不表。元素从下标0开始存储 */
    void PrintList( List L ); /* 裁判实现,细节不表 */
    bool Insert( List L, ElementType X );
    
    int main()
    {
        List L;
        ElementType X;
    
        L = ReadInput();
        scanf("%d", &X);
        if ( Insert( L, X ) == false )
            printf("Insertion failed.\n");
        PrintList( L );
    
        return 0;
    }
    

    /* 你的代码将被嵌在这里 */
    输入样例1:
    5
    35 12 8 7 3
    10
    输出样例1:
    35 12 10 8 7 3
    Last = 5
    输入样例2:
    6
    35 12 10 8 7 3
    8
    输出样例2:
    Insertion failed.
    35 12 10 8 7 3
    Last = 5

    AC代码

    Position BinarySearch( List L, ElementType X )
    {
     int low = 1, high = L->Last+1,mid;
     while (low <= high)
     {
           mid = (low + high) / 2;
            if (L->Data[mid]<X)
                high = mid - 1;
            else if (L->Data[mid]>X)
                low = mid + 1;
            else
                return 1;
     }
     return 0;
    
    }
    bool Insert(List L, ElementType X)
    {
     int pos,i,j;
     if (L->Last + 1 >= MAXSIZE||1==BinarySearch(L, X)) return false;
        
     for ( i = 0; i <= L->Last; ++i)
      if (L->Data[i] <= X) break;
      pos=i;
     for (int j = L->Last;j>=pos; j--){
         L->Data[j+1] = L->Data[j];
     }  
      L->Data[pos] = X;
      L->Last++;
     return true;
    }
    

    话说结果里“Last = 5”是什么意思啊=͟͟͞͞( ‘ヮ’ 三 ‘ヮ’ =͟͟͞͞) 
    没看明白

    写完之后突然意识到,
    我为什么非得折腾半天用二分啊=͟͟͞͞( ‘ヮ’ 三 ‘ヮ’ =͟͟͞͞)
    算了算了练练手不亏

    不用二分

    bool Insert( List L, ElementType X )
    {
        if(L -> Last + 1 == MAXSIZE)//满了
            return false;
        for (int i = 0; i <= L -> Last; i++ )
        {
            if (L -> Data[i] == X) //已经有了
                return false;
            else if (L -> Data[i] < X)
            {
                for (int j = L ->Last; j >= i; j -- )//i之后的后移一位
                {
                    L -> Data[j + 1] = L -> Data[j];
                }
                L->Data[i] = X;
                L->Last ++;
                break;
            }
            else if (i==L->Last && L->Data[i]> X)//插在最后一位
            {
                L->Data[L->Last+1] = X;
                L->Last ++;
                break;
            }
        }
        return true;
    }
    
    展开全文
  • C语言:编写一个指针函数,向一个有序数组插入一个数据,保持数组的有序性。 #include <stdio.h> void f(int* a, int m) { int end, temp1, temp2; int i, j; //a[9]=64,是目前数组a的最后一个元素 //...
  • PTA|习题1.9 有序数组插入 (20 分) 关于本篇说明 数据结构渣渣,好不容易自己写出来一个,当时在网上找了很多都是暴力查找要插入的位置然后插入,比较慢,所以就用了类似二分查找的方法先找到要插入的位置,然后...
  • PTA - 插入有序数组

    千次阅读 2019-06-22 09:15:40
    插入有序数组 一个长度为10的数组中输入n(0≤n≤9)个整数,这n个整数从小到大有序。再输入一个x,把它插入数组适当位置,使数组仍保持有序。 输入格式: 输入n,再以从小到大顺序输入n个整数,再输入x。 输出格式: ...
  • 有序数组插入

    2020-03-03 19:48:28
    1.9 有序数组插入 (20分) 本题要求将任一给定元素插入从大到小排好序的数组中合适的位置,以保持结果依然有序。 函数接口定义: bool Insert( List L, ElementType X ); 其中List结构定义如下: typedef int ...
  • 有序数组插入 本题要求将任一给定元素插入从大到小排好序的数组中合适的位置,以保持结果依然有序。 函数接口定义: bool Insert( List L, ElementType X ); 其中List结构定义如下: typedef int Position; ...
  • 习题1.9 有序数组插入 (20分) 本题要求将任一给定元素插入从大到小排好序的数组中合适的位置,以保持结果依然有序。 函数接口定义: bool Insert( List L, ElementType X ); 其中List结构定义如下: typedef int ...
  • 6-1 有序数组插入 (20分) 这个我居然试了半天~。。 本题要求将任一给定元素插入从大到小排好序的数组中合适的位置,以保持结果依然有序。 函数接口定义: bool Insert( List L, ElementType X ); 其中List结构定义...
  • #include  int main()  ... /* 定义一个含有9个数据的数组 */ int i,m,n;  printf("请输入一个数据:");  scanf("%d",&n);/* 输入一个新的数据 */ for (i=0;i {  if (n { m=i; break; } /* 用
  • L是用户传入的一个线性表,其中ElementType元素可以通过>、==、Insert要将X插入Data[]中合适的位置,以保持结果依然有序(注意:元素从下标0开始存储)。但如果X已经在Data[]中了,就不要插入,返回失败的标记false...
  • PTA—习题1.9 有序数组插入 (20 分)

    千次阅读 2019-07-21 16:55:25
    大数据用MAXSIZE判断,不能用10 bool Insert( List L, ElementType X ) { int i=0,tag; while(L->Data[i]>X) { i++; } tag=i; if(L->Data[i]==X||(L->Last+1)>=MAXSIZE) ...
  • 本题要求将任一给定元素插入从大到小排好序的数组中合适的位置,以保持结果依然有序。 函数接口定义: bool Insert( List L, ElementType X ); 其中List结构定义如下: typedef int Position; typedef struct ...
  • 4. 合并两个有序数组

    2021-04-08 15:02:57
    给你两个有序整数数组nums1 和 nums2,请你将 nums2 合并到nums1中,使 nums1 成为一个有序数组。 初始化nums1 和 nums2 的元素数量分别为m 和 n 。你可以假设nums1 的空间大小等于m + n,这样它就有足够的空间保存...
  • PTA jmu-ds-有序插入数据 (25 分) 要求实现3个函数,在递增的顺序表中插入一个新整数,并保持该顺序表的有序性。 typedef int ElemType; typedef struct { ElemType data[MaxSize]; //存放顺序表元素 int ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 488
精华内容 195
关键字:

pta有序数组的插入