发布时间 : 星期一 文章数据结构各种算法更新完毕开始阅读6a583b91ed3a87c24028915f804d2b160b4e863b
数据结构
栈的进、出操作
#include \#include\#define stack_init_size 100 //初始空间 #define stackincrement 10 //增量
typedef int selemtype; typedef struct { selemtype *base; selemtype *top;
int stacksize; //当前已经分配的存储空间，以元素为单位
}sqstack;
void initstack(sqstack *s)
//栈的初始
{ s->base=(int *)malloc (stack_init_size * sizeof(int)); if(!s->base) { printf(\分配失败!\\n\ exit(0);
}
s->top=s->base;
s->stacksize=stack_init_size;
//初始空间
}
void destroystack(sqstack *s)
//销毁栈
{ free(s->base);
s->top=s->base=NULL; s->stacksize =0;
}
void clearstack(sqstack *s)
//清空
{ s->top=s->base;
}
int stackempty(sqstack s)
//判断是否为空
{ if((s.top-s.base)!=0) return 1; else { printf(\栈为空!\ return 0;
}
}
int stacklength(sqstack s) //求栈的长度 { if(stackempty(s)) { return s.top-s.base;
} return 0;
}
void gettop(sqstack s,int*e) //取值运算 { if(s.top==s.base) { printf(\栈为空!\
exit(0); }
*e=*(s.top-1);
}
void push(sqstack *s,int n) //输入栈（插入运算）
{
if((s->top-s->base)>=s->stacksize )
{s->base=(int*)realloc(s->base,(s->stacksize+ stackincrement)*sizeof(int));
if(!s->base) { printf(\分配失败!\\n\ exit(0);
}
s->top=s->base+s->stacksize ; s->stacksize +=stackincrement;
}
*s->top++=n;
}
void print_stack(sqstack *s) //输出栈
{ int *p=s->top; if(!s->base ) { printf(\栈不存在！\ exit(0);
}
if(s->top==s->base)
printf(\栈为空!\
else { while(p!=s->base) printf(\ }
printf(\
}
void pop(sqstack *s,int *e) //删除栈
{ if(s->top==s->base)
printf(\栈为空!\ else
*e=*--s->top; }
void main() { sqstack s; int a,i;
int A[]={0,1,2,3,4,5,6,7,8,9,10,11,12}; initstack(&s); for(i=0;i<13;i++)
push(&s,A[i]);
printf(\输出栈:\\n\ print_stack(&s);
printf(\请输入进栈的元素：\ scanf(\ push(&s,a);
printf(\再次输出栈:\\n\
print_stack(&s); } /* printf(\删除一个元素：\\n\ pop(&s,&b); printf(\ printf(\取值:\\n\ gettop(s,&b); printf(\
if(stackempty(s)) printf(\栈不为空！\ printf(\输出栈：\\n\ print_stack(&s); printf(\销毁栈\\n\ destroystack(&s); printf(\输出栈：\\n\ print_stack(&s);
*/
二叉树的操作（创建及遍历）
#include
struct Node *lchild,*rchild; //左右孩子
}tree;
tree *createtree()
//先序创建树
{ char temp; tree *t; temp=getchar();
t= (tree *)malloc(sizeof(tree)); if(temp=='#') return(NULL); //t=NULL; // else if(temp=';') exit(0); else { t->data =temp; t->lchild =createtree(); t->rchild =createtree();
} return t;
}
void xianxu(tree *root) //递归先序遍历 { tree *t; t=root;
if(t!=NULL) { printf(\ xianxu(t->lchild); xianxu(t->rchild); } }
void zhongxu(tree *root) {
tree *t;
t=root; if(t!=NULL)
{
zhongxu(t->lchild);
printf(\
zhongxu(t->rchild); } } void main() { tree *p; p=createtree(); xianxu(p); printf(\ zhongxu(p); printf(\
}
//二叉树：abc##de#g##f###
/*---------------------------------------------------------------------
广义表的存储结构
---------------------------------------------------------------------*/ #include
typedef char ElemType; //元素类型是字符型 struct GNode
//广义表的存储结构
{ int tag; //标志域
union{ //值域或子表的表头指针域 ElemType data; struct GNode *sublist;
};
struct GNode *next; //指向后继结点的指针域
};
/*----------------------函数声明----------------------*/ int LengthGList(struct GNode *GL); //求广义表的长度 int DepthGList(struct GNode *GL);
//求广义表的深度
void CreateGList(struct GNode **GL); //建立广义表的存储结构 void PrintGList(struct GNode *GL);
//打印输出广义表
int SearchGList(struct GNode *GL, ElemType e); //查找等于给定字符的单元素结点，查找成功则返回1，否则返回0 /*----------------------主函数----------------------*/ void main() { char search;
struct GNode *GL; //带表头附加结点 GL=(struct GNode *) malloc(sizeof(struct GNode));
printf(\输入一个广义表，以分号结束\\n\ CreateGList(&GL); //\为什么这样写 printf(\输出广义表：\
PrintGList(GL);
//\为什么这样写
printf(\
printf(\广义表的长度：\ printf(\
printf(\广义表的深度：\ printf(\ /*
printf(\请输入查找的值：\ scanf(\
printf(\搜索值 %c 的结果：\*/
printf(\
}
/*----------------------函数----------------------*/ //求广义表的长度 int LengthGList(struct GNode *GL) { if(GL!=NULL) return(1 + LengthGList(GL->next));
else
return(0);
}
//求广义表的深度 int DepthGList(struct GNode *GL) { int max=0; //给max赋初值
//遍历表中每一个结点，求出所有子表的最大深度 while(GL!=NULL)
{
if(GL->tag==1){
int dep = DepthGList(GL->sublist); //递归调用求出一个子表
的深度
if(dep > max)
max = dep; //让max始终为同一层所
求过的子表中深度的最大值 } GL = GL->next; //使GL指向同一层的下一个结点
}
return(max + 1); //返回表的深度
}
void CreateGList(struct GNode **GL) //建立广义表的存储结构 { char ch;
scanf(\ //读入一个字符，此处只可能读入空格#、左括号或英文字母 if(ch=='#') //若输入为空格，则置表头指针为空
*GL = NULL;
else if(ch=='(') //若输入为左括号则建立由*GL所指向的子表结点并
递归构造子表
{
*GL =(struct GNode *) malloc(sizeof(struct GNode));
//原始语
句为：*GL= malloc(sizeof(struct GNode));
(*GL)->tag = 1;
CreateGList(&((*GL)->sublist));
}
else //若输入为字符则建立由*GL所指向的单元素结点 {
*GL =(struct GNode *) malloc(sizeof(struct GNode)); (*GL)->tag = 0; (*GL)->data = ch;
}
scanf(\ //此处读入的字符必为逗号、右括号或分号 if(*GL==NULL); //若*GL为空，则什么都不做 else if(ch==',') //若输入逗号则递归构造后继表
CreateGList(&((*GL)->next));
else if((ch==')') || (ch==';')) //若输入为右括号或分号，则置*GL的
后继指针域为空
(*GL)->next = NULL;
}
//打印输出广义表 void PrintGList(struct GNode *GL) { //对于表结点的处理情况 if(GL->tag==1){ //存在子表，则输出左括号，作为开始符号
printf(\
if(GL->sublist==NULL) //若子表为空则输出'#'字符
printf(\
else //若子表非空，则递归输出子表
PrintGList(GL->sublist);
printf(\ //当一个子表输出结束后，应输出一个右括号终
止符 }
else //对于单元素结点，则输出该结点的值
printf(\ if(GL->next!=NULL) //输出结点的后继表
{ printf(\ //先输出逗号分隔符
PrintGList(GL->next); //再递归输出后继表
}
// printf(\
}
//查找等于给定字符的单元素结点，查找成功则返回1，否则返回0 int SearchGList(struct GNode *GL, ElemType e) {
while(GL!=NULL){ if(GL->tag == 1) //存在子表，则递归搜索本层该子表
{
回1
}
if(SearchGList(GL->sublist, e))
return(1);
p=h; if(h!=NULL)
do {
printf(\p=p->next;
else //存在单元素结点，则查询是否存在值e ，若存在则返
}
{ }
GL = GL->next; //使GL指向同一层的下一个结点
if(GL->data == e)
return(1);
}
}while(p!=0);
printf(\
void insert(struct student *h,int n) { struct student * p1,* p2; int i;
//插入
return(0); //剩下来的情况，GL值为NULL，代表搜索不到值e ，
输出0 }
双向链表的操作
#include
#define len sizeof (struct student) //int n; struct student { struct student *prior; int num; float score; struct student * next;
};
struct student *creat (void)
//返回首地址{ struct student *head; struct student * p1, * p2; p1=(struct student *) malloc(len); //n=0; head=p1; p2=p1;
scanf(\ while(p1->num!=0) { p1=(struct student *) malloc(len); scanf(\ p2->next=p1; p1->prior=p2; p2=p1;
}
p1->next=NULL; return(head);
}
void print(struct student *h)
//打印
{
struct student * p;
for(i=1;i { if(i==1) p1=h->next; else p1=p1->next; } p2=(struct student *) malloc(len); p2->next=p1->next; p2->prior=p1; p1->next->prior=p2; p1->next=p2; printf(\ scanf(\ } void main() { struct student * head; head=creat(); //返回首地址 printf(\原数据为：\\n\ print(head); //打印 insert(head,3); //插入 printf(\插入之后的数据为：\\n\ print(head); }