文档章节

线性表Linear List-线性表的链式表示和实现

秋风醉了
 秋风醉了
发布于 2014/05/06 20:09
字数 1284
阅读 86
收藏 2

线性表(Linear List)

线性表(Linear List)是由n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1]组成的有限序列

其中:

  • 数据元素的个数n定义为表的长度 = "list".length() ("list".length() = 0(表里没有一个元素)时称为空表)

  • 将非空的线性表(n>=0)记作:(a[0],a[1],a[2],…,a[n-1])

  • 数据元素a[i](0≤i≤n-1)只是个抽象符号,其具体含义在不同情况下可以不同 

 

线性链表

线性链表:线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这些存储单元可以是连续的,也可以是不连续的)。因此,为了表示每个数据元素ai来说,除了存储其本身的信息之外,还需要存储一个指示其直接后继的信息(即直接后继的存储位置)。

节点,包括两个域:数据域,指针域。链表有很多种不同的类型:单向链表,双向链表以及循环链表。

头指针:单链表的头指针指向头结点。

头结点:有时,我们在单链表的第一个节点之前附设一个节点,称之为头结点。

头结点的指针域存储指向第一个节点的指针若线性表为空,则头节点的指针域为空。

如图所示

 

C语言实现单链表

单链表的结构体定义

typedef struct Node
{
    ElemType data;  //数据域
    struct Node *next; //指针域
}Node,*LinkList;

单链表的C实现:

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define SWAP(x,y) {t=x,x=y,y=t;}

typedef int ElemType;
typedef int Status;

typedef struct LNode //线性表的单链表存储结构
{
    int data;  //数据域
    struct LNode *next; //指针域
}LNode,*LinkList;
//这里的LNode实际上就是struct LNode的别名,同时LinkList是指针类型的,指向LNode

//箭头运算符是二院操作符,其左边操作数必须是指针类型
Status Create_LinkList_Head(LinkList *L,int n)
{
    int i;
    LinkList p;
    *L=(LinkList)malloc(sizeof(LNode));
    (*L)->next=NULL; //先建立一个带有头结点的单链表
    for(i=0 ; i<n ; i++)
    {
        if(!(p=(LinkList)malloc(sizeof(LNode))))
        {
            printf("内存分配失败!");
            exit(OVERFLOW);
        }
        printf("%d\n",p->data);
		printf("%x\n",p->data);
        scanf("%d",&(p->data));
        printf("插入数据成功\n");
        ////插入到表头。可以画图演示链接的过程
        p->next=(*L)->next; //断开头结点和第一个节点间的连接。把当前第一个节点的地址赋给新节点的指针域。
        (*L)->next=p;//同时头结点的指针域指向新节点
    }
    printf("ok");
    return OK;
}

Status Create_LinkList_Tail(LinkList *L,int n)
{
    LinkList r,s;
    *L=(LinkList)malloc(sizeof(LNode)); //新建一个节点
    r=*L;

    int i;
    for(i=0 ; i<n ; i++)
    {
        if(!(s=(LinkList)malloc(sizeof(LNode))))
        {
            printf("内存分配失败");
            exit(OVERFLOW);
        }
        scanf("%d",&(s->data));
        r->next=s; //新的节点s被链接到上一个节点的指针域
        r=s; //把节点s插入到尾部
    }
    r->next=NULL; //当前链表结束
    return OK;
}

Status Insert_LinkList(LinkList L,int i,ElemType e)//插入节点
{
    int j=0;
    LinkList p=L,s;
    while(j<i-1 && p)
    {
        p=p->next;
        j++;
    }

    if(!p || j>i-1)
        return ERROR;

    if(!(s=(LinkList)malloc(sizeof(LNode))))
    {
        printf("内存分配失败");
        exit(OVERFLOW);
    }
    s->data=e;
    s->next=p->next;
    p->next=s;

    return OK;

}

Status Delete_LinkList(LinkList L,int i,ElemType *e)//删除节点
{
    int j=0;
    LinkList p=L->next,q;
    while(j<i-1 && p)
    {
        p=p->next;
        j++;
    }
    if(!p || j>i-1)
        return ERROR;

    q=p->next;
    *e=q->data;
    p->next=q->next;
    free(q);

    return OK;
}

Status GetElem_LinkList(LinkList L,int i,ElemType *e)//得到指定的节点元素
{
    int j;
    LinkList p;

    j=1,p=L->next;

    while(j<i && p)
    {
        p=p->next;
        j++;
    }
    if(!p || j>i)
        return ERROR;

    *e=p->data;

    return OK;
}
Status Print_LinkList(LinkList L)//打印链表
{
    LinkList p=L->next;

    while(p)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

int  LinkList_Length(LinkList L)//获取链表的长度
{
    int len=0;
    LinkList p=L->next;

    while(p)
    {
        len++;
        p=p->next;
    }
    printf("length ok");
    return len;
}

Status Destory_LinkList(LinkList head)//销毁链表
{
    LinkList p = head;

    while(head!=NULL)
    {
        head = head->next;
        free(p);
        p = head;
    }
    return OK;
}
Status Sort_LinkList(LinkList L)//排序
{
    LinkList La,Lb;
    ElemType t;

    La=L->next;
    Lb=La->next;

    while(Lb)
    {
        if(La->data>Lb->data)
        {
            SWAP(La->data,Lb->data);
        }
        Lb = Lb->next;
        if(!Lb)
        {
            La = La->next;
            Lb = La->next;
        }
    }
    return OK;
}


int main()
{
    int n,ch,pos;
    ElemType insert;
    LinkList L=NULL;

    printf("请输入你要输入元素的个数\n");
    scanf("%d",&n);

    printf("输入1,选择头插法(顺序),输入2,选择尾插法(逆序)\n");
    scanf("%d",&ch);
    if(ch!=1 && ch!=2)
    {
        printf("输入错误,请重新输入");
        scanf("%d",&ch);
    }
    if(ch==1)
    {
        printf("请输入%d个元素\n",n);
        Create_LinkList_Head(&L,n);
    }
    else if(ch==2)
    {
        printf("请输入%d个元素\n",n);
        Create_LinkList_Tail(&L,n);
    }

    printf("lyx");
    printf("链表的长度为%d\n",LinkList_Length(L));

    printf("打印链表==>\n");
    Print_LinkList(L);

    printf("请输入你要插入的数据和位置\n");
    scanf("%d%d",&insert,&pos);
    Insert_LinkList(L,pos,insert);

    int dl;
    printf("删除链表中的元素\n");
    Delete_LinkList(L,3,&dl);
    Print_LinkList(L);

    int e;
    GetElem_LinkList(L,3,&e);
    printf("第三个节点的数据域是%d\n",e);

    printf("链表排序\n");
    Sort_LinkList(L);
    Print_LinkList(L);

    printf("销毁链表\n");
    Destory_LinkList(L);
    return 0;
}

====END====

© 著作权归作者所有

秋风醉了
粉丝 251
博文 532
码字总数 405713
作品 0
朝阳
程序员
私信 提问
线性表(Linear List)

线性表(linear list) 1、特点 线性表是我们日常工作中最简单也是最常用的一种数据结构。 它有如下特点: 每个数据元素最多只能有一个直接前趋。 每个数据元素最多只能有一个直接后继。 只有...

星汉
2018/09/07
8
0
线性表Linear List-线性表的顺序表示和实现

线性表Linear List 线性表:线性表(Linear List)是由n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1]组成的有限序列 其中: 数据元素的个数n定义为表的长度 = "list".length() ("...

秋风醉了
2014/05/04
95
0
数据结构线性表、栈和队列(C描述)

数据结构线性表、栈和队列(C描述) 资料: 线性表的链式表示和实现 http://my.oschina.net/xinxingegeya/blog/261287 线性表的顺序表示和实现 http://my.oschina.net/xinxingegeya/blog/23...

秋风醉了
2014/09/14
58
0
Java容器简要教程

java中,经常会在运行中创建任意类型的任意数量的对象 保存多个对象最常用的方法是使用数组 比如一个类叫Apple他有多个对象apple0,apple1,......,apple98,apple99有100个。 那么我们可以创建...

骏珏
2017/04/29
0
0
C语言 数据结构与算法 单向链表

单向链表 线性表的一种(可以理解为线性表的链式链式表示和实现) 逻辑位置相邻 物理位置不相邻 与线性表相比劣势:不能随机存取 与线性表相比优势:插入和删除较快 链式存贮结构一般由一个个...

起什么name呢
2016/03/24
26
0

没有更多内容

加载失败,请刷新页面

加载更多

只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
昨天
59
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
昨天
28
0
全世界到底有多少软件开发人员?

埃文斯数据公司(Evans Data Corporation) 2019 最新的统计数据(原文)显示,2018 年全球共有 2300 万软件开发人员,预计到 2019 年底这个数字将达到 2640万,到 2023 年达到 2770万。 而来自...

红薯
昨天
65
0
Go 语言基础—— 通道(channel)

通过通信来共享内存(Java是通过共享内存来通信的) 定义 func service() string {time.Sleep(time.Millisecond * 50)return "Done"}func AsyncService() chan string {retCh := mak......

刘一草
昨天
58
0
Apache Flink 零基础入门(一):基础概念解析

Apache Flink 的定义、架构及原理 Apache Flink 是一个分布式大数据处理引擎,可对有限数据流和无限数据流进行有状态或无状态的计算,能够部署在各种集群环境,对各种规模大小的数据进行快速...

Vincent-Duan
昨天
60
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部