数据结构-线性表

2. 线性表

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

定义：n（n>=0）个相同数据类型的数据元素构成的有限序列，n=0时，线性表为空表。线性表用L一般表示为：

L = (a1,a2,a3....,ai-1,ai....,an)

几个概念:
ai是线性表中的“第i个”元素线性表中的位序注意:位序从1开始，数组下标从0开始
a1是表头元素; an 是表尾元素。

除第一个元素外，每个元素有且仅有一个直接前驱:除最后一个元素外，每个元素有且仅有一个直接后继

InitList(&L):初始化表。构造一个空的线性表L，分配内存空间。

DestroyList(&():销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

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

ListDelete(&L,&e):删除操作。删除表l中第1个位置的元素，并用e返回删除元素的值。

LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。

GetElem(Lj):按位查找操作。获取表L中第i个位置的元素的值。其他常用操作:

Length(U:求表长。返回线性表L的长度，即L中数据元素的个数。

PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。.

Empty(L):判空操作。若L为空表，则返回true，否则返回false.

Tips:
①对数据的操作(记忆思路) --创销、增删改查

②C语言函数的定义-- <返回值类型> 函数名(<参数1类型>参数1，<参数2类型>参数2，...)

③实际开发中，可根据实际需求定义其他的基本操作

④函数名和参数的形式、命名都可改变(Reference: 严蔚敏版《数据结构》Key:命名要有可读性

⑤什么时候要传入参数的引用“&”--对参数的修改结果需要“带回来”

2.2 顺序表

2.2.1 顺序表的定义

线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列

线性表L的逻辑结构

线性表的存储结构：顺序表——即在逻辑结构上相邻，在物理（存储）结构上也相邻

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

顺序表的实现——静态分配

#define MaxSize 10  			//定义最大长度
typedef struct{
    //ElemType是需要给定的数据类型
	ElemType data [MaxSize] ;	//用静态的“数组”存放数据元素.
	int length;					//顺序表的当前长度.
}SqList;						//顺序表的类型定义(静态分配方式)

eg:

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

void InitList(SqLsit &L){
	for(int i=0; i<MaxSize; i++){
        L.data[i] = 0;		//若不赋值，不能保障之前内存是否留存“脏数据”
    }
    L.length = 0;
}

int main(){
	SqList L; 		//声明一个顺序表
	InitList(L);	//初始化顺序表
	//....
	return 0;
}

静态分配会存在数据存满后就不能存的情况

顺序表的实现——动态分配**

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

动态申请和释放空间

C——malloc、free函数
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize)
C++——new、delete

eg：

#include <stdlib.h>
#define InitSize 10 	//默认的最大长度
typedef struct{
    int *data;			//指示动态分配数组的指针
    int MaxSize;		//顺序表的最大容量
    int length;			//顺序表的当前长度
}SeqList;

void InitList(SeqList &L){
    //用mal1oc 函数申请一片连续的存储空间
    L.data=(int * )malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize=InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
    int *p=L.data; //让p指向原区域
    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);
    //....往顺序表中插入几个元素
    IncreaseSize(L,5);
    return 0;
}

顺序表的特点:

①随机访问，即可以在O(1)时间内找到第i个元素。代码实现: data[i-1];静态分配、动态分配都一样

②存储密度高，每个节点只存储数据元素

③拓展容量不方便(即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高)

④插入、删除操作不方便，需要移动大量元素

2.2.2 顺序表的基本操作

1. 顺序表的插入和删除

顺序表的基本操作——插入

void ListInsert(SqList &L, int i, int e){	//在L的位序i处插入元素e
    for(int j = L.length;j>i;j--)	//所有i后面的元素往后移一位
        L.data[j] = L.data[j-1]
    L.data[i-1] = e;				//位序i，对应数组i-1
    L.length++;
}

优化代码：

bool ListInsert(SqList &L,int i,int e){
    if(i<1 || i>L.length+1)		//判断i的范围是否有效
    	return false;
    if(L.length>=MaxSize)    	//当前存储空间已满，不能插入
    	return false;
    for(int j=L.length;j>=i;j--) //将第i个元素及之后的元素后移
    	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)		//判断i的范围是否有效
        return flase;
    e = L.data[i-1];			//将被删除的元素赋值给e
     for(int j=L.length;j>=i;j--) //将第i个元素及之后的元素前移
    	L.data[j-1]=L.data[j];
    L.length--;    //长度减1
    return ture;
}

2. 顺序表的查找

顺序表按位查找

GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

#define MaxSize 10 				//定义最大长度
typedef struct{
    ElemType data [MaxSize] ;	//用静态的“数组”存放数据元素（静态分配）
    int length;					//顺序表的当前长度:
}SqList;						//顺序表的类型定义(静态分配方式)

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

GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

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

时间复杂度：O(1)

由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素——“随机存取”特性

顺序表按值查找

LocateElem(,e):按值查找操作。在表L中查找具有给定关键字值的元素。

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

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

基本数据类型: int、 char、 double、float等可以直接用运算符“==”比较

对于结构体的比较：

需要依次对比各个分量来判断两个结构体是否相等
typedef struct {
 int num;
 int people; 
} Customer;
if (a.num ==: b.num && a.people == b.people) {
	printf("相等");
}else {
	printf( "不相等");
}

2.3 单链表

单链表和顺序表的区别

struct LNode{			//结点
	ElemType data;		//数据域
	struct LNode* p;	//指针域
}

增加一个新的结点:在内存中申请一个结点所需空间，并用指针p指向这个结点

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

typedef关键字一一数据类型重命名

typedef <数据类型> <别名>
typedef struct LNode LNode;
LNode *p= (LNode *)malloc(sizeof(LNode));

代码优化：

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

LNode *p和 LNode L都表示指向结构体的指针

LNode *p 一般表示节点的指针

LNode L 头指针，一般用来表示一个链表

2.3.1 单链表的定义

不带头结点的单链表

bool InitList(LinkList &L){
	L = NULL;			//空表暂时没有任何节点（防止脏数据）
	return ture;
}

void test(){
	LinkList L;		//注意，此处并没有创建个结点
	InitList(L);
}

判空

//判断单链表是否为空
bool Empty(LinkList L) {
	if (L == NULL)
		return true;
	else
		return false;
}
//或者
bool Empty(LinkList L) {
	return (L==NULL); .
}

带头结点的单链表

//初始化-个单链表(带头结点)
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;
}

不带头结点，写代码更麻烦。对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑。对空表和非空表的处理需要用不同的代码逻辑

2.3.2 单链表的基本操作

1. 单链表的插入和删除

按位序插入（带头结点）

//在第i个位置插插入元素e (带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
		return false;
    LNode *p; 	//指针p指向当前扫描到的结点
    int j=0;     //当前p指向的是第几个结点
    p = L;	    //L指向头结点，头结点是第0个结点(不存数据)
    while (p!= NULL && j<i-1) { //循环找到第 i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL) 	//i值不合法
   		return false;
    LNode *s = (LNode *)malloc(sizeof (LNode));
    s->data = e;
    s->next=p->next;	//跟下一句有先后关系
	p->next=s;    //将结点s连到p之后
    return true;    //插入成功.
}

i = 1（插在表头）最好时间复杂度：O(1)

i = n （插在表尾）最坏时间复杂度：O(n)

平均时间复杂度:O(n)

按位序插入（不带头结点）

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 	//p指问第1个结点(注意:不是头结点)
    //下面和带头节点逻辑一样
    while (p!= NULL && j<i-1) { //循环找到第 i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL) 	//i值不合法
   		return false;
    LNode *s = (LNode *)malloc(sizeof (LNode));
    s->data = e;
    s->next=p->next;	//跟下一句有先后关系
	p->next=s;    //将结点s连到p之后
    return true;    //插入成功.
}

指定结点的后插操作

相当于按位序插入中查找步骤完成

bool ListInsert(LNode *p,  ElemType e){
	if(p==NULL) 	//i值不合法
   		return false;
    LNode *s = (LNode *)malloc(sizeof (LNode));
    s->data = e;
    s->next=p->next;	//跟下一句有先后关系
	p->next=s;    //将结点s连到p之后
    return true;    //插入成功.
}

时间复杂度：O(1)

指定结点的前插操作

1.循环查找p的前驱q，再对q后插
时间复杂度：O(n)

2.数据替换法

//前插操作:在p结点之前插入元素e
bool InsertPriorNode (LNode *p, ElemType 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 ;
}

时间复杂度：O(1)

按位序删除（带头结点）

ListDelete(&L,i,&e)：删除操作。删除表L中第==i个位置==的元素，并用e返回删除元素的值。

找到第 i-1 个结点，将其指针指向第i+1个结点，并释放第i个结点

bool ListDelete(LinkList &L，int i, ElemType &e){
    if(i<1)
	    return false;
    LNode *p; 	// 指针p指向当前扫描到的结点
    int j=0;    //当前p指向的是第几个结点
    p=L;    	//L指向头结点，头结点是第0个结点(不存数据)
    while (p!=NULL && j<i-1) { //循环找到第 i-1 个结点
        p=p->next;
        j++;
    }
    if( p==NULL)    //i值不合法
	    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;		    //删除成功
}

i = 1（删除在表头）最好时间复杂度：O(1)

i = n （删除在表尾）最坏时间复杂度：O(n)

平均时间复杂度:O(n)

指定结点的删除**

找到其后继节点，将后继节点数据转到当前节点，删除后继节点

bool DeleteNode(LNode *p){
	if( p==NULL)    //i值不合法
	    return false;
     LNode *q=p->next;    	//令q指向*p的后继结点
    p->data = p->next->data;//和后继节点交换数据
    p->next = q->next;	    //将*q结点从链中“断开”
    free(q);			    //释放结点的存储空间
    return true;		    //删除成功
}

注意：

如果p是最后一个节点，则只能从表头开始依次寻找p的前驱，时间复杂度O(n)

2. 单链表的查找

按位查找

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

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

按值查找

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

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

求表的长度

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

时间复杂度：O(n)

2.3.3 单链表的建立

1. 尾插法

尾插法建立单链表原理

//在第i个位置插插入元素e (带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
		return false;
    LNode *p; 	//指针p指向当 前扫描到的结点
    int j=0;     //当前p指向的是第几个结点
    p = L;	    //L指向头结点，头结点是第0个结点(不存数据)
    while (p!= NULL && j<i-1) { //循环找到第 i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL) 	//i值不合法
   		return false;
    LNode *s = (LNode *)malloc(sizeof (LNode));
    s->data = e;
    s->next=p->next;	//跟下一句有先后关系
	p->next=s;    //将结点s连到p之后
    return true;    //插入成功.
}

尾插法建立链表实现：

LinkList List_Taillinsert(LinkList &L){
	int x;	//设置Element的类型为整型
    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;			//r指向新的尾表节点
        scanf("%d",&x);
    }
    r->next = NULL;		//尾指针置为空
    return L;
}

时间复杂度：O(n)

2. 头插法

头插法建立单链表原理

//后插操作:在p结点之后插入元素e
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保存数据元素e
    s->next=p->next;
    p->next=s;    	//将结点s连到p之后
    return true;
}

每次都对头节点进行后插操作

头插法建立单链表实现：相当于每次新结点都是作为第一个结点

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;
}

L->next=NULL;
不能去除，在尾插法中可以去掉，但是还是建议都加上

头插法建立单链的重要应用：==链表的逆置==

2.4 双链表

双链表和单链表的区别

typedef struct DNode{		//定义双链表结点类型
    ElemType data;				//数据域
    struct DNode *prior, *next;	//前驱和后继指针
}DNode，*DLinklist;

相比于单链表，双链表访问前后相邻节点跟方便，同时其存储密度也更低一点

2.4.1 双链表的初始化

双链表的初始化（带头结点）

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

//判断双链表是否为空(带头结点)
bool Empty(DLinklist L) {
if (L->next == NULL)
	return true;
else
	return false;
}

双链表的插入

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
    if(p=NULL || s=NULL) //非法参数
        return false;
    s->next=p->next;//将结点*s插入到结点*p之后
    if(p->next->prior!=NULL) //为了防止p是最后一个节点
	    p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}

位序插入：先遍历，找到对应位序的前一个节点，进行后插操作（O(n)）

前插操作：找到对应节点的前一个节点，进行后插操作（O(1)）

2.3.2 双链表的删除

//删除p结点的后继结点
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结点不是最后- 个结点
        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 双链表的遍历

//后向遍历
while(p!=NULL){
    //....对节点p的相关操作
	p = p->next;
}

//前向遍历
while(p!=NULL){
    //....对节点p的相关操作
	p = p->prior;
}

//前向遍历（跳过头节点）
while(p->prior!=NULL){
    //....对节点p的相关操作
	p = p->prior;
}

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度O(n)

2.5 循环链表

2.5.1 循环单链表

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

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;
}

//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L，LNode *p){
    if (p->next==L)]
        return true ;
    else
        return false;
}

单链表：从一个结点出发只能找到后续的各个结点

循环单链表：从一个结点出发可以找到其他任何一个结点

常对链表的头部或尾部进行操作时，可以让L指向表尾元素(插入、删除时可能需要修改)，即用一个不带头结点且有尾指针的单循环链表

2.5.2 循环双链表

//初始化空的循环双链表
bool InitDLinkL ist (DLinklist &L){
    L = (DNode *) malloc(sizeof (DNode)); //分配-个头结点
    if (L==NULL) 	//内存不足，分配失败
        return false;
    L->prior = L;	//头结点的prior指向头结点（特性：prior指向尾节点）
    L->next = L;	//头结点的next 指向头结点
    return true;
}

//判断循环双链表是否为空
bool Emptv(DL inklist L){
    if(L->next ==L）
       return true;
     else
       return false;
}

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

循环双链表插入

//在p结点之后插入s结点
bool InsertNextDNode (DNode *p, DNode *s){
    s->next=p->next; //将结点*s插入到结点和之后
    p->next->prior=s; //普通双链表在此处需判断p是否尾节点
    s->prior=p;
    p->next=s;
}

循环双链表的删除

从删除p的后继结点q
p->next=q->next;
q->next->prior=p;	//普通双链表在此处需判断p是否尾节点
free(q);

2.6 静态链表

2.6.1 静态链表定义

单链表：各个结点在内存中星罗棋布、散落天涯。

静态链表：分配一整片连续的内存空间，各个结点集中安置。每个数据元素 4B，每个游标4B（每个结点共 8B）设起始地址为 addre

定义一个静态链表

#define MaxSize 10	//静态链表的最大长度
struct Node{		//静态链表结构类型的定义
    ElemType data;	//存储数据元素
    int next;		//下一个元素的数组下标
};

void testSLinkL ist() {
    struct Node a[MaxSize]; //数组a作为静态链表
    //......后续代码
}

等价于：

#define MaxSize 10	//静态链表的最大长度
typedef struct {	//静态链表结构类型的定义
    ElemType data;	//存储数据元素
    int next;	//下一个元素的数组下标
} SLinkList[MaxSize];

void testSLinkList() {
    SLinkList a;
    //.....后续代码
}

在代码阅读感知方面：

//a是一个Node型数组
struct Node a[MaxSize]; //数组a作为静态链表

//a是一个静态链表
SLinkList a;

2.6.1 基本操作实现

初始化静态链表：把 a[0] 的 next 设为 -1 把其他结点的 next 设为一个特殊值用来表示结点空闲，如 -2
查找：从头结点出发挨个往后遍历结点（O(n)）
插入位序为 i 的结点：
1. 找到一个空的结点，存入数据元素
2. 从头结点出发找到位序为 i-1 的结点
3. 修改新结点的 next
4. 修改 i-1 号结点的 next
删除某个结点：
1. 从头结点出发找到前驱结点
2. 修改前驱结点的游标
3. 被删除结点 next 设为特殊值（如-2）

2.7 顺序表vs链表

特性	顺序表	链表
逻辑结构	线性结构	线性结构
存储结构	顺序存储	链式存储

存储结构：

顺序存储：

优点：支持随机存取、存储密度高

缺点：大片连续空间分配不方便，改变容量不方便

链式存储：

优点：离散的小空间分配方便，改变容量方便

缺点：不可随机存取，存储密度低

基本操作比较

创建

销毁

增、删

查找

基于基本操作，选取上的优先级

特性	顺序表	链表
弹性（可扩容）	✗	✔
增、删	✗	✔
查	✔	✗

表长难以预估、经常要增加/删除元素 ——链表

表长可预估、查询（搜索）操作较多 ——顺序表

如果觉得文章对你有用，请随意赞赏

数据结构

数据结构-线性表

http://localhost:8090/archives/2614e4ed-349e-4a6c-9661-a429201c3d71

作者

Administrator

发布于

2024-09-22

更新于

2024-09-22

许可协议

CC BY 4.0

数据结构-线性表

2. 线性表

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

2.2 顺序表

2.2.1 顺序表的定义

2.2.2 顺序表的基本操作

1. 顺序表的插入和删除

2. 顺序表的查找

2.3 单链表

2.3.1 单链表的定义

2.3.2 单链表的基本操作

1. 单链表的插入和删除

2. 单链表的查找

2.3.3 单链表的建立

1. 尾插法

2. 头插法

2.4 双链表

2.4.1 双链表的初始化

2.3.2 双链表的删除

2.3.3 双链表的遍历

2.5 循环链表

2.5.1 循环单链表

2.5.2 循环双链表

2.6 静态链表

2.6.1 静态链表定义

2.6.1 基本操作实现

2.7 顺序表vs链表

作者

发布于

更新于

许可协议

评论