C中输入任意多个数，排序
任意多是指事先不知道多少个数，在输入时想什么时候停止就停止，除了定义一个足够大的数组外，还有没有别的方法？不需要程序问我想输入多少个数（。。） 思路，用回车符判断输入结束就可以了 本帖最后由 Croper 于 2019-5-8 21:33 编辑
你这是两个问题：
第一：如何判断一串数字输入完毕的问题
1）确定输入的数字间以什么分割：最好空格或tab分割，这样可以使用scanf直接读取，其他的分割方式，如','分割，需要进行特殊处理
2）确定以什么标志输入结束，以及如何判断输入结束：如果以回车结束，需要用getchar判断'\n'符号，同时需要考虑空格接回车等不太规范的输入
第二、如何储存这些数字：
1) 申请一个足够大的数组，推荐
2）申请一个较小的数组，不够再使用realloc扩大容量，如果数据量非常大的话可考虑
3）链表，不推荐，排序的效率将会大大降低
反正思路就这样，怎么实现就看你了
Croper 发表于 2019-5-8 21:31
你这是两个问题：
第一：如何判断一串数字输入完毕的问题
1）确定输入的数字间以什么分割：最好空格或t ...
嗯，谢谢你的详细的补充。 Croper 发表于 2019-5-8 21:31
你这是两个问题：
第一：如何判断一串数字输入完毕的问题
1）确定输入的数字间以什么分割：最好空格或t ...
我认为链表的排序效率高过数组
链表只需要修改指针的指向就行了，数组需要移动大量数据元素，如果这个数据元素比较大的话，那效率更是不容乐观
本帖最后由 Croper 于 2019-5-8 22:53 编辑
人造人 发表于 2019-5-8 21:56
我认为链表的排序效率高过数组
链表只需要修改指针的指向就行了，数组需要移动大量数据元素，如果这个数 ...
嗯。。。同样的方法两者代码写出来都是同样的数量级(O或O，视排序方法不同),但是链表本神的访问就比数组要慢得多
（忘了在哪儿看的了，即使是a(链表就是head->next)这种访问，链表都要比数组慢一个数量级),
链表的优势在插入，和删除中间元素，但主流的排序方法除了插入排序，似乎涉及不到这一点，
所以除非插入排序，链表完全没有优势吧。 Croper 发表于 2019-5-8 22:50
嗯。。。同样的方法两者代码写出来都是同样的数量级(O或O，视排序方法不同),但是链表本神 ...
我又花时间研究了一下这部分的内容，我发现了我之前犯的错误，但是我依然没有找到 数组的排序效率高过链表的排序效率的方法
“我认为链表的排序效率高过数组
链表只需要修改指针的指向就行了，数组需要移动大量数据元素，如果这个数据元素比较大的话，那效率更是不容乐观”
数组需要移动大量数据元素
好的排序算法可以避免移动大量数据元素，但是对于数组，移动数据元素是不可避免的，而链表只需要修改指针
“我认为链表的排序效率高过数组
链表只需要修改指针的指向就行了，而数组需要移动数据元素，如果这个数据元素比较大的话，那效率更是不容乐观”
下面用代码说话
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
size_t id;
char name;
} user_info_t;
void swap(user_info_t *a, user_info_t *b)
{
user_info_t temp = *a;
*a = *b;
*b = temp;
}
// 按id排序
void sort(user_info_t info[], size_t size)
{
for(size_t i = 0; i < size; ++i)
{
for(size_t j = i + 1; j < size; ++j)
{
if(info.id > info.id)
swap(&info, &info);
}
}
}
int main(void)
{
printf("user_info_t size: %ld\n", sizeof(user_info_t));
user_info_t info;
for(size_t i = 0; i < 1024; ++i)
{
info.id = 1024 - i;
}
sort(info, 1024);
for(size_t i = 0; i < 1024; ++i)
printf("%ld ", info.id);
printf("\n");
return 0;
}
数组版本用时33ms
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
size_t id;
char name;
} user_info_t;
typedef user_info_t elem_type;
typedef struct node_tag
{
elem_type data;
struct node_tag *next;
} node_t;
typedef struct
{
node_t *head;
} list_t;
void list_init(list_t *l)
{
l->head = (node_t *)malloc(sizeof(node_t));
l->head->next = NULL;
}
void list_add(list_t *l, const elem_type *e)
{
node_t *node = (node_t *)malloc(sizeof(node_t));
node->data = *e;
node->next = l->head->next;
l->head->next = node;
}
void list_clear(list_t *l)
{
node_t *node = l->head->next;
while(node)
{
node_t *temp = node;
node = node->next;
free(temp);
}
l->head->next = NULL;
}
void list_traverse(const list_t *l)
{
node_t *node = l->head->next;
while(node)
{
printf("%ld ", node->data.id);
node = node->next;
}
printf("\n");
}
void list_destroy(list_t *l)
{
list_clear(l);
free(l->head);
l->head = NULL;
}
void swap(node_t *a, node_t *b)
{
node_t *temp = a->next;
a->next = b->next;
b->next = temp;
temp = a->next->next;
a->next->next = b->next->next;
b->next->next = temp;
}
// 按id排序
void sort(list_t *l)
{
for(node_t *i = l->head; i->next; i = i->next)
{
for(node_t *j = i->next; j->next; j = j->next)
{
if(i->next->data.id > j->next->data.id)
{
node_t *i_next = i->next;
swap(i, j);
if(i_next == j) // 如果i和j紧挨着，交换后j的指向会出错，这里修正一下
j = i->next;
}
}
}
}
int main(void)
{
printf("user_info_t size: %ld\n", sizeof(user_info_t));
user_info_t info = {0, {0}};
list_t l;
list_init(&l);
for(size_t i = 0; i < 1024; ++i)
{
info.id = i;
list_add(&l, &info);
}
sort(&l);
list_traverse(&l);
list_destroy(&l);
return 0;
}
链表版本用时21ms
因为链表版本只是修改指针指向，并不移动数据元素
我认为这个和排序算法无关，只要两者使用相同的排序算法，链表效率一定高过数组，这是我目前认为的，如果你不同意，请用代码说服我^_^
Croper 发表于 2019-5-8 22:50
嗯。。。同样的方法两者代码写出来都是同样的数量级(O或O，视排序方法不同),但是链表本神 ...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
size_t id;
char name;
} user_info_t;
typedef user_info_t elem_type;
typedef struct node_tag
{
elem_type data;
struct node_tag *next;
} node_t;
typedef struct
{
node_t *head;
} list_t;
void list_init(list_t *l)
{
l->head = (node_t *)malloc(sizeof(node_t));
l->head->next = NULL;
}
void list_add(list_t *l, const elem_type *e)
{
node_t *node = (node_t *)malloc(sizeof(node_t));
node->data = *e;
node->next = l->head->next;
l->head->next = node;
}
void list_clear(list_t *l)
{
node_t *node = l->head->next;
while(node)
{
node_t *temp = node;
node = node->next;
free(temp);
}
l->head->next = NULL;
}
void list_traverse(const list_t *l)
{
node_t *node = l->head->next;
while(node)
{
printf("%ld ", node->data.id);
node = node->next;
}
printf("\n");
}
void list_destroy(list_t *l)
{
list_clear(l);
free(l->head);
l->head = NULL;
}
void swap(node_t *a, node_t *b)
{
node_t *temp = a->next;
a->next = b->next;
b->next = temp;
temp = a->next->next;
a->next->next = b->next->next;
b->next->next = temp;
}
// 按id排序
void sort(list_t *l)
{
for(node_t *i = l->head; i->next; i = i->next)
{
for(node_t *j = i->next; j->next; j = j->next)
{
if(i->next->data.id > j->next->data.id)
{
node_t *i_next = i->next;
swap(i, j);
if(i_next == j) // 如果i和j紧挨着，交换后j的指向会出错，这里修正一下
j = i->next;
}
}
}
}
int main(void)
{
printf("user_info_t size: %ld\n", sizeof(user_info_t));
user_info_t info = {0, {0}};
list_t l;
list_init(&l);
for(size_t i = 0; i < 1024; ++i)
{
info.id = i;
list_add(&l, &info);
}
sort(&l);
list_traverse(&l);
list_destroy(&l);
return 0;
}
23ms，链表几乎不受数据元素大小的影响
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
size_t id;
char name;
} user_info_t;
void swap(user_info_t *a, user_info_t *b)
{
user_info_t temp = *a;
*a = *b;
*b = temp;
}
// 按id排序
void sort(user_info_t info[], size_t size)
{
for(size_t i = 0; i < size; ++i)
{
for(size_t j = i + 1; j < size; ++j)
{
if(info.id > info.id)
swap(&info, &info);
}
}
}
int main(void)
{
printf("user_info_t size: %ld\n", sizeof(user_info_t));
user_info_t info;
for(size_t i = 0; i < 1024; ++i)
{
info.id = 1024 - i;
}
sort(info, 1024);
for(size_t i = 0; i < 1024; ++i)
printf("%ld ", info.id);
printf("\n");
return 0;
}
350ms，因为数组在不停的移动数据元素
虽然说name预留4096字节有点夸张，但是这只是为了演示数据元素比较大的情况
name预留4096字节恐怕只有在这里才会出现，但是在现实中数据元素比较大的情况并不罕见
另外，上面也证明了可以用代码量换时间
数组46行，链表112行^_^
本帖最后由 Croper 于 2019-5-12 11:59 编辑
人造人 发表于 2019-5-11 22:24
23ms，链表几乎不受数据元素大小的影响
嗯，你提到了关于数组移动元素的问题，我之前按照楼主的意思，一直把这个数组默认为整数数组，移动元素的时间代价应该是很小的，所以完全没有考虑这一点，
不过你这么一说，我也做了下实验
排序方法以及排序时使用的元素：
//关于数组和链表排序速度的实验，排序方法：快排
#include <time.h>
#include <random>
#include <iostream>
using namespace std;
//数组和链表的大小
const int ARRSIZE = 100000;
//测试次数
const int TESTTIME = 10;
//数组排序
template <typename T>
void qsort(T* a, int size) {
struct ele {
T* a;
int size;
};
ele *stk = new ele;
int c_stk=0;
while (size>1){
int p = 0, q = size - 1;
T t = a;
T n = a;
while (q > p) {
if (n < t) {
a = n;
if (p + 1 < size) n = a;
}
else {
T tmp = a;
a = n;
n = tmp;
}
}
a = t;
int size2 = size - p - 1;
if (size2 > 1) stk={ a + p + 1,size2 };
size = p;
if (size < 2 && c_stk!=0) {
--c_stk;
size = stk.size;
a = stk.a;
}
}
}
//链表节点声明
template <typename T>
struct Node {
T val;
Node* next;
Node(T n) :val(n), next(nullptr) {};
};
//删除链表
template <typename T>
void dellist(Node<T>* head) {
while (head != nullptr) {
Node<T>* tmp = head->next;
delete head;
head = tmp;
}
}
//链表排序
template <typename T>
void qsort(Node<T>*& head) {
struct ele {
Node<T>** begin;
Node<T>* end;
};
ele *stk = new ele;
int c_stk = 0;
Node<T> **begin = &head;
Node<T> *end = nullptr;
while (*begin != end && (*begin)->next!=end) {
Node<T> *p = *begin;
Node<T> *mid = *begin;
Node<T> *& newhead=*begin;
while (p->next!=end) {
if (p->next->val < mid->val) {
Node<T>* tmp = p->next->next;
p->next->next = newhead;
newhead = p->next;
p->next = tmp;
}
else {
p = p->next;
}
}
if (mid->next != end && mid->next->next != end) {
stk = { &(mid->next),end };
}
end = mid;
if ((*begin==end || (*begin)->next == end) && c_stk!=0) {
--c_stk;
begin = stk.begin;
end = stk.end;
}
}
}
//这是能指定大小的需要排序的元素元素，重载了operator<();
template <int SIZE>
struct mulint {
int val;
mulint() {};
mulint(int n) {
val = n;
}
mulint& operator=(int n) {
val = n;
return *this;
}
bool operator<(const mulint& m2) {
return val < m2.val;
}
};
测试代码
template <int N>
void test() {
clock_t t1, t2;
t1 = t2 = 0;
for (int i = 0; i < TESTTIME; ++i) {
//初始化数组和链表，保证其中的元素完全一样
mulint<N> a;
Node<mulint<N>>* preb = new Node<mulint<N>>(0);
Node<mulint<N>>* p = preb;
for (int j = 0; j < ARRSIZE; ++j) {
int t = rand() % ARRSIZE;
a = t;
p->next = new Node<mulint<N>>(t);
p = p->next;
}
//测试排序时间
clock_t t = clock();
qsort(a, ARRSIZE);
t1 += clock() - t;
t = clock();
qsort(preb->next);
t2 += clock() - t;
dellist(preb);
}
cout <<"数据大小："<<N<< " 数组排序耗费时间：" << t1 << endl;
cout <<"数据大小："<<N<< " 链表排序耗费时间：" << t2 << endl;
}
int main() {
test<1>();
test<10>();
test<20>();
test<30>();
test<40>();
test<50>();
test<60>();
test<70>();
test<80>();
test<90>();
system("pause");
}
测试结果：
数据大小：1 数组排序耗费时间：784
数据大小：1 链表排序耗费时间：1059
数据大小：10 数组排序耗费时间：1279
数据大小：10 链表排序耗费时间：1026
数据大小：20 数组排序耗费时间：1454
数据大小：20 链表排序耗费时间：1082
数据大小：30 数组排序耗费时间：1486
数据大小：30 链表排序耗费时间：1124
数据大小：40 数组排序耗费时间：1661
数据大小：40 链表排序耗费时间：1134
数据大小：50 数组排序耗费时间：1677
数据大小：50 链表排序耗费时间：1147
数据大小：60 数组排序耗费时间：1735
数据大小：60 链表排序耗费时间：1194
数据大小：70 数组排序耗费时间：1772
数据大小：70 链表排序耗费时间：1167
数据大小：80 数组排序耗费时间：1670
数据大小：80 链表排序耗费时间：1177
数据大小：90 数组排序耗费时间：1830
数据大小：90 链表排序耗费时间：1220
嗯。。。看起来似乎数组并没有多大优势，
但是仔细想一想，似乎在哪里看过，数组访问速度的优势很大程度是因为其能通过基于cpu加速，而链表必须老老实实访问内存。
但是debug模式下，这个优势并没有得到体现，于是改成了release模式，再次测试：
数据大小：1 数组排序耗费时间：69
数据大小：1 链表排序耗费时间：265
数据大小：10 数组排序耗费时间：93
数据大小：10 链表排序耗费时间：324
数据大小：20 数组排序耗费时间：115
数据大小：20 链表排序耗费时间：350
数据大小：30 数组排序耗费时间：164
数据大小：30 链表排序耗费时间：394
数据大小：40 数组排序耗费时间：257
数据大小：40 链表排序耗费时间：405
数据大小：50 数组排序耗费时间：337
数据大小：50 链表排序耗费时间：424
数据大小：60 数组排序耗费时间：381
数据大小：60 链表排序耗费时间：520
数据大小：70 数组排序耗费时间：481
数据大小：70 链表排序耗费时间：445
数据大小：80 数组排序耗费时间：528
数据大小：80 链表排序耗费时间：424
数据大小：90 数组排序耗费时间：632
数据大小：90 链表排序耗费时间：520
结果比较明显了，在数据大小比较小的时候，数组排序的效率能达到链表的三到四倍左右。
在数据大小大概为70*sizeof(int)=280Byte左右，两者速度差不多；再大一些，就是链表的优势区了 本帖最后由 Croper 于 2019-5-12 11:57 编辑
之后继续想了一下。。数据大的话谁会到处移动数据啊。。
正常来说，不应该是建立一个索引，然后通过索引访问么。。？
所以再次试了一下，这次为数组建立索引，然后通过索引访问数组，排序时也只移动索引，不移动元素本身：
//索引
template <int N>
struct mptr {
mulint<N>* p;
bool operator<(const mptr& p2) {
return p->val < p2.p->val;
}
};
template <int N>
void test2() {
clock_t t1, t2;
t1 = t2 = 0;
for (int i = 0; i < TESTTIME; ++i) {
//初始化数组和链表，保证其中的元素完全一样
mulint<N> a;
Node<mulint<N>>* preb = new Node<mulint<N>>(0);
Node<mulint<N>>* p = preb;
for (int j = 0; j < ARRSIZE; ++j) {
int t = rand() % ARRSIZE;
a = t;
p->next = new Node<mulint<N>>(t);
p = p->next;
}
//建立数组的索引：
mptr<N> index;
for (int j = 0; j < ARRSIZE; ++j) {
index.p = a + j;
}
//测试排序时间
clock_t t = clock();
qsort(index, ARRSIZE);
t1 += clock() - t;
t = clock();
qsort(preb->next);
t2 += clock() - t;
dellist(preb);
}
cout << "数据大小：" << N << " 数组排序耗费时间：" << t1 << endl;
cout << "数据大小：" << N << " 链表排序耗费时间：" << t2 << endl;
}
int main() {
test2<1>();
test2<10>();
test2<20>();
test2<30>();
test2<40>();
test2<50>();
test2<60>();
test2<70>();
test2<80>();
test2<90>();
system("pause");
}
结果：
数据大小：1 数组排序耗费时间：118
数据大小：1 链表排序耗费时间：328
数据大小：10 数组排序耗费时间：112
数据大小：10 链表排序耗费时间：347
数据大小：20 数组排序耗费时间：129
数据大小：20 链表排序耗费时间：353
数据大小：30 数组排序耗费时间：136
数据大小：30 链表排序耗费时间：389
数据大小：40 数组排序耗费时间：136
数据大小：40 链表排序耗费时间：391
数据大小：50 数组排序耗费时间：140
数据大小：50 链表排序耗费时间：429
数据大小：60 数组排序耗费时间：149
数据大小：60 链表排序耗费时间：512
数据大小：70 数组排序耗费时间：150
数据大小：70 链表排序耗费时间：445
数据大小：80 数组排序耗费时间：157
数据大小：80 链表排序耗费时间：439
数据大小：90 数组排序耗费时间：153
数据大小：90 链表排序耗费时间：490
可以看到，通过索引访问数组之后，数组的排序速度基本是3倍于链表，
更不用说数组在随机访问等其他方面的优势了
所以综上：
我仍然认为链表的排序速度低于数组 Croper 发表于 2019-5-12 11:48
之后继续想了一下。。数据大的话谁会到处移动数据啊。。
正常来说，不应该是建立一个索引，然后通过索引访 ...
今天我花时间研究了一下这部分内容
只要把 数组中存储对象本身 改为 数组中存储对象指针，链表的排序优势就不复存在
你赢了^_^
但前提是 数组中存储对象指针
页:
[1]