データ構造実験コード

429959 ワード
C
抽象データ型の表現と実現
一、実験目的及び要求(1)非数値問題を理解する数学モデルは数学方程式ではなく、表、木、図などのデータ構造である.(2)データ、データ要素、データ対象、データ構造とデータ型などの定義を理解する.データの論理構造と記憶構造及びその種類を把握する.アルゴリズムの重要な特徴など.(3)クラスC言語の表記規範を熟知しており,特にパラメータの違い,入出力の方式とエラー処理方式,抽象データ型の表現と実現に注意する.(4)文頻度に応じてアルゴリズムの時間的複雑度を推定する.
二、実験内容1.データ交換2.最大値と最小値の関数3.三元グループを設立し、一連の操作を行う三、実験の主な流れ、基本操作またはコアコード、アルゴリズムフラグメント(この部分が記入されていない場合は、添付ページに記入してください)
1.    
#include
void swap(int &a,int &b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}
void main()
{
	int i,j;
	cin>>i>>j;
	cout<<"start :i="<<i<<",j="<<j;
	swap(i,j);
	cout<<endl<<"then :i="<<i<<",j="<<j<<endl;
}
2.         
#include
#define N 10
typedef float ET; 
void MAX(ET a[],int n,ET  &max)
{
	max=a[0];
	int i;
	for(i=0;i<n;i++)
	{
		if(a[i]>max)
		{
			max=a[i];
		}
	}
}
void MIN(ET a[],int n,ET &min)
{
	min=a[0];
	int i;
	for(i=0;i<n;i++)
	{
		if(a[i]<min)
		{
			min=a[i];
		}
	}
}
void  main()
{
     ET a[N],max,min;
	 int n;
	 cout<<"n=?"<<endl;
	 cin>>n;
	 for(int i=0;i<n;i++)
	 {
		 cout<<" "<<i+1<<" ：";
		 cin>>a[i];
	 }
	 MAX(a,n,max);
     MIN(a,n,min);
	 cout<<"max="<<max<<",min="<<min<<endl;
}
3.             
typedef int ET;
typedef ET * Tri;
typedef int Status;//   1.h
#include
#include
#include
#include
#include
#define OK 1
#define OVERFLOW -2 
#define ERROR 0
#define TRUE 1
#define FALSE 0//    2.h
Status Crea(Tri &T,ET v1,ET v2,ET v3)
{
	T=(ET*)malloc(3*sizeof(ET));//  3     
	if(!T)
		exit(OVERFLOW);//      
	T[0]=v1;T[1]=v2;T[2]=v3;
	return OK;
}
Status Destory(Tri &T)
{
	free(T);
	T=NULL;
	return OK;
}
Status Get(Tri T,int i,ET &e)
{
	if(i<1||i>3)
	return ERROR;
	e=T[i-1];
	return OK;
}
Status Put(Tri &T,int i,ET e)
{
	if(i<1||i>3)
		return ERROR;
	T[i-1]=e;
	return OK;
}
Status IsDescending(Tri T)
{
	return (T[0]<=T[1])&&(T[1]<=T[2]);
}
Status Max(Tri T,ET &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(Tri T,ET &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 Avr(Tri T,float &e)
{
	e=(T[0]+T[1]+T[2])/(float)3;
		return OK;
}//    3.h	
#include "1.h"
#include "2.h"
#include "3.h"
void main()
{
	system("color 0E");
	Tri T;
	ET a,b,c,e;
	int i;
	float f;
	cout<<"***************     1.0***************"<<endl;
	cout<<"        ："<<endl;
	cin>>a>>b>>c;
	int choice;
	do
	{
		printf("————————————————————————
");
		printf("||         1.                            ||
");
		printf("||         2.                            ||
");
		printf("||         3.                       ||
");
		printf("||         4.                       ||
");
		printf("||         5.                         ||
");
		printf("||         6.                        ||
");
		printf("||         7.                        ||
");
		printf("||         8.                        ||
");
		printf("||         0.                               ||
");   
		printf("————————————————————————
");
		cin>>choice;
		switch(choice)
		{
		case 1:
			if(Crea(T,a,b,c)==OVERFLOW)
			   cout<<"        "<<endl;
			   else
			   cout<<"        "<<endl;
	 break;
		case 2:
			if(Destory(T)==OK)
				   cout<<"    "<<endl;
			else
				   cout<<"    "<<endl;
			break;
		case 3:
			cout<<"       （1，2，3）:"<<endl;
			cin>>i;
			while(i<1||i>3)
			{
			cout<<"     ，     "<<endl;
			cout<<"       （1，2，3）:"<<endl;
			cin>>i;
			}
			Get(T,i,e);
			cout<<e<<endl;
			break;
		case 4:
			cout<<"       （1，2，3）:"<<endl;
			cin>>i;
			while(i<1||i>3)
			{
			cout<<"     ，     "<<endl;
			cout<<"       （1，2，3）:"<<endl;
			cin>>i;
			}
			cout<<"        ："<<endl;
			cin>>e;
			Put(T,i,e);
			break;
		case 5:
			if(IsDescending(T)==1)
			   {
			   cout<<"     "<<endl;
			   }
			else
			{
			cout<<"      "<<endl;
			}
			break;
		case 6:
			Max(T,e);
			cout<<"    ："<<e<<endl;
			break;
		case 7:
			Min(T,e);
			cout<<"    ："<<e<<endl;
			break;
		case 8:
			Avr(T,f);
			cout<<"    ："<<f<<endl;
			break;
		case 0:
			break;
		}
	}while(choice!=0);
}
//   4.cpp

線形テーブルとその応用
一、実験の目的と要求(1)線形表の基本演算を熟知して2種類の記憶構造(順序構造とチェーン構造)の上で実現して、線形表の各種操作(創立、挿入、削除など)の実現を実験の重点とする;(2)今回の実験を通じて学生に順序表、チェーン表に対する理解を深めて、そして応用することを助ける;(3)循環チェーンテーブルと二重チェーンテーブルの定義と構造方法を把握する.二、実験内容(1)プログラミングは順序テーブルの基本操作(確立、挿入、削除、出力、順序検索、折半検索、並べ替えなど)を実現し、メニュー呼び出しを設計する.(2)プログラミングは単一チェーンテーブルの基本操作を実現する.(作成、挿入、削除、テーブル長の求め、順番の検索など)を行い、メニュー呼び出しを設計する.(3)プログラミングは双方向ループチェーンテーブルの基本操作(作成、挿入、削除、出力など)を実現し、メニュー呼び出しを設計する.(4)プログラミングはジョセフリング(ジョセフ問題):既知n人(番号1,2,3,...,nでそれぞれ示す)円卓の周りに囲まれている.k番の人から数を数え、mまで数えた人が列をなす.彼の次の人は1から数を数え、mまで数えた人が列をなす.この法則に従って、円卓の周りの人が列をなすまで繰り返す.注:(1)(2)は必須問題、(3)(4)は選択問題である.
三、実験の主な流れ、基本操作或いはコアコード、アルゴリズム断片(この部分は記入が足りない場合は、添付ページに記入してください)
1.            （  、  、  、  、    、    、   ），         。
#include
#include
#include
#include
#include//              
#include//             
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
#define OVERFLOW -1
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 100
typedef int STATUS;
typedef int ET;
typedef struct{
ET *elem;
int length;
int listsize;
}SqList;
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
STATUS InitList_Sq(SqList &L) {  
  //          L。
  L.elem = (ET *)malloc(LIST_INIT_SIZE*sizeof(ET));
  if (!L.elem) return OK;        //       
  L.length = 0;                  //      0
  L.listsize = LIST_INIT_SIZE;   //       
  return OK;
}
///////////////////////////////////////////////////////////////////
STATUS ListInsert_Sq(SqList &L, int i, ET e) { 
  //       L  i           e，
  // i     1≤i≤ListLength_Sq(L)+1
  ET *p;
  if (i < 1 || i > L.length+1) return ERROR;  // i    
  if (L.length >= L.listsize) {   //         ，    
    ET *newbase = (ET *)realloc(L.elem,
                  (L.listsize+LISTINCREMENT)*sizeof (ET));
    if (!newbase) return ERROR;   //       
    L.elem = newbase;             //    
    L.listsize += LISTINCREMENT;  //       
  }
  ET *q = &(L.elem[i-1]);   // q     
  for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;
                                  //             
  *q = e;       //   e
  ++L.length;   //    1
  return OK;
} // ListInsert_Sq
///////////////////////////////////////////////////////////////////
STATUS BuiltList_Sq(SqList &L,int n) {  
int i;
ET e;
for(i=1;i<=n;i++)
{
cin>>e;
ListInsert_Sq(L,i,e);
}
return OK;
}

///////////////////////////////////////////////////////////////////
STATUS ListDelete_Sq(SqList &L, int i, ET &e) {  
  // i     1≤i≤ListLength_Sq(L)。
  ET *p, *q;
  if (i<1 || i>L.length) return ERROR;  // i    
  p = &(L.elem[i-1]);                   // p         
  e = *p;                               //          e
  q = L.elem+L.length-1;                //        
  for (++p; p<=q; ++p) *(p-1) = *p;     //             
  --L.length;                           //    1
  return OK;
} 

///////////////////////////////////////////////////////////////////
void Show(SqList L)
{
int i;
for(i=0;i<L.length;i++)
{
cout<<L.elem[i]<<"  ";
}
cout<<endl;
}
///////////////////////////////////////////////////////////////////
STATUS Find(SqList &L, int i, ET &e)
{
if(i<L.length){
e=L.elem[i-1];
return OK;
}
else
return ERROR;
}
///////////////////////////////////////////////////////////////////
STATUS compare(ET a,ET b)
{
if(a==b)//strcmp(a,b)
{
return OK;
}
else
return ERROR;
}
///////////////////////////////////////////////////////////////////
int LocateElem_Sq(SqList L, ET e,STATUS (*compare)(ET, ET)) { 
  int i;
  ET *p;
  i = 1;        // i     1      
  p = L.elem;   // p     1        
  while (i <= L.length && (*compare)(*p++, e)) 
    ++i;
  if (i <= L.length) return i;
  else return 0;
} 
///////////////////////////////////////////////////////////////////
void Sort(SqList &L)
{
int i,j;
ET temp,min;
for(i=0;i<L.length;i++)
{
min=L.elem[i];
for(j=i;j<L.length;j++)
{
if(min>L.elem[j])
{
temp=min;
min=L.elem[j];
L.elem[j]=temp;
}
}
L.elem[i]=min;
}
}
///////////////////////////////////////////////////////////////////
STATUS Find2(SqList &L, int &i, ET e)
{
    Sort(L);
    int low=0,high=L.length-1,mid;     //        、     
    while(low<=high)
    {
        if(L.elem[low]==e)
            i= low;
        if(L.elem[high]==e)
            i= high;          
        mid=low+((high-low)/2);
            /*  (low+high)/2         
            （       low+high                     ，
                  ，      /2          ， low+((high-low)/2)
                       */
        if(L.elem[mid]==e)
          i= mid;             //      
        if(L.elem[mid]<e)
          low=mid+1;              
        else
          high=mid-1;             
    }
    if(low>high)
        return ERROR;// low>high             ，    
}
void qusort(SqList &L, int start, int end) /*     qusort()*///    
{
	
    int i, j,key;					/*         */
    i = start;				     /*         i*/
    j = end;					/*         j*/
    key = L.elem[start];			/*     */
    while (i < j)
    {
        while (i < j && key< L.elem[j])
            j--;				/*    */
        if (i < j)
        {
            L.elem[i] = L.elem[j];		/* s[j]  s[i]    */
            i++;					/*    */
        }
        while (i < j && L.elem[i] <= L.elem[0])
            i++;				/*    */
        if (i < j)
        {
            L.elem[j] = L.elem[i];		/*       s[j]  s[i]  */
            j--;				/*    */
        }
    }
    L.elem[i] = key;				/*          */
    if (start < i)
        qusort(L, start, j - 1);/*             qusort()*/
    if (i < end)
       qusort(L, j + 1, end);
	
}
void Qusort(SqList &L)
{
clock_t start1=clock();
qusort(L,0,L.length-1);
clock_t end1=clock();
  cout<<"   "<<end1-start1<<"  "<<endl;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include "1.h"
#include "2.h"
#include "3.h"
void main()
{
SqList L;
InitList_Sq(L);
cout<<"       "<<endl;
int n,i;
ET e;
cin>>n;
BuiltList_Sq(L,n);
int choice=-1;
do
{
printf("1.    
");
printf("2.    
");
printf("3.    
");
printf("4.      
");
printf("5.      
");
printf("6.       
");
printf("7.       
");
printf("0.  
");
cout<<"       "<<endl;
cin>>choice;
switch(choice)
{
case 1:
	cout<<"             "<<endl;
	cin>>i>>e;
	if(ListInsert_Sq(L,i,e)==OK)
	   {
	   cout<<"    "<<endl;
	   }
	else{
	cout<<"    "<<endl;
	}
	break;
case 2:
	cout<<"       "<<endl;
	cin>>i;
	if(ListDelete_Sq(L, i, e))
	{
	cout<<"    "<<endl;
	}
	else
	{
	cout<<"    "<<endl;
	}
	cout<<"       "<<e<<endl;
	break;
case 3:
	Show(L);
	break;
case 4:
    cout<<"       "<<endl;
	cin>>i;
	if(Find(L, i, e))
	{
	cout<<"    "<<endl;
	}
	else
	{
	cout<<"    "<<endl;
	}
	cout<<"       "<<e<<endl;
	break;
case 5:
	cout<<"    "<<endl;
	Show(L);
    cout<<"       "<<endl;
	cin>>e;
	if(!Find2(L, i, e))
	{
	cout<<"    "<<endl;
	}
	else
	{
	cout<<"    "<<endl;
	}
	cout<<"        "<<i+1<<endl;
	break;
case 6:
    Sort(L);
	Show(L);
	break;
case 7:
    Qusort(L);
	Show(L);
	break;
case 0:
	break;
default: 
	cout<<"     "<<endl;
	break;
}
}while(choice);

}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

2.  
            （  、  、  、   、     ），         。
            
typedef struct LNode{
ET data;
struct LNode  *next;
}LNode,*Linklist;
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Color()
{
int choice;
cout<<"        "<<endl;
cout<<"0.              ";
cout<<"1.  "<<endl;
cout<<"2.              ";
cout<<"3.   "<<endl;
cout<<"4.              ";
cout<<"5.  "<<endl;
cout<<"6.              ";
cout<<"7.  "<<endl;
cout<<"8.              ";
cout<<"9.   "<<endl;
cout<<"10.            ";
cout<<"11.    "<<endl;
cout<<"12.            ";
cout<<"13.   "<<endl;
cout<<"14.            ";
cout<<"15.   "<<endl;
cin>>choice;
switch(choice)
{
case 0:system("color F0");break;
case 1:system("color F1");break;
case 2:system("color F2");break;
case 3:system("color F3");break;
case 4:system("color F4");break;
case 5:system("color F5");break;
case 6:system("color F6");break;
case 7:system("color 07");break;
case 8:system("color F8");break;
case 9:system("color F9");break;
case 10:system("color FA");break;
case 11:system("color FB");break;
case 12:system("color FC");break;
case 13:system("color FD");break;
case 14:system("color FE");break;
case 15:system("color 0F");break;
}
}
//////////////////////////////////////////////////////////
STATUS Get_by_location(Linklist L,int i,ET &e)
{
struct LNode *p;
int j;
p=L->next;
j=1;
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i) return ERROR;
e=p->data;
return OK;
}
//////////////////////////////////////////////////////////
STATUS Insert(Linklist &L,int i,ET e)
{
struct LNode *p,*s;
int j;
p=L;
j=0;
while(p&&j<i-1)
{
p=p->next;
++j;
}
if(!p||j>i-1) return ERROR;
s=(Linklist)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
////////////////////////////////////////////////////////////
void Creat(Linklist &L,int n)
{
int i;
struct LNode *p,*q;
L=p=(Linklist)malloc(sizeof(LNode));
p->next=NULL;
/*
L=(Linklist)malloc(sizeof(LNode));
L->next=NULL;
for(i=n;i>0;--i){
p=(Linklist)malloc(sizeof(LNode));
cin>>p->data;
p->next=L->next;
L->next=p;
}
*///   
for(i=0;i<n;i++)
{
q=(Linklist)malloc(sizeof(LNode));
cin>>q->data;
q->next=NULL;//   
p->next=q;
p=q;
}
}
/////////////////////////////////////////////////////////////
void Show(Linklist L)
{
L=L->next;
while(L)
{
cout<<L->data<<"    ";
L=L->next;
}
cout<<endl;
}
////////////////////////////////////////////////
STATUS Get_by_value(Linklist L,int &i,ET e)
{
struct LNode *p;
int j;
p=L->next;
j=1;
while(p&&p->data!=e)
{
p=p->next;
++j;
}
if(!p) return ERROR;
i=j;
return OK;
}
////////////////////////////////////////////////////////////
STATUS Delet_by_value(Linklist &L,ET e)
{
struct LNode *p=L,*q=L->next;
while(q!=NULL&&q->data!=e)
{
p=q;
q=q->next;
}
if(q->data==e)
{
p->next=q->next;
free(q);
}
else
{
cout<<"      "<<endl;
}
return OK;
}
/////////////////////////////////////////////////////////////
STATUS Delet_by_location(Linklist &L,int i)
{
struct LNode *p=L,*q=L->next;
int j=1;
while(q!=NULL&&j!=i)
{
p=q;
q=q->next;
j++;
}
if(j==i)
{
p->next=q->next;
free(q);
}
else
{
cout<<"      "<<endl;
}
return OK;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include "1.h"
#include "2.h"
#include "3.h"
void main()
{
	cout<<"***************      （  ）2.0***************"<<endl;
	cout<<"    ,         "<<endl;
	int n,i;
	ET e;
	cin>>n;
	struct LNode *L;
	Creat(L,n);
	cout<<endl;
	int choice=-1;
	do{
		printf("==========================================
");
		printf("|                                        |
");
		printf("|            1.                      |
");
		printf("|            2.                |
");
		printf("|            3.                |
");
		printf("|            4.                  |
");
		printf("|            5.                  |
");
		printf("|            6.                    |
");
		printf("|            7.                  |
");
		printf("|                                        |
");
		printf("==========================================
");
		cin>>choice;
		switch(choice)
		{
		case 1:
			cout<<"              "<<endl;
			cin>>i>>e;
			if(Insert(L,i,e)==OK)
			{
			cout<<"    "<<endl;
			}
			else
			{
			cout<<"    "<<endl;
			}
		break;
		case 2:
			cout<<"       "<<endl;
			cin>>i;
			if(Get_by_location(L,i,e)==OK)
			{
			cout<<"    ,       "<<e<<endl;
			}
			else
			{
			cout<<"    "<<endl;
			}
		break;
		case 3:
			cout<<"       "<<endl;
			cin>>i;
			if(Get_by_value(L,i,e)==OK)
			{
			cout<<"    ,      "<<i<<endl;
			}
			else
			{
			cout<<"    "<<endl;
			}
		break;
		case 4:
			cout<<"       "<<endl;
			cin>>i;
			if(Delet_by_location(L,i)==OK)
			{
			cout<<"    "<<endl;
			}
			else
			{
			cout<<"    "<<endl;
			}
		break;
		case 5:
			cout<<"       "<<endl;
			cin>>e;
			if(Delet_by_value(L,e)==OK)
			{
			cout<<"    "<<endl;
			}
			else
			{
			cout<<"    "<<endl;
			}
		break;
		case 6:
			Show(L);
			getchar();
			break;
		case 7:
			Color();
			break;
		default:  break;
		}
	}while(choice!=0);
} 
3.    
               （  、  、  、   ），         。
          
typedef int ET;
typedef struct LNode{
ET data;
struct LNode  *prior,*next;
}LNode,*Linklist;

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Color()//        
{
int choice;
cout<<"        "<<endl;
cout<<"0.              ";
cout<<"1.  "<<endl;
cout<<"2.              ";
cout<<"3.   "<<endl;
cout<<"4.              ";
cout<<"5.  "<<endl;
cout<<"6.              ";
cout<<"7.  "<<endl;
cout<<"8.              ";
cout<<"9.   "<<endl;
cout<<"10.            ";
cout<<"11.    "<<endl;
cout<<"12.            ";
cout<<"13.   "<<endl;
cout<<"14.            ";
cout<<"15.   "<<endl;
cin>>choice;
switch(choice)
{
case 0:system("color F0");break;
case 1:system("color F1");break;
case 2:system("color F2");break;
case 3:system("color F3");break;
case 4:system("color F4");break;
case 5:system("color F5");break;
case 6:system("color F6");break;
case 7:system("color 07");break;
case 8:system("color F8");break;
case 9:system("color F9");break;
case 10:system("color FA");break;
case 11:system("color FB");break;
case 12:system("color FC");break;
case 13:system("color FD");break;
case 14:system("color FE");break;
case 15:system("color 0F");break;
}
}
//////////////////////////////////////////////////////////
STATUS Insert(Linklist &L, int i, ET e) {
struct LNode *p,*s;
int j;
p=L;
j=0;
while(p&&j<i-1)
{
p=p->next;
++j;
}
if(!p||j>i-1) return ERROR;
s=(Linklist)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
s->prior=p;
p->next->prior=s;
p->next=s;
return OK;
} 
//////////////////////////////////////////////////////////
STATUS Delet(Linklist &L, int i, ET &e) {
struct LNode *p=L,*q=L->next;
int j=1;
while(q!=NULL&&j!=i)
{
p=q;
q=q->next;
j++;
}
if(j==i)
{
p->next=q->next;
q->next->prior=p;
e=q->data;
free(q);
}
else
{
cout<<"      "<<endl;
}
return OK;
}
//////////////////////////////////////////////////////////
void Creat(Linklist &L,int n)
{
int i;
struct LNode *p,*q;
L=p=(Linklist)malloc(sizeof(LNode));
p->next=NULL;
/*
L=(Linklist)malloc(sizeof(LNode));
L->next=NULL;
for(i=n;i>0;--i){
p=(Linklist)malloc(sizeof(LNode));
cin>>p->data;
p->next=L->next;
L->next=p;
}
*///   
for(i=0;i<n;i++)
{
q=(Linklist)malloc(sizeof(LNode));
cin>>q->data;
q->next=NULL;//   
p->next=q;
p=q;
q->prior=p;
}
}
/////////////////////////////////////////////////////////////
void Show(Linklist L)
{
L=L->next;
while(L)
{
cout<<L->data<<"    ";
L=L->next;
}
cout<<endl;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
4.        （     ）：  n  （   1,2,3...,n    ）         。    k      ，  m      ；        1    ，  m       ；        ，            。
          
typedef struct LNode{
ET data;
struct LNode  *next;
}LNode,*Linklist;

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Creat(Linklist &L,int n)
{
int i;
struct LNode *p,*q;
L=p=(Linklist)malloc(sizeof(LNode));
p->data=1;
p->next=NULL;
for(i=2;i<=n;i++)
{
q=(Linklist)malloc(sizeof(LNode));
q->data=i;
q->next=NULL;
p->next=q;
p=q;
}
q->next=L;
}
//////////////////////////////////////////////////////////////////
Linklist Circle(Linklist &L,int &k,int m)
{
int i;
Linklist a,b;
a=b=L;
for(i=1;i<k;i++)
{
a=a->next;
}
int j;
b=a;
for(j=1;j<m;j++)
{
a=b;
b=b->next;
}
a->next=b->next;
cout<<"       ："<<b->data<<endl;
free(b);
k=1;
if(a->next==a)
{
cout<<"      :"<<a->data<<endl;
return NULL;
}
else
{
return a->next;
}
}
/////////////////////////////////////////////////////////////////
void Show(Linklist L,int n)
{
int i=1;
while(L&&(i<=n))
{
i++;
cout<<L->data<<"    ";
L=L->next;
}
cout<<endl;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include "1.h"
#include "2.h"
#include "3.h"
void main()
{
int n,m,k;
cout<<"      n，    K， m   "<<endl;
cin>>n>>k>>m;
Linklist L;
Creat(L,n);//     
Show(L,n);
while(L)
{
L= Circle(L,k,m);
}
}

スタックとキューとその応用
一、実験目的及び要求(1)スタックとキューの二つの特殊な線形表を把握し、それらの特性を熟知し、実際の問題の背景の下でそれらを柔軟に運用する.(2)本実験訓練の要点はスタックの観点と典型的な応用である.二、実験内容(1)プログラミングは順序スタックの基本操作を実現し、スタックの基本操作を応用し、a)進数の変換を実現する.b)式の文法検査(括弧の一致).c)四則演算式の評価.(2)プログラミング実装キュー(チェーンキューまたはループキュー)の基本操作を行い、スタックとキューを適用して返信シーケンスの判定を実現する.三、実験メインフロー、基本操作またはコアコード、アルゴリズムセグメント(この部分は記入が足りない場合は添付ページに記入してください)
1.    
#define STACK_INTT_SIZE 100
#define STACKINCREMENT 10
typedef int ST;
typedef struct{
ST *base;
ST *top;
int stacksize;
}SqStack;

Status InitStack(SqStack &S){
S.base=(ST * )malloc(STACK_INTT_SIZE*sizeof(ST));
if(!S.base)
exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INTT_SIZE;
return OK;
}


Status Push(SqStack &S,ST e){
if(S.top-S.base>=S.stacksize)
//  ，    
{
S.base=(ST*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ST));
//  10 ST
if(!S.base)
exit(OVERFLOW);
//      
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}


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

Status StackEmpty(SqStack S)
{
if(S.top==S.base)
return OK;
else
return ERROR;
}

void Conversion_Zhengshu(int N,int R)
{
int e=0;
SqStack S;
InitStack(S);
while(N){
Push(S,N%R);
N=N/R;
}
while(!StackEmpty(S)){
Pop(S,e);
if(e>=0&&e<=9)
printf("%d",e);
else
printf("%c",e-10+'A');
}
}

void Conversion_XiaoShu(float B,int R)
{
int e;
while(B>0.0001){
B=B*R;
e=(int)B;
B=B-e;
if(e>=0&&e<=9)
printf("%d",e);
else
printf("%c",e-10+'A');
}
}

void main()
{
float N=0;
int R=0;
cout<<"          ："<<endl;
cin>>N;
cout<<"           ："<<endl;
cin>>R;

int A=0;//    
float B=0;//    
A=(int)N;
B=N-A;

if(A>0)//         ，    ，    0
Conversion_Zhengshu(A,R);//      ，    
else
printf("0");

printf(".");//     

if(B>0.00001)//          ，    ，    0
Conversion_XiaoShu(B,R);//      ，    
else
cout<<"0";

cout<<endl;
}

2.        （     ）
   1，2，3     
Cpp  ：
#include "1.h"
#include "2.h"
#include "3.h"
void main()
{
SqStack S;
InitStack(S);
char a[100]="";
cout<<"     :(,),[,],{,}"<<endl;
scanf("%s",&a);
int i=0;
char ch;
while(a[i]!='\0')
{
if(a[i]=='('||a[i]=='['||a[i]=='{')
Push(S,a[i]);
else if(a[i]==')')
{
Pop(S,ch);
if(ch!='(')
{
cout<<"     "<<endl;
break;
}
}
else if(a[i]==']')
{
Pop(S,ch);
if(ch!='[')
{
cout<<"     "<<endl;
break;
}
}
else if(a[i]=='}')
{
Pop(S,ch);
if(ch!='{')
{
cout<<"     "<<endl;
break;
}
}
i++;
}
if(!StackEmpty(S))
cout<<"       "<<endl;
else
cout<<"      "<<endl;
}

3.       （            ）
   1,2      
   3       
char GetTop(SqStack S)
{
if(StackEmpty(S)!=OK)
return *S.top;
else
return '#';
} 

char Precede(char A,char B)
{
if(A=='+'&&((B=='+')||(B=='-')||(B==')')||(B=='#')))
return '>';
else
return ';
if(A=='-'&&((B=='+')||(B=='-')||(B==')')||(B=='#')))
return '>';
else
return ';
if(A=='*'&&B=='(')
return ';
else
return '>';
if(A=='/'&&B=='(')
return ';
else
return '>';	
if(A=='('&&B==')')
return '=';
else if(A=='('&&B!='#')
return ';
if(A=='#'&&B=='#')
return '=';
else if(A=='#'&&B!=')')
return ';
if(A==')'&&B!='(')
return '>';
}

char Operate(char a,char op,char b)
{
if(op=='+')
return '0'+atoi(&a)+atoi(&b);
else if(op=='-')
return '0'+atoi(&b)-atoi(&a);
else if(op=='*')
return '0'+atoi(&b)*atoi(&a);
else if(op=='/')
return '0'+atoi(&b)/atoi(&a);
else
return '0';
}


Cpp  ：
#include "1.h"
#include "2.h"
#include "3.h"
void main()
{

char a[100];
printf("          ， “#”  
");
scanf("%s",&a);
//     

SqStack S1;//   
InitStack(S1);
Push(S1,'#');
//       ，   #

int i=0;
char e;
for(i=0;a[i]!='\0';i++)
//             ，       ，            
{
if(isdigit(a[i]))
printf("%2c",a[i]);
else if(Precede(a[i],GetTop(S1))=='>')
Push(S1,a[i]);
else if(Precede(a[i],GetTop(S1))=='=')
Pop(S1,e);
else
{
while(Precede(a[i],GetTop(S1))=='&&StackEmpty(S1)!=OK)
{
Pop(S1,e);
printf("%2c",e);
}
}
}

while(StackEmpty(S1)!=OK)
//                
{
Pop(S1,e);
printf("%2c",e);
}

printf("
");

}

 ．      
   1      
   2：          ，          
typedef char ET;
   3      
   4：
typedef struct QNode{
ET data;
struct QNode  *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;//  
   5：//     
Status InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}

Status DestroyQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}

Status EnQueue(LinkQueue &Q,ET e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}

Status DeQueue(LinkQueue &Q,ET &e)
{
QueuePtr p;
if(Q.front==Q.rear)return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return OK;
}

Status QueueEmpty(LinkQueue Q)
{
if(Q.front==Q.rear)
return OK;
else
return ERROR;
}

Status GetHead(LinkQueue Q,ET &e)
{
if(Q.front==Q.rear)
return ERROR;
else 
{
e=Q.front->next->data;
return OK;
}
}

int QueueLength(LinkQueue Q)
{
int n=0;
QueuePtr p;
p=Q.front->next;
while(p)
{
n++;
p=p->next;
}
return n;
}

void ShowQueue(LinkQueue Q)
{
QueuePtr p;
p=Q.front->next;
while(p)
{
cout<<p->data<<"  ";
p=p->next;
}
}

Cpp  ：
#include "1.h"
#include "2.h"
#include "3.h"
#include "4.h"
#include "5.h"
void main()
{
	LinkQueue Q;
	InitQueue(Q);
	SqStack S;
	InitStack(S);
	char a[100];
	cout<<"          ："<<endl;
	scanf("%s",&a);

	int i=0;
	while(a[i]!='\0')
	{
	EnQueue(Q,a[i]);
	Push(S,a[i]);
	i++;
	}
	cout<<endl;

	char q,s;
	int flag=0;
	while(!QueueEmpty(Q)&&!StackEmpty(S))
	{
	DeQueue(Q,q);
	Pop(S,s);
	if(q!=s)
	{
	cout<<"      "<<endl;
	exit(-1);
	}
	}
	cout<<"     "<<endl;
}

文字列
一、実験の目的と要求(1)文字列タイプの定義と表現を熟知する.(2)シリアルのいくつかの基本操作を実現する.二、実験内容(1)プログラミングは二つのシリアルSとTの比較を実現する.(2)プログラミングはシリアルのモードマッチングアルゴリズム(BFアルゴリズム)を実現する.三、実験の主な流れ、基本操作或いはコアコード、アルゴリズム断片(この部分に記入が足りない場合は、別紙に記入してください)
   ：
#include
#include
#include
#define MAXSTRLEN 255
typedef int Status;
typedef char ET;
typedef char SString[MAXSTRLEN+1];
int StrLength(SString T)
    ：
//       
{
	int a;
	a=T[0];
	return a;
}

void Into_SString(SString &T)
{//       
	int i=1;
	char ch=getchar();
	while(ch!='
')
	{
		T[i]=ch;
		ch=getchar();
		i++;
	}
	T[0]=i-1;//        
}

Status Concat(SString &T, SString S1, SString S2) { 
   int i;
   Status uncut;
   if (S1[0]+S2[0] <= MAXSTRLEN) {  //    
      for (i=1; i<=S1[0]; i++) T[i] = S1[i];
      for (i=1; i<=S2[0]; i++) T[i+S1[0]] = S2[i];
      T[0] = S1[0]+S2[0];
      uncut = TRUE;
   } else if (S1[0] < MAXSTRLEN) {  //   
      for (i=1; i<=S1[0]; i++) T[i] = S1[i];
      for (i=S1[0]+1; i<=MAXSTRLEN; i++) T[i] = S2[i-S1[0]];
      T[0] = (char)MAXSTRLEN;
      uncut = FALSE;
   } else {                         //   (  S1)
      for (i=0; i<=MAXSTRLEN; i++) T[i] = S1[i];
      uncut = FALSE;
   }
   return uncut;
}

int StrCompare(SString S, SString T)
{//       
	int i=0;
		for(i=0;i<=S[0]&&i<=T[0];i++)
		{
			if(S[i]!=T[i])
			{
			return (int)(S[i]-T[i]);
			}
		}
	return 0;
}

Status SubString(SString &Sub, SString S, int pos, int len) { 
   int i;
   if (pos < 1 || pos > S[0] || len < 0 || len > S[0]-pos+1)
      return ERROR;
   for(i=1; i<=len; i++)
      Sub[i] = S[pos+i-1];
   Sub[0] = len;
   return OK;
} 

void get_next(SString T, int *next) {  
  int i=1;
  next[1]=0;
  int j=0;
  while (i<T[0]) {
    if(j==0 || T[i]== T[j]) {
      ++i;  ++j;  next[i] = j;
    } else j= next[j];
  }
}


void get_nextval(SString T, int *next) {  
  //     T next          nextval。
  int i = 1;
  int j = 0;
  next[1] = 0;
  while (i<T[0]) {
    if (j==0 || T[i]==T[j]) {
      ++i;  ++j;
      if (T[i]!=T[j]) next[i] = j;
      else next[i] = next[j];
    }
    else j = next[j];
  }
} 

int Index(SString S, SString T, int pos) { 
   int n,m,i;
   SString sub;
   if(S[0]<T[0])
	  return -1;
   if(pos+1>S[0])
	  return -1;
  //       ，   S> T,     
   if (pos > 0) {
      n = StrLength(S);  
      m = StrLength(T);
      i = pos;
      while (i <= n-m+1) {
         SubString (sub, S, i, m);
         if (StrCompare(sub,T) == 0) ++i;
         else return i;
      } 
   } 
   return 0;                    
}

int Index_KMP(SString S, SString T, int pos) {  
  if(S[0]<T[0])
	  return -1;
  if(pos+1>S[0])
	  return -1;
  //       ，   S> T,     

  int next[255];
  int i = pos;
  int j = 1;
  //get_next(T, next);
  get_nextval(T,next);
  //nextval    

  while (i <= S[0] && j <= T[0]) {
    if (j == 0 || S[i] == T[j]) {  //         
      ++i;  ++j;
    } else j = next[j]; //        
  }
  if (j > T[0]) return  i-T[0];   //     
  else return 0;
} 
   ：
void main()
{
		SString S1,S2;
			printf("      1
");
		Into_SString(S1);
			printf("      2
");
		Into_SString(S2);
        //     

        printf("         ：");
		if(StrCompare(S1,S2)==0)
			printf("S1=S2
");
		else if(StrCompare(S1,S2)>0)
			printf("S1>S2
");
		else if(StrCompare(S1,S2)<0)
			printf("S1);
        //     

		int value=0,pos=0;
			printf("            
");
		scanf("%d",&pos);
        value=Index_KMP(S1,S2,pos);
		//value=Index(S1,S2,pos);
		//       ,        KMP   
		if(value==-1)
			printf("    
");
		else
			printf("        %d   
",value);
		//     
}

疎行列
一、実験目的及び要求(1)疎行列の三元群順序表記憶表示を把握する;(2)疎行列の転置演算を実現する.二、実験内容(1)プログラムは疎行列の三元群順序表示方法及び基本操作の実現(確立、出力、転置など)を実現する.(2)プログラムにより疎行列を実現するクロスチェーンテーブル記憶表示及び基本操作の実現(確立、出力等).三、実験の主な流れ、基本操作又はコアコード、アルゴリズムセグメント(この部分は記入が足りない場合は添付ページに記入してください)
Define.h
#define OK 1
#define ERROR 0
#define MAXSIZE 12500
typedef int ElemType;
typedef int Status;







MyTSMatrix.h
#include "Define.h"
#include "stdio.h"
#include "iostream.h"

typedef struct
{
	int col,row;	//         
	ElemType value;
}Trible;//     

typedef struct OLNode{
	int i,j;//       
	ElemType e;
	struct OLNode *right,*down;//        
}OLNode,*OLink;

typedef struct{
	OLink *rhead,*chead;
	int mu,nu,tu;// ， ，   
}CrossList;

class MyTSMatrix  
{
public:
	Status CreateSMatrix_OL_HR();
	void ShowSMatrix_OL();
	Status CreateSMatrix_OL();
	void FastTransposeSMatrix();
	void TransSMatrix();
	void ShowSMatrix();
	void CreateSMatrix();
	MyTSMatrix(int col,int row)
	{
	mu=col;
	nu=row;
	}
	virtual ~MyTSMatrix();
private:
	Trible data[MAXSIZE+1];//data[0]  
	int mu,nu,tu;
	CrossList M;
	int OL_m,OL_n,OL_t;
};








MyTSMatrix.cpp
#include "stdio.h"
#include "iostream.h"
#include "MyTSMatrix.h"
#include "Define.h"
#include "malloc.h"
MyTSMatrix::~MyTSMatrix()
{

}

void MyTSMatrix::CreateSMatrix()
{
	int i,j,k=1;
	ElemType temp;
	tu= 0;
	cout<<"  "<<mu<<" "<<nu<<"      ："<<endl;
	for (i=1;i<=mu;i++)
	{
		for (j=1;j<=nu;j++)
		{
			cin>>temp;
			if (temp!=0)
			{
				data[k].col = j;// 
				data[k].row = i;// 
				data[k].value = temp;//  
				tu++;//      1
				k++;//data[]   1
			}
		}
	}
}

void MyTSMatrix::ShowSMatrix()
{
	int i,j;
	int pos =1;
	for (i=1;i<=mu;i++)
	{
		for (j=1;j<=nu;j++)
		{
			if (data[pos].row==i&&data[pos].col==j)
			{
				cout<<data[pos].value<<"   ";
				pos++;
			}
			else
				cout<<0<<"   ";
		}
		cout<<endl;
	}
}

void MyTSMatrix::TransSMatrix()
{
	  int p, q, col,T_tu;
	  Trible *T=new Trible[tu+1];
	  for (T_tu=1; T_tu<=tu; T_tu++){
		  T[T_tu].col=data[T_tu].col;
		  T[T_tu].row=data[T_tu].row;
		  T[T_tu].value=data[T_tu].value;
		  }
	  //             

		q = 1;
		for (col=1; col<=nu; ++col)
		  for (p=1; p<=tu; ++p)
			if (T[p].row== col) {
			  data[q].col=T[p].row;
			  data[q].row=T[p].col;
			  data[q].value=T[p].value;
			  ++q; 
			}
	  //                    

		int temp;
		temp=nu;
		nu=mu;
		mu=temp;
	  //    mu nu    
		delete T;
}

void MyTSMatrix::FastTransposeSMatrix()
{
	int *num= new int[nu];
	int t;
	for(t=1;t<=nu;t++)
	num[t]=0;//num[]     
	for(t=1;t<=tu;++t)
	num[data[t].col]++;//             

	int *cpot=new int[nu];
	cpot[1]=1;
	int col;
	for(col=2;col<=nu;col++)
	cpot[col]=0;//cpot[]      
	for(col=2;col<=nu;++col)
	cpot[col]=cpot[col-1]+num[col-1];//               
	
	int T_tu;
	Trible *T=new Trible[tu+1];
	  for (T_tu=1; T_tu<=tu; T_tu++){
		  T[T_tu].col=data[T_tu].col;
		  T[T_tu].row=data[T_tu].row;
		  T[T_tu].value=data[T_tu].value;
		  }
	  //             

	int p,q;
	for(p=1;p<=tu;++p){
		col=T[p].col;//   p         
		q=cpot[col];// cpot[]        col         
		data[q].col=T[p].row;
		data[q].row=T[p].col;
		data[q].value=T[p].value;//              
		++cpot[col];//     cpot[col]        1
	}

	int temp;
	temp=nu;
	nu=mu;
	mu=temp;
	  //    mu nu    

	delete num,cpot,T;//     num[],cpot[],  T

}

Status MyTSMatrix::CreateSMatrix_OL()
{
   //       M。          。
  OLNode *p,*q;
  int i,j,e;

  cout<<"                ,         ："<<endl;
  int m,n,t;
  cin>>m>>n>>t;

  M.mu=m;  M.nu=n;  M.tu=t; 
  OL_m=m;  OL_n=n;  OL_t=t;

  if (!(M.rhead = (OLink *)malloc((m+1)*sizeof(OLink)))) return ERROR;
  if (!(M.chead = (OLink *)malloc((n+1)*sizeof(OLink)))) return ERROR;

  for(int a=1;a<=m;a++)  
     M.rhead[a]=NULL;
  for(int b=1;b<=n;b++) 
	 M.chead[b]=NULL;//           ；         

  cout<<"          ， ， ："<<endl;
  for ( int c=1; c<=t; c++) { 
		cin>>i>>j>>e;
		if (!(p = (OLNode *)malloc(sizeof(OLNode)))) 
				return ERROR;
		p->i=i;  p->j=j;  p->e=e;  p->down=NULL;  p->right=NULL; //    

		if (M.rhead[i] == NULL || M.rhead[i]->j > j) {
				p->right = M.rhead[i];   
				M.rhead[i]= p; //                    
		} 
		else {  
			  for (q=M.rhead[i]; (q->right) && (q->right->j<j); q=q->right);
			  p->right = q->right;  q ->right = p;    //                      
		}  //      

		if (M.chead[j] == NULL || M.chead[j]->i > i) {
				p->down = M.chead[j];   M.chead[j]= p;  
		} 
		else { 
			  for ( q=M.chead[j]; (q->down) && q->down->i <i;  q = q->down );
					p->down = q->down;  q->down = p;    
		}  //      
  } 
  return OK;
}

void MyTSMatrix::ShowSMatrix_OL()
{//    
	int i,j;
	OLNode *p;
	for (i=1;i<=OL_m;i++)
	{
		p=M.rhead[i];
		for (j=1;j<=OL_n;j++)
		{
			if (p!=NULL&&p->j==j)
			{
				cout<<p->e<<"   ";
				p=p->right;
			}
			else
				cout<<0<<"   ";
		}
		cout<<endl;
	}
}

Status MyTSMatrix::CreateSMatrix_OL_HR()
{
  OLNode *p,*q;
  int i,j;

  cout<<"                    ："<<endl;
  int m,n;
  cin>>m>>n;

  M.mu=m;  M.nu=n;  
  OL_m=m;  OL_n=n;  OL_t=0;  

  if (!(M.rhead = (OLink *)malloc((m+1)*sizeof(OLink)))) return ERROR;
  if (!(M.chead = (OLink *)malloc((n+1)*sizeof(OLink)))) return ERROR;

  for(int a=1;a<=m;a++)  
     M.rhead[a]=NULL;
  for(int b=1;b<=n;b++) M.chead[b]=NULL;//           ；         

  cout<<"       ："<<endl;
  ElemType temp;
  for (i=1;i<=OL_m;i++)
	{
		for (j=1;j<=OL_n;j++)
		{
			cin>>temp;
			if (temp!=0)
			{
				if (!(p = (OLNode *)malloc(sizeof(OLNode)))) return ERROR;
				p->i=i;  p->j=j;  p->e=temp;  p->down=NULL;  p->right=NULL; //    
				if (M.rhead[i] == NULL || M.rhead[i]->j > j) {
				p->right = M.rhead[i];   M.rhead[i]= p; //                    
				} 
				else {  
					  for (q=M.rhead[i]; (q->right) && (q->right->j<j);  q=q->right);
						p->right = q->right;  q ->right = p;    //                      
				}  //      

				if (M.chead[j] == NULL || M.chead[j]->i > i) {
						p->down = M.chead[j];   M.chead[j]= p;  
				} 
				else { 
					  for ( q=M.chead[j]; (q->down) && q->down->i <i;  q = q->down );
							p->down = q->down;  q->down = p;    
				}  //      
				OL_t++;
			}
		}
	}
  return OK;
}






Main.cpp
#include "stdio.h"
#include "iostream.h"
#include "MyTSMatrix.h"
#include "Define.h"
int main()
{
	int row,col;
	cout<<"                    ："<<endl;
	cin>>col>>row;
	MyTSMatrix S(col,row);
	S.CreateSMatrix();
	cout<<"    ："<<endl;
	S.ShowSMatrix();
	S.TransSMatrix();
	//S.FastTransposeSMatrix();
	cout<<"      ："<<endl;
	S.ShowSMatrix();
	//S.CreateSMatrix_OL();
	S.CreateSMatrix_OL_HR();
	cout<<"      ："<<endl;
	S.ShowSMatrix_OL();
	return 0;	
}

ツリーとその応用
一、実験目的及び要求(1)実験により、二叉木の二つの基本的な記憶構造及び二叉木の構築、遍歴(先序、中序、後序、階層遍歴)を把握し、応用(二叉木の高さの計算、ノード数の統計など).
二、実験内容(1)二叉木における接点の値を先順に入力し,二叉鎖表を記憶構造とする二叉木を構築し,その後,先順,中順,後順,層順にそれぞれこの二叉木を遍歴し,二叉木の対応情報の統計(各種接点数,計算高さなど)を完了した.(2)二叉並べ替え木を1本作成し、中順遍歴を行い、動的検索を実現する.(3)完全な符号化/復号システムを設計する:1つのドキュメントに対して、各文字の出現回数を統計し、それのためにHuffman符号化を設計し、それから復号を行う.注:(1)必ず問題を作るため、(2)～(3)選択のために問題を作る.三、実験の主な流れ、基本操作またはコアコード、アルゴリズムの断片(この部分が記入し足りない場合は、添付ページに記入してください)
#include
#include
#include
#include
#include
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
#define OVERFLOW -1
typedef int Status;
typedef int TElemType;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild,*rchild;//      
}BiTNode,*BiTree;
//     
typedef BiTree ET;
typedef struct QNode{
ET data;
struct QNode  *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q.front) exit(OVERFLOW);
	Q.front->next=NULL;
	return OK;
}

Status DestroyQueue(LinkQueue &Q)
{
	while(Q.front)
	{
		Q.rear=Q.front->next;
		free(Q.front);
		Q.front=Q.rear;
	}
	return OK;
}

Status EnQueue(LinkQueue &Q,ET e)
{
	QueuePtr p;
	p=(QueuePtr)malloc(sizeof(QNode));
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}

Status DeQueue(LinkQueue &Q,ET &e)
{
	QueuePtr p;
	if(Q.front==Q.rear)return ERROR;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)
	Q.rear=Q.front;
	free(p);
	return OK;
}

Status QueueEmpty(LinkQueue Q)
{
	if(Q.front==Q.rear)
	return OK;
	else
	return ERROR;
}

Status CreateTree(BiTree &T)
{//               （  ）
	//           
	TElemType ch;
	ch=getchar();
	if(ch=='#')
		T = NULL;
	else
	{
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
			exit(OVERFLOW);
		T->data = ch;//     
		CreateTree(T->lchild);//     
		CreateTree(T->rchild);//     
	}
	return OK;
}
void PreOrder(BiTree T)
{//    
	if(T!=NULL)
	{
		cout<<T->data;
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

void IntOrder(BiTree T)
{//  
	if(T)
	{
		IntOrder(T->lchild);
		cout<<T->data;
		IntOrder(T->rchild);
	}
}
void PostOrder(BiTree T)
{//  
	if(T)
	{
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		cout<<T->data;
	}
}

void LevelOrder(BiTree T)
{//    
	LinkQueue Q;
	BiTree b;
	InitQueue(Q);
	if(T)
	{
		EnQueue(Q,T);
		while(!QueueEmpty(Q))
		{
			DeQueue(Q,b);
			cout<<b->data;
			if(b->lchild)
				EnQueue(Q,b->lchild);
			if(b->rchild)
				EnQueue(Q,b->rchild);
		}
	}
}
int TreeDepth(BiTree T)
{//    
	int h,lh,rh;
	if(!T)
		h=0;
	else
	{
		lh = TreeDepth(T->lchild);
		rh = TreeDepth(T->rchild);
		if(lh>=rh)
			h = lh+1;
		else
			h = rh+1;
	}
	return h;
}
int Count(BiTree T)
{//    
	int num,numl,numr;
	if(!T)
		num = 0;
	else
	{
		numl = Count(T->lchild);
		numr = Count(T->rchild);
		num = numl+numr+1;
	}
		return num;
}

void insert(BiTree &T,TElemType x)
{//       
	if(T==NULL)
	{
		T=(BiTree)malloc(sizeof(BiTNode));
		T->data=x;
		T->lchild=NULL;
		T->rchild=NULL;
	}
	else
	{
		if(x<=T->data)
			insert(T->lchild,x);
		else
			insert(T->rchild,x);
	}
}

void CreateBiTree(BiTree &root)
{//       
	TElemType x;
	root=NULL;
	cin>>x;
	while(x!=0)
	{
		insert(root,x);
		cin>>x;
	}
}

Status Delete(BiTree &p) {  
  //            p，          
  BiTree q, s;
  if (!p->rchild) {  //               
    q = p;  p = p->lchild;  free(q);
  } else if (!p->lchild) {  //          
    q = p;  p = p->rchild;  free(q);
  } else {  //        
    q = p;  s = p->lchild;
    while (s->rchild)   //   ，       
      { q = s;  s = s->rchild; }
    p->data = s->data;                  // s       “  ”
    if (q != p) q->rchild = s->lchild;  //   *q    
    else q->lchild = s->lchild;         //   *q    
    free(s);    
  }
  return TRUE;
} // Delete
#include "IncludeFile.h"
#include "DefineFile.h"
#include "Bitree.h"
#include "Bitree2.h"
#include "LinkQueue.h"
#include "LinkQueueFun.h"
#include "BitreeFun.h"
#include "BitreeFun2.h"
//abc##de#g##f###
//123##45#6##7###
//1 9 8 5 6 7 4 3 2 0
void main()
{
	
	BiTree T;
	cout<<"       "<<endl;
	CreateTree(T);
	cout<<"    "<<endl;
	PreOrder(T);
	cout<<endl;
	cout<<"    "<<endl;
	IntOrder(T);
	cout<<endl;
	cout<<"    "<<endl;
	PostOrder(T);
	cout<<endl;	
	cout<<"    "<<endl;
	LevelOrder(T);
	cout<<endl;
	cout<<"     ："<<endl;
	cout<<TreeDepth(T)<<endl;
	cout<<"     ："<<endl;
	cout<<Count(T)<<endl;
	cout<<"       "<<endl;
	cout<<endl;

	BiTree T1;
	CreateBiTree(T1);
	cout<<"    "<<endl;
	IntOrder(T1);
	cout<<endl;

	free(T);//    
}

図とその応用
一、実験目的及び要求(1)本実験を完了することにより、図の2つの基本的な記憶構造(隣接マトリクス、隣接テーブル)及び図の基本アルゴリズムの実現(確立、遍歴)を把握し、図構造を用いていくつかの実際の問題を分析し、解決することができる.(2)本実験訓練の要点は、図の2つの基本的な記憶構造及び各種操作のアルゴリズムの実現である.(確立、遍歴、図の典型的な応用).二、実験内容(1)確立図の隣接行列(または隣接表)は、頂点の度(入度、出度)を計算し、深さ優先または広さ優先で図を遍歴することを記憶する.(2)最小生成ツリー解を実現するPrimアルゴリズムをプログラミングする.(3)プログラミングはAOV網のトポロジーソートを実現する.(4)AOEネットワークを実現するためのプログラミングのキーパス.(5)単一ソースポイントの最短パスを実現するDijkstraアルゴリズムをプログラミングする.三、実験のメインフロー、基本操作またはコアコード、アルゴリズムセグメント(この部分は記入が足りない場合は添付ページに記入してください)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef int Status;

#define INIFINITY 1000   			//    
#define MAX_VERTEX_NUM 20    		//     
typedef enum{DG,DN,UDG,UDN} GraphKind; 	//      
typedef char VertexType;			//    
typedef  bool  visited;
typedef  struct {
   VertexType vexs[MAX_VERTEX_NUM]; 	//    
   int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//    
   int vexnum,arcnum;			//        
   GraphKind kind;				//    
}MGraph;
struct 
	{
		VertexType adjvex;
		int lowcost;
	}closedge[MAX_VERTEX_NUM];
	//    
Status CreateUDN(MGraph &G){
	int i,j,k;
    	VertexType v1,v2;
	int w;
	cout<<endl<<"          ：";
    	cin>>G.vexnum>>G.arcnum;
    	cout<<endl<<"        ：";
    	for (i=0;i<G.vexnum;i++) cin>>G.vexs[i];
    	for (i=0;i<G.vexnum;i++) 
		for (j=0;j<G.vexnum;j++) G.arcs[i][j]=INIFINITY;
    	cout<<endl<<"       v1,v2,w"<<endl;
    	for (k=0;k<G.arcnum;k++) {
        	 	cin>>v1;
				cin>>v2;
				cin>>w;
        	 	i=LovateVex(G,v1);  
		j=LovateVex(G,v2);  
		G.arcs[i][j]=w;
         	 	G.arcs[j][i]=G.arcs[i][j];
	}//for k
   	return OK;
 }//CreateUDN
Status CreateDN(MGraph &G){
	int i,j,k;
    	VertexType v1,v2;
	int w;
	cout<<endl<<"          ：";
    	cin>>G.vexnum>>G.arcnum;
    	cout<<endl<<"        ：";
    	for (i=0;i<G.vexnum;i++) cin>>G.vexs[i];
    	for (i=0;i<G.vexnum;i++) 
		for (j=0;j<G.vexnum;j++) G.arcs[i][j]=INIFINITY;
    	cout<<endl<<"       v1,v2,w"<<endl;
    	for (k=0;k<G.arcnum;k++) {
        	 	cin>>v1;
				cin>>v2;
				cin>>w;
        	 	i=LovateVex(G,v1);  
		j=LovateVex(G,v2);  
		G.arcs[i][j]=w;
        //G.arcs[j][i]=G.arcs[i][j];
	}//for k
   	return OK;
 }//CreateDN

Status CreateUDG(MGraph &G){
	int i,j,k;
    	VertexType v1,v2;
	//int w;
	cout<<endl<<"          ：";
    	cin>>G.vexnum>>G.arcnum;
    	cout<<endl<<"        ：";
    	for (i=0;i<G.vexnum;i++) cin>>G.vexs[i];
    	for (i=0;i<G.vexnum;i++) 
		for (j=0;j<G.vexnum;j++) G.arcs[i][j]=0;
    	cout<<endl<<"       v1,v2"<<endl;
    	for (k=0;k<G.arcnum;k++) {
        	 	cin>>v1;
				cin>>v2;
        	 	i=LovateVex(G,v1);  
		j=LovateVex(G,v2);  
		G.arcs[i][j]=1;
        G.arcs[j][i]=G.arcs[i][j];
	}//for k
   	return OK;
 }//CreateUDG

Status CreateDG(MGraph &G){
	int i,j,k;
    	VertexType v1,v2;
	//int w;
	cout<<endl<<"          ：";
    	cin>>G.vexnum>>G.arcnum;
    	cout<<endl<<"        ：";
    	for (i=0;i<G.vexnum;i++) cin>>G.vexs[i];
    	for (i=0;i<G.vexnum;i++) 
		for (j=0;j<G.vexnum;j++) G.arcs[i][j]=0;
    	cout<<endl<<"       v1,v2"<<endl;
    	for (k=0;k<G.arcnum;k++) {
        	 	cin>>v1;
				cin>>v2;
        	 	i=LovateVex(G,v1);  
		j=LovateVex(G,v2);  
		G.arcs[i][j]=1;
        //G.arcs[j][i]=G.arcs[i][j];
	}//for k
   	return OK;
 }//CreateDG

//   G     
Status CreateGraph(MGraph &G){
   int kind;
   cout<<endl<<"      ：0-DG,1-DN,2-UDG,3-UDN:"<<endl;
   cin>>kind;
   G.kind=(GraphKind)kind;
   switch (G.kind){
    	case  DG	:return CreateDG(G);
     	case  DN	:return CreateDN(G);
     	case  UDG	:return CreateUDG(G);
       	case  UDN	:return CreateUDN(G);
       	default 	:return ERROR;
   }
}//CreateGraph
//          
int LovateVex(MGraph G,VertexType v)
{
   for (int i=0;G.vexs[i]!=v;i++);
   return i;
}

//     
int GetOut(MGraph G,int i)
{
	int j;
	int sum=0;
	for(j=0;j<G.vexnum;j++)
	{
		if(G.arcs [i][j]!=0&&G.arcs [i][j]!=INIFINITY)
			sum++;
	}
	return sum;
}

//     
int GetIn(MGraph G,int j)
{
	int i;
	int sum=0;
	for(i=0;i<G.vexnum;i++)
	{
		if(G.arcs [i][j]!=0&&G.arcs [i][j]!=INIFINITY)
			sum++;
	}
	return sum;
}

//    
int GetInAndOut(MGraph G,int i)
{
	int j;
	int sum=0;
	for(j=0;j<G.vexnum ;j++)
	{
		if(G.arcs [i][j]!=0&&G.arcs [i][j]!=INIFINITY)
		sum++;
	}
	return sum;
}
//    
void BFSTraverse(MGraph G)
{
	visited visited[MAX_VERTEX_NUM];
	int v,u,w;
	for(v=0;v<G.vexnum ;v++)
		visited[v]=false;
	//   ，              
	LinkQueue Q;
	InitQueue(Q);
	//    
	for(v=0;v<G.vexnum ;v++)
		if(!visited[v])
		{
			visited[v]=true;
			cout<<G.vexs[v];
			EnQueue(Q,v);
			while(!QueueEmpty(Q))
			{
				DeQueue(Q,u);
				for(w=0;w<G.vexnum ;w++)
				{
					if((G.arcs [u][w]==1)&&(!visited[w]))
					{
						visited[w]=true;
						cout<<G.vexs [w];
						EnQueue(Q,w);
					}
				}		
			}
		}
}
//    
void DFS(MGraph G,int v,visited *visited)
{
	visited[v]=true;
	cout<<G.vexs [v];
	for(int w=0;w<G.vexnum ;w++)
	{
		if((G.arcs [v][w]==1)&&(!visited[w]))
			DFS(G,w,visited);
	}
}
void DFSTraverse(MGraph G)
{
	visited visited[MAX_VERTEX_NUM];
	int v;
	for(v=0;v<G.vexnum ;v++)
		visited[v]=false;
	//   ，              
	for(v=0;v<G.vexnum ;v++)
		if(!visited[v])
			DFS(G,v,visited);
}
//  closedge         
int mininum(MGraph G)
{
	int min,los;
	//          0
	for(int j=0;j<G.vexnum ;j++)
	{
		if(closedge[j].lowcost!=0)
			min=closedge[j].lowcost;
	}
	//       0  
	for(j=0;j<G.vexnum ;j++)
	{
		if(closedge[j].lowcost!=0&&closedge[j].lowcost<=min)
		{
			min=closedge[j].lowcost;
			los=j;
		}			
	}
	//    0       
	return los;
}
//            
void MiniSpanTree_PRIM(MGraph G,VertexType u)
{
	int k=LovateVex(G,u);
	for(int j=0;j<G.vexnum ;j++)
		if(j!=k)
		{
			closedge[j].adjvex=u;
			closedge[j].lowcost=G.arcs [k][j];
		}
	closedge[k].adjvex=u;
	closedge[k].lowcost=0;
	//   
	for(int i=1;i<G.vexnum ;i++)
	{
		k=mininum(G);
		cout<<closedge[k].adjvex<<"--"<<G.vexs [k]<<"||";
		closedge[k].lowcost=0;
		for(int j=0;j<G.vexnum ;j++)
		{
			if(G.arcs [k][j]<closedge[j].lowcost)
			{
				closedge[j].adjvex=G.vexs [k];
				closedge[j].lowcost=G.arcs [k][j];
			}
		}
		//  closedge    
	}
}

void DijkstraPath(MGraph g,int *dist,int *path,int v0)   //v0      
{
    int i,j,k;
    bool *visited=(bool *)malloc(sizeof(bool)*g.vexnum );
    for(i=0;i<g.vexnum ;i++)     //    
    {
        if(g.arcs [v0][i]>0&&i!=v0)
        {
            dist[i]=g.arcs[v0][i];
            path[i]=v0;     //path        v0 i       
        }
        else
        {
            dist[i]=INIFINITY;    // i  v0    ，         
            path[i]=-1;
        }
        visited[i]=false;
        path[v0]=v0;
        dist[v0]=0;
    }
    visited[v0]=true;
    for(i=1;i<g.vexnum;i++)     //    n-1  
    {
        int min=INIFINITY;
        int u;
        for(j=0;j<g.vexnum ;j++)    //               
        {
            if(visited[j]==false&&dist[j]<min)
            {
                min=dist[j];
                u=j;        
            }
        } 
        visited[u]=true;
        for(k=0;k<g.vexnum ;k++)   //  dist          
        {
            if(visited[k]==false&&g.arcs [u][k]>0&&min+g.arcs [u][k]<dist[k])
            {
                dist[k]=min+g.arcs [u][k];
                path[k]=u; 
            }
        }        
    }    
}
void showPath(int *path,int v,int v0)   //             
{
    stack<int> s;
    int u=v;
    while(v!=v0)
    {
        s.push(v);
        v=path[v];
    }
    s.push(v);
    while(!s.empty())
    {
        cout<<s.top()<<" ";
        s.pop();
    }
} 
//   G
void PrintGraph(MGraph G){	
	int v0;
    int *dist=(int *)malloc(sizeof(int)*G.vexnum );
    int *path=(int *)malloc(sizeof(int)*G.vexnum );
    int i,j;
    cout<<endl<<"        ：";
    cout<<setw(3)<<G.vexnum<<setw(3)<<G.arcnum;
    cout<<endl<<"      ："<<endl;
    for (i=0;i<G.vexnum;i++) cout<<setw(3)<<G.vexs[i];
	if(G.kind ==DG||G.kind ==DN)
	{
		cout<<endl<<"      ："<<endl;
		for (i=0;i<G.vexnum;i++) cout<<setw(3)<<GetOut(G,i);
		cout<<endl<<"      ："<<endl;
		for (i=0;i<G.vexnum;i++) cout<<setw(3)<<GetIn(G,i);
	}
	else
	{
		cout<<endl<<"    ："<<endl;
		for (i=0;i<G.vexnum;i++) cout<<setw(3)<<GetInAndOut(G,i);	
	}	
    cout<<endl<<"      ："<<endl;
    for (i=0;i<G.vexnum;i++){
		cout<<endl;
		for (j=0;j<G.vexnum;j++)
			  if (G.arcs[i][j]==INIFINITY)cout<<setw(5)<<"∞";
			 else cout<<setw(5)<<G.arcs[i][j];
		}//for i
	cout<<endl;
	if(G.kind ==UDG)
	{
		 cout<<endl<<"      ："<<endl;
		 BFSTraverse(G);
		 cout<<endl<<"      ："<<endl;
		 DFSTraverse(G);	 
		 cout<<endl;
	}
	 if(G.kind ==DN)
	 {
		 cout<<"    （  ）:";
		 cin>>v0;        //      
			DijkstraPath(G,dist,path,v0);
			for(i=0;i<G.vexnum ;i++)
			{
				if(i!=v0)
				{
					showPath(path,i,v0);
					cout<<dist[i]<<endl;
				}
			}
	 }
	 //MiniSpanTree_PRIM(G,G.vexs [2]);
}
コピペでpaddingとborderを幅(width)と高さ(height)に含める(CSS)
JAVA-1.1-JAVA概要