数据结构与算法之线性表的顺序表示和实现

形式一(动态分配)

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

#define MAXSIZE 20
typedef struct{

    int *pBase;
    int len;//线性表的最大长度
    int cnt;//表示线性表的当前长度

}SqList;

void InitList(SqList *L)//初始化操作，建立一个空的线性表L
{
    L->pBase = (int *)malloc(sizeof(int)*MAXSIZE);
    
    if(L->pBase==NULL){

        printf("内存分配失败");
        exit(-1);
    }

    L->cnt = 0;
    L->len = MAXSIZE;
}

bool ListEmpty(SqList L)//判断线性表L是否为空
{
    if(L.cnt == 0){

        return true;
    }else{

        return false;
    }
}

void ClearList(SqList *L)//将线性表L清空
{
    L->cnt = 0;
}

void DestoryList(SqList *L)//将线性表L销毁
{
    free(L->pBase);
    L->pBase = NULL;
    L->cnt = 0;
    L->len = 0;
}

void GetElem(SqList L,int i,int *e)//将线性表L中的第i个位置元素值返回给e
{
    if(i<1||i>L.cnt){

        printf("查找的位置不存在\n");
        exit(-1);
    }
    
    *e = *(L.pBase+i-1);
}

int LocateElem(SqList L,int e)//查找线性表L中元素值为e的元素的位置
{
    int i=0;

    while(i<L.cnt){

        if(L.pBase[i]==e)
        {
            return i+1;
        }

        i++;
    }
    return -1;//表示查询无果
}

void PriorElem(SqList L,int aim,int *e)//获取线性表中的元素aim的前一个元素
{
    int k=LocateElem(L,aim);
    if(k==-1 || k==1){
        
        printf("%d元素不存在或者aim本身就是第一个元素\n",aim);
        exit(-1);
    }
    
    *e =  L.pBase[k-2];
}

void NextElem(SqList L,int aim,int* e)//获取线性表中的元素aim的后一个元素
{
    int k=LocateElem(L,aim);
    if(k==-1 || k==L.cnt){
        
        printf("%d元素不存在或者aim本身就是最后一个元素\n",aim);
        exit(-1);
    }
    
    *e =  L.pBase[k];
}

void ListInsert(SqList *L,int i,int e)//在线性表L的第i个位置插入元素e
{
    int *newBase,*p,*q;

    if(i<1||i>L->cnt+1){

        printf("插入的位置不存在\n");
        exit(-1);
    }

    if(L->cnt>=L->len){//表示可插入的位置已满，需要重新扩展空间
    
        newBase = (int *)realloc(L->pBase,(L->len+MAXSIZE)*sizeof(int));
        if(newBase==NULL){

            printf("内存分配失败\n");
            exit(-1);
        }
        L->pBase = newBase;
        L->len += MAXSIZE;
    }
    
    q = L->pBase+i-1;//q表示当前要插入的位置的地址
    for(p=L->pBase+L->cnt;p>q;p--){
        
        *p = *(p-1);
    }
    *p = e;
    L->cnt++;
    
}

void ListDelete(SqList *L,int i,int *e)//删除线性表L第i个位置上的元素，并把元素保存在e中
{
    int *q;

    if(i<1||i>L->cnt){

        printf("删除的位置不存在\n");
    }
    
    q = L->pBase+i-1;//要删除元素位置的地址
    *e = *q;
    while(q<L->pBase+L->cnt-1){

        *q = *(q+1);
        q++;
    }
}

int ListLength(SqList L)//返回线性表L中当前元素的个数
{
    return L.cnt;
}

void ListTraverse(SqList L)//遍历线性表L
{
    int i = 0;
    
    while(i<ListLength(L)){
        
        printf("%d ",L.pBase[i]);
        i++;
    }
    printf("\n");
}

int main()
{
    SqList L;
    int i,e;

    InitList(&L);//初始化线性表
    for(i=1;i<=19;i++){//循环往线性表插入元素

         ListInsert(&L,i,i);
    }
    printf("执行插入操作之后结果如下：\n");
    ListTraverse(L);

    if(LocateElem(L,17)==-1){
        printf("未能在线性表L中找到待查询的元素\n");
    }else{
        printf("值为17的元素位置:%d\n",LocateElem(L,17));
    }

    GetElem(L,6,&e);
    printf("第6个位置上的元素为：%d\n",e);
    
    ListDelete(&L,4,&e);
    printf("执行删除操作之后结果如下：\n");
    ListTraverse(L);
    
    PriorElem(L,7,&e);//获取aim的前一个元素
    printf("aim的前一个元素是:%d\n",e);

    NextElem(L,7,&e);//获取aim的后一个元素
    printf("aim的后一个元素是:%d\n",e);
    return 0;   
}

形式二（静态分配）

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

#define MAXSIZE 20
typedef struct{

    int pBase[MAXSIZE];
    int cnt;//表示线性表的当前长度

}SqList;

void InitList(SqList *L)//初始化操作，建立一个空的线性表L
{
    L->cnt = 0;
}

bool ListEmpty(SqList L)//判断线性表L是否为空
{
    if(L.cnt == 0){

        return true;
    }else{

        return false;
    }
}

void ClearList(SqList *L)//将线性表L清空
{
    L->cnt = 0;
}

int LocateElem(SqList L,int e)//查找线性表L中元素值为e的元素的位置
{
    int i=0;

    while(i<L.cnt){

        if(L.pBase[i]==e)
        {
            return i+1;
        }

        i++;
    }
    return -1;//表示查询无果
}
void PriorElem(SqList L,int aim,int *e)//获取线性表中的元素aim的前一个元素
{
    int k=LocateElem(L,aim);
    if(k==-1 || k==1){
        
        printf("%d元素不存在或者aim本身就是第一个元素\n",aim);
        exit(-1);
    }
    
    *e =  L.pBase[k-2];
}

void NextElem(SqList L,int aim,int* e)//获取线性表中的元素aim的后一个元素
{
    int k=LocateElem(L,aim);
    if(k==-1 || k==L.cnt){
        
        printf("%d元素不存在或者aim本身就是最后一个元素\n",aim);
        exit(-1);
    }
    
    *e =  L.pBase[k];
}

void GetElem(SqList L,int i,int *e)//将线性表L中的第i个位置元素值返回给e
{
    if(i<1||i>L.cnt){

        printf("查找的位置不存在\n");
        exit(-1);
    }
    
    *e = *(L.pBase+i-1);
}

void ListInsert(SqList *L,int i,int e)//在线性表L的第i个位置插入元素e
{
    int k;
   
    if (i<1 || i>L->cnt+1 || L->cnt==MAXSIZE){

        printf("插入的位置无效或数组已满\n");
        exit(-1);
    }
  
    for(k=L->cnt;k>i-1;k--){
        
        L->pBase[k] = L->pBase[k-1];
    }
    
    L->pBase[k] = e;
    L->cnt++;
    
}

void ListDelete(SqList *L,int i,int *e)//删除线性表L第i个位置上的元素，并把元素保存在e中
{
    int k;  
   
    if (i<1 || i>L->cnt){

        printf("删除的位置无效\n");
        exit(-1);
    }

    *e = L->pBase[i-1];
    for(k=i-1;k<L->cnt-1;k++){
        
        L->pBase[k] = L->pBase[k+1];
    }

    L->cnt--;
}

int ListLength(SqList L)//返回线性表L中当前元素的个数
{
    return L.cnt;
}

void ListTraverse(SqList L)//遍历线性表L
{
    int i = 0;
    
    while(i<ListLength(L)){
        
        printf("%d ",L.pBase[i]);
        i++;
    }
    printf("\n");
}

int main()
{
    SqList L;
    int i,e;

    InitList(&L);//初始化线性表
    for(i=1;i<=19;i++){//循环往线性表插入元素

         ListInsert(&L,i,i);
    }
    printf("执行插入操作之后结果如下：\n");
    ListTraverse(L);

    if(LocateElem(L,17)==-1){
        printf("未能在线性表L中找到待查询的元素\n");
    }else{
        printf("值为17的元素位置:%d\n",LocateElem(L,17));
    }

    GetElem(L,6,&e);
    printf("第6个位置上的元素为：%d\n",e);
    
    ListDelete(&L,4,&e);
    printf("执行删除操作之后结果如下：\n");
    ListTraverse(L);
    
    PriorElem(L,7,&e);//获取aim的前一个元素
    printf("aim的前一个元素是:%d\n",e);

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

推荐阅读更多精彩内容