从0开始——线性表

一、ADT：抽象数据类型(abstract data type)

之前学习过ADT的概念：其实就是数据+操作的集合，例如未来我们要学习到的[表、树、图]，以及他们的相关的[操作]一起称之为抽象数据类型，未来学习以此展开！

二、线性表

1.定义
0个或者多个数据元素的有限序列。

2.线性表抽象数据类型 ADT
线性表分顺序存储结构和链式存储结构，分别称为顺序表，链表

ADT 线性表(SqList)：顺序表
Data
  线性表的数据对象集合为{a1,a2,...an},没个元素的类型均为DataType。
Operation:
InitList(L)    初始化线性表，建立一个空的线性表
ListEmpty(*L)  判断线性表是否为空，空返回true
ClearList(*L)  清空线性表
GetElem(L,I,*e) 获取线性表L中的第i个元素给e
LocateElem(L,e)在线性表L中查找元素e，若存在返回e的下标，否则返回0
ListLength(L) 返回线性表的长度
ListInsert(*L,i,e)在线性表L中的第i个位置插入新元素e
ListDelete(*L,i,*e)删除线性表L中的第i个位置的元素，并用e返回其值

3.顺序表的实现

/*
ADT：顺序表  
*/

#include <stdio.h>;
#include <windows.h>;

#define MAXSIZE 20//顺序表的最大长度
typedef int ElemType;//这里ElemType要根据实际需求去定义
#define ERROR 0
#define OK 1

typedef struct 
{
    ElemType data[MAXSIZE];//用数组存储线性表中的元素
    int len;//顺序表长度 
} SqList;

//初始化顺序表 
void InitList(SqList *L)
{
    printf("在init函数中 L=%x &L =%x *L =%x\n",L,&L,*L);
    if(L == NULL)
        return;
    (L)->len = 0;   
    printf("初始化线性表成功\n");   
}
//判断线性表是否为空，空返回true
boolean ListEmpty(SqList *L)
{
    if(L->len == 0)
    {
        printf("线性表为空\n");
        return 1;
    }
    else
    {
        printf("线性表 不为 空\n");
        return 0;       
    }   
}
//清空线性表
ClearList(SqList *L)
{
    printf("清空线性表\n");
    L->len = 0;         
} 
//获取线性表L中的第i个元素给e 
int GetElem(SqList *L,int i,ElemType *e)
{
    if(L->len==0 || i<0 || i> L->len)
        return ERROR;
    *e = L->data[i-1];
    printf("线性表L中的第%d个元素为%d\n",i,*e); 
    return OK;  
}
//在线性表L中查找元素e，若存在返回e的下标，否则返回0
LocateElem(SqList *L,ElemType e)
{
    int i;
    for(i=0; i < L->len; i++)
    {
        if(e == L->data[i])
        {
            printf("线性表L中的找到元素%d,下标为%d\n",e,i);
            return i;//返回下标 
        }
            
    }
    printf("线性表L中的找不到元素%d\n",e);
    return ERROR;//返回0 
}
//返回线性表的长度 
int ListLength(SqList *L)
{
    printf("线性表L的长度为%d\n",L->len);
    return L->len;
} 
//在线性表L中的第i个位置插入新元素e
int ListInsert(SqList *L,int i,ElemType e)
{
    int k;
    if(L->len== MAXSIZE)
    {
        printf("数组已满，插入失败\n");
        return ERROR;
    }
    if(i < 1 || i > L->len+1)
    {
        printf("插入位置有误\n");
        return ERROR;
    }
    for(k=L->len-1;k>=i-1;k--)
        L->data[k+1] = L->data[k];//元素往后移动
    L->data[i-1] = e; //插入元素 
    L->len++;//长度加1 
    return OK;
}
//删除线性表L中的第i个位置的元素，并用e返回其值
int ListDelete(SqList *L,int i,ElemType *e)
{
    int j; 
    if(i<1 || i>L->len)
    {
        printf("删除位置有误\n");
        return ERROR; 
    } 
    *e=L->data[i-1];//记录会删掉的元素 
    printf("删除掉的元素为%d\n",*e);
    for(j=i-1;j<L->len-1;j++)
    {
        L->data[j]=L->data[j+1];
    }
    L->len--;
    
    return OK;
}
//打印顺序表
void show(SqList *L)
{
    int i;
    for(i=0 ;i < L->len;i++)
        printf("%d ",L->data[i]);
    printf("\n");
} 

int main()
{   
    SqList *L  = (SqList*)malloc(sizeof(SqList));;
    printf("分配之前L=%x &L =%x *L =%x \n",L,&L,*L);
    int i,temp;
    InitList(L);
    printf("分配之后 L=%x &L =%x *L =%x \n\n",L,&L,*L);
    for(i=1;i<=15;i++)
        ListInsert(L,i,i);  
    show(L);
    ListLength(L);
    GetElem(L,8,&temp);
    LocateElem(L,10);
    LocateElem(L,88);
    ListLength(L);
    ListEmpty(L);
    ListDelete(L,6,&temp);
    show(L);
    system("pause");
    return OK;
}

运行结果

顺序表

4.链表的实现

/*
ADT 线性表(SqList)：链表
Data
  线性表的数据对象集合为{a1,a2,...an},没个元素的类型均为DataType。
Operation:
InitList(L)    初始化线性表，建立一个空的线性表
ListEmpty(*L)  判断线性表是否为空，空返回true
ClearList(*L)  清空线性表
GetElem(L,I,*e) 获取线性表L中的第i个元素给e
LocateElem(L,e)在线性表L中查找元素e，若存在返回e的下标，否则返回0
ListLength(L) 返回线性表的长度
ListInsert(*L,i,e)在线性表L中的第i个位置插入新元素e
ListDelete(*L,i,*e)删除线性表L中的第i个位置的元素，并用e返回其值
*/

#include <stdio.h> 
#include <windows.h>

#define OK 1
#define ERROR 0
typedef int ElemType;//这里ElemType要根据实际需求去定义

typedef struct Node
{
    ElemType data;//保存数据
    struct Node * next; 
}Node,*LinkList;//注意这里LinkList 是一个一级指针
//初始化线性表，建立一个空的线性表
LinkList InitList()
{
    //创建头结点 
    LinkList head = (LinkList)malloc(sizeof(Node));
    if(head ==NULL)
    {
        printf("初始化失败\n"); 
        return NULL;
    }
    printf("初始化成功\n");
    head->data = 0;//头结点的data保存链表的长度
    head->next=NULL; 
    return head;
}
//判断线性表是否为空，空返回true 
boolean ListEmpty(LinkList L)
{
    if(L->next == NULL)
        printf("链表为空\n");
    else
        printf("链表不为空\n");
    return L->next ==NULL;  
}
//获取线性表L中的第i个元素给e 
int GetElem(LinkList L,int i,ElemType *e)
{
    LinkList p =L;//指向头结点
    int j =1;
    while(p->next != NULL && j<=i)
    {
        p=p->next;
        j++;
    }   
    if(p ==NULL || j>i+1 || j<=0)
    {
        printf("获取出错\n");
        return ERROR;   
    }
    printf("第%d个元素的值为%d\n",i,p->data);
    return OK;
        
}
//在线性表L中查找元素e，若存在返回e的下标，否则返回0
int LocateElem(LinkList L,ElemType e)
{
    LinkList p = L;//指向头结点
    int j=1;
    while(p->next != NULL)
    {
        if(p->next->data == e)
        {
            printf("元素%d在第%d个位置\n",e,j);
            return j;
        }
        p=p->next;
        j++;
    }
    printf("链表中不包含元素%d\n",e);
    return ERROR;   
}
//返回线性表的长度
int ListLength(LinkList L) 
{
    printf("链表长度为%d\n",L->data);
    return L->data; 
}
// 尾插法：在线性表L中的第i个位置插入新元素e
int ListTailInsert(LinkList L,int i,ElemType e)
{
    LinkList p=L,s;//p指向头结点 
    int j = 1;
    while(p->next !=NULL && j<i)
    {
        p= p->next;
        j++;
    }
    if(p == NULL || j>i)
    {
        printf("插入位置有误\n");
        return ERROR;
    }
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    L->data++;//链表长度+1
    return OK;
        
}
//头插法
int ListHeadInsert(LinkList L,ElemType e)
{
    LinkList p = L;//指向头结点
    LinkList s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    p->data++;//链表长度+1 
    return OK ; 
} 
//删除线性表L中的第i个位置的元素，并用e返回其值
int ListDelete(LinkList L,int i,ElemType *e)
{
    int j =1;
    LinkList p,q;   
    p = L;//指向头结点
    while(p->next!=NULL && j<i)
    {
        p=p->next;
        j++;
    } 
    if(p->next == NULL || j>i)
    {
        printf("删除位置有误！\n");
        return ERROR;
    }
    q=p->next;
    p->next = q->next;
    *e = q->data;
    L->data--;//链表长度-1
    free(q);
    printf("删除的节点为%d\n",*e);
    return OK; 
}
//清空顺序表 
void ClearList(LinkList L)
{
    LinkList p,q;
    p = L->next;//指向第一个节点
    while(p!=NULL)
    {
        q=p->next;
        free(p);
        p=q;
    }   
    L->next = NULL; 
}

//打印顺序表 
void showList(LinkList L)
{
    LinkList p=L;//指向头结点 
    
    while(p->next != NULL)
    {
        p=p->next;
        printf("%d ",p->data);  
    }
    printf("\n");
    ListLength(L);//输出链表长度
}

int main()
{
    LinkList head = InitList();
    LinkList head2 = InitList();
    int i,t;
    printf("尾插法创建链表\n"); 
    for(i=1;i<16;i++)
        ListTailInsert(head,i,i);
    showList(head);
    printf("头插法创建链表\n"); 
    for(i=1;i<16;i++)
        ListHeadInsert(head2,i);        
    showList(head2);
    GetElem(head,7,&t); 
    LocateElem(head,13);
    LocateElem(head,20); 
    ListDelete(head,1,&t);
    showList(head);
    system("pause");
    return OK;
}

运行结果

链表

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

推荐阅读更多精彩内容

  • 2018之线性表的基本概念
    转自：http://blog.csdn.net/oreo_go/article/details/52116214 ...
    YYT1992阅读 957评论 0赞 4
  • 数据结构-线性表
    基础概念 数据结构的分类 在数据结构中，按照不同的角度，数据结构分为逻辑结构和物理结构（存储结构）。 逻辑结构：指...
    IAM四十二阅读 1,093评论 2赞 5
  • 数据结构三(线性表)
    1.线性表的定义 线性表:零个或多个数据元素的有限序列序列:也就是说元素之间是有顺序的,若元素存在多个,则第一个元...
    e40c669177be阅读 2,027评论 6赞 15
  • 几番
    和他去看篮球比赛，中场啦啦队上场跳舞，拿出手机想拍照，却被前排站起来的一个女生挡住了镜头，她皱眉。他转头看到她不开...
    M不荒阅读 376评论 0赞 0
  • 女孩的来信（二）
    女孩的来信（二） 信寄出去后一周、两周，他没有收到女孩的回信。他既有几分失落，又觉得这不就是自己想要的吗，没有回信...
    粪草阅读 297评论 0赞 6