C Primer+Plus（十七）高级数据表示 编程练习（一）

1、修改程序清单17.2，使其既能以郑旭又能以逆序显示电影列表。一种方法是修改链表定义使其可以双向遍历；另一种用递归

//双向链表

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TSIZE 45
struct film
{
   char title[TSIZE];
   int rating;
   struct film *prev;
   struct film *next;
};

int main(void)
{
   struct film *head=NULL;
   struct film *temp,*current;
   char input[TSIZE];
 
   puts("Enter title:");
   while(gets(input)!=NULL&&input[0]!='')
   {
     current=(struct film*)malloc(sizeof(struct film));
     if(head==NULL)
     {
        head=current;
        current->prev=NULL;
     }
     else
     {
        temp->next=current;
        current->prev=temp;
     }
     current->next=NULL;
     strcpy(current->title,input);
     puts("Enter rating:");
     scanf("%d",&current->rating);
     while(getchar()!='
')  continue;
     puts("Enter next title:");
     temp=current;
    }
    if(head==NULL)
       printf("No list.
");
    else
       printf("here is the list:
");
    current=head;
    while(current!=NULL)
    {
       printf("Movie:%s Rating:%d
",current->title,current->rating);
       current=current->next;
    }
    printf("NIXU list:
");
    current=head;
    while(current->next!=NULL)
    {
       current=current->next;
    }

    while(current->prev!=NULL)
    {
       printf("Movie:%s Rating:%d
",current->title,current->rating);
       current=current->prev;
    }
    printf("Movie:%s Rating:%d
",current->title,current->rating);   
    current=head;
    while(head!=NULL)
    {
       free(current);
       head=head->next;
       current=head;
    }
    printf("BYE!
");
    getch();
    return 0;
}

//递归显示
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TSIZE 45
struct film
{
   char title[TSIZE];
   int rating;
   struct film *next;
};
void showlist(const struct film *fp)
{
   if(fp!=NULL)
   {
      showlist(fp->next);
      printf("Movie:%s Rating:%d
",fp->title,fp->rating);
   }
}
int main(void)
{
   struct film *head=NULL;
   struct film *prev,*current;
   char input[TSIZE];
 
   puts("Enter title:");
   while(gets(input)!=NULL&&input[0]!='')
   {
     current=(struct film*)malloc(sizeof(struct film));
     if(head==NULL)
        head=current;
     else
        prev->next=current;
     current->next=NULL;
     strcpy(current->title,input);
     puts("Enter rating:");
     scanf("%d",&current->rating);
     while(getchar()!='
')  continue;
     puts("Enter next title:");
     prev=current;
    }
    if(head==NULL)
       printf("No list.
");
    else
       printf("here is the list:
");
    current=head;
    while(current!=NULL)
    {
       printf("Movie:%s Rating:%d
",current->title,current->rating);
       current=current->next;
    }
    printf("NIXULIST:
");
    showlist(head);
    current=head;
    while(head!=NULL)
    {
       free(current);
       head=head->next;
       current=head;
    }
    printf("BYE!
");
    getch();
    return 0;
}

3、假设list.h（程序清单17.3）如下定义列表：

typedef struct list
{
   Item entries[100];  //项目数组
   int items;         //项目数量
}List;

重写17.5,并用17.4测试

#include<stdio.h>
#include<stdlib.h>
#include<string.h>


struct film
{
   char title[45];
   int rating;
};
typedef struct film Item;

typedef struct list
{
  Item entries[100];
  int items;
}List;


//数组型数据接口定义
void InitializeList(List *plist)
{
   int i;
   for(i=0;i<100;i++)
   {
     plist->entries[i].title[0]='';
     plist->entries[i].rating=0;
   }
   plist->items=0;
}

int ListIsEmpty(const List *plist)
{
    return plist->items==0;
}
 

int ListIsFull(const List *plist)
{
    return plist->items==100;
}    

int ListItemCount(const List *plist)
{
    return plist->items;
}

int AddItem(Item item,List *plist)
{
    int i=0;
    if(ListIsFull(plist))
       return 0;
    else
    {
       while(plist->entries[i].title[0]!='')
            i++;
       plist->entries[i]=item;
       plist->items++;
       return 1;
     }
}
    
void Traverse(const List *plist,void(*pfun)(Item item))
{
     int i=0;
     while(plist->entries[i].title[0]!='')
     {
        (*pfun)(plist->entries[i]);
        i++;
     }
}

void showmovies(Item item)
{
    printf("Movie:%s Rating:%d
",item.title,item.rating);
}

//接口定义完成

int main(void)
{
   List movies;
   Item temp;

   InitializeList(&movies);
   if(ListIsFull(&movies))
   {  printf("Error!
");
      exit(1);
   }

 
   puts("Enter title:");
   while(gets(temp.title)!=NULL&&temp.title[0]!='')
   {
     puts("Enter your rating:");
     scanf("%d",&temp.rating);
     while(getchar()!='
')  continue;
     if(AddItem(temp,&movies)==0)
     {
        printf("Error!
");
        break;
     }
     if(ListIsFull(&movies))
     {
         puts("The list is now full.");
         break;
     }
     puts("Enter next title:");
   }
   if(ListIsEmpty(&movies))
        printf("NO DATA!
");
   else
   {
     printf("Here is the movies:
");
     Traverse(&movies,showmovies);
   }
   printf("You entered %d movies.
",ListItemCount(&movies));
 
    printf("BYE!
");
    getch();
    return 0;
}


   

 4、重写mall.c，使其用两个队列模拟两个摊位

#include<stdio.h>
#include<stdlib.h>

#define MAXQUEUE 10
#define MIN_PER_HR 60.0

//队列ADT定义描述
typedef struct item
{  long arrive;     //一位顾客加入队列的时间
   int processtime; //其所需要的咨询时间
}Item;  

typedef struct node
{ 
  Item item;
  struct node *next;
}Node;      

typedef struct queue
{
   Node *front;
   Node *rear;
   int items;
}Queue;

/*函数原型                         */
/*操作：初始化队列                 */
/*操作前：pq指向一个队列           */
/*操作后：该队列被初始化为空       */
void InitializeQueue(Queue *pq);

/*操作：判断队列是否为空              */
/*操作前：pq指向一个已初始化的队列    */
/*操作后：若空返回true,否则返回false  */
int QueueIsEmpty(const Queue *pq);


/*操作：判断队列是否满                */
/*操作前：pq指向一个已初始化的队列    */
/*操作后：若满返回true,否则返回false  */
int QueueIsFull(const Queue *pq);


/*操作：确定队列中项目数量            */
/*操作前：pq指向一个已初始化的队列    */
/*操作后：返回项目数量                */
int QueueItemCount(const Queue *pq);


/*操作：在队列尾部添加新项目                               */
/*操作前：pq指向一个已初始化的队列,item是要被添加的项目    */
/*操作后：如果添加成功，返回true,否则返回false             */
int EnQueue(Item item,Queue *pq);

/*操作：从队列首端删除项目                                        */
/*操作前：pq指向一个已初始化的队列                                */
/*操作后：如果队列非空，队列首端项目被复制到*pitem                */
/*        并被从队列中删除，函数返回true;如果这个操作使队列为空   */
/*        则把队列重置为空队列；如果队列开始就为空，返回false
int DeQueue(Item *pitem,Queue *pq);

/*操作：  清空队列                      */
/*操作前：pq指向一个已初始化的队列      */
/*操作后：队列为空                      */
void EmptyTheQueue(Queue *pq);

//队列ADT定义描述---------finished

//队列ADT接口代码

/*操作：初始化队列                 */
/*操作前：pq指向一个队列           */
/*操作后：该队列被初始化为空       */
void InitializeQueue(Queue *pq)
{
  pq->front=NULL;
  pq->rear=NULL;
  pq->items=0;
}

/*操作：判断队列是否为空              */
/*操作前：pq指向一个已初始化的队列    */
/*操作后：若空返回true,否则返回false  */
int QueueIsEmpty(const Queue *pq)
{
  return pq->items==0;
}
  


/*操作：判断队列是否满                */
/*操作前：pq指向一个已初始化的队列    */
/*操作后：若满返回true,否则返回false  */
int QueueIsFull(const Queue *pq)
{
  return pq->items==MAXQUEUE;
}


/*操作：确定队列中项目数量            */
/*操作前：pq指向一个已初始化的队列    */
/*操作后：返回项目数量                */
int QueueItemCount(const Queue *pq)
{
   return pq->items;
}


/*操作：在队列尾部添加新项目                               */
/*操作前：pq指向一个已初始化的队列,item是要被添加的项目    */
/*操作后：如果添加成功，返回true,否则返回false             */
int EnQueue(Item item,Queue *pq)
{  Node *pnew;
   if(QueueIsFull(pq))
       return 0;
   pnew=(Node*)malloc(sizeof(Node));
   if(pnew==NULL)
       return 0;
   pnew->item=item;
   pnew->next=NULL;
   if(QueueIsEmpty(pq))
      pq->front=pnew;
   else
      pq->rear->next=pnew;
   pq->rear=pnew;
   pq->items++;
   return 1;
}


/*操作：从队列首端删除项目                                        */
/*操作前：pq指向一个已初始化的队列                                */
/*操作后：如果队列非空，队列首端项目被复制到*pitem                */
/*        并被从队列中删除，函数返回true;如果这个操作使队列为空   */
/*        则把队列重置为空队列；如果队列开始就为空，返回false     */
int DeQueue(Item *pitem,Queue *pq)
{
  Node *temp;
  if(QueueIsEmpty(pq))
      return 0;
  *pitem=pq->front->item;
  temp=pq->front;
  pq->front=pq->front->next;
  free(temp);
  pq->items--;
  if(pq->items==0)
     pq->rear=NULL;
  return 1;
}
  
  

/*操作：  清空队列                      */
/*操作前：pq指向一个已初始化的队列      */
/*操作后：队列为空                      */
void EmptyTheQueue(Queue *pq)
{
  Item *pitem;
  while  (!QueueIsEmpty(pq))
     DeQueue(pitem,pq);
}


//队列ADT接口代码-------------finish


//x是顾客到来的平均间隔时间（秒）
//如果这1分钟有则1;

int newcustomer(double x)       
{
    if (rand()*x/RAND_MAX<1)  return 1;
    else return 0;
}

//设置顾客参量
//when是顾客到来时间
Item customertime(long when)
{
   Item cust;
   cust.processtime=rand()%3+1;
   cust.arrive=when;
   return cust;
}    

int main(void)
{
  Queue line1,line2;
  Item temp;    //新顾客数据
  int hours;    //模拟小时数
  int perhour;  //每小时平均顾客到来数
  long cycle,cyclelimit;
  long turnaways=0;    //被拒顾客数
  long customers1=0;    //加入队列的顾客数
  long customers2=0;
  long served1=0;        //接受服务的顾客数
  long served2=0; 
  long sum_line=0;     //累计队列长度
  int wait_time1=0;    //从当前到sigmund空闲所需时间
  int wait_time2=0;
  double min_per_cust;     //顾客到来的平均间隔时间
  long line_wait=0;       //队列累计等待时间

 
  InitializeQueue(&line1);
  InitializeQueue(&line2);
  srand(time(0));
  puts("Case Study:Sigmund Lander's Advice Booth");
  puts("Enter the number of simulation hours:");
  scanf("%d",&hours);
  cyclelimit=MIN_PER_HR*hours;
  puts("Enter average number of customers per hour:");
  scanf("%d",&perhour);
  min_per_cust=MIN_PER_HR/perhour;


  for(cycle=0;cycle<cyclelimit;cycle++)
  {
   if(newcustomer(min_per_cust))
   {
     if(QueueIsFull(&line1)&&QueueIsFull(&line2))
        turnaways++;
     else if(QueueItemCount(&line1)<=QueueItemCount(&line2))
     {
    customers1++;
        temp=customertime(cycle);
    EnQueue(temp,&line1);
     }
     else
     {
    customers2++;
        temp=customertime(cycle);
    EnQueue(temp,&line2);
     }
    }
    if(wait_time1<=0&&!QueueIsEmpty(&line1))
    {
      DeQueue(&temp,&line1);
      wait_time1=temp.processtime;
      line_wait+=cycle-temp.arrive;
      served1++;
    }
    if(wait_time2<=0&&!QueueIsEmpty(&line2))
    {
      DeQueue(&temp,&line2);
      wait_time2=temp.processtime;
      line_wait+=cycle-temp.arrive;
      served2++;
    }
    if(wait_time1>0)
        wait_time1--;
    if(wait_time2>0)
        wait_time2--;
    sum_line+=QueueItemCount(&line1)+QueueItemCount(&line2);
   }
   if(customers1>0)
   {
    printf("-------Queue A-------
");
    printf("A Customers accepted:%ld
",customers1);
    printf(" A Customers served:%ld
",served1);
   }
   if(customers2>0)
   {
    printf("-------Queue B-------
");
    printf("B Customers accepted:%ld
",customers2);
    printf(" B Customers served:%ld
",served2);
   }

   else puts("No customers!");
   printf("--------Other info------
");
   printf("turnaways:%ld
",turnaways);
   printf("average queue size:%f
",(double)sum_line/cyclelimit);
   printf("average wait time:%f minutes
",(double)line_wait/(served1+served2));
   EmptyTheQueue(&line1);
   EmptyTheQueue(&line2);
   puts("Bye!");
   getch();
   return 0;
}

5、编写一个程序，让您输入一个字符串。该程序将此字符串中字符逐个压入一个栈，然后弹出这些字符并显示。结果是将字符串逆序显示。

#include<stdio.h>
#include<string.h>
#define MAXNUM 100

typedef char Item;
typedef struct node
{ 
  Item item;
  struct node *next;
}Node;      

typedef struct stack
{
   Node *top;
   Node *bottom;
   int items;
}Stack;

/*函数原型                         */
/*操作：初始化堆栈                 */
void InitializeStack(Stack *ps)
{
  ps->top=NULL;
  ps->bottom=NULL;
  ps->items=0;
}

/*操作：判断堆栈是否为空              */
/*操作前：ps指向一个已初始化的队列    */
/*操作后：若空返回true,否则返回false  */
int StackIsEmpty(const Stack *ps)
{
  return ps->items==0;
}
  


/*操作：判断Stack是否满                */
int StackIsFull(const Stack *ps)
{
  return ps->items==MAXNUM;
}


/*操作：确定堆栈中项目数量            */
int StackItemCount(const Stack *ps)
{
   return ps->items;
}


/*操作：在堆栈顶部添加新项目                               */
/*操作前：ps指向一个已初始化的堆栈,item是要被添加的项目    */
/*操作后：如果添加成功，返回true,否则返回false             */
int PushStack(Item item,Stack *ps)
{  Node *pnew;
   if(StackIsFull(ps))
       return 0;
   pnew=(Node*)malloc(sizeof(Node));
   if(pnew==NULL)
       return 0;
   pnew->item=item;
   if(StackIsEmpty(ps))
   {   ps->top=pnew;
       pnew->next=NULL;
   }
   else
   {
       pnew->next=ps->top;
       ps->top=pnew;
   }
   ps->items++;
   return 1;
}


/*操作：从堆栈顶部删除项目                                        */
/*操作前：ps指向一个已初始化的队列                                */
/*操作后：如果堆栈非空，顶部项目被复制到*pitem                */
/*        并被从堆栈中删除，函数返回true;如果这个操作使队列为空   */
/*        则把堆栈重置为空队列；如果堆栈开始就为空，返回false     */
int DeStack(Item *pitem,Stack *ps)
{
  Node *temp;
  if(StackIsEmpty(ps))
      return 0;
  *pitem=ps->top->item;
  temp=ps->top;
  ps->top=ps->top->next;
  free(temp);
  ps->items--;
  if(ps->items==0)
     ps->bottom=NULL;
  return 1;
}
  
  

/*操作：  清空堆栈                      */
/*操作前：ps指向一个已初始化的堆栈      */
/*操作后：堆栈为空                      */
void EmptyTheStack(Stack *ps)
{
  Item *pitem;
  while  (!StackIsEmpty(ps))
     DeStack(pitem,ps);
}

int main()
{
   char st[100];
   Item *a;
   int i=0;
   Stack *cs;

   printf("input the string:
");
   scanf("%s",st);
   while(getchar()!='
') continue;
   InitializeStack(cs);
   while(st[i]!='')
   {
      if(StackIsFull(cs))
        printf("Stack Full!
");
      else
        PushStack(st[i],cs);
      i++;
   }
  
   while(cs->items!=0)
   {
     DeStack(a,cs);
     putch(*a);
   }
   getch();
   return 0;
}
  

6、写一个接受3个参数的函数。这3个参数为：存有已排序的整数的数组名，数组元素个数和要查找的整数。如果该整数在数组中，函数返回1；否则返回0.用折半搜索法实现。

#include<stdio.h>

void find(int a[100],int num,int x)
{
   int i=num/2;
   int lowp=0;
   int highp=num;    //设置范围标记

   while(x!=a[i])
   {
    if(x<a[i])
           highp=i;
        else
           lowp=i;
        if(i==(lowp+highp)/2) break;   //如果折半后还为原数，则结束，推出循环
        else      i=(lowp+highp)/2;
   }  
   if(x==a[i])
        printf("the number x exist in the array.serial muber is:%d.
",i);
   else
        printf("the number x is not exist.");

}

int main()
{
   int arrm[100]={1,2,5,7,9,12,17,18,21,22,39,56,78,89,108,112,158,336,511};
   int x=112;

   find(arrm,19,x);
   getch();
   return 0;
}