我必須在鏈接列表上創建一個快速排序(在C中)。 我有我的第一個和最後一個指針的樞軸(在這個代碼中它是列表的第一個元素)。 我該結構的使用方法:C快速排序(鏈接列表)分段錯誤
typedef struct list_element list_element;
struct list_element {
char *password;
int count;
list_element* next;
};
typedef struct list list;
struct list {
list_element* first;
list_element* last;
};
我有100個密碼和計數的文件。 像這樣: 密碼1 123(下一行)密碼2 435(下一行)password3 133 ... 口令必須被(根據其計數)在此PROGRAMM的端排序。 因爲我只需要使用下一個指針,所以不需要爲左右列表添加任何額外的內存分配。 (這就是在鍛鍊的提示說。)
給定的主要功能:
int main(int argc, char** args)
{
if (argc != 2)
{
printf("Nutzung: %s <Dateiname>\n",args[0]);
return 1;
}
list mylist;
init_list(&mylist);
read_data(args[1],&mylist);
qsort_list(&mylist);
printf("Sortierte Liste:\n");
print_list(&mylist);
free_list(&mylist);
return 0;
}
我已經初始化我的名單:
void init_list(list* mylist)
{
mylist->first = NULL;
mylist->last = NULL;
}
而在末尾插入一個新元素(passwort =文件的密碼,hauefigkeit =文件數):從文件
void insert_list(list_element* le, list* mylist)
{
if (mylist->first != NULL) {
le->next = mylist->last;
mylist->last = le;
le->next= NULL;
}
else {
mylist->last->next = le;
mylist->last = le;
mylist->last->next = NULL;
}
}
讀取數據:
void read_data(char* filename, list* mylist)
{
FILE *file_in = fopen(filename, "r");
if (file_in == NULL) {
perror("Could not open input file!");
exit(1);
}
char buffer[999] = "0";
char *passwort = (char*) calloc(1,sizeof(passwort));
int haeufigkeit = 0;
while (fgets(buffer, sizeof(buffer), file_in) != NULL) {
sscanf(buffer, "%s %d", passwort, &haeufigkeit);
list_element* le = (list_element*)calloc(1,sizeof(list_element));
for(int i = 0; i <=100; i++) {
le->password[i] = passwort[i];
}
le->count = haeufigkeit;
le->next = NULL;
insert_list(le, mylist);
}
fclose(file_in);
}
分區列表:
list_element* partition(list* input, list* left, list* right)
{
list_element* pivot = NULL;
if (input->first != NULL) {
list_element* temp;
pivot = input->first;
input->first = input->first->next;
pivot->next = NULL;
left->first = NULL;
right->first = NULL;
while (input->first != NULL) {
if((pivot->count)>(input->first->count)){
temp=input->first->next;
insert_list(input->first, left);
input->first=temp;
}
else {
temp = input->first->next;
insert_list(input->first, right);
input->first = temp;
}
}
}
return pivot;
}
實際的快速排序:
void qsort_list(list* mylist)
{
if(mylist->first == mylist->last){
}
else{
list* left = calloc(1,sizeof(list));
list* right= calloc(1,sizeof(list));
list_element* pivot = partition(mylist, left, right);
qsort_list(left);
qsort_list(right);
if(left->first == NULL){
mylist->first = pivot;
}
else{
mylist->first = left->first;
left->last->next = pivot;
}
if(right->first == NULL){
pivot->next = NULL;
mylist->last = pivot;
}
else{
pivot->next = right->first;
mylist->last = right->last;
}
free(right);
free(left);
}
}
最終打印列表:
void print_list(list* mylist)
{
list_element *elem = mylist->first;
while (elem != NULL) {
printf("%s %d\n", elem->password, elem->count);
elem = elem->next;
}
}
而且空閒列表:
void free_list(list* mylist)
{
list_element *current;
list_element *second;
current = mylist->first;
while (current != NULL) {
second = current->next;
free(current);
current = second;
}
}
語法應該沒問題。 GCC(c99,Wall)編譯時沒有任何問題。
但存在分段錯誤。我一直在尋找幾個小時,我不知道問題出在哪裏。也許你可以幫我解決這個問題。
在前兩個答案後沒有任何分段錯誤。但是read_data函數仍然有問題。 程序無法正確讀取密碼。也許我誤解了你有關閱讀功能的答案。 這就是當前的函數:
void read_data(char* filename, list* mylist)
{
FILE *file_in = fopen(filename, "r");
if (file_in == NULL) {
perror("Could not open input file!");
exit(1);
}
char buffer[999] = "0";
int haeufigkeit = 0;
while (fgets(buffer, sizeof(buffer), file_in) != NULL) {
char passwort[100];
sscanf(buffer, "%s %d", passwort, &haeufigkeit);
list_element* le = (list_element*)
calloc(1,sizeof(list_element));
le->password = passwort;
le->count = haeufigkeit;
le->next = NULL;
insert_list(le, mylist);
}
fclose(file_in);
}
請問您可以調試它,並告訴我們在哪一行seg。故障在發生? –