データ構造(陳越、何欽銘)--第二週プログラミング作業

＊＊
02-リニア構造1の2つの秩序チェーンシーケンスの統合(15分)
＊＊本題では、関数を実現し、2つのチェーンで表されるインクリメントされた整数系列を、1つのインクリメントされていない整数系列にマージする必要があります.
関数インターフェースの定義:

List Merge( List L1, List L2 );

List構造の定義は以下の通りである.

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /*        */
    PtrToNode   Next; /*            */
};
typedef PtrToNode List; /*         */

L 1およびL 2は、所定の先頭ノードの単一チェーンテーブルであり、そのノードに格納されているデータは、インクリメント順序である.関数Mergeは、L 1とL 2をインクリメントしない整数系列に結合します.元のシーケンスの結点を直接使用して、帰結後の先頭結点のチェーンポインタを返します.
審判試験手順の例:

#include 
#include 

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /*        */
void Print( List L ); /*       ；      NULL */

List Merge( List L1, List L2 );

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/*            */

入力例:3 1 3 5 5 2 4 6 10出力例:1 3 4 6 8 10 NULL NULL

List Merge(List L1, List L2)
{
    List Head, Rear, l1, l2;
    Head = (List)malloc(sizeof(PtrToNode));
    Head -> Next = NULL;
    Rear = Head;
    l1 = L1 -> Next;
    l2 = L2 -> Next;
    
    while(l1 && l2)
    {
            if(l1 -> Data < l2 -> Data)
            {
                Rear -> Next = l1;
                Rear = Rear -> Next;
                l1 = l1 -> Next;
            }
            
            else
            {
                Rear -> Next = l2;
                Rear = Rear -> Next;
                l2 = l2 -> Next;
            }
    }
    
    for(;l1;l1 = l1 -> Next)
    {
        Rear -> Next = l1;
        Rear = Rear -> Next;
    }
    
    for(;l2;l2 = l2 -> Next)
    {
        Rear -> Next = l2;
        Rear = Rear -> Next;
    }
    
    L1 -> Next = NULL;
    L2 -> Next = NULL;
    
    return Head;
}

＊＊
02-線形構造2一元多項式の乗算と加算(20分)
＊設計関数はそれぞれ2元の多項式の積と和を求めます.
入力形式:入力は2行に分けて、各行はそれぞれ多項非ゼロ項の個数を与えてから、指数降順で多項非ゼロ係数と指数(絶対値は1000を超えない整数)を入力します.数値をスペースで区切る.
出力フォーマット:出力は2ラインに分けて、積多項式と多項式非ゼロ項の係数と指数をそれぞれ指数関数的に降順して出力します.数字の間はスペースで区切られていますが、最後にスペースが余ってはいけません.0以上は0を出力します.
入力例:4 4 4-5 6 1-2 0 3 20-7 3 1出力例:15 24-25 22 21-10 20-21 35 6-33 5 4-15 3 18 2-6 5 20 20-4 4-5 9 1-2 0

#include 
#include 

typedef struct PolyNode* Polynomial;
struct PolyNode
{
    int coef;
    int expon;
    Polynomial link;
};

Polynomial ReadPoly();
void Attach(int c, int e, Polynomial *pRear);
Polynomial Add(Polynomial P1, Polynomial P2);
Polynomial Mult(Polynomial P1, Polynomial P2);
void PrintPoly(Polynomial P);

int main()
{
    Polynomial P1, P2, PP, PS;

    P1 = ReadPoly();
    P2 = ReadPoly();
    PP = Mult(P1, P2);
    PrintPoly(PP);
    PS = Add(P1, P2);
    PrintPoly(PS);

    return 0;
}

Polynomial ReadPoly()
{
    Polynomial P, Rear, t;
    int c, e, N;

    scanf("%d", &N);
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P -> link = NULL;
    Rear = P;
    while(N--)
    {
        scanf("%d %d", &c, &e);
        Attach(c, e, &Rear);
    }
    t = P;
    P = P->link;
    free(t);

    return P;
}

void Attach(int c, int e, Polynomial *pRear)
{
    Polynomial P;

    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->coef = c;
    P->expon = e;
    P->link = NULL;
    (*pRear)->link = P;
    *pRear = P;
}

Polynomial Mult(Polynomial P1, Polynomial P2)
{
    Polynomial P, Rear, t1, t2, t;
    int c, e;

    if (!P1 || !P2)
        return NULL;

    t1 = P1;
    t2 = P2;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->link = NULL;
    Rear = P;
    while(t2)
    {
        Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);
        t2 = t2->link;
    }

    t1 = t1->link;
    while(t1)
    {
        t2 = P2;
        Rear = P;
        while(t2)
        {
            c = t1->coef * t2->coef;
            e = t1->expon + t2->expon;
            while(Rear->link && Rear->link->expon > e)
                Rear = Rear->link;

            if(Rear->link && Rear->link->expon == e)
            {
                if(Rear->link->coef + c)
                    Rear->link->coef += c;
                else
                {
                    t = Rear->link;
                    Rear->link = t->link;
                    free(t);
                }
            }

            else
            {
                t = (Polynomial)malloc(sizeof(struct PolyNode));
                t->coef = c;
                t->expon = e;
                t->link = Rear->link;
                Rear->link = t;
                Rear = Rear->link;
            }
            t2 = t2->link;
        }
        t1 = t1->link;
    }
    t2 = P;
    P = P->link;
    free(t2);

    return P;
}

Polynomial Add(Polynomial P1, Polynomial P2)
{
    Polynomial P, t1, t2, Rear;

    t1 = P1;
    t2 = P2;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->link = NULL;
    Rear = P;
    while(t1 && t2)
    {
        if(t1->expon == t2->expon)
        {
            if(t1->coef+t2->coef)
            {
                Attach(t1->coef+t2->coef, t1->expon, &Rear);
            }
            t1 = t1->link;  t2 = t2->link;
        }

        else if(t1->expon > t2->expon)
        {
            Attach(t1->coef, t1->expon, &Rear);
            t1 = t1->link;
        }

        else
        {
            Attach(t2->coef, t2->expon, &Rear);
            t2 = t2->link;
        }
    }

    while(t1)
    {
        Attach(t1->coef, t1->expon, &Rear);
        t1 = t1->link;
    }

    while(t2)
    {
        Attach(t2->coef, t2->expon, &Rear);
        t2 = t2->link;
    }

    t1 = P;  P = P->link;  free(t1);
    return P;
}

void PrintPoly(Polynomial P)
{
    int flag = 0;

    if(!P)
    {
        printf("0 0
");
        return;
    }

    while(P)
    {
        if(!flag)
            flag = 1;
        else
            printf(" ");
        printf("%d %d", P->coef, P->expon);
        P = P->link;
    }
    printf("
");
}

02-リニア構造3 Reversing Linked List(25分)
Given a constant K and a singly linked list L,You are supposed to reverse the links of every K elements on L.For example,given L being 1→2→3→4→5、if K=3、then must output 3→2→5→4if K=4,you must output 4→3→2→1→5→6.
Input Speciification:Each input file contains one test case.For each case、the first line contains the address of the first node、a positive N(≦10の5回のべきess)which the total number of nodes、andandaaadededes、and inininininininininininininininininininininininininininininindes、and the the the the the the the the the the the the the the the theaaaaaaaaaaadedededededededededeve integer、and NULL is represented by-1.
The n N lines follow、each describes a node in the format:Addres Data Next
where Addres is the position of the node,Data is an integer,and Next is the position of the next node.
Output Specification:For each case,output the resung orded linked list.Each node occupies a line,and is presd in the same format.
Sample Input:0016 4 4 000009 1 12309 68237-1 33218 3 000009 68237 12309 2 33218
Sample Output:00000 4 33218 3 12309 12309 2 00100 1 9999 5 68237 68237-1

#include
typedef struct unit Data;
struct unit{
	int address;//  
	int data;//  
	int nextAddress;//      
	int nextIndex;//           
};
int reverse(Data b[],int legal,int k){//    
	int i,j;
	int tail,ptr1,ptr2;//tail             
	int head;
	int firstTime=0;//         
	ptr1=0;
	ptr2=1;
	if(k==1||legal==1)
		return -1;
	else{
		for(i=0;i<legal/k;i++){//    k     
			for(j=0;j<k-1;j++){//                   
				b[ptr2].nextIndex=ptr1;
				ptr1++;
				ptr2++;
			}
			firstTime++;
			if(firstTime==1){//                       
				head=ptr1;
				tail=0;
			}
			else{//                                      
				b[tail].nextIndex=ptr1;
				tail+=k;
			}
			if(i+1>=legal/k)//                                   
				b[tail].nextIndex=ptr2;
			else{
				ptr1++;
				ptr2++;
			}
		}
	}
	return head;
}
void adjust(Data b[],int legal,int head){//         nextAddress  
	int i;
	for(i=0;i<legal;i++){
			if(i+1<legal){
				b[head].nextAddress=b[b[head].nextIndex].address;
				head=b[head].nextIndex;
			}
			else
				b[head].nextAddress=-1;
		}
}
void output(Data b[],int legal,int head){//  
	int i=0;
	if(head==-1){//           1         
		for(i=0;i<legal;i++){
			if(b[i].nextAddress==-1)
				printf("%05d %d %d",b[i].address,b[i].data,b[i].nextAddress);
			else
				printf("%05d %d %05d
",b[i].address,b[i].data,b[i].nextAddress);
		}
	}
	else{
		for(i=0;i<legal;i++){
			if(b[head].nextAddress==-1)
				printf("%05d %d %d",b[head].address,b[head].data,b[head].nextAddress);
			else
				printf("%05d %d %05d
",b[head].address,b[head].data,b[head].nextAddress);
			head=b[head].nextIndex;
		}
	}
}
int main(){
	Data a[100001];//                       
	Data temp;
	int FirstAddress,N,k; //              
	int head;
	int i,legal; //legal       
	scanf("%d %d %d",&FirstAddress,&N,&k);
	Data b[N];// b      N，         
	for(i=0;i<N;i++){ //        a
		scanf("%d %d %d",&temp.address,&temp.data,&temp.nextAddress);
		a[temp.address]=temp;
		if(temp.address==FirstAddress)//          b    
			b[0]=temp;
	}
	i=0;
	while(b[i].nextAddress!=-1){//       a       b  ，   nextIndex         
		b[i].nextIndex=i+1;
		b[i+1]=a[b[i].nextAddress];
		i++;
	}
	legal=i+1;//      
	head=reverse(b,legal,k);
	if(head!=-1)
		adjust(b,legal,head);
	output(b,legal,head);

	return 0;
}

02-線形構造4 Pop Sequence(25分)
Given a stack which can keep M numbers at most.Push N numbers in the ordes of 1,2,3,…,N and pop radomly. You ararsupposed to tell ifea given sequence of numbes isa possible posible pop sequence of FoForeck.Forever.Foreck.5.Forever.aaable.Foreck.5.fs.Foreck.aaaable.5.fs.s.fs.s.s.s.s.aaaaaaap SeSepapapapapapapapapapapapapapapapapapapapapapapapat 3,2,1,7,5,6,4.
Input Specification:Each input file contains one test case.For each case,the first line contains 3 numbers(all no more than 1000):M(the maximm capacity of the stack),N(the length of push Sequence),line of the fonce e e of line of theeach contains a pop sequence of N numbers.All the numbers in a line are separated by a space.
Output Specification:For each pop sequence、print in one line「YES」if it is indeed a possible pop sequence of the stack、or「NO」if not.
Sample Input:5 5 5 1 2 3 5 5 5 5 6 6 6 6 6 5 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 3 3 3 3 Sample Output:YES NO NO YES NO NO YES NO NO NO NO

#include 
#define MAXSIZE 1000

void Output(int number[], int M, int N);

int main()
{
    int M, N, K;
    int i, j;
    int number[MAXSIZE][MAXSIZE];
    
    scanf("%d %d %d", &M, &N, &K);


    /*     */
    if(K)
    {
        for(i = 0; i < K; i++)
        {
            for(j = 0; j < N; j++)
            {
                scanf("%d", &number[i][j]);
            }

        }
    }

    for(i = 0; i < K; i++)
    {
        Output(number[i], M, N);
    }

    return 0;
}

void Output(int number[], int M, int N)
{
    int i, j, h;
    int flag = 1;
    for(i = 0; i < N; i++)
    {
        if((number[i]) > (M + i))
        {
            flag = 0;
            break;
        }
    }
    int max, beforemax;
    for(i = 0; i < N-2; i++)
    {
        max = number[i];
        for(j = i+ 1; j < N-1; j++)
        {
            if(number[j] < max)
            {
                beforemax = number[j];
                for(h = j+1; h < N; h++)
                {
                    if((number[h] < max) && (number[h] > beforemax))
                    {
                        flag = 0;
                        break;
                    }
                }
            }
        }
    }
    if(flag)
        printf("YES
");
    else
        printf("NO
");
}