ex12.cpp

C／C＋＋程序设计教程

			/////	第12章   结  构 与 联 合

	
 ////   [例12.1]结构变量的内存与边界对齐效应
    #include<stdio.h>   
	void main (void)
    {   struct S {     char   c;   	  int k;     }  s ;
        struct A {     char  c[9];    double d;  }  a ;		
		struct B {     char  *c[9];    double* d; }  b;
		struct C {     char  c[8];    double  d; }  c ;
		printf("%d,%d, %d,%d \t",sizeof(S),sizeof(a) ,sizeof(B),sizeof(c));	
	}   //输出：8 ,24,40,16
////	[例12.2] 字符指针成员和字符数组成员
	# include<stdio.h>  
    typedef struct data_s	{     int  n;	 char *s;		} SData;
    typedef struct data_a	{     int  n;	 char a[12];	} AData;
	void main(void) 
	 {  SData d[]={1,"For",2,"Before",3,"And",4,"Anyone"};
        AData c[]={5,"for",6,"before",7,"and",8,"anyone"};
        const int n=sizeof(d)/sizeof(d[0]);
		d[1].s=c[3].a;// d[1].s是char *型的左值，c[3].a是char *型的右值
	    d[1].s[1]='N';//当SData的指针成员s指向左值内存区时可以对其更新
    	//d[0].s[1]='O';// 当SData的指针成员s指向只读内存区时不应对其更新
		SData*p=d;//定义结构指针p，以优化输出的寻址计算，p初值等于d
		int k ;for(k=0;k<n;k++,p++)      printf("{%p,%s} ",d[k].s,p->s);   
		printf("\n");
        for( k=0;k<n;k++)   printf("{%p,%s} ",(*(c+k)).a,(c+k)->a);		printf("\n"); 
		AData *q=c; //定义结构指针q，优化输出的寻址计算，q初值等于c
	  	for(p=d,k=0;k<n;k++,p++,q++)  printf("[%d,%d] ",p->n,q->n);
     }//输出结果:
//////////[例12.3]求数组和的函数double sum(double* ,int )求结构成员数组的和
	# include<stdio.h>  
   	typedef struct SType {    int  v;   double  a[6];   }   S,  *  PS;	
    double sum(double* q,int n) 
	{ 
		double s=0;
       for(double*p=q;p<q+n;p++) s+=*p;  return s;  
	}
    void main()
    {   S a[2]={4,{1,2,3,4},5,{1,2,3,4,5}};    //结构成员数组的截断赋值
	    for(PS  s=a;s<a+2;s++)    printf("%2.0f ",sum(s->a,s->v)); //输出结果:10 15
    }

////[例12.4]数值形参a,引用形参r和指针形参p对实参结构变量的影响
	# include<stdio.h>  
   	typedef struct Sa {    int x;   }   A;	
    void f(A a,A& r,A* p){     a.x += 1;   r.x += 2;    p->x  += 3;   }
	void main()
    {   A a[3]={1,2,3};    //结构数组的初始赋值
        f(a[0],a[1],a+2);
	    printf("%d,%d,%d",a[0].x, a[1].x, a[2].x); //输出结果:1,4,6
    }
//[例12.5] 数值形参v和引用形参u求点积的函数double DotProduct( PT& u, PT  v)
    # include <stdio.h>    
	# include <stdio.h>    
	typedef  struct point_t { double x,y,z;} PT;
	double DotProduct( PT& u, PT  v)		{ return  u.x*v.x+u.y*v.y+u.z*v.z;}
	double Dot(double p[3], double *q){return  p[0]*q[0]+p[1]*q[1]+p[2]*q[2]; }
	void main(void)
	{     PT x={1,1,0},y={0,2,1},z={1,0,3};
		 PT  a;	          a.y=Dot(&y.x,&z.x);
        a.x=DotProduct(x,y);		a.z=DotProduct(z,x);
		printf("a={%1.0f,%1.0f,%1.0f}\t", a.x,a.y,a.z); 
	}   //输出：a={2,3,1}
 ///   [例12.6] 只读指针形参double DotProduct(const point_t *, const point_t *)求点积
    # include <stdio.h>    
	typedef  struct {   double   v[3];    }   point_t;
	double DotProduct(const point_t *p, const point_t *q)
		{ 	return  p->v[0]*q->v[0]+p->v[1]*q->v[1]+p->v[2]*q->v[2]; }
	double Dot(double *p, double q[3]){return p[0]*q[0]+p[1]*q[1]+p[2]*q[2]; }
	void main(void)
	{   point_t  x={1,1,0},  y={0,2,1},  z={1,0,3};
	    point_t  a={DotProduct(&x,&y),DotProduct(&y,&z),Dot(z.v,x.v)};		
   		printf("a={%1.0f,%1.0f,%1.0f}\n", a.v[0],a.v[1],a.v[2]); 	
	 }  //输出：a={2,3,1}
/////////[例12.7]对结构不同成员的排序
	# include<stdio.h>  
    #include<string.h>  
     typedef struct data_tag	{  int  n;   char *s;} SData;
	void SelectSort(SData* a, int n)        //选择排序的优点在于变量的交换次数少
	{	 for(int i=0;i<n-1;i++)  
		 { int min=i;                 //设置最小元素下标初始值为i
  		  for(int j=i+1;j<n;j++)        //在无序区间中寻找最小值对应的下标min         
    		  if(strcmp(a[j].s,a[min].s)<0)	min=j;
		  if(min!=i) {  SData t=a[i];a[i]=a[min];a[min]=t; }
		 }     //仅在min!=i即最小值在无序区才交换结构变量
	}
    void BubbleSort(SData a[],int n)         //对结构数组排序
	{ 	for(int i=1;i<n;i++)                  //外层循环i共循环n-1回
	   		for(int j=0;j<n-i;j++)              //从0~n-i进行内层循环
          		if (a[j].n>a[j+1].n)          
				{ SData t=a[j];a[j]=a[j+1];a[j+1]=t;}//交换结构变量
	}        //对结构数组排序算法的效率不及下面对结构指针数组的排序的效率高
	void BubbleSort(SData *a[],int n) //对结构指针数组的排序
	{ 	for(int i=1;i<n;i++)
	   		for(int j=0;j<n-i;j++)              
          	  if (a[j]->n > a[j+1]->n)
				{SData *t=a[j];a[j]=a[j+1];a[j+1]=t;}    //交换指针数组元素的值	
	}                                 //交换指针的值相当于交换int型变量的值
     void main(void) 
	 {  char *  const  ca[]={"For","Before","FOR","And","anyone"};	 
       SData d[]={6,ca[0],4,ca[1],7,ca[2],5,ca[3],8,ca[4]};//定义结构数组d[5]
       const int n=sizeof(d)/sizeof(d[0]); int k;
	   for(k=0;k<n;k++)  printf("{%d,%s} ",d[k].n,d[k].s);//显示原始数据
	   printf("\n1");BubbleSort(d,n);      //1调用结构数组的冒泡排序算法
       SData* p=d; //定义一级结构指针p，以优化输出的寻址计算，p初值等于d
 	   for(k=0; k<n;k++,p++)  printf("{%d,%s} ",p->n,p->s); //显示排序后的数据
       printf("\n2");SelectSort(d,n);      //2调用选择法对字符串排序
	   for( k=0;k<n;k++)  printf("{%d,%s} ",d[k].n,(d+k)->s); //显示排序后的数据
       SData* s[n];  //定义结构指针数组s[5]，s[i]分别指向数组d的相应元素d[i]。
	   for( k=0;k<n;k++) s[k]=d+k;//相当于s[0]=&d[0], s[1]=&d[1], ..., s[n-1]=&d[n-1],
	   printf("\n3");BubbleSort(s,n);     //3调用结构指针数组的冒泡排序算法
       SData** pp=s;p=*pp; //定义二级结构指针pp，以优化输出结构成员的寻址计算
	   for( k=0;k<n;k++,pp++,p=*pp)   printf("{%d,%s} ",p->n,s[k]->s);
     }
///	[例12.8] 指针形参输出成员数据
   	#include<stdio.h> 
	typedef  struct a_t  { int   x ;     }    A;
	typedef  struct b_t  { 	int   m;    A   a; }   B;
    typedef  struct c_t  { 	int   n;    B   b; }   C; 
	void show(const C* pc)
	{  printf("c={%d,%d,%d}\t",pc->n,pc->b.m,pc->b.a.x);}
	void main (void)
    {	A a={1}; B b={3,4};  	C c={6,7,8};      
		C *pc=&c;	
        pc->b = b;            show(pc); 
		pc->b.a=a;            show(&c);       
	}   //输出：c={6,3,4}    c={6,3,1}
///	[例12.9]结构数组和链表
    # include <stdio.h>    
	# include <memory.h> 
	typedef  struct  SList_tag
	{    float  data;
		 int   elem;
		 struct  SList_tag* pNext;
	} SList;
 	void ShowL(SList* p)                         //显示单链表结构数据的函数
	 {	 while(p!=0)                         //要求链表中存在结束的0指针值
		 { printf("p=%p{%3.1f,%d}, ",p,p->data,p->elem);//显示当前结点的物理数据
             p=p->pNext;                         //指向下一个结点
		 }
	 }
	void ShowP(SList p[],int n)
	 {	for(int k=0;k<n;p++,k++)
		   printf("c[%d]{%3.1f,%d}, ",k,p->data,p->elem);
	 }
	void ShowA(SList *p,int n)
	  { for (int k=0;k<n;k++) printf("d[%d]{%3.1f,%d}, ",k,p[k].data,p[k].elem);	 }
	static SList d[]={5.0,1,NULL,  4.0,2,NULL,	 6.0,3,NULL};	  //静态结构数组定义
	void main(void)
 	{	 const int n=sizeof(d)/sizeof(SList);      //n=3
		 SList c[n];                          //局部结构数组定义
		 memcpy(c,d,sizeof(d));                //将结构数组d的元素赋值给c的元素
		 printf("show array d:");	 ShowA(d,n);    //显示d[0],d[1],d[2]
		 printf("\nshow array c:"); ShowP(c,n);    //显示c[0],c[1],c[2]
		int k; for( k=0;k<n-1;k++)		           //对结构数组元素d[k]的pNext赋值
			 d[k].pNext=&d[k+1];	           //d[0].pNext=&d[1]; d[1].pNext=&d[2];
		 printf("\nshow List  from d[0]:\n");
		 ShowL(d);                           //显示d单链中的元素
		 for( k=n-1;k>0;k--)		                //对结构数组元素c[k]的pNext赋值
			 c[k].pNext=&c[k-1];	            //c[2].pNext=&c[1]; c[1].pNext=&c[0];	 
		 printf("\nshow List from &c[n-1]:\n");
		 ShowL(&c[n-1]);                      //显示c单链中的元素
	}
////////////////[例12.10]先建立单链表然后赋值的算法
	# include <stdio.h>  	
    typedef  struct  SList_tag
	{	 float  data; int    elem;
		 struct  SList_tag* pNext;
	} SList;
	void Show(SList* p){ for(;p;p=p->pNext) printf("{%1.0f,%d},",p->data,p->elem);}
	SList* Create(int n)                     //建立拥有n个结点的单链表
	{  SList*    pThis=new SList();         //申请新的结点，pThis指向这个结点
	   SList*    pHead=pThis;             //建立表头
	   SList*    pPrev=pThis;             // 定义pPrev保留当前的位置
	   for(int i=1;i<n;i++)                 //循环建立中间的单链表
	   { pThis=new SList();               //申请新的结点，pThis指向这个结点
	     pPrev->pNext= pThis;            //先前结点的pNext指向这个新的结点
		 pPrev=pThis;                    // pPrev保留新的结点位置，以便下次循环
	   }  
	   pThis->pNext=0;                   //尾结点的pNex等于0
	   return pHead;                      //返回链结妥当的单链表的头指针
	}
	inline void SetData(SList& d,const SList& s)    //仅仅设置结点的数据项
		{ d.data=s.data; d.elem=s.elem;}
	SList* ListCpy(SList s[],int n)            //将结构数组逆序拷贝给单链表
	{  SList* pHead=Create(n);	            //建立单链表但数据项尚未赋值
	   SList* p=pHead;
	   int i=0;                            //s的初始值经由虚实结合得到
	   for(s+=n-1;i<n;i++)                  //s+=n-1表示向后偏移入口地址n-1个元素
	   {  SetData(*p,*s);                   //仅仅对单链表的数据项赋值操作
		  p=p->pNext;                     //向下遍历链表
		  s--;	                         //向前遍历数组
	   }        //重要概念:SetData(*p,*s)不能改为*p=*s这破坏单链表的连接关系
	   return pHead;                        //返回数据项已经赋值的单链表
	}	
   void main(void)
 	{ 	static SList s[]={{5.0,1,0},{4.0,2,0},{6.0,3,0},{7.0,4,0},{8.0,5,0},{9.0,6,0}};
		SList* pHead=ListCpy(s,6);
		Show(pHead);   // 输出：{9,6},{8,5},{7,4},{6,3},{4,2},  {5,1},          
	}		
////	[例12.11] 插入结点到已知链表中
    # include <stdio.h>    
	typedef  struct  SList_tag
	{ 	  int    elem; char  data;
		 struct  SList_tag* pNext;
	} SList;
	SList* Insert(SList*pHead,SList*pAdd)
    {  const int  key=pAdd->elem;            //引入局部不变量使代码略微清晰
      if(pHead==NULL)                      //头指针为空时的处理
		{ pAdd->pNext = NULL;              //插入点既是表头又是表尾        
          return pAdd;                      //返回新的表头即pAdd
        }
	  if(key <= pHead->elem)  //插入点在原头结点之前, [pAdd]<= [pHead]<[...]<[Tail]
		{ pAdd->pNext=pHead;                //插入点变为新的表头
          return pAdd;                       //返回新的表头即pAdd	
        }
      SList*pFind=pHead;        //pFind是一个探寻插入位置的指针，首先指向头结点
      SList*pPrev= pFind;        // pPrev记住插入位置的当前结点，此时指向头结点
		while(pFind->elem<key && pFind->pNext!=0)   //循环查找插入位置
		{  /*要找的结点元素小于关键值同时后面尚有非0结点，进入循环*/
			 pPrev=pFind;                // pPrev保留搜寻的当前位置
             pFind=pFind->pNext;        // pFind指针后移，即指向下一个结点
		}                         //循环结束则找到插入位置，分两种状况
         if(pFind->elem>=key)       //跳出while循环,此时pFind ->elem>=key
		   {   pPrev->pNext=pAdd;  //包含 pFind->pNext!=0或==0