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

【伪代码】数据结构-期末复习 线性表

news 2025/4/27 8:43:11

目录

例1 矩阵相乘

线性表

2.1   线性表的类型定义

例2-1 求并集  LA=LA∪LB

例2-2 有序表归并

2. 2  线性表的顺序表示和实现

1．构造空表

2．插入

3．删除

4．定位

顺序表的优点：

顺序表的缺点：

例：交替扫描

2. 3  线性表的链式表示和实现

绪论

例1 矩阵相乘

两个方阵相乘Cn×n=An×n × Bn×n

for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {c[i][j] = 0;//把新矩阵中的每个数初始化为0，方便后续计算新矩阵每位的值for (k = 0; k < n; k++) {c[i][j] = c[i][j] + a[i][k] * b[k][j];//每次计算第i行第k位上的数和第j列第k位上的数的乘积并进行累加，得到新矩阵中第i行第j列上的数}}
}

线性表

2.1   线性表的类型定义

基本操作效果
InitList（&L）初始化线性表，将线性表设置为初始状态（比如长度置为 0 等）
DestroyList（&L）销毁线性表，释放线性表占用的内存空间等相关资源
ClearList（&L）置空表，也就是清除表中已有的元素，使表的长度变为 0，但保留线性表结构本身，以便后续继续使用
ListEmpty（L）判空表，判断线性表是否为空，若为空返回真（通常用 1 表示），否则返回假（通常用 0 表示）
ListLength（L）求表长，返回线性表中当前所包含元素的个数
GetElem（L，i，&e）取第 i 个元素，将线性表 L 中第 i 个位置的元素值赋给变量 e（通过传址 &e）
LocateElem（L，e，compare（））查找元素，根据给定的比较函数 compare，在线性表 L 中查找和元素 e 满足比较条件的元素位置（比如相等时的首次出现位置等）
PriorElem（L，cur_e，&pre_e）求前驱元素，在线性表 L 中查找元素 cur_e 的前驱元素，并将其值赋给 pre_e（通过传址 &pre_e），如果 cur_e 无前驱则按约定进行相应返回（比如返回特殊值表示无前驱等）
NextElem（L，cur_e，&next_e）求后继元素，在线性表 L 中查找元素 cur_e 的后继元素，并将其值赋给 next_e（通过传址 &next_e），如果 cur_e 无后继则按约定进行相应返回（比如返回特殊值表示无后继等）
ListInsert（&L，i，e）插入元素，将元素 e 插入到线性表 L 的第 i 个位置，插入后线性表长度会相应增加
ListDelete（&L，i，&e）删除元素，删除线性表 L 中第 i 个位置的元素，并将被删除的元素值赋给 e（通过传址 &e），删除后线性表长度会相应减少
ListTraverse（L，visit（））按照 visit 函数定义的方式遍历表，对线性表中的每个元素依次执行 visit 函数指向的操作

例2-1 求并集  LA=LA∪LB

void union(List& La, List Lb)
{int La_len = ListLength(La);int Lb_len = ListLength(Lb);int e;for (int i = 0; i < Lb_len; i++){GetEleme(Lb, i, e);//把Lb中 i下标的元素放到变量e中if (!LocatList(La, e, equal))//如果La中没有找到和e相同的数ListInsert(La, ++La_len, e);//把e元素插入到La的最后，La的长度再自加}}

例2-2 有序表归并

void MergeList(List La, List Lb, List& Lc)
{InitList(Lc);int La_len = ListLength(La);int Lb_len = ListLength(Lb);int i, j, k = 0;while (i <= La_len && j <= Lb_len)//把La和Lb中较小的一个先放入Lc中{GetEleme(La, i, ai);GetEleme(LB, j, Bj);if (ai <= bj){ListInsert(Lc, ++k, ai);++i;}else {ListInsert(Lc, ++k, bj);++j;}}while (i <= La_len)//Lb已经遍历完，剩下La部分直接插入Lc{GetEleme(La, i, ai);ListInsert(Lc, ++k, ai);++i;}while (j <= Lb_len)//La已经遍历完，剩下Lb部分直接插入Lc{GetEleme(Lb, i, bj);ListInsert(Lc, ++k, bj);++j;}}

2. 2  线性表的顺序表示和实现

顺序表(Sequential List) ：用顺序存储的线性表，即把线性表的结点按逻辑次序依次存放到一组地址连续的存储单元里 

顺序表通过 元素的存储顺序 反映逻辑关系

1．构造空表

typedef int Elemtype;//把int类型重命名为Elemtype,想要修改类型时只需改此处
const int maxsize = 100;
typedef struct//定义了一个名字叫Sqlist1的数据结构
{Elemtype elem[maxsize];int length;
}Sqlist1;void InitList(Sqlist1* L)//初始化线性表
{l->length = 0;
}

2．插入

在表的第i（0≤i≤n+1）个位置上，插入一个新结点x，使长度为n的线性表(a1,…,ai−1,ai,…,an)变为长度为n+l的线性表(a1,…,ai−1,x,ai,…,an)。

先将表中位置i～n上的结点全部后移一位以空出第i个位置，然后在该位置上插入新结点x，最后表长加1。  

注意：移动只能从后向前进行，即按n,n−1,…,i的次序进行。

int ListInsert(Sqlist* L, ElemType x, int i)//在顺序表L中的第i个位置插入x
{int j；if（L->n == maxsize）//判满{ cout << "表满，不能插入！（上溢）\n";//cout <<相当于print（），是打印的意思return -1; }if (i<0 || i> L->n + 1)//判位{cout << "非法插入位置\n"；return 0；}//插入操作for (j = L->n; j >= i; j--)L->elem[j] = L->elem[j - 1];//把i位置前的数后移L->elem[i - 1] = x;//插入x，第i个位置的下标是i-1L->n++;//表长加一return 1；//修改成功}

平均时间复杂度 

3．删除

将表的第i（1≤i≤n）个结点删去，使长度为n的线性表(a1,…,ai−1,ai,ai+1,…,an)变为长度为n−1的线性表(a1,…,ai−1,ai+1,…,an-1)。

先将表中位置i+1～n上的结点全部前移一位以填补删除操作造成的空缺。最后表长减1。 注意：移动只能从前向后进行，即按 i+1, i+2, …, n 的次序进行。

int ListDelete(Sqlist* L, int i)
{int j;if (L->length == 0)//判空cout << "表空，不能删除！（下溢）\n"；return -1；if (i<1 || i> L->n)//判合法删除cout << "非法删除位置！\n"；return 0；for (j = i + 1; j <= L->n; j++)//把i位置的后面的数依次前移，覆盖掉i位置的数L->elem[j - 2] = L->elem[j - 1];//为什么是L->elem[j-2] = L->elem[j-1];//“第i个位置”对应i-1下标，因为只有第一、二……个位置的说法（即i从1开始计数）,而下标是从0开始的//删掉“第i个位置”上的数，相当于用后一位数覆盖i位置上的数，后面剩下的数往前移 补空位//循环控制变量 j 需要从要删除元素位置的下一个【位置】开始，也就是 i + 1 开始，然后依次把 j 【位置】的元素往前移动一位，赋值给 j - 1 【位置】//因此j【位置】的数组【下标】是j-1，j-1【位置】的数组【下标】是j-2L->n--;//修改表长return 1;}

4．定位

求表L中第一个值为x的结点的序号，当不存在这种结点时结果为0。因此可从前向后比较各结点的值是否等于x。

int LocatElem(Sqlist* L, int x)
{int i；for (i = 1; i <= L->n；i++)if (elem[i - 1] == x) return i;//找到else return 0;//未找到
}

顺序表是线性表最简单的一种存储结构

顺序表的优点：

1  无需为表示逻辑关系而增加额外的存储空间(物理顺序可反映逻辑关系)；

2.可随机存取任一元素；i,    l.elem+  (i-1)sizeof(type)；p++;a[];

3.方法简单(各种高级语言都有数组类型)。

顺序表的缺点：

1.插入、删除会引起大量元素移动；

2.空间预(静态)分配，有浪费或不足问题。

例：交替扫描

已知顺序表结点值有正有负，使负值结点位于顺序表的前面部分，正值结点位于顺序表的后面部分。

方法1：对顺序表从前向后搜索（或称扫描），遇到正值结点就将它插入到表的后部（或从后向前搜索，遇到负值结点就将它插入到表的前部）。但顺序表上插入或删除不方便，要移动大量结点，效率不高。

方法2：由表的两端向中间交替扫描，即先从前向后扫描，找到一个值为正的结点，再从后向前扫描，找到一个值为负的结点，然后交换两者的内容。接着再从这两个位置开始继续进行同样的过程，直到两个扫描方向相遇，整个表扫描处理完毕。这样就避免了大量结点的移动问题。

void order(Sqlist *L)
{Elemtype x;
int i=0;
int j=L-> length-1;
while(i<j){while(i<j && L-> elem[i]<0) i++;//从前往后找正数while(i<j && L-> elem[j]>0) j--;//从后往前找负数if(i<j)//交换{ x= L-> elem[i];L-> elem[i] = L-> elem[j];L-> elem[j] = x;i++;j--;}}
}

2. 3  线性表的链式表示和实现

链表 (Linked List) ：用链式存储的线性表，即用一组任意的存储单元存储线性表的各个数据元素，相互间的逻辑关系(前趋或后继)通过附加指针表示；所有结点通过指针域链接在一起，构成一个链表。

  •  元素之间的逻辑关系通过附加指针表示；  
  • 结点可以连续，可以不连续；  
  • 结点的逻辑顺序与物理顺序可以不一致。

2.3.1  单链表

单链表(Singly Linked List)：每个结点有两部分信息：数据域，存放结点的值（内容）；指针域（亦称链域），存放结点后继的地址（或位置）。由于每个结点只有一个链域，故得名。

概念解释：

  • 空指针：不指向任何结点;
  • 头指针：单链表第一个结点的地址;
  •  单链表由头指针唯一确定；
  •  头指针具有标识单链表的作用；
  •  单链表常用头指针命名，如 head 表。
  • 头结点：单链表第一个结点前人为增加的结点，不存放数据。  作用：1、简化链表操作，统一空表与非空表  2、有时可将头结点看成0号结点

创建结点

typedef int ElemType;//给int类型起了一个别名ElemTypetypedef struct LNode{//结点中的两个成员变量
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//通过typedef为struct LNode结构体定义了两个别名
//一个是LNode（可以直接用来声明结构体变量，等同于使用struct LNode）
//另一个是*LinkList，LinkList通常用于表示指向链表头节点的指针类型LinkList head,p;// head 和 p 是两个指针变量，等价于LNode  *head ,  *p  ；

结点的动态分配与释放

//动态分配
p= new LNode;//方法一
p= (LinkList) malloc(sizeof(LNode));//方法二//malloc用于在堆内存中动态分配指定字节大小的内存空间
//它的参数sizeof(LNode) 计算了LNode 类型所占用的字节大小
//然后malloc 函数会在堆上找到一块对应大小的空闲内存块
//并返回指向这块内存起始地址的指针（该指针类型为void *，即无类型指针）
//由于需要将其赋值给LinkList 类型的指针p
//所以进行了强制类型转换(LinkList)//释放
delete p;//方法一
p=NULL;//方法二
free(p);//方法三

（1）插入(无头结点)

情况一：在空表上、首结点前插入

s= new LNode;//产生一个新节点
s->data = x;//把x赋到数值域中
s-> next = head;//把s和head（头结点）地址赋给s
head=s;//s就成了头结点

情况二：在中间结点、尾结点后插入

s=new LNode;
s->data = x;
s->next = p ->next;//先把后面的链子接上
p->next = s; //再链接前面的

注意指针修改顺序：先改变本身指针域，后改变指向本身的指针域。

（1）插入(有头结点)

情况一：插入到任意结点后

s = new LNode;
s -> data = x;
s-> next = p ->next;//先链接上后面
p->next = s;//再链接上前面

情况二：插入到第i结点前 

思路：

  1. 查找第 i-1个结点；
  2. 建立新结点；
  3. 修改第 i-1个结点和新结点的指针。

不需移动结点，只需修改有关指针 ；需从表头开始顺序查找插入位置

int insert(LinkList head, ElemType x, int i) {LinkList q, s;q = LocateElem(head, i - 1);//找到第i-1结点的地址if (q == 0) {//无第i-1位置的结点，即i<1 || i> (LinkList->length)cout << "非法插入位置！\n"；return 0；}s = new LNode;//生成新结点s->data = x;s->next = p->next;//新点的后继是原第i个点p->next = s; //原第i−1个点的后继是新点return 1;//插入成功
}

（1）等效插入（在*p之前 前插）

不用找前趋的前插 ：

  • 新结点插在当前点*p后
  • 交换两结点内容

逻辑上与原来在*p之前插入等效。

//正常把s节点插入，通过和前一个节点互换数值，从而在逻辑上实现“前插”
s= new LNode;
s->data = p->data;//把p中数值放到s中
s->next = p->next;//s链接后面的结点
p->next = s;//s链接前面的节点
p->data = x;//把s的值放入p中

（2）删除(无头结点)

情况一：删除首结点

 

p=head;//记录头结点
head=head->next;//把下一个结点设为头结点
delete p;//删除原头结点

情况二：删除中间结点、尾结点

q->next = p->next;
delete p;

（2） 删除(有头结点)

删除任意结点

q->next = p->next;
delete p;

（2）删除第i结点(等效删除)

思路：

  • 查找链表的第 i-1个结点，设q指向它， p指向第i个结点；
  • 修改第 i-1个结点的后继指针，使其指向第i个结点的后继；
  • 释放第i个结点空间；
int delete(LinkList head, int i) {LinkList p, q;q = LoacteElem(head, i - 1);//找待删点的前驱if (q == NULL || q->next == NULL) {cout << "非法删除位置！\n"；return 0;}p = q->next;//保存一份待删点的地址q->next = p->next;//修改前趋的后继指针delete p;//释放结点return 1;//删除成功}

(3) 建表(头插法)

  • 从空表开始，反复读入数据:
  1.  生成新结点
  2. 将读入数据存放到新结点的数据域中
  3. 将该新结点插入到链表的前端
  • 直到读入结束符为止。

LinkList create() {//创造头结点LinkList head, s;char ch;head = new LNode;//创造头结点while (cin >> ch, ch != '$') {s = new LNode;//创造结点s->next = head->next;s->data = ch;head->next = s;}return head;
}

 (3)建表(尾插法)

  • 从空表开始，反复读入数据：
  1. 生成新结点
  2. 将读入数据存放到新结点的数据域中
  3. 将该新结点插入到链表的尾端
  • 直到读入结束符为止。

LinkList create()//尾插法建表，有头结点
{LinkList head, rear, s;char ch;head = new LNode;//生成头结点（说明是空表）rear = head;//第一个结点既是头结点也是尾结点while (cin >> ch, ch != '$')//这是一个逗号表达式，最后一条语句的结果就是（）的结果，cin>>类似scanf（），把键盘输入的值传入变量ch中{s = new LNode;s->data = ch;//生成新节点rear->next = s;rear = s;//用rear标识尾结点}raer->next = NULL;//尾结点的后继为空return head；//链表的头结点可以标识一整个链表
}

 (4)初始化

建立一个只有头结点的空表

LinkList initlist()
{ LinkList head;head=new Lnode;head−>next=NULL;return head;
}

(5)求表长

int ListLength_L(LinkList L)
{int j = 0;LinkList p;p = L->next;//从首结点开始//从首结点开始是 p = L->next 而不是 p = L 的原因:
//在常见的链表实现中（尤其是带头结点的链表），头结点主要起到一个 “标识” 作用
//它本身通常并不存放实际要处理的数据元素
其 next 指针才指向链表中的第一个真正存有有效数据的节点，也就是首结点。while(p !=NULL)//逐点检测、计数{j++;p = p->next;}return j;
}

(6)按值查找

LinkList LocateElem_L(LinkList L, ElemType x)
{LinkList p;p = L->next;//从首结点开始搜索 注意！不是头结点！是首结点！while (p != NULL){if (p->data == x) return p;//找到了，立即终止函数，并返回查找节点的地址p = p->next;//没找到，继续找}return NULL;//P==NULL了都没找到
}

注意：返回结点号,头结点视为0号

(7)按序号查找(定位)


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

相关文章：

  • 【git】git回退到之前版本+拓展git命令
  • TCP/IP杂记
  • 本地搭建MQTT服务器
  • Onedrive技巧与问题
  • v-for遍历多个el-popover；el-popover通过visible控制显隐；点击其他隐藏el-popover
  • 【实操GPT-SoVits】声音克隆模型图文版教程
  • Python爬虫之urllib库使用总结
  • Mac软件推荐
  • maxscript中BoundingBox求一个模型的高度
  • C#-WPF 常见类型转换方法（持续更新）
  • 5G Multi-TRP R16~R18演进历程
  • Linux网络基础知识————网络编程
  • rk3588-ubuntu22.04系统网关实现路由器功能：
  • 《Hadoop大数据技术应用综合训练》----以NBA冠军球队计数为例
  • C# .NET CORE 开发问题汇总
  • day10 电商系统后台API——接口测试（使用postman）
  • 【Spark】Spark Join类型及Join实现方式
  • 数据结构DAY1
  • 开发EDA工具常用的三方开源
  • 第七天：Linux中文本编辑工具和文本三剑客-grep 第八天：Linux中shell脚本编程1