广义表的实现
author: kk.h
date: 2006.10
http://www.cocoon.org.cn
*/
#include "stdio.h"
typedef struct node
{
int tag
union{struct node *sublist
char data
}dd
struct node *link
}NODE
/* 递归创建广义表，注意参数比较复杂，指针的指针 */
NODE *creat_GL(char **s)
{
NODE *h
char ch
ch=*(*s)
(*s)++
if(ch!='\0')
{
h=(NODE*)malloc(sizeof(NODE))
if(ch=='(')
{
h->tag=1
h->dd.sublist=creat_GL(s)
}
else
{
h->tag=0
h->dd.data=ch
}
}
else
h=NULL
ch=*(*s)
(*s)++
if(h!=NULL)
if(ch==',')
h->link =creat_GL(s)
else
h->link=NULL
return(h)
}
/* 递归打印广义表 */
vOId prn_GL(NODE *p)
{
if(p!=NULL)
{
if(p->tag==1)
{
printf("(")
if(p->dd.sublist ==NULL)
printf(" ")
else
prn_GL(p->dd.sublist )
}
else
printf("%c",p->dd.data)
if(p->tag==1)
printf(")")
if(p->link!=NULL)
{
printf(",")
prn_GL(p->link)
}
}
}
/* 递归复制广义表 */
NODE *copy_GL(NODE *p)
{
NODE *q
if(p==NULL) return(NULL)
q=(NODE *)malloc(sizeof(NODE))
q->tag=p->tag
if(p->tag)
q->dd.sublist =copy_GL(p->dd.sublist )
else
q->dd.data =p->dd.data
q->link=copy_GL(p->link)
return(q)
}
/* 求表的深度函数（有错误？） */
int depth(NODE *p)
{
int h,maxdh
NODE *q
if(p->tag==0) return(0)
else
if(p->tag==1&&p->dd.sublist==NULL) return 1
else
{
maxdh=0
while(p!=NULL)
{
if(p->tag==0) h=0
else
{q=p->dd.sublist
h=depth(q)
}
if(h>maxdh)
maxdh=h
p=p->link
}
return(maxdh+1)
}
}
/* 求原子结点的个数函数 */
int count(NODE *p)
{
int m,n
if(p==NULL) return(0)
else
{
if(p->tag==0) n=1
else
n=count(p->dd.sublist)
if(p->link!=NULL)
m=count(p->link)
else m=0
return(n+m)
}
}
main()
{
NODE *hd,*hc
char s[100]="(a,(b,(c,d)))",*p
/*p=gets(s)*/
p=s
hd=creat_GL(&p)
hc=copy_GL(hd)
printf("\ncopy after:")
prn_GL(hc)
printf("\ndepth=%d (wrong?)",depth(hc))
printf("\ncount=%d",count(hc))
getch()
}
自学c语言中的数据结构与算法，我把它分为入门，巩固，应用，提高，进化这几个阶段，不同阶段可以看不同书籍。《数据结构与算法分析——C语言描述》 ，一般大学普遍教程。
《算法设计与分析》
《算法引论》
《Elements of Programming》
《C Interfaces and Implementation》
这个相关书籍貌似没得，可以自己是一些功能，如下：
《Algorithm Design Manual》
《The Science of Programming》
《编程珠玑》
《Algorithms 4th》
《Advanced Data Structures》
如果你想成为一个码农或是熟练工（Code Monkey），你大可以不学算法，因为算法对你确实没有用；但如果你想成为一个优秀的开发者（Developer），扎实的算法必不可少，因为你会不断的掉进一些只能借助算法才能爬出去的坑里。所以，骚年加油把。
//顺序栈#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct
{
int *base
int *top
int stacksize
}SqStack
typedef int ElemType
int InitStack(SqStack &S) //为栈S分配存储空间，并置S为空栈
{
int size = STACK_INIT_SIZE
S.base=(int *)malloc(size*sizeof(ElemType))
if(!S.base)
return 0
S.top=S.base//置栈S为空栈
S.stacksize=STACK_INIT_SIZE
return 1
}
int GetTop(SqStack S,int &e) //若栈不空，则用e返回S的栈顶元素
{
if(S.top==S.base) return 0
e=*(S.top-1)
return 1
}
int Push(SqStack &S, int e) /*进栈函数,将e插入栈S中,并使之成为栈顶元素*/
{ if(S.top-S.base>=S.stacksize) /*栈满，追加存储空间*/
{
int stackinvrement = STACKINCREMENT
S.base=(ElemType *) realloc(S.base,(S.stacksize+stackinvrement)*sizeof(ElemType))
if(!S.base)
return 0/*存储分配失败*/
S.stacksize+=STACKINCREMENT
}
*S.top++=e
return 1
}
int Pop(SqStack &S,int &e)/*出栈函数,若栈S不空,则删除S的栈顶元素,用e返回其值*/
{ if(S.top==S.base) return 0
e=*--S.top
return 1
}
void OutputStack(SqStack &S)
{int *q
q=S.top-1
for(int i=0i<S.top-S.basei++)
{
printf("%3d ",*q)q--}
}
void main()
{
int a,b,c
char m
SqStack s
InitStack(s)
printf("请输入要进栈的元素个数是:")
scanf("%d",&a)
printf("\n请输入要进栈的%d个元素:",a)
for(b=0b<ab++) {
scanf("%d",&c)
Push(s,c)}
do { printf("\n")
printf("*********** 1.输出栈的元素**********\n")
printf("*********** 2.取栈顶元素************\n")
printf("*********** 3.删除栈顶元素**********\n")
printf("*********** 4.退出程序**********\n")
printf("\n请选择一个字符:")
getchar()
scanf("%c",&m)
switch(m) {
case '1': printf("\n输出的栈为:")
OutputStack(s)
break
case '2': GetTop(s,c)
printf("\n栈顶元素为:%d",c)
printf("\n输出的栈为:")
OutputStack(s)
break
case '3': Pop(s,c)
printf("\n删除的栈顶元素:%d",c)
printf("\n输出的栈为:")
OutputStack(s)
printf("\n")
break
case '4':break
default: printf("输入的数字有错，请重新选择!\n")break
}
}while(m!='4')
}
//链栈
#include<stdio.h>
#include<stdlib.h>
typedef struct SNode
{
int data
struct SNode *next
}SNode,*LinkStack
LinkStack top
LinkStack PushStack(LinkStack top,int x)//入栈
{
LinkStack s
s=(LinkStack)malloc(sizeof(SNode))
s->data=x
s->next=top
top=s
return top
}
LinkStack PopStack(LinkStack top) //退栈
{
LinkStack p
if(top!=NULL)
{
p=top
top=top->next
free(p)
printf("退栈已完成\n")
return top
}
else printf("栈是空的，无法退栈！\n")return 0
}
int GetStackTop(LinkStack top)//取栈顶元素
{
return top->data
}
bool IsEmpty()//bool取值false和true，是0和1的区别,bool只有一个字节,BOOL为int型,bool为布尔型
{
return top==NULL ? true:false
}
void Print()
{
SNode *p
p=top
if(IsEmpty())
{
printf("The stack is empty!\n")
return
}
while(p)
{
printf("%d ", p->data)
p=p->next
}
printf("\n")
}
void main()
{
int x,a,b
char m
do { printf("\n")
printf("###############链栈的基本操作##################\n")
printf("××××××××1.置空栈××××××××××\n")
printf("××××××××2.进栈×××××××××××\n")
printf("××××××××3.退栈×××××××××××\n")
printf("××××××××4.取栈顶元素××××××××\n")
printf("××××××××5.退出程序×××××××××\n")
printf("##############################################\n")
printf("\n请选择一个字符:")
scanf("%c",&m)
switch(m){
case '1':
top=NULL
printf("\n栈已置空!")
break
case '2':
printf("\n请输入要进栈的元素个数是:")
scanf("%d",&a)
printf("\n请输入要进栈的%d个元素:",a)
for(b=0b<ab++) {
scanf("%d",&x)
top=PushStack(top,x)}
printf("进栈已完成！\n")
printf("\n输出栈为:")
Print()
break
case '3':
printf("\n操作之前的输出栈为:")
Print()
top=PopStack(top)
printf("\n操作过后的输出栈为:")
Print()
break
case '4':
printf("\n输出栈为:")
Print()
if(top!=NULL)
printf("\n栈顶元素是：%d\n",GetStackTop(top))
else
printf("\n栈是空的，没有元素！")
break
case '5':break
default:
printf("\n输入的字符不对，请重新输入!")
break
}
getchar()
}while(m!='5')
}
