連結リストをソート

学校の課題なんですが正直手も足も出ません。
どういった流れで作成すればいいんでしょうか。


1.連結リストにデータ（文字列）をソートされた順序に追加するようなプログラムを作成する．
2.連結リストのデータを順にプリントするプログラムを作成する。
3.セルをキーとそれに対応する値を含めるように拡張し、与えられたキーを持つセルを探索して
　それに対する値を返すプログラムを作成する。

課題を解く際には以下のプログラムを参考にする


#include <stdio.h>
struct element{
char data;
struct element *next;
};
struct elements *new()
{
return((struct element *)malloc(sizeof(struct element)));
}
struct element *create()
{
struct element *p;

p=new();
p->next=NULL;
return(p);
}

void insert(struct element *l,int k,char item)
{
struct element *p;

if(k>1)
insert(l->next,k-1,item);

else{
p=new();
p->data=item;
p->next=p;
l->next=p;
}
}

void delete(struct element *l,int k)
{
if(k>1)
delete(l->next,k-1);
else l->next=l->next->next;
}

char access(struct element *l,int k)
{
if(k>1)
return(access(l->next,k-1));
else return(l->next->data);
}

No.1 回答者： HKB 回答日時： 2007/12/22 08:36

#include <stdio.h>

#include <stdlib.h>
#include <string.h>

/*
文字列の挿入、探索を行うリストプログラム
mallocの戻り値チェックは省略(提出物であれば省略すべきではない)
「キー」「値」の型(int?、文字列?)が示されていないので、その実装は行っていない。
一応動作確認はしてあるが、バグが残っている可能性は捨てきれないため、十分な検証が必要。
*/

#define WORD_MAX 10 // 文字列最大長

// リストの1要素
typedef struct scell
{
struct scell *next;
char word[WORD_MAX]; // 文字列保持
} cell;

// リスト構造体
typedef struct slist
{
cell* head; // リスト先頭ダミーセル
} list;

/*
@return 新しいセル
*/
cell* newCell()
{
cell* newc = (cell*)malloc(sizeof(cell));
newc->next = NULL;
newc->word[0] = '\0';
return newc;
}

/*
@param n 次のセル
@param w 保持する文字列
@return 新しいセル
*/
cell* newCell2(cell* n , char* w)
{
cell* newc = (cell*)malloc(sizeof(cell));
newc->next = n;
strncpy(newc->word , w , WORD_MAX);
return newc;
}

/*
@return 新しいリスト
*/
list* newList()
{
list* newl = (list*)malloc(sizeof(list));
newl->head = newCell();
return newl;
}

/*
@param c このセルを含め、後続のセルを解放
*/
void freeCell(cell* c)
{
cell* tmp;
while(c != NULL)
{
tmp = c->next;
c->word[0] = '\0';
c->next = NULL;
free(c);
c = tmp;
}
}

/*
@param l このリストを解放
*/
void freeList(list* l)
{
freeCell(l->head);
l->head = NULL;
free(l);
}

/*
@param l このリストの全要素を表示
*/
void dispList(list* l)
{
int i;
cell* c;
for(i=0 , c = l->head->next ; c != NULL ; i++ , c = c->next)
{
printf("%d %s\n" , i , c->word);
}
printf("\n");
}

/*
@param ls 挿入対象のリスト
@param w 挿入する文字列
*/
void insertWord(list* ls , char* w)
{
cell* c;
for(c = ls->head ; c->next != NULL ; c = c->next)
{
if(strncmp(w , c->next->word , WORD_MAX) < 0)
{
break;
}
}
cell* newc = newCell2(c->next , w);
c->next = newc;
}

/*
@param ls 探索対象のリスト
@param w 探索対象の文字列
@return 文字列を発見した場合、その文字列を保持するセル。発見しなかった場合、NULL
*/
cell* searchWord(list* ls , char* w)
{
cell* c;
for(c = ls->head->next ; c != NULL ; c = c->next)
{
if(strncmp(c->word , w , WORD_MAX) == 0)
{
break;
}
}
return c;
}

int main(void)
{
list* ls = newList();
insertWord(ls , "charlie");
insertWord(ls , "alpha");
insertWord(ls , "blavo");
cell* c;
if((c = searchWord(ls , "blavo")))
{
printf("found %s\n" , c->word);
}
dispList(ls);
freeList(ls);
return 0;
}