顺序表-静态顺序表

线性表，全名为线性存储结构。将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）。
顺序表，全名顺序存储结构。将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序表，即逻辑上相邻的元素在物理上也是相邻的。

顺序表的初始化

使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用表中的数据，顺序表还需要实时记录以下 2 项数据：

顺序表申请的存储容量；
顺序表的长度，也就是表中存储数据元素的个数；
首先自定义顺序表。

#define MaxSize 50
#define Error 0
typedef int ElemType;

typedef struct SqList{
    ElemType data[MaxSize];
    int Length;
}SeqList, *pSeqList;

注意这里定义了一个MaxSize用来指明顺序表申请的存储容量， Length指明表中数据元素的个数。
接着初始化顺序表。

//初始化
void InitSeqList(pSeqList psqlt) {
    assert(NULL != psqlt);
    memset(psqlt->data, 0, sizeof(ElemType)*MaxSize);
    psqlt->Length = 0;
}

顺序表插入元素

尾插，时间复杂度O(1)，总是从顺序表的末尾插入，没有元素的移动。

//尾插
void InsertLast(pSeqList psqlt, ElemType e) {
    assert(NULL != psqlt);
    if (psqlt->Length == MaxSize) {
        printf("SeqList is FULL.......\n");
        return;
    }
    psqlt->data[psqlt->Length++] = e;
}

首插，总是将新元素插入到顺序表的首地址位置，需要将顺序表的Length个元素往后移动一个位置，时间复杂度O(n)。

//首插
void InsertFront(pSeqList psqlt, ElemType e) {
    assert(NULL != psqlt);
    if (psqlt->Length == MaxSize) {
        printf("SeqList is FULL....\n");
    }
    for (int i=psqlt->Length; i>0; i--) {
        psqlt->data[i] = psqlt->data[i-1];
    }
    psqlt->data[0] = e;
    psqlt->Length ++;
}

在指定位置插入

1.通过遍历，找到数据元素要插入的位置
2.将要插入位置元素以及后续的元素整体向后移动一个位置
3.将元素放到腾出来的位置

//在指定位置i插入e
void Insert(pSeqList psqlt, ElemType e, int p) {
    assert(NULL != psqlt);
    if (psqlt->Length == MaxSize) {
        printf("SeqList is Full....\n");
        return;
    }
    if (psqlt->Length == 0) {
        printf("SeqList if Empty....\n");
        p = 1;
    }
    for (int i=psqlt->Length; i>=p; i--) {
        psqlt->data[i] = psqlt->data[i-1];
    }
    psqlt->data[p-1] = e;
    psqlt->Length ++;
}

顺序表删除元素

尾删，总是从顺序表的尾部开始删除元素，时间复杂度为O(1)，没有元素的移动。

//尾删
void PopLast(pSeqList psqlt) {
    assert(NULL != psqlt);
    if (psqlt->Length == 0) {
        printf("SeqList is empty....\n");
        return;
    }
    psqlt->Length --;
}

首删，总是从顺序表的首地址开始删除元素，将其后的Length-1个元素都需要向前移动一位置，时间复杂度为O(n)。

//首删
void PopFront(pSeqList psqlt) {
    assert(NULL != psqlt);
    if (psqlt->Length == 0) {
        printf("Seqlist is Empty......\n");
        return;
    }
    for (int i=0; i<psqlt->Length; i++) {
        psqlt->data[i] = psqlt->data[i+1];
    }
    psqlt->Length --;
}

在指定位置删除

只需找到目标元素，并将其后续所有元素整体前移 1 个位置即可。（后续元素整体前移一个位置，会直接将目标元素删除，可间接实现删除元素的目的。）

//删除指定位置i的数
void Pop(pSeqList psqlt, int p) {
    assert(NULL != psqlt);
    if (psqlt->Length == 0) {
        printf("SeqList if Empty....\n");
        return;
    }
    if (p > psqlt->Length || p < 1) {
        printf("not exixet...\n");
    }
    for (int i=p-1; i<psqlt->Length; i++) {
        psqlt->data[i] = psqlt->data[i+1];
    }
    psqlt->Length--;
}

逆置

//逆置
void Reverse(pSeqList psqlt) {
    assert(NULL != psqlt);
    int start = 0;
    int end = psqlt->Length - 1;
    while (start != end) {
        int temp = psqlt->data[start];
        psqlt->data[start] = psqlt->data[end];
        psqlt->data[end] = temp;
        start ++;
        end --;
    }
}

有序表删除重复元素

//有序表删除所有值重复的元素
void DeleteRepeat(pSeqList psqlt) {
    assert(NULL != psqlt);
    if (psqlt->Length == 0) {
        printf("SeqList is Empty....\n");
        return;
    }
    for (int i=0; i<psqlt->Length; i++) {
        if (psqlt->data[i] == psqlt->data[i+1]) {
            if (psqlt->data[0] == psqlt->data[1]) {
                for (int j=0; j<psqlt->Length; j++) {
                    psqlt->data[j] = psqlt->data[j+1];
                }
                psqlt->Length --;
            }
            for (int j=i; j<psqlt->Length; j++) {
                psqlt->data[j] = psqlt->data[j+1];
            }
            psqlt->Length --;
        }
    }
}

有序表拼接

//有序表拼接 s1+s2
void SeqlistJoin(pSeqList ps1, pSeqList ps2, pSeqList psqlt) {
    assert(NULL != ps1);
    assert(NULL != ps2);
    if (ps1->Length == 0 || ps2->Length == 0) {
        printf("Seqlist is Empty...\n");
        return;
    }
    if (ps1->Length + ps2->Length > MaxSize) {
        printf("Seqlist is Full...\n");
        return;
    }
    int i=0, j=0, k=0;
    while (i<ps1->Length && j<ps2->Length) {
        if (ps1->data[i] <= ps2->data[j]) {
            psqlt->data[k++] = ps1->data[i++];
        }
        else {
            psqlt->data[k++] = ps2->data[j++];
        }
    }
    while (i<ps1->Length) {
        psqlt->data[k++] = ps1->data[i++];
    }
    while (j<ps2->Length) {
        psqlt->data[k++] = ps2->data[j++];
    }
    psqlt->Length = k;
}

循环右移p个单位

//循环右移p个单位
void MoveP(pSeqList psqlt, int p) {
    assert(psqlt);
    pSeqList new;
    new = (SeqList *)malloc(sizeof(SeqList));
    for (int i=0; i<p-1; i++) {
        new->data[i] = psqlt->data[i];
        new->Length ++;
    }
    int j=p-1;
    for (int i=0; i<=p; i++) {
        psqlt->data[i] = psqlt->data[j];
        j++;
    }
    int k = p;
    for (int i=0; i<p; i++) {
        psqlt->data[k] = new->data[i];
        k++;
    }
}

找出list1和list2的中位数

//找出中位数
int M_Search(pSeqList list1, pSeqList list2) {
    assert(list1);
    assert(list2);
    int s1=0, d1=list1->Length-1, m1, s2=0, d2=list2->Length-1, m2;
    while (s1!=d1 || s2!=d2) {
        m1 = (s1+d1)/2;
        m2 = (s2+d2)/2;
        if (list1->data[m1] == list2->data[m2]) {
            return list2->data[m1];
        }
        if (list1->data[m1] < list2->data[m2]) {
            if ((s1+d1)%2 == 0) {
                s1 = m1;
                d2 = m2;
            }
            else {
                s1 = m1+1;
                d2 = m2;
            }
        }
        else {
            if ((s2+d2)%2 == 0) {
                d1 = m1;
                s2 = m2;
            }
            else {
                d1 = m1;
                s2 = m2+1;
            }
        }
    }
    return list1->data[s1]<list2->data[s2]?list1->data[s1]:list2->data[s2];
}

找出主元素

1> 有这样的一组数列，假设数列的第一个数是主元素，我们就计作主元素个数为1，假设下一个元素等于主元素，计数+1，如果不是，计数-1，当计数为0是，我们就把当前这个数计做主元素
2>如果计数>数组长度的一半，就表示找到了主元素，否则没找到

//找出主元素
int Majority(pSeqList list) {
    int c, count=0;
    c = list->data[0];
    for (int i=1; i<list->Length; i++) {
        if (list->data[i] == c) {
            count ++;
        }
        if (list->data[i]  != c && count>0) {
            count --;
        }
        else {
            c = list->data[i];
            count = 1;
        }
    }
    count = 0;
    for (int i=0; i<list->Length; i++) {
        if (list->data[i] == c) {
            count ++;
        }
    }
    if (count > list->Length/2) {
        return c;
    }
    return -1;
}

找出未出现的最小正整数

//找出未出现的最小正整数
int FindMissMin(pSeqList list) {
    pSeqList new = (SeqList *)malloc(sizeof(SeqList));
    pSeqList flagnew = (SeqList *)malloc(sizeof(SeqList));
    for (int i=0; i<list->Length; i++) {
        new->data[i] = i+1;
        new->Length ++;
        if (new->data[i] == list->data[i]) {
            flagnew->data[i] = 0;
            flagnew->Length ++;
        }
        if(new->data[i] < list->data[i]) {
            flagnew->data[i] = 1;
            flagnew->Length ++;
        }
    }
    for (int i=0; i<list->Length; i++) {
        if (flagnew->data[i] == 1) {
            return new->data[i];
        }
    }
    return new->data[new->Length-1]+1;
}

测试

void testSequlist() {
    SeqList list;
    SeqList list2;
    InitSeqList(&list);
    InitSeqList(&list2);
    SeqList list3;
    InitSeqList(&list3);
    SeqList list4;
    InitSeqList(&list4);
    InsertLast(&list, 34);
    PrintSeqList(list);
    InsertFront(&list, 20);
    PrintSeqList(list);
    PopLast(&list);
    PrintSeqList(list);
    PopFront(&list);
    PrintSeqList(list);
    Insert(&list, 23, 1);
    PrintSeqList(list);
    Pop(&list, 1);
    PrintSeqList(list);
    InsertLast(&list, 11);
    InsertLast(&list, 13);
    InsertLast(&list, 15);
    InsertLast(&list, 17);
    InsertLast(&list, 19);
    PrintSeqList(list);
    InsertLast(&list2, 2);
    InsertLast(&list2, 4);
    InsertLast(&list2, 6);
    InsertLast(&list2, 8);
    InsertLast(&list2, 20);
    PrintSeqList(list2);
//    MoveP(&list, 3);
//    PrintSeqList(list);
    printf("%d\n", M_Search(&list, &list2));
    InsertLast(&list3, 0);
    InsertLast(&list3, 5);
    InsertLast(&list3, 5);
    InsertLast(&list3, 3);
    InsertLast(&list3, 5);
    InsertLast(&list3, 7);
    InsertLast(&list3, 5);
    InsertLast(&list3, 7);
    PrintSeqList(list3);
    printf("%d\n", Majority(&list3));
    printf("FindMissMin...\n");
    InsertLast(&list4, 1);
    InsertLast(&list4, 2);
    InsertLast(&list4, 3);
    InsertLast(&list4, 4);
    InsertLast(&list4, 5);
    InsertLast(&list4, 6);
    InsertLast(&list4, 7);
    InsertLast(&list4, 9);
    printf("%d\n", FindMissMin(&list4));
}

最后编辑于：2020.04.03 11:00:02

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