结构化数据

结构化数据

       结构变量名称和成员名称间的句点是一个运算符,成为成员选择运算符     如果指定了结构变量的指针,那么可以使用->来访问成员,->称为成员指针运算符。

      

       有时,我们分配了很多的内存,而实际上我们是不需要那么多内存的,比如struct horse myhorse[100],有时可能只使用了2个结构体,那么就会浪费98个相同量级的内存。那么此时我们就可以使用指针来动态分配内存,节省内存。

       方式我struct horse *pmyhorse[100],而这样只是分配了指针的内存,然后我们可以使用循环malloc来分配一个内存,使用完后free掉,那么此时如果对于结构体比较大的数据而言,可以节省很多的内存。

*如果我们在结构体中递归定义了struct horse *next,就可以不用分配指针内存,照样可以工作~,此时的结构体就是一个链表。

       在使用结构体的时候需要注意,结构体的字节数有时并不是所有成员的和,编译器有时为了优化以及速度方面的考虑,会是24的整数倍,这里就设计到了边界调整(boundary alignment)。

       所有的基本数据类型(包含数组)都可以成为结构的成员,除此之外,还可以把一个结构作为另一个结构的成员,不仅指针可以是结构的成员,结构指针也可以是结构的成员。

       不过,c编译器值允许结构最多有15层,并且,每一次都需要输入所有的结构成员名称。

       需要处理数量未知的结构的应用程序中,链表非常有用,链表的主要优点是内存的使用和便于处理。存储和处理链表所占用的内存量最少,即使所使用的内存比较分散,也可以从一个结构进入下一个结构。因此,链表可以用于同时处理几个不同类型的对象,每个对象都可以用它自己的链表来处理,以优化内存的使用。但链表也有一个小缺点,数据处理的速度比较慢,尤其是要随机访问数据时,速度更慢。

链表的概念:

clip_image002

结构中的位字段

clip_image004

       位字段提供的机制允许定义变量来表示一个整数中的一个或多个位,这样,就不需要为每个位明确指定成员名称了。

       位字段常用在必须节省内存的情况下,但是位字段会明显降低程序执行的速度。

       上面的示例表明,flag1有一个字节,flag43个字节。

结构及指针作为函数的变元

clip_image006

       在调用函数时,传送给函数的是变元值的副本。如果变元是一个非常大的结构,就需要相当多的时间,并占用结构副本的内存。在这种情况下,应该使用结构指针作为变元,这可以避免占用内存,节省复制的时间,因为只需要复制指针,函数也可以通过指针直接访问原来的结构。另外,使用指针给函数传送结构,也提高了效率。

clip_image008

两个的区别:

1.      将参数的类型指定为horse结构的常量指针;

2.      将参数指定为指向horse结构类型的常量指针。

二叉树

       二叉树的实现涉及到递归和动态分配内存,还要使用指针传送结构。

       二叉树包含一系列相互关联的元素,称为节点。起始节点是树的根,称为根节点。每个节点一般包括一个数据项,以及两个指向后续节点的指针(左节点和右节点)。如果有一个后续节点不存在,对应的指针就是NULL。节点还可以包含 一个计数器,记录树中合适有重复的数据项。

       在二叉树中添加数据项的时候,需要从树中的根节点开始,比较树中节点的值和新项。如果新项比给定的节点小,就查看节点的左子结点,反之,就查看右子结点。

       比如一个节点定义和创建根节点为:

clip_image010

个人感觉比较帅的就是在插入节点是的递归调用,awesome~

clip_image012

而对于遍历二叉树也是很方便的:

clip_image014

整体的程序为:

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

 

struct Node *createnode(long value);

struct Node *addnode(long value,struct Node* pNode);

void listnodes(struct Node *pNode);

void freenodes(struct Node *pNode);//release memory

 

 

struct Node

{

               long item;//The data item

               int count;//Number of copies of item

               struct Node *pLeft;//Pointer to left node

               struct Node *pRight;//Pointer to right node

};

 

int main(void)

{

               long newvalue = 0;

               struct Node *pRoot = NULL;

               char answer = ‘n’;

               do

               {

                               printf("Enter the node values:");

                               scanf("%ld",&newvalue);

                               if(pRoot == NULL)

                                              pRoot = createnode(newvalue);

                               else

                                              addnode(newvalue,pRoot);

                               printf("\nDo you want to enter another (y or n)?");

                               scanf("%c",&answer);

               }while(tolower(answer) == ‘y’);

 

               printf("The values iin ascending sequence are: ");

               listnodes(pRoot);//output the contents of the tree

               freenodes(pRoot);

 

               return 0;

}

 

 

//create the root node

struct Node *createnode(long value)

{

               //allocate memory for a new node

               struct Node *pNode = (struct Node *)malloc(sizeof(struct Node));

 

               pNode -> item = value;//set the value

               pNode -> count = 1;//set the count

               pNode -> pLeft = pNode -> pRight = NULL;//No left or right nodes

               return pNode;

}

 

//insert node

struct Node *addnode(long value,struct Node* pNode)

{

               if(pNode == NULL)//if there is no node

                               return createnode(value);//then create one and return it

 

               if(value == pNode->item)//value equals current node

                               {

                               ++pNode->count;//…so increment count and

                               return pNode;//…return the same node

               }

 

               if(value < pNode->item)//if less than current node value

                               {

                               if(pNode->pLeft == NULL)//and there’s no left node

                                              {

                                              pNode->pLeft = createnode(value);//create a new left node and

                                              return pNode->pLeft;//return it

                               }

                               else//if there is a left node

                                              return addnode(value,pNode->pLeft)//add value via the left node

               }

               else//value is greater than current

                               {

                               if(pNode->pRight) == NULL)//so the same process with

                                              {

                                              pNode->pRight = createnode(value);//the right node

                                              return pNode->pRight;

                               }

                               else

                                              return addnode(value,pNode->pRight);

               }

}

 

//list the node values in ascending sequence

void listnodes(struct Node *pNode)

{

               if(pNode->pLeft != NULL)

                               listnodes(pNode->pLeft);//list nodes in the left subtree

               for(int i =0;i<pNode->count;i++)

                               printf("\n%10ld",pNode->item);//output the current node value

               if(pNode->pRight != NULL)

                               listnodes(pNode->pRight);//list nodes in the right subtree

}

 

 

void freenodes(struct Node *pNode)//release memory

{

               if(pNode == NULL)

                               return ;

               if(pNode -> pLeft != NULL)

                               freenodes(pNode -> pLeft);

               if(pNode -> pRight != NULL)

                               freenodes(pNode -> pRight);

               free(pNode);

}

 

 

可以使用二叉树来存储任意类型的数据,包括结构对象和字符串,如果要在二叉树中组织字符串,就可以在每个节点中使用指针引用字符串,而无须复制树中的字符串

共享内存联合

       前面说过的位字段bit-field节省内存,一般用于逻辑变量,c语言中还有union联合可以将几个变量放在相同的内存区中,并且这个功能在内存短缺时比位字段应用的更广,因为实际上,我们常常使用几个变量,但是只有一个变量在任意给定的时刻为有效。

       多个变量共享内存的另一种情形是,程序处理许多不同类型的数据,但是一次只能处理一种,要处理的类型在执行期间确定。

       C语言中,允许在多个不同变量共享同一内存区的功能成为联合union。联合的声明和定义与struct类似。

clip_image016

我们可以通过sizeof的值,整个联合所占用的空间为其中成员占用最大的空间。

注意:在声明联合时,若需要初始化联合的实例,只能用和联合中第一个变量相同类型的常量进行初始化

       由于联合中占用相同的内存,所以在每次使用值的时候要确认一下联合当时所使用的类型。

定义自己的数据类型

       前面关于结构体的声明都比较复杂,比如struct point point1;为声明一个

struct point的变量point1,测试可以使用typedef struct point MyPoint,然后只需要使用MyPoint point1即可,这对于复杂的结构体,好处自然不言而喻。比如:typedef struct pts *pPoint

然后使用pPoint p1;就可以知名p1为执行结构体pts的指针。

 

而对于前面定义过的函数指针:

int (*pfun)(int,int);

只需在前面加上typedef即可将原来的函数指针声明为pfun

typedef int (*pfun)(int,int);

pfun pfun1

示例

clip_image018

源码

/* Program 11.9 Generating a bar chart */

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stdbool.h>

 

#define PAGE_HEIGHT  20

#define PAGE_WIDTH   40

 

typedef struct barTAG

{

  double value;

  struct barTAG *pnextbar;

}bar;

 

typedef unsigned int uint;     /* Type definition*/

 

/* Function prototype */

int bar_chart(bar *pfirstbar, uint page_width, uint page_height, char *title);

 

int main(void)

{

  bar firstbar;            /* First bar structure */

  bar *plastbar = NULL;    /* Pointer to last bar */

  char value[80];          /* Input buffer        */

  char title[80];          /* Chart title         */

 

  printf("\nEnter the chart title: ");

  gets(title);             /* Read chart title    */

 

  for( ;; )                /* Loop for bar input  */

  {

    printf("Enter the value of the bar, or use quit to end: ");

    gets(value);

 

    if(strcmp(value, "quit") == 0)   /* quit entered?       */

     break;                          /* then input finished */

 

    /* Store in next bar */

    if(!plastbar)                /* First time?             */

    {

      firstbar.pnextbar = NULL;  /* Initialize next pointer */

      plastbar = &firstbar;      /* Use the first           */

    }

    else

    {

      /* Get memory */

      if(!(plastbar->pnextbar = malloc(sizeof(bar))))

      {

        printf("Oops! Couldn’t allocate memory\n");

        return 1;

      }

      plastbar = plastbar->pnextbar;    /* Old next is new bar  */

      plastbar->pnextbar = NULL;        /* New bar next is NULL */

    }

    plastbar->value = atof(value);      /* Store the value      */

  }

 

  /* Create bar-chart */

  bar_chart(&firstbar, PAGE_WIDTH, PAGE_HEIGHT, title);

 

  /* We are done, so release all the memory we allocated */

  while(firstbar.pnextbar)

  {

    plastbar = firstbar.pnextbar;           /* Save pointer to next */

    firstbar.pnextbar = plastbar->pnextbar; /* Get one after next   */

    free(plastbar);                         /* Free next memory     */

  }

  return 0;

}

 

int bar_chart(bar *pfirstbar, uint page_width, uint page_height,

                                                       char *title)

{

  bar *plastbar = pfirstbar;  /* Pointer to previous bar         */

  double max = 0.0;           /* Maximum bar value               */

  double min = 0.0;           /* Minimum bar value               */

  double vert_scale = 0.0;    /* Unit step in vertical direction */

  double position = 0.0;      /* Current vertical position on chart */

  uint bar_count = 1;         /* Number of bars – at least 1     */

  uint barwidth = 0;          /* Width of a bar                  */

  uint space = 2;             /* spaces between bars             */

  uint i = 0;                 /* Loop counter                    */

  uint bars = 0;              /* Loop counter through bars       */

  char *column = NULL;        /* Pointer to bar column section   */

  char *blank = NULL;         /* Blank string for bar+space      */

  bool axis = false;          /* Indicates axis drawn            */

  /* Find maximum and minimum of all bar values */

 

  /* Set max and min to first bar value */

  max = min = plastbar->value;

 

  while((plastbar = plastbar->pnextbar) != NULL)

  {

    bar_count++;              /* Increment bar count */

    max = (max < plastbar->value)? plastbar->value : max;

    min = (min > plastbar->value)? plastbar->value : min;

  }

  vert_scale = (max min)/page_height; /* Calculate step length */

 

  /* Check bar width */

  if((barwidth = page_width/bar_count space) < 1)

  {

    printf("\nPage width too narrow.\n");

    return 1;

  }

 

  /* Set up a string that will be used to build the columns */

 

  /* Get the memory */

  if((column = malloc(barwidth + space + 1)) == NULL)

  {

    printf("\nFailed to allocate memory in barchart()"

                           " – terminating program.\n");

    exit(1);

  }

  for(i = 0 ; i<space ; i++)

    *(column+i)=‘ ‘;         /* Blank the space between bars */

  for( ; i<space+barwidth ; i++)

    *(column+i)=‘#’;         /* Enter the bar characters     */

  *(column+i) = ‘\0’;        /* Add string terminator        */

 

  /* Set up a string that will be used as a blank column */

 

  /* Get the memory */

  if((blank = malloc(barwidth + space + 1)) == NULL)

  {

    printf("\nFailed to allocate memory in barchart()"

                           " – terminating program.\n");

    exit(1);

  }

 

  for(i = 0 ; i<space+barwidth ; i++)

    *(blank+i) = ‘ ‘;        /* Blank total width of bar+space */

  *(blank+i) = ‘\0’;         /* Add string terminator          */

 

    printf("^ %s\n", title);   /* Output the chart title      */

 

  /* Draw the bar chart */

  position = max;

  for(i = 0 ; i <= page_height ; i++)

  {

    /* Check if we need to output the horizontal axis */

    if(position <= 0.0 && !axis)

    {

      printf("+");           /* Start of horizontal axis    */

      for(bars = 0; bars < bar_count*(barwidth+space); bars++)

        printf("-");         /* Output horizontal axis      */

      printf(">\n");

      axis = true;           /* Axis was drawn              */

      position -= vert_scale;/* Decrement position           */

      continue;

    }

    printf("|");             /* Output vertical axis        */

    plastbar = pfirstbar;    /* start with the first bar    */

 

    /* For each bar… */

    for(bars = 1; bars <= bar_count; bars++)

    {

      /* If position is between axis and value, output column */

      /* otherwise output blank                               */

      printf("%s", position <= plastbar->value &&

                    plastbar->value >= 0.0 && position > 0.0 ||

                    position >= plastbar->value &&

                    plastbar->value <= 0.0 &&

                    position <= 0.0 ? column: blank);

      plastbar = plastbar->pnextbar;

    }

    printf("\n");            /* End the line of output        */

    position -= vert_scale;  /* Decrement position            */

  }

  if(!axis)            /* Have we output the horizontal axis? */

  {                    /* No, so do it now                    */

    printf("+");

    for(bars = 0; bars < bar_count*(barwidth+space); bars++)

      printf("-");

    printf(">\n");

  }

 

  /* Code for rest of the function…  */

  free(blank);               /* Free memory for blank string   */

  free(column);              /* Free memory for column string  */

  return 0;

}

 

 

 

基本输入和输出操作

基本输入和输出操作

       与大多数现代编程语言一样,C语言也没有输入输出的能力,所有这类操作都由标准库中的函数提供。

       stderr流只是将来自C库的错误信息传送出去,也可以将自己的错误信息传送给stderrstderrstdout之间的主要差别是,输出到stdout的流在内存上缓存,所以写入stdout的数据不会马上送到设备上,而stderr不缓存,所以写入到stderr的数据会立刻传送到设备上。对于缓存的流,程序会在内存中传入或传出缓存区域的数据,在物理设备上传入或传出数据可以异步进行。这使输入输出比较高效,而为错误信息使用不缓存的流,其优点是可以确保错误信息显示出来,但输出操作是低效的。缓存的流比较高效,但是如果程序因某种原因失败,缓存的流就不会刷新,所以输出可能永远不会显示出来。

       scanf()会忽略空白字符。

scanfprintf中有个格式控制符%n:表示输出有效字符的数量。

       N多的scanf参数也可以保证,你可以用许多方式得到自己希望得到的数据

但是有一点需要注意,就是scanf对输入格式很挑剔,稍微错一点就会导致整个读取输入出错。

     scanf的格式控制符%s只能读取不含空格的字符串,但是%[]可以读取包含空格的字符串,比如I love you,就可以全部读取。

       scanf的陷阱

l  变元必须是指针,最常犯的错误是将变量指定为scanf的变元时,忘记在变量名的前面加上&符号,不过使用printf时不需要这个&字符,此外,如果变元时数组名或指针变量,也不需要&符号;

l  在读字符串时,要确保有足够的空间存放读入的字符串,这个字符串需包含终止字符’\0’,否则,会覆盖内存中的饿数据,甚至是程序代码。

 

对于字符串输入,使用getsfgets通常是首选方式,除非要控制字符串的内容。

函数再探-已经发布

函数再探已经发布

       指针对于操作数据和含有数据的变量时一个非常有用的工具。只要有一个指针就可以处理所有的数据。同样,使用指针也可以操作函数,函数的内存地址存储了函数开始执行的位置,存储在函数指针中的内容就是这个地址。

声明函数指针

       函数指针的声明看起来有点奇怪,容易混淆,比如,模式为:

int (*pfunction) (int);

       注意pfunction*的括号不能去掉,不然就不是一样的含义了,就编程了pfunction函数的声明了。

通过函数指针调用函数

       比如有如下函数原型:

int sum(int a, int b);

可以通过int (*pfun)(int,int)=sum;来将sum的地址存储在指针pfun中,然后我们就可以使用pfun了,比如:

int result = pfun(45,55);

       所以,我们看到其实函数的用法非常类似于数组,如果需要的是数组的地址,只要使用数组名即可,同样,如果需要的是函数的地址,也是只使用函数名即可。

函数指针数组

       函数指针和一般的变量是一样的,所以可创建函数指针的数组。要声明函数之后在呢数组,只需将数组的大小放在函数指针数组名之后即可,例如:

       int (*pfunctions[10]) (int);

使用:

int sum(int a, int b);

int (*pfunctions[10]) (int,int);

pfunctions[0] = sum;

就可以使用pfunctions[0](xy);来计算xy的和。

也可以这样初始化指针数组的所有元素:

int (*pfunctions[3]) (int,int) = {sum,product,difference};

作为变元的函数指针

       函数指针也可以作为变元来传递,这样就可以根据指针所指向的函数,而调用不同的函数了。比如:

       int any_function(int (*pfun)(int,int),int x,int y);

 

int any_function(int (*pfun)(int,int),int x,int y)

{

       return pfun(x,y);

}

 

       将程序分解为函数,不仅简化了开发程序的过程,还增强了程序语言解决问题的能力。设计优良的函数常常可以重用,使新应用程序的开发变得更快、更简单。标准库就证明了可重用函数的威力。

静态常量:函数内部的追踪

       C语言中的一个关键字static声明的为静态常量,特点为:

l  虽然static在函数的作用域内定义,但是当执行退出该函数后,这个静态变量不会删除;

l  自动变量每次进入作用域时,都会初始化一次,但是声明为static的变量只在程序开始时初始化一次;

l  静态变量只能在包含其声明的函数中可见,但是它是一个全局变量,因此可以用全局变量的方式使用它;

l  只要程序开始执行,静态变量就一直存在,但是它只能在声明它的范围内可见,不能再该作用域的外部引用。

 

对于全局变量,虽然很有好处,比如可以简化并缩短某些程序,但是过度使用会使程序容易出错,主要原因是很容易修改全局变量,而忘记它对整个程序带来的后果。所以,最好不要给本地变量和全局变量使用相同的名字,这不但没有好处,反而有坏处。

变元个数可变的函数

       标准库stdarg.h提供了编写这种函数的例程。

比如,一个求均值的函数:

double average(double v1,double v2,…)

{

       va_list parg;

       double sum = v1 + v2;

       double value = 0;

       int count = 2;

 

       va_start(parg,v2);

       while((value = va_arg(parg,double)) != 0.0 )//这里要求最后一个值为0

{

              sum += value;

              count ++;

}

       va_end(parg);

       return sum/count;

}

长度可变的变元列表的基本规则

l  在变元数目可变的函数中,至少要有一个固定变元;

l  必须调用va_start初始化函数中可变变元列表指针的值,变元指针的类型必须声明为va_list类型;

l  必须有确定每个变元类型的机制;

l  必须有确定何时终止变元列表的方法;

l  va_arg的第二个变元指定了变元值的类型,这个指针类型可以在类型名的后面加上*来指定;

l  在退出变元数目可变的函数前,必须调用va_end,否则,函数将不能正常工作。

结束程序

结束程序由三种方式:

l  return

l  abort  这种表示是非正常结束;

l  exit –通常0表示正常结束,其他值以某种方式代表程序的状态。

提高性能

       有两个工具可以使编译器生成性能更高的代码。其中一个与短函数调用的编译方式相关,另一个涉及指针的使用。

内联声明函数

       C语言的功能结构要求将程序分解为许多函数,函数有时可以非常短,短函数的每次调用可以用实现该函数功能的内联代码替代,提高执行性能。要采用这种技术,可以使用内联指定短函数。

       inline double sumdouble x, double y

{

       return x+y;

}

 

一、inline 关键字用来定义一个类的内联函数,引入它的主要原因是用它替代C中表达式形式的宏定义。

表达式形式的宏定义一例:

#define ExpressionName(Var1,Var2) ((Var1)+(Var2))*((Var1)-(Var2))为什么要取代这种形式呢,且听我道来:

1.        首先谈一下在C中使用这种形式宏定义的原因,C语言是一个效率很高的语言,这种宏定义在形式及使用上像一个函数,但它使用预处理器实现,没有了参数压栈,代码生成等一系列的操作,因此,效率很高,这是它在C中被使用的一个主要原因。

2.        这种宏定义在形式上类似于一个函数,但在使用它时,仅仅只是做预处理器符号表中的简单替换,因此它不能进行参数有效性的检测,也就不能享受C++编译器严格类型检查的好处,另外它的返回值也不能被强制转换为可转换的合适的类型,这样,它的使用就存在着一系列的隐患和局限性。

3.        C++中引入了类及类的访问控制,这样,如果一个操作或者说一个表达式涉及到类的保护成员或私有成员,你就不可能使用这种宏定义来实现(因为无法将this指针放在合适的位置)

4.        inline 推出的目的,也正是为了取代这种表达式形式的宏定义,它消除了它的缺点,同时又很好地继承了它的优点。

为什么inline能很好地取代预定义呢?

对应于上面的1-3点,阐述如下:

1.        inline 定义的类的内联函数,函数的代码被放入符号表中,在使用时直接进行替换,(像宏一样展开),没有了调用的开销,效率也很高。

2.        很明显,类的内联函数也是一个真正的函数,编译器在调用一个内联函数时,会首先检查它的参数的类型,保证调用正确。然后进行一系列的相关检查,就像对待任何一个真正的函数一样。这样就消除了它的隐患和局限性。

3.        inline 可以作为某个类的成员函数,当然就可以在其中使用所在类的保护成员及私有成员。

在何时使用inline函数:

首先,你可以使用inline函数完全取代表达式形式的宏定义。

另外要注意,内联函数一般只会用在函数内容非常简单的时候,这是因为,内联函数的代码会在任何调用它的地方展开,如果函数太复杂,代码膨胀带来的恶果很可能会大于效率的提高带来的益处。内联函数最重要的使用地方是用于类的存取函数。

使用restrict关键字

       为了优化设计指针的代码,编译器必须能肯定指针没有别名的换言之,每个指针引用的数据项都没有在给定范围内以其他方式引用。关键字restrict就可以告诉编译器,合适出现这种情况,并允许应用代码优化功能。

       在大多数情况下,不需要使用关键字restrict,只有代码进行大量计算,进行代码优化才有显著的效果,而这还取决于编译器。

游戏

clip_image002

//Program reversi an otherlo type game

#include <stdio.h>

#include <stdbool.h>

#include <ctype.h>

#include <string.h>



//const int SIZE = 6; //board size, must be even

#define SIZE 6

const char comp_c = '@'; //computer's counter

const char player_c = 'O'; //player's counter



//functional prototypes

void display(char board[][SIZE]);

int valid_moves(char board[][SIZE],bool moves[][SIZE],char player);

void make_move(char board[][SIZE],int row,int col, char player);

void computer_move(char board[][SIZE],bool moves[][SIZE],char player);

int best_move(char board[][SIZE],bool moves[][SIZE],char player);

int get_score(char board[][SIZE],char player);



int main(void)

{

char board[SIZE][SIZE] = { 0 }; //the board

bool moves[SIZE][SIZE] = {false}; //valid moves

int row = 0; //board row index

int col = 0; //board column index

int no_of_games =0;//number of games

int no_of_moves = 0;//count of moves

int invalid_moves = 0;//invalid move count

int comp_score = 0;//computer score

int user_score = 0;//player score

char y = 0;//column letter

int x = 0;//row number

char again = 0;//replay choice input



//player indicator : true for player and false for computer

bool next_player = true;



printf("\nREVERSI\n\n");

printf("You can go first on the first game, then we will take turns.\n");

printf(" You will be while - (%c)\n I will be black - (%c).\n",

player_c,comp_c);

printf("Select a square for your move by typing a digit for the row\n "

"and a letter for the column with no spaces between.\n");

printf("\nGood luck ! Press Enter to start.\n");

scanf("%c",&again);



//the main game loop

do

{//on even games the player starts;

//on odd games the computer starts;

next_player = !next_player;

no_of_moves = 4;//starts with four counters



//blank all the board squares

for(row = 0; row < SIZE; row ++)

for (col = 0 ; col < SIZE; col ++)

board[row][col] = ' ';



//place the initial four counters in the center

int mid = SIZE/2;

board[mid - 1][mid - 1] = board[mid][mid] = player_c;

board[mid - 1][mid] = board[mid][mid - 1] = comp_c;



//the game play loop

do

{

display(board); //display the board

if(next_player = !next_player)

{

//it is the player's turn

//code to get the player's move and execute it

if(valid_moves(board,moves,player_c))

{

//read player moves until a valid move is entered

for(;;)

{

printf("Please enter your move (row column): ");

scanf("%d%c",&x,&y);//read input

y = tolower(y) - 'a';//convert to column index

x --;//convert to row index

if(x >= 0 && y >= 0 && x < SIZE && y < SIZE && moves[x][y])

{

make_move(board,x,y,player_c);

no_of_moves++;//increment move count

break;

}

else

printf("Not a valid move , try again\n");

}

}

else//no valid moves

if(++invalid_moves < 2)

{

printf("\nYou have to pass, press return");

scanf("%c",&again);

}

else

printf("\nNeither of us can go, so the game is oves. \n");

}

else

{

//it is the computer's turn

//code to make the computer's move

if(valid_moves(board,moves,'@'))//check for valid moves

{

invalid_moves = 0;//reset invalid count

computer_move(board,moves,'@');

no_of_moves++;//increment move count

}

else

{

if(++invalid_moves < 2)

printf("\nI have to pass, your go\n");//no valid move

else

printf("\nNeither of us can go, so the game is over.\n");

}

}

}while(no_of_moves < SIZE*SIZE && invalid_moves < 2);



//game is over

display(board); //show final board



//get final scores and display them

comp_score = user_score = 0;

for(row = 0; row < SIZE; row ++)

for(col = 0 ;col < SIZE; col++)

{

comp_score += board[row][col] == comp_c;

user_score += board[row][col] == player_c;

}

printf("The final score is: \n");

printf("Computer %d\nUser %d\n",comp_score,user_score);



printf("Do you want to play again (y/n):");

scanf("%c",&again);//get y or n

}while(tolower(again) == 'y');

printf("\nGoodby\n");

return 0;

}



//Function to display the board in its

//current state with row numbers and column

//letters to identify squares

//parameter is the board array

void display(char board[][SIZE])

{

//display the column labels

char col_label = 'a';//column label

printf("\n "); //start top line

int col;

for(col = 0; col < SIZE; col++)

printf(" %c ",col_label+col);///display the top line

printf("\n");//end the top line



//display the rows...

int row;

for (row = 0; row < SIZE; row ++)

{

//display the top line for the current row

printf(" +");



for(col = 0; col < SIZE; col++)

printf("---+");

printf("\n%2d|",row + 1);



//display the counters in current row

for(col = 0 ; col < SIZE; col ++)

printf(" %c|",board[row][col]);//display counters in row

printf("\n");

}

//finally display the bottom line of the board

printf(" +");//start the bottom line

for(col = 0; col < SIZE; col ++)

printf("---+");

printf("\n");



}



//calculates which squares are valid moves

//for player, Valid moves are recorded in the

//moves array - true indicates a valid move ,

//false indicates an invalide move

//first parameter is the board array

//second parameter is the moves array

//third parameters identifies the palyer

//to make the move

//Return valid move count



int valid_moves(char board[][SIZE],bool moves[][SIZE],char player)

{

int rowdelta = 0 ;//row increment aroud a square

int coldelta = 0;//column increment around a square

int x = 0;//row index when searching

int y = 0;//column index when searching

int no_of_moves = 0;//number of valid moves

int row,col;

//set the oppoonent

char opponent = (player == player_c) ? comp_c : player_c;



//initialize moves array to false

for(row = 0; row < SIZE; row ++)

for(col = 0; col < SIZE;col++)

moves[row][col] = false;





//find squares for valid moves

//a valid mvoe must be on a blank square and must enclose

//at least one opponent between two player squares

for(row = 0;row < SIZE;row++)

for(col = 0; col < SIZE; col++)

{

if(board[row][col] != ' ')//is it a blank sqare?

continue;



//check all the sqares aroud the blank square

//for the opponents counter

for(rowdelta = -1; rowdelta <= 1; rowdelta++)

for(coldelta = -1; coldelta <= 1; coldelta++)

{

//do not check outside the array or the current square

if(row + rowdelta < 0 || row + rowdelta >= SIZE ||

col + coldelta <0 || col + coldelta >= SIZE ||

(rowdelta == 0 && coldelta == 0))

continue;

//now check the square

if(board[row + rowdelta][col + coldelta] == opponent)

{

//if we find the opponent , move in the delta direction

//over opponent counters searching for a player counter

x = row + rowdelta;//move to

y = col + coldelta;//opponet square



//look for a player sqare in the delta directioin

for(;;)

{

x += rowdelta;//go to next square

y += coldelta;//in delta direction



//if we move outside the array, give up

if(x < 0 || x >= SIZE || y < 0 || y >=SIZE)

break;



//if we find a blank squaer , give up

if(board[x][y] == ' ')

break;





//if the square has a player counter

//then we have a valid move

if(board[x][y] == player)

{

moves[row][col] = true;//mark as valid

no_of_moves++;//increase valid moves count

break;//go check another sqares

}

}

}

}

}

return no_of_moves;

}



//make a move , this places the counter on a sqare and reverses

//all the oppnent's counters affected by the move.

//first parameter is the board array

//second and third parameters are the row and column indices.

//fourth paramter identified the player



void make_move(char board[][SIZE],int row,int col, char player)

{

int rowdelta = 0;//row increment

int coldelta = 0;//column increment

int x = 0;//row index for searching

int y = 0;//column index for searching



//identify opponent

char opponent = (player == player_c) ? comp_c : player_c;

board[row][col]=player;//place the palyer counter



//check all the squares aroud this square

//for the opponents counter

for(rowdelta = -1; rowdelta <= 1; rowdelta++)

for(coldelta = -1; coldelta <= 1; coldelta++)

{

//do no check off the board, or the current square

if(row + rowdelta < 0 || row + rowdelta >= SIZE ||

col + coldelta <0 || col + coldelta >= SIZE ||

(rowdelta == 0 && coldelta == 0))

continue;



//now check the square

if(board[row+rowdelta][col+coldelta] == opponent)

{

//if we find the opponet , search in the same direction

//for a player counter

x = row + rowdelta;//move to opponent

y = col + coldelta;//square

}



for(;;)

{

x += rowdelta;//move to the next square

y += coldelta;



//if we are off the board give up

if(x < 0 || x >= SIZE || y < 0 || y >= SIZE)

break;

//if the square is blank give up

if(board[x][y] == ' ')

break;



//if we find the player counter, go backward from here

//changing all the opponents counters to player

if(board[x][y] == player)

{

while(board[x -= rowdelta][y -= coldelta] == opponent)

//opponent

board[x][y] = player;//yes change it ,

break; //we are done

}

}

}

}



//find the best move for the computer, this is the move for

//which the opponent's best possible move score is a minimu

//first parameter is teh board array

//second parameter is the moves array containing valid moves

//third parameter identified the computer

void computer_move(char board[][SIZE],bool moves[][SIZE],char player)

{

int best_row = 0;//best row index

int best_col = 0;//best column index

int new_score = 0;//score for current move

int score = 100;//minimum opponent score

char temp_board[SIZE][SIZE];//local copy of board

bool temp_moves[SIZE][SIZE];//local valid moves array

int row,col;

//identify opponent

char opponent = (player == player_c) ? comp_c : player_c;



//go through all valid moves

for(row = 0; row < SIZE; row ++)

for(col = 0; col < SIZE; col ++)

{

if(!moves[row][col])

continue;



//first make copies of the board array

memcpy(temp_board,board,sizeof(temp_board));



//now make this move on the temporary board

make_move(temp_board,row,col,player);



//find valid moves for the opponent after this move

valid_moves(temp_board,temp_moves,opponent);



//now find the score for the opponent's best move

new_score = best_move(temp_board,temp_moves,opponent);



if(new_score < score)//is it worse

{//yes, so save this move

score = new_score;//record new lowest opponent score

best_row = row;//record best move row

best_col = col;//and column

}

}

make_move(board,best_row,best_col,player);



}



//calculates the score for the current board position for the

//player, player counters score +1, opponent counters score -1

//first parameter is the board array

//second parameter identified the player

//return value is the score

int get_score(char board[][SIZE],char player)

{

int score = 0; //score for current position

int row,col;

//identify opponent

char opponent = (player == player_c) ? comp_c : player_c;



//check all board squares

for(row = 0 ; row < SIZE; row ++)

for(col = 0; col < SIZE; col++)

{

score -= board[row][col] == opponent;//decrement for opponent

score += board[row][col] == player;//increment for player

}

return score;

}



//calculates the score for the best move out of the valid moves

//for player in the current position

//first parameter is the board array

//second parameter is the moves array defining valid moves

//third parameter identifies the player

//the score for the best move is returned

int best_move(char board[][SIZE],bool moves[][SIZE],char player)

{

//identify opponent

char opponent = (player == player_c) ? comp_c : player_c;

int row,col;

char new_board[SIZE][SIZE] = {0};//local copy of board

int score = 0;//best score

int new_score = 0;//score for current move



//check all valid moves to find the best

for(row = 0; row < SIZE; row++)

for(col = 0; col < SIZE; col++)

{

if(!moves[row][col])

continue;//not a valid move? go to the next



//copy the board

memcpy(new_board,board,sizeof(new_board));



//make move on the board copy

make_move(new_board,row,col,player);



//get score for move

new_score = get_score(new_board,player);



if(score < new_score)//is it better,

score = new_score;//yes save it as best score

}

return score;//return best score

}

程序的结构

程序的结构

       将程序分成适度的自包含单元是开发任一程序的基本方式。当工作很多时,最明智的做法就是把它分成许多便于管理的部分,使每一个部分都能很轻松地完成,并确保正确完成整个工作。如果仔细设计各个代码块,就可以在其他程序中重用其中的一些代码块。

 

按值传递

       比如float averagefloat value1float value2);中的value1value2就是按值传递,按值传递的重点是value1value2的副本作为变元传递给函数,而没有传送变量本身。也就是说,函数不能改变存储在value1value2中的值

按指针传递

       如果上面的float averagefloat value1float value2);更改为float averagefloat * pvalue1float * pvalue2);那么对两个value的操作将会影响他们的值,因为虽然我们使用的指针也是原来的指针副本,但是它们指向的值确实原始值,所以对其操作会影响原始值。

 

 

float averageconst *float pvalue1const *float pvalue2);表示函数将传递给参数的变元看做一个常量。

float averagefloat const * pvalue1float const * pvalue2);表示函数将传递给参数的为一个常量指针。

       从上面两个可以看出,const修饰的为后面的全部信息

注意绝对不要反悔函数中本地变量的地址

创建和使用函数时的重点

l  C程序由一个或多个函数组成,其中一个是main函数。该函数永远是执行的起点,操作系统通过一个用户命令调用它;

l  函数时程序中独立的一块代码。函数的名称采用标识符名称的形式,由一系列字母和数字组成,第一个字符必须是字母,当然下划线也是字母;

l  函数定义由函数头和函数体组成。函数头定义了函数的名称、函数返回值的类型以及函数中所有参数的类型和名称。函数体含有函数的可执行语句,定义了这个函数的功能;

l  在函数中声明的所有变量都是函数的本地变量;

l  函数原型是一个以分号终止的声明语句;

l  将指针参数指定为const,就是告诉编译器,这个函数不改变该参数指向的数据;

l  函数变元的类型必须符合函数头中对应的参数;

l  在调用函数中,是将变元值的副本传给函数,而不是传送原始值。这种给函数传递数据的方式称为按值传递机制;

l  如果函数要修改在调用函数中定义的变量,就需要将这个变量的地址作为变元传送;

指针

指针

       指针是用C语言高效编程的一个基本元素。

       在程序中,计算机使用变量名引用这块内存,但是一旦编译执行程序,计算机就使用内存位置的地址来引用它。

       int *pointer = NULL; //NULL是在标准库中定义的一个常量,对于指针它表示0NULL是一个不指向任何内存位置的值。这表示,使用不指向任何对象的指针,不会意外覆盖内存。

       使用指针时,一定要初始化它们。使用未初始化的指针存储数据项是很危险的。

       long value = 9999L;

       const long *pvalue = &value;

上面的const代表的意思是不能通过pvalue来改变值,但是可以对value进行操作。

       int count = 30

       int *const pcount = &count;

上面的count为常量指针,表示指针中存储的地址不能改变,即pcount指向的总是相同的对象。但仍然可以使用pcount来改变其指向的值。

       int item = 25

       const int *const pitem = &item;

对于上面的语句就表示是一个指向常量的常量指针,所以所有的信息都是固定不变的。既不能改变存储在pitem中的地址,也不能使用pitem改变它指向的内容。

 

       对于一维数组int a[5],可以使用*a来获得第一个值;而对于N维数组就需要用N*来获取第一个变量了。

 

       指针是一个非常灵活且强大的编程工具,有非常广泛的应用。大多数C程序都在某种程度上使用了指针。C语言还进一步增强了指针的功能,为在代码中使用指针提供了很强的激励机制,它允许在执行程序时动态分配内存。只有使用指针,才能动态分配内存

 

       对于malloc函数返回的为void *,表示可以指向任意类型的数据,但是在我们使用的时候,我们需要指定具体是什么类型。

 

       callocmalloc函数相比有两个优点。分别为:

l  它把内存分配为给定大小的数组;

l  它初始化了所分配的内存,所有的位都是0

 

使用动态分配的内存的基本规则:

l  避免分配大量的小内存块,分配堆上的内存有一些系统开销,所以分配许多小的内存块比分配几个大内存块的系统开销大;

l  仅在需要时分配内存,只要使用完堆上的内存块,就释放它;

l  总是确保释放已经分配的内存,在编写分配内存的代码时,就要确定在代码的什么地方释放内存;

l  在释放内存之前,确保不会无意中覆盖堆上分配的内存的地址,否则程序就会出现内存泄露,这个在循环分配内存时,要特别小心。

 

使用指针高效的一个原因:比如比较两个数组的大小,我们只需交换两个数组的指针即可,而数据还位于原来的地方,只是指针变了。

计算器改进程序:

#include <stdio.h>         //standard input/output

#include <string.h> //for string functions

#include <ctype.h> //for classifying characters

#include <stdlib.h> //for converting strings to numeric values

#include <math.h> //for power()function



#define BUFFER_LEN 256



int main(void)

{

char input[BUFFER_LEN]; //input expression

char number_string[30]; //stores a number string from input

char op = 0; //stores an operator

unsigned int index = 0; //index of the current character in input

unsigned int to = 0; //to index for copying input to itself

size_t input_length = 0; //length of the string in input

unsigned int number_length = 0; //length of the string in number_string

double result = 0.0; //the result of an operation

double number = 0.0; //stores the value of number_string



printf("\nTo use this calculator , enter any expression with"

" or without spaces");

printf("\nAn expression may include the operators:");

printf("\n + , - , * , / , %%, or ^(raise to a power).");

printf("\nUse = at the beginning of a line to operate on");

printf("\nThe result of the previous calculatioin.");

printf("\nUse quit by itself to stop the calculator.\n\n");



//the main calculator loop

while (strcmp(fgets(input, BUFFER_LEN, stdin), "quit\n") != 0) {

input_length = strlen(input); //get the input string length

input[--input_length] = '\0'; //remove newline at the end



//remove all spaces from the input by copy the string to itself

//including the string terminating character

for (to = 0, index = 0; index <= input_length; index++)

if (*(input + index) != ' ') //if it is not a space

*(input + to++) = *(input + index); //copy the character

input_length = strlen(input); //get the new string length

index = 0; //start at the first character

//code to implement the calculator

if (input[index] == '=')

index++;

else { //no - look for the left operand

//the first operator

//now look for 'op number' combinations

// for(;index < input_length;)

// {

// op = *(input + index++);//get the operator



//check for sign and copy it

number_length = 0; //initialize length

if (input[index] == '+' || input[index] == '-') //is it + or -

*(number_string + number_length++) = *(input + index++); //yes so copy it



//copy all following digits

for (; isdigit(*(input + index)); index++) //is it a digit

*(number_string + number_length++) =

*(input + index);



//copy any fractional part

if (*(input + index) == '.') //is it decimal point

{

//yes so copy the decimal point and the following digits

*(number_string + number_length++) =

*(input + index++);



for (; isdigit(*(input + index)); index++) //for each digit

*(number_string + number_length++) = *(input + index); //copy it

}

*(number_string + number_length) = '\0'; //append string terminator



//if we have a left operand, the length of number_string

//will be > 0. In this case convert to a double so we

//can use it in the calculation

if (number_length > 0)

result = atof(number_string); //store first number as result



}



//now look for 'op number' combinations

for (; index < input_length;) {

op = *(input + index++); //get the operator



//check for sign and copy it

number_length = 0; //initialize length

if (input[index] == '+' || input[index] == '-') //is it + or -

*(number_string + number_length++) = *(input + index++); //yes so copy it



//copy all following digits

for (; isdigit(*(input + index)); index++) //is it a digit

*(number_string + number_length++) =

*(input + index);



//copy any fractional part

if (*(input + index) == '.') //is it decimal point

{

//yes so copy the decimal point and the following digits

*(number_string + number_length++) =

*(input + index++);



for (; isdigit(*(input + index)); index++) //for each digit

*(number_string + number_length++) = *(input + index); //copy it

}

*(number_string + number_length) = '\0'; //append string terminator



//if we have a left operand, the length of number_string

//will be > 0. In this case convert to a double so we

//can use it in the calculation

number = atof(number_string); //store first number as result



//execute operatioin , as 'result op= number'

switch (op) {

case '+':

result += number;

break;

case '-':

result -= number;

break;

case '*':

result *= number;

break;

case '/':

//check second operand for zero

if (number == 0)

printf

("\n\n\aDivision by zero error!\n");

else

result /= number;

break;

case '%':

//check second operand for zero

if ((long) number == 0)

printf

("\n\n\aDivision by zero error!\n");

else

result =

(double) ((long) result %

(long) number);

break;

case '^':

result = pow(result, number);

break;

default:

printf("\n\n\aIllegal operation!\n");

break;

}

}

//code to analyze the operator and right operand

//and produce the result

printf("= %f\n", result);

}

return 0;

}