为了账号安全，请及时绑定邮箱和手机立即绑定
首页 免费课 数据结构探险之线性表篇 笔记

数据结构探险之线性表篇

james_yuan 学生
查看讲师更多课程 james_yuan讲师的其他课程
难度中级
时长 3小时 9分
学习人数
综合评分9.57
121人评价 查看评价
9.7 内容实用
9.4 简洁易懂
9.6 逻辑清晰
最热 最新
  • 慕粉9558438

    bool List::InsertHead(Node *pNode)

    {

        Node* temp = m_pList->next;

        Node* newNode = new Node;

        if(newNode == NULL)

        {

            return fasle;

        }

        newNode->data = pNode->data;

        m_pList->next = newNode;

        newNode = temp;

        return true;

    }


    bool List::InsertTail(Node *pNode)

    {

        Node* currentNode = m_pList;

        while(currentNode->next != NULL)

        {

            currentNode = currentNode->next;

        }

        Node* newNode = new Node;

        if(newNode == NULL)

        {

            return fasle;

        }

        newNode->data = pNode->data;

        newNode->next = NULL;

        currnetNode->next = newNode;

         return true;

    }

    查看全部
    0 采集 收起 来源：链表编码实战（三）

    2021-07-31

  • 慕粉9558438 06:53

    bool List::InsertHead(Node *pNode)

    {

        Node* temp = m_pList->next;

        Node* newNode = new Node;

        if(newNode == NULL)

        {

            return fasle;

        }

        newNode->data = pNode->data;

        m_pList->next = newNode;

        newNode = temp;

        return true;

    }


    bool List::InsertTail(Node *pNode)

    {

        Node* currentNode = m_pList;

        while(currentNode->next != NULL)

        {

            currentNode = currentNode->next;

        }

        Node* newNode = new Node;

        if(newNode == NULL)

        {

            return fasle;

        }

        newNode->data = pNode->data;

        newNode->next = NULL;

        currnetNode->next = newNode;

         return true;

    }

    查看全部
    0 采集 收起 来源：链表编码实战（三）

    2021-07-31

  • 慕粉9558438 06:40

    void List::ClearList()

    {

        Node *currentNode = m_pList->next;

        while(currentNode != NULL)

        {

            Node *temp = currentNode->next;

            delete currentNode;

            currentNode = temp;

        }

        m_pList->next = NULL;

    }

    List::~List()

    {

        ClearList();

        delete m_pList;

        m_pList = NULL; 

    }

    查看全部
    0 采集 收起 来源：链表编码实战（二）

    2021-07-31

  • 慕粉9558438 05:54

    List::List()

    {

        m_pList = new Node;

        m_pList->data = 0;

        m_pList->next = NULL;

        m_pList->iLength = 0;

    }

    bool List::ListEmpty()

    {

        if(m_iLength == 0)

        {

            return true;

        }

        else

        {

            return false;

        }

    }

    int List::ListLength()

    {

        return m_iLength;

    }

    查看全部
    0 采集 收起 来源：链表编码实战（一）

    2021-07-29

  • 张ACA

    1234567

    查看全部
    0 采集 收起 来源：课程概述

    2021-03-14

  • fengyunzhu 04:01

    数据结构之线性表

    查看全部
    0 采集 收起 来源：课程概述

    2020-10-15

  • UFO2015 00:52

    析构函数(destructor) 与构造函数相反，当对象结束其生命周期，如对象所在的函数已调用完毕时，系统自动执行析构函数。 析构函数往往用来做“清理善后” 的工作（例如在建立对象时用new开辟了一片内存空间，delete会自动调用析构函数后释放内存）。

    查看全部
    0 采集 收起 来源：顺序表编码实战（一）

    2020-09-17

  • younger_321 06:48

    do more

    查看全部
    0 采集 收起 来源：课程概述

    2020-03-18

  • 我入戲太深

    建立链表的时候，头结点我们把数据域设置为固定的0，并且这个数据域没有任何意义，这个头结点存在的意义只是为了指向这一条链表。   头结点之后的第一个节点， 我们认为他是第0个节点。

    建立一个毫无意义的头结点的好处在于：

    1、可以很好的固定住链表的入口

    2、再清空整个链表的时候（清空不是释放），可以留有一个入口记录下链表的内存位置。  如果没有这个节点，把链表清空了 就相当于释放了

    查看全部
    0 采集 收起 来源：链表编码实战（五）

    2020-03-14

  • 我入戲太深 05:41

    什么是线性表：n个 数据元素的有限序列


    1、顺序表：使用数组，访问速度快，搜索能力强（数组本身就有下标）

    2、链表：静态链表、单链表、循环链表、双向链表

    栈与队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除，二者的区别是：栈只允许在表的一端进行插入和删除操作，是一种“后进先出”的线性表；而队列是允许在一端进行插入操作，在别一端进行删除和操作，是一种”先进先出“的线性表


    线性表的应用场景：通讯录、一元多项式

    查看全部
    1 采集 收起 来源：课程概述

    2020-03-13

  • 孙三三 
    List.h:

//修改主要：
//1.将Elem改为Node
//2.加了两个操作：一个向头插入节点，一个向尾插入节点


#ifndef INC_0131_LIST_H
#define INC_0131_LIST_H

#include "Node.h"

class List
{
public:
    List();//先放一个头节点,不需要size作为参数
    ~List();
    void ClearList();//清空链表较为麻烦
    bool ListEmpty();
    int ListLength();
    bool GetElem(int i, Node *pNode);//获取指定元素
    int LocateElem(Node *pNode);//寻找第一个满足e的元素的位序
    bool PriorElem(Node *pCurrentNode,Node *preNode);//获取指定元素的前驱
    bool NextElem(Node *pCurrentNode,Node *pNextNode);//获取指定元素的后继
    bool ListInsert(int i,Node *pNode);
    bool ListDelete(int i,Node *pNode);
    void ListTraverse();//遍历链表元素
    bool ListInsertHead(Node *pNode);//插入头节点的下一个节点
    bool ListInserTail(Node *pNode);//插入到最后一个节点


private:
    Node *m_pList;
    //int m_iSize;//链表不需要
    int m_iLength;
};

#endif //INC_0131_LIST_H


    List.cpp:

//n 2020-02-06.
//

#include "List.h"
#include <iostream>
#include "Node.h"
using namespace std;

//构造函数
List::List() {
    m_pList = new Node;//头节点
    m_pList->data = 0;//头节点的数据域没有意义
    m_pList->next = NULL;
    m_iLength = 0;//头节点不计入
}



void List::ClearList() {
    //顺藤摸瓜式清除，先找头节点,直到找到指针域为空，用while循环
     Node *currentNode = m_pList->next;
     while(currentNode != NULL){
         Node *tmp = currentNode->next;
         delete currentNode;//释放掉当前currentNode的内存
         currentNode = tmp;
     }
     //不要忘记将头节点的next置为0
     m_pList->next = NULL;

}

//析构函数：将整个内存释放掉,
//与ClearList有异曲同工之处：~List需要将头节点和后续所有节点都释放掉，而ClearList不需要释放头节点
List::~List(){//可以利用已经写好的clearlist
    ClearList();
    delete m_pList;
    m_pList =NULL;

}

bool List::ListEmpty() {
    if(m_iLength == 0){
        return true;
    } else {
        return false;
    }
}

int List::ListLength(){
    return m_iLength;
}

bool List::ListInsertHead(Node *pNode){
    Node *tmp = m_pList->next;
    Node *newNode = new Node;//一定要从堆中去申请内存，因为如果从栈中申请内存，函数执行完成之后这个内存就被回收了
    //注意考虑内存申请失败的情况
    if(newNode == NULL){
        return false;
    }

    newNode->data = pNode->data;
    m_pList->next = newNode;
    newNode->next = tmp;
    m_iLength++;
    return true;
}

bool List::ListInserTail(Node *pNode){
    Node *curentNode = m_pList;
    while(curentNode->next != NULL){
        curentNode = curentNode->next;
    }
    Node *newNode = new Node;
    if(newNode == NULL){
        return false;
    }
    newNode->data = pNode->data;
    newNode->next = NULL;
    curentNode->next = newNode;
    m_iLength++;
    return true;
}

bool List::ListInsert(int i,Node *pNode){
    if(i < 0 || i > m_iLength){
        return false;
    }


    Node *currentNode = m_pList;
    for(int k = 0;k < i;k++){
        currentNode = currentNode->next;
    }
    //自己写：找到插入的位置
    Node *newNode = new Node;
    if(newNode == NULL){
        return false;
    }
//    newNode = currentNode->next;
//    currentNode->next = pNode;
//    pNode->next = newNode;
//错误，为什么？
    newNode->data = pNode->data;
    newNode->next = currentNode->next;
    currentNode->next = newNode;
    m_iLength++;
    return true;
}

bool List::ListDelete(int i,Node *pNode){
    if(i < 0||i >= m_iLength){
        return false;
    }
    Node *currentNode = m_pList;
    Node *currentNodeBefore = NULL;
    for(int k = 0;k <= i ;k++){
        currentNodeBefore = currentNode;
        currentNode = currentNode->next;
    }
    currentNodeBefore->next = currentNode->next;
    pNode->data = currentNode->data;
    delete currentNode;
    currentNode = NULL;
    m_iLength--;

}

bool List::GetElem(int i, Node *pNode){
    if(i < 0 || i >= m_iLength){
        return false;
    }
    Node *currentNode = m_pList;
    Node *currentNodeBefore = NULL;
    for(int k = 0;k <= i ;k++){
        currentNodeBefore = currentNode;
        currentNode = currentNode->next;
    }

    pNode->data = currentNode->data;
    return true;
}

int List::LocateElem(Node *pNode){
    Node *currentNode = m_pList;
    int i = 0;
    while(currentNode->next != NULL){
        currentNode = currentNode->next;//对链表进行遍历，对比数据域
        //i++;不应该写在这里，只有不相同时才++
        if(currentNode->data == pNode->data) {//返回什么？位置？而且只返回第一个符合的值（可能有多个）
            return i;
        }
        i++;//不写在if语句之前，因为m_pList的数据域无效。
    }
    //如果一个节点都没有找到,易忽略
    return -1;

}

bool List::PriorElem(Node *pCurrentNode,Node *preNode){
     Node *currentNode = m_pList;
     Node *tempNode = NULL;
     while(currentNode->next != NULL){
         tempNode = currentNode;
         currentNode = currentNode->next;
         if(currentNode->data == pCurrentNode->data){
             if(tempNode == m_pList){//如果当前节点的前驱是头节点
                 return false;
             }
             preNode->data = tempNode->data;
             return true;
         }
     }
}

bool List::NextElem(Node *pCurrentNode,Node *pNextNode){
    Node *currentNode = m_pList;
    while(currentNode->next != NULL){
        currentNode = currentNode->next;
        if(currentNode->data == pCurrentNode->data){
            if(currentNode->next == NULL){
                return false;
            }
            pNextNode->data = currentNode->next->data;
            return true;
        }
    }
}

void List::ListTraverse(){
    Node *currentNode = m_pList;
    while (currentNode->next != NULL){
        currentNode = currentNode->next;
        currentNode->printNode();
    }

}
    Node.h:

//
// Created by w on 2020-02-07.
//

#ifndef INC_0131_NODE_H
#define INC_0131_NODE_H

class Node{
public:
    int data;//数据域,直接写在public下边就是为了方便付值
    Node *next;//指针域
    void printNode();
};

#endif //INC_0131_NODE_H
    Node.cpp:
//
// Created by x on 2020-02-07.
//
#include <iostream>
#include "Node.h"
using namespace std;

void Node::printNode(){
    cout << data <<endl;
}
    main.cpp:

#include <iostream>
#include <stdlib.h>
#include "List.h"

using namespace std;

//int a=3,b=5 ;
//printf( "max=%d\n" , max(a,b) ); //这里的a,b就是实参
//int max( int a , int b ) ;//这里的a,b就是形参
//在main函数中
//        调用函数swap(&a,&b);
//定义函数时：
//void swap(int *a, int *b);
//这个是配套使用的。


int main(){
    Node node1;//括号加了会出错？why？
    node1.data = 3;
    Node node2;//括号加了会出错？why？
    node2.data = 4;
    Node node3;//括号加了会出错？why？
    node3.data = 5;
    Node node4;//括号加了会出错？why？
    node4.data = 6;
    List *pList = new List();

    Node node5;
    node5.data =7;
    Node tmp;
//    pList->ListInsertHead(&node1);
//    pList->ListInsertHead(&node2);
//    pList->ListInsertHead(&node3);
//    pList->ListInsertHead(&node4);
//    pList->ListTraverse();

    pList->ListInserTail(&node1);
    pList->ListInserTail(&node2);
    pList->ListInserTail(&node3);
    pList->ListInserTail(&node4);
    pList->ListInsert(1,&node5);

//    pList->ListDelete(1,&tmp);

    pList->PriorElem(&node5,&tmp);

    pList->ListTraverse();

    cout << "tmp = " << tmp.data <<endl;

    delete pList;
    pList = NULL;

    return 0;
}


    查看全部
    0 采集 收起 来源：链表编码实战（七）

    2020-02-10

  • 孙三三

    为什么有了顺序表还需要链表，因为两者互为补充

    顺序表的优缺点：

    优点：遍历和寻址时非常方便（因为基于数组）

    缺点：插入删除元素

    链表：

    http://img1.sycdn.imooc.com//5e3d32430001138b13400720.jpg

    http://img1.sycdn.imooc.com//5e3d324f0001138b13400720.jpg

    http://img1.sycdn.imooc.com//5e3d325b0001138b13400720.jpg

    有些计算机语言没有指针：

    http://img1.sycdn.imooc.com//5e3d326b0001cd4c09560716.jpg

    查看全部
    1 采集 收起 来源：链表算法说明

    2020-02-07

  • 孙三三

    未完成，待细学

    查看全部
    0 采集 收起 来源：顺序表编码实战（八）

    2020-02-07

  • 孙三三 
    List.h:


//


#ifndef INC_0131_LIST_H
#define INC_0131_LIST_H

class List
{
public:
    List(int size);
    ~List();
    void ClearList();//清空线性表不等于释放内存
    bool ListEmpty();
    int ListLength();
    bool GetElem(int i, int *e);//获取指定元素
    int LocateElem(int *e);//寻找第一个满足e的元素的位序
    bool PriorElem(int *currentElem,int *preElem);//获取指定元素的前驱
    bool NextElem(int *currentElem,int *nextElem);//获取指定元素的后继
    bool ListInsert(int i,int *e);
    bool ListDelete(int i,int *e);
    void ListTraverse();//遍历链表元素


private:
    int *m_pList;
    int m_iSize;
    int m_iLength;
};

#endif //INC_0131_LIST_H
    List.cpp:

//n 2020-02-06.
//

#include "List.h"
#include <iostream>
using namespace std;

//构造函数
List::List(int size) {
    m_iSize = size;
    //c++中分配内存,确定此线性表的容量：
    m_pList = new int[size];
    m_iLength = 0;
}

//析构函数：作用主要是将在构造函数中申请的内存释放掉
List::~List() {
    delete []m_pList;
    m_pList = NULL;//iSize置0无所谓，因为内存被释放后该对象也不存在了
}

void List::ClearList(){
    m_iLength = 0;
}

bool List::ListEmpty(){
    if(m_iLength == 0){
        return true;
    } else{
        return false;
    }
    //也可：
    //reture m_iLength == 0 ? true :false;
}

int List::ListLength(){
    return  m_iLength;
}

bool List::GetElem(int i,int *e){
    if(i < 0 || i >= m_iSize){
        return false;
    }

    *e = m_pList[i];
    return true;
}

int List::LocateElem(int *e){
    for(int i = 0;i < m_iLength;i++)
    {
        if(m_pList[i] == *e)
        {
            return i;
        }
    }
    return -1;
}
bool List::PriorElem(int *currentElem,int *preElem){
    int tmp = LocateElem(currentElem);
    //不是先判断是否是第一个元素，先判断是否找得到这个数
    if(tmp == -1){
        return false;
    } else{
        if(tmp == 0){
            return false;
        } else{
            *preElem = m_pList[tmp - 1];//注意是*preElem
            return true;
        }
    }
}

bool List::NextElem(int *currentElem,int *nextElem){
    //判断是否存在这样一个元素
    int tmp = LocateElem(currentElem);
    if(tmp == -1){
        return false;
    } else{
        if(tmp == m_iLength-1){
            return false;
        } else{
            *nextElem = m_pList[tmp+1];
            return true;
        }
    }
}

//自己写的，有错误
//bool List::PriorElem(int *currentElem,int *preElem){
//    //先判断是否是第一个元素
//    int tmp = LocateElem(currentElem);//注意用之前写好的函数
//    if(tmp == 1){
//        return false;
//    } else {
//        preElem = m_pList[tmp - 1];
//        return true;
//    }
//}
//
//bool List::NextElem(int *currentElem,int *nextElem){
//    //先判断是否为最后一个元素
//    int tmp = LocateElem(currentElem);
//    if(tmp == m_iLength-1){
//        return false;
//    } else{
//        nextElem = m_pList[tmp+1];
//        return true;
//    }
//}

void List::ListTraverse(){
    for(int i = 0; i < m_iLength;i++){
        cout << m_pList[i] <<endl;
    }
}

bool List::ListInsert(int i,int *e){
    //先判断是否超过size了
    if(m_iSize == m_iLength || i < 0 || i > m_iLength){//已经满了或i不符合标准
        return false;
    } else{
        for(int k = m_iLength - 1; k >= i; k--){
            m_pList[k+1] = m_pList[k];
        }
        m_pList[i] = *e;
        m_iLength++;//容易忘
        return true;//记得返回正确
    }
}

bool List::ListDelete(int i,int *e){
    //先判断i是否合法
    if(i < 0 || i >= m_iLength){
        return false;
    }
    *e = m_pList[i];

    for(int k = i+1;k < m_iLength;k++){
        m_pList[k-1] = m_pList[k];
    }

    m_iLength--;
    return true;
}
    main.cpp:

#include <iostream>
#include <stdlib.h>
#include "List.h"

using namespace std;
int main(){
    int e1 = 1;
    int e2 = 2;
    int e3 = 3;
    int e4 = 4;
    int e5 = 5;
    int e6 = 6;
    int tmp = 1;
    List *list1 = new List(10);
    cout << "length:" << list1->ListLength() <<endl;

    list1->ListInsert(0,&e1);
    cout << "length:" << list1->ListLength() <<endl;
    list1->ListInsert(1,&e2);
    list1->ListInsert(2,&e3);
    list1->ListInsert(3,&e4);
    list1->ListInsert(4,&e5);
    list1->ListInsert(5,&e6);

    list1->ListDelete(0,&tmp);
    cout << "#" << tmp <<endl;

    if(!list1->ListEmpty()){
        cout << "not empty" <<endl;
    }
    list1->ClearList();
    list1->ListTraverse();

    list1->ListInsert(0,&e1);
    list1->ListInsert(1,&e2);
    list1->ListInsert(2,&e3);
    list1->ListInsert(3,&e4);
    list1->ListInsert(4,&e5);
    list1->ListInsert(5,&e6);

    list1->GetElem(4,&tmp);
    cout << "tmp:" << tmp <<endl;

    cout << list1->LocateElem(&tmp) << endl;//注意是传地址

    list1->PriorElem(&e4,&tmp);
    cout<<"前驱:" << tmp <<endl;
    list1->NextElem(&e4,&tmp);
    cout<<"后继:" << tmp <<endl;


    delete list1;
    list1 = NULL;
    return 0;
}


    查看全部
    0 采集 收起 来源：顺序表编码实战（八）

    2020-02-07

  • 孙三三

    顺序表编码：

    http://img1.sycdn.imooc.com//5e3bd8d30001d7d711520702.jpg

    查看全部
    0 采集 收起 来源：顺序表编码说明

    2020-02-06

  • 孙三三

    什么是线性表：n个 数据元素的有限序列

    http://img1.sycdn.imooc.com//5e3bd6b1000102b609480592.jpg

    线性表分为 

        1.顺序表（数组）  2.链表

    链表：

    1.静态链表

    2.单链表

    3.循环链表

    4.双向链表


    线性表的应用场景：通讯录、一元多项式


    查看全部
    0 采集 收起 来源：课程概述

    2020-02-06

  • qq_慕粉4389469 08:32

    头结点没有数据域？

    查看全部
    0 采集 收起 来源：链表编码实战（五）

    2019-11-13

  • qq_慕粉4389469 03:01

    取出第N个节点的数据，只需要找到该节点，将data部分赋值出去则可

    查看全部
    0 采集 收起 来源：链表编码实战（五）

    2019-11-13

  • qq_慕粉4389469 11:23

    删除第N个节点

    思路：需保留第N个节点的上一个节点

    将当前的节点的next赋值给上一个节点的next则可，再释放掉当前节点

    查看全部
    0 采集 收起 来源：链表编码实战（四）

    2019-11-13

  • qq_慕粉4389469 05:16

    链表插入到第N个节点

    原理都是找到要使用的当前节点，新结点被当前节点指，前节点的next赋值给新结点的next

    查看全部
    0 采集 收起 来源：链表编码实战（四）

    2019-11-13

  • qq_慕粉4389469 06:03

    链表尾部插入新结点

    思路：先找到最后一个节点，在申请一个新结点，再让最后一个节点的next指向新结点，并且传参的节点只取了其中的数据，指针是自己new出来的

    查看全部
    0 采集 收起 来源：链表编码实战（三）

    2019-11-13

  • qq_慕粉4389469 03:37

    链表在头部插入新结点

    思路：其实是放到头节点后的第一个位置

    并且传参的节点只取了其中的数据，指针是自己new出来的

    查看全部
    0 采集 收起 来源：链表编码实战（三）

    2019-11-13

  • qq_慕粉4389469 05:13

    循环清空链表的数据  将当前的下一个指针赋值给临时指针 删掉当前指针 再将临时指针赋值给当前指针

    查看全部
    0 采集 收起 来源：链表编码实战（二）

    2019-11-13

  • qq_慕粉4389469

    链表：指针域 数据域 头结点 节点

    查看全部
    0 采集 收起 来源：链表算法说明

    2019-11-12

  • qq_慕粉4389469

    顺序表缺点：插入删除元素时，顺序表需前移或者后移

    查看全部
    0 采集 收起 来源：链表算法说明

    2019-11-12

  • qq_慕粉4389469

    顺序表链表互为补充

    查看全部
    0 采集 收起 来源：链表算法说明

    2019-11-12

首页上一页1234567下一页尾页

举报

0/150
提交
取消
开始学习
课程须知
"本课程是数据结构初级课程 1、熟练掌握C++语言基础语法"
老师告诉你能学到什么？
1、顺序表的工作原理 2、顺序表的实现方法及编码技巧 3、链表的工作原理 4、链表的实现方法及编码技巧 5、通讯录的实现原理及编码技巧

微信扫码，参与3人拼团

意见反馈 帮助中心 APP下载
官方微信
友情提示：

您好，此课程属于迁移课程，您已购买该课程，无需重复购买，感谢您对慕课网的支持！

查看已购买的课程