首页 > 其他分享 >王道数据结构个人向笔记-第二章（线性表）

王道数据结构个人向笔记-第二章（线性表）

时间：2024-05-02 11:23:23浏览次数：23  
标签：NULL return 线性表 int next 王道 数据结构 data LNode

目录

2.1 线性表的定义和基本操作

线性表:是具有相同数据类型的\(n(n>=0)\)个元素的有限序列，其中n为表长，当\(n=0\)时线性表是一个空表。若用L命名线性表，则其一般表示为

\[L=(a_1,a_2,...,a_i,a_{i+1},...,a_n) \]

image

  • 相同的数据类型意味着每个元素所占的空间一样大
  • \(a_i\)是表头元素：\(a_n\)是表尾元素
  • 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继
    线性表的基本操作
    InitList(&L):初始化表。构造一个空的线性表L，分配内存空间。
    DestroyList(&L):销毁线性表，并释放线性表L所占用的内存空间
    ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e
    ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
    LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值得元素。
    GetElem(L,i):按位查找操作。获取表L中第i个位置得元素得值。
    其他常用操作：
    Lengt h(L):求表长。返回线性表L得长度，即L中数据元素的个数。
    PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。
    Empty(L):判空操作。若L为空表，则返回true，否则返回false.
    image

2.2 顺序表

2.2.1 顺序表的定义

顺序表：用顺序存储的方式实现线性表。所谓顺序存储，把逻辑上相邻的元素存储在物理上也相邻的存储单元中，元素之间的关系由存储单元的临界关系来体现。

顺序表的实现-静态分配

#define MaxSize 10  //定义最大长度
typedef struct {
    ElemType data[MaxSize]; //用静态的数组存放数据元素
    int length; //顺序表的当前长度
}SqList;

实现

#include <bits/stdc++.h>

using namespace std;
#define MaxSize 10
typedef struct {
    int data[MaxSize];  //用静态的数组存放数据元素
    int length; //顺序表的当前长度
}SqList;

void InitList(SqList &L){
    for(int i=0; i<MaxSize; i++){
        L.data[i]=0;    //将所有数据元素设置为默认初始值
    }
    L.length=0; //顺序表初始长度为0
}

int main() {
   SqList L;    //生命一个顺序表
    InitList(L);
   return 0;
}

image
顺序表的实现-动态分配

#define InitSize 10
typedef struct {
   ElemType *data;  //指示动态分配数组的指针
   int MaxSize; //顺序表的最大容量
   int length;  //顺序表的当前长度
}SeqList;   //顺序表的类型定义（动态分配方式）

c语言中提供了malloc和free函数动态申请和释放内存空间

#include <bits/stdc++.h>

using namespace std;
#define InitSize 10
typedef struct {
   int *data;  //指示动态分配数组的指针
   int MaxSize; //顺序表的最大容量
   int length;  //顺序表的当前长度
}SeqList;   //顺序表的类型定义（动态分配方式）

void InitList(SeqList &L){
    L.data=(int*)malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize=InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
    int *p=L.data;
    L.data=(int *) malloc((L.MaxSize+len)*sizeof(int));
    for(int i=0; i<L.length; ++i){
        L.data[i]=p[i]; //将数据复制到新区域
    }
    L.MaxSize=L.MaxSize+len;    //顺序表最大长度增加len
    free(p);
}

int main() {
    SeqList L;  //声明一个顺序表
    InitList(L);    //初始化顺序表
    cout<<L.MaxSize<<'\n';
    IncreaseSize(L,5);
    cout<<L.MaxSize<<'\n';
    return 0;
}

image

顺序表的特点

  • 随机访：即可以在\(O(1)\)时间内找到第i个元素
  • 存储密度高，每个节点只存储数据元素
  • 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
  • 插入、删除操作不方便，需要移动大量元素

image

2.2.2 顺序表的插入、删除（实现是基于静态分配）

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。

#include <bits/stdc++.h>

using namespace std;
#define MaxSize 10
typedef struct {
   int data[MaxSize];  //用静态的数组存放数据元素
   int length;  //顺序表的当前长度
}SqList;   //顺序表的类型定义（动态分配方式）

void InitList(SqList &L){
    for(int i=0; i<MaxSize; i++){
        L.data[i]=0;    //将所有数据元素设置为默认初始值
    }
    L.length=0; //顺序表初始长度为0
}

void ListInsert(SqList &L, int i, int e){
    for(int j=L.length;j>=i;j--)    L.data[j]=L.data[j-1];
    L.data[i-1]=e;  //在位序i处放入e
    L.length++; //插入元素后长度增加1
}

void Print(SqList L){
    for(int i=0; i<L.length; ++i) cout<<L.data[i]<<' ';
    cout<<'\n';

}

int main() {
    SqList L;   //生命顺序表
    InitList(L);
    ListInsert(L,1,1);
    ListInsert(L,2,2);
    Print(L);
    ListInsert(L,3,3);
    Print(L);
    return 0;
}

image

更健壮的代码
考虑了插入位置是否合法，空间容量是否合法

bool ListInsert(SqList &L, int i, int e){
    if(i<1||i>L.length+1||L.length>=MaxSize)   return false;
    for(int j=L.length;j>=i;j--)    L.data[j]=L.data[j-1];
    L.data[i-1]=e;  //在位序i处放入e
    L.length++; //插入元素后长度增加1
    return true;
}

插入操作的时间复杂度
关注最深层for循环语句执行的次数与问题规模n的关系
image
顺序表的删除

bool ListDelete(SqList &L, int i, int &e){
    if(i<1||i>L.length) return false;   //判断i的位置是否合法
    e=L.data[i-1];  //回带删除元素的值
    for(int j=i; j<L.length; j++)   L.data[j-1]=L.data[j];  //将第i个位置后的元素前移
    L.length--; //线性表当前长度加1
    return true;
}

egg

#include <bits/stdc++.h>

using namespace std;
#define MaxSize 10
typedef struct {
   int data[MaxSize];  //用静态的数组存放数据元素
   int length;  //顺序表的当前长度
}SqList;   //顺序表的类型定义（动态分配方式）

void InitList(SqList &L){
    for(int i=0; i<MaxSize; i++){
        L.data[i]=0;    //将所有数据元素设置为默认初始值
    }
    L.length=0; //顺序表初始长度为0
}

bool ListInsert(SqList &L, int i, int e){
    if(i<1||i>L.length+1||L.length>=MaxSize)   return false;
    for(int j=L.length;j>=i;j--)    L.data[j]=L.data[j-1];
    L.data[i-1]=e;  //在位序i处放入e
    L.length++; //插入元素后长度增加1
    return true;
}


bool ListDelete(SqList &L, int i, int &e){
    if(i<1||i>L.length) return false;   //判断i的位置是否合法
    e=L.data[i-1];  //回带删除元素的值
    for(int j=i; j<L.length; j++)   L.data[j-1]=L.data[j];  //将第i个位置后的元素前移
    L.length--; //线性表当前长度加1
    return true;
}

void Print(SqList L){
    for(int i=0; i<L.length; ++i) cout<<L.data[i]<<' ';
    cout<<'\n';

}

int main() {
    SqList L;   //生命顺序表
    InitList(L);
    ListInsert(L,1,1);
    ListInsert(L,2,2);
    ListInsert(L,3,3);
    Print(L);
    int e=0;
    ListDelete(L,3,e);
    cout<<"Delete element's value is "<<e<<'\n';
    Print(L);
    return 0;
}

image

删除操作的时间复杂度
image

image

2.2.3 顺序表的查找

查找有两种一种是按位茶盅，一种是按值查找
按位查找

int GetElem(SqList L, int i){
    return L.data[i-1];
}

image
按值查找

//按值查找,在顺序表L找查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqList L, int e){
    for(int i=0; i<L.length; ++i){
        if(L.data[i]==e)    return i+1; //数组下标为i的元素值等于e，返回其位序i+
    }
    return 0;   //查找失败返回0
}

image

image

2.3 链表

关于链表的实现可以看这篇博客（侧重于实现）链表的实现

2.3.1 单链表的定义

image

typedef struct LNode{   //定义单链表的节点类型
    ElemType data;  //每个节点存放一个数据元素
    struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;

image

不带头节点的单链表的初始化

bool InitList(LinkList &L){
    L=NULL; //空表，暂时还没有任何节点
    return true;
}

void test(){
    LinkList L; //声明一个指向单链表的指针
    InitList(L);
}

带头结点的单链表


typedef struct LNode{   //定义单链表的节点类型
    int data;  //每个节点存放一个数据元素
    struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;

bool InitList(LinkList &L){
    L=(LNode *) malloc(sizeof(LNode));  //分配一个头节点
    if(L==NULL) return false;   //内存不足，分配失败
    L->next=NULL;   //头节点之后暂时还有没节点
    return true;
}

bool Empty(LinkList L){
    if(L->next==NULL)   return true;
    else    return false;
}

void test(){
    LinkList L; //声明一个指向单链表的指针
    InitList(L);
}

image

2.3.2 单链表的插入删除

带头结点的插入

//在第i各位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e){
    if(i<1) return false;
    LNode *p;   //指针p指向当前扫描到的节点
    int j=0;
    p=L;    //L指向头节点，头节点是第0各节点（不存数据）
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL) return false;
    LNode *s=(LNode *) malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

不带头结点需要对第一个位置进行特殊处理

指定节点的后插操作

//后插操作，在p节点之后插入元素e
bool InsertNextNode(LNode *p, int e){
    if(p==NULL) return false;
    LNode *s=(LNode *) malloc(sizeof (LNode));
    if(s==NULL) return false;   //内存分配失败
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

指定节点的前插操作（头天换日O（1））

//前插操作：在p节点之前插入元素e
bool InsertPriorNode(LNode *p, int e){
    if(p==NULL) return false;
    LNode *s = (LNode *) malloc(sizeof(LNode));
    if(s==NULL) return false;   //内存分配失败
    s->next=p->next;
    p->next=s;  //新节点s连到p之后
    s->data=p->data;    //将p中元素复制到s中
    p->data=e;  //p中元素覆盖为e
    return true;
}

按位序删除

bool ListDelete(LinkList &L, int i, int e){
    if(i<1) return false;
    LNode *p;   //指针p指向当前扫描到的节点
    int j=0;    //当前o指向的是第几个节点
    p=L;    //L指向头节点，头节点是第0个节点
    while(p!=NULL&&j<i-1){//循环找到第i-1个节点
        p=p->next;
        j++;
    }
    if(p==NULL) return false;   //i值不合法
    if(p->next==NULL)  return false; //第i-1个节点之后已经无其他节点
    LNode *q=p->next;   //q指向被删除节点
    e=q->data;  //用e返回元素的值
    p->next=q->next;    //将*q节点从链中断开
    free(q);    //释放节点的存储空间
    return true;
}

删除指定节点

//删除指定节点p
bool DeleteNode(LNode *p){
    if(p==NULL) return false;
    LNode *q=p->next;
    p->data=p->next->data;
    p->next=q->next;
    free(q);
    return true;
}

上面代码是有bug的，当是最后一个结点的是偶p->next->data这个会出错，因为p->next=NULL

2.3.3 单链表的查找

按位序查找

//按位查找，返回第i个元素（带头结点）
LNode *GetElem(LinkList L, int i){
    if(i<0) return NULL;
    LNode *p;   //当指针p指向当前扫描到的结点
    int j=0;    //当前p指向的是第几个结点
    p=L;
    while(p!=NULL&&j<i){//循环找到第i个结点
        p=p->next;
        j++;
    }
    return p;
}

按值查找

//按值查找，找到数据域==e的结点
LNode * LocateElem(LinkList L, int e){
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e)  p=p->next;
    return p;   //找到后返回该结点指针，否则返回NULL；
}

2.3.4 单链表的建立

image
尾插法可以设置一个变量length记录当前链表的长度，然后调用之前的按位序插入函数这样的话时间复杂度是\(O(n^2)\)的，因为每次我们都需要从头开始遍历这是没有必要的，我们可以用一个指针去指向最后一个结点

LinkList List_Tailnsert(LinkList &L){
    int x;
    L=(LinkList) malloc(sizeof(LNode)); //建立头节点
    LNode *s,*r=L;  //r为表尾指针
    scanf("%d",&x); //输入结点的值
    while(x!=9999){//输入9999表示结束
        s=(LNode *) malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;   //尾结点指针置空
    return L;
}

头插法

//头插法
LinkList List_HeadInsert(LinkList &L){//逆向建立单链表
    LNode  *s;
    int x;
    L=(LinkList) malloc(sizeof (LNode));    //创建头节点
    L->next=NULL;   //初始化空链表
    scanf("%d",&x);
    while(x!=9999){//输入9999表示结束
        s=(LNode *) malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;  //将新节点插入到表中，L为头指针
        scanf("%d",&x);
    }
    return L;
}

头插法可以实现链表的逆置

2.3.4 双链表

双链表的定义

typedef struct DNode{
    int data;
    struct DNode *prior, *next; //前驱和后继
}DNode, *DLinklist;

双链表的初始化

bool InitDLinkList(DLinklist &L){
    L=(DNode *) malloc(sizeof(DNode));  //分配一个头节点
    if(L==NULL) return false;   //内存不足，分配失败
    L->prior=NULL;  //头节点的prior永远指向NULL
    L->next=NULL;   //头节点之后暂时还没有结点
    return true;
}

双链表的插入

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
    if(p==NULL||s==NULL)    return false;   //非法参数
    s->next=p->next;
    //如果p有后继结点
    if(p->next!=NULL)   p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}

双链表的删除

bool DeleteNextDNode(DNode *p){
    if(p==NULL) return false;
    DNode *q=p->next;   //找到p的后继节点q
    if(q==NULL) return false;   //p没有结点
    p->next=q->next;
    if(q->next!=NULL)   q->next->prior=p;
    free(q);
    return true;
}

image

2.3.5 循环链表

image
循环单链表
初始化循环单链表

//初始化一个循环单链表
bool InitList(LinkList &L){
    L=(LNode *) malloc(sizeof (LNode));
    if(L==NULL) return false;
    L->next=L;  //头节点next指向头结点
    return true;
}

判空

//判断循环单链表是否为空
bool Empty_(LinkList L){
    if(L->next==L)  return true;
    else    return false;
}

循环单链表可以从任意结点出发找到任何单链表中的结点
image
循环双链表
image
循环双链表的初始化


//初始化空的循环双链表
bool InitDLinkList_(DLinklist &L){
    L=(DNode*) malloc(sizeof (DNode));
    if(L==NULL) return false;
    L->prior=L; //头节点的prior指向头节点
    L->next=L;  //头节点的next指向头节点
    return true;
}

判空的和循环单链表一样

//判断结点p是否为循环双链表的表尾结点
bool isTaol(DLinklist L, DNode *p){
    if(p->next==L)  return true;
    else    return false;
}

双链表的插入

//在p结点之后插入s结点
bool InsertDNode_(DNode *p, DNode *s){
    s->next=p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}

image

2.3.6 静态链表

参考现实博客

2.3.7 顺序表和链表的对比

标签：NULL,return,线性表,int,next,王道,数据结构,data,LNode
From： https://www.cnblogs.com/cxy8/p/18167096

相关文章

  • Redis核心数据结构与高性能原理
    参考-图灵课堂-https://vip.tulingxueyuan.cnhttps://www.runoob.com/redis/redis-tutorial.html 常见得数据类型：Redis支持五种数据类型：string（字符串），hash（哈希），list（列表），set（集合）及zset(sortedset：有序集合)。stringstring是redis最基本的类型，你可以理解成与Memcached一......
  • 数据结构--线段树合并
    线段树合并前置知识权值线段树，动态开点线段树简单说明一下，权值线段树就是以值域开的一棵线段树，而动态开点就是因为值域过大导致线段树开不下，于是开一棵残疾的线段树。线段树合并模板例：给定两个数列\(a,b\)，求\(\suma_i+b_i\)当然我只是为了引出模板。代码(\(x\)表......
  • 好题——数学与数据结构
    前言本文章将会持续更新，主要是一些个人觉得比较妙的题，主观性比较强（给自己记录用的），有讲错请补充。带！号的题是基础例题，带*号的是推荐首先完成的题（有一定启发性的）。组合数P6620[省选联考2020A卷]组合数问题运用斯特林数好的例题，普通幂转下降幂。用到第二类斯特林数。\[......
  • 数据结构-二叉树的初始化
    数据结构-二叉树的相关初始化/*************************************************/***@filename: DcirLLinkInsert*@brief对双向循环链表插入的功能实现*@[email protected]*@date2024/04/29*@version1.0：在下坂本，有何贵干*@property：none......
  • python3的数据结构
    一.列表(列表可以修改,字符串和元组不能)list.append(x)-把一个元素添加到列表的结尾-相当于a[len(a):]=[x]list.extend(L)-通过添加指定列表的所有元素来扩充列表-相当于a[len(a):]=Llist.insert(i,x)-在指定位置插入一个元素-a.insert(0,x)会插入到整个列表之前-a.i......
  • .h5ad数据结构解释（anndata 数据格式）
    官方网站：https://anndata.readthedocs.io/en/latest/下面的内容官网都有概述h5ad文件提供了一种可扩展的方式来记录数据及其注释(annotation)，主要包含X,obs,var,uns等多个部分，分别存储不同的信息。结构如下图所示X是表达量矩阵，用来联系obs和var。具体来说X是一个稀疏......
  • 数据结构周测错题小结
    小题：1、若函数调用时的实参为变量时，以下关于函数形参和实参的叙述中正确的是（）A.函数的实参和其对应的形参共占同一存储单元B.形参只是形式上的存在，不占用具体存储单元C.同名的实参和形参占同一存储单元D.函数的形参和实参分别占用不同的存储单元参考答案：D2、假定一个顺序存......
  • 王道数据结构第一章个人向笔记
    目录1.1.0导读1.1.1绪论1.1.2数据结构的三要素逻辑结构数据的运算物理结构（存储结构）1.2.1算法的基本概念1.2.2时间复杂度1.2.3空间复杂度1.1.0导读数据结构在学什么？如何用程序代码把显示世界的问题信息画如何用计算机高效地处理这些信息从而创造价值1.1.1绪论数据......
  • 数据结构与算法学习(1)——BFS(广度优先搜索)
    BFS基础BFS会从根节点开始搜索，在每一个路口面临分叉的时候，先把每个岔路记录下来，然后再去一个一个的往前走一步。节点进行广度优先搜索的顺序题目PS:下列题目均来自leetcode中灵神题单1311.获取你好友已观看的视频......
  • 数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）
    版本:2024年4月26日V1.0发布于博客园/***@filename:DoubleLinkedList.c*@brief:实现双向循环链表的相关功能*@author:[email protected]*@date:2024/04/26*@version:1.0*@note:*CopyRight(c)2023-2024RISE_AND......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99