数据结构——绪论/线性表

news/2024/11/23 5:41:56/

文章目录

    • **一 基本概念**
    • **二 算法和算法评价**
    • **三 线性表的定义和基本操作**
    • **四 线性表的顺序表示**
      • **1 定义**
      • **2 基本操作**
    • **五 线性表的链式表示**
      • **1 单链表的定义**
      • **2 单链表的基本操作实现**
      • **3 双链表**
      • **4 循环链表**
      • **5 静态链表**

一 基本概念

数据类型：（1）原子类型：不可再分的，如int，char

（2）结构类型：可以再分解若若干成分，如

struct lnode
{int a;char C;
}LNODE;

（3）抽象数据类型：抽象数据组织及与之相关的操作，如栈（Stack）就是一种抽象数据类型。栈是一种具有后进先出（Last-In-First-Out，LIFO）特性的数据结构，它支持两个基本操作：压栈（Push）将元素添加到栈顶，弹栈（Pop）将栈顶元素移除并返回。

算法：对特定问题求解步骤的一种描述，是指令的有限序列

一个算法的设计取决于所选定的逻辑结构；算法的实现依赖于所采用的存储结构

数据结构分为两类：

（1）逻辑结构

数据元素间的逻辑关系

在这里插入图片描述

（2）存储结构

数据结构在计算机中的表示，又称物理结构

主要有顺序存储，链式存储，索引存储和散列（哈希）存储

散列存储：根据元素的关键字（散列函数）直接计算元素的存储地址

在这里插入图片描述

二 算法和算法评价

算法的特性：有穷性，确定性，可行性，输入，输出

一个好的算法：可读性，正确性，健壮性，高效率和低存储量

算法效率的度量：

（1）时间复杂度

通常考虑最坏情况

加法规则：以最大的为准

乘法规则：直接相乘

常见的时间复杂度

O(1)<O(Log2N)<O(N)<O(N*Log2N)<O(N2)<O(N3)<O(2N)<O(N!)<O(Nn)

（2）空间复杂度

算法所耗费的空间，一般是辅助空间

算法原地工作即O（1）

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

线性表是具有相同数据类型的n个元素的有限序列，是一种逻辑结构

即逻辑上每个数据是相邻的；每个元素只有一个直接前驱和直接后继

特点：个数有限，逻辑上的顺序性，每个元素都是单个数据元素，且类型相同

线性表的主要操作

Initlist(&L);       \\初始化表
Length(L);          \\求表长
LocateELem(L,e);    \\按值查找
GetElem(L，i);      \\按位查找
ListInsert(&L,i,e); \\插入操作
Listdelete(&L.i,&e);\\删除操作
PrintList(L);       \\输出操作
Empty(L);           \\判空操作
DestroyList(&L);    \\销毁操作

采用的存储结构不同，存储结构也不同，算法的实现也不同；&在C++中表示引用调用

四 线性表的顺序表示

1 定义

线性表的顺序存储又称顺序表，用一组地址连续的存储单元依次存储线性表中的元素，常称为数组

#define MaxSize 50
typedef struct
{ElemType data[MaxSize];int length;
}Sqlist;

空间的静态分配：事先固定大小，空间占满时会发生溢出

动态分配：程序执行过程中通过动态存储分配语句分配的，占满后就开辟一块新的空间，不需要一次性划分

#define InitSize 100
typedef struct
{Elemtype *data;         \\指示动态分配数组的指针int maxsize,length;     \\数组的最大容量和当前个数
}seqlist;L.data = (elemtype)malloc(sizeof(elemtypr)*Initsize);    \\C的动态分配
L.data = new elemtype(Initsize);                         \\C++的动态分配\\动态分配不是链表，只是运行时决定分配的空间大小

顺序表的特点：随机访问，存储密度高，物理上相邻，插入删除需要移动大量数据

2 基本操作

（1）插入

bool ListInsert(sqlist &L,int i , elemtype e)  \\位置i插入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--)L.data[j]=L.data[j-1];             \\逐个移动数据直到位置i  L.data[i-1]=e;                            \\插入eL.length++;return true;                  
}

时间复杂度O（n）

（2）删除

bool Listdelete(sqlist &L,int i , elemtype e)  \\位置i删除并返回为e
{ if(i < 1 || i > L.length)                 \\i有效return false;e = L.data[i-1];for(int j =i;j<L.length;j++)L.data[j-1]=L.data[j];L.length--;return true;
}

（3）按值查找

int LocateElem(sqlist &L,Elemtype e)
{ int i;for(i=0;i<L.length;i++){if(L.data == e)return i;       \\返回下标   }return -1;              \\表示查找失败
}

五 线性表的链式表示

1 单链表的定义

typedef struct Lnode
{ELemtype data;          \\数据struct Lnode * next;    \\指针,指向下一个节点
}Lnode, *Linklist;

解决了需要大量连续存储单元的缺点，但是也存在浪费空间；是非随机存取的，必须从头开始遍历查找

用头指针来标识一个单链表

在第一个节点之前加一个头结点，不存入信息，方便操作；不管带不带头结点，头指针L都指向第一个结点

在这里插入图片描述

2 单链表的基本操作实现

（1）头插法建立单链表

Linklist List_Headinsert(Linklist &L)
{ Lnode *s;int x;L=(Linklist)malloc(sizeof(Lnode));   \\创建头结点L->next = NULL;                      \\初始为空结点scanf("%d",&x);while(x!=9999){s = (Lnode *)malloc(sizeof(Lnode));    \\Lnode* 和 Linklist 是一样的  都是创建新结点s->data =x;s->next = L->next;L->next =s;scanf("%d",x);}return L;
}

在这里插入图片描述

（2）尾插法建立单链表

Linklist List_Tailinsert(Linklist &L)
{ int x;L=(Linklist)malloc(sizeof(Lnode));   \\创建头结点Lnode *s ，*r =L;                       scanf("%d",&x);while(x!=9999){s = (Lnode *)malloc(sizeof(Lnode));s->data =x;r->next =s;r =s ;scanf("%d",x);}r->next=NULL;return L;
}

在这里插入图片描述

（3）按序号查找结点

Lnode *Getelem(Linklist &L,int i)
{if(i<1)return NULL;int j =i;Lnode *p=L->next;while(p!=NULL&&j<i){p = p->next;j++;}return p;
}

（4）按值查找表结点

Lnode *Locateelem(Linklist &L,elemtype e)
{Lnode *p=L->next;while(p!= NULL&&p->data!=e){p=p->next;}return p;
}

（5）插入结点

p=Getelem(L,i-1);
s->next=p->next;
p->next=s;\\对某一结点进行前插
s->next=p->next;
p->next=s;
temp = p->data;
p->data=s->data;
s->data=temp;

在这里插入图片描述

（6）删除结点

p=Getelem(L,i-1);
q=p->next;
p->next=q->next;
free(q);\\删除结点*p
q=p->next;
p->data=p->next->data;
p->next=q->next;
free(q);

在这里插入图片描述

3 双链表

typedef struct Dnode
{Elemtype data;struct Dnode * pri,*next;
}Dnode, *Dlinklist;

在这里插入图片描述

（1）插入操作

s->next=p->next;
p->next->pri=s;
s->pri =p;
p->next=s;

在这里插入图片描述

（2）删除操作

p->next=q->next;
q->next->pri=p;c
free(q);

在这里插入图片描述

4 循环链表

（1）循环单链表

即最后个结点的指针指向头结点

在这里插入图片描述

（2）循环双链表

空表时，pri和next都指向L

在这里插入图片描述

5 静态链表

借助数组来面熟线性表的链式存储结构，这里的指针是结点的相对地址（数组下标），要预先分配空间

#define Maxsize 100
typedef struct
{Elemtype data;int next;
}SLinklist[Maxsize];

以next==-1作为结束

在这里插入图片描述

6 顺序表与链表的比较

顺序表链表
存取方式顺序、随机顺序
逻辑/物理结构物理上也相邻物理上不一定相邻
查找/插入和删除时间复杂度O(N)或者O(log2n)O（n）
空间分配静态会溢出，动态效率低需要时动态申请，操作灵活

http://www.ppmy.cn/news/287378.html

相关文章

华为采取饥渴营销很无奈，三星和苹果成为最大赢家

华为采取饥渴营销很无奈，三星和苹果成为最大赢家

华为近期推出的mateX2上线销售仅1分钟就售罄&#xff0c;而无良商家更是加价2万出售这款手机&#xff0c;被人质疑饥渴营销&#xff0c;导致如此结果实属无奈&#xff0c;它如此做让三星和苹果成为最大赢家。 在折叠手机市场&#xff0c;三星取得绝对领先优势&#xff0c;统计数…
阅读更多...
三星PM981/PM981a硬盘安装黑苹果(第六版)

三星PM981/PM981a硬盘安装黑苹果(第六版)

三星PM981/PM981a硬盘安装黑苹果 问题描述解决思路思路一思路二 安装方法方法一——打补丁方法二——备份还原方法三——分区拷贝 注意事项下次更新出详细教程&#xff0c;教程请参见我的同名博客(第五版) 使用前请先完整阅读本文章&#xff0c;否则可能导致安装失败 问题描述 …
阅读更多...
创新能力哪家强？三星Note8 VS. 苹果iPhone X

创新能力哪家强？三星Note8 VS. 苹果iPhone X

火星撞地球&#xff0c;手机圈上演年度大戏 要说最近手机圈的年度大戏&#xff0c;莫过于两大新旗舰——苹果iPhone X和三星Note8的“火星撞地球”了。说来也巧&#xff0c;苹果iPhone X和三星Note8的国行版&#xff0c;居然不约而同都选择了在北京时间9月13日发布。两大老对手…
阅读更多...
三星苹果诺基亚齐推廉价智能机 抢食中印市场

三星苹果诺基亚齐推廉价智能机 抢食中印市场

网易科技讯 8月25日消息&#xff0c;据路透社报道&#xff0c;全球最大的两家手机厂商&#xff0c;诺基亚和三星24日同时发布了最新廉价版智能手机&#xff0c;以期抵御苹果即将发布的廉价iPhone 4的冲击。 消息人士本周向路透社透露&#xff0c;苹果公司不久将推出低成本的廉…
阅读更多...
三星PM981(a)硬盘安装黑苹果(第五版)

三星PM981(a)硬盘安装黑苹果(第五版)

三星PM981/PM981a硬盘安装黑苹果 使用前请先完整阅读本文章&#xff0c;否则可能导致安装失败 PM981 1.判断硬盘厂商&#xff0c;前往官网查看品牌机驱动下载页微码一栏是否有SSD新固件&#xff0c;有则尝试升级 2.在/EFI/clover/kexts/other/目录下添加NVMeFix.kext&#xff0…
阅读更多...
扫雷小游戏 2.0版本

扫雷小游戏 2.0版本

游戏名称&#xff1a; 扫雷小游戏2.0 游戏操作&#xff1a; 详情请见&#xff1a;主页->专栏->小游戏->扫雷小游戏1.0->游戏操作 创作背景&#xff1a; 昨天才说大概要8.21之后更新&#xff0c;但由于我提高组模拟赛爆0 ak了入门组模拟赛&#xff0c;所以 提前…
阅读更多...
Zikko上市同时搭载HDMI2.1和2.5GbE新款雷电4扩展坞

Zikko上市同时搭载HDMI2.1和2.5GbE新款雷电4扩展坞

近日&#xff0c;专注Thunderbolt技术产品的Zikko&#xff08;即刻&#xff09;推出新款雷电4扩展坞&#xff0c;它拥有高达11个数据端口&#xff0c;搭载英特尔8000系列认证芯片&#xff08;代号JHL8440&#xff09;&#xff0c;支持40Gbps高速传输&#xff0c;并带有96W PD快…
阅读更多...
MTK android11 替换默认壁纸库

MTK android11 替换默认壁纸库

MTK android11默认的壁纸库&#xff0c;路径如下&#xff1a; \vendor\mediatek\proprietary\packages\apps\WallpaperPicker\res\drawable-nodpi 修改默认壁纸&#xff0c;路径如下&#xff1a; \frameworks\base\core\res\res\drawable-nodpi\default_wallpaper.png
阅读更多...
最新文章

Copyright @ 2022~2023