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

news/2024/10/14 10:40:08

目录
  • 2.1 线性表的定义和基本操作
  • 2.2 顺序表
    • 2.2.1 顺序表的定义
    • 2.2.2 顺序表的插入、删除（实现是基于静态分配）
    • 2.2.3 顺序表的查找
  • 2.3 链表
    • 2.3.1 单链表的定义
    • 2.3.2 单链表的插入删除
    • 2.3.3 单链表的查找
    • 2.3.4 单链表的建立
    • 2.3.4 双链表
    • 2.3.5 循环链表

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;    //顺序表最大长度增加lenfree(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处放入eL.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处放入eL.length++; //插入元素后长度增加1return 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--; //线性表当前长度加1return 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处放入eL.length++; //插入元素后长度增加1return 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--; //线性表当前长度加1return 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中元素覆盖为ereturn 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永远指向NULLL->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的后继节点qif(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;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.ryyt.cn/news/26771.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！

相关文章

Java安全基础之Java反射机制和ClassLoader类加载机制

Java安全基础之Java反射机制和ClassLoader类加载机制

反射机制允许程序在运行时检查和操作类、对象、方法以及属性的信息。类加载机制负责将类的字节码加载到内存中，并且在运行时动态地链接和初始化类。目录Java 反射机制反射 java.lang.RuntimeClassLoader 类加载机制URLClassLoaderloadClass() 与 Class.forName() 的区别？ Jav…
阅读更多...
高中生一定就会了么？？？（i）

高中生一定就会了么？？？（i）

\(题源：2023星光杯数学思维能力测评（小学组）第一试\)\(表示离谱\)
阅读更多...
高中生一定就会了么？？？（ii）

高中生一定就会了么？？？（ii）

阅读更多...
1. SpringBoot 入门

1. SpringBoot 入门

1. SpringBoot 简介 SpringBoot是由Pivotal团队提供的全新框架，可以帮助我们开发基于Spring的、独立的、生产级的应用程序。​ 其中SpringBoot的官网是：Spring Boot Reference DocumentationSpringBoot的主要目标是：为所有Spring开发提供更快的入门体验开箱即用，提供了自动…
阅读更多...
鸿蒙安装apk软件失败(不支持该设备)

鸿蒙安装apk软件失败(不支持该设备)

1.关闭纯净模式增强模块 2.给文件管理器一个权限，一个安装外部来源应用的权限魔芋爽要犯了.jpg1.关闭纯净血压增高模块 2.安装外部来源(默认文件管理器是没有权限的) 3.没登华为账号，等七天过了再来试试后续(matepad11.5就是垃圾，快退！.jpg)
阅读更多...
mysql连接不上，服务中找不到mysql

mysql连接不上，服务中找不到mysql

分析 因为太久没使用mysql，服务自动删除了解决 注册/安装服务 win+x,a,以管理员打开powershell（或者使用cmd，随你） # 注意此处需要引号,因为有空格 # 1. cd到mysql的可执行文件，如果记不得或者像我一样懒，直接everything搜索mysqld.exe即可 cd C:\Program Files\MySQL\My…
阅读更多...
星趴解包教程

星趴解包教程

目录#1 提取资源文件#2 解密#3 读取资源#4 导出资源#4.1 导出单个 / 少量资源#4.2 按种类导出资源#5 资源去重（可选） 本篇文章偏小白向，有一定基础的可以选择性阅读 本文仅供学习交流使用，请勿用于商业用途。更新至 2024.5.2, 星趴版本号 v1.2.3_20240430_123a#1 提取资源文…
阅读更多...
站立会议和燃尽图10

站立会议和燃尽图10

站立会议和燃尽图10 一、小组情况 组长：李宏威 组员：董泽豪 队名：隐约雷名 二、Scrum例会 时间：2024年4月29日 出席人员：李宏威，董泽豪 要求1 工作照片要求2 时间跨度 2024年4月29日 7:00 至 2024年4月29日 7:20 共计 20 分钟 要求3 地点 石家庄铁道大学 要求4 立会内容包…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 尧图建网站 广利置业