链栈

链栈只是单链表的一个简单应用，只要理解单链表的头插法，链栈的出栈入栈很好理解。

代码实现

linkstack.h如下：

#include <stdio.h>
#include <malloc.h>
#include <stddef.h>

typedef int ElemType;
typedef struct Node{
	ElemType data;
	struct Node * next;
}LinkStack;

LinkStack.cpp如下：

#include "linkstack.h"
void initLinkStack(LinkStack *&ls);
bool push(LinkStack *&ls, ElemType e);
bool pop(LinkStack *&ls, ElemType &e);
bool peek(LinkStack *ls, ElemType &e);
void printStack(LinkStack *ls);

int main() {
	LinkStack * ls;
	initLinkStack(ls);

	push(ls,10);
	push(ls,20);
	push(ls,30);
	printStack(ls);

	ElemType e;
	pop(ls,e);
	printStack(ls);
	return 0;
}
void initLinkStack(LinkStack *&ls){
	ls = (LinkStack *) malloc(sizeof(LinkStack));
	ls->next = NULL;
}

void destroy(LinkStack *&ls){
	LinkStack *p = ls, *q;
	q = p->next;
	while(q != NULL){
		free(p);
		p = q;
		q = q->next;
	}
	free(p);
}

//入栈，就是一个头插法，很简单
bool push(LinkStack *&ls, ElemType e){
	LinkStack* node = (LinkStack*) malloc(sizeof(LinkStack));
	node->next = ls->next;
	node->data = e;
	ls->next = node;
	return true;
}

//出栈
bool pop(LinkStack *&ls, ElemType &e){
	if(ls->next == NULL){
		printf("栈空，无法出栈");
		return false;
	}
	LinkStack *p = ls->next;
	e = p->data;
	ls->next = p->next;
	free(p);
	return true;
}

//取栈顶
bool peek(LinkStack *ls, ElemType &e){
	if(ls->next == NULL){
		printf("栈空，无栈顶元素");
		return false;
	}
	e = ls->next->data;
	return true;
}

void printStack(LinkStack *ls){
	LinkStack *q = ls->next;
	while(q!=NULL){
		printf("%d\t",q->data);
		q = q->next;
	}
	printf("\n");
}

输出结果为:

30	20	10	
20	10

记录:二进制和十进制的转换
我们知道十进制转换为二进制采用余数倒转法，二进制转换为十进制使用2的指数与位数乘积之和

101000101
第一个1之和有8位，2^8为256，第二个1之和有6位，2^6为64，以此类推，相加为256+64+4+1=325

417
417位于256到512之间，256=2^8，则100000000，1后有8个0，
417减去256=161，位于128到256之间，1后有7个0，和之前的拼接，即110000000
以此类推，得出110100001