基于ACM平台的编程训练（数据结构）

（1）编写一个将数组元素逆序打印的递归函数。

（2）编写main函数，输入N个整数，将其存入到一个数组中，并调用（1）中的函数，将元素逆序输出。

Example:

从键盘读入：5，7，1，4，6

输出为：6，4，1，7，5

#include

#include

void InversePrint(int a[], int n)

{

/***补全函数***/

}

int main()

{

    int i;

    int a[5];

    for(i=0;i<5;i++){

       scanf("%d", &a[i]);

    }

    InversePrint(a,5);

}

/*

用带头结点的单链表存储一帧数据，计算该帧数据的累加值作为校验码，并将其附加在数据帧尾部

**************************************************

Please input the length of frame:

5

Please input the element of frame one by one:

9 3 8 4 1

The frame is: 1 4 8 3 9

The length of the frame is: 5

The checksum added is: 25

The length of the frame with added checksum is: 6

The frame with added checksum is: 1 4 8 3 9 25

**************************************************

Please input the length of frame:

0

The frame is:

The length of the frame is: 0

*/

#include "stdio.h"   

#include "stdlib.h"  

#define OK 1

#define ERROR 0

#define MAXSIZE 20

typedef int Status;

typedef int ElemType;

typedef struct Node

{

    ElemType data;

    struct Node *next;

}Node;

typedef struct Node *LinkList;

//==========================

//打印单链表

//==========================

void ListTraverse(LinkList L)

{

    LinkList p=L->next;

    while(p)

    {

        printf("%d ", p->data);

        p=p->next;

    }

    printf("\n");

}

//=======================================

//初始化单链表

//=======================================

Status InitList(LinkList *L)

{

/***补全函数***/

}

int ListLength(LinkList L)

{

    int i=0;

    LinkList p=L->next;

    while(p)                       

    {

        i++;

        p=p->next;

    }

    return i;

}

Status GetElem(LinkList L, int i, ElemType *e)

{

/***补全函数***/

}

Status ListInsert(LinkList *L, int i, ElemType e)

{

    int j;

    LinkList p,s;

    p = *L;  

    j = 1;

    while (p && j < i)

    {

       p = p->next;

       j=j+1;

    }

    if (!p || j > i)

       return ERROR;

    s = (LinkList)malloc(sizeof(Node));

    if(!(s))

        return ERROR;

    s->data = e; 

    s->next = p->next;

    p->next = s;

    return OK;

}

//=========================================================

//求单链表所有元素的累加和，并将该累加和作为一个新的结点插在单链表的尾部

//=========================================================

Status AddSumForChecking(LinkList *L)

{

/***补全函数***/

}

int main()

{       

    LinkList L;

    ElemType e;

    Status i;

    int j,k,l;

    i=InitList(&L);

    if(i==ERROR)

    {

        return 0;

    }

    printf("Please input the length of frame:\n");

    scanf("%d", &k);

    if (k > 0)

        printf("Please input the element of frame one by one:\n");

    for(j=1;j<=k;j++)

    {

        scanf("%d", &l);

        i=ListInsert(&L,1,l);

    }

    printf("The frame is: ");

    ListTraverse(L);

    printf("The length of the frame is: %d \n",ListLength(L));

    if(OK==AddSumForChecking(&L))

    {

       GetElem(L, ListLength(L), &e);

       printf("The checksum added is: %d\n", e);

        printf("The length of the frame added checksum is: %d \n",ListLength(L));

        printf("The frame added checksum is: ");

        ListTraverse(L);

    }

    return 0;

}

/*

将两个顺序表 Sqlist1 和 SqList2 交叉合并，得到顺序表 SqList3

*********************************

Please input the length of SqList1:

5

Please input the element of SqList1 one by one:

9 1 5 8 3

The SqList1 is: 3 8 5 1 9

The length of SqList1 is: 5

Please input the length of SqList2:

2

Please input the element of SqList2 one by one:

55

66

The SqList2 is: 66 55

The length of SqList1 is: 2

The SqList3 of interleaving L1&2 is: 3 66 8 55 5 1 9

The length of SqList1 is: 7

*********************************

Please input the length of SqList1:

3

Please input the element of SqList1 one by one:

11

33

66

The SqList1 is: 66 33 11

The length of SqList1 is: 3

Please input the length of SqList2:

6

Please input the element of SqList2 one by one:

9 1 5 8 3 7 4

The SqList2 is: 7 3 8 5 1 9

The length of SqList1 is: 6

The SqList3 of interleaving L1&2 is: 66 7 33 3 11 8 5 1 9

The length of SqList1 is: 9

*/

#include "stdio.h"   

#include "stdlib.h"  

#define OK 1

#define ERROR 0

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;

typedef int ElemType;

typedef struct

{

    ElemType data[MAXSIZE];

    int length;

}SqList;

void ListTraverse(SqList L)

{

    int i;

    for(i=0;i

        printf("%d ",L.data[i]);

    printf("\n");

}

int ListLength(SqList L)

{

    return L.length;

}

Status GetElem(SqList L,int i,ElemType *e)

{

/***补全函数***/

}

Status ListInsert(SqList *L,int i,ElemType e)

{

    int k;

    if (L->length>=MAXSIZE || i<0 || i>L->length)

       return ERROR;

    for(k=L->length-1;k>=i;k--)

           L->data[k+1]=L->data[k];

    L->data[i]=e;

    L->length++;

    return OK;

}

void InterLeaving(SqList *L3, SqList L1, SqList L2)

{

 /***补全函数***/

}

int main()

{

    SqList L1, L2, L3;

    Status i;

    int j,k,l;

    printf("Please input the length of SqList1:\n");

    scanf("%d", &k);

    L1.length = 0;

    if (k > 0)

        printf("Please input the element of SqList1 one by one:\n");

    for(j=1;j<=k;j++)

    {

        scanf("%d", &l);

        i=ListInsert(&L1,0,l);

    }

    printf("The SqList1 is: ");

    ListTraverse(L1);

    printf("The length of SqList1 is: %d \n",ListLength(L1));

    printf("Please input the length of SqList2:\n");

    scanf("%d", &k);

    L2.length = 0;

    if (k > 0)

        printf("Please input the element of SqList2 one by one:\n");

    for(j=1;j<=k;j++)

    {

        scanf("%d", &l);

        i=ListInsert(&L2,0,l);

    }

    printf("The SqList2 is: ");

    ListTraverse(L2);

    printf("The length of SqList1 is: %d \n",ListLength(L2));

    L3.length = 0;

    InterLeaving(&L3, L1, L2);

    printf("The SqList3 of interleaving L1&2 is: ");

    ListTraverse(L3);

    printf("The length of SqList1 is: %d \n",ListLength(L3));

    return 0;

}

/*

给定一个字符串，采用堆栈将其进行翻转. 例如 "ILoveChina, ILoveBJTU, ILoveGJCXSJXL"

 应被转换成 "LXJSXCJGevoLI ,UTJBevoLI ,anihCevoLI".

【编程提示】：

1. 建一个空栈；
2. 将字符串数组的元素逐一进栈；
3. 将堆栈元素逐一出栈，依次存入字符串数组中。

*/

#include

#include

#include

#include

struct Stack

{

    int top;

    unsigned capacity;

    char* array;

};

struct Stack* createStack(unsigned capacity)

{

    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));

    stack->capacity = capacity;

    stack->top = -1;

    stack->array = (char*) malloc(stack->capacity * sizeof(char));

    return stack;

}

int isFull(struct Stack* stack)

{

    int full = 0;

    full = (stack->top == (int)stack->capacity - 1)?1:0;

    return full;

}

int isEmpty(struct Stack* stack)

{

    return stack->top == -1;

}

void push(struct Stack* stack, char item)

{

  /***补全函数****/

}

char pop(struct Stack* stack)

{

    if (isEmpty(stack))

        return CHAR_MIN;

    return stack->array[stack->top--];

}

void reverseStr(char str[])

{

/***补全函数****/

}

int main()

{

    char str[] = "ILoveChina, ILoveBJTU, ILoveGJCXSJXL";

    printf("The given string %s has %d characters.\n", str, strlen(str));

    reverse(str);

    printf("Reversed string is %s\n", str);

    return 0;

}

利用队列编写程序模拟计算机 *** 作系统的分时任务调度。

结构体QElemType定义了队列中任务的各个数据元素，其中成员id为任务编号，cycle为任务需要消耗的CPU计算资源，rescycle记录任务完成还需要的CPU计算资源，wait统计任务完成总共等待的调度周期。

函数create_task（int id, QElemType *t）用于生成随机任务，参数id为任务id，t为新生成的任务。新生成任务的cycle及rescycle为[1,CYCLEMAX]之间的随机数，wait初始化为0。

已知计算机的CPU核数为N，则被调度任务（即出队列任务）的rescycle值将减少N，如果该任务的rescycle值仍大于0，则需要将该任务重新入队列等待下次调度，如果小于等于0，则该任务完成并将recycle赋值0。如图所示，假设CPU核数为4，程序初始化后开始。队列头成员a0出队列后，判断（recycle-4=3）仍大于0，a0重新入队列。每个调度周期需要更新队列中所有成员的wait值，即wait值加1变为1。

补全函数说明如下：

（1）int EnQueue(LinkQueue *Q, QElemType t)

入队列基本 *** 作。

（2）int ProcQueue(LinkQueue *Q, QElemType *t, int N)

取出队列元素将rescycle减 N，判断rescycle值是否大于0，如果大于0则将任务重新入队列，否则将recycle赋值为0。

（3）int QueueTraverse(LinkQueue *Q)

遍历队列中所有成员并将其wait值加1。

#include

#include

#define TASKMAX 10

#define CYCLEMAX 10

#define TASKINIT 5

#define OK 1

#define ERROR 0

typedef struct{

    int id;   // task id

    int cycle; // task complexity: cpu cycles

    int rescycle;  // count residual cpu cycles

    int wait;  // count the wait times to finish task

}QElemType;

typedef struct QNode {

    QElemType data;

    struct QNode *next;

} QNode, *QueuePtr;

typedef struct{

    QueuePtr front;

    QueuePtr rear;

    int len;

} LinkQueue;

/***  create random new task  ***/

int create_task(int id, QElemType *t){

    t->id=id;

    t->cycle=rand()%CYCLEMAX+1;

    t->rescycle=t->cycle;

    t->wait=0;

    return OK;

}

/* Initialize a link queue */

int InitQueue (LinkQueue *Q){

    Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));

    if(!Q->front) return ERROR;

    Q->front->next=NULL;

    Q->len=0;

    return OK;

} //InitQueue

/* insert element to link queue */

int EnQueue(LinkQueue *Q, QElemType t){

} 

/***补全函数****/

/* delete element from link queue */

int DeQueue(LinkQueue *Q, QElemType *t){

    QueuePtr p;

    if(Q->front==Q->rear) return ERROR;

    p=Q->front->next;

    *t=p->data;

    Q->front->next=p->next;

    Q->len--;

    if(Q->rear==p)

        Q->rear=Q->front;

    free(p);

    return OK;

}

/* process the task in link queue */

int ProcQueue(LinkQueue *Q, QElemType *t, int N){

 /***补全函数****/

}

/* traverse link queue to update the element value of wait by adding one */

int QueueTraverse(LinkQueue *Q){

   /***补全函数****/

}

int main(){

    int i;

    int N;

    int taskid;

    QElemType t;

    LinkQueue Q;

    InitQueue(&Q);

    for(i=1; i<=TASKINIT; i++){

        create_task(i, &t);

        EnQueue(&Q, t);

    }

    taskid=TASKINIT+1;

    printf("Please input the number of CPU cores of your computer: ");

    scanf("%d", &N);

    while(Q.front!=Q.rear){

        ProcQueue(&Q,&t,N);

        if(t.rescycle==0)

            printf("task %4d with %4d cycles has finished and wait %4d schedule times.\n", t.id, t.cycle, t.wait);

        QueueTraverse(&Q);

        if (taskid<=TASKMAX){

            create_task(taskid, &t);

            EnQueue(&Q,t);

            taskid++;

        }

    }

    return 0;

}