開発環境
- OS X Lion - Apple(OS)
- Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
- プログラミング言語: C
- Clang (コンパイラ)
プログラミング言語C 第2版 ANSI規格準拠 (B.W. カーニハン D.M. リッチー (著)、 石田 晴久 (翻訳)、共立出版)の第6章(構造体)、6.4(構造体へのポインタ)、6.5(自己参照的構造体)、演習6-3を解いてみる。
その他参考書籍
- プログラミング言語Cアンサー・ブック 第2版 (クロビス・L．トンド、スコット・E．ギンペル(著)、矢吹 道郎(翻訳))
演習 6-3.
コード
sample.c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
struct linked_list{
int line_number;
struct linked_list *p;
};
struct tnode {
char *word;
struct linked_list *line_numbers;
struct tnode *left;
struct tnode *right;
};
struct tnode *addtree(struct tnode *, char *, int);
void treeprint(struct tnode *);
int getword(char *, int);
int noise_word(char *);
int main(int argc, char *argv[])
{
struct tnode *root;
char word[MAXWORD];
int line_number;
line_number = 1;
root = NULL;
while (getword(word, MAXWORD) != EOF) {
if (isalpha(word[0]) && noise_word(word) == -1) {
root = addtree(root, word, line_number);
} else if (word[0] == '\n') {
line_number++;
}
}
treeprint(root);
return 0;
}
struct tnode *talloc(void);
struct linked_list *lalloc(void);
void add_line_number(struct tnode *, int);
struct tnode *addtree(struct tnode *p, char *w, int line_number)
{
int cond;
if (p == NULL) {
p = talloc();
p->word = strdup(w);
p->line_numbers = lalloc();
p->line_numbers->line_number = line_number;
p->line_numbers->p = NULL;
p->left = p->right = NULL;
} else if ((cond = strcmp(w, p->word)) == 0) {
add_line_number(p, line_number);
} else if (cond < 0) {
p->left = addtree(p->left, w, line_number);
} else if(cond > 0) {
p->right = addtree(p->right, w, line_number);
}
return p;
}
void add_line_number(struct tnode *p, int line_number)
{
struct linked_list *tmp;
tmp = p->line_numbers;
while (tmp->p != NULL && tmp->line_number != line_number) {
tmp = tmp->p;
}
if (tmp->line_number != line_number) {
tmp->p = lalloc();
tmp->p->line_number = line_number;
tmp->p->p = NULL;
}
}
struct tnode *talloc(void)
{
return (struct tnode *) malloc(sizeof(struct tnode));
}
struct linked_list *lalloc(void)
{
return (struct linked_list *) malloc(sizeof(struct linked_list));
}
void treeprint(struct tnode *p)
{
struct linked_list *tmp;
if (p != NULL) {
treeprint(p->left);
printf("%s: ", p->word);
for (tmp = p->line_numbers; tmp != NULL; tmp = tmp->p) {
printf("%d ", tmp->line_number);
}
printf("\n");
treeprint(p->right);
}
}
int getword(char *word, int lim)
{
int c, d, getch(void), skipcomment();
void ungetch(int);
char *w = word;
while (isspace(c = getch()) && c != '\n')
;
if (c != EOF) {
*w++ = c;
}
if (isalpha(c) || c == '_' || c == '#') {
for (; --lim > 0; w++) {
if (!isalnum(*w = getch())) {
ungetch(*w);
break;
}
}
}
*w = '\0';
return c;
}
int noise_word(char *w)
{
/* https://drupal.org/node/1202 のNoise Words Listより */
char *noise_word[] = {
"$",
"0",
"1",
"2",
"3",
"4",
"5",
"6",
"7",
"8",
"9",
"a",
"b",
"about",
"after",
"all",
"also",
"an",
"and",
"another",
"any",
"are",
"as",
"at",
"be",
"because",
"been",
"before",
"being",
"between",
"both",
"but",
"by",
"c",
"came",
"can",
"come",
"could",
"d",
"did",
"do",
"e",
"each",
"f",
"for",
"from",
"g",
"get",
"got",
"h",
"had",
"has",
"have",
"he",
"her",
"here",
"him",
"himself",
"his",
"how",
"i",
"if",
"in",
"into",
"is",
"it",
"j",
"k",
"l",
"like",
"make",
"m",
"many",
"me",
"might",
"more",
"most",
"much",
"must",
"my",
"n",
"never",
"now",
"o",
"of",
"on",
"only",
"or",
"other",
"our",
"out",
"over",
"p",
"q",
"r",
"s",
"said",
"same",
"see",
"should",
"since",
"some",
"still",
"such",
"t",
"take",
"than",
"that",
"the",
"their",
"them",
"then",
"there",
"these",
"they",
"this",
"those",
"through",
"to",
"too",
"u",
"under",
"up",
"very",
"v",
"w",
"was",
"way",
"we",
"well",
"were",
"what",
"where",
"which",
"while",
"who",
"with",
"would",
"x",
"y",
"you",
"your",
"z"
};
int cond, mid;
int low = 0;
int high = sizeof(noise_word) / sizeof(char *) - 1;
while (low <= high) {
mid = (low + high) / 2;
if ((cond = strcmp(w, noise_word[mid])) < 0) {
high = mid - 1;
} else if (cond > 0) {
low = mid + 1;
} else {
return mid;
}
}
return -1;
}
#define BUFSIZE 100
char buf[BUFSIZE];
int bufp = 0;
int getch(void)
{
return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(int c)
{
if (bufp >= BUFSIZE) {
printf("ungetch: too many characters\n");
} else {
buf[bufp++] = c;
}
}
入出力結果(Terminal)
$ curl http://www.example.com | ./a.out
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
100 1270 100 1270 0 0 1245 0 0:00:01 0:00:01 --:--:-- 1788
Arial: 14
Content: 7
Domain: 4 44
Example: 4 44
Helvetica: 14
More: 47
Neue: 14
Open: 14
Sans: 14
This: 45
You: 45
asking: 46
auto: 19 33 34
background: 11 21 30
body: 10 29 42 49
border: 22 35
charset: 6 7
color: 11 21 25 30
content: 7 8
coordination: 46
css: 9
decoration: 26
device: 8
div: 17 32 43 48
doctype: 1
documents: 45
domain: 45 46
domains: 47
em: 19 22 36
equiv: 7
established: 45
example: 47
examples: 45 46
family: 14
font: 14
h1: 44
head: 3 40
href: 47
html: 1 2 7 50
http: 7 47
iana: 47
illustrative: 45
information: 47
initial: 8
link: 24
margin: 12 19 34
max: 28
may: 45
media: 28
meta: 6 7 8
name: 8
none: 26
org: 47
padding: 13 20 36
permission: 46
prior: 46
px: 18 20 28
radius: 22 35
sans: 14
scale: 8
serif: 14
style: 9 39
text: 7 9 26
title: 4
type: 7 9
use: 45
used: 45
utf: 6 7
viewport: 8
visited: 24
width: 8 18 28 33
without: 46
www: 47
$
0 コメント:
コメントを投稿