顺序栈
/* 静态分配栈空间，大小固定，不能扩充*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define maxleng 10
typedef int ElemType;
typedef struct
{ ElemType elem[maxleng+1]; /*栈元素空间*/
int top; /*顶指针*/
}SqStack;
/******************************************************
SqStack为结构类型
例：SqStack s；说明s为结构类型变量，可表示一个栈
其中,s.top----顶指针；s.elem[s.top]----顶元素
未用元素s.elem[0]
******************************************************/
/**********************************************************
** 功能：测试栈是否为空 **
** 输入：栈对象S **
** 输出,空时返回TRUE,非空时返回FALSE **
**********************************************************/
int StackEmpty(SqStack S)
{ if (S.top==0)
return TRUE;
else
return FALSE;
}
/**********************************************************
** 功能：进栈操作 **
** 输入：栈对象S的指针，数据元素e **
** 输出,成功时返回OK **
**********************************************************/
int Push(SqStack *S,ElemType e)
{
int j;
if (S->top==maxleng) /*栈溢出*/
{
printf("OVERFLOW");
return ERROR;
}
S->top++; /*栈顶加1*/
S->elem[S->top]=e; /*新元素进栈*/
return OK;
}
/*******************************************************************
** 功能：退栈操作 **
** 输入：栈对象S的指针 **
** 输出,成功时返回OK、通过数据元素指针e返回栈顶元素的值 **
** 空栈时返回ＥＲＲＯＲ **
*******************************************************************/
int Pop(SqStack *S,ElemType *e)
{
if(StackEmpty(*S)) return ERROR; /*空栈,失败返回 */
*e=S->elem[S->top];/*取栈顶元素*/
S->top=S->top-1; /*栈顶减1*/
return OK; /*成功返回 */
}
main()
{
int i; ElemType elem;
SqStack s; /*定义栈对象s*/
s.top=0; /*初始化栈对象s*/
clrscr();
for(i=1;i<=5;i++) /*输入5个数据元素并进栈*/
{
printf("No%d? ",i);
scanf("%d",&elem);
Push(&s,elem);
};
for(i=1;i<=7;i++) /*退栈操作*/
{
if (Pop(&s,&elem)==OK) /*正确退栈时，可通过elem输出数据元素*/
printf("No%d=%d ",i,elem);
else /*若栈已空，结束，此时elem的值无意义，*/
{ printf("stack has been empty!"); break;}
};
}
4链式队列
定义结点类型
(1)存放元素的结点类型
typedef int ElemType;
typedef struct QNode
{ ElemType data;
struct QNode *next;
} QNode,*QueuePtr;
/*可理解为定义两个类型:
QNode ----- 链式队列结点的结构类型;
QueuePtr ----- 链式队列结点指针类型，指向链式队列结点,
*/
(2)由头、尾指针组成的结点类型
typedef struct {
QueuePtr front; /*队头指针*/
QueuePtr rear; /*队尾指针*/
} LinkQueue; /*结构类型LinkQueue的变量为队列对象*/
/**********************************************************
** 功能：初始化队列 **
** 输入：队列对象S的指针 **
** 输出,成功时返回OK **
**********************************************************/
int InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=(QueuePtr) malloc(sizeof(QNode));
if (Q->front==NULL) return ERROR;
Q->front->next=NULL;
return OK;
}
/**********************************************************
** 功能：测试队列是否为空 **
** 输入：队列对象Q **
** 输出,空时返回TRUE,非空时返回FALSE **
**********************************************************/
int QueueEmpty(LinkQueue Q)
{
if (Q.front==Q.rear) return TRUE;
else return FALSE;
}
/**********************************************************
** 功能：进队列操作 **
** 输入：队列对象Q的指针，数据元素e **
** 输出,成功时返回OK **
**********************************************************/
int EnQueue(LinkQueue *Q,ElemType e) /*进队列*/
{
Q->rear->next=(QueuePtr) malloc(sizeof(QNode)); /*创建新结点*/
if(Q->rear->next==NULL) exit(OVERFLOW);
Q->rear=Q->rear->next; /*修改尾结点指针*/
Q->rear->data=e; Q->rear->next=NULL; /*新结点赋值*/
return OK;
}
/*******************************************************************
** 功能：出队操作 **
** 输入：队列对象S的指针 **
** 输出,成功时返回OK、通过数据元素指针e返回队首元素的值 **
** 空队列时返回ＥＲＲＯＲ **
*******************************************************************/
int DeQueue(LinkQueue *Q,ElemType *e) /*出队列*/
{
QueuePtr p;
if (QueueEmpty(*Q)) return ERROR; /*空队列，返回错误*/
p=Q->front->next; /*p指向删除结点*/
*e=p->data; /*取数据*/
Q->front->next=p->next; /*修改队头指针*/
if (Q->rear==p) Q->rear=Q->front;/*若删除结点为队尾结点，
设置为空队列*/
free(p);
return OK;
}
_
main()
{
int i;
ElemType elem;
LinkQueue que; /*定义队列对象que*/
InitQueue(&que); /*队列que初始化*/
EnQueue(&que,1); /*元素1进队列*/
EnQueue(&que,2); /*元素2进队列*/
EnQueue(&que,3); /*元素3进队列*/
DeQueue(&que,&elem); printf("%d",elem); /*1 出队列*/
DeQueue(&que,&elem); printf("%d",elem); /*2 出队列*/
DeQueue(&que,&elem); printf("%d",elem); /*3 出队列*/
DeQueue(&que,&elem); printf("%d",elem);
/*队列已空，由于未检查返回结果，取出的还是3,产生错误*/
}
5．顺序队列
#define MAXQSIZE 100 /*首次分配连续存储单元的大小，可存储MAXQSIZE个元素*/
typedef int ElemType;
typedef struct SqList
{ ElemType *base; /*连续存储单元首地址*/
int front; /*队列头指针，若队列不空，指向队头元素*/
int rear; /*队列尾指针，若队列不空，指向队尾元素的下一个位置*/
} SqQueue; /*SqQueue为结构类型，用其说明的变量在程序中作为队列*/
/**********************************************************
** 功能：初始化队列 **
** 输入：队列对象S的指针 **
** 输出,成功时返回OK **
**********************************************************/
int InitQueue(SqQueue *Q)
{
Q->base=(ElemType *) malloc(MAXQSIZE*sizeof(ElemType));
if (!Q->base) exit(OVERFLOW);
Q->front=Q->rear=0;
return OK;
}
/**********************************************************
** 功能：进队列操作 **
** 输入：队列对象Q的指针，数据元素e **
** 输出,成功时返回OK **
**********************************************************/
int EnQueue(SqQueue *Q,ElemType e)
{
if ((Q->rear+1)%MAXQSIZE==Q->front)
return ERROR;
Q->base[Q->rear]=e;
Q->rear=(Q->rear+1)%MAXQSIZE;
return OK;
}
/*******************************************************************
** 功能：出队操作 **
** 输入：队列对象S的指针 **
** 输出,成功时返回OK、通过数据元素指针e返回队首元素的值 **
** 空队列时返回ＥＲＲＯＲ **
*******************************************************************/
int DeQueue(SqQueue *Q,ElemType *e)
{
if (Q->rear==Q->front)
return ERROR;
*e=Q->base[Q->front];
Q->front=(Q->front+1)%MAXQSIZE;
return OK;
}
main()
{
ElemType *elem;
SqQueue que;
clrscr();
InitQueue(&que);
EnQueue(&que,1); /*元素1进队列*/
EnQueue(&que,2); /*元素2进队列*/
EnQueue(&que,3); /*元素3进队列*/
DeQueue(&que,&elem); printf("%d",elem); /*1 出队列*/
DeQueue(&que,&elem); printf("%d",elem); /*2 出队列*/
DeQueue(&que,&elem); printf("%d",elem); /*3 出队列*/
DeQueue(&que,&elem); printf("%d",elem);
/*队列已空，由于未检查返回结果，取出的还是3,产生错误，
所以应检查返回结果，当返回结果为OK时访问elem才有意义*/
}
6．串将串长作为存储结构的一部分：
typedef struct {
char *ch; //若是非空串，则按串长分配存储区，否则ch为NULL
int length; //串长度
} HString;
/*******************************************************************
** 功能：将串清空 **
** 输入：串对象S的指针 **
** 输出,无 **
*******************************************************************/
void ClearString(HString *S)
/*将S清为空串*/
{
if (S->ch)
{ free(S->ch);
S->ch=NULL;
}
S->length=0;
}
/*******************************************************************
** 功能：字符串赋值操作 **
** 输入：字符串对象指针的T，字符指针表示的C字符串 **
** 输出,成功时返回OK **
*******************************************************************/
int StrAssign(HString *T,char *chars)
/*根据chars表示的串常量产生串T*/
{
char *c; int i;
if (T->ch) free(T->ch); /*释放T原有空间*/
for(i=0,c=chars; *c; i++,++c); /*求chars的串长i*/
if (!i)
{T->ch=NULL;T->length=0;} /*当chars为空串时*/
else {
if (!(T->ch=(char *) malloc(i*sizeof(char))))
return exit(OVERFLOW);
T->length=i;
for(; i>0; i--) /*复制chars串值到串T*/
T->ch[i-1]=chars[i-1];
}
return OK;
}
/*******************************************************************
** 功能：输出字符串 **
** 输入：字符串对象T **
** 输出,无 **
*******************************************************************/
void StrPrint(HString T)
/*显示串T*/
{
int i;
for(i=0;i<T.length;i++)
putchar(T.ch[i]);
}
/*******************************************************************
** 功能：字符串联接,串1+串2=>结果T **
** 输入：结果字符串对象指针的T和字符串对象S1、S2 **
** 输出,成功时返回OK **
*******************************************************************/
int Concat(HString *T,HString S1,HString S2)
/*用Ｔ返回Ｓ１和Ｓ２连接而成的新串*/
{
int i;
if (T->ch) free(T->ch); /*释放T原有空间*/
if (!(T->ch=(char *) malloc((S1.length+S2.length)*sizeof(char))))
exit(OVERFLOW);
for(i=0;i<S1.length;i++) /*复制S1串值到串T*/
T->ch[i]=S1.ch[i];
for(i=0;i<S2.length;i++) /*复制S2串值到串T*/
T->ch[S1.length+i]=S2.ch[i];
T->length=S1.length+S2.length; /*设定Ｔ的长度*/
return OK;
}
main()
{
HString str1={NULL,0},str2={NULL,0},str3={NULL,0}; /*定义串对象str1,str2,str3*/
clrscr();
ClearString(&str1);
StrAssign(&str1,"abcd");
StrAssign(&str2,"1234");
Concat(&str3,str1,str2);
StrPrint(str3);
}
4.2.3串的单链表表示
例 一个结点只放1个字符
struct node1
{ char data； //为一个字符
struct node *next； //为指针
}*ps1；
data next
头指针 首结点 尾结点
存储密度=串值所占存储位/实际分配存储位存储效率太低，存储密度为 0.33
若一个结点放多个字符，可提高存储效率，但算法就会变复杂。
7．二叉树算法综合举例：
#include "stdio.h"
#define leng sizeof(BiTNode) /*结点所占空间的大小*/
typedef int TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
/*******************************************************************
** 功能：利用二叉树的的特性产生二叉树 **
** 输入：算法执行中输入各结点的满二叉树序号值和结点的值 **
** 输出,二叉树根指针 **
*******************************************************************/
#define MAXSIZE 100
BiTree CreatTree()
{
BiTNode *s[MAXSIZE+1],*root,*q;
int i,j;
TElemType x;
printf("i,x="); scanf("%d%d",&i,&x); /*输入结点序号和值*/
while(i!=0)
{
q=(BiTNode *) malloc(sizeof(BiTNode));
q->data=x;q->lchild=q->rchild=NULL;
s[i]=q;
if (i==1) root=q; /*处理根结点*/
else {
j=i/2; /* j 为当前结点的父结点序号*/
if (i%2) s[j]->rchild=q; /*当前结点为其父结点的右孩子*/
else s[j]->lchild=q; /*当前结点为其父结点的左孩子*/
}
printf("i,x="); scanf("%d%d",&i,&x); /*输入结点序号和值*/
}
return root; /*返回二叉树根指针*/
}
/*******************************************************************
** 功能：利用带空二叉树的先序序列生产二叉树 **
** 输入：算法执行中输入带空二叉树的先序序列 **
** 输出,二叉树根指针 **
*******************************************************************/
BiTree CreatBiTree()
{ char ch;
BiTree root;
scanf("%c",&ch); /*输入一个结点，假定为字符型*/
if (ch =='φ') root=NULL;
else
{ root=(BiTree) malloc(leng);
root->data=ch; /*生成根结点 */
root->lchild=CreatBiTree(); /*递归构造左子树 */
root->rchild=CreatBiTree(); /*递归构造右子树 */
}
return root;
}
/*******************************************************************
** 功能：计算二叉树结点数 **
** 输入：二叉树的根结点指针 **
** 输出,结点数数值 **
*******************************************************************/
int count(BiTree root)
{ int n=0 ;
if (root)
{ n=1;
n+=count(root->lchild);
n+=count(root->rchild);
}
return n;
}
/*******************************************************************
** 功能：二叉树的先序遍历操作 **
** 输入：二叉树的根结点指针 **
** 输出,无 **
*******************************************************************/
void PreOrderTraverse(BiTree T)
{
if (T) {
printf("%d",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
/*******************************************************************
** 功能：二叉树的中序遍历操作 **
** 输入：二叉树的根结点指针 **
** 输出,无 **
*******************************************************************/
void MidOrderTraverse(BiTree T)
{
if (T) {
MidOrderTraverse(T->lchild);
printf("%d",T->data);
MidOrderTraverse(T->rchild);
}
}
/*******************************************************************
** 功能：二叉排序树的生成 **
** 输入：二叉排序树的根结点指针，新结点数据 **
** 输出：二叉排序树的根结点指针 **
*******************************************************************/
BiTree intree(BiTree t,TElemType x)
{ if (t==NULL) /*t是指向二叉树根指针的指针*/
{ t=(BiTree) malloc(sizeof(BiTNode));
t->data=x; /*生成并插入结点x*/
t->lchild=t->rchild=NULL; /*为叶子结点*/
}
else if(x<t->data)
t->lchild=intree(t->lchild,x);
else t->rchild=intree(t->rchild,x);
return t;
}
main()
{
int i;
BiTree tree1,tree2;
clrscr();
tree1=CreatTree();
tree2= CreatBiTree()
printf(“第一棵树的先序序列：”);
PreOrderTraverse(tree1);
printf(" 结点数=%d",count(tree1));
printf(“第二棵树的先序序列：”);
PreOrderTraverse(tree2);
printf(" 结点数=%d",count(tree2));
printf(“输入二叉排序树的数据：”);
scanf("%d",&i);
while (i)
{
tree=intree(tree,i);
scanf("%d",&i);
}
printf(“二叉排序树的先序序列：”);
PreOrderTraverse(tree);putchar('\n');
printf(“二叉排序树的中序序列：”);
MidOrderTraverse(tree);
}
/* 静态分配栈空间，大小固定，不能扩充*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define maxleng 10
typedef int ElemType;
typedef struct
{ ElemType elem[maxleng+1]; /*栈元素空间*/
int top; /*顶指针*/
}SqStack;
/******************************************************
SqStack为结构类型
例：SqStack s；说明s为结构类型变量，可表示一个栈
其中,s.top----顶指针；s.elem[s.top]----顶元素
未用元素s.elem[0]
******************************************************/
/**********************************************************
** 功能：测试栈是否为空 **
** 输入：栈对象S **
** 输出,空时返回TRUE,非空时返回FALSE **
**********************************************************/
int StackEmpty(SqStack S)
{ if (S.top==0)
return TRUE;
else
return FALSE;
}
/**********************************************************
** 功能：进栈操作 **
** 输入：栈对象S的指针，数据元素e **
** 输出,成功时返回OK **
**********************************************************/
int Push(SqStack *S,ElemType e)
{
int j;
if (S->top==maxleng) /*栈溢出*/
{
printf("OVERFLOW");
return ERROR;
}
S->top++; /*栈顶加1*/
S->elem[S->top]=e; /*新元素进栈*/
return OK;
}
/*******************************************************************
** 功能：退栈操作 **
** 输入：栈对象S的指针 **
** 输出,成功时返回OK、通过数据元素指针e返回栈顶元素的值 **
** 空栈时返回ＥＲＲＯＲ **
*******************************************************************/
int Pop(SqStack *S,ElemType *e)
{
if(StackEmpty(*S)) return ERROR; /*空栈,失败返回 */
*e=S->elem[S->top];/*取栈顶元素*/
S->top=S->top-1; /*栈顶减1*/
return OK; /*成功返回 */
}
main()
{
int i; ElemType elem;
SqStack s; /*定义栈对象s*/
s.top=0; /*初始化栈对象s*/
clrscr();
for(i=1;i<=5;i++) /*输入5个数据元素并进栈*/
{
printf("No%d? ",i);
scanf("%d",&elem);
Push(&s,elem);
};
for(i=1;i<=7;i++) /*退栈操作*/
{
if (Pop(&s,&elem)==OK) /*正确退栈时，可通过elem输出数据元素*/
printf("No%d=%d ",i,elem);
else /*若栈已空，结束，此时elem的值无意义，*/
{ printf("stack has been empty!"); break;}
};
}
4链式队列
定义结点类型
(1)存放元素的结点类型
typedef int ElemType;
typedef struct QNode
{ ElemType data;
struct QNode *next;
} QNode,*QueuePtr;
/*可理解为定义两个类型:
QNode ----- 链式队列结点的结构类型;
QueuePtr ----- 链式队列结点指针类型，指向链式队列结点,
*/
(2)由头、尾指针组成的结点类型
typedef struct {
QueuePtr front; /*队头指针*/
QueuePtr rear; /*队尾指针*/
} LinkQueue; /*结构类型LinkQueue的变量为队列对象*/
/**********************************************************
** 功能：初始化队列 **
** 输入：队列对象S的指针 **
** 输出,成功时返回OK **
**********************************************************/
int InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=(QueuePtr) malloc(sizeof(QNode));
if (Q->front==NULL) return ERROR;
Q->front->next=NULL;
return OK;
}
/**********************************************************
** 功能：测试队列是否为空 **
** 输入：队列对象Q **
** 输出,空时返回TRUE,非空时返回FALSE **
**********************************************************/
int QueueEmpty(LinkQueue Q)
{
if (Q.front==Q.rear) return TRUE;
else return FALSE;
}
/**********************************************************
** 功能：进队列操作 **
** 输入：队列对象Q的指针，数据元素e **
** 输出,成功时返回OK **
**********************************************************/
int EnQueue(LinkQueue *Q,ElemType e) /*进队列*/
{
Q->rear->next=(QueuePtr) malloc(sizeof(QNode)); /*创建新结点*/
if(Q->rear->next==NULL) exit(OVERFLOW);
Q->rear=Q->rear->next; /*修改尾结点指针*/
Q->rear->data=e; Q->rear->next=NULL; /*新结点赋值*/
return OK;
}
/*******************************************************************
** 功能：出队操作 **
** 输入：队列对象S的指针 **
** 输出,成功时返回OK、通过数据元素指针e返回队首元素的值 **
** 空队列时返回ＥＲＲＯＲ **
*******************************************************************/
int DeQueue(LinkQueue *Q,ElemType *e) /*出队列*/
{
QueuePtr p;
if (QueueEmpty(*Q)) return ERROR; /*空队列，返回错误*/
p=Q->front->next; /*p指向删除结点*/
*e=p->data; /*取数据*/
Q->front->next=p->next; /*修改队头指针*/
if (Q->rear==p) Q->rear=Q->front;/*若删除结点为队尾结点，
设置为空队列*/
free(p);
return OK;
}
_
main()
{
int i;
ElemType elem;
LinkQueue que; /*定义队列对象que*/
InitQueue(&que); /*队列que初始化*/
EnQueue(&que,1); /*元素1进队列*/
EnQueue(&que,2); /*元素2进队列*/
EnQueue(&que,3); /*元素3进队列*/
DeQueue(&que,&elem); printf("%d",elem); /*1 出队列*/
DeQueue(&que,&elem); printf("%d",elem); /*2 出队列*/
DeQueue(&que,&elem); printf("%d",elem); /*3 出队列*/
DeQueue(&que,&elem); printf("%d",elem);
/*队列已空，由于未检查返回结果，取出的还是3,产生错误*/
}
5．顺序队列
#define MAXQSIZE 100 /*首次分配连续存储单元的大小，可存储MAXQSIZE个元素*/
typedef int ElemType;
typedef struct SqList
{ ElemType *base; /*连续存储单元首地址*/
int front; /*队列头指针，若队列不空，指向队头元素*/
int rear; /*队列尾指针，若队列不空，指向队尾元素的下一个位置*/
} SqQueue; /*SqQueue为结构类型，用其说明的变量在程序中作为队列*/
/**********************************************************
** 功能：初始化队列 **
** 输入：队列对象S的指针 **
** 输出,成功时返回OK **
**********************************************************/
int InitQueue(SqQueue *Q)
{
Q->base=(ElemType *) malloc(MAXQSIZE*sizeof(ElemType));
if (!Q->base) exit(OVERFLOW);
Q->front=Q->rear=0;
return OK;
}
/**********************************************************
** 功能：进队列操作 **
** 输入：队列对象Q的指针，数据元素e **
** 输出,成功时返回OK **
**********************************************************/
int EnQueue(SqQueue *Q,ElemType e)
{
if ((Q->rear+1)%MAXQSIZE==Q->front)
return ERROR;
Q->base[Q->rear]=e;
Q->rear=(Q->rear+1)%MAXQSIZE;
return OK;
}
/*******************************************************************
** 功能：出队操作 **
** 输入：队列对象S的指针 **
** 输出,成功时返回OK、通过数据元素指针e返回队首元素的值 **
** 空队列时返回ＥＲＲＯＲ **
*******************************************************************/
int DeQueue(SqQueue *Q,ElemType *e)
{
if (Q->rear==Q->front)
return ERROR;
*e=Q->base[Q->front];
Q->front=(Q->front+1)%MAXQSIZE;
return OK;
}
main()
{
ElemType *elem;
SqQueue que;
clrscr();
InitQueue(&que);
EnQueue(&que,1); /*元素1进队列*/
EnQueue(&que,2); /*元素2进队列*/
EnQueue(&que,3); /*元素3进队列*/
DeQueue(&que,&elem); printf("%d",elem); /*1 出队列*/
DeQueue(&que,&elem); printf("%d",elem); /*2 出队列*/
DeQueue(&que,&elem); printf("%d",elem); /*3 出队列*/
DeQueue(&que,&elem); printf("%d",elem);
/*队列已空，由于未检查返回结果，取出的还是3,产生错误，
所以应检查返回结果，当返回结果为OK时访问elem才有意义*/
}
6．串将串长作为存储结构的一部分：
typedef struct {
char *ch; //若是非空串，则按串长分配存储区，否则ch为NULL
int length; //串长度
} HString;
/*******************************************************************
** 功能：将串清空 **
** 输入：串对象S的指针 **
** 输出,无 **
*******************************************************************/
void ClearString(HString *S)
/*将S清为空串*/
{
if (S->ch)
{ free(S->ch);
S->ch=NULL;
}
S->length=0;
}
/*******************************************************************
** 功能：字符串赋值操作 **
** 输入：字符串对象指针的T，字符指针表示的C字符串 **
** 输出,成功时返回OK **
*******************************************************************/
int StrAssign(HString *T,char *chars)
/*根据chars表示的串常量产生串T*/
{
char *c; int i;
if (T->ch) free(T->ch); /*释放T原有空间*/
for(i=0,c=chars; *c; i++,++c); /*求chars的串长i*/
if (!i)
{T->ch=NULL;T->length=0;} /*当chars为空串时*/
else {
if (!(T->ch=(char *) malloc(i*sizeof(char))))
return exit(OVERFLOW);
T->length=i;
for(; i>0; i--) /*复制chars串值到串T*/
T->ch[i-1]=chars[i-1];
}
return OK;
}
/*******************************************************************
** 功能：输出字符串 **
** 输入：字符串对象T **
** 输出,无 **
*******************************************************************/
void StrPrint(HString T)
/*显示串T*/
{
int i;
for(i=0;i<T.length;i++)
putchar(T.ch[i]);
}
/*******************************************************************
** 功能：字符串联接,串1+串2=>结果T **
** 输入：结果字符串对象指针的T和字符串对象S1、S2 **
** 输出,成功时返回OK **
*******************************************************************/
int Concat(HString *T,HString S1,HString S2)
/*用Ｔ返回Ｓ１和Ｓ２连接而成的新串*/
{
int i;
if (T->ch) free(T->ch); /*释放T原有空间*/
if (!(T->ch=(char *) malloc((S1.length+S2.length)*sizeof(char))))
exit(OVERFLOW);
for(i=0;i<S1.length;i++) /*复制S1串值到串T*/
T->ch[i]=S1.ch[i];
for(i=0;i<S2.length;i++) /*复制S2串值到串T*/
T->ch[S1.length+i]=S2.ch[i];
T->length=S1.length+S2.length; /*设定Ｔ的长度*/
return OK;
}
main()
{
HString str1={NULL,0},str2={NULL,0},str3={NULL,0}; /*定义串对象str1,str2,str3*/
clrscr();
ClearString(&str1);
StrAssign(&str1,"abcd");
StrAssign(&str2,"1234");
Concat(&str3,str1,str2);
StrPrint(str3);
}
4.2.3串的单链表表示
例 一个结点只放1个字符
struct node1
{ char data； //为一个字符
struct node *next； //为指针
}*ps1；
data next
头指针 首结点 尾结点
存储密度=串值所占存储位/实际分配存储位存储效率太低，存储密度为 0.33
若一个结点放多个字符，可提高存储效率，但算法就会变复杂。
7．二叉树算法综合举例：
#include "stdio.h"
#define leng sizeof(BiTNode) /*结点所占空间的大小*/
typedef int TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
/*******************************************************************
** 功能：利用二叉树的的特性产生二叉树 **
** 输入：算法执行中输入各结点的满二叉树序号值和结点的值 **
** 输出,二叉树根指针 **
*******************************************************************/
#define MAXSIZE 100
BiTree CreatTree()
{
BiTNode *s[MAXSIZE+1],*root,*q;
int i,j;
TElemType x;
printf("i,x="); scanf("%d%d",&i,&x); /*输入结点序号和值*/
while(i!=0)
{
q=(BiTNode *) malloc(sizeof(BiTNode));
q->data=x;q->lchild=q->rchild=NULL;
s[i]=q;
if (i==1) root=q; /*处理根结点*/
else {
j=i/2; /* j 为当前结点的父结点序号*/
if (i%2) s[j]->rchild=q; /*当前结点为其父结点的右孩子*/
else s[j]->lchild=q; /*当前结点为其父结点的左孩子*/
}
printf("i,x="); scanf("%d%d",&i,&x); /*输入结点序号和值*/
}
return root; /*返回二叉树根指针*/
}
/*******************************************************************
** 功能：利用带空二叉树的先序序列生产二叉树 **
** 输入：算法执行中输入带空二叉树的先序序列 **
** 输出,二叉树根指针 **
*******************************************************************/
BiTree CreatBiTree()
{ char ch;
BiTree root;
scanf("%c",&ch); /*输入一个结点，假定为字符型*/
if (ch =='φ') root=NULL;
else
{ root=(BiTree) malloc(leng);
root->data=ch; /*生成根结点 */
root->lchild=CreatBiTree(); /*递归构造左子树 */
root->rchild=CreatBiTree(); /*递归构造右子树 */
}
return root;
}
/*******************************************************************
** 功能：计算二叉树结点数 **
** 输入：二叉树的根结点指针 **
** 输出,结点数数值 **
*******************************************************************/
int count(BiTree root)
{ int n=0 ;
if (root)
{ n=1;
n+=count(root->lchild);
n+=count(root->rchild);
}
return n;
}
/*******************************************************************
** 功能：二叉树的先序遍历操作 **
** 输入：二叉树的根结点指针 **
** 输出,无 **
*******************************************************************/
void PreOrderTraverse(BiTree T)
{
if (T) {
printf("%d",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
/*******************************************************************
** 功能：二叉树的中序遍历操作 **
** 输入：二叉树的根结点指针 **
** 输出,无 **
*******************************************************************/
void MidOrderTraverse(BiTree T)
{
if (T) {
MidOrderTraverse(T->lchild);
printf("%d",T->data);
MidOrderTraverse(T->rchild);
}
}
/*******************************************************************
** 功能：二叉排序树的生成 **
** 输入：二叉排序树的根结点指针，新结点数据 **
** 输出：二叉排序树的根结点指针 **
*******************************************************************/
BiTree intree(BiTree t,TElemType x)
{ if (t==NULL) /*t是指向二叉树根指针的指针*/
{ t=(BiTree) malloc(sizeof(BiTNode));
t->data=x; /*生成并插入结点x*/
t->lchild=t->rchild=NULL; /*为叶子结点*/
}
else if(x<t->data)
t->lchild=intree(t->lchild,x);
else t->rchild=intree(t->rchild,x);
return t;
}
main()
{
int i;
BiTree tree1,tree2;
clrscr();
tree1=CreatTree();
tree2= CreatBiTree()
printf(“第一棵树的先序序列：”);
PreOrderTraverse(tree1);
printf(" 结点数=%d",count(tree1));
printf(“第二棵树的先序序列：”);
PreOrderTraverse(tree2);
printf(" 结点数=%d",count(tree2));
printf(“输入二叉排序树的数据：”);
scanf("%d",&i);
while (i)
{
tree=intree(tree,i);
scanf("%d",&i);
}
printf(“二叉排序树的先序序列：”);
PreOrderTraverse(tree);putchar('\n');
printf(“二叉排序树的中序序列：”);
MidOrderTraverse(tree);
}
