No.15619![]() |
リスト作成後ソートを行うプログラム 投稿者---Zk(2004/07/17 15:53:51) |
||
初めまして、大学でC言語を学習している初心者です。 No1のプログラムにより線形リストを行ったデータを、クイックソートを用いてソートを行うのが目的です。そこでlength(バイトカウント)をキーとしたクイックソートのプログラムとして、No2を作成してみたのですが…。これを活用するためにはどうしたらよいでしょうか。 ご指導、よろしくお願いします。 〔No1〕 typedef struct log *log_p; typedef struct log { log_p next; char address[256]; char datetime[256]; char command[256]; int code,length; }log_type; log_p start=NULL; main() { FILE *fp; char buf[256]; char *strp; log_type *p,*q; if ((fp = fopen("data2.txt", "r")) == NULL) exit(-1); while (fgets(buf, sizeof(buf), fp)!=NULL) { /*mallocで領域を確保*/ if((p = (log_type *) malloc(sizeof(log_type)))==NULL) exit(-1); /*アドレス*/ strp = strtok(buf, " "); strcpy(p->address, strp); /*日時*/ strp = strtok(NULL, "]"); strp = strp+5; /*5文字分スキップ*/ strcpy(p->datetime, strp); /*コマンド*/ strp = strtok(NULL, "\""); strp = strtok(NULL, "\""); strcpy(p->command, strp); /*コード*/ strp = strtok(NULL, " "); p->code = atoi(strp); /*バイトカウント*/ strp = strtok(NULL, " "); p->length = atoi(strp); if(start==NULL){ start=p; p->next=NULL; }else{ for(q=start;q!=NULL;q=q->next){ if(q->next==NULL) break; } } q->next=p; p->next=NULL; } for (p=start; p!=NULL; p=p->next) { printf("%s, %s, %s, %d, %d\n", p->address, p->datetime, p->command, p->code, p->length); } fclose(fp); } 〔No2〕 void quick_sort(log_type a[], int left, int right) { int i, j; int pivot; log_type x; if(left >= right) return; pivot = a[right].length; i = left; j = right-1; for(;;){ while(a[i].length < pivot) i++; while(i < j && pivot < a[j].length) j--; if(i < j) { x = a[i]; a[i] = a[j]; a[j] = x; } else { break; } } x = a[i]; a[i] = a[right]; a[right] = x; quick_sort(a, left, i-1); quick_sort(a, i+1, right); } 〔入力データ〕 246.801.45.65 - - [13/Jnne/2004:14:55:21 +0800] "GET /HTTP/1.0" 152 321 246.801.45.65 - - [13/Jnne/2004:14:55:21 +0800] "GET /HTTP/1.0" 152 285 246.801.45.65 - - [13/Jnne/2004:14:55:21 +0800] "GET /HTTP/1.0" 152 154 246.801.45.65 - - [13/Jnne/2004:14:55:21 +0800] "GET /HTTP/1.0" 152 675 246.801.45.65 - - [13/Jnne/2004:14:55:21 +0800] "GET /HTTP/1.0" 152 972 246.801.45.65 - - [13/Jnne/2004:14:55:21 +0800] "GET /HTTP/1.0" 152 158 246.801.45.65 - - [13/Jnne/2004:14:55:21 +0800] "GET /HTTP/1.0" 152 159 |
No.15622![]() |
Re:リスト作成後ソートを行うプログラム 投稿者---とおりすがり(2004/07/17 19:22:41) |
||
> そこでlength(バイトカウント)をキーとしたクイックソートのプログラムとして、No2を作成してみたのですが…。 あなたが、本当にNo2のプログラムを作ったのなら、活用方法などわからないはず がないのですが…? その関数にどういう入力を入れたら、どうなるかを考えて作ったんでしょ? |
No.15628![]() |
Re:リスト作成後ソートを行うプログラム 投稿者---Zk(2004/07/17 22:26:22) |
||
ソートだけをできる関数をNo2として作りました。 No2の場合はポイントから渡されるものではなく、既存のデータをそのまま構造体とし、その中でのlengthをソートするようにしています。そのデータがp->lengthといったポインタで渡されている場合は、どのようにしたらよいのかで悩んでしまったのですが…。 No2のプログラムができている時点で、僕は何か重大な見落としをしているのでしょうか…? |
No.15634![]() |
Re:リスト作成後ソートを行うプログラム 投稿者---かずま(2004/07/18 01:47:23) |
||
> No2のプログラムができている時点で、僕は何か重大な見落としをしているのでしょうか…? そのプログラムは、配列のソートです。リストのソートには使えません。 ということで、リストのクイックソートを書いてみました。いかがでしょうか? #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct Node { struct Node *next; char *address, *datetime, *command; int code, length; } Node; void *emalloc(size_t n) { void *p = malloc(n); if (p == NULL) puts("out of memory"), exit(1); return p; } char *str_dup(const char *s) { return strcpy(emalloc(strlen(s) + 1), s); } Node *new_node(const char *address, const char *datetime, const char *command, int code, int length) { Node *p = emalloc(sizeof(Node)); p->address = str_dup(address); p->datetime = str_dup(datetime); p->command = str_dup(command); p->code = code; p->length = length; return p; } void print_list(Node *p) { for (; p; p = p->next) printf("%s %s %s %d %d\n", p->address, p->datetime, p->command, p->code, p->length); } Node *concat(Node *a, Node *b) { Node *p; if (a == NULL) return b; for (p = a; p->next; p = p->next) ; p->next = b; return a; } Node *quick_sort(Node *p) { int pivot; Node *lt = NULL, *eq = NULL, *gt = NULL, *next; if (p == NULL || p->next == NULL) return p; pivot = p->length; for (; p; p = next) { next = p->next; if (p->length < pivot) p->next = lt, lt = p; else if (p->length > pivot) p->next = gt, gt = p; else p->next = eq, eq = p; } return concat(quick_sort(lt), concat(eq, quick_sort(gt))); } int main(void) { char buf[256], address[256], datetime[256], command[256]; int code, length; Node *head = NULL, *p; FILE *fp = stdin; while (fgets(buf, sizeof buf, fp)) { if (sscanf(buf, "%s%*[^[][%[^]]] \"%[^\"]\"%d%d", address, datetime, command, &code, &length) != 5) continue; p = new_node(address, datetime, command, code, length); p->next = head; head = p; } head = quick_sort(head); print_list(head); return 0; } |
No.15639![]() |
Re:リスト作成後ソートを行うプログラム 投稿者---Zk(2004/07/18 11:26:41) |
||
『配列』と『リスト』について僕の中は同じような感じで受け止めてしまったようです。少し理解できないところもあるので、もっと勉強してみます。また、他のソート方法についても考えてみます。 本当にありがとうございました! |