リニアテーブルチェーンストレージの練習問題

1819 ワード

Q 1:L 1とL 2がそれぞれ2つの単鎖テーブルのヘッダノードを指すことが知られており、その長さがそれぞれm、nであることが知られているので、L 2をL 1の後ろに接続するアルゴリズムを設計してください.このアルゴリズムを実現し,テストを完了し,このアルゴリズムの複雑さを解析した.
A:l 1のテールポインタをl 2ヘッダノードに向けるだけで、アルゴリズムは簡単ですが、l 1のテールポインタをl 2ヘッダノードに向けた後、無駄なl 2のヘッドポインタfreeを落とすことを忘れないでください.
status connectlinklist(linklist l1,linklist l2){
    linklist p=l1->next;
    while(p->next)
        p=p->next;
    p->next=l2->next;
    free(l2);
}

アルゴリズムの複雑さはO(m)であり,L 1のヘッダノードからそのテールノードを見つけるだけで,L 2の長さnに関係なくL 1の長さに関係する.
Q 2:単一チェーンテーブルLがインクリメントされているか否かを判定するアルゴリズムを設計する.このアルゴリズムを実現する
A:チェーンテーブルを巡って、前の要素が後の要素より大きい場合があるかどうかを判断すればよい
status isincrease(linklist l){
    linklist p=l->next,q;
    while(p){
        q=p;
        while(q->next){
            if(p->data>=q->next->data)
                return ERROR;
            else
                q=q->next;
        }
        p=p->next;
    }
    return OK;
}