数据结构实训报告

 

 

 

 

 

 

 

 

 

 

 

 

 

班 级：计算机应用

姓 名： 

学 号：             

计算机系数据结构实训报告
学号：        姓名：   
实验日期：班级： 计算机应用技术  课程名称： 计算机系数据结构实训批改教师：    主持教师：

第一题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
程序分析：兔子的规律为数列1,1,2,3,5,8,13,21....
#include<stdio.h>
void main()
{
long f1,f2;
int i,n,m;
f1=f2=1;
printf("输入月数:\n");
scanf("%d",&n);
for(i=3;i<=n;i++)
{
    m=f2;
    f2+=f1;
    f1=m;
}
    printf("%d\n",f2);
}
执行结果：

第二题目：一个5位数，判断它是不是回文数。即12321是回文数，个位与万位相同，十位与千位相同。
#include "stdio.h"
#include "conio.h"
main( )
{
  long ge,shi,qian,wan,x;
  scanf("%ld",&x);
  wan=x/10000;
  qian=x%10000/1000;
  shi=x%100/10;
  ge=x%10;
  if(ge==wan&&shi==qian)
    printf("this number is a 回文\n");
  else
    printf("this number is not a 回文\n");
  getch();
}
执行结果：

第三题目：两个线性表的合并，有线性表LA和线性表LB，合并为LC
#include "stdio.h"
#define maxsize 100
typedef int elemtype;
typedef struct
{
   elemtype num[maxsize];
   int length;
}List;
List LC(List LA,List LB)
{
 int j,x;
 List LC;
 LC.length=LA.length+LB.length;
 for(j=0;j<LA.length;j++)
 {
  LC.num[j]=LA.num[j];
        }
        for(j=0;j<LB.length;j++)
 {
  LC.num[j+LA.length]=LB.num[j];
        }
 return(LC);
}
List create(int n)     
{
  List L;elemtype e;
  int i;
  printf("input element(初始数值):\n");
  for(i=0;i<n;i++)
   {
 scanf("%d",&e);
    L.num[i]=e;
   }
  L.length=n;
  return L;
 }
void ListTr(List L) 
{int i;
  if(L.length<=0)
   printf("顺序表为空\n");
  else
   {
   printf("当前顺序表中的元素为:\n");
    for(i=1;i<=L.length;i++)
 printf("%d\n",L.num[i-1]);
   }
}
void main()
 {
  int n;
  List LA,LB;
  printf("input the LA number（顺序表的长度）:");
  scanf("%d",&n);
  LA=create(n);
  printf("input the LB number（顺序表的长度）:");
  scanf("%d",&n);
  LB=create(n);
  ListTr(LC(LA,LB));
 }
执行结果：
 
第四题目：新建一个单链表，要求实现单链表的就地逆置。
#include<stdio.h>
#include <stdlib.h>
typedef struct QLink
{
         int data;
         struct QLink *next;
}QLink;

main()
{
      
       QLink *head,*p,*q;
      int length,i;
      printf("此程序是实现链表置逆的功能.\n");
      printf("请输入链表的长度:");
      scanf("%d",&length);
      while(length<=0)
      {
          printf("输入错误，长度必须为自然数，请重新输入.\n");
          printf("请输入链表的长度:");
          scanf("%d",&length);
      }
      printf("现在要输入各结点的值.\n");
      for(i=1;i<=length;i++)
      {
            p=(QLink *)malloc(sizeof(QLink));
            scanf("%d",&p->data);
            p->next=NULL;
            if(i==1) head=p;
            else
            {
                 q=head;
                 while(q->next!=NULL) q=q->next;
                 q->next=p;
            }
      }
      printf("链表已建立，现在要将它输出.\n");
      p=head;
      for(i=1;i<=length;i++)
      {
            printf("%d  ",p->data);
            p=p->next;
      }
      printf("\n");
      printf("现在要将其置逆.\n");
      printf("置逆成功.现在要将新的链表输出.\n");
      p=head;
      while(head->next!=NULL)
      {
           q=p;
           p=head->next;
           head->next=p->next;
           p->next=q;
      }
      head=p;
      p=head;
      for(i=1;i<=length;i++)
      {
            printf("%d  ",p->data);
            p=p->next;
      }
      system("pause");
}
执行结果：

   第五题：
键盘输入循环缓冲区算法。要求采用循环队列来实现。
说明：在操作系统中，循环队列经常用于实时应用程序。分时处理方法：用户键入的内容不能在屏幕上立刻显示出来，直到当前正在工作的那个进程结束为止。但在这个进程执行时，系统是在不断地检查键盘状态，如果检测到用户键入了一个新的字符，就立刻把它存到系统缓冲区中，然后继续运行原来的进程。
#include <conio.h>
#include <stdio.h>
int main( void )
{
      while( !_kbhit() )
      _cputs( "Hit me!! " );
     printf( "\nKey struck was '%c'\n", _getch() );
}
程序代码：
#define  TRUE 1
#define  FALSE 0
#define  QueueElementType char
#define MAXSIZE 50 
typedef struct
{
 QueueElementType  element[MAXSIZE]; 
 int front;   
int rear; }
SeqQueue;

void InitQueue(SeqQueue *Q)
{ 
 
 Q->front=Q->rear=0;
}
int EnterQueue(SeqQueue *Q, QueueElementType x)
{ 
 if((Q->rear+1)%MAXSIZE==Q->front)    return(FALSE);
 Q->element[Q->rear]=x;
 Q->rear=(Q->rear+1)%MAXSIZE;  /
 return(TRUE);  }

int DeleteQueue(SeqQueue *Q, QueueElementType *x)
{
 if(Q->front==Q->rear)
  return(FALSE);
 *x=Q->element[Q->front];
 Q->front=(Q->front+1)%MAXSIZE; 
 return(TRUE); 
}
int GetHead(SeqQueue *Q, QueueElementType *x)
{
 
 if(Q->front==Q->rear)
  return(FALSE);
 *x=Q->element[Q->front];
 return(TRUE); 
}
int IsEmpty(SeqQueue *Q)
{
 if(Q->front==Q->rear)
  return(TRUE);
 else
  return(FALSE); 
}
#include "stdio.h"
#include "conio.h"
void main()
{
 char ch1,ch2;
 SeqQueue  Q;
 int f;
 InitQueue (&Q);
 while(TRUE)
 {
  while(TRUE)
  {
   printf("A");

   if(kbhit())
   {
    ch1=getch();
    if(ch1==';'||ch1=='.')
     break;
    f= EnterQueue(&Q,ch1);
    if(f==FALSE)
    {
     printf("full");
     break;
    }
   }
  }
  while (!IsEmpty(&Q))
  {
   DeleteQueue(&Q,&ch2);
   putchar(ch2);
  }
  getch();
  if(ch1=='.') break;
 }
}
执行结果：

第六题：
数制转换：十进制数转化为二进制数。要求采用堆栈来实现。
#include <malloc.h>
#include<stdio.h>
#define MAXSIZE 32
#define OVERFLOW -1
#define ERROR -2
#define DATATYPE int
typedef enum{FALSE, TRUE} BOOL;
typedef struct
{
      DATATYPE * data;
      int top;
}STACK;
void initStack(STACK * ps)
{
     ps->data = (DATATYPE *)malloc(MAXSIZE*sizeof(DATATYPE));
     ps->top =-1;
}
BOOL empty(STACK * ps)
{
     if (ps->top == -1)
     {
          printf("\nstack empty.\007");
          return TRUE;
     }
     return FALSE;
}
BOOL full(STACK * ps)
{
     if (ps->top == MAXSIZE -1)
     {
          printf("stack full.\007\n");
          return TRUE;
     }
     return FALSE;
}
void push(STACK * ps, DATATYPE element)
{
     if (!full(ps))
     {
         ps->data[++ps->top] = element;
     }
}
DATATYPE pop(STACK *ps)
{
     if (empty(ps))
     {
          return OVERFLOW;
     }
     return ps->data[ps->top--];
}
DATATYPE getTop(STACK * ps)
{
     if (!empty(ps))
        return ps->data[ps->top];
     return ERROR;
}
void clearStack(STACK * ps)
{
     ps->top = -1;
}
void destroy(STACK * ps)
{
     free(ps);
}
#include <stdio.h>
#include <stdlib.h>
 int main()
{
     STACK stack;
     int num;
     int temp;
 initStack(&stack);
printf("please input a number:");
     scanf("%d", &num);
while(num)
     {
          push(&stack, num%2);
          num = num/2;
     }
     while(!empty(&stack))
     {
           printf("%d", pop(&stack));
     }
     return 0;
}
程序结果：

第七题：
括号匹配算法。要求采用堆栈来实现。
说明：表达式中包含三种括号：圆括号、方括号和花括号，它们可互相嵌套，如( [ { } ] ( [ ] ) )或({ ( [ ] [ ( ) ])})等均为正确的格式，而{ [ ] }) }或( [ ] }均为不正确的格式。在检查算法中可设置一个栈，每读入一个括号，若是左括号，则直接入栈，等待相匹配的同类右括号；若读入是右括号，且与当前栈顶的左括号同类型，则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况。另外，如果输入序列已读尽，而栈中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的左括号，均属不合法的情况。当输入序列和栈同时为空时，说明所有括号完全匹配。
#include <stdio.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define maxsize 100
#define STACK_INC 10
typedef char Elem;
typedef struct{
  Elem *base;
  Elem *top;
  int size;
}SqStack;
typedef int Status;
Status CreatStack(SqStack &S)
{
  S.base=(Elem *)malloc(maxsize*sizeof(Elem));
  S.top=S.base;
  S.size=maxsize;
  return OK;
}
Status StackEmpty(SqStack S){
  if(S.top!=S.base) return ERROR;
  return OK;
}
Status Push(SqStack &S,Elem e){
  if(S.top-S.base>=S.size)
{
    S.base=(Elem *)realloc(S.base,(S.size+STACK_INC)*sizeof(Elem));
    S.top=S.base+S.size;
    S.size+=STACK_INC;
  }
  *S.top=e;
  S.top+=1;
  return OK;
}
Status Pop(SqStack &S,Elem &e){
  if(S.top==S.base) return ERROR;
  S.top-=1;
  e=*S.top;
  return OK;
}
Status Bracket(SqStack &S,char *str){
  int i=0,flag1=0,flag2;
  Elem e;
  while(str[i]!='\0'){
    switch(str[i]){
      case '(':Push(S,'(');break;
      case '[':Push(S,'[');break;
      case '{':Push(S,'{');break;
      case ')':{Pop(S,e);
                if(e!='(') flag1=1; break;}
      case ']':{Pop(S,e);
                if(e!='[') flag1=1;break;} '
      case '}':{Pop(S,e);
          if(e!='{') flag1=1;break;}
      default: break;
    }
    if(flag1) break;
    i++;
  }
  flag2=StackEmpty(S);
  if(!flag1 && flag2) printf("括号匹配!\n");
  else printf("括号不匹配!\n");
  return OK;
}
void main()
{
  char temp,flag='y';
  while(flag=='y'){
    char str[255];
    SqStack S;
    printf("请输入字符串:");
    scanf("%s",str);
    scanf("%c",&temp);
    CreatStack(S);
    Bracket(S,str);
    printf("你想再试一次吗(按y继续): ");
    scanf("%c",&flag);
    printf("\n");
  }
  printf("程序结束.\n");
}
执行结果：

个人体会：：
     我个人认为数据结构蛮复杂，编程时需要有太多的地方去注意，需要注意的细节很多，而且思路必须清晰，否则很容易出现错误。
   通过编程可以看出：运用的队列、堆栈运算只能限定在特定的位置进行，而储存的数据类型是特定的数据类型，编程时要注意队列与堆栈的区别，考虑到它们元素的进出有很大的不同；另外，编程时要考虑最后的输出结果是否与要求一致，这就需要注意入队、入栈时的顺序问题。
编程时有很多错误，要看看头文件是否完整，以及符号是否是在英文输入状态下键入，然后具体问题具体对待。