第一章　绪论

三元组的实现

c1.h　万能头文件

#include<string.h>
#include<ctype.h>
#include<malloc.h>
#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
#include<io.h>
#include<math.h>
#include<process.h>
#include<iostream>
using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1

typedef int Status;//函数返回类型
typedef int Boolean;//布尔类型
typedef int ElemType;

c1-1.h

typedef ELemType *Tripelet;

bo1-1.cpp

#include "c1.h"
#include "c1-1.h"

Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3)
{
    if(!(T=(ElemType *)malloc(3*sizeof(ElemType))))
        exit(OVERFLOW);
    T[0]=v1,T[1]=v2,T[2]=v3;
    return OK;
}
Status DestroyTriplet(Triplet &T)
{
    free(T);
    T=NULL;
    return OK;
}
Status Get(Triplet T,ElemType &e,int i)
{
    if(i<1||i>2)
        return ERROR;
    e=T[i-1];
    return OK;
}
Status Put(Triplet &T,ElemType e,int i)
{
    if(i<1||i>2)
        return ERROR;
    T[i-1]=e;
    return OK;
}
Status IsAscending(Triplet T)
{
    return T[0]<T[1]&&T[1]<T[2];
}
Status IsDecending(Triplet T)
{
    return T[0]>T[1]&&T[1]>T[2];
}
Status Max(Triplet T,ElemType &e)
{
    e=T[0]>T[1]?T[0]>T[2]?T[0]:T[2]:T[1]>T[2]?T[1]:T[2];
    return OK;
}
Status Min(Triplet T,ElemType &e)
{
    e=T[0]<T[1]?T[0]<T[2]?T[0]:T[2]:T[1]<T[2]?T[1]:T[2];
    return OK;
}

main1-1.cpp(可对照上面的函数文件自行修改)

#include"c1.h"
#include"c1-1.h"
#include"bo1-1.cpp"

int main()
{
    Triplet T;
    ElemType m;
    Status i;
    i=InitTriplet(T,5,7,9);
    printf("调用初始化函数后，i=%d(1:成功) T的3个值为",i);
    cout<<T[0]<<' '<<T[1]<<' '<<T[2]<<endl;
    int j=2;
    i=Get(T,j,m);
    if(i==OK)
    {
        cout<<"T的第二个值为"<<m<<endl;
    }
    i=Put(T,2,6);
    if(i==OK)
        cout<<"将T的第2个值改为6后，T的3个值为 "<<T[0]<<' '<<T[1]<<' '<<T[2]<<endl;
    i=IsAscending(T);
    printf("调用升序函数后，是否成功？ %d\n",i);
    i=IsDecending(T);
    printf("是否为降序？%d\n",i);
    j=Max(T,m);
    printf("最大值为：%d\n",m);
    j=Min(T,m);
    printf("最小值为：%d\n",m);
    i=DestroyTriplet(T);
    if(i)
        printf("成功销毁");
    else
    {
        printf("未能成功销毁");
    }
    return 0;
}

区分引用类型和非引用类型（注：必须保存为c++后缀即：.cpp）

algo1-3.cpp

#include<stdio.h>
void fa(int a)
{
	a++;
	printf("在函数fa中：a=%d\n",a);
}
void fb(int &a)
{
	a++;
	printf("在函数fb中：a=%d\n",a);
}
int main()
{
	int n=1;
	printf("在主程序中，调用函数fa之前：n=%d\n",n);
	fa(n);
	printf("在主程序中，调用函数fa之后，fb之前：n=%d\n",n);
	fb(n);
	printf("在主程序中，调用函数fb之后：n=%d\n",n);
	return 0;
}

exit的作用

algo1-4.cpp

#include"c1.h"

int a(int i)
{
    if(i==1)
    {
        printf("退出程序的运行\n");
        exit(0);//里面的值0代表正常退出运行，值为1则代表异常退出运行
    }
    return i;
}

int main()
{
    int i;
    printf("请输入i: ");
    scanf("%d",&i);
    printf("a(i)=%d\n",a(i));
    return 0;
}

记录程序运行时间

一般的方法是使用time.h头文件中的clock()函数

#include<stdio.h>
#include<time.h>
int main()
{
    clock_t begin,end;
    begin = clock();
    for(int i=0;i<1000000000;++i);//可替换为待检测的程序
    end = clock();
    printf("%lf",(double)(end-begin)/CLOCKS_PER_SEC);
    return 0;
}

另一种方法是调用sys/timb.h头文件

#include<stdio.h>
#include<sys/timeb.h>
int main()
{
    timeb t1,t2;
    long t;
   
    ftime(&t1);
    for(int i=1;i<1000000000;++i);
    ftime(&t2);
    t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm);
    printf("用时%ld毫秒\n",t);
    return 0;
}

增加两种时间表达方式 ( 转载 )

#include<iostream>
#include<Windows.h>
 
using namespace std;
int main()
{
	long begin=GetTickCount();
	for(int i=0;i<1000000000;i++);
	long end=GetTickCount();
 
	cout<<begin-start<<endl;
	return 0;
 }

#include<stdio.h>
#include <windows.h>
int main() {
	double run_time;
	_LARGE_INTEGER time_start;	//开始时间
	_LARGE_INTEGER time_over;	//结束时间
	double dqFreq;		//计时器频率
	LARGE_INTEGER f;	//计时器频率
	QueryPerformanceFrequency(&f);
	dqFreq=(double)f.QuadPart;
	QueryPerformanceCounter(&time_start);	//计时开始
	for(int i = 1; i <= 100000000; i++);	//要计时的程序
	QueryPerformanceCounter(&time_over);	//计时结束
	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
	//乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
	printf("\nrun_time：%fus\n",run_time);
	return 0;
}

第二章　线性表

顺序表

c2-1.h 线性表动态分配顺序结构

#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 2

#ifndef _TEST_H_ 
#define _TEST_H_ 
struct SqList{
    ElemType *elem;
    int length;
    int listsize;
};
#endif

bo2-1.cpp 顺序表的操作

#include "c2-1.h"
#include "c1.h"

void InitList(SqList &L){
    L.elem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);
    if(!L.elem)
        exit(OVERFLOW);
    L.listsize=LIST_INIT_SIZE;
    L.length=0;
}

void DestroyList(SqList &L){
    free(L.elem);
    L.elem=NULL;
    L.length=0;
    L.listsize=0;
}

void ClearList(SqList &L){
    L.length=0;
}

Status ListEmpty(SqList L)
{
    return L.length==0;
}

Status ListLength(SqList L,int &len)
{
    return L.length;
}

Boolean ListInsert(SqList &L,int i,int e)
{
    ElemType *newbase,*q,*p;
    if(i<1&&i>L.length+1)
        exit(OVERFLOW);
    if(L.length>=L.listsize)
    {
        if(!(newbase=(ElemType*)realloc(L.elem,(sizeof(ElemType))*(L.listsize+LIST_INCREMENT))))
            exit(OVERFLOW);
    L.elem=newbase;
    L.listsize=L.listsize+LIST_INCREMENT;
    }
    q=L.elem+i-1;
    for(p=L.elem+L.length-1;p>=q;--p)
    {
        *(p+1)=*p;
    }
    *q=e;
    ++L.length;
    return OK;
}

Status ListDelete(SqList &L,int i,int &e)
{
    ElemType *p,*q;
    if(i<1||i>L.length)
        return ERROR;
    e=*(L.elem+i-1);
    for(int j=i;j<L.length;++j)
    {
        *(L.elem+j-1)=*(L.elem+j);
    }
    --L.length;
    return OK;
}

Boolean GetElem(SqList L,int i,ElemType &e)
{
    if((e=*(L.elem+i-1)))
        return OK;
    else
    {
        return FALSE;
    }
}

Status LocateElem(SqList L,int &i,ElemType e)
{
    ElemType *p=L.elem;
    i=0;
    while(*p!=e)
    {
        ++i;
        ++p;
    } 
    if(*p==e&&i<=L.length)
        return OK;
    else
        return ERROR;
}

Status PriorElem(SqList L,int i,int &e)
{
    if((e=*(L.elem+i-2)))
        return OK;
    else
    {
        return ERROR;
    }
    
}

Status NextElem(SqList L,int i,int &e)
{
    if((e=*(L.elem+i)))
        return OK;
    else return ERROR;
}

void ListTraverse(SqList L,void (*vi)(ElemType &))
{
    ElemType *p;
    int i;
    p=L.elem;
    for(i=0;i<L.length;++i)
    {
        vi(*p++);
    }
    printf("\n");
}

main2-1.cpp (可对照上面的函数文件自行修改)

#include "c1.h"//注意：需要调用第一章的代码
#include "c2-1.h"
#include "bo2-1.cpp"

void print(ElemType &p)
{
    printf("%d",p);
}

int main()
{
    SqList L;
    ElemType e,e0;
    Status i;
    int j,k;
    InitList(L);
    printf("初始化后：L.elem=%u L.length=%d L.listsize=%d\n",L.elem,L.length,L.listsize);
    for(j=1;j<=5;++j)
        i=ListInsert(L,1,j);
    for(j=1;j<=5;++j)
        cout<<*(L.elem+j-1)<<" ";
    cout<<endl;
    printf("变化后：L.elem=%u L.length=%d L.listsize=%d\n",L.elem,L.length,L.listsize);
    DestroyList(L);
    printf("变化后：L.elem=%u L.length=%d L.listsize=%d\n",L.elem,L.length,L.listsize);
    i=ListEmpty(L);
    printf("L是否为空 0 空 、1 非空 i= %d\n",i);
    InitList(L);
    for(j=1;j<=10;++j)
    {
        ListInsert(L,j,j);
    }
    printf("在L的表头插入1-10后：\n");
    for(j=1;j<=10;++j)
    {
        cout<<*(L.elem+j-1);
    }
    cout<<endl;
    GetElem(L,5,e);
    printf("第五个元素为：%d\n",e);
    for(j=0;j<10;++j)
    {
        k=LocateElem(L,i,j);
        if(k)
            printf("值为%d的元素位于第%d个\n",j,k);
        else
        {
            printf("未找到%d\n",k);
        }
        if(j>1)
        {
            PriorElem(L,j,e);
            printf("值为%d的元素前驱为%d\n",j,e);
        }
        if(j<L.length)
        {
            NextElem(L,j,e);
            printf("值为%d的元素后继为%d\n",j,e);
        }
    }
    ListDelete(L,5,e);
    ListTraverse(L,print);

    printf("被删除的元素为：%d\n",e);


    DestroyList(L);

}

algo2-2.cpp 独立实现，没有用bo2-1.cpp

#include"c1.h"
#include"c2-1.h"

typedef int Scale;

void initList(SqList &L,Scale i)
{
    L.elem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE*i);
    if(!L.elem)
        exit(OVERFLOW);
    L.listsize=LIST_INIT_SIZE*i;
    L.length=0;
}

void MergeList(SqList La,SqList Lb,SqList &Lc)
{
    ElemType *p=La.elem,*q=Lb.elem,*s=Lc.elem;
    Lc.length=La.length+Lb.length;
    int i=0,j=0;
    while(p&&q&&i<La.length&&j<Lb.length)
    {
        
        if(*p<*q)
        {
            *s=*p;
            ++s;
            ++p;
            ++i;
        }
        else if(*p>*q)
        {
            *s=*q;
            ++s;
            ++q;
            ++j;
        }
        else
        {
            *s=*p;
            *(s+1)=*q;
            s+=2;
            ++p;
            ++q;
            ++i;
            ++j;
        }
    }
    if(i<La.length)
    {
        while(i<La.length)
        {
            *s=*p;
            ++s;
            ++p;
            ++i;
        }
    }
    else if(j<Lb.length)
    {
        while(j<Lb.length)
        {
            *s=*q;
            ++s;
            ++q;
            ++j;
        }
    }
}

void PrintList(SqList Lc)
{
    ElemType *p=Lc.elem;
    int j=0;
    while(j<Lc.length)
    {
        printf("%d",*p);
        ++p;
        ++j;
    }
}

void inputList(SqList &L)
{
    ElemType *q=L.elem;
    int i,n;
    printf("Please input num of List: ");
    scanf("%d",&n);
    if(n>L.listsize)
        exit(OVERFLOW);
    for(i=0;i<n;++i)
    {
        scanf("%d",&(*q));
        ++q;
    }
    L.length=n;
}

int main()
{
    SqList La,Lb,Lc;
    initList(La,1);
    initList(Lb,1);
    initList(Lc,2);
    inputList(La);
    inputList(Lb);
    
    MergeList(La,Lb,Lc);
    PrintList(Lc);
    return 0;
}

链表

func2-3 打印比较这类函数（单独写出，无它，为了结构化规范）

Status equal(ElemType c1,ElemType c2)
{
    if(c1==c2)
        return TRUE;
    else
        return FALSE;
}
int comp(ElemType a,ElemType b)
{
    if(a==b)
        return 0;
    else
    {
        return (a-b)/abs(a-b);
    }
}
void print(ElemType c)
{
    printf("%d ",c);
}

c2-2.h

typedef struct LNode
{
    ElemType data;
    LNode *next;
}*LinkList;

bo2-2.h

void InitList(LinkList &L)
{
    L=(LinkList)malloc(sizeof(LNode));
    if(!L)
        exit(OVERFLOW);
    L->next=NULL;
}
void DestroyList(LinkList &L)
{
    LinkList q;
    while(L)
    {
        q=L->next;
        free(L);
        L=q;
    }
}
void ClearList(LinkList L)
{
    LinkList p,q;
    p=L->next;
    while(p)
    {
        q=p->next;
        free(p);
        p=q;
    }
    L->next=NULL;
}
Status ListEmpty(LinkList L)
{
    if(L->next)
        return FALSE;
    else 
        return TRUE;
}

int ListLength(LinkList L)
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        ++i;
        p=p->next;
    }
    return i;
}

Status GetElem(LinkList L,int i,ElemType &e)
{
    int j=1;
    LinkList p=L->next;
    while(p&&j<i)
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i)
        return ERROR;
    e=p->data;
    return OK;
}
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        i++;
        if(compare(p->data,e))
            return i;
    }
    return 0;
}

Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e)
{
    LinkList q,p=L->next;
    while(p->next)
    {
        q=p->next;
        if(q->data==cur_e)
        {
            pre_e=p->data;
            return OK;
        }
        p=q;
    }
    return INFEASIBLE;

}

Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e)
{
    LinkList p=L->next;
    while(p->next)
    {
        if(p->data==cur_e)
        {
            next_e=p->next->data;
            return OK;
        }

        p=p->next;
    }
    return INFEASIBLE;
}

Status ListInsert(LinkList L,int i,ElemType e)
{
    int j=0;
    LinkList p=L,s;
    while(p&&j<i-1)
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i-1)
        return ERROR;
    s=(LinkList)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
}

Status ListDelete(LinkList L,int i,ElemType &e)
{
    int j=0;
    LinkList p=L,q;
    while(p->next&&j<i-1)
    {
        p=p->next;
        ++j;
    }
    if(!p->next||j>i-1)
        return ERROR;
    q=p->next;
    p->next=q->next;
    e=q->data;
    free(q);
    return OK;
}

void ListTraverse(LinkList L,void (*vi)(ElemType))
{
    LinkList p=L->next;
    while(p)
    {
        vi(p->data);
        p=p->next;
    }
    printf("\n");
}

main2-2.cpp(可对照上面的函数文件自行修改)

#include"c1.h"
typedef int ElemType;
#include"c2-2.h"
#include"bo2-2.cpp"
#include"func2-3.cpp"

int main()
{
    LinkList L;
    ElemType e,e0;
    Status i;
    int j,k;
    InitList(L);
    for(j=1;j<=5;++j)
        i=ListInsert(L,1,j);
    printf("插入1-5后：L=");
    ListTraverse(L,print);
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)]n",i);
    ClearList(L);
    printf("清空L后：L=");
    ListTraverse(L,print);
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)]n",i);
    for(j=1;j<=10;j++)
        ListInsert(L,j,j);
    printf("在L的表尾插入1-10后：L=");
    ListTraverse(L,print);
    GetElem(L,5,e);
    printf("第5个元素的值为%d\n",e);
    for(j=1;j<=2;++j)
    {
        GetElem(L,j,e0);
        i=PriorElem(L,e0,e);
        if(i==INFEASIBLE)
            printf("元素%d无前驱\n",e0);
        else
        {
            printf("元素%d的前驱为%d\n",e0,e);
        }   
    }
    for(j=ListLength(L)-1;j<=ListLength(L);++j)
    {
        GetElem(L,j,e0);
        i=NextElem(L,e0,e);
        if(i==INFEASIBLE)
            printf("元素%d无后继\n",e0);
        else
        {
            printf("元素%d的后继为%d\n",e0,e);
        }   
    }
    k=ListLength(L);
    for(j=k+1;j>=k;--j)
    {
        i=ListDelete(L,j,e);
        if(i==ERROR)
            printf("删除第%d个元素失败\n",j);
        else
        {
            printf("删除第%d个元素成功，其值为%d\n",j,e);
        }
    }
    printf("现在L的元素为：");
    ListTraverse(L,print);
    DestroyList(L);
    printf("销毁L后：L=%u\n",L);
}

第三章　栈和队列

栈

c3-1.h

#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
typedef int SElemType;
struct SqStack{
    SElemType *top,*base;
    int stacksize;
};

bo3-1.cpp

#include"c3-1.h"
#include"c1.h"

void InitStack(SqStack &S)
{
    S.base=(SElemType*)malloc(sizeof(SElemType)*STACK_INIT_SIZE);
    S.top=S.base;
    if(!S.base)
        exit(OVERFLOW);
    S.stacksize=STACK_INIT_SIZE;
}

void DestroyStack(SqStack &S)
{
    free(S.base);
    S.base=S.top=NULL;
    S.stacksize=0;
}

void ClearStack(SqStack &S)
{
    S.stacksize=0;
}

Status StackEmpty(SqStack &S)
{
    return S.stacksize==0;
}

int StackLength(SqStack &S)
{
    return S.top-S.base;
}

Status GetTop(SqStack &S)
{
    if(S.top>S.base)
        return *(S.top-1);
    else
    {
        return ERROR;
    }
}

void Push(SqStack &S,SElemType e)
{
    
    if(S.top-S.base>=S.stacksize)
    {
        S.base=(SElemType *)realloc(S.base,sizeof(SElemType)*(STACK_INCREMENT+STACK_INIT_SIZE));
        if(!S.base)
            exit(OVERFLOW);
        S.top=S.base+S.stacksize;
        S.stacksize+=STACK_INCREMENT;
    }
    
    *(S.top)++=e;
}

Status Pop(SqStack &S,SElemType &e)
{
    if(S.top==S.base)
        return ERROR;
    e=*(--S.top);
    return OK;
}

Status PrintStack(SqStack S)
{
    int i=1;
    if(S.top==S.base)
        return ERROR;
    while(S.top-i!=S.base)
    {
        printf("%d ",*(S.top-i));
        ++i;
    }
    printf("%d",*(S.top-i));
    return OK;
}

main3-1.cpp(可对照上面的函数文件自行修改)

#include"bo3-1.cpp"

int main()
{
    int i;
    SqStack s;
    InitStack(s);
    int n;
    printf("请输入入栈数：");
    scanf("%d",&n);
    for(i=0;i<n;++i)
    {
        Push(s,i);
    }
    PrintStack(s);
    int t;
    printf("\n");
    for(i=0;i<n/2;++i)
    {
        Pop(s,t);
        printf("%d\n",t);
    }
    PrintStack(s);
    return 0;
}

第四章　串

KMP

c4-1

#define MAXSTRLEN 40 /* 用户可在255以内定义最大串长（1个字节） */
 typedef char SString[MAXSTRLEN+1]; /* 0号单元存放串的长度 */

bo4-1

 Status StrAssign(SString T,char *chars)
 { /* 生成一个其值等于chars的串T */
   int i;
   if(strlen(chars)>MAXSTRLEN)
     return ERROR;
   else
   {
     T[0]=strlen(chars);
     for(i=1;i<=T[0];i++)
       T[i]=*(chars+i-1);
     return OK;
   }
 }

 Status StrCopy(SString T,SString S)
 { /* 由串S复制得串T */
   int i;
   for(i=0;i<=S[0];i++)
     T[i]=S[i];
   return OK;
 }

 Status StrEmpty(SString S)
 { /* 若S为空串,则返回TRUE,否则返回FALSE */
   if(S[0]==0)
     return TRUE;
   else
     return FALSE;
 }

 int StrCompare(SString S,SString T)
 { /* 初始条件: 串S和T存在 */
   /* 操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0 */
   int i;
   for(i=1;i<=S[0]&&i<=T[0];++i)
     if(S[i]!=T[i])
       return S[i]-T[i];
   return S[0]-T[0];
 }

 int StrLength(SString S)
 { /* 返回串的元素个数 */
   return S[0];
 }

 Status ClearString(SString S)
 { /* 初始条件:串S存在。操作结果:将S清为空串 */
   S[0]=0;/* 令串长为零 */
   return OK;
 }

 Status Concat(SString T,SString S1,SString S2) /* 算法4.2改 */
 { /* 用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE */
   int i;
   if(S1[0]+S2[0]<=MAXSTRLEN)
   { /* 未截断 */
     for(i=1;i<=S1[0];i++)
       T[i]=S1[i];
     for(i=1;i<=S2[0];i++)
       T[S1[0]+i]=S2[i];
     T[0]=S1[0]+S2[0];
     return TRUE;
   }
   else
   { /* 截断S2 */
     for(i=1;i<=S1[0];i++)
       T[i]=S1[i];
     for(i=1;i<=MAXSTRLEN-S1[0];i++)
       T[S1[0]+i]=S2[i];
     T[0]=MAXSTRLEN;
     return FALSE;
   }
 }

 Status SubString(SString Sub,SString S,int pos,int len)
 { /* 用Sub返回串S的第pos个字符起长度为len的子串。算法4.3 */
   int i;
   if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)
     return ERROR;
   for(i=1;i<=len;i++)
     Sub[i]=S[pos+i-1];
   Sub[0]=len;
   return OK;
 }

 int Index(SString S,SString T,int pos)
 { /* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0。 */
   /* 其中,T非空,1≤pos≤StrLength(S)。算法4.5 */
   int i,j;
   if(1<=pos&&pos<=S[0])
   {
     i=pos;
     j=1;
     while(i<=S[0]&&j<=T[0])
       if(S[i]==T[j]) /* 继续比较后继字符 */
       {
         ++i;
         ++j;
       }
       else /* 指针后退重新开始匹配 */
       {
         i=i-j+2;
         j=1;
       }
     if(j>T[0])
       return i-T[0];
     else
       return 0;
   }
   else
     return 0;
 }

 Status StrInsert(SString S,int pos,SString T)
 { /* 初始条件: 串S和T存在,1≤pos≤StrLength(S)+1 */
   /* 操作结果: 在串S的第pos个字符之前插入串T。完全插入返回TRUE,部分插入返回FALSE */
   int i;
   if(pos<1||pos>S[0]+1)
     return ERROR;
   if(S[0]+T[0]<=MAXSTRLEN)
   { /* 完全插入 */
     for(i=S[0];i>=pos;i--)
       S[i+T[0]]=S[i];
     for(i=pos;i<pos+T[0];i++)
       S[i]=T[i-pos+1];
     S[0]=S[0]+T[0];
     return TRUE;
   }
   else
   { /* 部分插入 */
     for(i=MAXSTRLEN;i<=pos;i--)
       S[i]=S[i-T[0]];
     for(i=pos;i<pos+T[0];i++)
       S[i]=T[i-pos+1];
     S[0]=MAXSTRLEN;
     return FALSE;
   }
 }

 Status StrDelete(SString S,int pos,int len)
 { /* 初始条件: 串S存在,1≤pos≤StrLength(S)-len+1 */
   /* 操作结果: 从串S中删除第pos个字符起长度为len的子串 */
   int i;
   if(pos<1||pos>S[0]-len+1||len<0)
     return ERROR;
   for(i=pos+len;i<=S[0];i++)
     S[i-len]=S[i];
   S[0]-=len;
   return OK;
 }

 Status Replace(SString S,SString T,SString V)
 { /* 初始条件: 串S,T和V存在,T是非空串（此函数与串的存储结构无关） */
   /* 操作结果: 用V替换主串S中出现的所有与T相等的不重叠的子串 */
   int i=1; /* 从串S的第一个字符起查找串T */
   if(StrEmpty(T)) /* T是空串 */
     return ERROR;
   do
   {
     i=Index(S,T,i); /* 结果i为从上一个i之后找到的子串T的位置 */
     if(i) /* 串S中存在串T */
     {
       StrDelete(S,i,StrLength(T)); /* 删除该串T */
       StrInsert(S,i,V); /* 在原串T的位置插入串V */
       i+=StrLength(V); /* 在插入的串V后面继续查找串T */
     }
   }while(i);
   return OK;
 }

 void DestroyString()
 { /* 由于SString是定长类型,无法销毁 */
 }

 void StrPrint(SString T)
 { /* 输出字符串T。另加 */
   int i;
   for(i=1;i<=T[0];i++)
     printf("%c",T[i]);
   printf("\n");
 }

KMP原

 #include"c1.h"
 #include"c4-1.h"
 #include"bo4-1.c"

 void get_next(SString T,int next[])
 { /* 求模式串T的next函数值并存入数组next 算法 4.7 */
   int i=1,j=0;
   next[1]=0;
   while(i<T[0])
     if(j==0||T[i]==T[j])
     {
       ++i;
       ++j;
       next[i]=j;
     }
     else
       j=next[j];
 }

 int Index_KMP(SString S,SString T,int pos,int next[])
 { /* 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。 */
   /* 其中,T非空,1≤pos≤StrLength(S)。算法 4.6 */
   int i=pos,j=1;
   while(i<=S[0]&&j<=T[0])
     if(j==0||S[i]==T[j]) /* 继续比较后继字符 */
     {
       ++i;
       ++j;
     }
     else /* 模式串向右移动 */
       j=next[j];
   if(j>T[0]) /* 匹配成功 */
     return i-T[0];
   else
     return 0;
 }

 void main()
 {
   int i,j,*p;
   SString s1,s2; /* 以教科书中图4.5为例 */
   StrAssign(s1,"acabaabaabcacaabc");
   printf("主串为: ");
   StrPrint(s1);
   StrAssign(s2,"abaabcac");
   printf("子串为: ");
   StrPrint(s2);
   i=StrLength(s2);
   p=(int*)malloc((i+1)*sizeof(int)); /* 生成s2的next数组 */
   get_next(s2,p);
   printf("子串的next函数为: ");
   for(j=1;j<=i;j++)
     printf("%d ",*(p+j));
   printf("\n");
   i=Index_KMP(s1,s2,1,p);
   if(i)
     printf("主串和子串在第%d个字符处首次匹配\n",i);
   else
     printf("主串和子串匹配不成功\n");
 }

第五章　数组和广义表

第六章　树和二叉树

二叉树

c6-1.h

#define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */
typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点 */

typedef struct
{
  int level,order; /* 结点的层,本层序号(按满二叉树计算) */
}position;

bo6-1.cpp

typedef int Status;
 Status InitBiTree(SqBiTree T)
 { /* 构造空二叉树T。因为T是固定数组，不会改变，故不需要& */
   int i;
   for(i=0;i<MAX_TREE_SIZE;i++)
     T[i]=Nil; /* 初值为空 */
   return OK;
 }

 void DestroyBiTree()
 { /* 由于SqBiTree是定长类型,无法销毁 */
 }

 Status CreateBiTree(SqBiTree T)
 { /* 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T */
   int i=0;
 #if CHAR
   int l;
   char s[MAX_TREE_SIZE];
   printf("请按层序输入结点的值(字符)，空格表示空结点，结点数≤%d:\n",MAX_TREE_SIZE);
   gets(s); /* 输入字符串 */
   l=strlen(s); /* 求字符串的长度 */
   for(;i<l;i++) /* 将字符串赋值给T */
   {
     T[i]=s[i];
     if(i!=0&&T[(i+1)/2-1]==Nil&&T[i]!=Nil) /* 此结点(不空)无双亲且不是根 */
     {
       printf("出现无双亲的非根结点%c\n",T[i]);
       exit(ERROR);
     }
   }
   for(i=l;i<MAX_TREE_SIZE;i++) /* 将空赋值给T的后面的结点 */
     T[i]=Nil;
 #else
   printf("请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤%d:\n",MAX_TREE_SIZE);
   while(1)
   {
     scanf("%d",&T[i]);
     if(T[i]==999)
       break;
     if(i!=0&&T[(i+1)/2-1]==Nil&&T[i]!=Nil) /* 此结点(不空)无双亲且不是根 */
     {
       printf("出现无双亲的非根结点%d\n",T[i]);
       exit(ERROR);
     }
     i++;
   }
   while(i<MAX_TREE_SIZE)
   {
     T[i]=Nil; /* 将空赋值给T的后面的结点 */
     i++;
   }
 #endif
   return OK;
 }

 #define ClearBiTree InitBiTree /* 在顺序存储结构中，两函数完全一样 */

 Status BiTreeEmpty(SqBiTree T)
 { /* 初始条件: 二叉树T存在 */
   /* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
   if(T[0]==Nil) /* 根结点为空,则树空 */
     return TRUE;
   else
     return FALSE;
 }

 int BiTreeDepth(SqBiTree T)
 { /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
   int i,j=-1;
   for(i=MAX_TREE_SIZE-1;i>=0;i--) /* 找到最后一个结点 */
     if(T[i]!=Nil)
       break;
   i++; /* 为了便于计算 */
   do
     j++;
   while(i>=pow(2,j));
   return j;
 }

 Status Root(SqBiTree T,TElemType *e)
 { /* 初始条件: 二叉树T存在 */
   /* 操作结果:  当T不空,用e返回T的根,返回OK;否则返回ERROR,e无定义 */
   if(BiTreeEmpty(T)) /* T空 */
     return ERROR;
   else
   {
     *e=T[0];
     return OK;
   }
 }

 TElemType Value(SqBiTree T,position e)
 { /* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */
   /* 操作结果: 返回处于位置e(层,本层序号)的结点的值 */
   return T[(int)pow(2,e.level-1)+e.order-2];
 }

 Status Assign(SqBiTree T,position e,TElemType value)
 { /* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */
   /* 操作结果: 给处于位置e(层,本层序号)的结点赋新值value */
   int i=(int)pow(2,e.level-1)+e.order-2; /* 将层、本层序号转为矩阵的序号 */
   if(value!=Nil&&T[(i+1)/2-1]==Nil) /* 给叶子赋非空值但双亲为空 */
     return ERROR;
   else if(value==Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) /*  给双亲赋空值但有叶子（不空） */
     return ERROR;
   T[i]=value;
   return OK;
 }

 TElemType Parent(SqBiTree T,TElemType e)
 { /* 初始条件: 二叉树T存在,e是T中某个结点 */
   /* 操作结果: 若e是T的非根结点,则返回它的双亲,否则返回＂空＂ */
   int i;
   if(T[0]==Nil) /* 空树 */
     return Nil;
   for(i=1;i<=MAX_TREE_SIZE-1;i++)
     if(T[i]==e) /* 找到e */
       return T[(i+1)/2-1];
   return Nil; /* 没找到e */
 }

 TElemType LeftChild(SqBiTree T,TElemType e)
 { /* 初始条件: 二叉树T存在,e是T中某个结点 */
   /* 操作结果: 返回e的左孩子。若e无左孩子,则返回＂空＂ */
   int i;
   if(T[0]==Nil) /* 空树 */
     return Nil;
   for(i=0;i<=MAX_TREE_SIZE-1;i++)
     if(T[i]==e) /* 找到e */
       return T[i*2+1];
   return Nil; /* 没找到e */
 }

 TElemType RightChild(SqBiTree T,TElemType e)
 { /* 初始条件: 二叉树T存在,e是T中某个结点 */
   /* 操作结果: 返回e的右孩子。若e无右孩子,则返回＂空＂ */
   int i;
   if(T[0]==Nil) /* 空树 */
     return Nil;
   for(i=0;i<=MAX_TREE_SIZE-1;i++)
     if(T[i]==e) /* 找到e */
       return T[i*2+2];
   return Nil; /* 没找到e */
 }

 TElemType LeftSibling(SqBiTree T,TElemType e)
 { /* 初始条件: 二叉树T存在,e是T中某个结点 */
   /* 操作结果: 返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回＂空＂ */
   int i;
   if(T[0]==Nil) /* 空树 */
     return Nil;
   for(i=1;i<=MAX_TREE_SIZE-1;i++)
     if(T[i]==e&&i%2==0) /* 找到e且其序号为偶数(是右孩子) */
       return T[i-1];
   return Nil; /* 没找到e */
 }

 TElemType RightSibling(SqBiTree T,TElemType e)
 { /* 初始条件: 二叉树T存在,e是T中某个结点 */
   /* 操作结果: 返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回＂空＂ */
   int i;
   if(T[0]==Nil) /* 空树 */
     return Nil;
   for(i=1;i<=MAX_TREE_SIZE-1;i++)
     if(T[i]==e&&i%2) /* 找到e且其序号为奇数(是左孩子) */
       return T[i+1];
   return Nil; /* 没找到e */
 }

 void Move(SqBiTree q,int j,SqBiTree T,int i) /* InsertChild()用到。加 */
 { /* 把从q的j结点开始的子树移为从T的i结点开始的子树 */
   if(q[2*j+1]!=Nil) /* q的左子树不空 */
     Move(q,(2*j+1),T,(2*i+1)); /* 把q的j结点的左子树移为T的i结点的左子树 */
   if(q[2*j+2]!=Nil) /* q的右子树不空 */
     Move(q,(2*j+2),T,(2*i+2)); /* 把q的j结点的右子树移为T的i结点的右子树 */
   T[i]=q[j]; /* 把q的j结点移为T的i结点 */
   q[j]=Nil; /* 把q的j结点置空 */
 }

 Status InsertChild(SqBiTree T,TElemType p,Status LR,SqBiTree c)
 { /* 初始条件: 二叉树T存在,p是T中某个结点的值,LR为0或1,非空二叉树c与T */
   /*           不相交且右子树为空 */
   /* 操作结果: 根据LR为0或1,插入c为T中p结点的左或右子树。p结点的原有左或 */
   /*           右子树则成为c的右子树 */
   int j,k,i=0;
   for(j=0;j<(int)pow(2,BiTreeDepth(T))-1;j++) /* 查找p的序号 */
     if(T[j]==p) /* j为p的序号 */
       break;
   k=2*j+1+LR; /* k为p的左或右孩子的序号 */
   if(T[k]!=Nil) /* p原来的左或右孩子不空 */
     Move(T,k,T,2*k+2); /* 把从T的k结点开始的子树移为从k结点的右子树开始的子树 */
   Move(c,i,T,k); /* 把从c的i结点开始的子树移为从T的k结点开始的子树 */
   return OK;
 }

 typedef int QElemType; /* 设队列元素类型为整型(序号) */
 #include "c3-3.h" /* 顺序非循环队列 */
 #include "bo3-4.c" /* 顺序非循环队列的基本操作 */
 Status DeleteChild(SqBiTree T,position p,int LR)
 { /* 初始条件: 二叉树T存在,p指向T中某个结点,LR为1或0 */
   /* 操作结果: 根据LR为1或0,删除T中p所指结点的左或右子树 */
   int i;
   Status k=OK; /* 队列不空的标志 */
   SqQueue q;
   InitQueue(&q); /* 初始化队列，用于存放待删除的结点 */
   i=(int)pow(2,p.level-1)+p.order-2; /* 将层、本层序号转为矩阵的序号 */
   if(T[i]==Nil) /* 此结点空 */
     return ERROR;
   i=i*2+1+LR; /* 待删除子树的根结点在矩阵中的序号 */
   while(k)
   {
     if(T[2*i+1]!=Nil) /* 左结点不空 */
       EnQueue(&q,2*i+1); /* 入队左结点的序号 */
     if(T[2*i+2]!=Nil) /* 右结点不空 */
       EnQueue(&q,2*i+2); /* 入队右结点的序号 */
     T[i]=Nil; /* 删除此结点 */
     k=DeQueue(&q,&i); /* 队列不空 */
   }
   return OK;
 }

 Status(*VisitFunc)(TElemType); /* 函数变量 */
 void PreTraverse(SqBiTree T,int e)
 { /* PreOrderTraverse()调用 */
   VisitFunc(T[e]);
   if(T[2*e+1]!=Nil) /* 左子树不空 */
     PreTraverse(T,2*e+1);
   if(T[2*e+2]!=Nil) /* 右子树不空 */
     PreTraverse(T,2*e+2);
 }

 Status PreOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
 { /* 初始条件: 二叉树存在,Visit是对结点操作的应用函数 */
   /* 操作结果: 先序遍历T,对每个结点调用函数Visit一次且仅一次。 */
   /*           一旦Visit()失败,则操作失败 */
   VisitFunc=Visit;
   if(!BiTreeEmpty(T)) /* 树不空 */
     PreTraverse(T,0);
   printf("\n");
   return OK;
 }

 void InTraverse(SqBiTree T,int e)
 { /* InOrderTraverse()调用 */
   if(T[2*e+1]!=Nil) /* 左子树不空 */
     InTraverse(T,2*e+1);
   VisitFunc(T[e]);
   if(T[2*e+2]!=Nil) /* 右子树不空 */
     InTraverse(T,2*e+2);
 }

 Status InOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
 { /* 初始条件: 二叉树存在,Visit是对结点操作的应用函数 */
   /* 操作结果: 中序遍历T,对每个结点调用函数Visit一次且仅一次。 */
   /*           一旦Visit()失败,则操作失败 */
   VisitFunc=Visit;
   if(!BiTreeEmpty(T)) /* 树不空 */
     InTraverse(T,0);
   printf("\n");
   return OK;
 }

 void PostTraverse(SqBiTree T,int e)
 { /* PostOrderTraverse()调用 */
   if(T[2*e+1]!=Nil) /* 左子树不空 */
     PostTraverse(T,2*e+1);
   if(T[2*e+2]!=Nil) /* 右子树不空 */
     PostTraverse(T,2*e+2);
   VisitFunc(T[e]);
 }

 Status PostOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
 { /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
   /* 操作结果: 后序遍历T,对每个结点调用函数Visit一次且仅一次。 */
   /*           一旦Visit()失败,则操作失败 */
   VisitFunc=Visit;
   if(!BiTreeEmpty(T)) /* 树不空 */
     PostTraverse(T,0);
   printf("\n");
   return OK;
 }

 void LevelOrderTraverse(SqBiTree T,Status(*Visit)(TElemType))
 { /* 层序遍历二叉树 */
   int i=MAX_TREE_SIZE-1,j;
   while(T[i]==Nil)
     i--; /* 找到最后一个非空结点的序号 */
   for(j=0;j<=i;j++)  /* 从根结点起,按层序遍历二叉树 */
     if(T[j]!=Nil)
       Visit(T[j]); /* 只遍历非空的结点 */
   printf("\n");
 }

 void Print(SqBiTree T)
 { /* 逐层、按本层序号输出二叉树 */
   int j,k;
   position p;
   TElemType e;
   for(j=1;j<=BiTreeDepth(T);j++)
   {
     printf("第%d层: ",j);
     for(k=1;k<=pow(2,j-1);k++)
     {
       p.level=j;
       p.order=k;
       e=Value(T,p);
       if(e!=Nil)
         printf("%d:%d ",k,e);
     }
     printf("\n");
   }
 }

main6-1.cpp

/*#define CHAR 1 /* 字符型 */
 #define CHAR 0 /* 整型(二者选一) */
 #include"c1.h"
 #if CHAR
   typedef char TElemType;
   TElemType Nil=' '; /* 设字符型以空格符为空 */
 #else
   typedef int TElemType;
   TElemType Nil=0; /* 设整型以0为空 */
 #endif
 #include"c6-1.h"
 #include"bo6-1.cpp"

 Status visit(TElemType e)
 {
   printf("%d ",e);
   return OK;
 }

int main()
 {
   Status i;
   int j;
   position p;
   TElemType e;
   SqBiTree T,s;
   InitBiTree(T);
   CreateBiTree(T);
   printf("建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
   i=Root(T,&e);
   if(i)
     printf("二叉树的根为：%d\n",e);
   else
     printf("树空，无根\n");
   printf("层序遍历二叉树:\n");
   LevelOrderTraverse(T,visit);
   printf("中序遍历二叉树:\n");
   InOrderTraverse(T,visit);
   printf("后序遍历二叉树:\n");
   PostOrderTraverse(T,visit);
   printf("请输入待修改结点的层号 本层序号: ");
   scanf("%d%d",&p.level,&p.order);
   e=Value(T,p);
   printf("待修改结点的原值为%d请输入新值: ",e);
   scanf("%d",&e);
   Assign(T,p,e);
   printf("先序遍历二叉树:\n");
   PreOrderTraverse(T,visit);
   printf("结点%d的双亲为%d,左右孩子分别为",e,Parent(T,e));
   printf("%d,%d,左右兄弟分别为",LeftChild(T,e),RightChild(T,e));
   printf("%d,%d\n",LeftSibling(T,e),RightSibling(T,e));
   InitBiTree(s);
   printf("建立右子树为空的树s:\n");
   CreateBiTree(s);
   printf("树s插到树T中,请输入树T中树s的双亲结点 s为左(0)或右(1)子树: ");
   scanf("%d%d",&e,&j);
   InsertChild(T,e,j,s);
   Print(T);
   printf("删除子树,请输入待删除子树根结点的层号 本层序号 左(0)或右(1)子树: ");
   scanf("%d%d%d",&p.level,&p.order,&j);
   DeleteChild(T,p,j);
   Print(T);
   ClearBiTree(T);
   printf("清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
   i=Root(T,&e);
   if(i)
     printf("二叉树的根为：%d\n",e);
   else
     printf("树空，无根\n");


  return 0;
 }

第七章　图

第八章　动态存储管理

第九章　查找

第十章　内部排序

第十一章　外部排序

第十二章　文件