设顺序表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; }
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; }