结构化数据

结构化数据

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

      

       有时,我们分配了很多的内存,而实际上我们是不需要那么多内存的,比如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;

}