顺序表(数据结构)


本篇文章主要针对《数据结构》中的顺序表的增删查改以及一些常用算法进行详尽的代码描述。本代码使用c语言书写，并且通过测试。可以直接拷贝编译，在你的main函数中进行测试。

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 50  //顺序表的表长
#define InitSize 100 //顺序表的初始表长

typedef struct {
    int data[MaxSize];  //顺序表的元素
    int length;         //顺序表的长度
}SqList;              //顺序表的类型定义

typedef struct{
    int *data;          //指示动态分配的数组指针
    int dataSize,length; //数组的最大容量和当前储存元素的个数
}mSqList;

/*
 * [InitList 顺序表初始化函数]
 * @param  L [传入需要初始化的顺序表]
 * @return   [成功初始化返回 1]
 */
int InitList(mSqList *L,int size){
    for (int i = 0; i < size; i++) {
        L->data[i] = rand()%1000;
    }
    L->dataSize = InitSize;
    L->length = size;
    return 1;
}

/**
 * [Length 计算表长]
 * @param  L [传入需要计算长度的顺序表]
 * @return   [返回表长]
 */
int Length(mSqList L){
    return L.length;
}

/**
 * [LocateElem 查找元素e所在的位置]
 * @param  L [传入需要查找的顺序表]
 * @param  e [需要查找的元素e]
 * @return   [成功查找返回元素的位置，查找失败返回-1]
 */
int LocateElem(mSqList L,int e){
    for(int i = 0; i < L.length; i++)
    {
        if(L.data[i] == e)
        {
            return i+1;
        }
    }
    return -1;
}

/**
 * [GetElem 按位置查找元素]
 * @param  L        [传入需要查找的顺序表]
 * @param  position [传入需要查找的位置position]
 * @return          [查找成功返回查找元素，查找失败返回-1]
 */
int GetElem(mSqList L,int position){
    if (position <= 0 || position > L.length)
    {
        return -1;
    }
    return L.data[position - 1];
}

/**
 * [ListInsert 向线性表对应位置i插入元素e]
 * @param  L [需要插入的顺序表]
 * @param  i [元素插入的位置]
 * @param  e [插入的元素]
 * @return   [成功返回 1，插入失败返回-1]
 */
int ListInsert(mSqList *L,int i,int e){
    if (i < 1 | i > L->length + 1)
    {
        return -1;
    }
    if (L->length >= L->dataSize)
    {
        return -1;
    }
    for (int j = L->length; j >= i; j--)
    {
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length++;
    return 1;
}

/**
 * [ListDelete 删除顺序表中位置i的元素]
 * @param  L [待删除的顺序表]
 * @param  i [待删除元素的位置]
 * @return   [成功返回删除元素的值 e，失败返回 -1]
 */

int ListDelete(mSqList *L,int i)
{
    int e = 0;
    if (i < 1 || i > L->length)
    {
        return -1;
    }
    e = L->data[i-1];
    for (int j = i; j < L->length; j++)
    {
        L->data[j-1] = L->data[j];
    }
    L->length--;
    return e;
}

/**
 * [ListMinDelete 删除顺序表中最小的元素]
 * @param  L [待删除的顺序表]
 * @return   [成功返回删除的元素 e，失败返回 -1]
 */
int ListMinDelete(mSqList *L)
{
    int tmp = L->data[0];
    int position = 0;
    if(L->length < 1)
    {
        return -1;
    }
    for (int i = 0; i < L->length; i++)
    {
        if(tmp > L->data[i])
        {
            tmp = L->data[i];
            position = i;
        }
    }
    L->data[position] = L->data[L->length-1];
    L->length--;
    return tmp;
}

/**
 * [ListReverse 将顺序表原地逆置]
 * @param  L [需要逆置的顺序表]
 * @return   [成功返回 1，失败返回 -1]
 */
int ListReverse(mSqList *L)
{
    int tmp = 0;
    if(L->length <= 0)
    {
        return -1;
    }
    for(int i = 0; i < L->length / 2; i++)
    {
        tmp = L->data[i];
        L->data[i] = L->data[L->length - i - 1];
        L->data[L->length - i - 1] = tmp;
    }
    return 1;
}

/**
 * [ListElemDelete 删除顺序表中所有相同的元素]
 * @param  L [待删除的顺序表]
 * @param  x [待删除的元素 x]
 * @return   [成功删除反回删除后顺序表的长度 length，失败则返回 -1]
 */

int ListElemDelete(mSqList *L,int x)
{
    int k = 0;
    int delNUm = 0;
    if(L->length <= 0)
    {
        return -1;
    }
    for (int i = 0; i < L->length; i++)
    {
        if(L->data[i] != x)
        {
            L->data[k] = L->data[i];
            k++;
        }
    }
    delNUm = L->length - k;
    L->length = k;
    return delNUm;
}

/**
 * [ListRangeDelete 删除顺序表中在start 和 stop 范围内的 元素]
 * @param  L     [待删除的顺序表]
 * @param  start [删除值范围的最小值]
 * @param  stop  [删除值范围的最大值]
 * @return       [成功返回以删除的元素个数，失败返回-1]
 */
int ListRangeDelete(mSqList *L,int start,int stop)
{
    int k = 0;
    int delNUm = 0;
    if (start > stop)
    {
        return -1;
    }
    if (L->length <= 0)
    {
        return -1;
    }
    for (int i = 0; i < L->length; i++)
    {
        if(L->data[i] < start || L->data[i] > stop)
        {
            L->data[k] = L->data[i];
            k++;
        }
    }
    delNUm = L->length - k;
    L->length = k;
    return delNUm;
}

/**
 * [ListDumpDelete 删除有序的顺序表中含重复元素的项]
 * @param  L [待删除的有序顺序表]
 * @return   [成功返回删除返回删除元素个数，失败返回 -1]
 */
int ListDumpDelete(mSqList *L)
{
    int k = 0;
    int len = 0;
    if(L->length <=0 )
    {
        return -1;
    }
    for (int i = 1; i < L->length; i++)
    {
        if (L->data[k] != L->data[i])
        {
            L->data[++k] = L->data[j];
        }
    }
    len = L->length - k - 1;
    L->length = k + 1;
    return len;
}

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

推荐阅读更多精彩内容

  • Android - 收藏集
    Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 171,498评论 25赞 707
  • Java初级面试题
    1. Java基础部分 基础部分的顺序：基本语法，类相关的语法，内部类的语法，继承相关的语法，异常的语法，线程的语...
    子非鱼_t_阅读 31,581评论 18赞 399
  • 2017-09-29
    姓名:张丽娟 公司:个体 【日精进打卡第33天】 【知～学习】 《六项精进》1遍，共60遍 《大学》1遍，共49遍...
    兑了水的悲伤阅读 157评论 0赞 1
  • 喲嗬
    往前走一步，走一步，走一步，再走一步 你就会看见那个蜷缩在墙角的女孩 她那么无助的在等你 等你 等你…
    你从南方来阅读 210评论 0赞 0