☰

抚州市网站建设_网站建设公司_网站建设_seo优化

首页 / 建站日记 / 抚州市网站建设_网站建设公司_网站建设_seo优化
抚州市网站建设_网站建设公司_网站建设_seo优化
2025/12/28 15:11:23 网站建设 项目流程

2.1 线性表基础

  • 线性表是具有相同数据类型的 n 个数据元素的有限序列，n 为表长，n 为 0 时，线性表为“空表”
    • 线性表每个数据元素所占空间相同（因为表中元素的数据类型都相同）
    • 线性表中元素的个数有限
    • 线性表是有次序的
  • 线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指采用不同存储方式实现的线性表（既包含了线性表的逻辑结构消息，也包含了存储结构信息）
  • 用 \(L\) 命名线性表一般表示为：\(L=(a_1,a_2,\dots,a_i,a_{i+1},\dots,a_n)\)
    • \(a_i\) 在线性表中的位序为 \(i\) ，代表线性表中第 \(i\) 个元素；位序从 1 开始
      • a[i] 对应位序 i+1，即第 i+1 个元素
      • 为序为 i 的元素，则对应 a[i-1]
    • \(a_1\) 是表头元素；\(a_n\) 是表尾元素
    • 除第一个元素外，每个元素有且仅有一个直接前趋
    • 除最后一个元素外，每个元素有且仅有一个直接后继

2.2 顺序表

  • 顺序表：用顺序存储的方式实现线性表

    • 顺序存储：见“数据的存储结构”

  • 设顺序表的每个数据元素大小为 \(l\)（\(l=\) sizeof(ElemType)），则数据元素 \(a_i\) 和 \(a_{i+1}\) 的存储位置 \(LOC\) 满足：\(LOC(a_{i+1})=LOC(a_i)+l\)

    顺序表的第 \(i\) 个数据元素 \(a_i\) 的存储位置为：\(LOC(a_i)=LOC(a_1)+(i-1)\times l\)

  • 顺序表的特点：
    ① （优点）可随机访问，即可在 \(O(1)\) 时间找到第 \(i\) 个元素
    ② （优点）存储密度高（每个结点只存储数据）
    ③ （缺点）拓展容量不方便（因为顺序存储分配需要一段连续的存储空间）
    ④ （缺点）插入、删除操作不方便，需要移动大量元素

2.2.1 顺序表的实现：静态分配

#include <stdio.h>
#define MaxSize 10			//定义顺序表最大长度
typedef struct{ElemType data[MaxSize];	//用静态的数组存放数据元素int length;				//顺序表当前长度
}SqList;//初始化顺序表
void InitList(SqList &L){//对数据元素默认值的初始化可省略L.length=0;		//顺序表初始长度为0（此步不可省略）
}int main(){SqList L;	//声明一个顺序表InitList(L);	//初始化顺序表return 0;
}
  • 通过静态分配（数组）实现的顺序表是存在局限性的：顺序表的表长确定后就无法更改，因为这种顺序表的存储空间是静态的。

2.2.2 顺序表的实现：动态分配

  • C语言：使用 malloc 和 free 函数动态申请和释放内存空间（在头文件 <stdlib.h> 中）

    • malloc 申请的存储空间属于 “堆” 区，堆区申请的空间需要手动释放
    • 而定义一个数组对应的存储空间属于栈，属于静态资源，函数周期结束后会自动释放

  • C++：使用 new 和 delete 关键字

  • 动态分配的顺序表不在定义结构体时固定（数组）大小，而是在进行初始化或拓展存储大小时使用指针指向动态分配的一片连续的存储空间，其结构体包含上述指针、顺序表当前长度和顺序表当前的最大容量等，最大长度用于方便检查当前顺序表是否够用。

#include <stdio.h>
#include <stdlib.h>
#define InitSize 10	//顺序表默认初始最大长度
typedef struct{int *data;		//指示动态分配数组的指针，指向数组第一个元素int MaxSize;	//顺序表的最大长度（容量）int length;		//顺序表的当前长度
}SeqList;//顺序表初始化
void InitList(SeqList &L){//用malloc函数申请一片连续的存储空间L.data = (int *)malloc(InitSize*sizeof(int));L.length = 0;L.MaxSize = InitSize;
}//增加顺序表长度
void IncreaseSize(SeqList &L, int len){		//len是额外增加的长度//重新申请新存储空间前用一个指针记录原存储空间的起始地址int *p = L.data;//注意malloc是重新申请一片新的连续存储空间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;	//更新顺序表的最大长度free(p);	//释放原存储空间      
}int main(){SeqList L;InitList(L);// 当经过一系列操作导致顺序表长度不足IncreaseSize(L, 5);return 0;}

2.2.3 顺序表的基本操作

(1) 插入
#include <stdio.h>
#define MaxSize 10
typedef struct{int data[MaxSize];int length;
}SqList;//初始化顺序表
void InitList(SqList &L){L.length=0;
}//顺序表插入操作（通过返回bool健壮代码）（这里i是位号）
bool ListInsert(SqList &L,int i,int e){//判断插入位置i是否有效(1 <= i <= L.length+1)if(i<1||i>L.length+1)return false;//当存储空间已满，不能插入if(l.length>=MaxSize)return false;//将第i个（data[i-1]）及之后的元素后移（从最后一个元素开始）for(int j=L.length; j>=i; j--)	//j为后移位置j最终为i-1(j是位序)L.data[j] = L.data[j-1];	//数组中第j个元素的位序为j+1L.data[i-1] = e;	//在位置i处放入eL.length++;			//顺序表长度+1return true;
}int main(){SqList L;InitList(L);//一些列操作后if(ListInsert(L, 3, 3))printf("插入成功");elseprintf("插入失败")return 0;
}

顺序表插入操作时间复杂度：

image-20241029163022790
(2) 删除
#include <stdio.h>
#define MaxSize 10
typedef struct{int data[MaxSize];int length;
}SqList;//初始化顺序表
void InitList(SqList &L){L.length=0;
}//顺序表（按位）删除操作（通过bool健壮代码）
bool ListDelete(SqList &L, int i, int &e){	//注意是&e//判断删除位置i是否有效(1 <= i <= L.length)if(i<1||i>L.length)return false;e=L.data[i-1];	//位序为i的元素在数组中在第i-1个//将第i个位置后的元素前移（j指向要往前移的内容）for(int j=i; j<L.length; j++)L.data[j-1] = L.data[j];L.length--;		//顺序表长度-1return true;
}int main(){SqList L;InitList(L);//一系列操作后int e = -1;		// 用变量e获取被删除的元素if(ListDelete(L,3,e))printf("成功删除第3个元素，删除元素值为 %d", e);elseprintf("位序i不合法，删除失败");return 0;}

顺序表删除操作时间复杂度：

image-20241029164427685
(3) 按位查找
#define InitSize 10	//顺序表默认初始最大长度
typedef struct{ElemType *data;	//指示动态分配数组的指针，指向数组第一个元素int MaxSize;	//顺序表的最大长度int length;		//顺序表的当前长度
}SeqList;//按位查找，静态分配和动态分配实现的顺序表方法相同
ElemType GetElem(SeqList L, int i){return L.data[i-1]
}

顺序表按位查找时间复杂度： 顺序表是可以随机存取的，因此时间复杂度为 \(O(1)\)

(4) 按值查找
#define InitSize 10	//顺序表默认初始最大长度
typedef struct{ElemType *data;	//指示动态分配数组的指针，指向数组第一个元素int MaxSize;	//顺序表的最大长度int length;		//顺序表的当前长度
}SeqList;//顺序表按值查找
int LocateElem(SeqList L, ElemType e){for(int i=0; i<L.length; i++)if(L.data[i]==e)return i+1;		//返回位序return 0;	//推出循环，说明查找失败
}
  • 注意在 C 语言中结构体无法直接通过 "==" 比较，应确保 ElemType 是可以用 "==" 比较的类型

顺序表按值查找时间复杂度：

image-20241029183212681

2.3 链表

2.3.1 单链表

  • （单）链表：用链式存储结构实现线性表
  • 单链表一个结点存储一个数据元素，各结点间先后关系用于一个指针表示
  • 单链表和顺序表比较：
    顺序表：优点：可随机存取，存储密度高；缺点：要求大片存储空间，改变容量不便
    单链表：优点： 不要求大片连续空间，改变容量方便；缺点： 不可随机存取，要耗费一定空间存放指针
  • 单链表在实现上可以分为带头结点和不带头结点，头结点除指针不存放任何内容，综合上带头结点的方法更实用，本笔记后续内容未特意声明情况默认使用带头结点。
    • 带头结点优势：① 插入和删除数据元素的算法可以统一；② 空表和非空表的处理可以统一

单链表的定义：

//定义一个单链表
typedef struct LNode{ElemTpye data;		//每个结点存放一个数据元素struct LNode *next;	//指向下一个结点的指针，指针类型为结点结构体
}LNode, *LinkList;		//注意LNode代表一个结点，而*LinkList是指向LNode类型结点的指针//上述定义方法等价于如下方法（关于typedef关键字的使用）
struct LNode{ElemTpye data;		//每个结点存放一个数据元素struct LNode *next;	//指向下一个结点
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;//声明一个单链表（只需要声明一个指针，指向单链表的第一个结点）
LNode *L;
LinkList L;	//两种方法效果相同，前者强调表示单个结点，后者强调表示整个链表

不带头结点的单链表：

typedef struct LNode{ElemTpye data;		//每个结点存放一个数据元素struct LNode *next;	//指向下一个结点
}LNode, *LinkList;//初始化一个空的单链表
bool InitList(LinkList &L){	//注意形参使用&，使可以真正修改L的指向L = NULL;	//空表，暂时无任何结点return true;
}void test(){LinkList L;		//声明一个指向单链表的指针InitList(L);	//初始化一个空表
}

带头结点的单链表：

typedef struct LNode{ElemTpye 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;    
}void test(){LinkList L;		//声明一个指向单链表的指针InitList(L);	//初始化一个空表
}
  • 当你有一个指向结构体的指针变量，则需要用 -> 来访问该指针指向的结构体中的内容，即 -> 符号的左侧应该为结构体指针，如 L->data 表示 L 是一个结构体指针，要访问该指针指向的结构体中的内容 data
  • 当你有一个结构体变量，则需要用 . 来访问结构体中的内容，. 符号左侧为结构体变量。如 L.data 表示 L 是结构体变量，要访问中的 data
  • 若 p 是一个指向结构体的指针，则 *p 就是指针指向的内容，即结构体变量，p->data 和 (*p).data 完全等价
(1) 按位插入（带头结点）
//在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){if(i<1)return false;/* 查找可用 LNode *p = GetElem(L,i-1); */LNode *p;	//p指针将指向当前扫描到的结点int j=0;	//记录p当前指向第几个结点（初始指向头结点）p = L;		//L指向头结点（第0个不存数据的结点）while(j<i-1 && p!=NULL){	//循环找到第i-1个结点p=p->next;j++;}/* 插入可用 return InsertNextNode(p, e); */if(p==NULL)//当插入位置大于“链表长度+1”时不合法return false;LNode *s = (LNode *)malloc(sizeof(LNode));s->data = e;//注意下面两步修改指针指向的顺序不可颠倒s->next = p->next;	//先将后面的结点与s连上p->next = s;		//再将连上后面结点的s与前面的结点连上return true;
}

按位序插入（带头结点）时间复杂度： 最好 \(O(1)\)，最差 \(O(n)\)，平均 \(O(n)\)

(2) 按位插入（不带头结点）
//在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){if(i<1)return false;if(i==1){	//插入第1个结点的操作不同LNode *s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = L;L = s;	//头指针指向新结点return true;}LNode *p;int j=1;	//记录p当前指向第几个结点（不带头结点，所以从第一个结点开始）p = L;		//L指向第1个结点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;
}
(3) 指定结点后插
bool InsertNextNode(LNode *p, ElemType 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;
}
(4) 指定结点前插
  • 直接指定结点所以无法获取前趋结点，通过后插并交换结点内容实现前插
bool InsertNextNode(LNode *p, ElemType e){if(p==NULL)return false;LNode *s = (LNode *)malloc(sizeof(LNode));if(s==NULL)		//内存分配失败return false;//通过与后插结点交换data内容实现前插操作（两极反转！）s->data = p->data;s->next = p->next;p->data = e;p->next = s;return true;
}

时间复杂度：\(O(1)\)

(5) 按位删除
bool ListDelete(LinkList &L, int i, ElemType &e){	//注意实用了&eif(i<1)return false;LNode *p;int j=0;p = L;while(p!=NULL && j<i-1){	//循环找到第i-1个结点p=p->next;j++;}if(p==NULL)//当删除位置大于“链表长度+1”时不合法return false;if(p->next==NULL)//第i-1个结点为最后一个结点return false;LNode *q = p->next;	//q指针指向待删除结点e = q->data;		//用e返回被删除元素的值p->next = q->next;	//断开q指向的结点free(q);			//释放被删除结点的存储空间return true;
}

时间复杂度： 最好 \(O(1)\)，最差 \(O(n)\)，平均 \(O(n)\)

(6) 指定结点删除（不适用尾结点）

方法1： 指定结点导致无法获取直接前趋结点，所以通过与后继结点交换数据域实现，但存在bug：当指定的结点为最后一个结点时如下方法不可用

bool DeleteNode_1(LNode *p){if(p==NULL) return false;if(p->next==NULL) return false;	//若为尾结点无法实现后续操作LNode *q = p->next;	//q指向p的后继结点p->data = q->data;	//与后继结点交换数据p->next = q->next;	//断开qfree(q);return true;
}

方法1时间复杂度：\(O(1)\)

(7) 按位查找
LNode * GetElem(LinkList L, int i){	//返回指针或NULLif(i<0)return NULL;LNode *p;int j=0;p = L;while(p!=NULL && j<i){p=p->next;j++;}return p;
}

时间复杂度： 平均 \(O(n)\)

(8) 按值查找
//找到数据域为e的结点
LNode *LocateElem(LinkList L, ElemType e){LNode *p = L->next;//从第1个结点开始查找数据域为e的结点while(p!=NULL && p->data!=e)	//注意：若e为struct类型则不可之间判断是否相等p = p->next;return p;	//找到后返回该结点指针，否则返回NULL
}

时间复杂度： 平均 \(O(n)\)

(9) 求表的长度
int Length(LinkList L){int len = 0;LNode *p = L;while(p->next!=NULL){p = p->next;len++;}return len;
}

时间复杂度：\(O(n)\)

(10) 尾插法建立单链表
LinkList List_TailInsert(LinkList &L){	//这里L只是声明过的指针int x;	//设ElemType为整型L = (LNode *)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;		//r重新指向为结点scanf("%d", &x);}r->next = NULL;	//尾结点置空return L;
}

时间复杂度：\(O(n)\)

(11) 头插法建立单链表
  • 头插法实现策略可应用于链表的逆置（即链表序列与输入序列相反）
LinkList List_TailInsert(LinkList &L){	//这里L只是声明过的指针LNode *s;int x;L = (LNode *)malloc(sizeof(LNode));	//建立头结点L->next = NULL;						//初始为空链表（不可省）scanf("%d",&x);while(x!=9999){s = (LNode *)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;	//插入新结点scanf("%d", &x);}return L;
}

2.3.2 双链表

介绍

双链表可以双向检索，但存储密度相对下降（需要存储额外的指针信息）

双链表每个结点有两个指针，一个指向前趋结点，一个指向后继结点

//双链表定义
typedef struct DNode{ElemType 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;
}void testDLinkList(){DLinkList L;InitDLinkList(L);//……
}
(1) 插入
//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){if(p==NULL || s==NULL)return false;s->next = p->next;if(p->next!=NULL)	//若p有后继结点，使该结点的前趋指向sp->next->prior = s;s->prior = p;p->next = s;return true;
}
(2) 删除、销毁
//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){if(p==NULL)return false;DNode *q = p->next;	//找到p的后继结点if(q==NULL)	//p无后继结点return false;p->next=q->next;if(q->next!=NULL)	//待删除的q结点非最后一个结点q->next->prior = p;free(q);return true;
}void DestoryList(DLinkList &L){//循环释放各个结点while(L->next!=NULL)DeleteNextDNode(L);free(L);	//释放头结点L=NULL;		//头指针指向NULL
}

2.3.3 循环链表

循环单链表

在单链表的基础上，使表尾结点的 next 指针指向头节点

判断循环单链表（带头节点）是否为空，只需判断头结点的 next 指针是否指向自身

判断结点p是否为表尾结点，只需判断其 next 指针是否指向头节点

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

在双链表的基础上，使头节点的前趋指针指向表尾结点，使表尾结点的后继指针指向头节点

相比双链表，循环双链表的后插、后删操作不用再判断是后继结点是否存在

2.3.4 静态链表

  • 静态链表是用数组来描述线性表的链式存储结构，每个结点也有数据域 data 和指针域 next，但这里指针实际上是指数组的下标（游标）

    • 数组下标（游标）：下一个结点在连续空间中的（抽象的）位置，0 号结点为头结点，游标为 -1 表示当前是表尾结点

  • 适用场景： 不支持指针的低级语言；数据元素数量固定不变的场景（如OS的文件分配表FAT）

image-20251028174832888

2.4 顺序表 vs 链表

  • 逻辑结构上：都属于线性表，都是线性结构
  • 存储结构上：
    • 顺序表优点：①支持随机存取、②存储密度高（结点中存储的辅助信息少）
    • 顺序表缺点：① 大片连续空间分配起来不方便、② 容量扩充不方便
    • 链表优点：① 离散的空间分配起来方便、②改变容量方便
    • 链表缺点：① 不可随机存取、② 存储密度低
  • 在查找操作上：
    • 顺序表
      • 按位查找O(1)
      • 按值查找O(n)；若表内元素有序，则可在O(\(\log_2n\)) 时间内找到
    • 链表
      • 按值查找O(n)
      • 按位查找O(n)
标签： 网站建设 企业官网 项目流程 UI设计 前端开发

热门文章

文章分类

标签云

网站建设 响应式设计 用户体验 SEO优化 前端开发 小程序 电商平台 性能优化

相关文章

您可能感兴趣的其他内容

只学 Java 不娱乐，是自律还是自毁？程序员心理健康与高效成长的平衡之道
2025/12/28 15:10:50 网站建设

只学 Java 不娱乐，是自律还是自毁？程序员心理健康与高效成长的平衡之道

只学 Java 不娱乐&#xff0c;是自律还是自毁&#xff1f;程序员心理健康与高效成长的平衡之道 关键词&#xff1a;Java 开发、程序员心理、心理健康、技术成长、自律与平衡、职业发展 引言&#xff1a;当“卷”成为信仰&#xff0c;娱乐成了原罪&#xff1f; 在当今竞争激烈的…...

阅读更多 →
YOLO模型版本管理怎么做？配合GPU环境一键切换
2025/12/28 15:10:49 网站建设

YOLO模型版本管理怎么做？配合GPU环境一键切换

YOLO模型版本管理怎么做&#xff1f;配合GPU环境一键切换 在智能制造车间的视觉质检线上&#xff0c;工程师常常面临一个尴尬问题&#xff1a;新部署的YOLOv8模型虽然精度更高&#xff0c;但在老旧GPU设备上推理延迟翻倍&#xff1b;而回退到YOLOv5又会漏检微小缺陷。这种“升级…...

阅读更多 →
商业照明趋势：平衡能效与光品质的多维考量
2025/12/28 15:10:48 网站建设

商业照明趋势：平衡能效与光品质的多维考量

于商业照明范畴之内&#xff0c;能效跟品质之间的平衡&#xff0c;乃是设计人员以及运营者长时间予以关注的课题。伴随LED技术趋向成熟以及市场认知得以深化&#xff0c;节能业已并非单纯是降低电费成本的那种单一诉求&#xff0c;而是跟空间光环境质量、设备长时间可靠性以及综…...

阅读更多 →

需要专业的网站建设服务？

联系我们获取免费的网站建设咨询和方案报价，让我们帮助您实现业务目标

立即咨询