質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

4回答

1020閲覧

C言語での文字列の照合アルゴリズム

退会済みユーザー

退会済みユーザー

総合スコア0

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2018/06/11 11:59

「C言語によるはじめてのアルゴリズム入門」という本の3-6にある「文字列の照合」
でのソースコードで理解できないところがあります。
下記のコードで
for (p = text; p <= text + m - n; p++)
という部分があるのですがtextは文字列なのにfor分のなかにあり、整数であるm-nを加えていて、
このコードがどういう動きをしているのか分かりません。
p=text(文字列)とはどういう意味なのでしょうか
初歩的な質問で申し訳ないのですがお願いしますm(__)m

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

C ソースコード

#include "stdafx.h"
#include <string.h>

char *search(char *, char *);

void main(void)
{
static char text[] = "This is a pen.That is a pensil.";
char *p, *key = "pen";

p = search(text, key); while (p != NULL) { printf("%s\n", p); p = search(p + strlen(key), key); }

}

char *search(char *text, char *key)
{
int m, n;
char *p;

m = strlen(text); n = strlen(key); for (p = text; p <= text + m - n; p++) { if (strncmp(p, key, n) == 0) return p; } return NULL;

}

試したこと

ここに問題に対して試したことを記載してください。

補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答4

0

char *search(char *text, char *key)

では、textは文字列の先頭アドレス(ポインタ)なので、加減算ができます。
従って、 text + m - nは文字列の先頭+文字列長ー検索する文字列長になります。
要は、文字列先頭から検索する文字列長を引いた値まで検索しているだけです。

投稿2018/06/11 12:11

cateye

総合スコア6851

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2018/06/11 13:15

なるほどtextは文字列の先頭のアドレスを表していてそれにm-nを加えることで先頭から文字列長ー検索する文字列長までを繰り返しているということですね わかりやすい説明ありがとうございました すっきりしました
guest

0

C言語では「文字列」は,宣言と同時に配列型変数に代入する場合は**「NULL終端する文字の配列」**と一般的には等価です。
(厳密には,ポインタ型変数に代入したりインラインリテラルとして使用する場合はメモリ確保の方法が少し異なります)

c

1static char text[] = "This is a pen.That is a pensil.";

c

1static char text[] = {'T', 'h', 'i', 's', ' ', 'i', 's', ' ', 'a', ' ', 'p', 'e', 'n', '.', 'T', 'h', 'a', 't', ' ', 'i', 's', ' ', 'a', ' ', 'p', 'e', 'n', 's', 'i', 'l', '.', '\0'};

上記2つは等価です。

  • 整数としておなじみの int は一般的には値の範囲が -21474836482147483647 の数値です。(環境に左右されます)
  • 文字としておなじみの char も実は値の範囲が -128127 の数値です。各番号に形式上文字が割り当てられているだけの話です。ASCII文字コード - IT用語辞典
  • char のアドレスを表す char * もまた数値です。32ビット環境では -21474836482147483647,64ビット環境では -92233720368547758089223372036854775807 になります。

ここでたとえば text0x80000000 番地(16進数表記)から始まっていると仮定すると,各アドレスに対応するデータは以下のようになります。

c

10x80000000 84 (T) 20x80000001 104 (h) 30x80000002 105 (i) 40x80000003 115 (s) 50x80000004 32 ( ) 60x80000005 105 (i) 70x80000006 115 (s) 80x80000007 32 ( ) 90x80000008 97 (a) 100x80000009 32 ( ) 110x8000000a 112 (p) 120x8000000b 101 (e) 130x8000000c 110 (n) 140x8000000d 46 (.) 150x8000000e 84 (T) 160x8000000f 104 (h) 170x80000010 97 (a) 180x80000011 116 (t) 190x80000012 32 ( ) 200x80000013 105 (i) 210x80000014 115 (s) 220x80000015 32 ( ) 230x80000016 97 (a) 240x80000017 32 ( ) 250x80000018 112 (p) 260x80000019 101 (e) 270x8000001a 110 (n) 280x8000001b 115 (s) 290x8000001c 105 (i) 300x8000001d 108 (l) 310x8000001e 46 (.) 320x8000001f 0 (\0)

C言語においては int 型に限らず charchar * も加算・減算することができます。今回は char * の加算を利用しています。

一般的にC言語における文字列はNULL終端している必要がありますが,strncmpに関しては,「探される文字列」側はNULL終端している必要がありません。(strncmp を参照)そのため,今回のコードで書いているような以下のアルゴリズムが利用できます。

  • 「探される文字列」の先頭アドレスを1つずつずらしていく
  • 現在のアドレスから「探す文字列」の長さのぶんだけ strncmp 関数にチェックさせる

1回目: Thipen が一致するか?
2回目: hispen が一致するか?
3回目: is pen が一致するか?
4回目: s apen が一致するか?
5回目: apen が一致するか?
6回目: a ppen が一致するか?
7回目: pepen が一致するか?
8回目: penpen が一致するか?

投稿2018/06/11 13:28

編集2018/06/11 13:43
mpyw

総合スコア5223

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2018/06/11 13:39

C言語における文字列の定義からさまざまな事柄に関して丁寧な説明本当にありがとうございます! C言語への理解が少し深まりました ここまでの説明をぱっとできるなんて本当にすごいです! ありがとうございます!
退会済みユーザー

退会済みユーザー

2018/06/11 13:41

標準関数に同じことができるものがあるんですね… まだ全然そこらへんを知らないので勉強していこうと思います ありがとうございます
guest

0

ベストアンサー

p = text

char のポインタを代入してます

p <= text + m - n

 pとtext+m-n のアドレスとを比較してます

p++

pをインクリメントしてます

その他不明なところはあるでしょうか

投稿2018/06/11 12:10

y_waiwai

総合スコア87719

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2018/06/11 13:15

textは先頭アドレスを表しているということを完全に忘れていました for文でアドレスを比較するのは初めての経験だったので分かりやすい説明ありがとうございます! その他不明な点としてmain関数内での while (p != NULL) { printf("%s\n", p); p = search(p + strlen(key), key); } でprintfしているpはこのtextの文章で最初にkeyであるpenが見つかったアドレス以降の文字列を表示しているからこのソースを実行すると一行目には pen.That is a pensil.が表示される そして p = search(p + strlen(key), key); ではp(前にkeyが見つかったアドレスの先頭)にkeyの長さを加えてまたsearch関数に入れることで次のkeyが出てくるアドレスを探し同じように 見つかったアドレスを返してそのアドレス以降の文字列を表示するので二行目はpensil. になるということであってますかね!? 重ね重ねすいません
y_waiwai

2018/06/11 13:22

それであってます パズルみたいなもんで、読み込んでいくと面白いですね
退会済みユーザー

退会済みユーザー

2018/06/11 13:28

重ね重ねありがとうございました
guest

0

ポインタとかアドレスの概念をまず勉強しましょう。

多分、概念を理解されていません。失礼ながら基礎なしではそもそも議論にならないと思いますよ。

投稿2018/06/11 12:58

HogeAnimalLover

総合スコア4830

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問