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

🕗 发布于 2024-12-12 05:03 数据结构 算法

例1 矩阵相乘

线性表

2.1 线性表的类型定义

绪论

例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-1

L->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-2

L->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类型起了一个别名ElemType

typedef 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结点前

思路：

查找第 i-1个结点；
建立新结点；
修改第 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) 建表(头插法)

从空表开始，反复读入数据:

生成新结点
将读入数据存放到新结点的数据域中
将该新结点插入到链表的前端

直到读入结束符为止。

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)建表(尾插法)

从空表开始，反复读入数据：

生成新结点
将读入数据存放到新结点的数据域中
将该新结点插入到链表的尾端

直到读入结束符为止。

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)按序号查找(定位)

LinkList GetElem_L(LinkList L, int i)
{
    int j;
    LinkList p;
    if (i<0 || i> L->length) 
    {
        cout << "位置非法，无此结点\n"；
            return NULL;
    }
    j = -1;
    p = head;
    while (p != NULL)
    {
        j++;
        if (j == i) break;
        p = p->next;
    }
    return p
}
//为什么j要从−1开始
  //一般情况下，链表的节点位置计数是从 1 开始
  //指针p是从链表的头结点开始搜索的,然而头结点本身在实际数据节点计数时不算在内，算作0位置
  //进入while循环时，先j++,刚好j为0，标识0位置的头结点
  //当p第一次移动时，再变为 1，正好和实际数据节点从 1 开始计数的方式相对应

例单链表求和

ElemType sum(LinkList L)
{
    LinkList p = L->next;
    ElemType sum = 0;
   
    
    while (p != NULL)
    {
        sum += p->data;
        p = p->next;
    }
    return sum;

}

例单链表清空

void DeleteAll(LinkList L)
{
    LinkList p, q;
    p = L->next;
    while(p != NULL)
    {
        q = p;//记录待删点
        p = p->next;//p继续往后走
        delete q;//释放空间
    }
    L->next = NULL;//只剩头结点了，后驱置空

}

例单链表逆置

思路：

对每个结点*p，将其next改指其前趋*q；
修改*p的next后，将不能从*p搜索到其后继，所以修改前先将其后继*r的位置保留起来。
原首结点成为尾结点，其next应为NULL；为使该结点的处理与其它结点一致，可在算法开始时将其前趋置为NULL而不是head。
头结点的next指向原尾结点。

void reverse(LinkList head)
{
    LinkList q, p, r;
    p = head->next;//因为 head 通常是头结点，head->next 才指向链表中第一个存有有效数据的节点
    q = NULL;//用q来标记p的前一个结点
    while (p != NULL)//用p来遍历链表
    {
        r = p->next;//用r来记录当前结点的后驱
        p->next = q;//把p的后驱指向前一个结点，此时p原来的后驱就丢失了,而r刚好记录
        q = p;//用q记录p，p继续向后走
        p = r;//r记录了p的后驱，此时q相当于前一个结点

    }
}

例：链表合并

将两个递增有序线性链表归并成一个非递减有序表。

原理：将两表当前结点中较小的尾插到新表

LinkList merge(LinkList A, LinkList B)
{
    LinkList p, q, r, head;
    head = new Lnode;
    r = head;
    p = A->next; q = B->next;
    while (p != NULL && q != NULL)//当p，q都没有到末尾时
        if (p->data < q->data) //如果A链表数据更小
        { r->next = p; //新链表的下一个结点就是p
        r = p; //用r标识新链表中的 当前结点
        p = p->next;//A中p前进一位
        }
        else { r->next = q; //否则，B中数据大
        r = q;
        q = q->next; }
    if (p != NULL)  r->next = p;//如果A链表还没被遍历完，新链表直接接上A剩下的结点
    if (q != NULL)  r->next = q;//如果B链表还没被遍历完，新链表直接接上B剩下的结点
    delete A;
    delete B;
}

小结

单链表是线性表的一种链式存储结构
线性链表的特点:

通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；
插入、删除操作通过修改结点的指针实现；
不能随机存取元素；

原文地址：https://blog.csdn.net/2301_81949860/article/details/144312824

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：微服务架构解析：跨越传统架构的技术革命
下一篇：新能源汽车安全充电管理方案

【开源免费】基于SpringBoot+Vue.JS加油站管理系统（JAVA毕业设计）
Vue.js+SpringBoot前后端分离新手入门项目《加油站管理系统》，包括论坛模块、加油站模块、汽油模块、加油模块
阅读更多2024-12-12
使用wol-web通过NAS远程唤醒电脑
相信很多人都有远程开机的需求，有时候需要远程控制家中的电脑办公、玩游戏。远程控制比较好实现，安装类似向日葵的软件即可。而远程开机稍微麻烦一点，有的通过物理开关实现（开机棒）我们选择远程网络唤醒的方式实
阅读更多2024-12-12
如何使用 Webpack ModuleFederationPlugin 构建微前端架构
在前端开发中，构建和部署大型应用程序变得越来越复杂。为了更好地管理这些复杂性，模块联邦（Module Federation）作为 Webpack 5 的一部分应运而生。模块联邦允许我们将应用程序拆分为
阅读更多2024-12-12
深入理解JavaScript中的自定义属性操作|style 样式属性操作|className 类名属性操作
通过本文的介绍，我们了解了如何使用JavaScript中的和方法来操作自定义属性，以及如何通过style属性和className属性来操作元素的样式和类名。掌握这些技巧可以帮助你在Web开发中更灵活地
阅读更多2024-12-12
Linux——rootfs根文件系统构建
根文件系统也叫做rootfsFATFS这类的文件系统属于Linux内核的一部分，属于软件代码，所以ROOTFS不等于FATFS。Linux的根文件系统实际上是一个文件夹或者叫目录，这个目录下会有许多子
阅读更多2024-12-12
SAP借助GenAI助力S/4HANA迁移，应对2027支持终止期限
针对用户对复杂定制系统迁移的担忧，SAP推出了一系列工具和方法，提高了对ECC现状的透明度和管理能力。SAP的挑战在于，尽管技术工具不断优化，但大量用户尚未开始迁移，这对系统集成商的资源和能力构成了极
阅读更多2024-12-12
latex公式符号
{}属于符号(右下划线)花体。
阅读更多2024-12-12
SpringBoot常见的注解
在 Spring Boot 开发中，注解是简化开发过程和提高效率的核心工具。通过使用各种注解，我们可以实现依赖注入、配置管理、Web 开发、数据访问等功能。以下是一些常见的 Spring Boot 注
阅读更多2024-12-12
交换排序(Swap Sort)详解
主要是通过两两比较待排元素的关键字，若发现与排序要求相逆，则交换之。在这类排序方法中最常见的是，其中快速排序是一种在实际应用中具有很好表现的算法。
阅读更多2024-12-12
Golang学习笔记_03——匿名函数和闭包
匿名函数，顾名思义，就是没有名称的函数。它们可以在需要函数值或函数类型的表达式中直接定义。闭包是指一个函数以及该函数所引用的所有外部变量的集合。闭包允许函数记住并访问其词法作用域（即定义时的环境）中的
阅读更多2024-12-12

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

绪论

例1 矩阵相乘

线性表

2.1 线性表的类型定义

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

例2-2 有序表归并

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

1．构造空表

2．插入

3．删除

4．定位

顺序表的优点：

顺序表的缺点：

例：交替扫描

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

2.3.1 单链表

概念解释：

创建结点

结点的动态分配与释放

（1）插入(无头结点)

（1）插入(有头结点)

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

（2）删除(无头结点)

（2） 删除(有头结点)

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

(3) 建表(头插法)

(3)建表(尾插法)

(4)初始化

(5)求表长

(6)按值查找

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

例 单链表求和

例 单链表清空

例 单链表逆置

例： 链表合并

小结

相关文章

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

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

（2）删除(有头结点)

例单链表求和

例单链表清空

例单链表逆置

例：链表合并