当前位置： 首页 > news >正文

线性表（1）

news 2024/10/28 19:44:10

线性表

1.线性表的定义：线性表是由相同数据类型的n个数据元素组成的有限序列。

2.线性表的特点：数据元素之间有线性关系，每个元素有唯一的位序。

3.线性表的存储：线性表可以采用数组、链表等存储结构。

线性表的基本操作

1.初始化：用于创建一个空的线性表。 2.销毁：用于销毁一个已存在的线性表，释放内存空间。 3.插入：在线性表中指定位置插入一个或多个元素。 4.删除：从线性表中删除一个或多个元素。 5.查找：按值查找或按位查找线性表中的元素。 6.其他操作：如获取线性表长度、打印线性表元素、判断线性表是否为空。

基本操作的重要性

1.方便使用：提供易用的函数封装数据结构的基本操作。

2.避免重复工作：封装基本操作可以重复使用代码。

3.理解意义：思考基本操作的意义，有助于更深入理解数据结构。

线性表的逻辑结构和存储结构

1.逻辑结构：线性表的逻辑结构是一条线的结构，数据元素之间有前后关系。

2.存储结构：线性表可以采用数组、链表等存储结构。

3.位序：数据元素在线性表中的位置，位序从1开始，数组下标从0开始。

顺序表

一、顺序表定义与特点： 顺序表是线性表的一种实现方式，通过顺序存储实现。其主要特点包括随机访问、存储密度高、拓展容量和插入删除操作不方便等。

二、静态分配实现： 静态分配实现顺序表时，需要定义最大长度，使用结构体存储数据元素和长度信息。当数组存满时，无法继续扩展。

三、动态分配实现： 动态分配实现顺序表时，可以通过malloc函数动态申请内存空间，使用结构体存储指针、最大容量和长度信息。动态分配方式可以克服静态分配容量固定的问题，但拓展容量仍有一定时间开销。

在静态分配方式中，如果刚开始就声明一个很大的内存空间，可能会浪费内存资源。在动态分配方式中，虽然可以克服容量固定的问题，但拓展容量仍有一定困难，时间开销较大。因此需要根据实际需求选择合适的实现方式。

静态分配的实现 

//顺序表 静态分配
#include<stdio.h>
#define MaxSize 10
#define ElemType int
typedef struct {ElemType data[MaxSize];int length;
}SqList;
//初始化
void InitList(SqList L)
{for (int i = 0; i < MaxSize; i++){L.data[i] = 0;}L.length = 0;
}
//插入
bool ListInsert(SqList &L, int i, int e)
{if (i > L.length + 1 || i < 1)return false;if (L.length >= MaxSize)return false;for (int k = L.length - 1; k <= i - 1; k--){L.data[k + 1] = L.data[k];}L.data[i - 1] = e;L.length++;return true;}
//删除
bool ListDelete(SqList &L, int i, int &e)
{if (i < 1 || i > L.length)return false;if (L.length > MaxSize)return false;e = L.data[i - 1];for (int k = i; k < L.length ; k++){L.data[k - 1] = L.data[k];}L.length--;return true;
}
//按位查找
ElemType GetElem(SqList L, int i)
{return L.data[i - 1];
}
//按值查找
int LocateElem(SqList L, ElemType e)
{for (int i = 0; i < L.length; i++){if (L.data[i] == e)return i + 1;}return 0;
}

动态分配的定义与初始化 

#include<stdio.h>
#include<malloc.h>
#define InitSize 10
#define ElemType inttypedef struct {ElemType *data;int MaxSize;int length;
}SeqList;void InitList(SeqList &L)
{L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);L.length = 0;L.MaxSize = InitSize;
}

链表

单链表

1. 单链表是线性表的一种链式存储结构，每个结点包括数据域和指针域。

2. 单链表可随机存取，存储密度高，不要求大片连续空间，改变容量方便。

3. 用代码定义单链表时，需使用struct关键字定义结点，并用malloc函数申请内存空间。

4. 带头结点的单链表写代码更方便，头结点不存储数据，主要用于操作方便。

5. 不带头结点的单链表在内存管理、处理空表和非空表时需要用不同的代码逻辑。

#include<stdio.h>
#include<malloc.h>
#define MaxSize 10
#define ElemType int
typedef struct LNode {int data;struct LNode *next;
}LNode,*LinkList;//带头结点
bool InitList(LinkList &L)
{L = (LNode*)malloc(sizeof(LNode));L->next = NULL;return true;
}
//长度
int Length(LinkList L)
{int length = 0;LNode *p = L;while (p->next != NULL){p = p->next;length++;}return length;
}
//按序号查找表结点
LNode *GetElem(LinkList L, int i)
{LNode *p = L;int flag = 0;while (p != NULL && flag < i){p = p->next;flag++;}return p;
}
//按值查找表结点
LNode *LocateElem(LinkList L, ElemType e)
{LNode *p = L->next;while (p != NULL && p->data != e){p = p->next;}return p;
}
//在第i个位上插入
bool ListInsert(LinkList &L, int i, ElemType e)
{//找到第i-1个结点int ret = 0;LNode *p = L;while (ret < i - 1 && p != NULL){ret++;p = p->next;}if (p == NULL)return false;LNode *s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return true;
}
//删除第i个结点
bool ListDelete(LinkList &L, int i, ElemType &e)
{int ret = 0;LNode *p = L;while (ret < i - 1 && p != NULL){ret++;p = p->next;}if (p == NULL || p->next == NULL)return false;LNode *q = p->next;e = q->data;p->next = q->next;free(q);return true;
}

头插法建立单链表

LinkList List_HeadInsert(LinkList &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;
}

头插法可以解决链表逆置的问题！ 

尾插法建立单链表 

LinkList List_TailInsert(LinkList &L)
{int x;L = (LNode*)malloc(sizeof(LNode));LNode *s, *tail = L;scanf("%d", &x);while (x != 9999){s = (LNode*)malloc(sizeof(LNode));s->data = x;s->next = tail->next;tail->next = s;tail = s;//tail指向尾结点scanf("%d", &x);}tail->next = NULL;return L;
}

双链表

1. 双链表可双向检索，插入和删除节点较方便，但存储密度略低。

2. 双链表的初始化需带头结点，方便操作。

3. 插入节点时需注意指针顺序，后插操作可实现按位序插入。

4. 删除节点时需小心处理指针关系，后删操作可实现便捷删除。

5. 双链表不可随机存取，只能用遍历方式实现按位查找和按值查找，时间复杂度为O(n)。

#include<stdio.h>
#include<malloc.h>
#define MaxSize 10
#define ElemType int
typedef struct DNode {ElemType data;struct DNode *prior, *next;
}DNode,*DLinklist;
//判空
bool Empty(DLinklist L) {if (L->next == NULL)return true;elsereturn false;
}
//p结点后插入s结点
bool InsertNextDNode(DNode *p, DNode *s) {if (p == NULL || s == NULL)return false;s->next = p->next;if (p->next != NULL)p->next->prior = s;s->prior = p;p->next = s;return true;
}
//删除p结点的后继结点
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;
}

循环链表 

1. 循环单链表：表尾结点的next指针指向头结点，形成循环。从一个结点出发可找到其他任何结点，时间复杂度为O(n)。

2. 循环双链表：表头结点的prior指向表尾结点，表尾结点的next指向头结点。双链表的插入和删除操作需特别注意指针的调整。

3. 遍历实现：可通过后向或前向遍历循环链表。

循环单链表

#define MaxSize 10
#define ElemType int
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;return true;
}
//判断是否为空
bool Empty(LinkList L) {if (L->next == L)return true;elsereturn false;
}
//判断是否为表尾结尾
bool isTail(LinkList L, LNode *p) {if (p->next == L)return true;elsereturn false;
}

循环双链表

#define MaxSize 10
#define ElemType inttypedef 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;L->next = L;return true;
}
//判断是否为空
bool Empty(DLinklist L) {if (L->next == L)return true;elsereturn false;
}
//判断是否为表尾结尾
bool isTail(DLinklist L, DNode *p) {if (p->next == L)return true;elsereturn false;
}
//在p结点后插入s结点
bool InsertNextDNode(DNode *p, DNode *s) {if (p == NULL || s == NULL)return false;s->next = p->next;p->next->prior = s;s->prior = p;p->next = s;return true;
}

静态链表

1. 静态链表是一种用数组实现的链表，各个结点在内存中连续存放。

2. 静态链表由头结点和一系列数据结点组成，每个数据结点包括数据和游标（指向下一个结点的数组下标）。

3. 初始化静态链表时，需将头结点的next设为特殊值（如-1），其他结点的next设为另一个特殊值（如-2）表示空闲。

4. 查找、插入和删除操作时，需从头结点开始遍历链表。插入操作需找到空闲结点并修改相关结点的next；删除操作需找到前驱结点并修改其next和被删除结点的数据。

5. 静态链表适用于不支持指针的低级语言或数据元素数量固定不变的场景，如操作系统的文件分配表FAT。

6. 静态链表用数组实现，具有增删操作不需要大量移动元素的优点，但缺点是不能随机存取，只能按顺序查找，且容量固定不可变。

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 1000
typedef struct 
{int Data;  //两个数据域 int Cur;   //一个是存储数据，另外一个就是游标（存储下一个元素的下标） 
}Component,StaticList[MaxSize];//Component是备用链表，StaticList是 静态链表。 void Init(StaticList Space)  //静态链表初始化。主要有两点：1.将Cur游标存储下一个结点的下标
{                            //2.最后一个结点的Cur游标存储第一个有数值的元素的下标。for(int i=0;i<MaxSize-1;i++) //space是静态链表，用循环将第i个结点的Cur游标赋值为i+1。{Space[i].Cur=i+1;}Space[MaxSize-2].Cur=0;  //最后一个空闲的结点Cur置为0，相当于指针置为NULL。Space[MaxSize-1].Cur=0;  //最后将最后一个结点的Cur游标初始化为0。先开始是空表所以为0，如果 //不是空表，那么此处就会记录第一个有数值元素的下标。
}int Malloc_StaticList(StaticList Space)  //申请一块空的内存区域 
{                            //因为第一个结点的Cur记录的是备用链表的第一个结点。           int Pos_Cur=Space[0].Cur;//除非这个链表满了，不然Pos_Cur就是一块空的内存区域。 if(Space[0].Cur)         //如果Space[0].Cur==0那么说明，链表满了放不了了。Space[0].Cur=Space[Pos_Cur].Cur;return Pos_Cur;          //如果Space[0]！=0，那么 Loc_Cur这个下标的结点是空的。//然后Space[0]是第一个结点，要记录备用链表第一个结点。
}	                         //而现在Pos_Cur这个结点要被用了，他就不是备用链表中的一部分了。 //所以此时Space[0].Cur就得换，根据性质备用结点的Cur存储的是下一 //个空结点位置。//综上所述Space[0].Cur值修改为Pos_Cur的下一个结点.,                             //（即Space[Pos_Cur].Cur）。 //查询链表中共有多少个结点 
int ListLength(StaticList Space)
{int count=0;for(int i=Space[MaxSize-1].Cur;i!=0;i=Space[i].Cur) //循环算出目前链表中有多少个接待你 {count++;}return count;
} //在Space这个静态链表中，插入一个结点，这个结点插在Node这个结点之前。 
bool ListInsert(StaticList Space,int Node,int Data)
{    if(Node<1||Node>ListLength(Space)+1)  //解释一下这个函数{                                     //如果Node==2,那就是在第2个结点前插入一个结点                           //也可以说在第一个结点后面插入一个结点。 return false;                     //条件判断：首先Node从1开始。如果 //Node==ListLength+1，ListLength是链表长度 }                                     //假设链表长度为x，那么说明Node插在第x个结点后面。 //这就是极限了，不能再大了，因为长度为x，没有第x+1 //个结点了。所以无法满足这俩条件，都没法插入.      int New_Cur=Malloc_StaticList(Space);//申请一块区域if(New_Cur) //如果New_Cur！=0，那么说明找到一个空闲结点。 {Space[New_Cur].Data=Data;//先把数据给存进去int Cur=MaxSize-1;       //利用最后一个结点定位首元结点。 for(int i=1;i<=Node-1;i++)//通过循环Cur，来找到Node前面一个结点。 {Cur=Space[Cur].Cur;}                        //循环完之后Cur指的是Node前面那个结点的指针，指向Node。 Space[New_Cur].Cur=Space[Cur].Cur;//新的结点指针通过Cur指向Node。 Space[Cur].Cur=New_Cur;         //然后Node上一个结点的Cur指向新结点，修改成New_Cur。 return true;}return false;//到了这一步都还没有return true的话，说明插入失败 
}                                                //在下标为number的结点，回收成为备用链表的一部分										         
void Free_StaticList(StaticList Space,int Number)
{Space[Number].Cur=Space[0].Cur;  //下标为Numbe的结点，Cur指向备用链表的第一个结点 Space[0].Cur=Number;             //第一个结点的Cur指向Number，这样Number就变成了备用链表 //中的第一个结点了。 
} //删除第k个这个下标位置的结点 
bool Delete_Static(StaticList Space,int k)
{if(k<1||k>ListLength(Space)) //和上面的if判断相似但有点不同，这里是删除第k个结点{                            //k肯定得k>=1&&k<=ListLengthreturn false;} //先找到Pos这个点吧int Cur=MaxSize-1;          //通过最后一个结点找到首元结点，再不断通过Cur遍历for(int i=1;i<=k-1;i++){Cur=Space[Cur].Cur;}                        //这个循环跟之前的一样都是找到第k个结点前一个结点下标位置。int k_Cur=Space[Cur].Cur;//找出k结点下标位置。 Space[Cur].Cur=Space[k_Cur].Cur;//k前面节点Cur直接指向k后面的结点 Free_StaticList(Space,k_Cur);//Free掉以k_Cur为下标的结点。 } 
void PrintList(StaticList Space) //通过最后一个结点定位首元节点再不断遍历 
{for(int i=Space[MaxSize-1].Cur;i!=0;i=Space[i].Cur){printf("%d ",Space[i].Data);}printf("\n");
}

http://www.mrgr.cn/news/60493.html

相关文章：

  • Android配置，build.gradle修改的坑
  • 关于嵌入式学习的一些短浅经验
  • Linux：编辑器Vim和Makefile
  • 传输层UDP
  • QT 机器视觉 1.相机类型
  • 6.1 创建gdt 表（1）
  • 2024年13个热门AI工具：涵盖思维导图、对话助理、绘画提示、批量抠图、翻译、音乐生成、文案撰写等功能
  • 安卓早期apk兼容性适配之内存读写
  • 等长运动：健身新概念，轻松提升肌肉力量
  • 目前市场主流的不同室内定位效果对比
  • IO--多线程（条件变量）
  • 小白如何成为编程高手？
  • 云渲染怎么实现网络连接的方法？一文解析
  • ssm005基于SSM框架的购物商城系统的开发与实现(论文+源码)_kaic
  • 雷池社区版OPEN API使用教程
  • WebRTC VAD 详解与代码示例
  • 雷池社区版中升级雷池遇到问题
  • 【云原生】云原生与DevOps的结合：提升软件开发与交付的效率
  • nacos安装与配置
  • 全网最简单的Java设计模式【九】原型模式深入解析
  • 装饰器模式详解：动态扩展对象功能的优雅解决方案
  • 【无标题】 text = text.encode(“utf-8“)
  • python multiprocessing lock锁在相同父进程ID起作用
  • 二分查找题目：二分查找
  • 【C++】继承与模板
  • vLLM推理部署Qwen2.5