1、已知线性表A,B,C 是递增有序的线性表。要求对A 表作如下运算：删去那些既在B 表 中出现又在C 表中出现的元素。A,B,C 以顺序表存储。
#include
#include
#define maxsize 100
typedef int datatype;
typedef struct
{
int createlist(seqlist *L)
{
}
seqlist same(seqlist *A, seqlist *B)
{
}
seqlist delet(seqlist *A, seqlist *B)
{
int i,j,k; for(i=0;ilength;i++) for(j=0;jlength;j++) if(A->data[i]==B->data[j]) seqlist C; int i,j,k=0; for(i=0;ilength;i++) for(j=0;jlength;j++) if(A->data[i]==B->data[j]) { } C.data[k]=A->data[i]; k++; int i; printf("please input the length of the list: "); scanf("%d",&L->length); printf("please input a list of number!\n"); for(i=0;ilength;i++) scanf("%d",&L->data[i]); return 0; datatype data[maxsize]; int length; }seqlist; C.length=k; return C;
}
} for(k=i;klength-1;k++) A->data[k]=A->data[k+1]; A->length--; return *A;
void dsip(seqlist *L)
{
}
int main()
{
} seqlist A,B,C; createlist(&A); createlist(&B); createlist(&C); printf("before:\n"); dsip(&A); C=same(&B,&C); A=delet(&A,&C); printf("after:\n"); dsip(&A); return 0; int i; for(i=0;ilength;i++) printf("%d ",L->data[i]); printf("\n");
2、已知线性表A,B,C 是递增有序的线性表。要求对A 表作如下运算：线性表A 中出现的元素，在线性表B 中也出现，则将A 中该元素删除。A ，B 以顺序表存储。
#include
#include
#define maxsize 100
typedef int datatype;
typedef struct
{
int createlist(seqlist *L)
{ datatype data[maxsize]; int length; }seqlist;
}
printf("please input the length of the list: "); scanf("%d",&L->length); printf("please input a list of number!\n"); for(i=0;ilength;i++) scanf("%d",&L->data[i]); return 0;
seqlist delet(seqlist *A, seqlist *B)
{
}
void dsip(seqlist *L)
{
}
int main()
{
} seqlist A,B; createlist(&A); createlist(&B); A=delet(&A,&B); printf("删除后："); dsip(&A); return 0; int i; for(i=0;ilength;i++) printf("%d ",L->data[i]); printf("\n"); int i,j,k; for(i=0;ilength;i++) for(j=0;jlength;j++) if(A->data[i]==B->data[j]) { } for(k=i;klength-1;k++) A->data[k]=A->data[k+1]; A->length--; return *A;
3、顺序表A 和顺序表B 的元素都是非递减排列，利用线性表的基本运算，将它们合并成一个顺序表C ，要求C 也是非递减排列。A ，B 表的值可以自行设计。
#include
#include
#define ListSize 100
#define OVERFLOW -1
#define ERROR 0
#define OK 1
#define DataType int
typedef int status;
typedef struct
{
DataType *list;
int listSize;
int length;
}SeqList;
int InitList(SeqList *L)
{
(*L).list=(DataType *) malloc(ListSize*sizeof(DataType));
if (!(*L).list)
exit(OVERFLOW);
(*L).length=0;
(*L).listSize=ListSize;
return OK; //线性表的初始化
}
void mergelist(SeqList la,SeqList lb,SeqList lc)
{
int *pa,*pb,*pc,*pa_last,*pb_last; int i; pa=la.list; lc.listSize=la.length+lb.length; pc=lc.list=(DataType *)malloc(lc.listSize*sizeof(DataType)); if(!lc.list) exit(0); pa_last=la.list+la.length-1; pb_last=lb.list+lb.length-1; while(pa
} printf("%d ",lc.list[i]); printf("\n");
int main()
{
} mergelist(la,lb,lc); return 0; } SeqList la,lb,lc; int i; la.length=0; lb.length=0; if(InitList(&la)) { } if(InitList(&lb)) { printf("输入顺序表lb:\n"); { } scanf("%d",&lb.list[i]); lb.length++; for(i=0;i
4、已知线性表La 和Lb 的元素按值非递减排列。归并La 和Lb 得到新的线性表Lc ，Lc 的元素也按值非递减排列。采用链式结构来实现。La 、Lb 表的值可以自行设计。
#include
#include
typedef int ElemType; // 定义ElemType 为整型
typedef struct LNode
{
ElemType data; struct LNode *next;
}LNode,*LinkList;
void CreateList(LinkList &L,int n)
{ // 正位序(结点插在表尾) 输入n 个元素的值，建立带表头结点的单链线性表L
int i;
LinkList p,q;
L=(LinkList)malloc(sizeof(LNode)); // 生成头结点
L->next=NULL; // 先建立一个带头结点的空单链表
q=L; // q指向空表的头结点(相当于尾结点)
printf("请输入%d个数据\n",n);
for(i=1;i
{
p=(LinkList)malloc(sizeof(LNode)); // 生成新结点 scanf("%d",&p->data); // 给新结点输入元素值 q->next=p; // 将新结点插在表尾 q=q->next; // q指向尾结点
}
p->next=NULL; // 最后一个结点的指针域为空
}
void MergeList(LinkList La,LinkList &Lb,LinkList &Lc) // 算法2.12
{ // 已知单链线性表La 和Lb 的元素按值非递减排列。
// 归并La 和Lb 得到新的单链线性表Lc ，Lc 的元素也按值非递减排列。(销毁Lb ，Lc 即新的La)
while(pa&&pb) // La和Lb 中的元素都未比较完
if(pa->datadata) // La的当前元素不大于Lb 的当前元素
{
}
else // Lb的当前元素小于La 的当前元素
{
}
pc->next=pa?pa:pb; // 插入剩余段
}
free(Lb); //释放Lb 的头结点 Lb=NULL; // Lb不再指向任何结点 pc->next=pb; // pb所指结点归并到Lc 中 pc=pb; // pc指向表Lc 的最后一个结点 pb=pb->next; // 表Lb 的下一个结点成为待比较结点 pc->next=pa; // 将pa 所指结点归并到Lc 中 pc=pa; // pc指向表Lc 的最后一个结点 pa=pa->next; // 表La 的下一个结点成为待比较结点 LinkList pa=La->next,pb=Lb->next,pc; // pa、pb 分别指向La 、Lb 的首元结点(待比较结点) Lc=pc=La; // 用La 的头结点作为Lc 的头结点，pc 指向La 的头结点(Lc的尾结点)
void Printf_L(LinkList&L)
{
}
void main()
{
}
int n=5; LinkList La,Lb,Lc; printf("按非递减顺序，"); CreateList(La,n); // 根据输入顺序，正位序建立线性表 printf("按非递减顺序，"); CreateList(Lb,n); // 根据输入顺序，逆位序建立线性表 printf("La="); Printf_L(La); // 输出链表La 的内容 printf("Lb="); Printf_L(Lb); // 输出链表Lb 的内容 MergeList(La,Lb,Lc); // 按非递减顺序归并La 和Lb ，得到新表Lc printf("Lc="); Printf_L(Lc); // 输出链表Lc 的内容 LNode*p; p=L->next; while(p!=NULL) { } printf("\n"); printf("%d ",p->data); p=p->next;
6、编写一个程序，实现双链表的各种基本运算（双链表的元素类型为char ），并在此基础上设计一个程序，完成如下功能：
（1）初始化双链表h ；
（2）采用尾插法依次插入元素a ，b ，c ，d ，e ；
（3）删除h 的第3个元素；
#include "stdio.h"
#include "malloc.h"
typedef char ElemType;
typedef struct DNode //定义双链表结点类型
{
ElemType data; struct DNode *prior; //指向前驱结点 struct DNode *next; //指向后继结点
} DLinkList;
/*初始化双链表*/
void InitList(DLinkList *&L)
{
}
/*向双链表L 的第i 个位置插入数据e*/
int ListInsert(DLinkList *&L,int i,ElemType e)
{
}
/*释放双链表*/
void DestroyList(DLinkList *&L)
{
DLinkList *p=L, *q=p->next; { } free(p); p=q; q=q->next; while(q!=NULL) int j=0; DLinkList *p=L,*s; while(jdata=e; s->next=p->next; if(p->next!=NULL) p->next->prior=s; s->prior=p; p->next=s; return 1; return 0; j++; p=p->next; L=(DLinkList *)malloc(sizeof(DLinkList)); L->prior=L->next=NULL;
free(p);
}
/*从双链表L 的第i 个位置删除数据e*/
int ListDelete(DLinkList *&L,int i,ElemType &e)
{
}
/*打印双链表*/
void DispList(DLinkList *L)
{
DLinkList *p=L->next;
while(p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
void main()
{
DLinkList *h; ElemType e; int j=0; DLinkList *p=L,*q; while(jnext; if(q==NULL) return 0; e=q->data; p->next=q->next; if(p->next!=NULL) p->next->prior=p; free(q); return 1; return 0; j++; p=p->next;
} printf("双链表的基本运算如下:\n"); printf(" (1)初始化双链表h\n"); InitList(h); printf(" (2)依次采用尾插法插入a,b,c,d,e 元素\n"); ListInsert(h,1,'a'); ListInsert(h,2,'b'); ListInsert(h,3,'c'); ListInsert(h,4,'d'); ListInsert(h,5,'e'); printf(" (3)输出双链表h:"); DispList(h); printf(" (4)删除h 的第3个元素\n"); ListDelete(h,3,e); printf(" (5)输出双链表h:"); DispList(h); printf(" (6)释放双链表h\n"); DestroyList(h);
7、利用堆栈实现进制转换，如10进制到8进制的转换（1348)10 = (2504) 8 #include
#include
#include
#define STACK_INIT_SIZE 100 // 存储空间的初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
struct SqStack
{
int *base;
int *top;
int stacksize; //当前已分配的存储空间
};
/*构造一个空栈*/
void InitStack(struct SqStack *S)
{
S->base = (int *)malloc(STACK_INIT_SIZE * sizeof (int));
if(!(S->base)) //存储分配失败
{
exit(0);
printf("内存分配错误!\n");
}
S->top = S->base ;
S->stacksize = STACKINCREMENT ;
}
/*入栈*/
void Push(struct SqStack *S, int e)
{
if(S->top - S->base >= S->stacksize) //栈满溢出
{
S->base = (int *)realloc(S->base,(STACKINCREMENT+STACK_INIT_SIZE)* sizeof (int));
//重新分配存储空间
if(!(S->base))
{
exit(0);
printf("存储失败\n");
}
S->top = S->base + S->stacksize ;
S->stacksize = S->stacksize + STACKINCREMENT ;
}
* (S->top++) = e;
}
/*出栈*/
int Pop(struct SqStack *S, int e)
{
if(S->top == S->base) //空栈
printf("此栈为空栈\n");
e = *( -- S->top);
return(e);
}
/*判断栈是否为空*/
int StackEmpty(struct SqStack *S)
{
if(S->top == S->base)
return 1;
else
return 0;
}
/*主函数*/
int main(int argc, char *argv[])
{
int n = 0;
int e = 1;
struct SqStack *Change;
Change = (struct SqStack *)malloc(sizeof(struct SqStack));
InitStack(Change);
printf("Please input the Primitive num (十进制数):");
scanf("%d",&n);
while(n)
{
Push(Change , n%8 );
n = n/8;
}
printf("The result is ( 八 进 制 数 ) : ");
while(!StackEmpty(Change))
{
e = Pop(Change,e);
printf("%d",e);
}
printf("\n");
if(e/8 == 0 )
printf("此栈已经为空了\n");
system("PAUSE");
return 0;
}
8、实现链栈的基本操作，然后利用堆栈将一个线性表中的元素按逆序重新存放。例如原来的顺序为 12，8，6，4，2，要求改为 2，4，6，8，12。
#include
#include
#include
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
#define OK 1
#define ERROR 0
typedef int Status;
typedef int SElemType;
#define ListSize 100
typedef int DataType;
typedef struct
{
typedef struct SqStack
{
SElemType *base;/* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ DataType list[ListSize]; int length; }SeqList;/*顺序表*/
}SqStack; /* 顺序栈 */
/*初始化顺序表*/
SeqList InitList()
{
int i;
DataType value[]={12,8,6,4,2};
SeqList L;
L.length=0;
for(i=0;i
{
L.list[i] = value[i];
L.length++;
}
return L;
}
/*顺序表输出函数*/
void displayList(SeqList *sq)
{
int index;
if(sq->length==0) return;
for(index=0;indexlength;index++)
{
printf("%4d",sq->list[index]);
}
}
Status InitStack(SqStack &S)
{ /* 构造一个空栈 S */
}
Status DestroyStack(SqStack &S)
{ /* 销毁栈 S ，S 不再存在 */
free(S.base); S.base=NULL; S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(-1); /* 存储分配失败 */ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; printf("\n");
}
S.stacksize=0; return OK;
Status Push(SqStack &S,SElemType e)
{ /* 插入元素 e 为新的栈顶元素 */
}
Status StackEmpty(SqStack S)
{ /* 若栈 S 为空栈，则返回 TRUE ，否则返回 FALSE */
} if(S.top==S.base) return OK; else return ERROR; if(S.top-S.base>=S.stacksize) /* 栈满，追加存储空间 */ { S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) exit(-1); /* 存储分配失败 */ S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *(S.top)++=e; return OK;
Status Pop(SqStack &S,SElemType &e)
{ /* 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK ；否则返回 ERROR */
}
void reverse(SqStack &S,SeqList &L)
{
SElemType e; DataType f; int i=0; while(!StackEmpty(S)) /* 当栈不空 */ { Pop(S,e); //f=e;/* 弹出栈顶元素且赋值给 e */ if(S.top==S.base) return ERROR; e=*--S.top; return OK;
}
} int main()
{
} Push(S,12); Push(S,8); Push(S,6); Push(S,4); Push(S,2); reverse(S,L); printf("利用堆栈反序线性表后："); displayList(&L); DestroyStack(S); return 0; SqStack S; InitStack(S); SeqList L; L = InitList(); printf("初始线性表L 元素为："); displayList(&L);
9、实现链队的各种基本运算，依次进队元素a ，b ，c ；然后出队一个元素，并输出该元素；输出链队的元素个数；
#include
#include
#include
typedef char ElemType;
typedef struct qnode
{
ElemType data;
struct qnode *next;
}QNode;
typedef struct
{
QNode *front;
QNode *rear;
}LiQueue;
//初始化队列
void InitQueue(LiQueue *&q)
{
q=(LiQueue *)malloc(sizeof(LiQueue));
q->front=q->rear=NULL;
}
//销毁队列
void DestroyQueue(LiQueue *&q)
{
QNode *p=q->front,*r;
if(p!=NULL)
{
r=p->next;
}
free(p);
free(q);
}
//进队列
void enQueue(LiQueue *&q,ElemType e)
{
QNode *p;
p=(QNode *)malloc(sizeof(QNode));
p->data=e;
p->next=NULL;
if(q->rear==NULL)
q->front=q->rear=p;
else
{
q->rear->next=p;
}
}
//出队列
bool deQueue(LiQueue *&q,ElemType &e)
{
QNode *t;
if(q->rear==NULL)
return false;
t=q->front;
if(q->front==q->rear) q->rear=p; while(r!=NULL) { free(p); p=r;r=p->next; }
q->front=q->rear=NULL;
else
q->front=q->front->next;
e=t->data;
free(t);
return true;
}
int QueueLength(LiQueue *q) //输出链队的元素个数
{
}
void main()
{
ElemType e;
LiQueue *q;
printf("链队的各种基本运算如下：\n");
printf("(1)初始化链队q");
InitQueue(q);
printf("\n");
printf("(3)依次进队元素a ，b ，c ；");
enQueue(q,'a');
enQueue(q,'b');
enQueue(q,'c');
printf("\n");
printf("(4)出队一个元素，并输出该元素:");
deQueue(q,e);
printf("%c",e);
printf("\n");
printf("(5)输出链队q 的元素个数：");
printf("%d\n",QueueLength(q));
printf("\n");
printf("(9)释放链队");
DestroyQueue(q);
printf("\n");
} int n=0; QNode *p=q->front; while(p!=NULL) { } return(n); n++; p=p->next;
10、若 x 和 y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。 提示：两个串相等表示对应的字符必须都相同，所以扫描两串，逐一比较相应位置的字符，若相同继续比较直到全部比较完毕，如果都相同则表示两串相等，否则表示两串不相等。 #include
#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 40 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型, 其值是函数结果状态代码，如OK 等 */
typedef char String[MAXSIZE+1]; /* 0号单元存放串的长度 */
/* 输出字符串T */ void StrPrint(String T) { /* 生成一个其值等于chars 的串T */ Status StrAssign(String T,char *chars) { int i; if(strlen(chars)>MAXSIZE) return ERROR; else { T[0]=strlen(chars); for(i=1;iT, 则返回值>0;若S=T, 则返回值=0;若S
int i;
for(i=1;i
if(S[i]!=T[i])
return S[i]-T[i];
return S[0]-T[0];
}
int main() { int i; String x,y; printf("(1)生成串x:"); StrAssign(x,"i take a test"); StrPrint(x); printf("(2)生成串y:"); StrAssign(x,"i get good grage"); StrPrint(x); printf("(3)比较串x 和串y:\n"); i=StrCompare(x,y); char s; if(i '; printf("串x%c串y\n",s); }
11、实现顺序串的基本运算，并在此基础上设计一个程序，完成如下功能：
建立串s=“abcdefghefghijklmn ”和串s1=“xyz ”，将串s 的第2个字符开始的5个字符替换成串s1而产生串s2。
#include
#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 40 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型, 其值是函数结果状态代码，如OK 等 */
typedef char String[MAXSIZE+1]; /* 0号单元存放串的长度 */
/* 输出字符串T */ void StrPrint(String T) { /* 生成一个其值等于chars 的串T */ Status StrAssign(String T,char *chars) { int i; if(strlen(chars)>MAXSIZE) return ERROR; else { T[0]=strlen(chars); for(i=1;iT, 则返回值>0;若S=T, 则返回值=0;若S
int i;
for(i=1;i
return S[i]-T[i]; return S[0]-T[0];
}
int main() { int i; String x,y; char s; StrAssign(x,"i take a test"); StrPrint(x); printf("(1)生成串x:");
printf("(2)生成串y:"); StrAssign(x,"i get good grage"); StrPrint(x); printf("(3)比较串x 和串y:\n"); i=StrCompare(x,y); if(i '; printf("串x%c串y\n",s); }
13、二叉树采用链接存储结构，试设计一个按层次顺序（同一层次自左至右）遍历二叉树的算法。
提示：算法要采用一个队列 q，先将二叉树根结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。
#include
#include
#include
#include
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf 为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针 T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点 T->data=ch; T->rchild=CreatBinTree(); //构造右子树 T->lchild=CreatBinTree(); //构造左子树 return(T); else{
}
}
//====利用" 先进先出" （FIFO ）队列，按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
}
//==========主函数=================
void main()
{
BinTree root;
int i;
/printf("\n");
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列，
//用#代表虚结点，如ABD###CE##F## root=CreatBinTree(); //创建二叉树，返回根结点
}
14、编写程序，输出相应图的DFS 结果。
} front=(front+1)%NodeNum; p=cq[front]; //出队 printf("%c",p->data); //出队，输出结点的值 if(p->lchild!=NULL){ cq[rear]=p->lchild; //左子树入队 } if(p->rchild!=NULL){ cq[rear]=p->rchild; //右子树入队 rear=(rear+1)%NodeNum; rear=(rear+1)%NodeNum; } printf("LevePrint Bin_Tree:"); Levelorder(root); //按层次遍历
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定义最大顶点数
typedef struct{
char vexs[MaxVertexNum]; //顶点表
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表
int n,e; //图中的顶点数n 和边数e
}MGraph; //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;in;i++)
{
scanf("%c",&a); G->vexs[i]=a; //读入顶点信息，建立顶点表
}
for(i=0;in;i++)
for(j=0;jn;j++) G->edges[i][j]=0; //初始化邻接矩阵
printf("Input edges,Creat Adjacency Matrix\n");
for(k=0;ke;k++) { //读入e 条边，建立邻接矩阵
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======
void DFSM(MGraph *G,int i)
{ //以Vi 为出发点对邻接矩阵表示的图G 进行DFS 搜索，邻接矩阵是0，1矩阵 int j;
printf("%c",G->vexs[i]); //访问顶点Vi
visited[i]=TRUE; //置已访问标志
for(j=0;jn;j++) //依次搜索Vi 的邻接点
}
void DFS(MGraph *G) if(G->edges[i][j]==1 && ! visited[j]) DFSM(G,j); //（Vi ，Vj ）∈E ，且Vj 未访问过，故Vj 为新出发点 scanf("%d%d",&i,&j); //输入边（Vi ，Vj ）的顶点序号 G->edges[i][j]=1; G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 }
int i;
for(i=0;in;i++)
}
//==========main=====
void main()
{
int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //为图G 申请内存空间
CreatMGraph(G); //建立邻接矩阵
printf("Print Graph DFS: ");
DFS(G); //深度优先遍历
printf("\n");
}
15、编写程序，输出相应图的BFS 结果。
visited[i]=FALSE; //标志向量初始化 if(!visited[i]) //Vi未访问过 DFSM(G,i); //以Vi 为源点开始DFS 搜索 for(i=0;in;i++)
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定义最大顶点数
typedef struct{
char vexs[MaxVertexNum]; //顶点表
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表
int n,e; //图中的顶点数n 和边数e
}MGraph; //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;in;i++)
{
G->vexs[i]=a; //读入顶点信息，建立顶点表
}
for(i=0;in;i++)
for(j=0;jn;j++) G->edges[i][j]=0; //初始化邻接矩阵
printf("Input edges,Creat Adjacency Matrix\n");
for(k=0;ke;k++) { //读入e 条边，建立邻接矩阵
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//===========BFS：广度优先遍历=======
void BFS(MGraph *G,int k)
{ //以Vk 为源点对用邻接矩阵表示的图G 进行广度优先搜索 int i,j,f=0,r=0;
int cq[MaxVertexNum]; //定义队列
for(i=0;in;i++)
visited[i]=FALSE; //标志向量初始化 for(i=0;in;i++) cq[i]=-1; //队列初始化
printf("%c",G->vexs[k]); //访问源点Vk
visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队 while(cq[f]!=-1) { //队非空则执行
}
//==========main=====
void main()
{
int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //为图G 申请内存空间
CreatMGraph(G); //建立邻接矩阵 i=cq[f]; f=f+1; //Vf出队 for(j=0;jn;j++) //依次Vi 的邻接点Vj if(G->edges[i][j]==1 && !visited[j]) { //Vj未访问 printf("%c",G->vexs[j]); //访问Vj visited[j]=TRUE; r=r+1; cq[r]=j; //访问过Vj 入队 scanf("%d%d",&i,&j); //输入边（Vi ，Vj ）的顶点序号 G->edges[i][j]=1; G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 } } }
printf("Print Graph BFS: ");
BFS(G,4); //以序号为3的顶点开始广度优先遍历
printf("\n");
}
16、编写程序，输出该树的前序遍历序列
#include
#include
#include
#include
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf 为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置========== BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T) { return(NULL); //读入#，返回空指针 T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点 T->data=ch; T->rchild=CreatBinTree(); //构造右子树 T->lchild=CreatBinTree(); //构造左子树 return(T); else{ }
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//==========主函数=================
void main()
{
BinTree root;
int i;
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列， // 用#代表虚结点，如ABD###CE##F## root=CreatBinTree(); //创建二叉树，返回根结点 式，输入序号。
printf("\t1: Preorder Traversal\n");
printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
printf("\n");
}
//从菜单中选择遍历方
1、已知线性表A,B,C 是递增有序的线性表。要求对A 表作如下运算：删去那些既在B 表 中出现又在C 表中出现的元素。A,B,C 以顺序表存储。
#include
#include
#define maxsize 100
typedef int datatype;
typedef struct
{
int createlist(seqlist *L)
{
}
seqlist same(seqlist *A, seqlist *B)
{
}
seqlist delet(seqlist *A, seqlist *B)
{
int i,j,k; for(i=0;ilength;i++) for(j=0;jlength;j++) if(A->data[i]==B->data[j]) seqlist C; int i,j,k=0; for(i=0;ilength;i++) for(j=0;jlength;j++) if(A->data[i]==B->data[j]) { } C.data[k]=A->data[i]; k++; int i; printf("please input the length of the list: "); scanf("%d",&L->length); printf("please input a list of number!\n"); for(i=0;ilength;i++) scanf("%d",&L->data[i]); return 0; datatype data[maxsize]; int length; }seqlist; C.length=k; return C;
}
} for(k=i;klength-1;k++) A->data[k]=A->data[k+1]; A->length--; return *A;
void dsip(seqlist *L)
{
}
int main()
{
} seqlist A,B,C; createlist(&A); createlist(&B); createlist(&C); printf("before:\n"); dsip(&A); C=same(&B,&C); A=delet(&A,&C); printf("after:\n"); dsip(&A); return 0; int i; for(i=0;ilength;i++) printf("%d ",L->data[i]); printf("\n");
2、已知线性表A,B,C 是递增有序的线性表。要求对A 表作如下运算：线性表A 中出现的元素，在线性表B 中也出现，则将A 中该元素删除。A ，B 以顺序表存储。
#include
#include
#define maxsize 100
typedef int datatype;
typedef struct
{
int createlist(seqlist *L)
{ datatype data[maxsize]; int length; }seqlist;
}
printf("please input the length of the list: "); scanf("%d",&L->length); printf("please input a list of number!\n"); for(i=0;ilength;i++) scanf("%d",&L->data[i]); return 0;
seqlist delet(seqlist *A, seqlist *B)
{
}
void dsip(seqlist *L)
{
}
int main()
{
} seqlist A,B; createlist(&A); createlist(&B); A=delet(&A,&B); printf("删除后："); dsip(&A); return 0; int i; for(i=0;ilength;i++) printf("%d ",L->data[i]); printf("\n"); int i,j,k; for(i=0;ilength;i++) for(j=0;jlength;j++) if(A->data[i]==B->data[j]) { } for(k=i;klength-1;k++) A->data[k]=A->data[k+1]; A->length--; return *A;
3、顺序表A 和顺序表B 的元素都是非递减排列，利用线性表的基本运算，将它们合并成一个顺序表C ，要求C 也是非递减排列。A ，B 表的值可以自行设计。
#include
#include
#define ListSize 100
#define OVERFLOW -1
#define ERROR 0
#define OK 1
#define DataType int
typedef int status;
typedef struct
{
DataType *list;
int listSize;
int length;
}SeqList;
int InitList(SeqList *L)
{
(*L).list=(DataType *) malloc(ListSize*sizeof(DataType));
if (!(*L).list)
exit(OVERFLOW);
(*L).length=0;
(*L).listSize=ListSize;
return OK; //线性表的初始化
}
void mergelist(SeqList la,SeqList lb,SeqList lc)
{
int *pa,*pb,*pc,*pa_last,*pb_last; int i; pa=la.list; lc.listSize=la.length+lb.length; pc=lc.list=(DataType *)malloc(lc.listSize*sizeof(DataType)); if(!lc.list) exit(0); pa_last=la.list+la.length-1; pb_last=lb.list+lb.length-1; while(pa
} printf("%d ",lc.list[i]); printf("\n");
int main()
{
} mergelist(la,lb,lc); return 0; } SeqList la,lb,lc; int i; la.length=0; lb.length=0; if(InitList(&la)) { } if(InitList(&lb)) { printf("输入顺序表lb:\n"); { } scanf("%d",&lb.list[i]); lb.length++; for(i=0;i
4、已知线性表La 和Lb 的元素按值非递减排列。归并La 和Lb 得到新的线性表Lc ，Lc 的元素也按值非递减排列。采用链式结构来实现。La 、Lb 表的值可以自行设计。
#include
#include
typedef int ElemType; // 定义ElemType 为整型
typedef struct LNode
{
ElemType data; struct LNode *next;
}LNode,*LinkList;
void CreateList(LinkList &L,int n)
{ // 正位序(结点插在表尾) 输入n 个元素的值，建立带表头结点的单链线性表L
int i;
LinkList p,q;
L=(LinkList)malloc(sizeof(LNode)); // 生成头结点
L->next=NULL; // 先建立一个带头结点的空单链表
q=L; // q指向空表的头结点(相当于尾结点)
printf("请输入%d个数据\n",n);
for(i=1;i
{
p=(LinkList)malloc(sizeof(LNode)); // 生成新结点 scanf("%d",&p->data); // 给新结点输入元素值 q->next=p; // 将新结点插在表尾 q=q->next; // q指向尾结点
}
p->next=NULL; // 最后一个结点的指针域为空
}
void MergeList(LinkList La,LinkList &Lb,LinkList &Lc) // 算法2.12
{ // 已知单链线性表La 和Lb 的元素按值非递减排列。
// 归并La 和Lb 得到新的单链线性表Lc ，Lc 的元素也按值非递减排列。(销毁Lb ，Lc 即新的La)
while(pa&&pb) // La和Lb 中的元素都未比较完
if(pa->datadata) // La的当前元素不大于Lb 的当前元素
{
}
else // Lb的当前元素小于La 的当前元素
{
}
pc->next=pa?pa:pb; // 插入剩余段
}
free(Lb); //释放Lb 的头结点 Lb=NULL; // Lb不再指向任何结点 pc->next=pb; // pb所指结点归并到Lc 中 pc=pb; // pc指向表Lc 的最后一个结点 pb=pb->next; // 表Lb 的下一个结点成为待比较结点 pc->next=pa; // 将pa 所指结点归并到Lc 中 pc=pa; // pc指向表Lc 的最后一个结点 pa=pa->next; // 表La 的下一个结点成为待比较结点 LinkList pa=La->next,pb=Lb->next,pc; // pa、pb 分别指向La 、Lb 的首元结点(待比较结点) Lc=pc=La; // 用La 的头结点作为Lc 的头结点，pc 指向La 的头结点(Lc的尾结点)
void Printf_L(LinkList&L)
{
}
void main()
{
}
int n=5; LinkList La,Lb,Lc; printf("按非递减顺序，"); CreateList(La,n); // 根据输入顺序，正位序建立线性表 printf("按非递减顺序，"); CreateList(Lb,n); // 根据输入顺序，逆位序建立线性表 printf("La="); Printf_L(La); // 输出链表La 的内容 printf("Lb="); Printf_L(Lb); // 输出链表Lb 的内容 MergeList(La,Lb,Lc); // 按非递减顺序归并La 和Lb ，得到新表Lc printf("Lc="); Printf_L(Lc); // 输出链表Lc 的内容 LNode*p; p=L->next; while(p!=NULL) { } printf("\n"); printf("%d ",p->data); p=p->next;
6、编写一个程序，实现双链表的各种基本运算（双链表的元素类型为char ），并在此基础上设计一个程序，完成如下功能：
（1）初始化双链表h ；
（2）采用尾插法依次插入元素a ，b ，c ，d ，e ；
（3）删除h 的第3个元素；
#include "stdio.h"
#include "malloc.h"
typedef char ElemType;
typedef struct DNode //定义双链表结点类型
{
ElemType data; struct DNode *prior; //指向前驱结点 struct DNode *next; //指向后继结点
} DLinkList;
/*初始化双链表*/
void InitList(DLinkList *&L)
{
}
/*向双链表L 的第i 个位置插入数据e*/
int ListInsert(DLinkList *&L,int i,ElemType e)
{
}
/*释放双链表*/
void DestroyList(DLinkList *&L)
{
DLinkList *p=L, *q=p->next; { } free(p); p=q; q=q->next; while(q!=NULL) int j=0; DLinkList *p=L,*s; while(jdata=e; s->next=p->next; if(p->next!=NULL) p->next->prior=s; s->prior=p; p->next=s; return 1; return 0; j++; p=p->next; L=(DLinkList *)malloc(sizeof(DLinkList)); L->prior=L->next=NULL;
free(p);
}
/*从双链表L 的第i 个位置删除数据e*/
int ListDelete(DLinkList *&L,int i,ElemType &e)
{
}
/*打印双链表*/
void DispList(DLinkList *L)
{
DLinkList *p=L->next;
while(p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
void main()
{
DLinkList *h; ElemType e; int j=0; DLinkList *p=L,*q; while(jnext; if(q==NULL) return 0; e=q->data; p->next=q->next; if(p->next!=NULL) p->next->prior=p; free(q); return 1; return 0; j++; p=p->next;
} printf("双链表的基本运算如下:\n"); printf(" (1)初始化双链表h\n"); InitList(h); printf(" (2)依次采用尾插法插入a,b,c,d,e 元素\n"); ListInsert(h,1,'a'); ListInsert(h,2,'b'); ListInsert(h,3,'c'); ListInsert(h,4,'d'); ListInsert(h,5,'e'); printf(" (3)输出双链表h:"); DispList(h); printf(" (4)删除h 的第3个元素\n"); ListDelete(h,3,e); printf(" (5)输出双链表h:"); DispList(h); printf(" (6)释放双链表h\n"); DestroyList(h);
7、利用堆栈实现进制转换，如10进制到8进制的转换（1348)10 = (2504) 8 #include
#include
#include
#define STACK_INIT_SIZE 100 // 存储空间的初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
struct SqStack
{
int *base;
int *top;
int stacksize; //当前已分配的存储空间
};
/*构造一个空栈*/
void InitStack(struct SqStack *S)
{
S->base = (int *)malloc(STACK_INIT_SIZE * sizeof (int));
if(!(S->base)) //存储分配失败
{
exit(0);
printf("内存分配错误!\n");
}
S->top = S->base ;
S->stacksize = STACKINCREMENT ;
}
/*入栈*/
void Push(struct SqStack *S, int e)
{
if(S->top - S->base >= S->stacksize) //栈满溢出
{
S->base = (int *)realloc(S->base,(STACKINCREMENT+STACK_INIT_SIZE)* sizeof (int));
//重新分配存储空间
if(!(S->base))
{
exit(0);
printf("存储失败\n");
}
S->top = S->base + S->stacksize ;
S->stacksize = S->stacksize + STACKINCREMENT ;
}
* (S->top++) = e;
}
/*出栈*/
int Pop(struct SqStack *S, int e)
{
if(S->top == S->base) //空栈
printf("此栈为空栈\n");
e = *( -- S->top);
return(e);
}
/*判断栈是否为空*/
int StackEmpty(struct SqStack *S)
{
if(S->top == S->base)
return 1;
else
return 0;
}
/*主函数*/
int main(int argc, char *argv[])
{
int n = 0;
int e = 1;
struct SqStack *Change;
Change = (struct SqStack *)malloc(sizeof(struct SqStack));
InitStack(Change);
printf("Please input the Primitive num (十进制数):");
scanf("%d",&n);
while(n)
{
Push(Change , n%8 );
n = n/8;
}
printf("The result is ( 八 进 制 数 ) : ");
while(!StackEmpty(Change))
{
e = Pop(Change,e);
printf("%d",e);
}
printf("\n");
if(e/8 == 0 )
printf("此栈已经为空了\n");
system("PAUSE");
return 0;
}
8、实现链栈的基本操作，然后利用堆栈将一个线性表中的元素按逆序重新存放。例如原来的顺序为 12，8，6，4，2，要求改为 2，4，6，8，12。
#include
#include
#include
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
#define OK 1
#define ERROR 0
typedef int Status;
typedef int SElemType;
#define ListSize 100
typedef int DataType;
typedef struct
{
typedef struct SqStack
{
SElemType *base;/* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ DataType list[ListSize]; int length; }SeqList;/*顺序表*/
}SqStack; /* 顺序栈 */
/*初始化顺序表*/
SeqList InitList()
{
int i;
DataType value[]={12,8,6,4,2};
SeqList L;
L.length=0;
for(i=0;i
{
L.list[i] = value[i];
L.length++;
}
return L;
}
/*顺序表输出函数*/
void displayList(SeqList *sq)
{
int index;
if(sq->length==0) return;
for(index=0;indexlength;index++)
{
printf("%4d",sq->list[index]);
}
}
Status InitStack(SqStack &S)
{ /* 构造一个空栈 S */
}
Status DestroyStack(SqStack &S)
{ /* 销毁栈 S ，S 不再存在 */
free(S.base); S.base=NULL; S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(-1); /* 存储分配失败 */ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; printf("\n");
}
S.stacksize=0; return OK;
Status Push(SqStack &S,SElemType e)
{ /* 插入元素 e 为新的栈顶元素 */
}
Status StackEmpty(SqStack S)
{ /* 若栈 S 为空栈，则返回 TRUE ，否则返回 FALSE */
} if(S.top==S.base) return OK; else return ERROR; if(S.top-S.base>=S.stacksize) /* 栈满，追加存储空间 */ { S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) exit(-1); /* 存储分配失败 */ S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *(S.top)++=e; return OK;
Status Pop(SqStack &S,SElemType &e)
{ /* 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK ；否则返回 ERROR */
}
void reverse(SqStack &S,SeqList &L)
{
SElemType e; DataType f; int i=0; while(!StackEmpty(S)) /* 当栈不空 */ { Pop(S,e); //f=e;/* 弹出栈顶元素且赋值给 e */ if(S.top==S.base) return ERROR; e=*--S.top; return OK;
}
} int main()
{
} Push(S,12); Push(S,8); Push(S,6); Push(S,4); Push(S,2); reverse(S,L); printf("利用堆栈反序线性表后："); displayList(&L); DestroyStack(S); return 0; SqStack S; InitStack(S); SeqList L; L = InitList(); printf("初始线性表L 元素为："); displayList(&L);
9、实现链队的各种基本运算，依次进队元素a ，b ，c ；然后出队一个元素，并输出该元素；输出链队的元素个数；
#include
#include
#include
typedef char ElemType;
typedef struct qnode
{
ElemType data;
struct qnode *next;
}QNode;
typedef struct
{
QNode *front;
QNode *rear;
}LiQueue;
//初始化队列
void InitQueue(LiQueue *&q)
{
q=(LiQueue *)malloc(sizeof(LiQueue));
q->front=q->rear=NULL;
}
//销毁队列
void DestroyQueue(LiQueue *&q)
{
QNode *p=q->front,*r;
if(p!=NULL)
{
r=p->next;
}
free(p);
free(q);
}
//进队列
void enQueue(LiQueue *&q,ElemType e)
{
QNode *p;
p=(QNode *)malloc(sizeof(QNode));
p->data=e;
p->next=NULL;
if(q->rear==NULL)
q->front=q->rear=p;
else
{
q->rear->next=p;
}
}
//出队列
bool deQueue(LiQueue *&q,ElemType &e)
{
QNode *t;
if(q->rear==NULL)
return false;
t=q->front;
if(q->front==q->rear) q->rear=p; while(r!=NULL) { free(p); p=r;r=p->next; }
q->front=q->rear=NULL;
else
q->front=q->front->next;
e=t->data;
free(t);
return true;
}
int QueueLength(LiQueue *q) //输出链队的元素个数
{
}
void main()
{
ElemType e;
LiQueue *q;
printf("链队的各种基本运算如下：\n");
printf("(1)初始化链队q");
InitQueue(q);
printf("\n");
printf("(3)依次进队元素a ，b ，c ；");
enQueue(q,'a');
enQueue(q,'b');
enQueue(q,'c');
printf("\n");
printf("(4)出队一个元素，并输出该元素:");
deQueue(q,e);
printf("%c",e);
printf("\n");
printf("(5)输出链队q 的元素个数：");
printf("%d\n",QueueLength(q));
printf("\n");
printf("(9)释放链队");
DestroyQueue(q);
printf("\n");
} int n=0; QNode *p=q->front; while(p!=NULL) { } return(n); n++; p=p->next;
10、若 x 和 y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。 提示：两个串相等表示对应的字符必须都相同，所以扫描两串，逐一比较相应位置的字符，若相同继续比较直到全部比较完毕，如果都相同则表示两串相等，否则表示两串不相等。 #include
#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 40 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型, 其值是函数结果状态代码，如OK 等 */
typedef char String[MAXSIZE+1]; /* 0号单元存放串的长度 */
/* 输出字符串T */ void StrPrint(String T) { /* 生成一个其值等于chars 的串T */ Status StrAssign(String T,char *chars) { int i; if(strlen(chars)>MAXSIZE) return ERROR; else { T[0]=strlen(chars); for(i=1;iT, 则返回值>0;若S=T, 则返回值=0;若S
int i;
for(i=1;i
if(S[i]!=T[i])
return S[i]-T[i];
return S[0]-T[0];
}
int main() { int i; String x,y; printf("(1)生成串x:"); StrAssign(x,"i take a test"); StrPrint(x); printf("(2)生成串y:"); StrAssign(x,"i get good grage"); StrPrint(x); printf("(3)比较串x 和串y:\n"); i=StrCompare(x,y); char s; if(i '; printf("串x%c串y\n",s); }
11、实现顺序串的基本运算，并在此基础上设计一个程序，完成如下功能：
建立串s=“abcdefghefghijklmn ”和串s1=“xyz ”，将串s 的第2个字符开始的5个字符替换成串s1而产生串s2。
#include
#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 40 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型, 其值是函数结果状态代码，如OK 等 */
typedef char String[MAXSIZE+1]; /* 0号单元存放串的长度 */
/* 输出字符串T */ void StrPrint(String T) { /* 生成一个其值等于chars 的串T */ Status StrAssign(String T,char *chars) { int i; if(strlen(chars)>MAXSIZE) return ERROR; else { T[0]=strlen(chars); for(i=1;iT, 则返回值>0;若S=T, 则返回值=0;若S
int i;
for(i=1;i
return S[i]-T[i]; return S[0]-T[0];
}
int main() { int i; String x,y; char s; StrAssign(x,"i take a test"); StrPrint(x); printf("(1)生成串x:");
printf("(2)生成串y:"); StrAssign(x,"i get good grage"); StrPrint(x); printf("(3)比较串x 和串y:\n"); i=StrCompare(x,y); if(i '; printf("串x%c串y\n",s); }
13、二叉树采用链接存储结构，试设计一个按层次顺序（同一层次自左至右）遍历二叉树的算法。
提示：算法要采用一个队列 q，先将二叉树根结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。
#include
#include
#include
#include
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf 为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针 T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点 T->data=ch; T->rchild=CreatBinTree(); //构造右子树 T->lchild=CreatBinTree(); //构造左子树 return(T); else{
}
}
//====利用" 先进先出" （FIFO ）队列，按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
}
//==========主函数=================
void main()
{
BinTree root;
int i;
/printf("\n");
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列，
//用#代表虚结点，如ABD###CE##F## root=CreatBinTree(); //创建二叉树，返回根结点
}
14、编写程序，输出相应图的DFS 结果。
} front=(front+1)%NodeNum; p=cq[front]; //出队 printf("%c",p->data); //出队，输出结点的值 if(p->lchild!=NULL){ cq[rear]=p->lchild; //左子树入队 } if(p->rchild!=NULL){ cq[rear]=p->rchild; //右子树入队 rear=(rear+1)%NodeNum; rear=(rear+1)%NodeNum; } printf("LevePrint Bin_Tree:"); Levelorder(root); //按层次遍历
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定义最大顶点数
typedef struct{
char vexs[MaxVertexNum]; //顶点表
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表
int n,e; //图中的顶点数n 和边数e
}MGraph; //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;in;i++)
{
scanf("%c",&a); G->vexs[i]=a; //读入顶点信息，建立顶点表
}
for(i=0;in;i++)
for(j=0;jn;j++) G->edges[i][j]=0; //初始化邻接矩阵
printf("Input edges,Creat Adjacency Matrix\n");
for(k=0;ke;k++) { //读入e 条边，建立邻接矩阵
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======
void DFSM(MGraph *G,int i)
{ //以Vi 为出发点对邻接矩阵表示的图G 进行DFS 搜索，邻接矩阵是0，1矩阵 int j;
printf("%c",G->vexs[i]); //访问顶点Vi
visited[i]=TRUE; //置已访问标志
for(j=0;jn;j++) //依次搜索Vi 的邻接点
}
void DFS(MGraph *G) if(G->edges[i][j]==1 && ! visited[j]) DFSM(G,j); //（Vi ，Vj ）∈E ，且Vj 未访问过，故Vj 为新出发点 scanf("%d%d",&i,&j); //输入边（Vi ，Vj ）的顶点序号 G->edges[i][j]=1; G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 }
int i;
for(i=0;in;i++)
}
//==========main=====
void main()
{
int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //为图G 申请内存空间
CreatMGraph(G); //建立邻接矩阵
printf("Print Graph DFS: ");
DFS(G); //深度优先遍历
printf("\n");
}
15、编写程序，输出相应图的BFS 结果。
visited[i]=FALSE; //标志向量初始化 if(!visited[i]) //Vi未访问过 DFSM(G,i); //以Vi 为源点开始DFS 搜索 for(i=0;in;i++)
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定义最大顶点数
typedef struct{
char vexs[MaxVertexNum]; //顶点表
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表
int n,e; //图中的顶点数n 和边数e
}MGraph; //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;in;i++)
{
G->vexs[i]=a; //读入顶点信息，建立顶点表
}
for(i=0;in;i++)
for(j=0;jn;j++) G->edges[i][j]=0; //初始化邻接矩阵
printf("Input edges,Creat Adjacency Matrix\n");
for(k=0;ke;k++) { //读入e 条边，建立邻接矩阵
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//===========BFS：广度优先遍历=======
void BFS(MGraph *G,int k)
{ //以Vk 为源点对用邻接矩阵表示的图G 进行广度优先搜索 int i,j,f=0,r=0;
int cq[MaxVertexNum]; //定义队列
for(i=0;in;i++)
visited[i]=FALSE; //标志向量初始化 for(i=0;in;i++) cq[i]=-1; //队列初始化
printf("%c",G->vexs[k]); //访问源点Vk
visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队 while(cq[f]!=-1) { //队非空则执行
}
//==========main=====
void main()
{
int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //为图G 申请内存空间
CreatMGraph(G); //建立邻接矩阵 i=cq[f]; f=f+1; //Vf出队 for(j=0;jn;j++) //依次Vi 的邻接点Vj if(G->edges[i][j]==1 && !visited[j]) { //Vj未访问 printf("%c",G->vexs[j]); //访问Vj visited[j]=TRUE; r=r+1; cq[r]=j; //访问过Vj 入队 scanf("%d%d",&i,&j); //输入边（Vi ，Vj ）的顶点序号 G->edges[i][j]=1; G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 } } }
printf("Print Graph BFS: ");
BFS(G,4); //以序号为3的顶点开始广度优先遍历
printf("\n");
}
16、编写程序，输出该树的前序遍历序列
#include
#include
#include
#include
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf 为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置========== BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T) { return(NULL); //读入#，返回空指针 T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点 T->data=ch; T->rchild=CreatBinTree(); //构造右子树 T->lchild=CreatBinTree(); //构造左子树 return(T); else{ }
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//==========主函数=================
void main()
{
BinTree root;
int i;
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列， // 用#代表虚结点，如ABD###CE##F## root=CreatBinTree(); //创建二叉树，返回根结点 式，输入序号。
printf("\t1: Preorder Traversal\n");
printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
printf("\n");
}
//从菜单中选择遍历方