顺序表

顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第 1 个元素存储在线性表的起始位置，第 i 个元素存储在线性表的起始位置，第 i 个元素的存储位置后紧接着存储的是第 i+1 个元素，称 i 为元素 ai 在线性表中的位序。
顺序表的特点是逻辑顺序与物理顺序相同。

定义一些变量

typedef int Status;
# define OVERFLOW -2
# define OK 1
# define TURE  1
#define FALSE  0
#define ERROR  0
#define INFEASIBLE  -1

数据结构的存储类型

typedef int ElemType;               //定义ElemType类型为int
# define  LIST_INIT_SIZE   100     // 线性表存储空间的初始分配量
# define   LISTINCREMENT    10    // 线性表存储空间的分配增量
//在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的
//一旦数据空间占满，就开辟一块更大的存储空间，用以替换原来的存储空间

typedef struct                //若后面不再用，可省略结构名
{
    ElemType *elem;         //存储空间基址
    int    length;      //当前表长（特指元素个数）
    int   listsize;     //当前分配的存储容量（以sizeof(ElemType)为单位）
} SqList;

初始化顺序表

Status InitList_Sq(SqList &L)
{
    //构造一个空的线性表L。
    L.elem = new ElemType[LIST_INIT_SIZE];
    if  ( ! L.elem )
        exit ( OVERFLOW ) ; // 存储分配失败
    //exit的功能为:退出当前运行的程序，并将参数value返回给主调进程。
    //exit(OVERFLOW)的含义就是:当程序运算出现上溢时,退出程序
    //返回OVERFLOW的值给主调进程报错

    L.length = 0;             // 空表长度为0
    L.listsize = LIST_INIT_SIZE;  // 初始存储容量
    return   OK;
}

销毁/清空顺序表

void DestroyList(SqList &L)
{
    if (L.elem) delete[] L.elem;    //释放存储空间
    L.length=0;
    L.listsize=0;
}

void ClearList(SqList &L)
{
    L.length=0;                //将线性表的长度置为0
}

获取表长，判断是否为空

int GetLength(SqList L)
{
    return (L.length);
}

int IsEmpty(SqList L)
{
    if (L.length==0)
        return TRUE;
    else
        return FALSE;
}

获取顺序表的元素/位置

//获取线性表某个元素
Status GetElem(SqList L, int i, ElemType &e)
{
    if (i<1||i>L.length) return ERROR;
    //判断i值是否合理，若不合理，返回ERROR
    e=L.elem[i-1];   //第i-1单元存储第i个数据
    return OK;
}

int LocateElem(SqList L,ElemType e)
{
    for (int i=0; i< L.length; i++)
        if (L.elem[i]==e) return i+1;
    return 0;
}

插入元素

Status ListInsert_Sq(SqList &L,int i,ElemType e)
{
    if(i<1 || i>L.length+1) return ERROR;            //i值不合法
    if (L.length==L.listsize)//当前存储空间已满，增加分配
    {
        ElemType *newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
        if (!newbase)  exit(OVERFLOW); //存储分配失败
        L.elem=newbase;  //新基址
        L.listsize+=LISTINCREMENT; //增加存储容量
    }
//先判断当前的指针是否有足够的连续空间，如果有，扩大mem_address指向的地址，并且将mem_address返回
//如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来mem_address所指内存区域
//（注意：原来指针是自动释放，不需要使用free），同时返回新分配的内存区域的首地址。即重新分配存储器块的地址。
    /*int* q = &(L.elem[i-1]); //q为插入位置
    for (int* p = &L.elem[L.length-1]; p>=q; p--)
        *(p+1)=*p;  //插入位置之后的元素右移
    *q=e;           //插入e
    ++L.length;     //表长增1*/
    for(int j = L.length; j >= i; j--)
    {
        L.elem[j] = L.elem[j-1];
    }
    L.elem[i-1] = e;
    ++L.length;
    return OK;
}

删除元素

Status ListDelete_Sq(SqList &L,int i,ElemType &e)
{
    if (i<1||i>L.length)
        return ERROR;   //i值不合法
    /*int* p=&(L.elem[i-1]);    //p为被删除元素的位置
    e=*p;           //被删除元素的值赋给e
    int* q=L.elem + L.length-1;     //表尾元素的位置
      for(++p; p<=q; ++p)
          *(p-1)=*p;        //被删除元素之后的元素左移
    --L.length;     //表长减1*/
    e = L.elem[i-1];
    for(int j = i; j <= L.length-1; j++)
    {
        L.elem[j-1] = L.elem[j];
    }
    L.length--;
    return OK;
}

显示所有元素的值

void showList(SqList L)
{
    for(int i = 0; i < L.length; i++)
    {
        cout << L.elem[i] << " ";
    }
    cout << endl;
}


关于顺序表的相关题型

1.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空显示出错信息并退出运行。
Status ListDeletemin_Sq(SqList &L, ElemType &e)
{
    if(L.length == 0)
        return ERROR;
    e = L.elem[0];
    int t = 0;
    for(int i = 1; i < L.length; i++)
    {
        //e < L.elem[i] 找最大
        if(e > L.elem[i])//找最小
        {
            e = L.elem[i];
            t = i;
        }
    }
    L.elem[t] = L.elem[L.length-1];
    L.length--;
    return TURE;
}
2.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)
void reverseList(SqList &L)
{
    int temp;
    for(int i = 0; i < (L.length+1)/2 ; i++)
    {
        temp = L.elem[i];
        L.elem[i] = L.elem[L.length-i-1];
        L.elem[L.length-i-1] = temp;
    }
}
3.对长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，该算法对删除线性表中所有为x的数据元素
void DeleteSameSq2(SqList &L, ElemType e)
{
    int sum = 0;
    for(int i = 0; i < L.length; i++)
    {
        if(L.elem[i] != e)
        {
            L.elem[sum] = L.elem[i];
            sum++;
        }

    }
    L.length = sum;
}

void DeleteSameSq(SqList &L, ElemType e)
{
    int sum = 0;
    for(int i = 0; i < L.length; i++)
    {
        if(L.elem[i] == e)
        {
            sum++;
        }
        else
            L.elem[i-sum] = L.elem[i];
    }
    L.length -= sum;
}
4.从有序顺序表中删除其值在给定值s与t之间的所有元素，如果s或t不合法或顺序表为空，则显示错误信息并退出。
Status deleteSTSq(SqList &L, ElemType s, ElemType t)
{
    if(s > L.elem[(L.length-1)] || t < L.elem[0] || s>=t || L.length == 0)
    {
        cout << "false" << endl;
        return ERROR;
    }

    int starts = 0;
    int ends = 0;
    for(int i = 0; i < L.length; i++)
    {

        if(L.elem[i] < s)
        {
            starts = i;
        }
        if(L.elem[i] <= t)
        {
            ends = i;
        }
    }
    int loop = ends - starts;
    for(int i = starts; i < (L.length-loop); i++)
    {
        L.elem[i+1] = L.elem[i+loop];
    }
    L.length -= loop;
    return OK;
}

Status deleteSTSq(SqList &L, ElemType s, ElemType t)
{
    if(s > L.elem[(L.length-1)] || t < L.elem[0] || s>=t || L.length == 0)
    {
        cout << "false" << endl;
        return ERROR;
    }
    
    int sum = 0;
    for(int i = 0; i < L.length; i++)
    {
        if(L.elem[i] < s || L.elem[i] > t)
        {
            L.elem[sum] = L.elem[i];
            sum++;
        }
    }
    L.length = sum;
}
5 从顺序表中删除其值在给定值s与t之间的所有元素（含s,t），如果s或t不合理或顺序表为空，则显示出错信息并退出运行。
Status DeleteSq5(SqList &L, ElemType s, ElemType t)
{
    if(L.length == 0 || s >= t)
    {
        cout << "false" << endl;
        return ERROR;
    }

    int sum = 0;
    for(int i = 0; i < L.length; i++)
    {
        if(L.elem[i] < s || L.elem[i] > t)
        {
            L.elem[sum] = L.elem[i];
            sum++;
        }
    }
    L.length = sum;
    return OK;
}
6 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
void DeleteRepeatSq(SqList &L)
{
    int sum = 1;
    for(int i = 1; i < L.length; i++)
    {
        if(L.elem[i] != L.elem[i-1])
        {
            L.elem[sum] = L.elem[i];
            sum++;
        }
    }
    L.length = sum;
}
7 将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
void IntergrateSq(SqList &La, SqList &Lb, SqList &Lc)
{
    int i = 0;
    int j = 0;
    int t = 0;
    Lc.length = La.length + Lb.length;

    while(i < La.length && j < Lb.length)
    {
        if(La.elem[i] <= Lb.elem[j])
        {
            Lc.elem[t++] = La.elem[i++];
        }
        else
        {
            Lc.elem[t++] = Lb.elem[j++];
        }
    }

    while(i < La.length)
    {
        Lc.elem[t++] = La.elem[i++];
    }

    while(j < Lb.length)
    {
        Lc.elem[t++] = Lb.elem[j++];
    }
}
8 已知在一维数组A[m+n]中依次存放两个线性表(a1,a2,a3....,am) 和 (b1,b2,b3....,bn) 。试编写一个函数，将数组中两个顺序表的位置互换，即将(b1,b2,b3....,bn) 放在 (a1,a2,a3....,am) 之前。

思路 :先将A(a,b)倒置为A(b', a')，在将其前 n 项倒置，然后将其后 m
项倒置。

void ReverseList(SqList &L,ElemType left, ElemType right,int arraySize)
{
    if(left >= right || right >= arraySize)
    return ERROR;
    int temp;
    for(int i = 0; i < ( right-left + 1)/2; i++)
    {
        temp = L.elem[i + left];
        L.elem[i + left] = L.elem[(right - i)];
        L.elem[(right - i)] = temp;
    }
}
void Exchange(DataType A[], int m, int n, int arraySize)
{
    ReverseList(A,0,A.length-1,arraySize);
    ReverseList(A,0,n-1,arraySize);
    ReverseList(A,n,n+m-1,arraySize);
}
9 线性表中的元素递增有序且按顺序存储与计算机内。要求设计一算法，完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素位置相交换，若找不到则将其插入表中并使表中元素仍递增有序。

思路：用折半查找法查找数值 x ,最后一个元素没有后继不用交换，插入前将其位置以后元素全部后移。

void Searchx(SqList &L, ElemType x)
{
    int starts  = 0;
    int ends = L.length-1;
    int mid;

    while(starts <= ends)
    {
        t = (ends+starts)/2;

        if(L.elem[mid] == x)
            break;

        if(L.elem[mid] > x)
            ends = mid - 1;

        if(L.elem[mid] < x)
            starts = mid + 1;

    }

    if(L.elem[mid] == x && mid != L.length-1)
    {
        L.elem[mid] = L.elem[mid+1];
        L.elem[mid+1] = x;
    }

    if(ends < starts)
    {
        L.length+=1;
        for(int i = L.length; i > starts; i--)
        {
            L.elem[i] = L.elem[i-1];
        }
        L.elem[starts] = x;
    }

}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,794评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,050评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,587评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,861评论 1赞 290
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,901评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,898评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,832评论 3赞 416
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,617评论 0赞 271
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,077评论 1赞 308
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,349评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,483评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,199评论 5赞 341
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,824评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,442评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,632评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,474评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,393评论 2赞 352