• 王道数据结构2（线性表）

    线性表

    一、线性表的概念

    （一）线性表的定义

    1. 线性表具有相同数据类型的n个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为L=(a1,a2,…ai，ai+1,…an)
    2. ① 各个元素所占的存储空间是一样的
      ②有限序列，所有整数不是线性表
      ③属于逻辑结构
    3. 表头、表尾
    4. 除了第一个元素以外，其余元素都可以找到它的直接前驱（有且只有一个）；除最后一个元素外，其他元素都可以找到它的直接后继（有且只有一个）。

    （二）线性表的基本操作

    （1）基础

    • 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个位置的元素的值。

    （2）其他常用操作：

    • Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
    • PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
    • Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

    二、顺序表

    （一）定义

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

    typedef struct{
   int num;
   int people;
}Customer;

    • 1
    • 2
    • 3
    • 4
    1. 设线性表第一个元素的存放位置是LOC(L)，各个元素的地址：LOC(L)+(n-1)*数据元素的大小
    #define MaxSize 10 //定义最大长度
typedef struct{
ElemType data[MaxSize]; //用静态的“数组”存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义（静态分配方式）

    • 1
    • 2
    • 3
    • 4
    • 5
    1. 给各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)

    （二）实现

    1. 在这里插入图片描述
    2. 顺序表的实现——静态分配
     #define MaxSize10 、 //定义最大长度
 typedef struct{ 
     ElemTypedata[MaxSize];//用静态的“数组”存放数据元素
     intlength;//顺序表的当前长度
}SqList;//顺序表的类型定义

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    动态分配空间，利用malloc函数返回一个指针，需要强制转型为你定义的数据元素类型指针

    L.data=(ElemType*)malloc(sizeof(ElemType)* InitSize);

    • 1

    （三）特点

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

    （四）顺序表的插入和删除

    1. 插入

    （1） ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
    （2）结构：用静态分配方式实现的顺序表

     #define MaxSize10 、 //定义最大长度
 typedef struct{ 
     ElemTypedata[MaxSize];//用静态的“数组”存放数据元素
     intlength;//顺序表的当前长度
}SqList;//顺序表的类型定义

    • 1
    • 2
    • 3
    • 4
    • 5
    /* 顺序表插入操作: 顺序表的第i(1~L.length)个位置插入新元素e 若i的位置不合法，返回false，否则，将顺序表的第i个元素及之后所有元素后移一位 空出第i个位置，将新元素e插入,顺序表长度加1. */
bool ListInsert(SqList& L, int i, ElemType e) { 
    if (i<1 || i>L.length+1) {  //判断插入的位置是否合法
        return false;
    }
    if (L.length >= L.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++;
    //cout << L.length << " zhi:" << L.data[i - 1] << endl;
    return true;
}
int main(){
 SqList L;
 Initlist(L);
 ……
 ListInsert(L,3,3);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    注意：① 这里要求是在第三个位置插入3，其实是在下标为2的位置，存入3，下标为≥3的位置后移。
    ② 注意插入的位置合法性的判定

    （3）时间复杂度：
    ① 最好情况：插入到表尾，不需要移动其他数据，循环0次，最好时间复杂度=O(1)
    ② 最坏情况：新元素插入到表头，需要将原有的n个元素全都向后移动，i=1，循环n次，最坏时间复杂度=O(n)
    ③ 平均情况：插入到任何一个元素位置概率都相同，循环次数：np+(n-1)p+(n-2)p+…+p=n/2 ,即O(n)

    2. 删除

    （1）代码

    /* 删除操作: 删除顺序表中第i个位置的元素，若成功返回true，并将被删除元素用引用 变量e返回，否则返回false */
bool ListDetele(SqList& L, int i, ElemType &e) { 
    if (i<1 || i>L.length) {  //判断删除的位置是否合法
        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--;               //线性表长度减1
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    注意：e、L使用引用型
    （2）时间复杂度
    ① 最好情况：删除表尾元素，不需要移动其他数据，循环0次，最好时间复杂度=O(1)
    ② 最坏情况：删除表头元素，需要将后序的n-1个元素全都向前移动，i=1，循环n-1次，最坏时间复杂度=O(n-1)=O(n)
    ③ 平均情况：插入到任何一个元素位置概率都相同，循环次数：np+(n-1)p+(n-2)p+…+p=n/2 ,即O(n)

    三、单链表

    (一) 结构及定义

    1. 定义一个单链表
    struct LNode{ 
    ElemType data;          
  struct LNode *next;
}; 

    • 1
    • 2
    • 3
    • 4
    1. 使用typedef将结构重命名
    typedef struct LNode{ 
    ElemType data;          
  struct LNode *next;
}SqList; 
struct LNode *p=(struct LNode*)malloc(sizeof(struct LNode));
SqList *p=(SqList*)malloc(sizeof(SqList));
//增加一个新的结点，在内存中申请一个结点所需的空间，并用指针p指向这个结点。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    1. 注意
    typedef struct LNode{ 
    ElemType data;          
  struct LNode *next;
}LNode,*LinkList;
LNode *GetElem(LinkList L,int i){} 

    • 1
    • 2
    • 3
    • 4
    • 5

    LNode *L=LinkList L,但是LinkList L强调这是一个单链表，LNode *L强调这返回的是一个结点。

    (二) 建立

    1. 不带头结点的单链表

    （1）建立并且初始化
    typedef struct LNode{ 
    ElemType data;          
  struct LNode *next;
}LNode,*LinkList;
//初始化一个空的单链表
bool InitList(LinkList &L){
  L=NULL;//防止出现脏数据
  return true;
}
//判断是否为空
bool Empty(LinkList L){
   if(L==NULL)
     return true;
   else
     return false;
}
void test(){
 LinkList L;//声明一个指向单链表的指针
 InitList(L);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    （2）按位序插入（不带头结点）
    bool ListInsert(LinkList &L,int i, ElemType e)
{
    if (i<1)
        return false;
    if(i==1){
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        return true;
    }   //不带头结点，需要专门针对插入第一个结点进行讨论
     LNode *p;//指针p指向当前扫描的节点
     // int j=0；//当前p指向的是第几个节点
     int j=1；//当前p指向的是第几个节点//带头结点为j=0
     p=L;//L指向头结点，头结点是第0个节点
     while (p!=NULL && j<i-1) //循环找到第i-1个结点
    {
        p=p->next;
        j++;
}
    if (p==NULL){
        return false;                          InsertNextNode(p,4) // 引用插入4的函数
    }
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s; // 将节点s连接到p之后
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    （3）后插操作
    （4）删除操作
    （5）建立一个表

    2. 带头结点的单链表

    （1）建立并且初始化
    typedef struct LNode{ 
    ElemType data;          
  struct LNode *next;
}LNode,*LinkList;
//初始化一个空的单链表
bool InitList(LinkList &L){
  L=(LNode *)malloc(sizeof(LNode));//分配一个头结点
  if (L==NULL)//防止内存不足
     return faslse;
  L->next=NULL;//头结点以后还没有数据
  return true;
}
//判断是否为空
bool Empty(LinkList L){
   if(L->next==NULL)
     return true;//是空的
   else
     return false;
}
void test(){
 LinkList L;//声明一个指向单链表的指针
 InitList(L);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    （2）按位序插入（头结点）
    typedef struct LNode{
     ElemType data; // 每个节点存放一个数据元素
     struct LNode *next;  // 指向下一个节点
}LNode,*LinkList；
//按位序插入 （带头结点）
//在第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个节点              LNode * GetElem(LinkList L,int i)
    while (p!=NULL && j<i-1) //循环找到第i-1个结点
    {                                                7. 按位查找
        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; // 将节点s连接到p之后
    return true;
}
int main()
{    LinkList L;
     ListInsert(L,6,8);
     return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    最坏情况：O(n)

    （3）后插操作
    （4）删除操作
    （5）按位查找
    bool ListInsert(LinkList &L,int i, ElemType e)
{
    if (i<0)
        returnB=NULL;
    LNode *p;//指针p指向当前扫描的节点
    int j=0；//当前p指向的是第几个节点
    p=L;//L指向头结点，头结点是第0个节点             
    while (p!=NULL && j<i) //循环找到第i-1个结点
    {                                                
        p=p->next;
        j++;
}
 return p;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    （6）按值查找
    LNode *Locate(LinkList L,int ElemType e)
{  LNode *p=L->next;
//从第一个结点开始查找数据域为e的结点
while(p!=NULL && p->data!=e)
  p=p->next;
return p;
  }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    （7）表长
    //单链表  计算单链表长度
int count(LinkList& L)
{
	if (L->next == NULL)
		return 0;
	int count=1;
	LNode *p=L->next;
	while (p->next)//注意是p指向空，而不是p为空
	{
		p = p->next; count++;
	}
	return count;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    （8）建立一个表

    尾插法，头插法
    具体代码见：代码总结

  • 相关阅读:
    前端性能优化总结
    值类型与引用类型
    深度解析：Stable Diffusion中negative prompt是如何作用的？
    《Bootstrap 4 Web设计与开发实战》简介
    python制作ppt
    使用spring cloud config来统一管理配置文件
    云服务器最佳实践-Linux云服务器SSH登录的安全加固
    【PHPWrod】使用PHPWord导出word文档
    操作系统复习：线程
    Stable Diffusion6
  • 原文地址：https://blog.csdn.net/qq_46126118/article/details/126875123