2020-06-11数据结构 -- 第二章*线性表

线性结构的基本特点是除第一个元素无直接前驱，最后一个元素无直接后继之外，其他每个元素都有一个前驱和后继。

2.1线性表(Linear List)的定义和特点：

定义：由n（n>=0）个数据特性相同的元素构成的有限序列称为线性表，n=0时称为空表。

        实例：a_{1} ,a_{2} ,a_{3} ......a_{n}

特点：

线性表特点

a_{1} 称为线性表的首节点，a_{n} 称为线性表的尾节点

a_{1} ,a_{2} ...a_{i-1} 都是a_{i} 的前驱，其中a_{i-1} 是a_{i} 的直接前驱；

a_{i+1}，a_{i+2}...a_{n} 都是a_{i} 的后继，其中a_{i+1}是a_{i} 的直接后继；

2.2线性表的逻辑结构

线性表结点可以是单值元素
线性表节点可以是记录行元素，关键字

2.3线性表的抽象数据类型定义

ADT List{

        数据对象：D = { a_{i} | a_{i} \in ElemSet,i = 1,2,....,n,n\geq 0 }

        数据关系：R = {<a_{i-1},a_{i} >|a_{i-1},a_{i}\in D,i=2,...,n }

        基本操作：

                操作名1：

                        初始条件

                        操作结果1

                                .

                                .

                                .

}ADT List

2.4线性表的顺序存储和实现

顺序存储：把线性表的节点按逻辑顺序依次存放在一组地址连续的存储单元里，用这种方法存储的线性表简称顺序表。

特点：

        线性表的逻辑顺序与物理顺序一致

        数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。

线性表的顺序存储
第i-1个数据元素存储地址为（i-1）*/存储单元+LOC（a1）

顺序表的基本操作：

        C语言定义结构体

宏定义和结构体定义

        1）顺序线性表初始化

表示给elem_array动态分配指针，如果没有分配到指针返回ERROR否认返回OK

        2）顺序线性表的插入

算法分析
C语言算法实现

js代码实现顺序线性表的插入：

js代码实现线性表的插入算法操作

        3）顺序线性表的删除

算法分析和C代码实现一部分
C代码实现剩余部分

js代码实现顺序线性表的删除


js代码实现顺序线性表的删除

2.5线性表的链式存储

链式存储：用一组任意的存储单元存储线性表中的数据元素，用这种方法存储的线性表简称线性链表。

        存储链表中节点的一组任意存储单元可以是连续的，也可以是不连续的，甚至零散分布至内存的任意位置上

        链表中节点的逻辑顺序和物理顺序不一定相同。

为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继节点的地址，C中称为指针，节点值（数据域）和地址（指针）两者组成链表中的结点结构。

链表结点结构

        链表通过每个结点的地址将线性表的n个结点按其逻辑顺序连接在一起。

        每一个结点只包含一个地址域的链表称为单链表。

        为操作方便，总是在链表的第一个结点之前附设一个头节点head指向第一个结点，头节点的数据域可以不存储任何信息（或链表长度信息）。

下图可以看出链表中节点的逻辑顺序和物理顺序不一定相同。

单链表示例


单链表的逻辑状态

结点的描述与实现

C语言中，用带指针的结构体来描述

typedef struct Lnode{

    ElemType data；//数据域，保存结点的值

    struct Lnode *next;//指针域

}LNode;  //结点的类型

结点的实现：

结点是通过动态分配指针和释放来实现，即需要时分配，不需要时释放。是现实是分别使用C语言提供的标准函数：malloc(),realloc(),sizeof(),free()。

动态分配：

p = (LNode*)malloc(sizeof(LNode));

函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放如指针变量p中。

动态释放：free（p）

系统回收由指针变量p所指向的内存区，p必须是最近一次调用malloc函数时的返回值。

最常见的基本操作及其示意图

结点的赋值
常见指针操作（1）
常见指针操作(2)

2.6单线性链表的基本操作

单项现象链表的基本操作

<script>

    //设计一个基于对象的链表

    //创建链表Node类

    function Node(element){

        this.element = element;

        this.next = null;

    }

    //创建链表/增删改查

    function LinkedList(){

        this.head = new Node('head');//创建头结点

        this.find = find; //查找结点

        this.insert = insert;//插入结点

        this.findPrev = findPrev;//找到某结点的前一结点

        this.remove = remove;//删除结点

        this.display = display;//显示链表元素


        //查找对应item的结点并返回

        function find(item){

            var currentNode = this.head;//从头节点开始搜索

            //循环遍历，直至找到item结束

            while(currentNode.element!=item){

                currentNode = currentNode.next;

            }

            //返回item的结点

            return currentNode;

        }

        //在item后插入新元素

        function insert(newElement,item){

            var newNode = new Node(newElement);//定义新元素结点

            var current = this.find(item);//从链表中找到item结点

            newNode.next = current.currentNode;//将item元素的结点后继赋值给新元素结点的后继

            current.next = newNode;//item元素的后继插入新元素

        }

        //显示链表

        function display(){

            var currentNode = this.head;

            while(!(currentNode.next==null)){

                console.log(currentNode.next.element);

                currentNode = currentNode.next;

            }

        }

        //删除链表的item结点元素

        //1.找到item结点的前一个结点

        function findPrev(item){

            var currentNode = this.head;//定义待删除结点的前一个结点

            /*

            算法分析：

            循环遍历currentNode的下一个结点，如果找到对应等于item的currentNode.next.element,

            while循环结束返回当前的currentNode，即待删除元素的前一个结点

            */

            while(!(currentNode.next==null) && currentNode.next.element!=item){

               currentNode = currentNode.next;

            }

            return currentNode;

        }

        //2.删除item阶段元素

        function remove(item){

            var prevNode = this.findPrev(item);//找到待删除结点的前一结点

            if(!(prevNode.next==null)){

                prevNode.next = prevNode.next.next;

            }


        }

    }

    //测试程序

    var cities = new LinkedList();

    cities.insert('北京','head');

    cities.insert('上海','北京');

    cities.insert('广州','上海');

    cities.insert('天津','广州');

    cities.display();//北京 上海 广州 天津

    cities.remove('北京');

    cities.display();//上海 广州 天津

    console.log(cities.find('上海').next)//Node {element: "广州", next: Node}

    console.log(cities.find('天津').next);//undefined

</script>

双向链表的基本操作

<script>

    //设计一个基于对象的双向链表

    //创建链表Node类

    function Node(element){

        //data数据

        this.element = element;

        //后继地址

        this.next = null;

        //前驱地址

        this.previous = null;

    }

    //创建链表/增删改查

    function LinkedList(){

        this.head = new Node('head');//创建头结点

        this.find = find; //查找当前结点

        this.insert = insert;//插入结点

        this.findPrevious = findPrevious;//找到某结点的前一结点

        this.remove = remove;//删除结点

        this.display = display;//显示链表元素

        this.findLast = findLast;//查找链表最后一个元素

        this.dispReverse = dispReverse;//反向显示


        //查找对应item的结点并返回

        function find(item){

            var currentNode = this.head;//从头节点开始搜索

            //循环遍历，直至找到item结束

            while(currentNode.element!=item){

                currentNode = currentNode.next;

            }

            //返回item的结点

            return currentNode;

        }

        //在item后插入新元素

        function insert(newElement,item){

            var newNode = new Node(newElement);//定义新元素结点

            var current = this.find(item);//从链表中找到item结点

            newNode.next = current.currentNode;//将item元素的结点后继赋值给新元素结点的后继

            newNode.previous = current;//将item元素赋值给新元素结点的前驱

            current.next = newNode;//item元素的后继插入新元素

        }

        //显示链表

        function display(){

            var currentNode = this.head;

            while(!(currentNode.next==null)){

                console.log(currentNode.next.element);

                currentNode = currentNode.next;

            }

        }

        //删除链表的item结点元素

        //1.找到item结点的前一个结点

        function findPrevious(item){

            var currentNode = this.head;//定义待删除结点的前一个结点

            /*

            算法分析：

            循环遍历currentNode的下一个结点，如果找到对应等于item的currentNode.next.element,

            while循环结束返回当前的currentNode，即待删除元素的前一个结点

            */

            while(!(currentNode.next==null) && currentNode.next.element!=item){

               currentNode = currentNode.next;

            }

            return currentNode;

        }

        //2.删除item阶段元素

        function remove(item){


            var currentNode = this.find(item);//找到当前待删除结点

            if(!(prevNode.next==null)){

                currentNode.previous.next = currentNode.next;//前一个元素结点的的后继指向当前元素的下一个元素结点

                currentNode.next.previous = currentNode.previous//后一个元素结点的前驱指向当前元素的前一个元素结点

                currentNode.next = null;//当前结点后继为空

                currentNode.previous = null;//当前结点前驱为空

            }


        }

        //双向链表查找最后一个结点

        function findLast(){

            var currentNode = this.head;//从头节点开始搜索

            //循环遍历,直到地址为空

            while(!(currentNode.next==null)){

                currentNode = currentNode.next;

            }

            //最后的结点

            return currentNode;

        }

        //反序显示双向链表中的元素

        function dispReverse(){

            var currentNode = this.findLast();

            while(!(currentNode.previous==null)){

                console.log(currentNode.element);

                currentNode = currentNode.previous;

            }

        }

    }

    //测试程序

    var cities = new LinkedList();

    cities.insert('北京','head');

    cities.insert('上海','北京');

    cities.insert('广州','上海');

    cities.insert('天津','广州');

    cities.display();//北京 上海 广州 天津

    cities.dispReverse();//天津 广州 上海 北京

    console.log(cities.find('上海').next)//Node {element: "广州", next: Node}

    console.log(cities.find('天津').next);//undefined

</script>

2.7循环链表

循环链表是一种头尾相接的链表，其特点是最后一个结点的指针指向链表的头节点，整个链表的指针域连接成一个环。

从循环链表的任意一个结点出发，都可以找到链表中的其他结点。

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