C言語関係掲示板

過去ログ

No.1195 リストのクイックソート

[戻る] [ホームページ]
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)


 『配列』と『リスト』について僕の中は同じような感じで受け止めてしまったようです。少し理解できないところもあるので、もっと勉強してみます。また、他のソート方法についても考えてみます。
 本当にありがとうございました!