软考路之线性表

2024-08-26 10:58
文章标签 软考 线性表

本文主要是介绍软考路之线性表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

背景:数据结构导论中介绍了什么是线性表以及线性表的存储,软考学习中也有这部分的内容,自己对这部分有点抵触,感觉乱乱的,现在梳理总结一下,同时消除心中的抵触。


一、线性表(Linear List)


    是一种线性结构,由n(n>=0)个元素组成的有穷序列,数据元素又称结点,结点个数n称为表长。



二、基本特征


1、线性表中结点具有一对一的关系

2、若结点数不为0,则除起始结点没有直接前驱外,其他每个结点有且仅有一个直接前驱。

3、若结点数不为0,则除终端结点没有直接后继外,其他每个结点有且仅有一个直接后继。

4、线性表中每个数据元素的含义在不同的应用中各不相同,但同一个线性表中的所有结点代表的数据元素具有相同的特性。



三、顺序存储


    将表中的结点依次存放在计算机内存中一组连续的存储单元中,数据元素在线性表中的邻接关系决定他们在存储空间中的存储位置,即逻辑结构中相邻的结点其存储位置也相邻。

    用顺序存储实现的线性表称为顺序表,一般用数组来表示顺序表。

    顺序表中的“第i个数据元素”存放在数组下标为“i-1”的位置。




1、插入


首先,将结点ai~an依次向后移动一个元素的位置,空出第i个数据元素的位置。

然后,将x置入该空位。

最后,表长加1。


void InsertSeqlist(SeqList L, DataType x ,int i)
{  //将元素x插入到顺序表L的第i个数据元素之前if(L.length==Maxsize)    exit(“表已满”);if(i<1 || i>L.length+1)  exit(“位置错”);   //检查插入位置是否合法
for(j=L.length;j>=I;j--)                            //初始i=L.lengthL.data[j]=L.data[j-1];                      //依次后移
L.data[i-1]=x;                                      //元素x置入到下标为i-1的位置
L.length++;                                         //表长度加1
}


2、删除


首先,结点a(i+1), ... ,an依次向左移动一个元素位置(从而覆盖掉被删除的结点ai)

然后,表长度减1。


void DeleteSeqlist(SeqList L, int i)
{  //删除线性表L中的第i个数据结点if(i<1 || i>L.length)  exit(“位置错”);   //检查插入位置是否合法
for(j=I ; j<L.length;j++)                         //第i个元素的下标为i-1L.data[j-1]=L.data[j];                    //依次左移
L.length--;                                       //表长度减1
}


3、定位


查找出线性表L中值等于x的结点序号的最小值,当找不到值为x的结点是,返回结果为0。

void LocateSeqlist(SeqList L, DataType x)
{  int i=0;while ((i<L.length) && (L.data[i]!=x));   //在顺序表中查找值为x的结点i++;if (i<L.length) return  i+1;             //若找到值为x的元素,返回元素的序号else return 0;                           //未找到值为x的元素,返回0
}


四、链接存储


    指它的存储结构是链式的,常见的链式存储结构有单链表、循环链表和双向循环链表。


    结点结构



    单链表示例


   变量head是链表的头指针,指向新创建的结点,即头结点。


1、初始化


首先,创建一个头结点并将其指针域设为NULL(标识该结点不指向任何结点)

然后,用一个LinkList类型(即结点的指针类型)的变量指向新创建的结点。


LinkList InitiateLinkList()
//创建一个空的单链表
{LinkList head;                //头指针head=malloc(sizeof(Node));    //动态构建一结点,它是头结点head—>next=Null;return head;
}

2、求表长


在单链表存储结构中,线性表的表长等于单链表中数据元素的结点个数,即除了头结点以外的结点的个数。


int LengthLinklist(LickList head)
//求单链表head的长度
{Node * p=head;            //p是工作指针,初始时p指向头结点int cnt=0;                //计数器置初值while (p—>next !=NULL)   //判断是否为尾结点{p= p—>next;          //指针移动到下一个结点cnt++;}return cnt;               //返回表长
}

3、读表元素


必须从头指针出发,一直往后移动,直到第i个结点。


Node * GetLinklist(LinkList  head , int i)
//在单链表head中查找第i个元素结点。若找到,则返回指向该结点的指针;否则返回NULL
{
Node * p;                      //p是工作指针
P=head—>next;                 //初始时,p指向首结点
int c=1;
while ((c<i) && (p!=NULL))     //当未到第i结点且未到尾结点时继续后移{ p=p—>next; c++;}
If (i==c) return  p;           //找到第i个结点
else return NULL;              //i<1或i>n,i值不合法,查找失败
}


4、定位


    对给定表元素的值,找出这个元素的位置。需要从头至尾访问链表,直至找到需要的结点,返回其序号。若未找到,返回0.



int LocateLinklist(LinkList head ,DataType  x)
//求表head中第一个值等于x的结点的序号,若不存在这种结点,返回0
{Node * p=head;                      //p是工作指针p=p—>next;                         //初始时p指向首结点int i=0;                            //i代表结点的序号,这里置初始值为0while (p!=NULL  && p—>data!=x)     //访问链表{i++;p=p—>next;}if (p!=NULL) return i+1;else  return  0;
}

5、插入


首先,找到链表的第i-1个结点q.

然后,生成一个值为x的新结点p,

最后,p的指针域指向q的直接后继结点,q的指针与指向p.


Void InsertLinkList (LinkList head ,DataType x,int i)
//在表head的第i个数据元素结点之前插入一个以x为值的新结点
{Node * p, *q;if (i==1) q=head;else q=GetLinklist(head,i-1)              //找第i-1个数据元素结点if (q==NULL)                              //第i-1个结点不存在exit (“找不到插入的位置”);else { p=malloc(sizeof(Node));p—>data=x;   //生成新结点P—>next=q—>next;   <span style="white-space:pre">		</span>      //新结点链域指向*q的后继结点q—>next=p;                          //修改*q的链域}
}


6、删除


给定一个值i,将链表中第i个结点从链表中移出,并修改相关结点的指针域,以维持剩余结点的链接关系。


void  DeleteLinkList (LinkList  head ,int i)
//删除表head的第i个结点
{Node * q;if (i==1) q=head;else q=GetLinklist(head,i-1);        //先找到待删除结点的直接前驱if (q!==NULL && q—>next !=NULL)     //若直接前驱存在且待删结点存在{p =q—>next;                      //p指向待删结点q—>next=p—>next;                //移除待删结点free(p);                          //释放已移出结点p的空间}else exit(“找不到要删除的结点”);    //结点不存在
}


五、比较



    总之,线性表的顺序实现与链接实现各有其优缺点,不能笼统地说哪种实现更好,只能根据实际问题的具体需要,并对各方面的优缺点加以综合平衡,最终选定比较适宜的实现方法。


六、学习心得


    虽然有点乱,但是,整理一下就会好很多,现在感觉,对这方面的了解多了一点。

    博客不光是写给别人看的,更是自己学习轨迹的体现,把不会的,不清楚的整理下来,后期翻阅的时候,就会有新的体会。同时,在整理的时候,是自己收获比较大的时候。










这篇关于软考路之线性表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1108368

相关文章

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页);内聚的类型;关于码制的知识点;地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位:为1时表示在内存期间被访问过,为0时表示未被访问;修改位:为1时表示该页面自从被装入内存后被修改过,为0时表示未修改过。 置换页面时,最先置换访问位和修改位为00的,其次是01(没被访问但被修改过)的,之后是10(被访问了但没被修改过),最后是11。 2.内聚的类型 功能内聚:完成一个单一功能,各个部分协同工作,缺一不可。 顺序内聚:

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

【软考】安全威胁

目录 1. 说明2. 典型的安全威胁2.1 授权侵犯2.2 拒绝服务2.3 窃听2.3 信息泄露2.4 截获/修改2.5 假冒2.6 否认2.7 非法使用2.8 人员疏忽2.9 完整性破坏2.10 媒体清理2.11 物理入侵2.12 资源耗尽 3. 例题3.1 例题1 1. 说明 1.随着信息交换的激增,安全威胁所造成的危害越来越被受到重视,因此对信息保密的需求也从军事

数据结构:线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入

[数据结构]线性表之单链表的类模板实现

类的具体实现如下: /#include"LinearList.h"#include <iostream>#include <cstdlib>using namespace std;template<class T>struct LinkNode //链表节点类{T data;LinkNode<T>* link;LinkNode(LinkNode<T>* ptr=NULL):

线性表中顺序表的合并

对两个顺序表进行合并,算法的复杂度为O(La.size+Lb.size)。 已知: 顺序线性表La和Lb的元素按值非递减排列 归并La和Lb得到的顺序线性表Lc,Lc的元素也按值非递减排列。 代码定义: void mergeList(SeqList *La,SeqList *Lb,SeqList *Lc){Lc->capacity = La->size + Lb->size;Lc->b

软考(计算机技术与软件专业技术资格(水平)考试)

天行健,君子以自强不息;地势坤,君子以厚德载物。 每个人都有惰性,但不断学习是好好生活的根本,共勉! 文章均为学习整理笔记,分享记录为主,如有错误请指正,共同学习进步。 月下飞天镜,云生结海楼。 ——《渡荆门送别》 信息系统项目管理师备考专栏 软考全称:计算机技术与软件专业技术资格(水平)考试 官网直达:中国计算机技术职业资格网 文章目录 软考介绍1.

软考学习 数据结构 排序

1. 冒泡排序(Bubble Sort) 基本原理: 冒泡排序是一种简单的交换排序算法,它通过重复地遍历要排序的数列,依次比较相邻的两个元素,并在顺序错误时交换它们的位置。每一轮遍历后,最大的元素会“冒泡”到数列的末尾,因此称为冒泡排序。这个过程不断重复,直到整个序列有序为止初始状态:从序列的第一个元素开始,依次比较相邻的两个元素。元素比较与交换: 如果前一个元素大于后一个元素,则交换它们的位

软考-软件设计师(UML习题)

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨   前言 小郑正在备考2024年下半年的中级软件设计师,所以打算开展一个软考备考专栏,在这里记录一下备