我正在尝试创建一个程序,该程序将在4个步骤中对元素进行排序(读取元素-打印元素-对其进行排序-打印已排序的版本)。
我需要有关排序(第三部分)的帮助。
这是我的代码:
/*
* A simple program to sort numbers in correct order
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
#define SENTINEL -99
int main()
{
int tableFill(int a[], int max);
void tableInsert(int a[], int num, int val);
void tableSort(int a, int n);
void tablePrint(int a, int n);
int num;
int table[MAXSIZE];
int max;
num=tableFill(table,MAXSIZE);
return EXIT_SUCCESS;
}
int tableFill(int a[], int max)
{
int r; // input from scanf
int next; // score from user
int cnt = 0;
printf("Enter the numbers! \n");
while ((r=scanf("%i", &next))!= EOF && cnt<max)
{
if (r == 0) //invalid input data
{
printf("Nonnumeric data entered. Please enter a number. \n");
while (getchar()!= '\n'); // flush invalid data
}
else
a[cnt++]=next;
}
if(r==1) //another value was read but the array is full
printf("Error - too many values. Array size %i.\n", max);
}
void tableInsert (int a[], int num, int val)
{
int pos;
for(pos = num; pos>0 && val<a [pos-1]; pos--)
a [pos] = a [pos -1];
a[pos] = val;
}
void tableSort(int a, int n)
{
}
void tablePrint(int a, int n)
{
int i;
for(i = n -1; i>=0; i++)
{
printf("%i\n",a[i]);
}
}
解决方案
我使用了David C. Rankin的解决方案,并修复了我的代码。这是我的最终版本:
/*
* A simple program to sort numbers in the correct order
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10 //max elements in array
int main () {
int tableFill (int a[], int max);
void tableSort (int a[], int n);
void tablePrint (const a[], int n);
int arr[MAXSIZE]; //creating an array
int n = tableFill (arr, MAXSIZE); //declaring variable to work with array
tablePrint (arr, n); //prints unsorted values
printf ("Here is your sorted array:\n");
tableSort (arr, n); // sorts values in order
tablePrint (arr, n); // prints sorted values
return 0;
}
// read values from stdin into array up to 'max' values
int tableFill(int a[], int max) {
int r; // input from scanf
int next; // score from user
int cnt = 0; // loop variable
printf("Enter the numbers! \n");
while ((r=scanf("%i", &next))!= EOF && cnt<max)
{
if (r == 0) //invalid input data
{
printf("Nonnumeric data entered. Please enter a number. \n");
while (getchar()!= '\n'); // flush invalid data
}
else
a[cnt++]=next;
}
if(r==1) //another value was read but the array is full
printf("Error - too many values. Array size %i.\n", max);
return cnt;
}
// swap values at array indexes 'i' and 'j'.
void tableSwap (int a[], int i, int min_index)
{
int tmp = a[i];
a[i] = a[min_index];
a[min_index] = tmp;
}
//sort array
void tableSort (int a[], int n)
{
void tableSwap (int a[], int i, int min_index);
int i, j; //loop counters
int min, min_index; //adjusting variables for loops
for (i = 0; i <= n - 2; i++) {
min = a[i];
min_index = i;
for (j = i + 1; j <= n - 1; j++) {
if (a[j] < min){
min = a[j];
min_index = j;
}
}
tableSwap (a, i, min_index);
}
}
//print all elements in array.
void tablePrint (const a[], int n)
{
int i; //variable for print
for (i = 0; i < n; i++)
printf ("%d ", a[i]);
printf ("\n");
}
正如评论中指出的那样,它qsort
是C标准库中包含的事实上的标准排序例程。由于结合了针对分类的数据范围进行了优化的分类方法,因此它具有极大的灵活性和惊人的快速性。入门C用户通常很难编写比较函数,因为它涉及指针的使用。只需花一些时间编写一些比较函数就可以适应它-从长远来看,它将为您省去很多麻烦。
也就是说,在查看两种替代类型之前,C样式通常将小写形式用于变量和函数名称。为C ++保留camelCase名称。参见例如NASA-C样式指南,1994年
用旧的慢速冒泡排序。如果要对大于100个元素的任何东西进行分选,气泡冒口的效率高。它比qsort
任何大量元素都要慢数百倍。话虽这么说,将满足您tableswap
需求的bubblesort放在一起很简单:
/** sort array using slow old bubblesort */
void tablebubblesort (int *a, int n)
{
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) /* For decreasing order use < */
tableswap (a, n, j, j+1);
}
}
}
您的tableswap
函数将类似于:
/** swap values at array indexes 'i' and 'j'. */
void tableswap (int *a, int n, int i, int j)
{
if (i >= n || j >= n) return;
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
只需使用以下命令在代码中调用该函数 tablebubblesort (arr, n);
qsort
更简单。完整功能(您实际上不需要单独的功能)是:
/** qsort the array */
void tablesort (int *a, int n, size_t sz)
{
qsort (a, n, sz, compare);
}
它需要一个简单的比较功能:
/** qsort compare function */
int compare (const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}
不要仅仅因为看到const void *a
等等就让眼睛翻过头。这确实是直截了当的。您的a
和b
指针表示指向数组中各个整数的指针(例如,如果说a[1] = 5
,该指针只是&a[1]
元素的地址)。因此,将compare函数拆开,知道您只是传递一个要比较的元素(例如整数指针)的地址,就可以将其写成如下形式:
int compare (const void *a, const void *b)
{
int *value1 = (int *)a; /* cast each to int pointer */
int *value2 = (int *)b;
if (*value1 > *value2) /* compare dereferenced values */
return 1;
if (*value1 < *value2)
return -1;
return 0;
}
或者,如果它使您更快乐,则可以一次强制转换和取消引用所有对象,然后仅对整数值进行操作:
int compare (const void *a, const void *b)
{
int value1 = *(int *)a;
int value2 = *(int *)b;
if (value1 > value2)
return 1;
if (value1 < value2)
return -1;
return 0;
}
无论哪种方式都是一样的。(可以说,第一个是最合适的,因为它避免了类型调整指针和取消引用void值的“外观”,但这是另一天的事情)没有魔术,只需对整数,字符串,结构等做足够的次数..直到它沉没。这是值得的。
将其余部分放在一起,您可以通过类似于以下内容满足您的要求:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXI 128
int tablefill (int *a, int max);
void tableinsert (int *a, int *n, int max, int num, int val);
void tableswap (int *a, int n, int i, int j);
void tablesort (int *a, int n, size_t sz);
void tablebubblesort (int *a, int n);
void tableprint (int *a, int n);
int compare (const void *a, const void *b);
int main (void) {
int arr[MAXI] = {0};
int n = 0;
printf ("enter array values ([ctrl+d] to end)\n");
n = tablefill (arr, MAXI);
tableprint (arr, n);
printf ("\ninsert '5' as the '2nd' element of array\n");
tableinsert (arr, &n, MAXI, 2, 5);
tableprint (arr, n);
printf ("\nswap indexes '1' and '3'\n");
tableswap (arr, n, 1, 3);
tableprint (arr, n);
printf ("\nsorted array\n");
#ifdef WQSORT
tablesort (arr, n, sizeof *arr); /* gcc -DWQSORT to use tablesort */
#else
tablebubblesort (arr, n);
#endif
tableprint (arr, n);
return 0;
}
/** read values from stdin into array up to 'max' values. */
int tablefill (int *a, int max)
{
int idx = 0, tmp;
while (idx + 1 < max && scanf ("%d", &tmp) == 1)
a[idx++] = tmp;
return idx;
}
/** insert 'val' as the 'num' element in 'a' ('num - 1' index),
* update 'n' to current number of elements.
*/
void tableinsert (int *a, int *n, int max, int num, int val)
{
if (num >= max || *n + 1 == max) return;
if (num >= *n) { a[num] = val; (*n)++; return; }
int i;
for (i = *n; i >= num; i--)
a[i] = a[i-1];
a[i] = val;
(*n)++;
}
/** swap values at array indexes 'i' and 'j'. */
void tableswap (int *a, int n, int i, int j)
{
if (i >= n || j >= n) return;
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
/** qsort the array */
void tablesort (int *a, int n, size_t sz)
{
qsort (a, n, sz, compare);
}
/** sort array using slow old bubblesort */
void tablebubblesort (int *a, int n)
{
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) /* For decreasing order use < */
tableswap (a, n, j, j+1);
}
}
}
/** print all elements in array. */
void tableprint (int *a, int n)
{
if (!a) return;
int i;
for (i = 0; i < n; i++)
printf (" a[%2d] : %d\n", i, a[i]);
}
/** qsort compare function */
int compare (const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}
该代码包含排序的bubblesort
和qsort
版本。您只需将定义传递-DWQSORT
给qsort
代码进行编译,或者不带定义就进行编译bubblesort
。例如
编译两个版本
$ gcc -Wall -Wextra -Ofast -o bin/array_fill array_fill.c
$ gcc -Wall -Wextra -Ofast -DWQSORT -o bin/array_fill_qsort array_fill.c
使用/输出示例
$ echo "1 4 2 3" | ./bin/array_fill
enter array values ([ctrl+d] to end)
a[ 0] : 1
a[ 1] : 4
a[ 2] : 2
a[ 3] : 3
insert '5' as the '2nd' element of array
a[ 0] : 1
a[ 1] : 5
a[ 2] : 4
a[ 3] : 2
a[ 4] : 3
swap indexes '1' and '3'
a[ 0] : 1
a[ 1] : 2
a[ 2] : 4
a[ 3] : 5
a[ 4] : 3
sorted array
a[ 0] : 1
a[ 1] : 2
a[ 2] : 3
a[ 3] : 4
a[ 4] : 5
$ echo "1 4 2 3" | ./bin/array_fill_qsort
<same outoput>
查看所有代码,如果您有任何疑问,请告诉我。这是基本的肉类和土豆C,您需要确保您了解每一行以及每一行中的每个字符。慢慢来。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句