【线性表,线性表中的顺序表和链表】

目录

  • 1、线性表的定义和基本操作
    • 1.1、线性表的定义
    • 1.2、线性表的基本操作
  • 2、顺序表和链表的比较
    • 2.1、顺序表
      • 2.1.1、顺序表的定义和特点
      • 2.1.2、顺序表的实现
        • (1)顺序表的静态分配:
        • (2)顺序表的动态分配
      • 2.1.3、顺序表的基本操作:
        • (1)插入操作
        • (2)删除操作
        • (3)按位查找
        • (4)按值查找
    • 2.2、链表
      • 2.2.1、链表的定义及特点
      • 2.2.2、链表的实现方式
        • (1)带头结点
        • (2)不带头结点:
      • 2.2.3、单链表的基本操作
        • (1)单链表的插入
        • (2)指定结点的后插操作
        • (3)指定结点的前插操作
        • (4)单链表的删除
          • 1)按位序删除结点
          • 2)指定结点的删除
        • (5)单链表的查找
          • 1)按位查找
          • 2)按值查找
        • (6)求单链表的长度
        • (7)单链表的建立
          • 1)尾插法建立单链表
          • 2)头插法建立单链表
          • 3)链表的逆置
      • 2.2.4、双链表
        • 2.2.4.1、双链表的初始化(带头结点)
        • 2.2.4.2、双链表的插入(后插)
        • 2.2.4.3、双链表的删除(后删)和销毁
        • 2.2.4.4、双链表的遍历
          • 1)前向遍历
          • 2)后向遍历
      • 2.2.5、循环链表
        • 2.2.5.1、循环单链表
        • 2.2.5.2、循环双链表
        • 2.2.5.3、循环链表的插入
        • 2.2.5.4、循环链表的删除
      • 2.2.6、静态链表
        • 2.2.6.1、静态链表的定义
    • 2.3、顺序表和链表的比较

1、线性表的定义和基本操作

1.1、线性表的定义

线性表是具有相同数据类型的n(n>0)个数据元素的有限序列
其中n为表长,当n=0时,线性表是一个空表,若用L命名线性表,则其一般表示为:
在这里插入图片描述
特点:

  1. 存在唯一的第一个元素;
  2. 存在唯一的最后一个元素;
  3. 除第一个元素外,每个元素均只有一个直接前驱;
  4. 除最后一个元素外,每个元素均只有一个直接后继;

【直接前驱】:指在该序列中位于其前面且紧邻的元素;
【直接后继】:指在该序列中位于其后面且紧邻的元素。
例如:在一个整数数组[1,5,8,10,49]中,元素8的直接前驱为5,直接后继为10。

1.2、线性表的基本操作

  1. InitList(&L):初始化表,构造一个空的线性表L,分配内存空间;
  2. DestroyList(&L):销毁操作,销毁线性表,并释放线性表L所占用的空间;
  3. ListInsert(&L;i,e):插入操作,在线性表L中的第i个位置上插入指定元素e;
  4. ListDelete(&L;i,&e):删除操作,删除线性表L中第i个位置处的元素,并用e返回删除的元素;
  5. LocateElem(L,e):按值查找操作,在表L中查找具有给定关键字值的元素;
  6. GetElem(L,i):按位查找操作,获取表L中第i个位置上的元素的值;
  7. Length(L):求表长,返回线性表L的长度,即L中数据元素的个数;
  8. PrintList(L):输出操作,按照前后顺序输出线性表L中的所有元素值;
  9. Empty(L):判空操作,若L为空表,则返回为true,否则返回false。
    发现在上述操作中,创销增删时传入的是参数的引用,其余操作传入的是参数,涉及到了传值调用传址调用,如下:
    1.传值调用
#include<stdio.h>
void test(int x) {
	x = 1024;
	printf("test函数内部 x = %d\n",x);
}

int main() {
	int x = 1;
	printf("调用test前 x = %d\n", x);
	test(x);
	printf("调用test后 x = %d\n", x);

	return 0;
}

程序输出结果为:
在这里插入图片描述
2.传址调用

#include<stdio.h>
void test(int &x) {
	x = 1024;
	printf("test函数内部 x = %d\n",x);
}

int main() {
	int x = 1;
	printf("调用test前 x = %d\n", x);
	test(x);
	printf("调用test后 x = %d\n", x);

	return 0;
}

程序输出结果为:
在这里插入图片描述

2、顺序表和链表的比较

2.1、顺序表

2.1.1、顺序表的定义和特点

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

顺序表的特点:

  1. 随机访问,即可以在O(1)时间内找到第i个元素;
  2. 存储密度高,每个节点只存储数据元素
  3. 拓展容量不方便,即使使用动态分配的方式实现,拓展长的的时间复杂度也比较高,因为需要把数据复制到新的区域;
  4. 插入删除操作不方便,需要移动大量的元素,时间复杂度为:O(n)。

2.1.2、顺序表的实现

顺序表的实现:顺序表的实现有静态分配动态分配

(1)顺序表的静态分配:
  1. 使用静态数组实现;
  2. 顺序表的表长刚开始确定后就无法再更改(存储空间是静态的)。
#include<stdio.h>
#define MaxSize 10 //定义表长最大值为10

using namespace std;

typedef struct {
    int data[MaxSize];//用静态数组存放数据元素
    int length;//顺序表的当前长度
}ArrayList;//顺序表的定义类型(静态分配方式)

void initList(ArrayList &L) {
    for (int i = 0; i < MaxSize;i++) {
        L.data[i] = 0;//将所有数据元素设置为默认初始值
    }
    L.length = 0;
}
void insertList(ArrayList& L,int i,int e) {

}

int main() {
    ArrayList L;//声明一个顺序表
    initList(L);//初始化一个顺序表
    for (int i =0; i < MaxSize; i++) {
        printf("data[%d] = %d\n", i, L.data[i]);//顺序表的打印
    }
    return 0;
}
(2)顺序表的动态分配
#include<stdio.h>
#include<stdlib.h>//malloc,free的头文件
#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) {
	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);
	increaseSize(L,5);
	return 0;
}

2.1.3、顺序表的基本操作:

(1)插入操作

ListInsert(&L,i,e):在第i个位置处插入指定元素e,平均时间复杂度为:O(n)

#define MaxSize 10    //定义最大长度
typedef struct{
	int data[MaxSize];  //用静态的数组存放数据
	int length;         //顺序表的当前长度
}SqList;                //顺序表的类型定义  
 
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;
}
 
int main(){ 
	SqList L;   //声明一个顺序表
	InitList(L);//初始化顺序表
	//...此处省略一些代码;插入几个元素
 
	ListInsert(L,3,3);   //再顺序表L的第三行插入3
 
	return 0;
}
(2)删除操作

ListDelete(&L,i,&e):删除表L中第i个位置处的元素,并用e返回删除元素的值,平均时间复杂度为:O(n)

#define MaxSize 10
 
typedef struct {
	int data[MaxSize];
	int length;
} SqList;
 
// 删除顺序表i位置的数据并存入e
bool ListDelete(SqList &L, int i, int &e) {
	if (i < 1 || i > L.length) // 判断i的范围是否有效
		return false;
	e = L.data[i-1]; // 将被删除的元素赋值给e 
	for (int j = i; j < L.length; j++) //将第i个位置后的元素前移 
		L.data[j-1] = L.data[j];
	L.length--;
	return true; 
}
 
int main() {
	SqList L;
	InitList(L);
	int e = -1;
	if (ListDelete(L, 3, e))
		printf("已删除第3个元素,删除元素值为%d\n", e);
	else
		printf("位序i不合法,删除失败\n"); 
	return 0; 
} 
(3)按位查找

GetElem(L,i):获取顺序表L中第i个位置上的元素,平均时间复杂度为:O(1)

// 静态分配的按位查找
#define MaxSize 10
 
typedef struct {
	ElemType data[MaxSize]; 
	int length;
}SqList;
 



ElemType GetElem(SqList L, int i) {
	return L.data[i-1];
}
// 动态分配的按位查找
#define InitSize 10
 
typedef struct {
	ElemType *data;
	int MaxSize;
	int length;
}SeqList;
 
ElemType GetElem(SeqList L, int i) {
	return L.data[i-1];
}
(4)按值查找

LocateElem(L,e):在表L中查找具有给的那个关键字值的元素,平均时间复杂度为:O(n)

#define InitSize 10          //定义最大长度 
typedef struct{
    ElemTyp *data;           //用静态的“数组”存放数据元素 
    int Length;              //顺序表的当前长度
}SqList;   
 
//在顺序表L中查找第一个元素值等于e的元素,并返回其位序
int LocateElem(SqList L, ElemType e){
    for(int i=0; i<L.lengthl i++)
        if(L.data[i] == e)  
            return i+1;     //数组下标为i的元素值等于e,返回其位序i+1
    return 0;               //推出循环,说明查找失败
}
//调用LocateElem(L,9)

2.2、链表

2.2.1、链表的定义及特点

单链表: 用链式存储实现了线性结构,一个结点存储一个数据元素,各结点间的前后关系用一个指针表示。

特点:

  1. 优点:不要求大片连续空间,改变容量方便
  2. 缺点:不可随机存取,要耗费一定空间存放指针
//定义单链表结点类型
typedef struct LNode{
    ElemType data;//数据域
    struct LNode *next;//指针域
}LNode, *LinkList;

强调这是一个结点的时候用LNode*;
强调这是一个单链表的时候用LinkList。

2.2.2、链表的实现方式

(1)带头结点

写代码更方便,头结点不存储数据,头结点指向的下一个结点才存放实际数据;

#include<stdlib.h>
#include<stdio.h>

typedef int ElemType;

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 = NULL;//头结点之后暂时还没有结点
    return true;
}

void test() {
    LinkList L;
    initList(L);
    //...
}

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

麻烦,对第一个数据结点与后续数据结点的处理需要用不同的代码逻辑,对空表和非空表的处理需要用到不同的代码逻辑。

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;
 
//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL; //空表,暂时还没有任何结点
    return true;
}
 
void test(){
    LinkList L;  //声明一个指向单链表的头指针
    //初始化一个空表
    InitList(L);
    ...
}
 
//判断单链表是否为空
bool Empty(LinkList L){
    return (L==NULL)
}

2.2.3、单链表的基本操作

(1)单链表的插入

ListInsert(&L,i,e): 在表L中第i个位置处插入一个元素e。找到第i-1个结点(前驱结点),将新结点插入其后,其中头结点可以看做第0个结点,故i=1时也适用。
平均时间复杂度为:O(n)

//带头结点的插入
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;
 
//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e)
{  
    //判断i的合法性, i是位序号(从1开始)
    if(i<1)
        return False;
    
    LNode *p;       //指针p指向当前扫描到的结点 
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点,头结点是第0个结点(不存数据)
 
    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }
 
    if (p==NULL)                 //如果p指针知道最后再往后就是NULL
        return false;
    
    //在第i-1个结点后插入新结点
    LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
    s->data = e;
    s->next = p->next;
    p->next = s;                 //将结点s连到p后,后两步千万不能颠倒
 
    return true;
}

不带头结点插入时,不存在第0个结点,因此!i = 1时,需要特殊处理:(插入删除)第1个元素时,需要更改头指针L;

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;
 
bool ListInsert(LinkList &L, int i, ElemType e)
{
    if(i<1)
        return false;
    
    //插入到第1个位置时的操作有所不同!
    if(i==1){
        LNode *s = (LNode *)malloc(size of(LNode));
        s->data =e;
        s->next =L;
        L=s;          //头指针指向新结点
        return true;
    }
 
    //i>1的情况与带头结点一样!唯一区别是j的初始值为1
    LNode *p;       //指针p指向当前扫描到的结点 
    int j=1;        //当前p指向的是第几个结点
    p = L;          //L指向头结点,头结点是第0个结点(不存数据)
 
    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }
 
    if (p==NULL)                 //i值不合法
        return false;
    
    //在第i-1个结点后插入新结点
    LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
    s->data = e;
    s->next = p->next;
    p->next = s;          
    return true;
 
}
(2)指定结点的后插操作

InsertNextNode(LNode *p, ElemType e);
给定一个结点p,在其后插入元素e,根据单链表的链表指针只能往后查找的逻辑关系,故给定一个结点p,p之后的结点我们可以知道,之前的就无法得知了。

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;
 
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;
}                         //平均时间复杂度 = O(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个结点(不存数据)
 
    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后4鸟会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }
 
    return InsertNextNode(p, e)
}
 
(3)指定结点的前插操作

设待插入结点为s,将s插入到结点p的前面,我们仍然可以将结点s插入到结点p之后,然后将p->data和s->data进行交换,这样既满足了逻辑关系,又能使得时间复杂度为O(n)。

//前插操作:在p结点之前插入元素e
bool InsertPriorNode(LNode *p, ElenType 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;
} 
(4)单链表的删除
1)按位序删除结点

ListDelete(&L,i,&e):删除表L中第i个位置上的元素,并用e来返回删除元素的值;头结点视为第0个结点;
思路:找到第i-1个结点,将其指针指向第i+1个结点,并释放第i个结点

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;
 
bool ListDelete(LinkList &L, int i, ElenType &e){
    if(i<1) return false;
 
    LNode *p;       //指针p指向当前扫描到的结点 
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点,头结点是第0个结点(不存数据)
 
    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }
 
    if(p==NULL) 
        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;
}
2)指定结点的删除
bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;
    
    LNode *q = p->next;      //令q指向*p的后继结点
    p->data = p->next->data; //让p和后继结点交换数据域
    p->next = q->next;       //将*q结点从链中“断开”
    free(q);
    return true;
} //时间复杂度 = O(1)
 
(5)单链表的查找
1)按位查找

GetElem(L,i):按位查找操作,获取表L中第i个位置上的元素
平均时间复杂度:O(n)

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;               //返回p指针指向的值
}
 
2)按值查找

GetElem(L,e):按值查找操作,在表L中查找具有关键字值e的元素;
平均时间复杂度:O(n)

LNode * LocateElem(LinkList L, ElemType e){
    LNode *P = L->next;    //p指向第一个结点
    //从第一个结点开始查找数据域为e的结点
    while(p!=NULL && p->data != e){
        p = p->next;
    }
    return p;           //找到后返回该结点指针,否则返回NULL
}
 
(6)求单链表的长度

Length(LinkList L):计算单链表中数据结点的个数(不含头结点),需要从第一个结点开始顺序依次访问表中的每个结点;
平均时间复杂度:O(n)

int Length(LinkList L){
    int len=0;       //统计表长
    LNode *p = L;
    while(p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}
(7)单链表的建立
  1. 初始化一个单链表
  2. 每次去一个数据元素,插入到表尾或表头
1)尾插法建立单链表

平均时间复杂度:O(n)
思路:每次都将新结点插入到当前链表的末尾,所以必须增加一个尾指针r,使其始终指向当前链表的为结点
优点:生成的链表中结点的次序和输入数据的顺序会一致

// 使用尾插法建立单链表L
LinkList List_TailInsert(LinkList &L){   
    int x;			//设ElemType为整型int  
    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;
}
2)头插法建立单链表

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

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;
   
}
3)链表的逆置

算法思想:逆置链表初始为空,原表结点从原链表中依次删除,再逐个插入逆置链表的表头(即“头插”到逆置链表中),使它成为逆置链表的新的第一个结点,如此循环,直至原链表为空;

LNode *Inverse(LNode *L)
{
	LNode *p, *q;
	p = L->next;     //p指针指向第一个结点
	L->next = NULL;  //头结点指向NULL
 
	while (p != NULL){
		q = p;
		p = p->next;
		q->next = L->next;  
		L->next = q;
	}
	return L;

2.2.4、双链表

对双链表中结点的描述:

//定义双链表结点类型
typedef struct DNode{
    ElemType data;//定义数据域
    struct DNode *prior, *next;//前驱指针和后继指针
}DNode,*DLinkList;
2.2.4.1、双链表的初始化(带头结点)
#include<stdlib.h>

typedef struct DNode {
	ElemType data;
	struct DNode* prior, * next;
}DNode, *DLinkList;

bool initlist(DLinkList &DL) {
	DL = (DNode*)malloc(sizeof(DNode));//分配一个结点
	if (DL == NULL)//内存不足,分配失败
		return false;

	DL->prior = NULL;//头结点的prior永远指向NULL
	DL->next = NULL;//头结点之后还没有结点
	return true;
}

void testDLinkList() {
	//初始化双链表
	DLinkList DL;
	initlist(DL);

}
//判断双链表是否为空
bool Empty(DLinkList DL) {
	if (DL->next == NULL)//判断头结点的next指针是否为空
		return false;
	else return true;
}
2.2.4.2、双链表的插入(后插)
//将结点p插到结点s之后
bool InsertNextDNode(DNode *s, DNode *p){
    if(p == NULL || s == NULL)
        return false;
    
    p->next = s->next;
    if(s->next != NULL)//s不是最后一个结点(s有后继结点)
        s->next->prior = p;
    p->prior = s;
    s->next = p;
}
2.2.4.3、双链表的删除(后删)和销毁
bool DeleteNextDNode(DNode *p){
    if(p == NULL) 
        return false;
    DNode *q = p->next;
    if(q == NULL)
        return false;
    p->next = q->next;
    if(q->next != NULL)
        q->next->prior = p;
    free(q);
    return true;
}
//销毁一个双链表
bool DestroyDLinkLIst(DLinkList &DL){
    //循环释放每一个结点
    while(DL->next !=NULL){
        DeleteNextDNode(DL);//删除头结点的后继节点
    free(DL);//释放头结点
    DL = NULL;//头结点指向空
    }
}
2.2.4.4、双链表的遍历
1)前向遍历
while(P != NULL){
    //对结点p做相应处理,eg.打印
    p = p->prior;
}
2)后向遍历
while(P != NULL){
    //对结点p做相应处理,eg.打印
    p = p->next;
}

注意:双链表不可以随机存取,按位查找和按值查找都只能用遍历的方式实现,时间复杂度为O(n)。

2.2.5、循环链表

2.2.5.1、循环单链表

最后一个结点的指针不是指向NULL而是指向头结点

typedef struct LNode{            
    ElemType data;               
    struct LNode *next;  
}DNode, *Linklist;
 
/初始化一个循环单链表
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点
    if(L==NULL)             //内存不足,分配失败
        return false;
    L->next = L;            //头结点next指针指向头结点
    return true;
}
 
//判断循环单链表是否为空(终止条件为p或p->next是否等于头指针)
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;
}

单链表和循环单链表的比较:

1. 单链表: 从一个结点出发,只能找到该结点后面的各个结点;对链表的操作大多都在头部或尾部;设立头指针,从头结点找到尾部得到时间复杂度为O(n),即对表尾操作需要O(n)的时间复杂度。
2. 循环单链表: 从表中任一个结点出发,可以找到该表中所有其他结点;设立尾指针,从尾部找到头部的时间复杂度为O(1),即对表头和表尾操作的时间复杂度都只需要O(1)的时间复杂度。
3. 循环单链表的优点: 从表中任一个结点出发,可以找到该表中所有其他结点;

2.2.5.2、循环双链表

表头结点的前驱结点prior指向表尾结点,表尾结点的后继结点next指向表头结点。

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 = L;          //头结点的prior指向头结点
    L->next = L;           //头结点的next指向头结点
}
 
void testDLinkList(){
    //初始化循环单链表
    DLinklist L;
    InitDLinkList(L);
    //...
}
 
//判断循环双链表是否为空
bool Empty(DLinklist 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;
}
 
2.2.5.3、循环链表的插入
bool InsertNextDNode(DNode *p, DNode *s){ 
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
2.2.5.4、循环链表的删除
//删除p的后继结点q
p->next = q->next;
q->next->prior = p;
free(q);

2.2.6、静态链表

2.2.6.1、静态链表的定义

用数组的方式来描述线性表的链式存储结构:分配一整片连续的内存空间,各个结点集中安置,包括了数据元素和下一个结点的数组下标(游标)。

#define MaxSize 10        //静态链表的最大长度
 
struct Node{              //静态链表结构类型的定义
    ElemType data;        //存储数据元素
    int next;             //下一个元素的数组下标(游标)
};
 
//用数组定义多个连续存放的结点
//相当于typedef struct Node SLinkList[MaxSize]; 重命名struct Node,用SLinkList定义“一个长度为MaxSize的Node型数组;
void testSLinkList(){
    struct Node a[MaxSize];  //数组a作为静态链表, 每一个数组元素的类型都是struct Node
    //...
}

或者是

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

2.3、顺序表和链表的比较

逻辑结构存储结构创建销毁增/删
顺序表线性表顺序存储 优点:支持随机存取,存储密度高 缺点:大片连续空间分配不方便,改变容量不方便静态分配:需要预分配大片连续空间,若空间太小,拓展容量不方便,若太大又浪费内存资源;动态分配:可以改变容量,但是需要移动大量元素,时间代价高对于静态数组,系统会自动回收;对于动态分配,需要手动进行free()插入/删除元素需要将后续元素进行后移/前移,时间复杂度为O(n),时间开销主要来自移动元素按位查找:O(1);按值查找:O(n),若表内元素有序,则可以在O(log2n)时间内找到
链表线性表链式存储 优点:离散的小空间分配方便,改变容量方便 缺点:不可随机存取,存储密度低只需要分配一个头结点或者声明一个头指针利用后删从头结点依次删除后续结点,最后释放头结点插入/删除元素只需要修改指针,时间复杂度为O(n),时间开销主要来自查找目标元素按位查找:O(n);按值查找:O(n)
顺序表链表
弹性(可扩容)不嘻嘻嘻嘻
增/删不嘻嘻嘻嘻
嘻嘻不嘻嘻

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

韦尔股份:深蹲起跳?

利润大增7倍&#xff0c;是反转信号还是回光返照&#xff1f; 今天我们聊聊光学半导体龙头——韦尔股份。 上周末&#xff0c;韦尔股份发布半年业绩预告&#xff0c;预计上半年净利润13至14亿&#xff0c;同比增幅高达 754%至 819%。 然而&#xff0c;回首 2023 年它的净利仅 …

如何将HEVC格式的视频转换为无损、未压缩的MP4格式视频?

在和大家分享视频格式转换之前&#xff0c;先跟大家分享一下HEVC格式的视频到底是什么文件&#xff1f;压缩原理是什么&#xff1f;了解了它的本质之后&#xff0c;我们就可以知道如何保证视频高清无损了。 如何将HEVC格式的视频转换为无损、未压缩的MP4格式视频&#xff1f; …

arm 、stm32、linux该如何学习?有没有先后顺序,先学什么比较好?

先讲自己&#xff0c;我是从Arduino单片机入门&#xff0c;再到stm32 &#xff0c;再开发瑞萨&#xff0c;TI&#xff0c;然后学校教了51。这是一个奇怪的学习过程&#xff0c;所以当我第一次接触51单片机的时候&#xff0c;刚好我有一些资料&#xff0c;是我根据网友给的问题精…

deep learning 环境配置

1 NVIDIA驱动安装 ref link: https://blog.csdn.net/weixin_37926734/article/details/123033286 2 cuda安装 ref link: https://blog.csdn.net/qq_63379469/article/details/123319269 进去网站 https://developer.nvidia.com/cuda-toolkit-archive 选择想要安装的cuda版…

光学传感器图像处理流程(二)

光学传感器图像处理流程&#xff08;二&#xff09; 2.4. 图像增强2.4.1. 彩色合成2.4.2 直方图变换2.4.3. 密度分割2.4.4. 图像间运算2.4.5. 邻域增强2.4.6. 主成分分析2.4.7. 图像融合 2.5. 裁剪与镶嵌2.5.1. 图像裁剪2.5.2. 图像镶嵌 2.6. 遥感信息提取2.6.1. 目视解译2.6.2…

PyTorch复现PointNet——模型训练+可视化测试显示

因为项目涉及到3D点云项目&#xff0c;故学习下PointNet这个用来处理点云的神经网络 论文的话&#xff0c;大致都看了下&#xff0c;网络结构有了一定的了解&#xff0c;本博文主要为了下载调试PointNet网络源码&#xff0c;训练和测试调通而已。 我是在Anaconda下创建一个新的…

硅纪元AI应用推荐 | 百度橙篇成新宠,能写万字长文

“硅纪元AI应用推荐”栏目&#xff0c;为您精选最新、最实用的人工智能应用&#xff0c;无论您是AI发烧友还是新手&#xff0c;都能在这里找到提升生活和工作的利器。与我们一起探索AI的无限可能&#xff0c;开启智慧新时代&#xff01; 百度橙篇&#xff0c;作为百度公司在202…

运算放大器(运放)输入失调电压

输入失调电压定义 理想状态下&#xff0c;如果运算放大器的两个输入端电压完全相同&#xff0c;输出应为0 V。实际上&#xff0c;还必须在输入端施加小差分电压&#xff0c;强制输出达到0。该电压称为输入失调电压VOS。输入失调电压可以看成是电压源VOS&#xff0c;与运算放大…

【排序 - 快速排序】

快速排序&#xff08;Quick Sort&#xff09;是一种高效的排序算法&#xff0c;它基于分治&#xff08;Divide and Conquer&#xff09;的策略。这种排序算法的核心思想是选择一个基准元素&#xff0c;将数组分割成两部分&#xff0c;使得左边的元素都小于等于基准元素&#xf…

实验-ENSP实现防火墙区域策略与用户管理

目录 实验拓扑 自己搭建拓扑 实验要求 实验步骤 整通总公司内网 sw3配置vlan 防火墙配置IP 配置安全策略&#xff08;DMZ区内的服务器&#xff0c;办公区仅能在办公时间内&#xff08;9: 00- 18:00)可以访问&#xff0c;生产区的设备全天可以访问&#xff09; 配置nat策…

(总结)编译ORB_SLAM2遇到的错误

目录 第一个错误error: ‘CV_BGR2GRAY’ was not declared in this scope 第二个错误error: ‘CV_GRAY2BGR’ was not declared in this scope 第三个错误是没有那个文件或目录 26 | #include 第四个错误是‘CV_LOAD_IMAGE_UNCHANGED’ was not declared in this scope 第…

Golang | Leetcode Golang题解之第228题汇总区间

题目&#xff1a; 题解&#xff1a; func summaryRanges(nums []int) (ans []string) {for i, n : 0, len(nums); i < n; {left : ifor i; i < n && nums[i-1]1 nums[i]; i {}s : strconv.Itoa(nums[left])if left < i-1 {s "->" strconv.It…

腾讯广告优量汇Android一面凉经(2024)

腾讯广告优量汇Android一面凉经(2024) 笔者作为一名双非二本毕业7年老Android, 最近面试了不少公司, 目前已告一段落, 整理一下各家的面试问题, 打算陆续发布出来, 供有缘人参考。今天给大家带来的是《腾讯广告优量汇Android一面凉经(2024)》。 面试职位: 腾讯广告优量汇-SDK客…

【算法】排序算法介绍 附带C#和Python实现代码

1. 冒泡排序(Bubble Sort) 2. 选择排序(Selection Sort) 3. 插入排序(Insertion Sort) 4. 归并排序(Merge Sort) 5. 快速排序(Quick Sort) 排序算法是计算机科学中的一个基础而重要的部分,用于将一组数据按照一定的顺序排列。下面介绍几种常见的排序算法,…

MVC分页

public ActionResult Index(int ? page){IPagedList<EF.ACCOUNT> userPagedList;using (EF.eMISENT content new EF.eMISENT()){第几页int pageNumber page ?? 1;每页数据条数&#xff0c;这个可以放在配置文件中int pageSize 10;//var infoslist.C660List.OrderBy(…

算法通关:004_1选择排序

代码一定要自己手敲理解 public class _004 {//选择排序&#xff0c;冒泡排序&#xff0c;插入排序//交换public static void swap(int[] arr,int i ,int j){int temp arr[i];arr[i] arr[j];arr[j] temp;}//选择排序public static void selectSort(int[] arr){if(arr null…

PDF 分割拆分 API 数据接口

PDF 分割拆分 API 数据接口 文件处理&#xff0c;PDF 高效的 PDF 分割工具&#xff0c;高效处理&#xff0c;可永久存储。 1. 产品功能 高效处理大文件&#xff1b;支持多语言字符识别&#xff1b;支持 formdata 格式 PDF 文件流传参&#xff1b;支持设置每个 PDF 文件的页数…

【PTA天梯赛】L1-005 考试座位号(15分)

作者&#xff1a;指针不指南吗 专栏&#xff1a;算法刷题 &#x1f43e;或许会很慢&#xff0c;但是不可以停下来&#x1f43e; 文章目录 题目题解try1 编译错误正确题解 总结 题目 题目链接 题解 try1 编译错误 #include<bits/stdc.h> using namespace std;typedef…

nginx正向代理、反向代理、负载均衡

nginx.conf nginx首要处理静态页面 反向代理 动态请求 全局模块 work processes 1; 设置成服务器内核数的两倍&#xff08;一般不不超过8个超过8个反而会降低性能一般4个 1-2个也可以&#xff09; netstat -antp | grep 80 查端口号 *1、events块&#xff1a;* 配置影响ngi…

微软Win11 24H2七月更新补丁KB5040435发布!附下载

系统之家于7月10日发出最新报道&#xff0c;微软为Win11用户发布了24H2版本七月的最新更新补丁KB5040435。用户升级系统后&#xff0c;会发现版本号升至 26100.1150。此次更新针对远程身份验证拨入用户服务(RADIUS)协议与 MD5冲突等问题进行修复。接下来跟随小编看看此次更新的…