iT邦幫忙

DAY 15
5

emacs的30天學習筆記系列 第 38

懷舊C語言:1988 The C Programming Language 2nd Edition(PART VII)

實務上兩個星星**(*)算是最多了,有看過三個星星的使用嗎?
因為C語言的特性,字串陣列是二維的陣列,所以
char *str[]算常用吧,
這時用
char **str**,反而不易看出字串陣列,
我猜作者大概是這個用意吧?!!所以範例程式不太用char **str
也是可讀性的一種體現。
其他語言,有字串型別,字串陣列應該是一維陣列吧。

本書第三個qsort的版本,高級版(標準版?)
作者試著要process any data type, not just character strings.
第一個範例,處理數字,第二個範例處理字串陣列,
這個範例試圖要一起處理。
第三版原型如下:
void qsort(**void ***v[], int left, int right,
int (*comp)(void *, void *))

最引人注意的是void的使用。
第一個沒有帶星號的void, 表示沒有return值。
其他的帶星號的void,

The generic pointer type void * is used for the pointer arguments. Any pointer can be cast to void * and back
again without loss of information,

泛型(generic )指標型別void *,用來做指標的參數,任何指標可轉型(cast )
void *,且回復型別時不會遺失任何資訊。
*!@#,這段話,筆者不知道要怎麼驗証,算是定義(無需証明),還是定理(可以証明)呢?
因為要能夠處理各種型別,不給定某特定型別,所以就產生了void *用於這種特定用途。
所以void 和
void *
,共用void這個字,其意義是天差地遠。

int (*comp)(void *, void *)

which says that comp is a pointer to a function that has two void * arguments and returns an int
意思是說,comp 是指向函數的指標,這個函數(不指定名稱)是有2個void *參數,傳回整數的
原型。如果沒有看書,用舊有經驗來理解程式,所謂用除錯器來學習程式的人,幾乎沒辦法完整理解這段宣告。
也許理解成:一個名為comp函數,傳回指向int的指標,這個comp函數,有兩個void *參數,,沒有函數指標的概念時,會這樣理解,但不懂為什麼它這樣寫,就可以切換
strcmp,numcmp。一切是配套的。
原作者即使是這個小節,也2~3頁就帶過,所以本書雖精簡。

不禁回想作者在評論UNIX系統的設計,UNIX是簡單的系統,透過天才的眼光來看的話

UNIX 的KISS (Keep It Simple, Stupid)哲學,雖然貫穿整個系統,在看穿簡單的本質之前,應該也曾經把事情搞得很複雜過,才會找出簡單的本質。
第三版的code,特別排版後,放上來,之前真得誤以為程式碼功能會變色,還會自動縮排。原來是誤判!!

#include <stdio.h>
#include <string.h>
#define MAXLINES 5000 /* max #lines to be sorted */
char *lineptr[MAXLINES]; /* pointers to text lines */
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void qsort(void *lineptr[], int left, int right,
	   int (*comp)(void *, void *));
int numcmp(char *, char *);
int strcmp(char *, char *);
/* sort input lines */
main(int argc, char *argv[])
{
  int nlines; /* number of input lines read */
  int numeric = 0; /* 1 if numeric sort */
  if (argc > 1 && strcmp(argv[1], "-n") == 0)
    numeric = 1;
  if ((nlines = readlines(lineptr, MAXLINES)) >= 0) 
    {
      qsort((void**) lineptr, 0, nlines-1,
	    (int (*)(void*,void*))(numeric ? numcmp : strcmp));
      writelines(lineptr, nlines);
      return 0;
    } 
  else
    {
      printf("input too big to sort\n");
      return 1;
    }
}
  void swap(void *v[], int, int);
/* qsort: sort v[left]...v[right] into increasing order */
void qsort(void *v[], int left, int right,
	   int (*comp)(void *, void *))
{
  int i, last;

  if (left >= right) /* do nothing if array contains */
    return; /* fewer than two elements */
  swap(v, left, (left + right)/2);
  last = left;
  for (i = left+1; i <= right; i++)
    if ((*comp)(v[i], v[left]) < 0)
      swap(v, ++last, i);
  swap(v, left, last);
  qsort(v, left, last-1, comp);
  qsort(v, last+1, right, comp);
}
/* strcmp: return <0 if s<t, 0 if s==t, >0 if s>t */
int strcmp(char *s, char *t)
{
  for ( ; *s == *t; s++, t++)
    if (*s == '\0')
      return 0;
  return *s - *t;
}

/* numcmp: compare s1 and s2 numerically */
int numcmp(char *s1, char *s2)
{
  double v1, v2;
  v1 = atof(s1);
  v2 = atof(s2);
  if (v1 < v2)
    return -1;
  else if (v1 > v2)
    return 1;
  else
    return 0;
}

#define MAXLEN 1000 /* max length of any input line */
char *alloc(int);
/* readlines: read input lines */
int readlines(char **lineptr, int maxlines)
{
  int len, nlines;
  char *p, line[MAXLEN];
  nlines = 0;
  while ((len = getline(line, MAXLEN)) > 0)
    if (nlines >= maxlines || (p = alloc(len)) == NULL)
      return -1;
    else 
      {
	line[len-1] = '\0'; /* delete newline */
	strcpy(p, line);
	*(lineptr+nlines++)= p;
      }
  return nlines;
}

int getline(char *s,int lim)  //s[]->*s
{
  int c, i;
  for (i=0; i < lim-1 && (c=getchar())!=EOF && c!='\n'; ++i)
    *(s+i) = c; //s[i]

  if (c == '\n')
    {
      *(s+i) = c; // s[i]
      ++i;
    }
  *(s+i) = '\0'; //s[i]
  return i;
}
/* writelines: write output lines */
void writelines(char **lineptr, int nlines)
{
  int i;
  for (i = 0; i < nlines; i++)
    printf("%s\n", *(lineptr+i));
}

/* swap: interchange v[i] and v[j] */
void swap(char **v, int i, int j)
{
  char *temp;
  temp = *(v+i);
  *(v+i) = *(v+j);
  *(v+j) = temp;
}

#define ALLOCSIZE 10000 /* size of available space */
static char allocbuf[ALLOCSIZE]; /* storage for alloc */
static char *allocp = allocbuf; /* next free position */
char *alloc(int n) /* return pointer to n characters */
{
  if (allocbuf + ALLOCSIZE - allocp >= n)
    { /* it fits */
    allocp += n;
    return allocp - n; /* old p */
    }
  else /* not enough room */
    return 0;
}

筆者終於原著的原汁原味,故意把**#include <string.h>**註解掉,
用書中的strcmp函數,不解,為何作者不用自己編的呢?
如果沒註解掉,會產生

sort04.c:10:5: error: conflicting types for 'strcmp'
sort04.c:50:5: error: conflicting types for 'strcmp'

註解掉,
卻產生

sort04.c: In function 'readlines':
sort04.c:97:2: warning: incompatible implicit declaration of built-in function 'strcpy'

一個產生error,一個產生warning,值得再探討的小問題。

不知道是不是這個緣故,
執行結果,並不如預期,
字串陣列的排序符合預期,數字陣列的排序不符合。

$ a
You
Give
Love
A
Bad
Name
^Z
A
Bad
Give
Love
Name
You

加上 -n的參數

$ a -n
You
Give
Love
A
Bad
Name
^Z
Love
A
Give
Bad
You
Name

所以 -n 照題意是排序數字陣列,
目前效果是

$ a -n
88
77
66
55
44
33
22
11
^Z
55
44
77
33
88
22
66
11

莫非筆者找到了bug??

今天事忙,改天再深究了。


上一篇
懷舊C語言:1988 The C Programming Language 2nd Edition(PART VI)
系列文
emacs的30天學習筆記38
0
chiounan
iT邦研究生 1 級 ‧ 2011-11-17 09:12:43

讚清楚又好讀

0
sula3065408
iT邦研究生 1 級 ‧ 2011-11-17 14:31:52

timloo提到:
泛型(generic )指標型別void *,用來做指標的參數,任何指標可轉型(cast )
成void *,且回覆型別時不會遺失任何資訊。
*!@#,這段話,筆者不知道要怎麼驗證,算是定義(無需證明),還是定理(可以證明)呢?
因為要能夠處理各種型別,不給定某特定型別,所以就產...(恕刪)

那是因為指標就是指標,當你宣告指標的時候,要到的是一個int的空間,要存的是位址,對位址怎麼搬都是位址,怎麼可能損失什麼資訊。
就算不是void *,你把位址搬來搬去,也不會損失什麼資訊阿,這也不是void的專利。
假設機器是32bit,宣告一個指標得到變數A的位址是12345678H,把變數填入87654321H如下
A[12345678H:87654321H]-*->char[87654321H:'a']
再宣告一個void *變數B得到位址1234567C
B[1234567C:????????H]-*->void[????????H:?]
然後填入變數A的值如下指令
B=(void *)A;
事實上只是把位址搬過去而已,就變成如下的狀態
B[1234567C:87654321H]-*->void[87654321H:'a']

函式宣告成void型別變數只會讓Compiler不幫你檢查型別而已,變數內容就拷貝到另外一個變數去了。

這樣解釋應該清楚一點了吧~~哈哈

timloo iT邦研究生 2 級 ‧ 2011-11-18 00:31:09 檢舉

A[12345678H:87654321H]-*->char[87654321H:'a']
這是表達意思用?還是真可以這樣寫?
我不太懂意思。

函式宣告成void型別變數只會讓Compiler不幫你檢查型別而已


我也同意。

這個程式 ,真沒保握以後可以常應用,覺得好神,

&lt;pre class="c" name="code">int (*comp)(void *, void *)

這段
<pre class="c" name="code">(int ()(void,void*))(numeric ? numcmp : strcmp));

和上段,編譯器 是怎麼判讀的呢?

感覺comp好像不用寫也沒關係?不寫又很怪,總會用到comp來表示函數名稱。

void *
算是沒有繼承的C語言,確有泛型的指標,來多型嗎?突然有這種念頭,不知道對不對。

timloo iT邦研究生 2 級 ‧ 2011-11-18 00:31:09 檢舉

A[12345678H:87654321H]-*->char[87654321H:'a']
這是表達意思用?還是真可以這樣寫?
我不太懂意思。

函式宣告成void型別變數只會讓Compiler不幫你檢查型別而已


我也同意。

這個程式 ,真沒保握以後可以常應用,覺得好神,

&lt;pre class="c" name="code">int (*comp)(void *, void *)

這段
<pre class="c" name="code">(int ()(void,void*))(numeric ? numcmp : strcmp));

和上段,編譯器 是怎麼判讀的呢?

感覺comp好像不用寫也沒關係?不寫又很怪,總會用到comp來表示函數名稱。

void *
算是沒有繼承的C語言,確有泛型的指標,來多型嗎?突然有這種念頭,不知道對不對。

sula3065408 iT邦研究生 1 級 ‧ 2011-11-18 14:22:20 檢舉

當然只是用來解釋變數名稱、位址、內容與指標的關係而已。

有個外國神人寫過一本英文書(書名忘了),就是用C語言來做物件導向,其中有一段就是要C做泛型,而他實現封裝靠的是結構,看完那本書會功力大增。
我看完發現,不是做不到只是我C還太嫩了而已。~XD

int (*comp)(void *, void *)<--宣告一個變數存位址當成函式而已,被為「函式指標」

(int (*)(void*,void*)) <--強迫轉型因為後面要取變數內的數值當位址,叫Compiler不用檢查了,我說了算 ~ XD
(numeric ? numcmp : strcmp)) <--三元運算是若numeric不為0則取numcmp當位址用否則取strcmp當位址用

本來就不用寫comp,舉例說phtotype是:void fnXXX(int a);
你呼叫函式不是這樣寫嗎?
fnXXX(199);
a<--應該沒啥用處了吧

所以函式comp變數的型別是這個東西(int (*)(void*,void*)) <-- 函式指標型別,comp是他的變數名稱

0
krarm
iT邦好手 1 級 ‧ 2011-11-17 21:50:29

timloo提到:
如果沒註解掉,會產生
sort04.c:10:5: error: conflicting types for 'strcmp'
sort04.c:50:5: error: conflicting types for 'strcmp'

改成這樣試試!!!!
int strcmp(const char *s, const char *t) {
....
}

timloo iT邦研究生 2 級 ‧ 2011-11-18 00:04:17 檢舉

strcmp 是字串比較,不會對傳入的字串做處理,純拿來比較,加上const ,倒還沒有理解const的意思,看來不是static的意思,謝謝,我再試試幾個const的狀況來理解這種用法。修飾傳入的兩個參數。

krarm iT邦好手 1 級 ‧ 2011-11-18 09:24:23 檢舉

最主要是string.h中有一段這樣的宣告,
short strcmp (const unsigned char *s1, const unsigned char *s2);
如果自己寫的字串比較換個名字,例如my_strcmp就ok拉。

const的意思是在它的scope中,變數的內容是不可以變的。
static靜態變數的意思是會取用上次使用的值,變數的內容是可以變的。

c++還有char *const這種東西,指的是指標本身的記憶體位址不變,但記憶體內容可以變,
C有沒有這個用法?我不太確定,至少我是修oop時學到的。

0
krarm
iT邦好手 1 級 ‧ 2011-11-17 21:51:53

timloo提到:
所以 -n 照題意是排序數字陣列,
目前效果是
$ a -n
88
77
66
55
44
33
22
11
^Z
55
44
77
33
88
22
66
11

加上這行試試!!!!
double atof(const char *);

0
timloo
iT邦研究生 2 級 ‧ 2011-11-18 00:09:52

也是const, 這樣可以說明,1988年,那個c 編譯器,不需要const修飾,便能正確執行(那個年代的c編譯器是比較聰明嗎??),
而2011年的gcc, 要const 才能要正確的結果,
倒是加深我對const的印象,

也對const對輸出結果的影響產生好奇。

有蠻多想試的。

sula3065408 iT邦研究生 1 級 ‧ 2011-11-18 14:34:41 檢舉

const你要去看記憶體與變數的對應表,看Compiler把變數宣告到那個區段去了,通常是code的區段,如果是在哈佛架構的計算機上的話,就會是在ROM的記憶體區塊內,變成唯讀,如果是在泛紐曼架構的計算機上,code區段還是在ram中,所以讀、寫都沒差別(如果你作業系統不攔你的話),至於哪一版有哪些限制,哪一版又沒有、聰不聰明,我就沒認真的去比對了。

C語言很多動作很「簡單」,這個簡單常常是直接對應到計算機架構上,如果你把兩個東西貫穿來看的話。

0
krarm
iT邦好手 1 級 ‧ 2011-11-18 09:45:00

timloo提到:
int (*comp)(void *, void *)

既然叫做函數指標,就是指標,指標不就是變數嗎?把comp當作一個變數來看就好了。

timloo提到:
(int (*)(void*,void*))(numeric ? numcmp : strcmp)

這個其實很簡單,先判斷numeric是不是0,不是則傳回numcmp這個變數,是0則傳回strcmp,
(int (*)(void*,void*))就只是強制轉型。

0
krarm
iT邦好手 1 級 ‧ 2011-11-18 09:55:35

timloo提到:
這個程式 ,真沒保握以後可以常應用,覺得好神,

void *v[]這個資料型態,讓你可以對大部分的資料型態進行排序,包含struct
例如學測分數,就是一個結構,然而每一科系對排名的定義不同,就是不同的函數指標,
其實qsort是滿常用的,因為彈性夠且速度快,原因有四點:

  1. 由函數指標來指定比較大小的方法。
  2. qsort只搬動記憶體位址,速度滿快的。
  3. 還有就是迷人的O(nlgn)時間複雜度。
  4. 最後就stdlib.h直接提供,也不用寫。

有寫錯請指正,太久沒有摸C/C++了。

0
timloo
iT邦研究生 2 級 ‧ 2011-11-24 22:18:42

謝謝兩位指教。

誠如邦友k先生所指出,stdlib.h沒有引入,為了測試大師的qsort,確讓atof異常。

&lt;pre class="c" name="code">#include &lt;stdio.h>

int numcmp(const char *s1, const char *s2)  ;

int main(void)
{
 char a[8]="12.34";
 char b[8]="3.2";
 int i;
 i = numcmp(a,b);
 printf("%d  \n",i);
 char c[8]="11.21";
 char d[8]="11.21";
 i = numcmp(c,d);
 printf("%d  \n",i);

 char e[8]="4.21";
 char f[8]="11.21";
 i = numcmp(e,f);
 printf("%d  \n",i);

 
}

int numcmp(const char *s1, const char *s2)  
{  
  double v1, v2;  
  v1 = atof(s1);  
  v2 = atof(s2);  
  if (v1 &lt; v2)  
    return -1;  
  else if (v1 > v2)  
    return 1;  
  else  
    return 0;  
}  

測試執行

$ gcc t03.c -g
$ a
0
0
0

結果不正確,
加上stdlib.h,

$ a
1
0
-1

結果正確

0
timloo
iT邦研究生 2 級 ‧ 2011-11-24 22:28:56

在mingw下,沒有引入 stdlib.h, 就用atof, 為什麼不會有error,或是warning,

類似undefined refererence 的錯誤,但是間接讓numcmp函數失效,又讓qsort無法正確排序數字,不遇到,說給人聽,大概沒人信!!

看兩位的留言,倒讓小弟受益良多。這陣子,在 user 打電話 問tiptop的空檔,就是練習
一些c的習題。還好有你們給的線索,蠻順利找出問題的來源。

小結:大師的習題中,也有自己實作atof的習題,小弟偷懶,沒實作。

glibc 是gcc的標準庫,因邦友的指教,小弟還跑去看原始碼。

謝謝兩位,提供很多參考。

我要留言

立即登入留言