首页 > 试题广场 >

设顺序表va中的数据元素递增有序,试写一算法,将x插入到顺序

[问答题]

设顺序表va中的数据元素递增有序,试写一算法,将x插入到顺序表的适当位置上,保持该表有序。

#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREAMENT 10

typedef struct {
	int *data;
	int length;
	int listsize;
}Sqlist;

void initlist( Sqlist * );
void input_sort( Sqlist *, int );
void sortlist( Sqlist * );
void insert( Sqlist *, int );
void show( Sqlist * );
int find_pos( Sqlist *, int ); 

int main ()
{
	int k, flag, x;
	Sqlist va;
	initlist ( &va );
	printf ( "当前可输入数据个数为0-%d,请输入你想要输入的数据个数:", va.listsize - va.length  );
	flag = 1;
	while ( flag )
	{
		scanf ( "%d", &k );
		if ( k < 0 || k > va.listsize - va.length )
			printf ( "您输入的数值不合法,请重新输入:" );
		else
			flag = 0;
	}
	if ( k != 0 )
	{
		printf ( "\n请输入数据:\n" );
		input_sort( &va, k );
	}
	show( &va );
	printf ( "\n请输入你要插入的数据:" );
	scanf ( "%d", &x );
	insert ( &va, x );
	show( &va );
	printf ( "\n" );
	system ( "pause" );
	return 0;
}

void initlist( Sqlist *va )
{
	va->data = ( int* )malloc( sizeof( int ) * LIST_INIT_SIZE );
	if ( NULL == va->data )
	{
		printf ( "动态内存分配失败,终止程序。" );
		exit( -1 );
	}
	else
	{
		va->length = 0;
		va->listsize = LIST_INIT_SIZE;
	}
	return;
}

void input_sort( Sqlist *va, int k )
{
	int i, m;
	for ( i = 0;i < k;i++ )
	{
		scanf ( "%d", &m );
		va->data[i] = m;
		va->length++;
	}
	sortlist ( va );
}

void sortlist( Sqlist *va )
{
	int i, j, temp;
	for ( i = 0;i < va->length;i++ )
	{
		for ( j = i + 1;j < va->length;j++ )
			if ( va->data[i] > va->data[j] )
			{
				temp = va->data[i];
				va->data[i] = va->data[j];
				va->data[j] = temp;
			}
	}
}

void insert( Sqlist *va, int x )
{
	int i, pos;
	pos = find_pos( va, x );
	if ( pos < va->length )
		for ( i = va->length - 1;i >= pos;i-- )
			va->data[i+1] = va->data[i];
	va->data[pos] = x;
	va->length++;
}

void show( Sqlist *va )
{
	int i = 0;
	printf ( "该顺序表为:" );
	for ( i = 0;i < va->length;i++ )
		printf ( "%d  ", va->data[i] );
}

int find_pos( Sqlist *va, int x )
{
	int pos;
	for ( pos = 0;pos < va->length;pos++ )
		if ( x <= va->data[pos] )
			return pos;
	return pos;
}

发表于 2019-12-17 21:03:37 回复(0)
新手初学数据结构,如有错误,请诸位大神斧正,共同进步
typedef struct SeqList
{
    int *data;
    int size;
    int last;
} list_t;

int insert(list_t *va, int x)
{
    int i;
    if (va->last == list->size - 1)
    {
        printf("顺序表已满无法插入!\n");
        return -1;
    }
    else
    {
        for (i = va->last; i >= 0 && va->data[i] > x; i--)
        {
            va->data[i + 1] = va->data[i];
        }
        va->data[i + 1] = x;
        va->last++;
    }
    return 0;
}


编辑于 2018-03-21 18:47:41 回复(0)