数据结构与算法分析练习

Question

1. 利用栈实现链表的就地逆置
int ReverseList (struct node * head) #成功逆置返回1，否则返回0
{

}
2. 利用栈实现十进制数字到N进制的转换
int ten_to_N ( int x) #打印出转换的N进制数(N<9),成功返回1，否则返回0
{

}
3. 利用两个栈实现一个队列
struct queue
{
stack<int> s1 , s2;
} ;
int enqueue ( struct queue *q , int x ) #将x插入到队列q中，成功返回1，否则返回0
{

}

int dequeue ( struct queue *q ) #队列q执行出队操作，成功则返回出队的元素，否则返回0
{

}

Answer 1

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

using namespace std;

struct node {
    int e;
    struct node *next;
};

/**
  * 初始化link
  * head为根节点，不保存数据
  */
struct node *initLink(struct node *link) {
    link = (struct node *)malloc(sizeof(struct node));
    link->next = NULL;

    struct node *q = link;

    int n=0;

    while(n!=-1) { //终止条件自行修改，比方说，建立n个节点
        cin >> n;
        if (n>0) {
            struct node *t = (struct node *)malloc(sizeof(struct node));
            t->e = n;
            t->next = NULL;
            q->next = t;
            q = t;
        }
    }
    return link;
}

/** 逆置(头插法)
  * 另有，递归法。递归法耗用资源多，头插法比较好。
  * #成功逆置返回1，否则返回0(不会有0的情况发生)
  */
int ReverseList (struct node *head) {
    struct node *p = head->next, *q;
    head->next = NULL;

    while (p) {
        q = p;
        p = p->next;
        q->next =head->next;
        head->next = q;
    }
    return 1;
}

/**
  * #打印出转换的N进制数(N<9),成功返回1，否则返回0
  */
int ten_to_N(int x, int N) {
    int r=-1;
    if (x>0) {
        r = x%N;
        ten_to_N(x/N, N);
    }
    if (r>=0)
        printf("%d",r);
    return 1;
}

struct queue {
    stack<int> s1 , s2;
};

/**
  * #将x插入到队列q中，成功返回1，否则返回0
  */
int enqueue ( struct queue *q , int x ) {
    if (q->s1.size()>0)
        q->s1.push(x);
    else {
        while (q->s2.size()>0) {
            q->s1.push(q->s2.top());
            q->s2.pop();
        }
        q->s1.push(x);
    }
    return 1;
}
/**
  * #队列q执行出队操作，成功则返回出队的元素，否则返回0
  */
int dequeue ( struct queue *q ) {
    int t = 0;
    if (q->s2.size()>0) {
        q->s2.top();
        q->s2.pop();
    } else {
        while (q->s1.size()>1) {
            q->s2.push(q->s1.top());
            q->s1.pop();
        }
        if(q->s1.size()==1){
            t=q->s1.top();
            q->s1.pop();
        }
    }
    return t;
}

int main()
{
    struct node *head = NULL;
    head = initLink(head);

    if (ReverseList(head) == 1) {
        struct node *p = head->next;
        while (p) {
            printf("%d ", p->e);
            p=p->next;
        }
        printf("\nReverseList done.\n");
    }

    ten_to_N(10, 4);
    struct node *q;
    while(head) {
        q = head->next;
        free(head);
        head = q;
    }
}