[cpp] view plaincopyprint?
****************************************************************
三元組
****************************************************************
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef ElemType *Triplet;
#include "h2.h"
Status InitTriplet(Triplet&T,ElemType v1,ElemType v2,ElemType v3)
{
T = (ElemType *)malloc(3*sizeof(ElemType));
if (!T) exit (OVERFLOW);
T[0] = v1; T[1] = v2; T[2] = v3;
return OK;
}
Status DestroyType(Triplet &T)
{
free(T); T = NULL;
return OK;
}
Status Get(Triplet T,int i,ElemType &e)
{
if(i<1 || i>3) return ERROR;
e = T[i-1];
return OK;
}
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;
}
Status Average(Triplet T,ElemType &e)
{
e = (T[0] + T[1] + T[2])/3;
return OK;
}
void main()
{
Triplet p;
ElemType e,v1,v2,v3;
int select,i;
printf("輸入三個數並建立一個三元組\n");
scanf("%d%d%d",&v1,&v2,&v3);
if (InitTriplet(p,v1,v2,v3)==OVERFLOW)
printf("分配失敗，退出程序！");
else
do
{
printf("1:取三元組第i個元素\n");
printf("2:求最大值\n");
printf("3:求最小值\n");
printf("4:求平均值\n");
printf("5:結束\n");
printf("輸入你的選擇\n");
scanf("%d",&select);
switch(select)
{ case 1:
printf("\ni=");
scanf("%d",&i);
if (Get(p,i,e)==ERROR) printf("i值不合法\n");
else printf("第%d個元素的值為：%d\n",i,e); break;
case 2:
Max(p,e);
printf("最大值是：%d\n",e);break;
case 3:
Min(p,e);
printf("最大值是：%d\n",e);break;
case 4:
Average(p,e);
printf("平均值是: %d\n",e);break;
case 0:
printf("操作結束！"); break;
default: printf("輸入選擇出錯！\n");
}//end switch
}while(select!=0); //end of while
DestroyType(p);
}// end of main
****************************************************************************************************
順序表
*****************************************************************************************************
#include <stdio.h>
#include <stdlib.h>
#define listinitsize 100
#define listincrement 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType *elem;
ElemType length;
ElemType listsize;
}Sqlist;
//.cpp
#include"h1.h"
Sqlist la;
ElemType *a;
ElemType e,k,pre_e,next_e,choice;
Status makelist(Sqlist &la)
{
ElemType i;
la.elem=(ElemType *)malloc(listinitsize *sizeof(ElemType));
if(!la.elem) exit(OVERFLOW);
la.length = 80;
la.listsize=listinitsize;
for(i=0 ; i<=la.length-1 ;i++)
la.elem[i]=i;
return OK;
}
Status listlengh(Sqlist &la)
{
return la.length ;
}
Status getelem(Sqlist la,ElemType k)
{
return la.elem[k];
}
Status priorelem(Sqlist &la,ElemType e ,ElemType &pre_e )
{
ElemType i;
for (i=0; i<=la.length-1;i++)
if(la.elem[i]==e)
pre_e=la.elem[i-1];
return OK;
}
Status nextelem(Sqlist &la,ElemType e ,ElemType &next_e )
{
ElemType i;
for (i=0; i<=la.length-1;i++)
if(la.elem[i]==e)
next_e=la.elem[i+1];
return OK;
}
Status listdelete(Sqlist &la,ElemType k,ElemType &e)
{
ElemType j;
if((k<1)||(k>la.length)) return ERROR;
e=la.elem[k-1];
for(j=k+1;j<=la.length-1;j++)
la.elem[j-1]=la.elem[j];
--la.length;
return OK;
}
Status listinsert(Sqlist &la,ElemType k,ElemType e)
{
ElemType j;
if((k<1)||(k>la.length+1)) return ERROR;
/*if(l.length>=l.listsize)
{*/
for(j=la.length;j>=k;j--)
la.elem[j]=la.elem[j-1];
la.elem[k]=e;
++la.length;
return OK;
}
Status main()
{
makelist(la);
do{
printf("1:求表長\n");
printf("2:取第k個元素\n");
printf("3:e的前驅\n");
printf("4:e的後繼\n");
printf("5:刪除第k個元素 \n");
printf("6:在第k個元素後面插入\n");
printf("0:操作結束！\n");
printf("Enter your choice :\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
listlengh(la);
printf("the length is %d\n",listlengh(la));
break;
case 2:
printf("Enter a number k :");
scanf("%d",&k);
getelem(la, k);
printf("k is %d\n",getelem(la,k));
break;
case 3:
printf("Enter a number e:\n");
scanf("%d",&e);
priorelem(la, e , pre_e );
if(priorelem(la, e , pre_e ))
printf("The priorelem is %d\n",pre_e);
break;
case 4:
printf("Enter a number e:\n");
scanf("%d",&e);
nextelem(la, e , next_e );
if(nextelem(la, e , next_e ))
printf("The nextelem is %d\n",next_e);
break;
case 5:
printf("Enter a number k :");
scanf("%d",&k);
listdelete(la,k,e);
printf("the delete number is:%d\n",e);
break;
case 6:
printf("Enter a number k :");
scanf("%d",&k);
printf("the insert number is:");
scanf("%d",&e);
listinsert(la,k,e);
break;
case 0:
printf("操作結束！");
break;
}
}while(choice!=0); //end of while
return OK; }
************************************************************************************************************
鏈表
************************************************************************************************************
#include <stdio.h>
#include <stdlib.h>
#define OK 0
#define ERROR -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct LNode{
ElemType data; //數據域
<SPAN style="WHITE-SPACE: pre"> </SPAN>struct LNode *next; //指針域
}LNode,*Linklist;Status GetElem_L(Linklist L,int i,ElemType &e) //L為帶頭結點的單鏈表的頭指針，取第i個元素，並用e返回
{
Linklist p=L; //初始化，p指向頭結點，j為計數器
int j=0;
while(p &&j<i) //順指針向後查找，直到p指向第i個元素或p為空
{
p=p->next;
++j;
}
if(!p ||j>i) return ERROR; //第i個元素不存在
e=p->data; //取第i個元素
return OK;
}
Status ListInsert_L(Linklist &L,int i,ElemType e) //在帶頭結點的單鏈表L中的第i個位置之前插入元素e
{
Linklist p=L; //初始化，p指向頭結點，j為計數器
int j=0;
Linklist s;
while(p && j<i-1)
{
p=p->next; //尋找第i-1個節點
++j;
}
if(!p ||j>i-1) return ERROR; //i小於1或者大於表長加1
s=(Linklist)malloc(sizeof(LNode)); //生成新節點,以linklist為頭結點
s->data = e; //插入L中
s->next=p->next;
p->next=s;
return OK;
}
Status ListDelete_L(Linklist &L,int i,ElemType &e) //在帶頭結點的單鏈表L中，刪除第i個元素，並由e返回其值
{ Linklist q;
Linklist p=L; //初始化，p指向頭結點，j為計數器
int j=0;
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;
}
Status CerateList_L(Linklist &L,int n) //逆為序輸入n個元素的值，建立帶表頭節點的單鏈表L
{
Linklist p;
L=(Linklist)malloc(sizeof(LNode));
L->next=NULL; //先建立一個帶頭結點的單鏈表
for(int i=n;i>0;--i)
{
p=(Linklist)malloc(sizeof(LNode)); //生成新結點
scanf("%d",&p->data); //插入元素值
p->next=L->next; //插入到表頭
L->next=p;
}
return OK;
}
Status Listlength(Linklist L,int &j) //求單鏈表的表長
{
j=0;
Linklist p=L;
while(p->next)
{
p=p->next;
j++;
}
return OK;
}
Status PriorEle(Linklist L,int cur_e,ElemType &pre_e) //求cur_e的前趨，並用pre_e返回
{
Linklist p=L;
while(p->next &&p->next->data !=cur_e)
p=p->next;
if(!p->next ||p==L) return ERROR; //前趨不存在
pre_e=p->data;
return OK;
}
Status search(Linklist L,int k) //在一個單鏈表中求倒數第k個元素
{
Linklist p,q;
int count =0;
p=q=L->next;
while(p != NULL) //p不為空的時候，p先走到第k個位置，然後p，q同時走
{
if(count <k)
{count ++;}
else
{q=q->next;}
p=p->next;
}
if(count<k) return ERROR; //輸入的k值不合法
else
return OK;
}
void Traverse (Linklist L) //遍歷鏈表
{
Linklist p;
p=L->next;
printf("鏈表的元素如下:\n");
while(p)
{
printf("%d ",p->data);
p=p->next;
}
}
void main()
{
Linklist L,q;
int select,i,e,j,k,cur_e,pre_e,n;
printf("請輸入一個數確定鏈表的元素個數:");
scanf("%d",&n);
CerateList_L(L,n);
Traverse (L);
do
{
printf("\n\n1:求鏈表的長度\n");
printf("2:取第i個元素的值\n");
printf("3:在第i個元素之前插入一個元素\n");
printf("4:刪除第i個元素\n");
printf("5:求元素cur_e的前趨\n");
printf("6:求倒數第k個元素的值\n");
printf("0:結束！\n");
printf("請輸入選擇！\n");
scanf("%d",&select);
switch(select)
{
case 1:
Listlength(L,j);
printf("鏈表的表長是:%d\n",j);
break;
case 2:
printf("i=");
scanf("%d",&i);
if(GetElem_L(L,i,e)==ERROR)
printf("第i個元素不存在\n");
else
printf("\n第%d個元素的值是:%d\n",i,e);
Traverse (L);
break;
case 3:
printf("i=");
scanf("%d",&i);
printf("e=");
scanf("%d",&e);
if(ListInsert_L(L,i,e)==ERROR )
printf("第i個元素不存在\n");
Traverse (L);
break;
case 4:
printf("i=");
scanf("%d",&i);
if(ListDelete_L(L,i,e)==ERROR)
printf("第i個元素不存在\n");
else
printf("\n刪除第%d個元素是 %d\n",i,e);
Traverse (L);
break;
case 5:
printf("cur_e=");
scanf("%d",&cur_e);
if(PriorEle(L,cur_e,pre_e)==ERROR)
printf("\n%d前趨不存在\n",cur_e);
else
printf("\n%d的前趨是 %d\n",cur_e,pre_e);
Traverse (L);
break;
case 6:
printf("k=");
scanf("%d",&k);
if(search(L,k)==ERROR)
printf("輸入的k值不合法\n");
else
printf("倒數第%d個元素的值是:%d\n",k,q->data);
Traverse (L);
break;
case 0:
printf("\n操作結束");
break;
default:
printf("輸入選擇出錯！\n");
} //end of switch
}while(select != 0); //end of while
}
*************************************************************************************************
隊列
***************************************************************************************************
Status InitQueue(SqQueue &Q){
Q.base = (QElemType *) malloc(MAXSIZE * sizeof(QElemType));
if (!Q.base)exit (OVERFLOW);
Q.front = Q.rear = 0;
return OK;
}
Status EnQueue(SqQueue &Q,QElemType e){
if((Q.rear+1)%MAXSIZE == Q.front) return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
return OK;
}
int QueueLength(SqQueue Q){
return ((Q.rear-Q.front+MAXSIZE)%MAXSIZE - 1);
}
Status DeQueue(SqQueue &Q,QElemType &e){
if(Q.front == Q.rear) return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front+1)%MAXSIZE;
return e;
}
/*Status TraversQueue(SqQueue &Q,QElemType e){
e=Q.base[Q.front];
while (Q.base[Q.front])
{
printf("%d ",e);
}
return OK;
}*/
int main()
{
int select,e,i;
SqQueue Q;
printf("\n1.建立一個循環隊列\n");
printf("2.求隊列長度\n");
printf("3.插入元素\n");
printf("4.刪除元素\n");
printf("0.操作結束。\n");
printf("請輸入選擇：");
scanf("%d",&select);
while(select!=0)
{
switch(select)
{
case 1:
InitQueue(Q);
while(e!=-1&&i<=MAXSIZE){
int i=0;
scanf("%d",&e);
EnQueue(Q,e);
i++;
}
break;
case 2:
printf("%d",QueueLength(Q));
break;
case 3:
scanf("%d",&e);
printf("插入%d",e);
EnQueue(Q,e);
break;
case 4:
DeQueue(Q,e);
printf("刪除%d",e);
break;
case 0:
printf("\nexit!\n");
break;
}
printf("\n1.建立一個循環隊列\n");
printf("2.求隊列長度\n");
printf("3.插入元素\n");
printf("4.刪除元素\n");
printf("0.操作結束。\n");
printf("請輸入選擇：");
scanf("%d",&select);
}
return OK;
}
************************************************************************************************
堆棧
*************************************************************************************************
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
//#define NULL 0;
typedef int Status;
typedef int SElemType;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
//.cpp
#include"h1.h"
Status InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.top==S.base)
return OK;
else return ERROR;
}
Status Push(SqStack &S,SElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return 0;
}
Status Pop(SqStack &S,SElemType &e)
{
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}
Status Compare()
{
SqStack S;
char ch;
SElemType e;
InitStack(S);
int flag=TURE;
while (((ch= getchar())!='#') && flag )
{
switch (ch) {
case '(' :
case '[' :
case '{' :
Push(S,ch);break;
case ')' :
if ( Pop(S,e)==ERROR || e!='(' )
flag=FALSE;
break;
case ']' :
if ( Pop(S,e)==ERROR || e!='[')
flag=FALSE;
break;
case '}' :
if ( Pop(S,e)==ERROR || e!='{')
flag=FALSE;
break;
}//switch
}
if (flag && ch=='#' && StackEmpty(S))
return TURE;
else return FALSE;
}
Status conversion()
{
SqStack S;
SElemType N,e;
InitStack(S);
printf("輸入一個十進制數：");
scanf("%d",&N);
while(N)
{
Push(S,N%16);
N=N/16;
}
while(!StackEmpty(S))
{
Pop(S,e);
if(e<10)
{
printf("%d",e);
}
else
{
switch(e)
{
case 10: printf("A"); break;
case 11: printf("B"); break;
case 12: printf("C"); break;
case 13: printf("D"); break;
case 14: printf("E"); break;
case 15: printf("F"); break;
}
}
}
return OK;
}
void main()
{
int select;
printf("1.進制轉換。\n");
printf("2.括號匹配。\n");
printf("0.操作結束。\n");
printf("請輸入選擇：");
scanf("%d",&select);
while(select!=0)
{
switch(select)
{
case 1:
conversion();
break;
case 2:
printf("\n輸入括號，以#結束：");
if(Compare()==TURE)
printf("匹配\n");
else
printf("不匹配\n");
break;
case 0:
printf("操作結束，退出程序。");
break;
}
printf("\n1.進制轉換。\n");
printf("2.括號匹配。\n");
printf("0.操作結束。\n");
printf("請輸入選擇：");
scanf("%d",&select);
}
}
*************************************************************************************************
矩陣
**************************************************************************************************
#include "stdio.h"
#define OK 1
#define ERROR 0
#define MAXSIZE 120
typedef int ElemType;
typedef int Status;
typedef struct {
int i,j;
ElemType e;
}Triple;
typedef struct{
Triple data[MAXSIZE + 1];
int mu,nu,tu;
}TSMatrix;
#include "1.h"
void InitMatrix(int A[P+1][N+1])
{ int i,j;
printf("請輸入一個4行5列的矩陣\n");
for(i=1;i<=P;i++)
for(j=1;j<=N;j++)
scanf("%d",&A[i][j]);
}
TSMatrix MatrixToTriple(int A[P+1][N+1],TSMatrix M)
{ int row,col,k=0;
for(row=1;row<=P;row++)
for(col=1;col<=N;col++)
if(A[row][col]!=0)
{ k++;
M.data[k].i=row;
M.data[k].j=col;
M.data[k].e=A[row][col];
}
M.mu=P; M.nu=N; M.tu=k;
return M;
}
TSMatrix FastTransposeSMatrix(TSMatrix M,TSMatrix T)
{ int col,t,p,q;
int num[N+1],cpot[N+1];
T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if(T.tu)
{ for(col=1;col<=M.nu;++col) num[col]=0;
for(t=1;t<=M.tu;++t) ++num[M.data[t].j];
cpot[1]=1;
for(col=2;col<=M.nu;++col)
cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=M.tu;++p)
{ col=M.data[p].j;
q=cpot[col];
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++cpot[col];
}
}
return T;
}
void PrintMatrix(TSMatrix T)
{ int B[N+1][P+1]={0};
int i,j,k=1;
for(i=1;i<N+1;i++)
for(j=1;j<P+1;j++)
if(i==T.data[k].i && j==T.data[k].j)
{ B[i][j]=T.data[k].e;++k;}
printf("output TransposeMatrix\n");
for(i=1;i<=N;i++)
{for(j=1;j<=P;j++)
printf("%4d",B[i][j]);
printf("\n");
}
}
int main()
{ int A[P+1][N+1]={0};
TSMatrix M={{0},0,0,0},T={{0},0,0,0};
InitMatrix(A);
M=MatrixToTriple(A,M);
T=FastTransposeSMatrix(M,T);
PrintMatrix(T);
return OK;
}
***********************************************************************************************
二叉樹
***********************************************************************************************
#include "stdio.h"
#include "malloc.h"
#include "iostream.h"
typedef int Status;
typedef int TElemType;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//二叉樹的二叉鏈表儲存
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
//#define NULL 0;
typedef int Status;
typedef int SElemType;
typedef struct TriTNode { // 結點結構
TElemType data;
struct TriTNode *lchild, *rchild;
// 左右孩子指針
struct TriTNode *parent; //雙親指針
} TriTNode, *TriTree;#include "stack.h"
#include "stack.cpp"
#include "queue.cpp"
Status CreateBiTree(BiTree &T) {
char ch;
scanf("%c",&ch);
if (ch=='# ') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
printf("overflow!\n");
T->data = ch; // 生成根結點
CreateBiTree(T->lchild); // 構造左子樹
CreateBiTree(T->rchild); // 構造右子樹
}
return OK;
} //創建二叉樹 CreateBiTree
void Preorder (BiTree T)
{ // 先序遍歷二叉樹
if (T) {
visit(T->data); // 訪問結點
Preorder(T->lchild); // 遍歷左子樹
Preorder(T->rchild);// 遍歷右子樹
}
}
Status inorder(BiTree T,SqStack &S,SElemType p))
{//中序遍歷非遞歸算法,s為存儲二叉樹結點指針棧
InitStack(S);Push(S,T);
while (!StackEmpty(S)){
while (GetTop(S,p)&& p) Push(S,p->lchild);
Pop(S,p);
if (!StackEmpty(S)){
Pop(S,p);
visit(p->data);
Push(S,p->rchild);
}//if
}//while
return OK;
}//inorder
Status PostOrderTraverse(BiTree T,Status ( * Visit)(TElemType e)){
}
int Depth (BiTree T ){ // 返回二叉樹的深度
if ( !T ) depthval = 0;
else {
depthLeft = Depth( T->lchild );
depthRight= Depth( T->rchild );
depthval = 1 + (depthLeft > depthRight ?
depthLeft : depthRight);
}
return depthval;
}
Status LevelOrder(BiTree T){
//按層次遍歷二叉樹T， Q為隊列
InitQueue(Q);
If (T!=NULL){ // 若樹非空
EnQueue(Q,T); //根結點入隊列
While (!QueueEmpty(Q)){
DeQueue(Q,b); //隊首元素出隊列
visit(b->data); //訪問結點
if (b->lchild!=NULL) EnQueue(Q,b->lchild);//左子樹非空，則入隊列
if (b->rchild!=NULL) EnQueue(Q,b->rchild); //右子樹非空，則入隊列
}//while
}//if
}LevelOrder
main(){
BiTree T;
printf("創建一個二叉樹：\n");
CreateBiTree(T);
return 0;
}
*************************************************************************************************************************
圖
***************************************************************************************************************************
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
#define MAX 100
#define ERROR 0
#define TRUE 1
#define OK 1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAXQSIZE 20
typedef int Status;
typedef char TElemType;
typedef struct
{
int *base;
int front;
int rear;
}SqQueue;
SqQueue Q;
int e=0;
Status InitQueue (SqQueue &Q ) {
Q.base = (int *)malloc(MAXQSIZE *sizeof (int));
if(!Q.base) exit (OVERFLOW);
Q.front = Q.rear = 0;
return OK;
}
Status QueueLength (SqQueue &Q )
{
return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
Status EnQueue (SqQueue &Q , int e){
if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR;
Q.base[Q.rear] = e;
Q.rear = (Q.rear+1) %MAXQSIZE;
return OK;
}
Status DeQueue (SqQueue &Q, int &e) {
if (Q.front == Q.rear) return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front+1)% MAXQSIZE;
return OK;
}
Status QueueEmpty(SqQueue Q)
{
if(Q.front==Q.rear)
return OK;
else
return ERROR;
}
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
char *info;
}ArcNode;
typedef struct VNode
{
int data;
ArcNode * firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
int FirstAdjVex(ALGraph G,int v)
{
if(G.vertices[v].firstarc)
return G.vertices[v].firstarc->adjvex;
return -1;
}
#include "1.h"
int NextAdjVex(ALGraph G,int v,int w)
{
ArcNode *p = G.vertices[v].firstarc;
while(p)
{
if(p->adjvex == w)
{
if(p->nextarc)
return p->nextarc->adjvex;
}
p=p->nextarc;
}
return -1;
}
int createUDG(ALGraph &G )
{
int i, v1, v2;
cout<<"請輸入結點個數:";
cin>>G.vexnum; //讀入結點數
cout<<"請輸入邊數:";
cin>>G.arcnum; //讀入弧（邊）數
for(i=1; i<=G.vexnum ; i++) //初始化空關系圖
{
G.vertices[i].firstarc =NULL;
G.vertices[i].data=i;
}
for(i=1;i<=G.arcnum ;i++)
{
cout<<"請輸入第 ["<<i<<"] 條邊"<<endl;
cin>>v1>>v2;//讀入一條邊（弧）
//正向
ArcNode *p;
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=v2;
p->nextarc=G.vertices[v1].firstarc;
G.vertices[v1].firstarc=p;
}
return OK;
}
void vist_P(ALGraph G)
{
int i;
ArcNode *p;
p=(ArcNode *)malloc(sizeof(ArcNode));
for (i = 1 ; i<= G.vexnum ; i++)
{
cout<<"."<<G.vertices[i].data<<"->";
p=G.vertices[i].firstarc;
while (p)
{
cout<<p->adjvex<<"->";
p= p->nextarc;
}
cout<<"^"<<endl;
}
}
int visited[MAX];
void DFS(ALGraph G,int v)
{
visited[v]=TRUE;
cout<<G.vertices[v].data<<" ";
for (int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
{
if (!visited[w]) DFS(G,w);
}
}
void DFSTraverse(ALGraph G)
{
int v;
for (v=1;v<=G.vexnum;v++)
{
visited[v]=ERROR;
}
for (v=1;v<=G.vexnum;v++)
{
if (!visited[v]) DFS(G,v);
}
}
void BFSTraverse(ALGraph G)
{
int w,v;
for (v=1; v<=G.vexnum; ++v)
visited[v] = ERROR; //初始化訪問標志
InitQueue(Q); // 置空的輔助隊列Q
for ( v=1; v<=G.vexnum; ++v )
if ( !visited[v])
{
visited[v] = TRUE;
cout<<G.vertices[v].data<<" ";// 尚未訪問
EnQueue(Q,v);
while(!QueueEmpty(Q))
{
int u ;
DeQueue (Q,u);
for(w = FirstAdjVex(G,u); w >= 0; w = NextAdjVex(G,u,w))
if(!visited[w])
{
visited[w] = TRUE ;cout<<G.vertices[w].data<<" " ;
EnQueue(Q,w);
}
}
}
}
void Collections(ALGraph G)
{
int num[20] = {0};
int i;
ArcNode *ptr;
for(i = 1; i <= G.vexnum ; i++)
{
if(G.vertices[i].firstarc)
{
ptr = G.vertices[i].firstarc;
while (ptr)
{
num[i]++;
num[ptr->adjvex]++;
ptr = ptr->nextarc;
}
}
}
for(i = 1 ; i <= G.vexnum; i++)
cout<<i<<"結點的度數為 :"<<num[i]<<endl;
}
void main()
{
printf(" 1.創建圖 \n");
printf(" 2.廣度優先遍歷\n");
printf(" 3.深度優先遍歷 \n");
printf(" 4.計算結點度數\n");
printf(" 0.退出!\n");
printf("請輸入您的選擇:");
ALGraph G ;
int select;
scanf("%d",&select);
while (0<select && select <5)
{
switch (select){
case 1:
createUDG(G );
cout<<"該圖為 :"<<endl;
vist_P(G);
cout<<endl;
cout<<endl;
break;
case 2:
cout<<"廣度優先遍歷結果為:"<<endl;
BFSTraverse( G);
cout<<endl;
break;
case 3:
cout<<"深度優先遍歷結果為 :"<<endl;
DFSTraverse( G);
cout<<endl;
printf("\n\n");
break;
case 4:
Collections(G);
break;
}
printf(" 1.創建圖 \n");
printf(" 2.廣度優先遍歷\n");
printf(" 3.深度優先遍歷 \n");
printf(" 4.計算結點度數\n");
printf(" 0.退出!\n");
printf("請輸入您的選擇:");
scanf("%d",&select);
}
}
************************************************************************************************************
查找排序
************************************************************************************************************
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 10
typedef int KeyType;
typedef int Status;
typedef struct{
KeyType key;
}Elemtype;
typedef struct{
Elemtype *elem;
int length;
}Sstable;
//.cpp
Status InitList_Ss(Sstable &st)
{//構造一個空的線性表st
st.elem=(Elemtype*)malloc(LIST_INIT_SIZE*sizeof(Elemtype));
if(!st.elem) return false;
st.length=0;
return true;
}//InitList_Ss
Sstable &Init_Ss(Sstable &st)
{//建立有序表
printf("請輸入數建立表：\n");
int i=0;
int t;
do
{
scanf("%d",&st.elem[i].key);
st.length++;
t=st.elem[i].key;
if(i>0)
{
for(int j=0;j<st.length-1;j++)
{
if(st.elem[i].key<st.elem[j].key)
{
for(int k=st.length-2;k>=j;k--)
{
st.elem[k+1].key=st.elem[k].key;
}
st.elem[j].key=t;
}
}
}
i++;
}while(t<1000);
st.length--;
return st;
}//Init_Ss
void Display(Sstable &st)
{//遍歷有序表
printf("遍歷有序表：\n");
if(st.length==0)
printf("有序表為空\n");
for(int i=0;i<st.length;i++)
{
printf("%5d",st.elem[i].key);
}
printf("\n");
}//Display
int Search_Bin(Sstable st,KeyType k)
{//折半查找
int low=0,high=st.length,mid;
while(low<=high)
{
mid=(low+high)/2; //取區間中點
if(st.elem[mid].key==k)
return (mid+1); //查找成功
else if(st.elem[mid].key>k)
high=mid-1; //在左子區間查找
else
low=mid+1; //在右子區間查找
}
return 0;
}//Search_Bin
void Menu()
{
printf("歡迎進入測試程序\n");
printf("1，建立表\n");
printf("2，折半查找\n");
printf("0，退出\n");
printf("請選擇:\n");
}
void main()
{
Sstable st; //有序表
KeyType k; //查找關鍵字
int x,n; //x為折半查找的返回位置,n為菜單選擇
Menu();
scanf("%d",&n);
while(n!=0)
{
switch(n)
{
case 1:
{
if(InitList_Ss(st))
{
st=Init_Ss(st);
Display(st);
}
else
printf("創建失敗\n");
break;
}
case 2:
{
printf("折半查找：\n");
scanf("%d",&k);
x=Search_Bin(st,k);
if(x!=0)
printf("查找成功，位置為%d\n",x);
else
printf("查找失敗\n");
break;
}
default:printf("輸入錯誤,請重新輸入!\n");
}
Menu();
scanf("%d",&n);
}
