顺序栈 /*静态分配栈空间,大小固定,不能扩充* #define TRUe #define FALSE 0 #define OK #define Error 0 #define maxleng 10 typedef int Elem Type Elem Type elem maxleng+1]/*栈元素空间* Int top, /*顶指针* qStack 称水称水水布幸本涂水水水水水客容布称水水客水水水涂水涂水水客水水水客水*水水客水客*水涂水本客水 SqStack为结构类型 例: SqStack s:说明s为结构类型变量,可表示一个栈 其中:stop-顶指针;sclm[stop-顶元素 未用元素 selem *客水水本客水客水*客*常水*客水凇客 幸幸幸幸幸*亲幸*幸**亲幸幸*幸/ 功能:测试栈是否为空 *输入:栈对象 *输出:空时返回TRUE,非空时返回 FALSE 水客客*客常 本*本*亲本本*亲*本亭******本本****幸***率***幸*/ int StackEmpty(sqStack S) eturn trUe return False. *水****客****客*水**客****客**水客*客客*幸*客水**水**客**客 功能:进栈操作 输入:栈对象S的指针,数据元素e 输出:成功时返回OK 水水*水**客水**客水*称水水水*幸***水客水*客水*客*水客水*幸*客水水客水**客 int Push(sqstack "S, Elem Type e Int f(S->top== maxing)/*栈溢出*
顺序栈 /* 静态分配栈空间，大小固定，不能扩充*/ #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 o 客水客水*水水水**水*水*称水客客*客水水容*客水*水水布**客水涂水客*水水客水*水*水水市**客水*称水水*客水客幸 **功能:退栈操作 输入:栈对象S的指针 输出:成功时返回OK、通过数据元素指针e返回栈顶元素的值* 空栈时返回 ERROR int Pop(sqstack"S, Elem Type 'e) if( Stack Empty(*S) return ErROR,/*空栈失败返回* e=S-elem[S->top]/*取栈顶元素* S->top=S->top-l;/栈顶减1* return OK. /成功返回* ma int 1; Elem Type elem Sqstacks *定义栈对象s* 初始化栈对象s* SCI for(i=1;i<=5,i++)/*输入5个数据元素并进栈 scanf("%d", &elem) Push(&s, elem) }; for(i=1;i<=7,i++)/退栈操作* f(Pop(&s&elem)=OK)/*正确退栈时,可通过elem输出数据元素* printf("No%d=%d ", i, elem) else/*若栈已空,结束,此时elem的值无意义,* i printf("stack has been empty! ") break
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)存放元素的结点类型 def int elem typedef struct Qnode I ElemType data struct QNode 半next 1 QNode, *QueuePtr /*可理解为定义两个类型: 链式队列结点的结构类型; Queue 链式队列结点指针类型,指向链式队列结点 */ (2)由头、尾指针组成的结点类型 QueuePtr front;/*队头指针* QueuePtr rear;/*队尾指针*/ I LinkQueue /*结构类型 LinkQueue的变量为队列对象*/ 客涂水客水水客水凇客*水*水*客水客涂客水水凇客*客水*水亦水常客水客水客 索功能:初始化队列 输入:队列对象S的指针 输出:成功时返回OK 水水常称*客水客水本水客本亦水常水客水农称水客水客涂*本水*客水客水常水*客客水涂水客*客客水 nt InitQueue(LinkQueue *Q Q->front=Q->rear=(QueuePtr) malloc(sizeof (QNode)) if(Q->front=NULL) return ERROR Q->front->nex t=NULL 涂*水客水水客客水 功能:测试队列是否为空 输入:队列对象Q 输出:空时返回TRUE,非空时返回 FALSE 幸幸*幸幸本幸李幸幸幸幸幸 int QueueEmpty(LinkQueue Q) if (Q. front==Q rear) return TRUE
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;
功能:进队列操作 输入:队列对象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=NUL;/*新结点赋值*/ return OK /*本*****幸本幸本*率本***幸*幸布春*幸本**率本幸率布容春***** 六功能:出队操作 输入:队列对象S的指针 索输出:成功时返回OK、通过数据元素指针e返回队首元素的值 空队列时返回 ERROR 客水常水凇客*水水客本客*本水水水水水水凇称水水容水凇*本客水本客容水市客宗 nt DeQueue( Link Queue*Q, ElemType*e)/*出队列*/ QueuePtr p if( QueueEmpty(*Q)) return error;/*空队列,返回错误*/ p=Q- front→>next; /*p指向删除结点*/ >data /*取数据* Q-> front->next=p->next;/*修改队头指针*/ f(Q->rear=p)Q-rear=Q> front;/*若删除结点为队尾结点 设置为空队列*/ free retur maino int 1 ElemType el LinkQ *定义队列对象que*/ InitQueue(&que) /*队列que初始化*/ /*元素1进队列*/
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 MAXQSIzE100/*首次分配连续存储单元的大小,可存储 MAXQS IZE个元素*/ typedef int elemType typedef struct Sqlist ElemType*base;/*连续存储单元首地址*/ int front /*队列头指针,若队列不空,指向队头元素*/ int rear /*队列尾指针,若队列不空,指向队尾元素的下一个位置*/ /* SqQueue为结构类型,用其说明的变量在程序中作为队列*/ 水客水**水容水常水水水本客水凇水凇水水客水水布客水*客水 功能:初始化队列 输入:队列对象S的指针 输出:成功时返回OK *亲*亲**亲**亲*亲**家本亲*****幸幸**幸*/ int InitQueuesqQueue *Q) Q->base=(Elem Type *)malloc( MAXQSIZE*sizeof (ElemType)) if (!Q->base) exit(OVERFLOW) Q->front=Q->rear=0 return oK **水客水容***水客水*涂水客水*客**客客水***水常客水涂水*水水***水*水*客**水常客水幸客 功能:进队列操作 输入:队列对象Q的指针,数据元素e 输出:成功时返回OK nt EnQueue(SqQueue *Q, Elem Type e) if ((Q->rear+1)%MAXQS IZE==Q->front) return error
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] Q->rear=(Q->rear+1)%MAXQSIZE return OK 功能:出队操作 输入:队列对象S的指针 输出:成功时返回OK、通过数据元素指针e返回队首元素的值 空队列时返回 ERROF 幸称水客水 水水本 int DeQueue (SqQueue * Q, Elem Type *e) if(Q->rear==Q->front return error *e=Q->base[Q->front] Q->front=(Q->front +1)%MAXQSIZE return maino ElemType *elem InitQueue(&que) End (&que,1) /*元素1进队列*/ EnQueue(&que,2);/*元素2进队列*/ EnQueue(&que, 3) /*元素3进队列*/ DeQueue(&que,&elem); printf("%d",elem);/*1出队列*/ DeQueue(&que,&elem); printf("%d",eem);/*2出队列*/ DeQueue(&que, &elem): printf (%d", elem) 队列*/ DeQueue(&que, &elem): printf("%d", elem) /*队列已空,由于未检查返回结果,取出的还是3,产生错误, 所以应检查返回结果,当返回结果为0K时访问elem才有意义*/
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 i char*ch;∥若是非空串,则按串长分配存储区,否则ch为NULL int length,∥串长度 /********率*本本***容率*******率**幸 ★功能:将串清空 输入:串对象S的指针 输出:无 水常称凇客水客水凇涂客水凇本水常水*布水涂水涂水称水水涂水水凇水客客本涂*水客水客水客水水水*客水 void Clear String(HString*S) /*将S清为空串* if(S->ch) f free(s->ch) /*本*****幸本幸本*率本***幸*幸布春*幸本**率本幸率布容春***** 功能:字符串赋值操作 输入:字符串对象指针的T,字符指针表示的C字符串 输出:成功时返回 int Str Assign(HString *T, char *chars) /*根据 chars表示的串常量产生串T*/ if(T->ch) free(T->ch); /*释放T原有空间 ++c),/*求 chars的串长i*/ if( i s、 T->ch=NULL; T->length=0,“当chs为空时 if(!(T-ch=(char*)malloc(i*sizeof(char))) return exit(OVERFLOW) for( i>0; 1--) /*复制 chars串值到串T*/ T->ch(i-1=chars(i-1;
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*/ for(i=0; i结果T 输入:结果字符串对象指针的T和字符串对象Sl、S2 输出:成功时返回OK int Concat( HString*T, HString Sl, HString $2) /*用T返回S1和S2连接而成的新串* Int f(T>ch)free(T>ch);/*释放T原有空间 if(T->ch=(char *)malloc((S1. length+S2. length) *sizeof(char)))) exit(OVERFLOW) for(i=0,ichi=SI.chi] for(i=0;ich(S1. length+i=S2. ch i T> length= Length+S2 length,/*设定T的长度* return oK maino HString str l=NULL,0},st2={NULL0},str3={NUL0};体定义串对象st1,st2,st3* lascr Clear String(&str1) StrAssign(&strl, " abcd"); StrAssign(&str2, 1234)
} return OK; } /******************************************************************* ** 功能：输出字符串 ** ** 输入：字符串对象 T ** ** 输出： 无 ** *******************************************************************/ void StrPrint(HString T) /*显示串 T*/ { int i; for(i=0;i结果 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;ich[i]=S1.ch[i]; for(i=0;ich[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, str l, str 2) StrPrint(str3) 423串的单链表表示 例一个结点只放1个字符 struct nodel i char data; ∥.一个字符 struct node*next:∥为指针 存储密度=串值所占存储位/实际分配存储位 存储效率太低,存储密度为033 若一个结点放多个字符,可提高存储效率,但算法就会变复杂
Concat(&str3,str1,str2); StrPrint(str3); } 4.2.3 串的单链表表示 例 一个结点只放 1 个字符 struct node1 { char data； //为一个字符 struct node *next； //为指针 }*ps1； data next 头指针 首结点 尾结点 存储密度=串值所占存储位/实际分配存储位 存储效率太低，存储密度为 0.33 若一个结点放多个字符，可提高存储效率，但算法就会变复杂。 data next ps1 A B C D
7.二叉树算法综合举例 # define leng sizeof( BiNOde)/结点所占空间的大小 typedef int TElemType typedef struct BiTNode TElem Type struct biNOde *Child.*rchild BiTNode.* BiTree 本涂本客客水水*水客幸客客宗本水本客水客水客水*水水凇客幸客 功能:利用二叉树的的特性产生二叉树 输入:算法执行中输入各结点的满二叉树序号值和结点的值 输出:二叉树根指针 #define MAXSIze 100 BiTree Creat tre BiTNode *s(MAXSIZE+ll, root, q: TElem Type x printf("ix="), scant("%d%od"ki,&x)/*输入结点序号和值* while(il=0) q=(BiTNode *)malloc(sizeof( BiTNode)) s[]=q if(i=1)root=q;,/处理根结点* else i j=i2;,/j为当前结点的父结点序号* f(%2)si]-> rchild=q,/*当前结点为其父结点的右孩子* else }-> lchild=q,当前结点为其父结点的左孩子* printf("i,x="), scanf("%d%d",&i,&x),/*输入结点序号和值*/ return root,/*返回二叉树根指针* 功能:利用带空二叉树的先序序列生产二叉树 六输入:算法执行中输入带空二叉树的先序序列
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; /*返回二叉树根指针*/ } /******************************************************************* ** 功能：利用带空二叉树的先序序列生产二叉树 ** ** 输入：算法执行中输入带空二叉树的先序序列 **
