プログラミング技法とデータ構造

課題

次の書きかけのプログラムを参考にし，data配列の中のデータ値を，LIST構造として連結せよ．ただし連結順は小さい値順にソートするものとする．

考察として，このプログラムに新たにデータを追加する際の計算量はどのくらいか見積り，もっと効率よく追加する方法を考えてみよ．

#include <stdio.h>
#include <stdlib.h>

typedef struct list{
    int val;
    struct list *next;
} LIST
LIST *newlist(void);

int main(void)
{
 int i;
 LIST *head;
 LIST *p;
 int data[15]={4,6,8,11,3,15,14,7,12,5,1,9,10,2,13,0};

 p=head=newlist();
 p->val=data[0];
 for(i=1; data[i]!=0; i++)
 {
    //LISTを確保してからそのvalにdata[i]を登録
    //headから順に探索して，前セルの値<data[i]<次セルの値
    //となるような位置に挿入
    //LISTを挿入する関数を自分で作ってもよい．
 }

 for(;;)
 {
   //headから最後までprintfでval表示 
 }
}

LIST *newlist(void)
{
  LIST *new = malloc(sizeof(LIST));
  if(new==NULL)
    exit(EXIT_FAILURE);
  new->val=0;
  new->next=NULL;
}

提出方法

• ワープロ作成でA4紙に印刷して提出
• 目次は　課題の説明，作成した処理の内容(理論)，プログラムソース，入力と出力(結果)，プログラムの説明と考察

締め切り

• 原則として来週の講義まで
• ただし，来年一月までは遅刻提出を受け付けるのであきらめないこと．