顺序表
1.结构体定义
#define MaxSize 50
typedef int ElemType;
typedef struct
{ ElemType data[MaxSize]; //存放顺序表元素int length; //存放顺序表的长度
} SqList; //顺序表的类型定义
2.建立
void CreateList(SqList *&L,ElemType a[],int n)
//建立顺序表
{int i;L=(SqList *)malloc(sizeof(SqList));for (i=0;i<n;i++)L->data[i]=a[i];L->length=n;
}
3.初始化
void InitList(SqList *&L)
{L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间L->length=0;
}
4.销毁
void DestroyList(SqList *&L)
{free(L);
}
5.判断是否为空表
bool ListEmpty(SqList *L)
{return(L->length==0);
}
6.求长度
int ListLength(SqList *L)
{return(L->length);
}
7.输出
void DispList(SqList *L)
{int i;for (i=0;i<L->length;i++)printf("%d ",L->data[i]);printf("\n");
}
8.按序号求表中元素
bool GetElem(SqList *L,int i,ElemType &e)
{if (i<1 || i>L->length)return false;e=L->data[i-1];return true;
}
9.按元素值查找
int LocateElem(SqList *L, ElemType e)
{int i=0;while (i<L->length && L->data[i]!=e) i++;if (i>=L->length)return 0;elsereturn i+1;
}
10.插入
bool ListInsert(SqList *&L,int i,ElemType e)
{int j;if (i<1 || i>L->length+1)return false;i--; //将顺序表位序转化为elem下标for (j=L->length;j>i;j--) //将data[i]及后面元素后移一个位置L->data[j]=L->data[j-1];L->data[i]=e;L->length++; //顺序表长度增1return true;
}
11.删除
bool ListDelete(SqList *&L,int i,ElemType &e)
{int j;if (i<1 || i>L->length)return false;i--; //将顺序表位序转化为elem下标e=L->data[i];for (j=i;j<L->length-1;j++) //将data[i]之后的元素前移一个位置L->data[j]=L->data[j+1];L->length--; //顺序表长度减1return true;
}
单链表
1.结构体定义
typedef int ElemType;
typedef struct LNode //声明单链表节点类型
{ElemType data;struct LNode *next; //指向后继节点
} LinkNode;
2.建立单链表---头插法
void CreateListF(LinkNode *&L,ElemType a[],int n)
//头插法建立单链表
{LinkNode *s;int i;L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头节点L->next=NULL;for (i=0;i<n;i++){ s=(LinkNode *)malloc(sizeof(LinkNode));//创建新节点s->data=a[i];s->next=L->next; //将节点s插在原开始节点之前,头节点之后L->next=s;}
}
3.建立单链表---尾插法
void CreateListR(LinkNode *&L,ElemType a[],int n)
//尾插法建立单链表
{LinkNode *s,*r;int i;L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头节点L->next=NULL;r=L; //r始终指向终端节点,开始时指向头节点for (i=0;i<n;i++){ s=(LinkNode *)malloc(sizeof(LinkNode));//创建新节点s->data=a[i];r->next=s; //将节点s插入到节点r之后r=s;}r->next=NULL; //终端节点next域置为NULL
}
4.初始化
void InitList(LinkNode *&L)
{L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头节点L->next=NULL;
}
5.销毁
void DestroyList(LinkNode *&L)
{LinkNode *p=L,*q=p->next;while (q!=NULL){ free(p);p=q;q=p->next;}free(p); //此时q为NULL,p指向尾节点,释放它
}
6.判断是否为空表
bool ListEmpty(LinkNode *L)
{return(L->next==NULL);
}
7.求长度
int ListLength(LinkNode *L)
{LinkNode *p=L;int i=0;while (p->next!=NULL){ i++;p=p->next;}return(i);
}
8.输出
void DispList(LinkNode *L)
{LinkNode *p=L->next;while (p!=NULL){ printf("%d ",p->data);p=p->next;}printf("\n");
}
9.按序号求表中元素
bool GetElem(LinkNode *L,int i,ElemType &e)
{int j=0;LinkNode *p=L;while (j<i && p!=NULL){ j++;p=p->next;}if (p==NULL) //不存在第i个数据节点return false;else //存在第i个数据节点{ e=p->data;return true;}
}
10.按元素值查找
int LocateElem(LinkNode *L,ElemType e)
{LinkNode *p=L->next;int n=1;while (p!=NULL && p->data!=e){ p=p->next;n++;}if (p==NULL)return(0);elsereturn(n);
}
11. 插入
bool ListInsert(LinkNode *&L,int i,ElemType e)
{int j=0;LinkNode *p=L,*s;while (j<i-1 && p!=NULL) //查找第i-1个节点{ j++;p=p->next;}if (p==NULL) //未找到位序为i-1的节点return false;else //找到位序为i-1的节点p{ s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新节点ss->data=e;s->next=p->next; //将s插入到p之后p->next=s;return true;}
}
12. 删除
bool ListDelete(LinkNode *&L,int i,ElemType &e)
{int j=0;LinkNode *p=L,*q;while (j<i-1 && p!=NULL) //查找第i-1个节点{ j++;p=p->next;}if (p==NULL) //未找到位序为i-1的节点return false;else //找到位序为i-1的节点p{ q=p->next; //q指向要删除的节点if (q==NULL) return false; //若不存在第i个节点,返回falsee=q->data;p->next=q->next; //从单链表中删除q节点free(q); //释放q节点return true;}
}
双链表
1.结构体定义
typedef int ElemType;
typedef struct DNode //定义双链表节点类型
{ElemType data;struct DNode *prior; //指向前驱节点struct DNode *next; //指向后继节点int freq; //用于2.11题
} DLinkNode;
2.头插法建立
void CreateListF(DLinkNode *&L,ElemType a[],int n)
//头插法建双链表
{DLinkNode *s;int i;L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头节点L->prior=L->next=NULL;for (i=0;i<n;i++){ s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新节点s->data=a[i];s->next=L->next; //将节点s插在原开始节点之前,头节点之后if (L->next!=NULL) L->next->prior=s;L->next=s;s->prior=L;}
}
3.尾插法建立
void CreateListR(DLinkNode *&L,ElemType a[],int n)
//尾插法建双链表
{DLinkNode *s,*r;int i;L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头节点L->prior=L->next=NULL;r=L; //r始终指向终端节点,开始时指向头节点for (i=0;i<n;i++){ s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新节点s->data=a[i];s->freq=0; //用于2.11题r->next=s;s->prior=r; //将节点s插入节点r之后r=s;}r->next=NULL; //尾节点next域置为NULL
}
4.初始化
void InitList(DLinkNode *&L)
{L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头节点L->prior=L->next=NULL;
}
5.销毁
void DestroyList(DLinkNode *&L)
{DLinkNode *p=L,*q=p->next;while (q!=NULL){free(p);p=q;q=p->next;}free(p);
}
6.判断是否为空表
bool ListEmpty(DLinkNode *L)
{return(L->next==NULL);
}
7.求长度
int ListLength(DLinkNode *L)
{DLinkNode *p=L;int i=0;while (p->next!=NULL){i++;p=p->next;}return(i);
}
8.
void DispList(DLinkNode *L)
{DLinkNode *p=L->next;while (p!=NULL){printf("%d[%d] ",p->data,p->freq); //用于练习题//printf("%d ",p->data);p=p->next;}printf("\n");
}bool GetElem(DLinkNode *L,int i,ElemType &e)
{int j=0;DLinkNode *p=L;while (j<i && p!=NULL){j++;p=p->next;}if (p==NULL)return false;else{e=p->data;return true;}
}int LocateElem(DLinkNode *L,ElemType e)
{int n=1;DLinkNode *p=L->next;while (p!=NULL && p->data!=e){n++;p=p->next;}if (p==NULL)return(0);elsereturn(n);
}bool ListInsert(DLinkNode *&L,int i,ElemType e)
{int j=0;DLinkNode *p=L,*s;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL) //未找到第i-1个节点return false;else //找到第i-1个节点p{s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新节点ss->data=e; s->next=p->next; //将节点s插入到节点p之后if (p->next!=NULL) p->next->prior=s;s->prior=p;p->next=s;return true;}
}bool ListDelete(DLinkNode *&L,int i,ElemType &e)
{int j=0;DLinkNode *p=L,*q;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL) //未找到第i-1个节点return false;else //找到第i-1个节点p{q=p->next; //q指向要删除的节点if (q==NULL) return false; //不存在第i个节点e=q->data;p->next=q->next; //从单链表中删除*q节点if (p->next!=NULL) p->next->prior=p;free(q); //释放q节点return true;}
}
循环单链表
//循环单链表运算算法
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode //定义单链表节点类型
{ElemType data;struct LNode *next;
} LinkNode;void CreateListF(LinkNode *&L,ElemType a[],int n)
//头插法建立循环单链表
{LinkNode *s;int i;L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头节点L->next=NULL;for (i=0;i<n;i++){ s=(LinkNode *)malloc(sizeof(LinkNode));//创建新节点s->data=a[i];s->next=L->next; //将节点s插在原开始节点之前,头节点之后L->next=s;}s=L->next; while (s->next!=NULL) //查找尾节点,由s指向它s=s->next;s->next=L; //尾节点next域指向头节点}void CreateListR(LinkNode *&L,ElemType a[],int n)
//尾插法建立循环单链表
{LinkNode *s,*r;int i;L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头节点L->next=NULL;r=L; //r始终指向终端节点,开始时指向头节点for (i=0;i<n;i++){ s=(LinkNode *)malloc(sizeof(LinkNode));//创建新节点s->data=a[i];r->next=s; //将节点s插入节点r之后r=s;}r->next=L; //尾节点next域指向头节点
}void InitList(LinkNode *&L)
{L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头节点L->next=L;
}void DestroyList(LinkNode *&L)
{LinkNode *p=L,*q=p->next;while (q!=L){free(p);p=q;q=p->next;}free(p);
}bool ListEmpty(LinkNode *L)
{return(L->next==L);
}int ListLength(LinkNode *L)
{LinkNode *p=L;int i=0;while (p->next!=L){i++;p=p->next;}return(i);
}void DispList(LinkNode *L)
{LinkNode *p=L->next;while (p!=L){printf("%d ",p->data);p=p->next;}printf("\n");
}bool GetElem(LinkNode *L,int i,ElemType &e)
{int j=0;LinkNode *p;if (L->next!=L) //单链表不为空表时{if (i==1){e=L->next->data;return true;}else //i不为1时{p=L->next;while (j<i-1 && p!=L){j++;p=p->next;}if (p==L)return false;else{e=p->data;return true;}}}else //单链表为空表时return false;
}int LocateElem(LinkNode *L,ElemType e)
{LinkNode *p=L->next;int n=1;while (p!=L && p->data!=e){p=p->next;n++;}if (p==L)return(0);elsereturn(n);
}bool ListInsert(LinkNode *&L,int i,ElemType e)
{int j=0;LinkNode *p=L,*s;if (p->next==L || i==1) //原单链表为空表或i==1时{s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新节点ss->data=e; s->next=p->next; //将节点s插入到节点p之后p->next=s;return true;}else{p=L->next;while (j<i-2 && p!=L){j++;p=p->next;}if (p==L) //未找到第i-1个节点return false;else //找到第i-1个节点p{s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新节点ss->data=e; s->next=p->next; //将节点s插入到节点p之后p->next=s;return true;}}
}bool ListDelete(LinkNode *&L,int i,ElemType &e)
{int j=0;LinkNode *p=L,*q;if (p->next!=L) //原单链表不为空表时{if (i==1) //i==1时{q=L->next; //删除第1个节点e=q->data;L->next=q->next;free(q);return true;}else //i不为1时{p=L->next;while (j<i-2 && p!=L){j++;p=p->next;}if (p==L) //未找到第i-1个节点return false;else //找到第i-1个节点p{q=p->next; //q指向要删除的节点e=q->data;p->next=q->next; //从单链表中删除q节点free(q); //释放q节点return true;}}}else return false;
}
循环双链表
//循环双链表运算算法
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct DNode //定义双链表节点类型
{ElemType data;struct DNode *prior; //指向前驱节点struct DNode *next; //指向后继节点
} DLinkNode;void CreateListF(DLinkNode *&L,ElemType a[],int n)
//头插法建立循环双链表
{DLinkNode *s;int i;L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头节点L->next=NULL;for (i=0;i<n;i++){ s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新节点s->data=a[i];s->next=L->next; //将节点s插在原开始节点之前,头节点之后if (L->next!=NULL) L->next->prior=s;L->next=s;s->prior=L;}s=L->next; while (s->next!=NULL) //查找尾节点,由s指向它s=s->next;s->next=L; //尾节点next域指向头节点L->prior=s; //头节点的prior域指向尾节点}void CreateListR(DLinkNode *&L,ElemType a[],int n)
//尾插法建立循环双链表
{DLinkNode *s,*r;int i;L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头节点L->next=NULL;r=L; //r始终指向尾节点,开始时指向头节点for (i=0;i<n;i++){ s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新节点s->data=a[i];r->next=s;s->prior=r; //将节点s插入节点r之后r=s;}r->next=L; //尾节点next域指向头节点L->prior=r; //头节点的prior域指向尾节点
}void InitList(DLinkNode *&L)
{L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头节点L->prior=L->next=L;
}void DestroyList(DLinkNode *&L)
{DLinkNode *p=L,*q=p->next;while (q!=L){free(p);p=q;q=p->next;}free(p);
}bool ListEmpty(DLinkNode *L)
{return(L->next==L);
}int ListLength(DLinkNode *L)
{DLinkNode *p=L;int i=0;while (p->next!=L){i++;p=p->next;}return(i);
}void DispList(DLinkNode *L)
{DLinkNode *p=L->next;while (p!=L){printf("%d ",p->data);p=p->next;}printf("\n");
}bool GetElem(DLinkNode *L,int i,ElemType &e)
{int j=0;DLinkNode *p;if (L->next!=L) //双链表不为空表时{if (i==1){e=L->next->data;return true;}else //i不为1时{p=L->next;while (j<i-1 && p!=L){j++;p=p->next;}if (p==L)return false;else{e=p->data;return true;}}}else //双链表为空表时return 0;
}int LocateElem(DLinkNode *L,ElemType e)
{int n=1;DLinkNode *p=L->next;while (p!=NULL && p->data!=e){n++;p=p->next;}if (p==NULL)return(0);elsereturn(n);
}bool ListInsert(DLinkNode *&L,int i,ElemType e)
{int j=0;DLinkNode *p=L,*s;if (p->next==L) //原双链表为空表时{ s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新节点ss->data=e;p->next=s;s->next=p;p->prior=s;s->prior=p;return true;}else if (i==1) //原双链表不为空表但i=1时{s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新节点ss->data=e;s->next=p->next;p->next=s; //将节点s插入到节点p之后s->next->prior=s;s->prior=p;return true;}else{ p=L->next;while (j<i-2 && p!=L){ j++;p=p->next;}if (p==L) //未找到第i-1个节点return false;else //找到第i-1个节点*p{s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新节点ss->data=e; s->next=p->next; //将节点s插入到节点p之后if (p->next!=NULL) p->next->prior=s;s->prior=p;p->next=s;return true;}}
}bool ListDelete(DLinkNode *&L,int i,ElemType &e)
{int j=0;DLinkNode *p=L,*q;if (p->next!=L) //原双链表不为空表时{ if (i==1) //i==1时{ q=L->next; //删除第1个节点e=q->data;L->next=q->next;q->next->prior=L;free(q);return true;}else //i不为1时{ p=L->next;while (j<i-2 && p!=NULL) {j++;p=p->next;}if (p==NULL) //未找到第i-1个节点return false;else //找到第i-1个节点p{q=p->next; //q指向要删除的节点if (q==NULL) return 0; //不存在第i个节点e=q->data;p->next=q->next; //从单链表中删除q节点if (p->next!=NULL) p->next->prior=p;free(q); //释放q节点return true;}}}else return false; //原双链表为空表时
}
顺序栈
//顺序栈运算算法
#include <stdio.h>
#include <malloc.h>#define MaxSize 100
typedef char ElemType;
//typedef int ElemType;
typedef struct
{ ElemType data[MaxSize];int top; //栈指针
} SqStack; //顺序栈类型定义void InitStack(SqStack *&s)
{s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;
} void DestroyStack(SqStack *&s)
{free(s);
}bool StackEmpty(SqStack *s)
{return(s->top==-1);
}bool Push(SqStack *&s,ElemType e)
{if (s->top==MaxSize-1) //栈满的情况，即栈上溢出return false;s->top++;s->data[s->top]=e;return true;
}bool Pop(SqStack *&s,ElemType &e)
{if (s->top==-1) //栈为空的情况，即栈下溢出return false;e=s->data[s->top];s->top--;return true;
} bool GetTop(SqStack *s,ElemType &e)
{if (s->top==-1) //栈为空的情况，即栈下溢出return false;e=s->data[s->top];return true;
}
顺序队列（环形队列）
//顺序队列（环形队列）运算算法
#include <stdio.h>
#include <malloc.h>#define MaxSize 100
typedef int ElemType;
typedef struct
{ ElemType data[MaxSize];int front,rear; //队首和队尾指针
} SqQueue;void InitQueue(SqQueue *&q)
{ q=(SqQueue *)malloc (sizeof(SqQueue));q->front=q->rear=0;
}void DestroyQueue(SqQueue *&q)
{free(q);
}bool QueueEmpty(SqQueue *q)
{return(q->front==q->rear);
}bool enQueue(SqQueue *&q,ElemType e)
{ if ((q->rear+1)%MaxSize==q->front) //队满上溢出return false;q->rear=(q->rear+1)%MaxSize;q->data[q->rear]=e;return true;
}bool deQueue(SqQueue *&q,ElemType &e)
{ if (q->front==q->rear) //队空下溢出return false;q->front=(q->front+1)%MaxSize;e=q->data[q->front];return true;
}
顺序队列（非环形队列）
//顺序队列（非环形队列）运算算法
#include <stdio.h>
#include <malloc.h>#define MaxSize 100
typedef char ElemType;
typedef struct
{ ElemType data[MaxSize];int front,rear; //队头和队尾指针
} SqQueue;void InitQueue(SqQueue *&q)
{ q=(SqQueue *)malloc (sizeof(SqQueue));q->front=q->rear=-1;
}void DestroyQueue(SqQueue *&q) //销毁队列
{free(q);
}bool QueueEmpty(SqQueue *q) //判断队列是否为空
{return(q->front==q->rear);
}bool enQueue(SqQueue *&q,ElemType e) //进队
{ if (q->rear==MaxSize-1) //队满上溢出return false; //返回假q->rear++; //队尾增1q->data[q->rear]=e; //rear位置插入元素ereturn true; //返回真
}bool deQueue(SqQueue *&q,ElemType &e) //出队
{ if (q->front==q->rear) //队空下溢出return false;q->front++;e=q->data[q->front];return true;
}
链栈
//链栈运算算法
#include <stdio.h>
#include <malloc.h>typedef char ElemType;
typedef struct linknode
{ ElemType data; //数据域struct linknode *next; //指针域
} LinkStNode; //链栈类型定义void InitStack(LinkStNode *&s)
{s=(LinkStNode *)malloc(sizeof(LinkStNode));s->next=NULL;
}void DestroyStack(LinkStNode *&s)
{LinkStNode *p=s->next;while (p!=NULL){ free(s);s=p;p=p->next;}free(s); //s指向尾节点,释放其空间
}bool StackEmpty(LinkStNode *s)
{return(s->next==NULL);
}void Push(LinkStNode *&s,ElemType e)
{ LinkStNode *p;p=(LinkStNode *)malloc(sizeof(LinkStNode));p->data=e; //新建元素e对应的节点pp->next=s->next; //插入p节点作为开始节点s->next=p;
}bool Pop(LinkStNode *&s,ElemType &e)
{ LinkStNode *p;if (s->next==NULL) //栈空的情况return false;p=s->next; //p指向开始节点e=p->data;s->next=p->next; //删除p节点free(p); //释放p节点return true;
}bool GetTop(LinkStNode *s,ElemType &e)
{ if (s->next==NULL) //栈空的情况return false;e=s->next->data;return true;
}
链队
//链队运算算法
#include <stdio.h>
#include <malloc.h>typedef char ElemType;
typedef struct qnode
{ ElemType data;struct qnode *next;
} DataNode; //链队数据结点类型定义typedef struct
{ DataNode *front;DataNode *rear;
} LinkQuNode; //链队类型定义void InitQueue(LinkQuNode *&q)
{ q=(LinkQuNode *)malloc(sizeof(LinkQuNode));q->front=q->rear=NULL;
}void DestroyQueue(LinkQuNode *&q)
{DataNode *p=q->front,*r; //p指向队头数据节点if (p!=NULL) //释放数据节点占用空间{ r=p->next;while (r!=NULL){ free(p);p=r;r=p->next;}}free(p);free(q); //释放链队节点占用空间
}bool QueueEmpty(LinkQuNode *q)
{return(q->rear==NULL);
}void enQueue(LinkQuNode *&q,ElemType e)
{ DataNode *p;p=(DataNode *)malloc(sizeof(DataNode));p->data=e;p->next=NULL;if (q->rear==NULL) //若链队为空,则新节点是队首节点又是队尾节点q->front=q->rear=p;else{ q->rear->next=p; //将*p节点链到队尾,并将rear指向它q->rear=p;}
}bool deQueue(LinkQuNode *&q,ElemType &e)
{ DataNode *t;if (q->rear==NULL) //队列为空return false;t=q->front; //t指向第一个数据节点if (q->front==q->rear) //队列中只有一个节点时q->front=q->rear=NULL;else //队列中有多个节点时q->front=q->front->next;e=t->data;free(t);return true;
}
顺序串
//顺序串基本运算的算法
#include <stdio.h>
#define MaxSize 100
typedef struct
{ char data[MaxSize];int length; //串长
} SqString;void StrAssign(SqString &s,char cstr[]) //字符串常量赋给串s
{int i;for (i=0;cstr[i]!='\0';i++)s.data[i]=cstr[i];s.length=i;
}void DestroyStr(SqString &s)
{ }void StrCopy(SqString &s,SqString t) //串复制
{int i;for (i=0;i<t.length;i++)s.data[i]=t.data[i];s.length=t.length;
}bool StrEqual(SqString s,SqString t) //判串相等
{bool same=true;int i;if (s.length!=t.length) //长度不相等时返回0same=false;else for (i=0;i<s.length;i++)if (s.data[i]!=t.data[i]) //有一个对应字符不相同时返回0{ same=false;break;}return same;
}int StrLength(SqString s) //求串长
{return s.length;
}SqString Concat(SqString s,SqString t) //串连接
{SqString str;int i;str.length=s.length+t.length;for (i=0;i<s.length;i++) //将s.data[0..s.length-1]复制到strstr.data[i]=s.data[i];for (i=0;i<t.length;i++) //将t.data[0..t.length-1]复制到strstr.data[s.length+i]=t.data[i];return str;
}SqString SubStr(SqString s,int i,int j) //求子串
{SqString str;int k;str.length=0;if (i<=0 || i>s.length || j<0 || i+j-1>s.length)return str; //参数不正确时返回空串for (k=i-1;k<i+j-1;k++) //将s.data[i..i+j]复制到strstr.data[k-i+1]=s.data[k];str.length=j;return str;
} SqString InsStr(SqString s1,int i,SqString s2) //插入串
{int j;SqString str;str.length=0;if (i<=0 || i>s1.length+1) //参数不正确时返回空串return str;for (j=0;j<i-1;j++) //将s1.data[0..i-2]复制到strstr.data[j]=s1.data[j];for (j=0;j<s2.length;j++) //将s2.data[0..s2.length-1]复制到strstr.data[i+j-1]=s2.data[j];for (j=i-1;j<s1.length;j++) //将s1.data[i-1..s1.length-1]复制到strstr.data[s2.length+j]=s1.data[j];str.length=s1.length+s2.length;return str;
}SqString DelStr(SqString s,int i,int j) //串删去
{int k;SqString str;str.length=0;if (i<=0 || i>s.length || i+j>s.length+1) //参数不正确时返回空串return str;for (k=0;k<i-1;k++) //将s.data[0..i-2]复制到strstr.data[k]=s.data[k];for (k=i+j-1;k<s.length;k++) //将s.data[i+j-1..s.length-1]复制到strstr.data[k-j]=s.data[k];str.length=s.length-j;return str;
}SqString RepStr(SqString s,int i,int j,SqString t) //子串替换
{int k;SqString str;str.length=0;if (i<=0 || i>s.length || i+j-1>s.length) //参数不正确时返回空串return str;for (k=0;k<i-1;k++) //将s.data[0..i-2]复制到strstr.data[k]=s.data[k];for (k=0;k<t.length;k++) //将t.data[0..t.length-1]复制到strstr.data[i+k-1]=t.data[k];for (k=i+j-1;k<s.length;k++) //将s.data[i+j-1..s.length-1]复制到strstr.data[t.length+k-j]=s.data[k];str.length=s.length-j+t.length;return str;
}void DispStr(SqString s) //输出串s
{int i;if (s.length>0){ for (i=0;i<s.length;i++)printf("%c",s.data[i]);printf("\n");}
}
顺序栈
//顺序栈运算算法
#include <stdio.h>
#include <malloc.h>#define MaxSize 100
typedef char ElemType;
typedef struct
{ ElemType data[MaxSize];int top; //栈指针
} SqStack; //顺序栈类型定义void InitStack(SqStack *&s)
{s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;
} void DestroyStack(SqStack *&s)
{free(s);
}bool StackEmpty(SqStack *s)
{return(s->top==-1);
}bool Push(SqStack *&s,ElemType e)
{if (s->top==MaxSize-1) //栈满的情况，即栈上溢出return false;s->top++;s->data[s->top]=e;return true;
}bool Pop(SqStack *&s,ElemType &e)
{if (s->top==-1) //栈为空的情况，即栈下溢出return false;e=s->data[s->top];s->top--;return true;
} bool GetTop(SqStack *s,ElemType &e)
{if (s->top==-1) //栈为空的情况，即栈下溢出return false;e=s->data[s->top];return true;
}
链串
////链串基本运算的算法
#include <stdio.h>
#include <malloc.h>
typedef struct snode
{ char data;struct snode *next;
} LinkStrNode;void StrAssign(LinkStrNode *&s,char cstr[]) //字符串常量cstr赋给串s
{int i;LinkStrNode *r,*p;s=(LinkStrNode *)malloc(sizeof(LinkStrNode));r=s; //r始终指向尾节点for (i=0;cstr[i]!='\0';i++) { p=(LinkStrNode *)malloc(sizeof(LinkStrNode));p->data=cstr[i];r->next=p;r=p;}r->next=NULL;
}void DestroyStr(LinkStrNode *&s)
{ LinkStrNode *pre=s,*p=s->next; //pre指向节点p的前驱节点while (p!=NULL) //扫描链串s{ free(pre); //释放pre节点pre=p; //pre、p同步后移一个节点p=pre->next;}free(pre); //循环结束时,p为NULL,pre指向尾节点,释放它
}void StrCopy(LinkStrNode *&s,LinkStrNode *t) //串t复制给串s
{LinkStrNode *p=t->next,*q,*r;s=(LinkStrNode *)malloc(sizeof(LinkStrNode));r=s; //r始终指向尾节点while (p!=NULL) //将t的所有节点复制到s{ q=(LinkStrNode *)malloc(sizeof(LinkStrNode));q->data=p->data;r->next=q;r=q;p=p->next;}r->next=NULL;
}bool StrEqual(LinkStrNode *s,LinkStrNode *t) //判串相等
{LinkStrNode *p=s->next,*q=t->next;while (p!=NULL && q!=NULL && p->data==q->data) { p=p->next;q=q->next;}if (p==NULL && q==NULL)return true;elsereturn false;
}int StrLength(LinkStrNode *s) //求串长
{int i=0;LinkStrNode *p=s->next;while (p!=NULL) { i++;p=p->next;}return i;
}LinkStrNode *Concat(LinkStrNode *s,LinkStrNode *t) //串连接
{LinkStrNode *str,*p=s->next,*q,*r;str=(LinkStrNode *)malloc(sizeof(LinkStrNode));r=str;while (p!=NULL) //将s的所有节点复制到str{ q=(LinkStrNode *)malloc(sizeof(LinkStrNode));q->data=p->data;r->next=q;r=q;p=p->next;}p=t->next;while (p!=NULL) //将t的所有节点复制到str{ q=(LinkStrNode *)malloc(sizeof(LinkStrNode));q->data=p->data;r->next=q;r=q;p=p->next;}r->next=NULL;return str;
}LinkStrNode *SubStr(LinkStrNode *s,int i,int j) //求子串
{int k;LinkStrNode *str,*p=s->next,*q,*r;str=(LinkStrNode *)malloc(sizeof(LinkStrNode));str->next=NULL;r=str; //r指向新建链表的尾节点if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s))return str; //参数不正确时返回空串for (k=0;k<i-1;k++)p=p->next;for (k=1;k<=j;k++) //将s的第i个节点开始的j个节点复制到str{ q=(LinkStrNode *)malloc(sizeof(LinkStrNode));q->data=p->data;r->next=q;r=q;p=p->next;}r->next=NULL;return str;
}LinkStrNode *InsStr(LinkStrNode *s,int i,LinkStrNode *t) //串插入
{int k;LinkStrNode *str,*p=s->next,*p1=t->next,*q,*r;str=(LinkStrNode *)malloc(sizeof(LinkStrNode));str->next=NULL;r=str; //r指向新建链表的尾节点if (i<=0 || i>StrLength(s)+1) //参数不正确时返回空串return str;for (k=1;k<i;k++) //将s的前i个节点复制到str{ q=(LinkStrNode *)malloc(sizeof(LinkStrNode));q->data=p->data;r->next=q;r=q;p=p->next;}while (p1!=NULL) //将t的所有节点复制到str{ q=(LinkStrNode *)malloc(sizeof(LinkStrNode));q->data=p1->data;r->next=q;r=q;p1=p1->next;}while (p!=NULL) //将节点p及其后的节点复制到str{ q=(LinkStrNode *)malloc(sizeof(LinkStrNode));q->data=p->data;r->next=q;r=q;p=p->next;}r->next=NULL;return str;
}LinkStrNode *DelStr(LinkStrNode *s,int i,int j) //串删去
{int k;LinkStrNode *str,*p=s->next,*q,*r;str=(LinkStrNode *)malloc(sizeof(LinkStrNode));str->next=NULL;r=str; //r指向新建链表的尾节点if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s))return str; //参数不正确时返回空串for (k=0;k<i-1;k++) //将s的前i-1个节点复制到str{ q=(LinkStrNode *)malloc(sizeof(LinkStrNode));q->data=p->data;r->next=q;r=q;p=p->next;}for (k=0;k<j;k++) //让p沿next跳j个节点p=p->next;while (p!=NULL) //将节点p及其后的节点复制到str{ q=(LinkStrNode *)malloc(sizeof(LinkStrNode));q->data=p->data;r->next=q;r=q;p=p->next;}r->next=NULL;return str;
}LinkStrNode *RepStr(LinkStrNode *s,int i,int j,LinkStrNode *t) //串替换
{int k;LinkStrNode *str,*p=s->next,*p1=t->next,*q,*r;str=(LinkStrNode *)malloc(sizeof(LinkStrNode));str->next=NULL;r=str; //r指向新建链表的尾节点if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s))return str; //参数不正确时返回空串for (k=0;k<i-1;k++) //将s的前i-1个节点复制到str{ q=(LinkStrNode *)malloc(sizeof(LinkStrNode));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}for (k=0;k<j;k++) //让p沿next跳j个节点p=p->next;while (p1!=NULL) //将t的所有节点复制到str{ q=(LinkStrNode *)malloc(sizeof(LinkStrNode));q->data=p1->data;q->next=NULL;r->next=q;r=q;p1=p1->next;}while (p!=NULL) //将节点p及其后的节点复制到str{ q=(LinkStrNode *)malloc(sizeof(LinkStrNode));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}r->next=NULL;return str;
}void DispStr(LinkStrNode *s) //输出串
{LinkStrNode *p=s->next;while (p!=NULL){ printf("%c",p->data);p=p->next;}printf("\n");
}
KMP算法
//KMP算法
#include "sqstring.cpp"
void GetNext(SqString t,int next[]) //由模式串t求出next值
{int j,k;j=0;k=-1;next[0]=-1;while (j<t.length-1) { if (k==-1 || t.data[j]==t.data[k]) //k为-1或比较的字符相等时{ j++;k++;next[j]=k;//printf("(1) j=%d,k=%d,next[%d]=%d\n",j,k,j,k);}else{k=next[k];//printf("(2) k=%d\n",k);}}
}int KMPIndex(SqString s,SqString t) //KMP算法
{int next[MaxSize],i=0,j=0;GetNext(t,next);while (i<s.length && j<t.length) {if (j==-1 || s.data[i]==t.data[j]) {i++;j++; //i,j各增1}else j=next[j]; //i不变,j后退}if (j>=t.length)return(i-t.length); //返回匹配模式串的首字符下标else return(-1); //返回不匹配标志
}int main()
{SqString s,t;StrAssign(s,"ababcabcacbab");StrAssign(t,"abcac");printf("s:");DispStr(s);printf("t:");DispStr(t);printf("位置:%d\n",KMPIndex(s,t));return 1;
}
改进的KMP算法
//改进的KMP算法
#include "sqstring.cpp"
void GetNextval(SqString t,int nextval[]) //由模式串t求出nextval值
{int j=0,k=-1;nextval[0]=-1;while (j<t.length) {if (k==-1 || t.data[j]==t.data[k]) { j++;k++;if (t.data[j]!=t.data[k]) nextval[j]=k;else nextval[j]=nextval[k];}else k=nextval[k]; }}int KMPIndex1(SqString s,SqString t) //修正的KMP算法
{int nextval[MaxSize],i=0,j=0;GetNextval(t,nextval);while (i<s.length && j<t.length) {if (j==-1 || s.data[i]==t.data[j]) { i++;j++; }else j=nextval[j];}if (j>=t.length) return(i-t.length);elsereturn(-1);
}int main()
{SqString s,t;StrAssign(s,"ababcabcacbab");StrAssign(t,"abcac");printf("s:");DispStr(s);printf("t:");DispStr(t);printf("位置:%d\n",KMPIndex1(s,t));return 1;
}
BF算法
//BF算法
#include "sqstring.cpp"
int index(SqString s,SqString t)
{int i=0,j=0;while (i<s.length && j<t.length) {if (s.data[i]==t.data[j]) //继续匹配下一个字符{ i++; //主串和子串依次匹配下一个字符j++; }else //主串、子串指针回溯重新开始下一次匹配{ i=i-j+1; //主串从下一个位置开始匹配j=0; //子串从头开始匹配}}if (j>=t.length) return(i-t.length); //返回匹配的第一个字符的下标else return(-1); //模式匹配不成功
}int main()
{SqString s,t;StrAssign(s,"ababcabcacbab");StrAssign(t,"abcac");printf("s:");DispStr(s);printf("t:");DispStr(t);printf("位置:%d\n",index(s,t));return 1;
}
二叉树
//二叉树的基本运算算法
#include <stdio.h>
#include <malloc.h>#define MaxSize 100
typedef char ElemType;
typedef struct node
{ ElemType data; //数据元素struct node *lchild; //指向左孩子结点struct node *rchild; //指向右孩子结点struct node *parent; //用于练习题21
} BTNode;void CreateBTree(BTNode * &b,char *str) //创建二叉树
{BTNode *St[MaxSize],*p=NULL;int top=-1,k,j=0; char ch;b=NULL; //建立的二叉树初始时为空ch=str[j];while (ch!='\0') //str未扫描完时循环{switch(ch) {case '(':top++;St[top]=p;k=1; break; //为左孩子结点case ')':top--;break;case ',':k=2; break; //为孩子结点右结点default:p=(BTNode *)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if (b==NULL) //*p为二叉树的根结点b=p;else //已建立二叉树根结点{ switch(k) {case 1:St[top]->lchild=p;break;case 2:St[top]->rchild=p;break;}}}j++;ch=str[j];}
}void DestroyBTree(BTNode *&b)
{ if (b!=NULL){ DestroyBTree(b->lchild);DestroyBTree(b->rchild);free(b);}
}BTNode *FindNode(BTNode *b,ElemType x)
{BTNode *p;if (b==NULL)return NULL;else if (b->data==x)return b;else {p=FindNode(b->lchild,x);if (p!=NULL) return p;else return FindNode(b->rchild,x);}
}BTNode *LchildNode(BTNode *p)
{return p->lchild;
}BTNode *RchildNode(BTNode *p)
{return p->rchild;
}int BTNodeHeight(BTNode *b)
{int lchildh,rchildh;if (b==NULL) return(0); //空树的高度为0else {lchildh=BTNodeHeight(b->lchild); //求左子树的高度为lchildhrchildh=BTNodeHeight(b->rchild); //求右子树的高度为rchildhreturn (lchildh>rchildh)? (lchildh+1):(rchildh+1);}
}void DispBTree(BTNode *b)
{if (b!=NULL){ printf("%c",b->data);if (b->lchild!=NULL || b->rchild!=NULL){ printf("("); //有孩子结点时才输出(DispBTree(b->lchild); //递归处理左子树if (b->rchild!=NULL) printf(","); //有右孩子结点时才输出,DispBTree(b->rchild); //递归处理右子树printf(")"); //有孩子结点时才输出)}}
}/*以下主函数用做调试
void main()
{BTNode *b;CreateBTree(b,"A(B(D,E),C(,F))");DispBTree(b);printf("\n");
}
*/
图的两种存储结构
//图的两种存储结构
#define INF 32767 //定义∞
#define MAXV 100 //最大顶点个数
typedef char InfoType;//以下定义邻接矩阵类型
typedef struct
{ int no; //顶点编号InfoType info; //顶点其他信息
} VertexType; //顶点类型
typedef struct
{ int edges[MAXV][MAXV]; //邻接矩阵数组int n,e; //顶点数，边数VertexType vexs[MAXV]; //存放顶点信息
} MatGraph; //完整的图邻接矩阵类型//以下定义邻接表类型
typedef struct ANode
{ int adjvex; //该边的邻接点编号struct ANode *nextarc; //指向下一条边的指针int weight; //该边的相关信息，如权值（用整型表示）
} ArcNode; //边节点类型
typedef struct Vnode
{ InfoType info; //顶点其他信息int count; //存放顶点入度,仅仅用于拓扑排序ArcNode *firstarc; //指向第一条边
} VNode; //邻接表头节点类型
typedef struct
{ VNode adjlist[MAXV]; //邻接表头节点数组int n,e; //图中顶点数n和边数e
} AdjGraph; //完整的图邻接表类型
图的基本运算算法
//图的基本运算算法
#include <stdio.h>
#include <malloc.h>
#include "graph.h"//------------------------------------------------------------
//----邻接矩阵的基本运算算法----------------------------------
//------------------------------------------------------------
void CreateMat(MatGraph &g,int A[MAXV][MAXV],int n,int e) //创建图的邻接矩阵
{int i,j;g.n=n; g.e=e;for (i=0;i<g.n;i++)for (j=0;j<g.n;j++)g.edges[i][j]=A[i][j];
}void DispMat(MatGraph g) //输出邻接矩阵g
{int i,j;for (i=0;i<g.n;i++){for (j=0;j<g.n;j++)if (g.edges[i][j]!=INF)printf("%4d",g.edges[i][j]);elseprintf("%4s","∞");printf("\n");}
}//------------------------------------------------------------//------------------------------------------------------------
//----邻接表的基本运算算法------------------------------------
//------------------------------------------------------------
void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e) //创建图的邻接表
{int i,j;ArcNode *p;G=(AdjGraph *)malloc(sizeof(AdjGraph));for (i=0;i<n;i++) //给邻接表中所有头节点的指针域置初值G->adjlist[i].firstarc=NULL;for (i=0;i<n;i++) //检查邻接矩阵中每个元素for (j=n-1;j>=0;j--)if (A[i][j]!=0 && A[i][j]!=INF) //存在一条边{ p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个节点pp->adjvex=j;p->weight=A[i][j];p->nextarc=G->adjlist[i].firstarc; //采用头插法插入节点pG->adjlist[i].firstarc=p;}G->n=n; G->e=n;
}void DispAdj(AdjGraph *G) //输出邻接表G
{int i;ArcNode *p;for (i=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("%3d: ",i);while (p!=NULL){printf("%3d[%d]→",p->adjvex,p->weight);p=p->nextarc;}printf("∧\n");}
}void DestroyAdj(AdjGraph *&G) //销毁图的邻接表
{ int i;ArcNode *pre,*p;for (i=0;i<G->n;i++) //扫描所有的单链表{ pre=G->adjlist[i].firstarc; //p指向第i个单链表的首节点if (pre!=NULL){ p=pre->nextarc;while (p!=NULL) //释放第i个单链表的所有边节点{ free(pre);pre=p; p=p->nextarc;}free(pre);}}free(G); //释放头节点数组
}
//------------------------------------------------------------
Floyd算法
//Floyd算法
#include "graph.cpp"
void Disp(int A[MAXV][MAXV],int path[MAXV][MAXV],int n,int k)
{int i,j;printf("A[%d]\t\t\t\t\t\tpath[%d]\n",k,k);for (i=0;i<n;i++){for (j=0;j<n;j++)if (A[i][j]!=INF)printf("%4d",A[i][j]);elseprintf("%4s","∞");printf("\t\t");for (j=0;j<n;j++)printf("%4d",path[i][j]);printf("\n");}
}void Dispath(MatGraph g,int A[][MAXV],int path[][MAXV])
{ int i,j,k,s;int apath[MAXV],d; //存放一条最短路径中间顶点(反向)及其顶点个数for (i=0;i<g.n;i++)for (j=0;j<g.n;j++){ if (A[i][j]!=INF && i!=j) //若顶点i和j之间存在路径{ printf(" 从%d到%d的路径为:",i,j);k=path[i][j];d=0; apath[d]=j; //路径上添加终点while (k!=-1 && k!=i) //路径上添加中间点{ d++; apath[d]=k;k=path[i][k];}d++; apath[d]=i; //路径上添加起点printf("%d",apath[d]); //输出起点for (s=d-1;s>=0;s--) //输出路径上的中间顶点printf(",%d",apath[s]);printf("\t路径长度为:%d\n",A[i][j]);}}
}void Floyd(MatGraph g) //Floyd算法
{ int A[MAXV][MAXV],path[MAXV][MAXV];int i,j,k;for (i=0;i<g.n;i++)for (j=0;j<g.n;j++) { A[i][j]=g.edges[i][j];if (i!=j && g.edges[i][j]<INF)path[i][j]=i; //顶点i到j有边时elsepath[i][j]=-1; //顶点i到j没有边时}for (k=0;k<g.n;k++) //依次考察所有顶点{printf("k=%d\n",k);for (i=0;i<g.n;i++)for (j=0;j<g.n;j++)if (A[i][j]>A[i][k]+A[k][j]){A[i][j]=A[i][k]+A[k][j]; //修改最短路径长度path[i][j]=path[k][j]; //修改最短路径printf("A[%d][%d]=%d,path[%d][%d]=%d\n",i,j,A[i][j],i,j,path[i][j]);}//Disp(A,path,g.n,k);}Dispath(g,A,path); //输出最短路径
}int main()
{MatGraph g;int A[MAXV][MAXV]={{0, 7, 11, INF,INF, INF},{7, 0, 10, 9, INF, INF},{11, 10, 0, 5, 7, 8},{INF,9, 5, 0, INF, INF},{INF,INF,7, INF,0, 6},{INF,INF,8, INF,6, 0} };int n=6, e=8;CreateMat(g,A,n,e); //建立图的邻接矩阵printf("图G的邻接矩阵:\n");DispMat(g); //输出邻接矩阵printf("各顶点对的最短路径:\n");Floyd(g);return 1;
}
深度优先遍历算法 DFS
//深度优先遍历算法
#include "graph.cpp"
int visited[MAXV]={0};
void DFS(AdjGraph *G,int v)
{ArcNode *p;visited[v]=1; //置已访问标记printf("%d ",v); //输出被访问顶点的编号p=G->adjlist[v].firstarc; //p指向顶点v的第一条弧的弧头结点while (p!=NULL) {if (visited[p->adjvex]==0) //若p->adjvex顶点未访问,递归访问它DFS(G,p->adjvex); p=p->nextarc; //p指向顶点v的下一条弧的弧头结点}
}int main()
{AdjGraph *G;int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};int n=5, e=8;CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表printf("图G的邻接表:\n");DispAdj(G); //输出邻接表Gprintf("深度优先序列:");DFS(G,2);printf("\n");DestroyAdj(G); //销毁邻接表return 1;
}
广度优先遍历算法 BFS
//广度优先遍历算法
#include "graph.cpp"
#define MaxSize 100
//---------------------------------------------------------
//--广度优先遍历中使用队列的基本运算算法-------------------
//---------------------------------------------------------
typedef int ElemType;
typedef struct
{ ElemType data[MaxSize];int front,rear; //队首和队尾指针
} SqQueue;void InitQueue(SqQueue *&q)
{ q=(SqQueue *)malloc (sizeof(SqQueue));q->front=q->rear=0;
}void DestroyQueue(SqQueue *&q)
{free(q);
}bool QueueEmpty(SqQueue *q)
{return(q->front==q->rear);
}bool enQueue(SqQueue *&q,ElemType e)
{ if ((q->rear+1)%MaxSize==q->front) //队满上溢出return false;q->rear=(q->rear+1)%MaxSize;q->data[q->rear]=e;return true;
}bool deQueue(SqQueue *&q,ElemType &e)
{ if (q->front==q->rear) //队空下溢出return false;q->front=(q->front+1)%MaxSize;e=q->data[q->front];return true;
}//---------------------------------------------------------void BFS(AdjGraph *G,int v)
{int w,i;ArcNode *p;SqQueue *qu; //定义环形队列指针InitQueue(qu); //初始化队列int visited[MAXV]; //定义顶点访问标志数组for (i=0;i<G->n;i++) visited[i]=0; //访问标志数组初始化printf("%2d",v); //输出被访问顶点的编号visited[v]=1; //置已访问标记enQueue(qu,v);while (!QueueEmpty(qu)) //队不空循环{ deQueue(qu,w); //出队一个顶点wp=G->adjlist[w].firstarc; //指向w的第一个邻接点while (p!=NULL) //查找w的所有邻接点{ if (visited[p->adjvex]==0) //若当前邻接点未被访问{printf("%2d",p->adjvex); //访问该邻接点visited[p->adjvex]=1; //置已访问标记enQueue(qu,p->adjvex); //该顶点进队}p=p->nextarc; //找下一个邻接顶点}}printf("\n");
}int main()
{AdjGraph *G;int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};int n=5, e=8;CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表printf("图G的邻接表:\n");DispAdj(G); //输出邻接表Gprintf("广度优先序列:");BFS(G,2);printf("\n");DestroyAdj(G); //销毁邻接表return 1;
}
二叉排序树算法
//二叉排序树算法
#include <stdio.h>
#include <malloc.h>
typedef int KeyType;
typedef char InfoType[10];
typedef struct node //记录类型
{KeyType key; //关键字项InfoType data; //其他数据域struct node *lchild,*rchild; //左右孩子指针
} BSTNode;bool InsertBST(BSTNode *&bt,KeyType k)
//在二叉排序树bt中插入一个关键字为k的节点。插入成功返回真，否则返回假
{ if (bt==NULL) //原树为空，新插入的节点为根节点{ bt=(BSTNode *)malloc(sizeof(BSTNode));bt->key=k; bt->lchild=bt->rchild=NULL;return true;}else if (k==bt->key) //树中存在相同关键字的节点，返回假return false;else if (k<bt->key) return InsertBST(bt->lchild,k); //插入到左子树中elsereturn InsertBST(bt->rchild,k); //插入到右子树中
}BSTNode *CreateBST(KeyType A[],int n) //创建二叉排序树
//返回BST树根节点指针
{ BSTNode *bt=NULL; //初始时bt为空树int i=0;while (i<n){ InsertBST(bt,A[i]); //将关键字A[i]插入二叉排序树bt中i++;}return bt; //返回建立的二叉排序树的根指针
}void DispBST(BSTNode *bt) //输出一棵排序二叉树
{if (bt!=NULL){ printf("%d",bt->key);if (bt->lchild!=NULL || bt->rchild!=NULL){ printf("("); //有孩子节点时才输出(DispBST(bt->lchild); //递归处理左子树if (bt->rchild!=NULL) printf(","); //有右孩子节点时才输出,DispBST(bt->rchild); //递归处理右子树printf(")"); //有孩子节点时才输出)}}
}BSTNode *SearchBST(BSTNode *bt,KeyType k)
{ if (bt==NULL || bt->key==k) //递归终结条件return bt;if (k<bt->key)return SearchBST(bt->lchild,k); //在左子树中递归查找elsereturn SearchBST(bt->rchild,k); //在右子树中递归查找
}BSTNode *SearchBST1(BSTNode *bt,KeyType k,BSTNode *f1,BSTNode *&f)
/*在bt中查找关键字为k的节点,若查找成功,该函数返回该节点的指针,
f返回其双亲节点;否则,该函数返回NULL。
其调用方法如下:SearchBST(bt,x,NULL,f);
这里的第3个参数f1仅作中间参数,用于求f,初始设为NULL*/
{ if (bt==NULL){ f=NULL;return(NULL);}else if (k==bt->key) { f=f1;return(bt);}else if (k<bt->key)return SearchBST1(bt->lchild,k,bt,f); //在左子树中递归查找elsereturn SearchBST1(bt->rchild,k,bt,f); //在右子树中递归查找
}void Delete1(BSTNode *p,BSTNode *&r) //当被删p节点有左右子树时的删除过程
{BSTNode *q;if (r->rchild!=NULL)Delete1(p,r->rchild); //递归找最右下节点relse //找到了最右下节点r{ p->key=r->key; //将r节点的值赋给节点pq=r; r=r->lchild; //直接将其左子树的根节点放在被删节点的位置上free(q); //释放原节点r的空间}
}void Delete(BSTNode *&p) //从二叉排序树中删除p节点
{BSTNode *q;if (p->rchild==NULL) //p节点没有右子树的情况{q=p;p=p->lchild; //直接将其右子树的根节点放在被删节点的位置上free(q); }else if (p->lchild==NULL) //p节点没有左子树的情况{q=p;p=p->rchild; //将p节点的右子树作为双亲节点的相应子树free(q); }else Delete1(p,p->lchild); //p节点既没有左子树又没有右子树的情况
}int DeleteBST(BSTNode *&bt,KeyType k) //在bt中删除关键字为k的节点
{if (bt==NULL) return 0; //空树删除失败else { if (k<bt->key) return DeleteBST(bt->lchild,k); //递归在左子树中删除为k的节点else if (k>bt->key) return DeleteBST(bt->rchild,k); //递归在右子树中删除为k的节点else {Delete(bt); //调用Delete(bt)函数删除*bt节点return 1;}}
}void DestroyBST(BSTNode *&bt) //销毁二叉排序树bt
{if (bt!=NULL){DestroyBST(bt->lchild);DestroyBST(bt->rchild);free(bt);}
}
