C言語アルゴリズムとデータ構造順序表の基本操作と実験事例

C言語アルゴリズムとデータ構造順序表の基本操作と実験事例
実験要求:
1.(80%)順序表の基本演算を完成する:初期化、表示、長さを求める、空を判定する、満を判定する、挿入する、削除する、要素を取るなど、そして主関数テストアルゴリズムを編纂する.2.(90%)設計アルゴリズム:1つの要素を秩序化された順序テーブルに挿入し、順序テーブルを秩序化させ、主関数テストアルゴリズムを記述する.3.(100%)AとBの2つの順序表を設定し、その要素を小さい順から大きい順に並べます.AとBのすべての要素を記述して、新しい小さいから大きいまでの順序表Cを構成するアルゴリズムを記述し、主関数テストアルゴリズムを記述する.ヒント:(1)アルゴリズム:整列テーブルのマージ.(2)秩序テーブルの生成は,人為的に入力してもよいし,コンテンツ2のアルゴリズム実装を呼び出すこともできる.

//          ，part 1,2,3
#include
#include
#include	//        ，      
#include	//             

#define MAXSIZE 1000	//        

typedef int elemtype;	//      

typedef struct	//       
{
	elemtype data[MAXSIZE];
	int last;
} datalist;
//     
//-----------------------------------------------------------------------
//    
int part1(void);
//    
char choiceitem();
//     
datalist * defaultlist(void);
//       
int addinfo(datalist * pl,int times);
//       
int deleteinfo(datalist * pl,int space);
//        ，   1  0
int ifempty(datalist * pl);
//        ，   1  0
int iffull(datalist * pl);
//      
int changeinfo(datalist * pl,int space,int change);
//    
void outputlist(datalist * pl);
//      
int lenthlist(datalist * pl);
//       
int insertinfo(datalist * pl,int space,int num);
//    
void deletelist(datalist * pl);
//-----------------------------------------------------------------------
//    
int part2(void);
//          
void rulenummade(datalist * pl);
//            
int findspace(datalist * pl,int num);
//-----------------------------------------------------------------------
//    
int part3(void);
//        
datalist * doublerulelistcontact(datalist * pc,datalist * pa,datalist * pb);

int main(void)
{
	system("color f0");
	system("title Main      dev: Ice2Faith");
    char sel;
	do	//                  
	{
		printf("\twelcome here

");
		printf("\t           

");//               
        printf("---------------------------------
");
		printf("     :
");
		printf("\t1.    
");
		printf("\t2.    
");
		printf("\t3.    
");
		printf("\t0.    
/> ");
		do	//               
		sel=getch();
		while(sel<'0'||sel>'3');
		system("cls");	//        
		switch(sel)
		{
			case '1':
				part1();
				break;
			case '2':
				part2();
				break;
			case '3':
				part3();
				break;
			case '0':
				break;
		}
	}while(sel!='0');


	return 0;
}

//    
int part1(void)
{
	system("title Part 1         dev: Ice2Faith");
	datalist * pl=defaultlist();	//     
	char chioce;
	do	//                 
    {
        chioce=choiceitem();	//             
        switch(chioce)	//       
        {
        case '1':
            outputlist(pl);	//    
            break;
        case '2':
            {
                int times;	//    
                fflush(stdin);
                printf("           :
/> ");
                scanf("%d",&times);
                printf("    %d    :
/> ",times);
                if(addinfo(pl,times)==-1)
					printf("    ，        

");
                break;
            }

        case '3':
            {
                int space;	//    
                fflush(stdin);
                printf("         :
/> ");
                scanf("%d",&space);
                if(deleteinfo(pl,space)==-1)
					printf("    ，      

");
                break;
            }

        case '4':
            {
                int space1,change;	//      
                fflush(stdin);
                printf("         :
/> ");
                scanf("%d",&space1);
                fflush(stdin);
                printf("        :
/> ");
                scanf("%d",&change);
                if(changeinfo(pl,space1,change)==-1)
					printf("    ，      

");
                break;
            }
        case '5':
            {
                int space2,num;	//    
                fflush(stdin);
                printf("          :
/> ");
                scanf("%d",&space2);
                fflush(stdin);
                printf("         :
/> ");
                scanf("%d",&num);
                if(insertinfo(pl,space2,num)==-1)
					printf("    ，      

");
                break;
            }
        case '6':
            deletelist(pl);	//    
            break;
        case '7':
            system("cls");	//  
            break;
        case '8':
            system("mode con cols=55 lines=40");	//        
            break;
        }
        if(chioce=='0')	//      
            printf("         !
");
        if(chioce!='7'&&chioce!='8')	//          
        {
            printf("
");
            system("pause");
        }
    }while(chioce!='0');
    free(pl);	//  pl  
    system("cls");
	return 0;
}

//    
char choiceitem()
{
	char choice;
	printf("\twelcome here

");	//        
	printf("   :

");
	printf("---------------------------------
");
	printf("\t1.     
");
	printf("\t2.    
");
	printf("\t3.    
");
	printf("\t4.    
");
	printf("\t5.    
");
	printf("\t6.     
");
	printf("\t7.  
");
	printf("\t8.         
");
	printf("\t0.     

");
	printf("---------------------------------
/> ");
	do	//     ，               
	{
	   choice=getch();
	}
	while(choice<'0'||choice>'8');
	printf("%c
",choice);
	return choice;
}

//     
datalist * defaultlist(void)
{
	datalist * pl;
	pl=(datalist *)malloc(sizeof(datalist));	//        datalist          
	pl->last=0;
	return pl;
}

//       
int addinfo(datalist * pl,int times)
{
	//check whether more than maxsize
	if(pl->last+times>MAXSIZE-1)	//           ，         ，    
		return -1;
	for(int i=0;i<times;i++)
	{
		scanf("%d",&(pl->data[pl->last+i]));
	}
	pl->last+=times;
	return 1;
}

//       
int deleteinfo(datalist * pl,int space)
{
	space-=1;
	if(space<0 ||space>=pl->last)	//          ，           ，  -1
		return -1;
	for(int i=space;i<=pl->last;i++)
		pl->data[i]=pl->data[i+1];
	pl->last--;
	return 1;
}

//        ，   1  0
int ifempty(datalist * pl)
{
	return pl->last==0?1:0;	//        ，    1    0
}

//        ，   1  0
int iffull(datalist * pl)
{
	return pl->last==MAXSIZE-1?1:0;	//        ，    1    0
}

//      
int changeinfo(datalist * pl,int space,int change)
{
	space-=1;
	if(space<0 ||space>pl->last-1)	//              
		return -1;
	pl->data[space]=change;
	return 1;
}

//    
void outputlist(datalist * pl)
{
    printf(">>> \t");
	if(pl->last==0)	//        ，   
		printf("    ，   ！！");
	for(int i=0;i<pl->last;i++)	//          
		printf("[%d]\t",pl->data[i]);
	printf("
");
}

//      
int lenthlist(datalist * pl)
{
	return pl->last;	//      
}

//       
int insertinfo(datalist * pl,int space,int num)
{
	space-=1;
	if(space<0 ||space>pl->last)	//          
		return -1;
	for(int i=pl->last;i>space;i--)	//                
		pl->data[i]=pl->data[i-1];
    pl->data[space]=num;	//        ，    +1
	pl->last++;
	return 1;
}

//    
void deletelist(datalist * pl)
{
    pl->last=0;	//      
}

//-----------------------------------------------------------------------
//    
int part2(void)
{
    system("title Part 2            dev: Ice2Faith");
	datalist * pl;	// pl          
	pl=defaultlist();
	char con='c';
    rulenummade(pl);	//            
	do	//        （  q）   
    {
        printf("        ，  :

");
        printf("---------------------------------
");
        printf("          

");	//        
        outputlist(pl);
        printf("---------------------------------
");
        printf("         :
/> ");	//                   
        int num;
        fflush(stdin);
        scanf("%d",&num);
        insertinfo(pl,findspace(pl,num),num);
        printf("           

");
        outputlist(pl);
        printf("---------------------------------
");
        printf("          ,     \'Q\',    :
/> ");	//             
        fflush(stdin);
        con=getch();
        if(con!='Q'||con!='q')
            system("cls");
    }while(con!='Q'&&con!='q');
    free(pl);
    return 0;
}
//          
void rulenummade(datalist * pl)
{
	srand((unsigned)time+rand());
	int lenth=rand()%300+10;	//                 
	int before=rand()%20+1;		//                  
	for(int i=0;i<=lenth;i++)	//  lenth ，        ，                   
	{
		srand((unsigned)time+rand());
		pl->data[i]=before;
		before+=rand()%8;
	}
	pl->last=lenth+1;	//      
}
//            
int findspace(datalist * pl,int num)
{
    int i=0;	//           
    while(num>pl->data[i]&&i<pl->last)
        i++;
    return i>pl->last?pl->last:++i;	//             ，         ，         
}

//-----------------------------------------------------------------------
//    
int part3(void)
{
    system("title Part 3             dev: Ice2Faith");
	datalist * pl;	//          pl,pk
	pl=defaultlist();
	datalist * pk;
	pk=defaultlist();
	datalist * pc;
	pc=defaultlist();
	char con='c';
	do 		//          
    {
       	rulenummade(pl); 	//              
        rulenummade(pk);
        printf("        ，  :

");
        printf("---------------------------------
");
        printf("        :

");	//           
        outputlist(pl);
        printf("---------------------------------
");
        outputlist(pk);
        printf("---------------------------------
");
        printf("   ，      ：
");
        system("pause");
        printf("         :

");	//           pl
        outputlist(doublerulelistcontact(pc,pl,pk));    //           pc           
        printf("---------------------------------
");
        printf("          ,     \'Q\',    :
/> ");	//              ，  ‘q'  
        fflush(stdin);
        con=getch();
        if(con!='Q'||con!='q')
            system("cls");
    }while(con!='Q'&&con!='q');
    free(pl);	//  pl,pk   
    free(pk);
    free(pc);
    return 0;
}

//        
datalist * doublerulelistcontact(datalist * pc,datalist * pa,datalist * pb)
{
	int i,j,k;
	i=0;
	j=0;
	k=0;
	while(pa->last>i && pb->last>j) //                     
	{
		if(pa->data[i]<pb->data[j])
			pc->data[k++]=pa->data[i++];
		else
			pc->data[k++]=pb->data[j++];
	}
	while(pa->last>i)   //                       
		pc->data[k++]=pa->data[i++];
	while(pb->last>j)
		pc->data[k++]=pb->data[j++];
	pc->last=pa->last+pb->last; //         
	return pc;  //      
}