结构数组给人错误的输出上整理 [英] structure array giving wrong output on sorting
问题描述
1）我有一个结构
结构节点
{
字符符号;
INT频率;
诠释左，右，根;
int值;
短is_sorted;
};
结构节点数据[1000];
，其中数据[215] .freq（频率）{0,1,2,3,4,5}是由从文件INPUT.TXT读书以下按字母顺序排列的符号（符号）（ABCDEF）值获得作为唯一argument.Now我一定要添加此阵列的两个最低频率，然后放置在同一个阵列，它将保持频率的递增的顺序获得的新元素（这是已经排序的数组，看到我们有0,1， 2,3,4,5）。
（2）我也有照顾两个最小的添加元素不得参与再排序和此外，他们还必须固定在其位置一次，如果他们已经加入，但新近获得通过添加元素可以参加此外，再次排序。例如：我们添加两个最小单元0和1，0 + 1 = 1，所以1是由加法运算得到的结果，现在这个1的位置必须在数据[]频率，使得仍然应该有增加的次序。 。因此：
数据[I] .freq = 0 1 1（这里补充）2 3 4 5
现在我们必须再次找到最小的两个节点（请阅读评论（2）再次很好地理解）。我们不能再增加0 abnd 1，因为他们已经参加了除。所以这一次，我们将增加1和2（这个人是在索引三，请不要混淆wwith一个索引二）。这样我们就得到1 + 2 = 3
0 1 1 2 3 3 4 5我们再次定位3维持增大的顺序。我们再次重申：在指数4和5元（因为我们已经做了另外的元素的索引0,1和2,3），我们将获得3 + 3 = 6，这又在数据[]频率定位<。 / P>
0 1 1 2 3 3 4 5 6此时6是大于4和5，因此会出现后5维持增大的顺序
最后，我们将获得数据[数据大小] .freq 是这样的：
数据[数据大小] .freq = [0 1 1 2 3 3 4 5 6 9 15]。
如此保持的加索引0,1和2,3和4,5和6,7和8,9之间，并在最后，我们有15是最后一个，因此这里我们停止。
这部分我已经在我的code已经完成了的。
什么帮助，我需要？的
当我运行code中的显示数据是这样的：
符号频率左右（它实际上是一个哈夫曼树实现只使用数组，没有malloc和没有指针）。
预期的输出是这样的：（当我使用的qsort（），它工作正常，但我没有使用的qsort因为复杂的原因（））：
./扩展INPUT.TXT
阅读文件...
数据是：
0：符号：一，频率：0，左：-1，右-1
1：符号：B，频率：1，左：-1，右-1
2：符号：0，频率：1，左：0，右1
3：符号：C，频率：2，左：-1，右-1
4：符号：D，频率：3，左：-1，右-1
5：符号：5，频率：3，左：2，右3
6：符号：E，频率：4，左：-1，右-1
7：符号：F，频率：5，左：-1，右-1
8：符号：4，频率：6，左：4，右5
9：符号：3，频率：9，左：6，（右）7
10：符号：2，频率：15，左：8，右9
D：00
答：0100
B：0101
C：011
E：10
F：11
因此，我已实现的算法我上面提到的，它可以很好地用于打印频率（频率）但是不打印的符号和左，右孩子正确，我长期以来尝试，但没有能够得到的地步，我有错我的code，（我相信树创作的部分是正确的（即移动）树（）函数，问题是在code写的一些地方 main（）函数，而且我有评论怀疑部分的）。 下面是我的code：
新台币主（INT ARGC，字符** argv的）
{
INT I，计数= 0，J，F，S;
结构节点数据[1000];
INT DATA_SIZE = -1;
如果（的argc 2）
{
的printf（提供输入文件..）;
返回;
}
的printf（读文件... \ N）;
的read_data（的argv [1]，数据，和安培; DATA_SIZE）;
的printf（数据大小数：％d \ N，DATA_SIZE）;
对于（i = 0; i + 1的＆LT; DATA_SIZE;我+ = 2）
{
//的printf（COUNT1数：％d \ N，算）;
数据[DATA_SIZE] .symbol ='0'+计数;
数据[DATA_SIZE] .freq =数据[DATA_SIZE] .root =数据[I] .freq +数据[I + 1] .freq;
数据[DATA_SIZE]。左=我;
数据[DATA_SIZE] .right = I + 1;
数据[I]。价值= 0;
数据[I + 1]。价值= 1;
数据[I] .is_sorted = 1;
数据[I + 1] .is_sorted = 1;
数据[DATA_SIZE] .value的='\ 0';
数据[DATA_SIZE] .is_sorted = 0;
为（J = DATA_SIZE-1，J＆GT; F + 1; j--）
{
如果（数据[DATA_SIZE] .root＆GT; =数据[J] .freq）
{
//的printf（如果内部循环的\ n）;
打破;
}
其他
{
//输出（其他回路的\ n）;
数据[J + 1] .freq =数据[J] .freq;
数据[J + 1] .symbol =数据[J] .symbol;
数据[J + 1]。左=数据[J]。左;
数据[J + 1] .right =数据[J] .right;
//数据[J + 1] =数据[J]。
}
}
////////////////
//printf("data[j+1].sym1：％C \ N，数据[J + 1] .symbol）;
数据[J + 1] .freq =数据[DATA_SIZE] .root;
数据[J + 1] .symbol =数据[DATA_SIZE] .symbol;
数据[J + 1]。左=数据[DATA_SIZE]。左;
数据[J + 1] .right =数据[DATA_SIZE] .right;
数= count_unsorted（数据，DATA_SIZE）;
DATA_SIZE ++;
的printf（COUNT2数：％d \ N，算）;
}
的printf（数据是：\ N）;
对于（i = 0; I＆LT; DATA_SIZE;我++）
{
的printf（％D：符号：％C，频率：％D，左：％D，右％D \ N，我的数据[I] .symbol，数据[I] .freq，数据[I]。左，数据[I] .right）;
}
焦炭路径[100] = {'\ 0'};
traverse_tree（数据，DATA_SIZE-1，路径）;
返回0;
}
卜我的code的输出是：
阅读文件...
0：符号：一，频率：0，左：-1，右-1
1：符号：B，频率：1，左：-1，右-1
2：符号：F，频率：1，左：-1，右-1
3：符号：C，频率：2，左：-1，右-1
4：符号：D，频率：3，左：-1，右-1
5：符号：F，频率：3，左：-1，右-1
6：符号：E，频率：4，左：-1，右-1
7：符号：F，频率：5，左：-1，右-1
8：符号：2，频率：6，左：4，右5
9：符号：3，频率：9，左：6，（右）7
10：符号：4，频率：15，左：8，右9
F：11
E：10
F：01
D：00
马力@ Ubuntu的：〜/桌面
当我尝试这样做：
的printf（数据研究[J] .SYM：％C \ N，数据[DATA_SIZE] .symbol）; insde注释的部分（这是最可疑的部分，其中i assin的值元素和符号），那么我已经很˚F数据[J] .SYM：符号是数据研究[J] .SYM奇怪的f值分析[J] .SYM：2数据[J] .SYM：3数据[J]。符号：4我不知道为什么它有F的前两个地方，应该有 0 1 1 2 3 4 不是 FF 2 3 4
因此，在最后，我刚才已经做到了自己：在这里，我把code的人，如果在未来getsimilar类型的问题：
无效sort_array（结构节点*数据，INT的长度）
{
INT I，J;
对于（i = 0; I＆LT;长度为1安培;＆放大器;数据[I] .freq＆LT; =数据[长度1] .freq;我++）; //这个当它到达所需的位置，所以复杂度大约是n-1个总n个元素循环中断。
为（J =长度为1; J＆GT;我; j--）
{
结构结点温度;
temp.symbol =数据[J] .symbol;
temp.freq =数据[J] .freq;
temp.left =数据[J]。左;
temp.right =数据[J] .right;
temp.value =数据[J]。价值;
数据[J] .symbol =数据[J-1] .symbol;
数据[J] .freq =数据[J-1] .freq;
数据[J]。左=数据[J-1]。左;
数据[J] .right =数据[J-1] .right;
数据[J]。价值=数据[J-1]。价值;
数据[J-1] .symbol = temp.symbol;
数据[J-1] .freq = temp.freq;
数据[J-1]。左= temp.left;
数据[J-1] .right = temp.right;
数据[J-1]。价值= temp.value;
}
}
1)I have a structure
struct node
{
char symbol;
int freq;
int left, right,root;
int value;
short is_sorted;
};
struct node data[1000];
where data[215].freq (frequency) {0,1,2,3,4,5} is obtained by reading following alphabetical symbols(symbol) (abcdef) values from a file "Input.txt" as a sole argument.Now i have to add two minimum frequencies of this array and then position the newly element obtained in the same array such that it will maintain the increasing order of the freq(It was already sorted array, see we have 0,1,2,3,4,5).
(2)I also have to take care that the two minimum added elements must not participate in sorting and addition again, they must be fixed at their position once if they are already added, but the newly obtained element by addition can participate in addition and sorting again. eg: we add two minimum element 0 and 1, 0+1=1, so "1" is the result obtained by addition, now this "1" must be positioned in data[].freq such that still there should be increasing order. so :
data[i].freq = 0 1 1(added here) 2 3 4 5
Now we have to again find the minimum two nodes (please read the comment (2) again to understand well) .We cannot add 0 abnd 1 again because they have already participated in in the addition. so this time we will add 1 and 2(this one is at index three, please don't get confused wwith the one at index two). so we get 1+2=3
0 1 1 2 3 3 4 5 we again positioned 3 to maintain increasing order. we repeat again: for element at index 4 and 5(because we have already done addition for element at index 0,1 and 2,3) we will get 3+3=6, again position it in data[].freq.
0 1 1 2 3 3 4 5 6 this time 6 is greater then 4 and 5 so it will appear after 5 to maintain increasing order.
At last we will get data[dataSize].freq like this:
data[dataSize].freq= [0 1 1 2 3 3 4 5 6 9 15].
so the addition held was between index 0,1 and 2,3 and 4,5 and 6, 7 and 8,9 and at last we have 15 which is last one, so here we stops.
This part i have already done in my code.
What help do i need ?
When i run the code the shows data will look like this:
Symbol Freq Left Right (It's actually a huffman tree implementation using only arrays,No malloc and No pointers).
The expected output is this: (when i use qsort() it works fine but i am not using qsort() because of complexity reasons):
./extended Input.txt
Reading file...
Data is:
0: symbol: a, Freq: 0, Left: -1, Right -1
1: symbol: b, Freq: 1, Left: -1, Right -1
2: symbol: 0, Freq: 1, Left: 0, Right 1
3: symbol: c, Freq: 2, Left: -1, Right -1
4: symbol: d, Freq: 3, Left: -1, Right -1
5: symbol: 5, Freq: 3, Left: 2, Right 3
6: symbol: e, Freq: 4, Left: -1, Right -1
7: symbol: f, Freq: 5, Left: -1, Right -1
8: symbol: 4, Freq: 6, Left: 4, Right 5
9: symbol: 3, Freq: 9, Left: 6, Right 7
10: symbol: 2, Freq: 15, Left: 8, Right 9
d: 00
a: 0100
b: 0101
c: 011
e: 10
f: 11
So I have implemented the algorithm i mentioned above and it works well for printing frequency(Freq) But it don't print the symbols and Left and Right child correctly, I am trying since long but not able to get the point where i have mistake in my code.(I am sure that tree creation part is correct (which is traverse)tree() function, The problem is some where in the code written in main() function , moreover i have commented the suspected part). Below is my code:
nt main(int argc, char **argv)
{
int i,count=0,j,f,s;
struct node data[1000];
int data_size=-1;
if(argc<2)
{
printf("Provide input file..");
return;
}
printf("Reading file...\n");
read_data(argv[1], data, &data_size);
printf("datasize: %d\n", data_size);
for (i=0; i+1<data_size; i+=2)
{
//printf("count1: %d\n", count);
data[data_size].symbol='0'+count;
data[data_size].freq=data[data_size].root =data[i].freq+data[i+1].freq;
data[data_size].left=i;
data[data_size].right=i+1;
data[i].value=0;
data[i+1].value=1;
data[i].is_sorted=1;
data[i+1].is_sorted=1;
data[data_size].value='\0';
data[data_size].is_sorted=0;
for (j=data_size-1; j>f+1; j--)
{
if (data[data_size].root >=data[j].freq)
{
// printf("Inside if loop\n");
break;
}
else
{
// printf("else loop\n");
data[j+1].freq=data[j].freq;
data[j+1].symbol=data[j].symbol ;
data[j+1].left=data[j].left ;
data[j+1].right=data[j].right ;
//data[j+1]=data[j];
}
}
////////////////
//printf("data[j+1].sym1: %c\n", data[j+1].symbol );
data[j+1].freq=data[data_size].root ;
data[j+1].symbol=data[data_size].symbol ;
data[j+1].left=data[data_size].left ;
data[j+1].right=data[data_size].right ;
count=count_unsorted(data,data_size);
data_size++;
printf("count2: %d\n", count);
}
printf("Data is:\n");
for(i=0;i<data_size;i++)
{
printf("%d: symbol: %c, Freq: %d, Left: %d, Right %d\n", i,data[i].symbol, data[i].freq, data[i].left, data[i].right);
}
char path[100]={'\0'};
traverse_tree(data, data_size-1,path);
return 0;
}
Bu the output of my code is:
Reading file...
0: symbol: a, Freq: 0, Left: -1, Right -1
1: symbol: b, Freq: 1, Left: -1, Right -1
2: symbol: f, Freq: 1, Left: -1, Right -1
3: symbol: c, Freq: 2, Left: -1, Right -1
4: symbol: d, Freq: 3, Left: -1, Right -1
5: symbol: f, Freq: 3, Left: -1, Right -1
6: symbol: e, Freq: 4, Left: -1, Right -1
7: symbol: f, Freq: 5, Left: -1, Right -1
8: symbol: 2, Freq: 6, Left: 4, Right 5
9: symbol: 3, Freq: 9, Left: 6, Right 7
10: symbol: 4, Freq: 15, Left: 8, Right 9
f: 11
e: 10
f: 01
d: 00
hp@ubuntu:~/Desktop
When i try to do :
printf("data[j].sym: %c\n", data[data_size].symbol );insde the commented part (which is the most suspected part where i assin the values to element and symbols)" then i have very strange value of symbol which is "data[j].sym: f data[j].sym: f data[j].sym: 2 data[j].sym: 3 data[j].sym: 4 " I don't know why it has "f" at first two places , there should be "0 1 2 3 4" not "f f 2 3 4 "
So at last,I have just done it myself:Here i put code for someone if getsimilar type of problem in future:
void sort_array(struct node *data, int length)
{
int i,j;
for(i=0;i<length-1 && data[i].freq<=data[length-1].freq;i++); //This loop breaks when it gets the desired position, So complexity is about n-1 for total n elements.
for(j=length-1;j>i;j--)
{
struct node temp;
temp.symbol=data[j].symbol;
temp.freq=data[j].freq;
temp.left=data[j].left;
temp.right=data[j].right;
temp.value=data[j].value;
data[j].symbol=data[j-1].symbol;
data[j].freq=data[j-1].freq;
data[j].left=data[j-1].left;
data[j].right=data[j-1].right;
data[j].value=data[j-1].value;
data[j-1].symbol=temp.symbol;
data[j-1].freq=temp.freq;
data[j-1].left=temp.left;
data[j-1].right=temp.right;
data[j-1].value=temp.value;
}
}
这篇关于结构数组给人错误的输出上整理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
