数据结构第二章

2024-07-01 01:08:55| 来源: 网络整理| 查看: 265

数据结构第二章——线性表的定义和特点线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列

其中数据元素的个数n定义为表的长度当n = 0时称为空表

线性表的逻辑特征：

在非空的线性表，有且仅有一个开始结点a1,他没有直接前驱，儿仅有一个直接后继a2有且仅有一个终端结点an,它没有直接后继，而仅有一个直接前驱an-1其余的内部结点ai(2 a >> b; swap(a, b); cout next; while(p){ length++; p = p->next; } return length; } 取值——取单链表中第i个元素的内容

算法步骤：

从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p = L -> nextj做计数器，累计当前扫描过的结点数，j初值为1当p 指向扫描到的下一结点时，计数器j 加1当j == i时，p所指的结点就是要找的第i个结点

算法实现

int getElem_L(LinkList L, int i, int &e){ //获取线性表L中的某个元素的内容，通过变量e返回 LinkList p; p = L->next; j = 1; while(p&&j next; ++j; } if(!p || j > i) return ERROR;//第i个元素不存在 e = p->data; return e; } 按值查找——根据指定数据获取该数据所在的位置（地址）

算法步骤：

从第一个结点起，依次和e相比较如果找到一个其值与e相等的数据元素，则返回其链表中的位置或地址如果查边整个链表都没找到其值和e相等的元素，则返回0或NULL Lnode *LocateElem_L(LinkList L, int e){ //在线性表L中查找值为e的数据元素 //找到，则返回L中值为e的数据元素的地址，查找失败就返回NULL LinkList L; p = L->next; while(p && p->data != e){ p = p->next; } return p; } 按值查找——根据指定数据获取数据位置序号 //在线性表L中查找值为e的数据元素的位置序号 int LocateElem_L(LinkList L, int e){ //返回L中值为e的数据元素的位置序号,查找失败返回0 LinkList p; p = L->next; j = 1; while(p && p->data != e){ p = p->next; j++; } if(p) return j; else return 0; } 插入——在第i个结点前插入值为e的新结点

算法步骤：

首先找到ai-1的存储位置p生成数据域为e的新结点s插入新结点新结点的指针域指向ai结点ai-1的指针域指向新结点 //在L中的第i个元素之前插入数据元素e int ListInsert_L(LinkList &L, int i, int e){ LinkList p; int j = 0; while(p && j < j - 1){ p = p->next; ++j; } if(!p || j > i - 1) return ERROR; s = new LNode; s -> data = e; s -> next = p -> next; p -> next = s; return OK; } 删除——删除第i个结点

算法步骤

先找到第i-1个结点的存储位置p，保存要删除的ai的值令p->next指向ai+1释放结点ai的空间

算法描述

//将线性表L中的第i个数据元素删除 int ListDelete_L(LinkList &L, int i, int &e){ LinkList p, q; int j = 0; while(p -> next && j < i - 1){ p = p -> next; ++j; }//寻找第i个结点，并令p指向其前驱 if(!(p->next) || j > i - 1) return ERROR;//删除位置不正确 q = p -> next;//临时保存被删除结点的地址以备 p -> next = q -> next;//改变删除结点前驱结点的指针域 e = q -> data;//保存删除结点的数据域 delete q;//释放删除结点的空间你 return OK; } 建立单链表：头插法——元素在链表头部，也叫前插法 void CreateList_H(LinkList &L, int n){ L = new LNode; L->next = NULL;//先建立一个带头结点的单链表 for(int i = n; i > 0; --i){ p = new LNode;//生成结点p cin >> p->data;输入元素值 p->next = L -> next;//插入到表头 L->next = p; } }

建立单链表：尾插法——原数插入在链表尾部，也叫后插法

步骤

从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点初始时，r同L均指向头结点，每读入一个数据元素则申请一个新结点，将新结点插入到尾结点多厚，r指向新结点 void CreateList_R(LinkList &L, int n){ L = new LNode; L -> next = NULL; r = L;//尾插法r指向头结点 for(int i = 0; i < n; i++){ p = new LNode;//生成新结点，输入元素值 cin >> p -> data; p->next = NULL; r->next = p;//插入到表尾 r = p;//r指向新的尾结点 } } 循环链表：

是一种头尾详解的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）

优点

从表中任一结点出发均可找到表中其他结点。

注意

由于循环链表没有NULL指针，故设计遍历操作时，其中其终止条件就不再像非循环链表那样判断p或p->next是否为空，而是判断它们是否等于头指针

循环条件：

LinkList Connect(LinkList Ta,LinkList Tb){//假设Ta\tb都是非空的单循环链表 LinkList p; p = Ta -> next;//p存放表头结点 Ta -> next = Tb -> next -> next;//Tb表头连接Ta表尾 delete Tb -> next;//释放Tb表头结点 Tb->next = p;//修改指针 return Tb; } 双向链表

在单链表的每个结点在增加一个指向其直接前驱的指针域Prior，这样链表就形成了有两个方向不同的链，故称为双向链表

双向链表的结构可定义如下

typedef struct DuLNode{ Elemtype data; struct DiLNode *prior, *next; }DuLNode, *DuLinkList; 双向循环链表

和单链表的循环表类似，双向链表也可以有循环表

让头结点的前驱指针指向链表的最后一个结点让最后一个结点的后继指针指向头结点

双向链表结构的对称性（设指针p指向某一节点）

p -> prior ->next = p = p -> next -> prior

双向链表的插入 int ListInsert_DuL(DuLinkList &L, int i, int e){ //在带头结点的双向循环链表L中的第i个位置之前插入元素e if(!(p = GetElemP_DuL(L,i))) return ERROR; s = new DuLNode; s -> data = e; s -> prior = p -> prior; p -> prior -> next = s; s -> next = p; p -> prior = s; return OK } 双向链表的删除(时间复杂度O（n）) int ListDelete_Dul(DuLink &L, int i, int &e){ //删除带头结点的双向循环链表L的第i个元素,并用e返回 if（!( p = GetElemP_DuL(L,i))） return ERROR; e = p -> data; p -> prior -> next = p->next; p -> next -> prior = p -> prior free(p); return OK; } 单链表、循环链表和双向链表的时间效率比较

请添加图片描述

顺序表和链表的比较链式存储结构的优点：结点空间可以动态申请和释放数据元素的逻辑次序依靠结点的指针来表示，插入和删除时不需要移动数据元素链式存储结构的缺点：存储密度小，每个结点的指针域需额外占用存储空间，当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显然很大。链式存储结构是非随机存储结构。对任意结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度。

顺序表和链表的比较

线性表的应用线性表的合并假设利用两个线性表La和Lb分别表示两个结合A和B，现要求一个新的集合A∪B

La = (7, 5, 3, 11) Lb = (2, 6, 3) => La = (7, 5, 3, 11, 2, 6)

算法步骤

依次取出Lb中的每个元素，执行以下步骤在La中查找该元素如果找不到，则将其插入La的最后 void union(List &La, List Lb){ La_Len = ListLength(La); Lb_Len = ListLength(Lb); for(int i = 1; i < Lb_Len; i++){ GetElem(Lb,i,e); if(!LocateElem(La, e)) ListInsert(&La, ++La_Len, e); } } 有序表的合并已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素按值非递减有序排列

La = (1, 7, 8) Lb = (2, 4, 5, 6, 8, 10, 11) => Lc = (1, 2, 4, 6, 7, 8, 8, 10, 11)

算法步骤

创建一个空表Lc

依次从La或Lb中“摘取”元素值较小的节点插入到Lc表的最后，直至其中一个表变空位置

继续讲La或Lb其中一个表的剩余节点插入在Lc表的最后

void MergeList_Sq(SqList LA, SqList Lb, SqList &Lc){ pa = LA.elem;//指针pa和pb的初值分别指向两个表的第一个元素 pb = Lb.elem; Lc.length = LA.length + Lb.length;//新表长度为待合并两个表的长度之和 Lc.elem = new ElemType[Lc.length];//为合并后的新表分配一个数组空间 pc = LC.elem;//指针pc指向新表的第一个元素 pa_last = LA.elem + LA.length - 1;//指针pa_last指向LA表的最后一个元素 pb_last = Lb.elem + Lb.length - 1;//指针pb_last指向Lb表的最后一个元素 while(pa next; } else{ pc -> next = pb; pc = pb; pb = pb -> next; } } pc -> next = pa ? pa : pb;//插入剩余段 delete Lb;//释放Lb的头结点 }

ast指向LA表的最后一个元素 pb_last = Lb.elem + Lb.length - 1;//指针pb_last指向Lb表的最后一个元素 while(pa if(pa -> data data){ pc -> next = pa; pc = pa; pa = pa -> next; } else{ pc -> next = pb; pc = pb; pb = pb -> next; } } pc -> next = pa ? pa : pb;//插入剩余段 delete Lb;//释放Lb的头结点 }

【本文地址】

公司简介

联系我们

今日新闻

点击排行

实验室常用的仪器、试剂和: 说到实验室常用到的东西，主要就分为仪器、试剂和耗

不用再找了，全球10大实验: 01、赛默飞世尔科技（热电）Thermo Fisher Scientif

三代水柜的量产巅峰T-72坦: 作者：寞寒最近，西边闹腾挺大，本来小寞以为忙完这

通风柜跟实验室通风系统有: 说到通风柜跟实验室通风，不少人都纠结二者到底是不

集消毒杀菌、烘干收纳为一: 厨房是家里细菌较多的地方，潮湿的环境、没有完全密

实验室设备之全钢实验台如: 全钢实验台是实验室家具中较为重要的家具之一，很多

图片新闻

实验室药品柜的特性有哪些: 实验室药品柜是实验室家具的重要组成部分之一，主要

小学科学实验中有哪些教学: 计算机计算器一般打孔器打气筒仪器车显微镜

实验室各种仪器原理动图讲: 1.紫外分光光谱UV分析原理：吸收紫外光能量，引起分

高中化学常见仪器及实验装: 1、可加热仪器：2、计量仪器：（1）仪器A的名称：量

微生物操作主要设备和器具: 今天盘点一下微生物操作主要设备和器具，别嫌我啰嗦

浅谈通风柜使用基本常识: 　众所周知，通风柜功能中最主要的就是排气功能。在

数据结构第二章

数据结构第二章

今日新闻

点击排行

推荐新闻

图片新闻

专题文章