顺序表的两次实现

顺序表：内存中的一块连续区域，紧密排列了若干个相同类型的数据。

故，必须事先知道元素有多少个，不然就无法开出合适的内存区域。

对于线性表的"."and"->"

在c语言中，->是指针操作符，.是结构操作符，如果L是一个结构实例的指针，用->,如果是一个结构的实例，用.

L为线性表时，调用*L表示线性表的第一个元素，而调用&L表示线性表的首地址

类型名称：线性表（List）

数据对象集：线性表是 n (≥0)个元素构成的有序序列( a1, a2, ...,an ) 线性表基本操作主要有：

1、List MakeEmpty()：初始化一个空线性表L；

2、ElementType FindKth( int K, List L )：根据位序K，返回相应元素 ；

3、int Find( ElementType X, List L )：在线性表L中查找X的第一次出现位置；

4、void Insert( ElementType X, int i, List L)：在位序i前插入一个新元素X；

5、void Delete( int  i, List L )：删除指定位序i的元素；

6、int Length( List L )：返回线性表L的长度n。


```

#include<malloc.h>

#include<stdio.h>

#include<stdlib.h>

typedef struct LNode *List;

typedef int ElementType;

typedef 100 MAXSIZE;

struct LNode{

    ElementType Data[MAXSIZE];

    int Last;

};

struct LNode L; //L.Data[i]

List PtrL; //PtrL->Data[i]

/*

**函数名: List MakeEmpty();

**作  用: 初始化一个空线性表L;

**形  参: 无;

**返回值: PtrL;

*/

List MakeEmpty(void) //初始化空间

{

    List PtrL;

    PtrL=(List)malloc(sizeof(struct LNode))；//void *表示未确定类型的指针。可强转为任何其他类型的的指针。

    PtrL->Last=-1;

    return PtrL;

}

/*

**函数名: int Find(ElementType K,List PtrL);

**作  用: 在线性表L中查找X的第一次出现位置

**形  参: int K, List PtrL;

**返回值: 位置i;

*/

int Find(ElementType K,List PtrL) //查找

{

    int i=0

    while(i<=PtrL->Last && PtrL->Data[i]!=K);

    i++;

    if(i>PtrL->Last) return -1

    else return i;

}

/*

**函数名:ElementType FindKth( int K, List L );

**作  用: 根据位序K，返回相应元素；

**形  参: int K,List PtrL;

**返回值: PtrL->Data[K]

*/

ElementType FindKth( int K, List PtrL)

{

    while(K<=PtrL->Last && K>=0);

        return PtrL->Data[K];

}

/*

**函数名: void Insert(ElementType K,int i,List PtrL);

**作  用: 根据位置i来插入参数K;

**形  参: ElementType K,int i,List Ptrl;

**返回值: PtrL;

*/

void Insert(ElementType K,int i,List Ptrl)   //插入

{

  if(PtrL->Last==MAXSIZE-1){

        printf("线性表满");

        return;

    }

    if(i<1||i>Ptrl->Last+2){

        printf("插入位置不合法");

        return；

    }

    for(j=PtrL->Last;j>i-1;j--){

      PtrL->Data[j+1]=PtrL->Data[j]

    }

    PtrL->Data[i+1]=K;

    PtrL->Last++;

}

/*

**函数名: void Delete( int  i, List PtrL )

**作  用: 删除指定位序i的元素；

**形  参: int  i, List PtrL

**返回值:

*/

void Delete( int  i, List PtrL)

{

    int j;

    if(i>1 || i<=PtrL->Last+1){

        for(j=i;j<=PtrL->Last;j++){

            PtrL->Data[j-1]=PtrL->Data[j];

        }

        PtrL->Last--;

    }else{

        return;

    }


}

/*

**函数名: int Length( List L );

**作  用: 返回线性表L的长度n;

**形  参: List PtrL

**返回值:

*/

int Length(List PtrL){

    //return sizeof(PtrL)/ElementType;

    return PtrL->Last+1;

}

```

<pre>

ss

</pre>

第二种是我刚写的

不多说，直接上code

```

#include<stdio.h>

#include<stdlib.h>

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

#define listincreament 10 //存储空间分配增量

typedef struct{

int *elem; //存储空间基址 (末尾)

int length;//当前长度

int listsize;// 当前分配的存储容量

} SqList;

//构造一个空的线性表（初始化）

int InitList_Sq(SqList *L)

{

//动态分配空间

L->elem=(int *)malloc(80*sizeof(int));

//存储分配失败

if(!L->elem)

exit(OVERFLOW);

//存储分配成功

//初始化长度为零

L->length=0;

//存储的初始容量为初始分配空间

L->listsize=80;

return OK;

}

//n为要插入的位置

int Input_Sq(SqList *L,int n)

{

int i ,*newbase;

if(n<0)

return ERROR;

if(n>L->listsize)

{

newbase=(int *)malloc(listincreament*sizeof(int));

if(!newbase){

exit(OVERFLOW);

}

L->elem=newbase;

L->length+=listincreament;

}

printf("请输入元素：\n");

for(i=0;i<n;i++)

{

scanf("%d",&L->elem[i]);

L->length++;

}

return OK;

}

//i为位置，并非下标，e为要插入的新元素

int ListInsert_Sq(SqList *L,int i,int e){

//i需要满足1<=i<=ListLength_Sq(L)+1

int *newbase;

int *p;

int *q;//插入的位置

int j;

//判断输入

if(i<1||i>L->length+1)

return ERROR;

//判断线性表是否已满

if(L->length>=L->listsize)//满，（鲁棒性）（扩展）是否动态增加空间？

{

/*newbase=(int *)realloc((L->listsize+listincreament)*sizeof(int));

if(!newbase)

exit(OVERFLOW);//分配失败

*/

for(j=0;j<L->length;j++)

{

newbase[j]=L->elem[j];

}

L->elem=newbase;//新基址

L->length+=listincreament;//增加存储容量

}

q=&(L->elem[i-1]);

for(p=&(L->elem[L->length+1]);p>=q;p--)//元素后移

*(p+1)=*p;

*q=e; //插入

L->length+=1;//表长加1

return L->length;//返回表长

}

int Output_Sq(SqList *L,int i)

{

int j;

printf("更新后的线性表为：\n");

for(j=0;j<i;j++)

printf("%d\t",L->elem[j]);

return OK;

}

//在顺序线性表删除第i个元素，用e返回其值

int Delete_Sq(SqList *L,int i,int e)

{

int *q;

//先检查i的合法性

if(i<1||i>L->length)

return ERROR;

e=L->elem[i-1];//被删除的元素赋给e,之后用作返回

int *p=&L->elem[i-1]; //指针p为被删除元素的位置

for(q=p+1;q<=p+(L->length);q++)

*(q-1)=*q;

L->length-=1;

return OK;

}

int main(void)

{

SqList MyL;

char a,yn;

a='Y';

int k,data,position,*e;

InitList_Sq(&MyL);

printf("请输入元素个数：");

scanf("%d",&k);

Input_Sq(&MyL,k);

Output_Sq(&MyL,k);

while(a=='Y')

{

printf("\n请输入要插入的元素：");

scanf("%d",&data);

printf("\n请输入要插入的位置：");

scanf("%d",&position);

ListInsert_Sq(&MyL,position,data);

//printf(&MyL.length);

Output_Sq(&MyL,k+1);

printf("\n请输入要删除的元素的位置：");

scanf("%d",&position);

Delete_Sq(&MyL,position,e);

Output_Sq(&MyL,k);

printf("\n请问是否继续（Y or N）？：");

getchar();

scanf("%c",&a);

}

system("pause");

return OK;

}

```

效果如下


​

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