为什么链表没有排序? [英] why linked list are not sorted?
本文介绍了为什么链表没有排序?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我尝试为字符串创建链表，并使用它们的分数进行排序，但是我的排序算法却无济于事.谢谢您的任何建议和帮助.
I try to make linked list for string and sort with their score but my sorting algorithm is doing nothing. Thank you for any advice and help.
void SortList(Linked_List *list) {
Node *temp, *index = NULL;
temp = list->head;
int tmp;
if (list->head == NULL) {
return;
} else {
while (temp != NULL) {
index = temp->next;
while (index != NULL) {
if (temp->score > index->score) {
tmp = temp->score;
temp->score = index->score;
index->score = tmp;
}
index = index->next;
}
temp = temp->next;
}
}
}
这是我的结构定义:
typedef struct Node {
void *data;
int score;
struct Node *next;
} Node;
typedef struct {
Node *head;
} Linked_List;
这是我的主要方法(我删除了前两种情况，因为它们与我的问题无关):
here is my main method(i removed first 2 cases because they are not related to my problem):
int main()
{
FILE *fp,*fp2,*fp3;
int bufferLength = 99;
char line[RSIZ][LSIZ];
char str[RSIZ][LSIZ];
int k,point=0;
Linked_List* char_list = create_empty_list();
char buffer[bufferLength];
char password[99];
int counter=0,len1=0,len2=0,choice,i=0,tot=0,j;
bool quit = false;
这是swtich案例方法:
and here is swtich case method:
while(!quit){
printf("\t\t\t3.LinkedList:\n");
printf("\t\t\tAny other to exit():\n");
scanf("%d",&choice);
switch(choice){
case 3:
fp3 = fopen("10-million-password-list-top/1000.txt","r");
if(fp3==NULL){
printf("Could not open the file\n");
}
while(fgets(str[k],LSIZ,fp3)){
str[k][strlen(str[k])-1]= '\0';
Linked_List* char_list = create_empty_list();
char_list->head = insert_end(char_list, str[k]);
计算密码强度的时间长于我删除的密码强度，对于此问题而言，这是不必要的细节.
calculating password strength it is longer than this one i removed it is unnecessary detail for this problem.
int j;
for(j=0;str[k][j]!=0;j++){
if(str[k][j]>=97 && str[k][j]<=122){ //lowercase
point+=3;
}
else if(str[k][j]>=48 && str[k][j]<=57){ //digits
point+=10;
}}
Scoring(char_list,point);
point=0;
k++;
SortList(char_list);
display(char_list);
printf("\n");
}break;
default:
quit=true;
break;
}}
free_list(char_list);
fclose(fp2);
return 0;
}
推荐答案
您正在交换节点中的数据，而不是链接指针.
You're swapping the data in the nodes, instead of the link pointers.
尽管您可以执行此操作，但是通常只有链接指针会被交换.假设您的 struct (另外)具有类似 int array [1000000]; 作为元素.您必须交换那个，与仅更改指针相比，它会非常慢.
While you can do this, normally, only the link pointers get swapped. Suppose your struct had (in addition), something like: int array[1000000]; as an element. You'd have to swap that and that would be very slow compared to just changing pointers.
而且，您只需做一次 传递数据.因此，您可能会在列表的最前面获得最低的值，但是所有其他值将保持未排序状态.
And, you only doing one pass on the data. So, you might get the lowest value at the front of the list, but all the others will remain unsorted.
也就是说，对于具有N个元素和简单排序(复杂度为O(N ^ 2))的列表，您需要N次通过.
That is, for a list with N elements, and simple sorts (with O(N^2) complexity), you need N passes.
我不得不重构一下代码.
I had to refactor your code a bit.
我想出的算法是要有一个临时的目的地".列出[最初为空].
The algorithm I came up with is to have a temporary "destination" list [initially empty].
对于每遍，都会扫描原始列表以查找最小/最低元素.
For each pass, the original list is scanned for the smallest/lowest element.
该元素从源列表中删除并附加到目标列表中.
That element is removed from the source list and appended to the destination list.
最后，临时列表头的地址被复制到原始列表的 head 元素中.
At the end, the address of the head of the temp list is copied into the original list's head element.
无论如何，这是代码.我试图尽可能地对其进行注释.它可以干净地编译，我已经在办公桌上检查了它的正确性.但是，我没有对其进行测试，因此可能存在一些错误.但是，它应该可以帮助您入门.
Anyway, here is the code. I tried to annotate it as much as possible. It compiles cleanly and I've desk checked it for correctness. But, I didn't test it, so it may have some bugs. But, it should get you started.
#include <stdio.h>
typedef struct Node {
void *data;
int score;
struct Node *next;
} Node;
typedef struct {
Node *head;
} Linked_List;
void
SortList(Linked_List *srclist)
{
Node *dsthead = NULL;
Node *dstprev = NULL;
// do N passes on the list
while (1) {
// get next element in source list -- stop when empty
Node *srcbest = srclist->head;
if (srcbest == NULL)
break;
// find smallest node in remaining list
Node *bestprev = NULL;
Node *curprev = NULL;
for (Node *cursrc = srcbest; cursrc != NULL; cursrc = cursrc->next) {
if (cursrc->score < srcbest->score) {
srcbest = cursrc;
bestprev = curprev;
}
curprev = cursrc;
}
// add selected node to tail of destination list
if (dsthead == NULL)
dsthead = srcbest;
else
dstprev->next = srcbest;
dstprev = srcbest;
// remove selected node from source list
if (bestprev != NULL)
bestprev->next = srcbest->next;
else
srclist->head = srcbest->next;
// fix the tail of destination list
dstprev->next = NULL;
}
// set new head of original list
srclist->head = dsthead;
}
更新:
我也尝试过此操作，但仍然没有排序给我相同的链表.
i tried this one also but still does not sort gives me same linked list.
自从我的原始帖子以来，我创建了一个测试程序.该算法有效(如发布).因此，您的代码中还必须包含其他内容.
Since my original post, I created a test program. The algorithm works [as posted]. So, there must be something else within your code.
该算法类似于插入排序.我添加了气泡排序变体.
The algorithm was similar to an insertion sort. I added a bubble sort variant.
这是完整的工作代码:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Node {
void *data;
int score;
struct Node *next;
} Node;
typedef struct {
Node *head;
Node *tail;
int count;
} Linked_List;
#define DOTEST(_fnc,_count) \
dotest(_fnc,#_fnc,_count)
#ifdef DEBUG
#define dbgprt(_fmt...) \
printf(_fmt)
#else
#define dbgprt(_fmt...) \
do { } while (0)
#endif
enum {
OPT_SWAPFLG = 1u << 0,
OPT_SHORTEN = 1u << 1,
};
double tsczero;
double
tscgetf(void)
{
struct timespec ts;
double sec;
clock_gettime(CLOCK_MONOTONIC,&ts);
sec = ts.tv_nsec;
sec /= 1e9;
sec += ts.tv_sec;
sec -= tsczero;
return sec;
}
int
show(Node *cur)
{
int score;
if (cur != NULL)
score = cur->score;
else
score = -1;
return score;
}
// SortList -- insertion sort
void
SortList(Linked_List *srclist)
{
Node *dsthead = NULL;
Node *dstprev = NULL;
// do N passes on the list
while (1) {
// get next element in source list -- stop when empty
Node *srcbest = srclist->head;
if (srcbest == NULL)
break;
// find smallest node in remaining list
Node *bestprev = NULL;
Node *curprev = NULL;
for (Node *cursrc = srcbest; cursrc != NULL; cursrc = cursrc->next) {
if (cursrc->score < srcbest->score) {
srcbest = cursrc;
bestprev = curprev;
}
curprev = cursrc;
}
// add selected node to tail of destination list
if (dsthead == NULL)
dsthead = srcbest;
else
dstprev->next = srcbest;
dstprev = srcbest;
// remove selected node from source list
if (bestprev != NULL)
bestprev->next = srcbest->next;
else
srclist->head = srcbest->next;
// fix the tail of destination list
dstprev->next = NULL;
}
// set new head of original list
srclist->head = dsthead;
}
// SwapCom -- bubble sort
void
SwapCom(Linked_List *list,unsigned int opt)
{
Node *dsthead = NULL;
Node *dstprev = NULL;
Node *tail = NULL;
int swapflg = 1;
// do N passes on the list -- stop early if list becomes sorted
while (swapflg) {
if (opt & OPT_SWAPFLG)
swapflg = 0;
Node *prev = list->head;
if (prev == NULL)
break;
dbgprt("SwapList: START\n");
Node *next;
Node *pprev = NULL;
for (Node *cur = prev->next; cur != NULL; cur = next) {
next = cur->next;
dbgprt("SwapCom: CUR head=%d pprev=%d prev=%d cur=%d next=%d\n",
show(list->head),show(pprev),show(prev),show(cur),show(next));
// last element is always in sort
if (cur == tail) {
dbgprt("SwapCom: SHORT\n");
break;
}
// the two elements are already in order
if (prev->score <= cur->score) {
pprev = prev;
prev = cur;
continue;
}
// say we had to swap -- we require another pass
dbgprt("SwapCom: SWAP\n");
swapflg = 1;
// adjust the head of the list
if (prev == list->head)
list->head = cur;
// swap the link pointers
cur->next = prev;
prev->next = next;
// adjust previous
if (pprev != NULL)
pprev->next = cur;
//next = prev;
pprev = cur;
//prev = cur;
}
if (opt & OPT_SHORTEN)
tail = prev;
}
}
// SwapEarly -- bubble sort
void
SwapEarly(Linked_List *list)
{
SwapCom(list,OPT_SWAPFLG);
}
// SwapShort -- bubble sort
void
SwapShort(Linked_List *list)
{
SwapCom(list,OPT_SWAPFLG | OPT_SHORTEN);
}
void
split(Linked_List *list,Linked_List *listl,Linked_List *listr)
{
int c2 = list->count / 2;
int idx = 1;
Node *rhs;
// find the midpoint
for (rhs = list->head; rhs != NULL; rhs = rhs->next, ++idx) {
if (idx >= c2)
break;
}
listl->head = list->head;
listl->count = c2;
listr->count = list->count - c2;
listr->head = rhs->next;
rhs->next = NULL;
}
void
merge(Linked_List *list,Linked_List *listl,Linked_List *listr)
{
Node *lhs = listl->head;
Node *rhs = listr->head;
Node *prev;
Node *cur;
list->head = NULL;
list->count = 0;
prev = NULL;
while ((lhs != NULL) && (rhs != NULL)) {
if (lhs->score <= rhs->score) {
cur = lhs;
lhs = lhs->next;
listl->count -= 1;
}
else {
cur = rhs;
rhs = rhs->next;
listr->count -= 1;
}
if (prev != NULL)
prev->next = cur;
else
list->head = cur;
list->count += 1;
prev = cur;
prev->next = NULL;
}
if (lhs != NULL) {
list->count += listl->count;
prev->next = lhs;
}
if (rhs != NULL) {
list->count += listr->count;
prev->next = rhs;
}
}
void
mergesort(Linked_List *list)
{
Linked_List listl;
Linked_List listr;
if (list->count >= 2) {
split(list,&listl,&listr);
mergesort(&listl);
mergesort(&listr);
merge(list,&listl,&listr);
}
}
// MergeSort -- merge sort
void
MergeSort(Linked_List *list)
{
mergesort(list);
}
Linked_List *
newlist(int count)
{
Linked_List *list = calloc(1,sizeof(*list));
Node *prev = NULL;
for (int idx = 1; idx <= count; ++idx) {
Node *cur = calloc(1,sizeof(*cur));
cur->score = count - idx;
if (prev != NULL)
prev->next = cur;
else
list->head = cur;
list->tail = cur;
list->count += 1;
prev = cur;
}
return list;
}
void
freelist(Linked_List *list)
{
Node *next;
for (Node *cur = list->head; cur != NULL; cur = next) {
next = cur->next;
free(cur);
}
free(list);
}
int
chklist(Linked_List *list)
{
Node *prev = list->head;
Node *cur;
int idx = 0;
int err = 0;
if (prev != NULL)
cur = prev->next;
else
cur = NULL;
for (; cur != NULL; cur = cur->next, ++idx) {
if (prev->score > cur->score) {
printf("chklist: ERROR index %d -- prev=%d cur=%d\n",idx,prev,cur);
if (++err > 10)
break;
}
prev = cur;
}
if (err)
exit(1);
// get the count
idx += 1;
return idx;
}
void
prtlist(Linked_List *list,const char *reason)
{
int totlen = 0;
totlen += printf("%s:",reason);
for (Node *cur = list->head; cur != NULL; cur = cur->next) {
totlen += printf(" %d",cur->score);
if (totlen >= 70) {
printf("\n");
totlen = 0;
}
}
if (totlen > 0)
printf("\n");
}
void
dotest(void (*sort)(Linked_List *),const char *reason,int count)
{
Linked_List *list;
int prtflg = (count <= 100);
printf("\n");
printf("Testing %s for %d elements ...\n",reason,count);
list = newlist(count);
if (prtflg)
prtlist(list,"Unsorted");
double tscbeg = tscgetf();
sort(list);
double tscend = tscgetf();
tscend -= tscbeg;
if (prtflg)
prtlist(list,"Sorted");
int chk = chklist(list);
if (chk != count) {
printf("dotest: check count mismatch -- expected: %d actual: %d\n",
count,chk);
exit(1);
}
freelist(list);
double rate;
#if 0
rate = count;
rate /= tscend;
#else
rate = tscend;
rate /= count;
#endif
printf("ELAPSED: %.9f RATE: %.9f\n",tscend,rate);
fflush(stdout);
}
int
main(void)
{
int counts[] = { 10, 100, 1000, 10000, 100000, -1 };
tsczero = tscgetf();
for (int idx = 0; ; ++idx) {
int count = counts[idx];
if (count < 0)
break;
printf("\n");
for (int idx = 0; idx <= 70; ++idx)
printf("-");
printf("\n");
DOTEST(SortList,count);
DOTEST(SwapEarly,count);
DOTEST(SwapShort,count);
DOTEST(MergeSort,count);
}
return 0;
}
这是程序输出:
-----------------------------------------------------------------------
Testing SortList for 10 elements ...
Unsorted: 9 8 7 6 5 4 3 2 1 0
Sorted: 0 1 2 3 4 5 6 7 8 9
ELAPSED: 0.000000696 RATE: 0.000000070
Testing SwapEarly for 10 elements ...
Unsorted: 9 8 7 6 5 4 3 2 1 0
Sorted: 0 1 2 3 4 5 6 7 8 9
ELAPSED: 0.000001120 RATE: 0.000000112
Testing SwapShort for 10 elements ...
Unsorted: 9 8 7 6 5 4 3 2 1 0
Sorted: 0 1 2 3 4 5 6 7 8 9
ELAPSED: 0.000000696 RATE: 0.000000070
Testing MergeSort for 10 elements ...
Unsorted: 9 8 7 6 5 4 3 2 1 0
Sorted: 0 1 2 3 4 5 6 7 8 9
ELAPSED: 0.000000835 RATE: 0.000000083
-----------------------------------------------------------------------
Testing SortList for 100 elements ...
Unsorted: 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79
78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55
54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
5 4 3 2 1 0
Sorted: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
97 98 99
ELAPSED: 0.000031237 RATE: 0.000000312
Testing SwapEarly for 100 elements ...
Unsorted: 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79
78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55
54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
5 4 3 2 1 0
Sorted: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
97 98 99
ELAPSED: 0.000083257 RATE: 0.000000833
Testing SwapShort for 100 elements ...
Unsorted: 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79
78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55
54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
5 4 3 2 1 0
Sorted: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
97 98 99
ELAPSED: 0.000045619 RATE: 0.000000456
Testing MergeSort for 100 elements ...
Unsorted: 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79
78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55
54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
5 4 3 2 1 0
Sorted: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
97 98 99
ELAPSED: 0.000007023 RATE: 0.000000070
-----------------------------------------------------------------------
Testing SortList for 1000 elements ...
ELAPSED: 0.003071345 RATE: 0.000003071
Testing SwapEarly for 1000 elements ...
ELAPSED: 0.008256265 RATE: 0.000008256
Testing SwapShort for 1000 elements ...
ELAPSED: 0.004658966 RATE: 0.000004659
Testing MergeSort for 1000 elements ...
ELAPSED: 0.000110933 RATE: 0.000000111
-----------------------------------------------------------------------
Testing SortList for 10000 elements ...
ELAPSED: 0.312265008 RATE: 0.000031227
Testing SwapEarly for 10000 elements ...
ELAPSED: 0.829503246 RATE: 0.000082950
Testing SwapShort for 10000 elements ...
ELAPSED: 0.450563461 RATE: 0.000045056
Testing MergeSort for 10000 elements ...
ELAPSED: 0.001036259 RATE: 0.000000104
-----------------------------------------------------------------------
Testing SortList for 100000 elements ...
ELAPSED: 31.850022147 RATE: 0.000318500
Testing SwapEarly for 100000 elements ...
ELAPSED: 84.817288841 RATE: 0.000848173
Testing SwapShort for 100000 elements ...
ELAPSED: 46.089681707 RATE: 0.000460897
Testing MergeSort for 100000 elements ...
ELAPSED: 0.012533725 RATE: 0.000000125
更新#2:
只是为了好玩，我已经编辑了第二个代码块以包含一个mergesort [并更新了程序输出块].
Just for fun, I've edited the second code block to include a mergesort [and updated the program output block].
我也用您的最后一个排序算法进行了测试，但仍然没有进行排序.–查克(Chuck)
i tested with your last sorting algorithm too but still werent sorted. – Chuck
对于较小的数字，我的测试程序会在排序后打印出列表.您可以目视检查之前和之后.
For smaller numbers, my test program prints out the list after sorting. You can visually inspect the before and after.
查克(Chuck)显然，您不知道如何测试列表是否已排序.向我们显示代码，使您可以确定列表是否已排序.–库巴没有忘记莫妮卡
Chuck Obviously you don't know how to test whether a list is sorted. Show us the code that lets you determine whether the list is sorted or not. – Kuba hasn't forgotten Monica
我的测试程序对列表是否排序进行了[简单]测试，如果列表未按 排序，则该测试将中止.
My test program had a [simple] test for the list being in sort or not, and would have aborted if the list were not sorted.
您可以将您的排序检查代码与我的 chklist 代码进行比较.
You can compare your sort check code to my chklist code.
不过……
在您最近更新中发布的代码中，从文件中逐行读取的代码被损坏.我已经注释并修复了以下代码:
In the code you posted in your recent update, the code that reads in lines from the file is broken. I've annotated and fixed this code:
// and this one is my main for reading from txt file:
fp3 = fopen("10-million-password-list-top/aa.txt", "r");
if (fp3 == NULL) {
printf("Could not open the file\n");
}
#if 0
// NOTE/BUG: why have str be an array of pointers?
while (fgets(str[k], LSIZ, fp3)) {
str[k][strlen(str[k]) - 1] = '\0';
// NOTE/BUG: this _destroys_ the list on each iteration
Linked_List *char_list = create_empty_list();
// NOTE/BUG: insert_end _modifies_ list->head _directly_ -- no need to return
// the head value
char_list->head = insert_end(char_list, str[k]);
}
#else
char linebuf[1000];
Linked_List *char_list = create_empty_list();
while (fgets(linebuf,sizeof(linebuf),fp3)) {
linebuf[strlen(linebuf) - 1] = 0;
insert_end(char_list,linebuf);
}
#endif
insert_end 代码也被破坏:
// NOTE/BUG: list->head is updated internally -- no need to return it
#if 0
Node *
insert_end(Linked_List *list, void *data)
#else
void
insert_end(Linked_List *list, const char *data)
#endif
{
Node *new_node;
Node *temp;
// NOTE/BUG: don't cast the return value of malloc
#if 0
new_node = (Node *) malloc(sizeof(Node));
#else
new_node = malloc(sizeof(*new_node));
#endif
// NOTE/BUG: this is _not_ the way to allocate space for the string
// NOTE/BUG: the next line blows away the value just obtained from malloc
#if 0
new_node->data = malloc(sizeof(char *));
new_node->data = (char *) data;
#else
new_node->data = strdup(data);
#endif
new_node->next = NULL;
if (list->head == NULL) {
list->head = new_node;
}
else {
temp = list->head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_node;
}
#if 0
return (list->head);
#endif
}
这篇关于为什么链表没有排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
