元素所占空间和表长合并为C语言的一个结构类型：
#define maxleng 100
typedef struct
{ ElemType elem[maxleng]；//下标:0,1,...,maxleng-1
int length； //表长
} SqList；
SqList La；
其中：typedef---别名定义，SqList----结构类型名
La----结构类型变量名
La.length---表长
La.elem[0]----a1
La.elem[La.length-1]---an
算法举例：
#include "stdio.h"
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef int ElemType; /*假定数据元素为int*/
#define maxlen 100 /*线性表最大容量*/
typedef struct
{ ElemType elem[maxlen]；/*连续存储单元*/
int length； /*线性表长度*/
} SqList； /*SqList为结构类型，用其说明的变量在程序中作为线性表*/
/**********************************************************
** 功能：线性表插入操作，将某数据元素插入到线性表 **
** 的第i个数据元素之前 **
** 输入：线性表指针L、位置i、待插入的数据元素e **
** 输出,成功时返回OK **
**********************************************************/
int insert_sq(SqList *L,int i,ElemType e)
{
int j;
if (i<1 || i>L->length+1) return ERROR; /*i的合法取值为1至n+1*/
if (L->length>=maxlen) /*溢出*/
{printf(“超过线性表最大容量”);
return ERROR;
}
for(j=L->length-1;j>=i-1;j--) /*向后移动元素，空出第i个元素的分量elem[i-1]*/
L->elem[j+1]=L->elem[j];
L->elem[i-1]=e; /*新元素插入*/
L->length++; /*线性表长度加1*/
return OK;
}
/**********************************************************
** 功能：线性表删除操作，删除线性表的第i个数据元素 **
** 输入：线性表指针L、位置i **
** 输出,成功时返回OK **
**********************************************************/
int delete_sq(SqList *L,int i)
{
int j;
if (i<1 || i>L->length) return ERROR;
for(j=i;j<L->length;j++) /*向前移动元素*/
L->elem[j-1]=L->elem[j];
L->length--; /*线性表长度减1*/
return OK;
}
/**********************************************************
** 功能：显示线性表的所有数据元素 **
** 输入：线性表L **
** 输出,无 **
**********************************************************/
void display(SqList L)
{
int i;
for (i=0;i<L.length;i++)
printf("\na[%d]=%d",i+1,L.elem[i]);
}
main()
{
SqList La;
clrscr();
La.length=0; /*初始化线性表La,表长度设置为0*/
insert_sq(&La,1,1); /*数据元素１插入到线性表La的第１个数据元素之前*/
insert_sq(&La,1,2); /*数据元素2插入到线性表La的第１个数据元素之前*/
insert_sq(&La,1,3); /*数据元素3插入到线性表La的第１个数据元素之前*/
insert_sq(&La,4,5); /*数据元素5插入到线性表La的第4个数据元素之前*/
delete_sq(&La,1); /*删除线性表La的第１个数据元素*/
display(La) /*显示线性表La的数据元素*/;
}
2 单链表算法举例（带表头结点的单链表）：
typedef int ElemType;
typedef struct LNode
{ ElemType data;
struct LNode *next;
} LNode,*LinkList;
/*可理解为定义两个类型:
LNode ----- 结构类型;
LinkList ----- 结点指针类型，指向结点,
由于头指针是结点指针，所以该类型变量可定义为链表
LNode *p 等价于 LinkList p */
/****************************************************
** 功能：初始化单链表，产生头结点 **
** 输入：无 **
** 输出,成功时返回头结点指针 **
****************************************************/
LinkList ListInit()
{
LNode *s;
s=(LinkList) malloc(sizeof(LNode)); /*产生头结点*/
s->data=0;s->next=NULL;
return s; /*返回头结点指针*/
}
/**********************************************************
** 功能：线性表插入操作，将某数据元素插入到单链表 **
** 的第i个数据元素之前 **
** 输入：单链表的头指针L、位置i、待插入的数据元素e **
** 输出,成功时返回OK **
**********************************************************/
int ListInsert(LinkList L,int i,ElemType e)
{
LNode *p,*s; int j;
p=(LNode *) L; /*p 指向链表头结点*/
j=0;
while (p && j<i-1)
{p=p->next;++j;} /* 执行 i-1 次定位第 i-1个结点 */
if (!p || j>i-1) return ERROR; /*p 为NULL时表示没有第 i-1个结点
j>i-1 表示 i<=0 时插入序号错*/
s=(LinkList) malloc(sizeof(LNode));
s->data=e;
s->next=p->next;p->next=s; /*s所指新结点插入p所指第i-1个结点之后*/
return OK;
}
/**********************************************************
** 功能：线性表删除操作，删除单链表的第i个结点 **
** 输入：单链表的头指针L、位置i **
** 输出,成功时返回OK **
**********************************************************/
int ListDelete(LinkList L,int i)
{
LNode *p,*q; int j;
p=(LNode *) L; /*p 指向链表头结点*/
j=0;
while (p->next && j<i-1)
{p=p->next;++j;} /* 执行 i-1 次，使p定位第 i-1个结点 */
p->next 指向结点第i个结点,search for ith node*/
if (!(p->next)||j>i-1) return ERROR;
q=p->next;p->next=q->next;
free(q);
return OK;
}
/**********************************************************
** 功能：读取线性表第i个结点的值 **
** 输入：单链表的头指针L、位置i **
** 输出,成功时返回OK、通过指针e返回第i个结点的值 **
** 失败返回ＥＲＲＯＲ **
**********************************************************/
int GetElem(LinkList L,int i,ElemType *e)
{
LNode *p,*s; int j;
p=(LNode *) L->next; /*p 指向链表第1个结点*/
j=1;
while (p && j<i)
{p=p->next;++j;} /* 执行 i-1 次，使p定位第 i个结点 */
if (!p||j>i) return ERROR;
*e=p->data;
return OK;
}
/**********************************************************
** 功能：显示单链表表示的线性表的所有数据元素 **
** 输入：线性表L **
** 输出,无 **
**********************************************************/
void display(LinkList L)
{
LNode *p;
p=L->next;
while (p)
{
printf("\n%d",p->data);
p=p->next;
}
}
main()
{
LinkList La,Lb; /*only define head pointer,no head node*/
int a;
clrscr();
La=ListInit();
Lb=ListInit();
ListInsert(La,1,7);
ListInsert(La,2,9);
ListInsert(La,3,6);
ListInsert(La,3,12);
ListDelete(La,1);
GetElem(La,3,&a);
printf("a=%d",a);
display(La);
}
3,顺序栈
/* 静态分配栈空间，大小固定，不能扩充*/
#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 maxleng 100
typedef struct
{ ElemType elem[maxleng]；//下标:0,1,...,maxleng-1
int length； //表长
} SqList；
SqList La；
其中：typedef---别名定义，SqList----结构类型名
La----结构类型变量名
La.length---表长
La.elem[0]----a1
La.elem[La.length-1]---an
算法举例：
#include "stdio.h"
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef int ElemType; /*假定数据元素为int*/
#define maxlen 100 /*线性表最大容量*/
typedef struct
{ ElemType elem[maxlen]；/*连续存储单元*/
int length； /*线性表长度*/
} SqList； /*SqList为结构类型，用其说明的变量在程序中作为线性表*/
/**********************************************************
** 功能：线性表插入操作，将某数据元素插入到线性表 **
** 的第i个数据元素之前 **
** 输入：线性表指针L、位置i、待插入的数据元素e **
** 输出,成功时返回OK **
**********************************************************/
int insert_sq(SqList *L,int i,ElemType e)
{
int j;
if (i<1 || i>L->length+1) return ERROR; /*i的合法取值为1至n+1*/
if (L->length>=maxlen) /*溢出*/
{printf(“超过线性表最大容量”);
return ERROR;
}
for(j=L->length-1;j>=i-1;j--) /*向后移动元素，空出第i个元素的分量elem[i-1]*/
L->elem[j+1]=L->elem[j];
L->elem[i-1]=e; /*新元素插入*/
L->length++; /*线性表长度加1*/
return OK;
}
/**********************************************************
** 功能：线性表删除操作，删除线性表的第i个数据元素 **
** 输入：线性表指针L、位置i **
** 输出,成功时返回OK **
**********************************************************/
int delete_sq(SqList *L,int i)
{
int j;
if (i<1 || i>L->length) return ERROR;
for(j=i;j<L->length;j++) /*向前移动元素*/
L->elem[j-1]=L->elem[j];
L->length--; /*线性表长度减1*/
return OK;
}
/**********************************************************
** 功能：显示线性表的所有数据元素 **
** 输入：线性表L **
** 输出,无 **
**********************************************************/
void display(SqList L)
{
int i;
for (i=0;i<L.length;i++)
printf("\na[%d]=%d",i+1,L.elem[i]);
}
main()
{
SqList La;
clrscr();
La.length=0; /*初始化线性表La,表长度设置为0*/
insert_sq(&La,1,1); /*数据元素１插入到线性表La的第１个数据元素之前*/
insert_sq(&La,1,2); /*数据元素2插入到线性表La的第１个数据元素之前*/
insert_sq(&La,1,3); /*数据元素3插入到线性表La的第１个数据元素之前*/
insert_sq(&La,4,5); /*数据元素5插入到线性表La的第4个数据元素之前*/
delete_sq(&La,1); /*删除线性表La的第１个数据元素*/
display(La) /*显示线性表La的数据元素*/;
}
2 单链表算法举例（带表头结点的单链表）：
typedef int ElemType;
typedef struct LNode
{ ElemType data;
struct LNode *next;
} LNode,*LinkList;
/*可理解为定义两个类型:
LNode ----- 结构类型;
LinkList ----- 结点指针类型，指向结点,
由于头指针是结点指针，所以该类型变量可定义为链表
LNode *p 等价于 LinkList p */
/****************************************************
** 功能：初始化单链表，产生头结点 **
** 输入：无 **
** 输出,成功时返回头结点指针 **
****************************************************/
LinkList ListInit()
{
LNode *s;
s=(LinkList) malloc(sizeof(LNode)); /*产生头结点*/
s->data=0;s->next=NULL;
return s; /*返回头结点指针*/
}
/**********************************************************
** 功能：线性表插入操作，将某数据元素插入到单链表 **
** 的第i个数据元素之前 **
** 输入：单链表的头指针L、位置i、待插入的数据元素e **
** 输出,成功时返回OK **
**********************************************************/
int ListInsert(LinkList L,int i,ElemType e)
{
LNode *p,*s; int j;
p=(LNode *) L; /*p 指向链表头结点*/
j=0;
while (p && j<i-1)
{p=p->next;++j;} /* 执行 i-1 次定位第 i-1个结点 */
if (!p || j>i-1) return ERROR; /*p 为NULL时表示没有第 i-1个结点
j>i-1 表示 i<=0 时插入序号错*/
s=(LinkList) malloc(sizeof(LNode));
s->data=e;
s->next=p->next;p->next=s; /*s所指新结点插入p所指第i-1个结点之后*/
return OK;
}
/**********************************************************
** 功能：线性表删除操作，删除单链表的第i个结点 **
** 输入：单链表的头指针L、位置i **
** 输出,成功时返回OK **
**********************************************************/
int ListDelete(LinkList L,int i)
{
LNode *p,*q; int j;
p=(LNode *) L; /*p 指向链表头结点*/
j=0;
while (p->next && j<i-1)
{p=p->next;++j;} /* 执行 i-1 次，使p定位第 i-1个结点 */
p->next 指向结点第i个结点,search for ith node*/
if (!(p->next)||j>i-1) return ERROR;
q=p->next;p->next=q->next;
free(q);
return OK;
}
/**********************************************************
** 功能：读取线性表第i个结点的值 **
** 输入：单链表的头指针L、位置i **
** 输出,成功时返回OK、通过指针e返回第i个结点的值 **
** 失败返回ＥＲＲＯＲ **
**********************************************************/
int GetElem(LinkList L,int i,ElemType *e)
{
LNode *p,*s; int j;
p=(LNode *) L->next; /*p 指向链表第1个结点*/
j=1;
while (p && j<i)
{p=p->next;++j;} /* 执行 i-1 次，使p定位第 i个结点 */
if (!p||j>i) return ERROR;
*e=p->data;
return OK;
}
/**********************************************************
** 功能：显示单链表表示的线性表的所有数据元素 **
** 输入：线性表L **
** 输出,无 **
**********************************************************/
void display(LinkList L)
{
LNode *p;
p=L->next;
while (p)
{
printf("\n%d",p->data);
p=p->next;
}
}
main()
{
LinkList La,Lb; /*only define head pointer,no head node*/
int a;
clrscr();
La=ListInit();
Lb=ListInit();
ListInsert(La,1,7);
ListInsert(La,2,9);
ListInsert(La,3,6);
ListInsert(La,3,12);
ListDelete(La,1);
GetElem(La,3,&a);
printf("a=%d",a);
display(La);
}
3,顺序栈
/* 静态分配栈空间，大小固定，不能扩充*/
#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);
}
