データ構造実践——単鎖表:逆置き、接続と増分判断

本稿では、データ構造インフラストラクチャ・シリーズのネットワーク・カリキュラム(2):リニア・テーブルの実践プロジェクトについて説明します.
【項目-単一チェーンテーブルアルゴリズム】(プログラムにおいて既に実現された単一チェーンテーブルアルゴリズムを利用しており、ヘッダファイルLinkList.h及びその中の関数の実現は単一チェーンテーブルアルゴリズムライブラリを参照)
1、アルゴリズムを設計し、1つの先頭ノードのデータドメインをa 1,a 2,...,an(n≧3)の単一チェーンテーブルのすべてのノードを逆置き、すなわち最初のノードのデータドメインをan,...,最後のノードのデータドメインをa 1にする.このアルゴリズムを実装し,テストを完了する.［参考解答］(プログラムにおいて既に実装されているシングルチェーンテーブルアルゴリズムを利用し、ヘッダファイルLinkList.h及びその中の関数の実装はシングルチェーンテーブルアルゴリズムライブラリを参照)

#include <stdio.h>
#include <malloc.h>
#include "linklist.h"
void Reverse(LinkList *&L)
{
    LinkList *p=L->next,*q;
    L->next=NULL;
    while (p!=NULL)     //       
    {
        q=p->next;      // q  *p        
        p->next=L->next;    //   *p           
        L->next=p;
        p=q;            // p       
    }
}

int main()
{
    LinkList *L;
    ElemType a[]= {1,3,5,7, 2,4,8,10};
    CreateListR(L,a,8);
    printf("L:");
    DispList(L);
    Reverse(L);
    printf("   L： ");
    DispList(L);
    DestroyList(L);
    return 0;
}

2、既知L 1とL 2はそれぞれ2つの単鎖テーブルのヘッダノードを指し、その長さはそれぞれm、nであることが知られているので、アルゴリズムを設計してL 2をL 1の後ろに接続してください.このアルゴリズムを実現し,テストを完了し,このアルゴリズムの複雑さを解析した.［参考解答］(プログラムにおいて既に実装されているシングルチェーンテーブルアルゴリズムを利用し、ヘッダファイルLinkList.h及びその中の関数の実装はシングルチェーンテーブルアルゴリズムライブラリを参照)

#include <stdio.h>
#include <malloc.h>
#include "linklist.h"

void Link(LinkList *&L1, LinkList *&L2)
{
    LinkList *p = L1;
    while(p->next != NULL)   //  L1    
        p = p->next;
    p->next = L2->next;  // L2          L1     
    free(L2);   //        L2    
}

int main()
{
    LinkList *A, *B;
    int i;
    ElemType a[]= {1,3,2,9};
    ElemType b[]= {0,4,7,6,5,8};
    InitList(A);
    for(i=3; i>=0; i--)
        ListInsert(A, 1, a[i]);
    InitList(B);
    for(i=5; i>=0; i--)
        ListInsert(B, 1, b[i]);
    Link(A, B);
    printf("A:");
    DispList(A);
    DestroyList(A);
    return 0;
}

アルゴリズムの複雑さはO(m)であり,L 1のヘッダノードからそのテールノードを見つけるだけで,L 2の長さnに関係なくL 1の長さに関係する.　　
3、単一チェーンテーブルLがインクリメントされているかどうかを判断するアルゴリズムを設計する.このアルゴリズムを実装し,テストを完了する.［参考解答］(プログラムにおいて既に実装されているシングルチェーンテーブルアルゴリズムを利用し、ヘッダファイルLinkList.h及びその中の関数の実装はシングルチェーンテーブルアルゴリズムライブラリを参照)

#include <stdio.h>
#include <malloc.h>
#include "linklist.h"

bool increase(LinkList *L)
{
    LinkList *p = L->next, *q;  //p   1     
    if(p != NULL)
    {
        while(p->next != NULL)
        {
            q = p->next;   //q p   
            if (q->data > p->data)   //      ，        
                p = q;
            else
                return false;    //             ，     
        }
    }
    return true;
}

int main()
{
    LinkList *A, *B;
    int i;
    ElemType a[]= {1, 3, 2, 9};
    ElemType b[]= {0, 4, 5 ,6, 7, 8};
    InitList(A);
    for(i=3; i>=0; i--)
        ListInsert(A, 1, a[i]);
    InitList(B);
    for(i=5; i>=0; i--)
        ListInsert(B, 1, b[i]);
    printf("A: %c
", increase(A)?'Y':'N');
    printf("B: %c
", increase(B)?'Y':'N');
    DestroyList(A);
    DestroyList(B);
    return 0;
}