数据结构例程——线性表顺序存储的应用

本文是数据结构基础系列网络课程(2)：线性表中第6课时线性表顺序存储的应用中所讲的例程。

例：删除元素

问题：已知长度为n的线性表A采用顺序存储结构，设计算法，删除线性表中所有值为x的数据元素。
要求：时间复杂度为O(n)、空间复杂度为O(1)的算法

解法0：用基本运算实现，不满足复杂度要求
（注：本文中所需要的list.h和list.cpp见点击参照…）

#include "list.h"
#include <stdio.h>

void delnode1(SqList *&L,ElemType x)
{
    int i;
    ElemType e;
    while((i=LocateElem(L,x))>0)
    {
        ListDelete(L, i, e);
    }
}

//用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);

    delnode1(sq, 7);

    printf("删除后 ");
    DispList(sq);
    return 0;
}

解法1：复制要保留的元素

#include "list.h"
#include <stdio.h>

void delnode2(SqList *&L,ElemType x)
{
    int k=0,i; //k记录非x的元素个数
    for (i=0; i<L->length; i++)
        if (L->data[i]!=x)
        {
            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);

    delnode2(sq, 7);

    printf("删除后 ");
    DispList(sq);
    return 0;
}

例：分离元素

问题 :设顺序表有10个元素，其元素类型为整型。 设计一个算法，以第一个元素为分界线，将所有小于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面

解法1：

#include "list.h"
#include <stdio.h>

void move1(SqList *&L)
{
    int i=0,j=L->length-1;
    ElemType pivot=L->data[0];  //以data[0]为基准
    ElemType tmp;
    while (i<j)             //从区间两端交替向中间扫描,直至i=j为止
    {
        while (i<j && L->data[j]>pivot)
            j--;            //从右向左扫描,找第1个小于等于pivot的元素
        while (i<j && L->data[i]<=pivot)
            i++;            //从左向右扫描,找第1个大于pivot的元素
        if (i<j)
        {
            tmp=L->data[i]; //L->data[i]和L->data[j]进行交换
            L->data[i]=L->data[j];
            L->data[j]=tmp;
        }
    }
    tmp=L->data[0];         //L->data[0]和L->data[j]进行交换
    L->data[0]=L->data[j];
    L->data[j]=tmp;
}


//用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);

    move1(sq);

    printf("移动后 ");
    DispList(sq);
    return 0;
}

解法2：

#include "list.h"
#include <stdio.h>

void move2(SqList *&L)
{
    int i=0,j=L->length-1;
    ElemType pivot=L->data[0];  //以data[0]为基准
    while (i<j)                 //从顺序表两端交替向中间扫描,直至i=j为止
    {
        while (j>i && L->data[j]>pivot)
            j--;                //从右向左扫描,找一个小于等于pivot的data[j]
        L->data[i]=L->data[j];  //找到这样的data[j],放入data[i]处
        i++;
        while (i<j && L->data[i]<=pivot)
            i++;                //从左向右扫描,找一个大于pivot的记录data[i]
        L->data[j]=L->data[i];  //找到这样的data[i],放入data[j]处
        j--;
    }
    L->data[i]=pivot;
}


//用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);

    move2(sq);

    printf("移动后 ");
    DispList(sq);
    return 0;
}