線形表【項目4線形表--順序表適用】の一つ

/**線形表【項目4線形表--順序表応用】の一つ*Copyright(c)2015煙台大学コンピュータと制御工学院*All right reserved.*ファイル名:xianxingbiao.cpp*タイトル:データ構造実践——順序表応用*分類:データ構造順序表応用*writer:羅海員
*date:2015年9月15日*バージョン:V 1.0.1*オペレーティングシステム:XP*実行環境:VC 6.0*問題説明:順序構造で格納された線形テーブルを定義し、設計アルゴリズムは以下の作業を完了する:1、要素が[x,y]の間のすべての要素を削除し、アルゴリズムの時間複雑度がO(n)、空間複雑度がO(1)であることを要求する.2、奇数をすべての偶数の前に移動し、アルゴリズムの時間複雑度をO(n)、空間複雑度をO(1)とする.
ヒント:1.前に確立したアルゴリズムライブラリを十分に利用して、順序テーブルの確立、線形テーブルの出力の問題を解決する.        2.複雑度の要求、アルゴリズムを設計して専門の関数でアルゴリズムを実現します;        3.理論と実践を結合*入力説明:(以下の図)
*アルゴリズムライブラリには2つのファイルがあります.ヘッダファイル:list.h、シーケンステーブルデータ構造を定義するコード、マクロ定義、アルゴリズムを実現する関数の宣言を含む.ソースファイル:list.cppは、各種アルゴリズムを実現する関数の定義とテストコードmain関数*プログラム出力を含む:(以下の図)*/
 

//  
//1、     [x, y]       ，           O(n)，      O(1)；
//main    
#include "list.h"
#include <stdio.h>

//      ，    x y     
void delx2y(SqList *&L, ElemType x,  ElemType y)
{
    int k=0,i; //k   x     
    ElemType t;
    if(x>y)
    {
        t=x;
        x=y;
        y=t;
    }
    for (i=0; i<L->length; i++)
        if (L->data[i]<x || L->data[i]>y )  //    [x, y]     
        {
            L->data[k]=L->data[i];
            k++;
        }
    L->length=k;
}

// main     
int main()
{
    SqList *sq;
    ElemType a[10]= {5,8,7,0,2,4,9,6,7,3};
    CreateList(sq, a, 10);
    printf("    ");
    DispList(sq);

    delx2y(sq, 4, 7);

    printf("    ");
    DispList(sq);
    return 0;
}

 

//   ，        
#include <stdio.h>
#include <malloc.h>
#include "list.h"

//        
void CreateList(SqList *&L, ElemType a[], int n)
{
    int i;
    L=(SqList *)malloc(sizeof(SqList));
    for (i=0; i<n; i++)
        L->data[i]=a[i];
    L->length=n;
}

//      InitList(L)
void InitList(SqList *&L)   //     
{
    L=(SqList *)malloc(sizeof(SqList));
    //          
    L->length=0;
}

//     DestroyList(L)
void DestroyList(SqList *&L)
{
    free(L);
}

//       ListEmpty(L)
bool ListEmpty(SqList *L)
{
    return(L->length==0);
}

//       ListLength(L)
int ListLength(SqList *L)
{
    return(L->length);
}

//     DispList(L)
void DispList(SqList *L)
{
    int i;
    if (ListEmpty(L)) return;
    for (i=0; i<L->length; i++)
        printf("%d ",L->data[i]);
    printf("
");
}

//        GetElem(L,i,e)
bool GetElem(SqList *L,int i,ElemType &e)
{
    if (i<1 || i>L->length)  return false;
    e=L->data[i-1];
    return true;
}

//      LocateElem(L,e)
int LocateElem(SqList *L, ElemType e)
{
    int i=0;
    while (i<L->length && L->data[i]!=e) i++;
    if (i>=L->length)  return 0;
    else  return i+1;
}

//      ListInsert(L,i,e)
bool ListInsert(SqList *&L,int i,ElemType e)
{
    int j;
    if (i<1 || i>L->length+1)
        return false;   //       false
    i--;            //               
    for (j=L->length; j>i; j--) // data[i..n]        
        L->data[j]=L->data[j-1];
    L->data[i]=e;           //    e
    L->length++;            //      1
    return true;            //      true
}

//      ListDelete(L,i,e)
bool ListDelete(SqList *&L,int i,ElemType &e)
{
    int j;
    if (i<1 || i>L->length)  //       false
        return false;
    i--;        //               
    e=L->data[i];
    for (j=i; j<L->length-1; j++) // data[i..n-1]    
        L->data[j]=L->data[j+1];
    L->length--;              //      1
    return true;              //      true
}

 

//   
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef int ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int length;
} SqList;
void CreateList(SqList *&L, ElemType a[], int n);//        
void InitList(SqList *&L);//      InitList(L)
void DestroyList(SqList *&L);//     DestroyList(L)
bool ListEmpty(SqList *L);//       ListEmpty(L)
int ListLength(SqList *L);//       ListLength(L)
void DispList(SqList *L);//     DispList(L)
bool GetElem(SqList *L,int i,ElemType &e);//        GetElem(L,i,e)
int LocateElem(SqList *L, ElemType e);//      LocateElem(L,e)
bool ListInsert(SqList *&L,int i,ElemType e);//      ListInsert(L,i,e)
bool ListDelete(SqList *&L,int i,ElemType &e);//      ListDelete(L,i,e)#endif // LIST_H_INCLUDED
#endif