数据结构例题代码及其讲解-顺序表

这篇具有很好参考价值的文章主要介绍了数据结构例题代码及其讲解-顺序表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

顺序表

静态分配内存及初始化

#include<stdio.h>
#include<stdlib.h>
#define Maxsize 100
//静态
typedef struct sqlist {
	int data[Maxsize];
	int length;
}SqList;
void InitList(SqList& L) {
	L.length = 0;				//顺序表的初始长度为0
}

动态分配内存及初始化

//动态
typedef struct {
	int* data;					//指示动态分配数组的指针
	int MaxSize;				//顺序表的最大容量
	int length;					//顺序表的当前长度
}SeqList;
void InitList(SeqList& L) {
	L.data = (int*)malloc(Maxsize * sizeof(int));
	L.length = 0;
	L.MaxSize = Maxsize;
}                                                                                               
01 对顺序表L进行遍历并输出每个数据元素的数据值
//对顺序表L进行遍历并输出每个数据元素的数据值
void print(SqList &L){
    for(int i=0;i<L.length;i++){
        printf("%d",L.data[i]);
    }
}
02 假设有一个顺序表L,其存储的所有数据元素均为不重复的正数,查找 L 中值为 e 的数据元素,若找到则返回其下标,若找不到则返回-1。
int search_e(SqList L, int e) {
	for (int i = 0; i < L.length; i++) {
		if (e == L.data[i]) {
			return i;
		}
	}
	return -1;
}
03 假设有一个顺序表 L,其存储的所有数据元素均为正数,查找 L 中第 i 个数据元素并返回其值。
//假设有一个顺序表 L,其存储的所有数据元素均为正数,查找 L 中第 i 个数据元素并返回其值。 
int Get_i(SqList L, int i) {
	if (i >= 1 && i <= L.length) {
		return L.data[i - 1];
	}
	return -1;//越界
}

①注意越界的判断

04 设计一个高效算法,将顺序表 L 的所有元素逆置,要求算法的空间复杂度为 O(1) 。
  1. 逆置:实现头和尾的转换
  2. 空间复杂度O(1):不能去定义数组啥的,只能用常量级别解决。
  3. 4个元素,交换两次,5个元素也交换两次,交换次数规律是length/2向下取整,而计算机中自动向下取整,这里大家可以自己去试着模拟一下,i < L.length/2,如果取等号,偶数个元素的顺序表,中间的两个元素会重新换回来(i多走了一步)。
  4. 逆置时用下标找规律。
//设计一个高效算法,将顺序表 L 的所有元素逆置,要求算法的空间复杂度为 O(1)
void Reverse(SqList& L) {
	int temp;
	for (int i = 0; i < L.length/2; i++) {
		temp = L.data[i];
		L.data[i] = L.data[L.length - i - 1];
		L.data[L.length - i - 1] = temp;
	}
}
05 在顺序表 L 的第 i 个位置插入新元素 e。若 i 的输入不合法,则返回 false, 表示插入失败;否则,将第 i 个元素及其后的所有元依次往后移动一个位置, 腾出一个空位置插入新元素 e,顺序表长度增加 1,插入成功,返回 true。
  1. 注意插入的位置可以是1~length+1
  2. 顺序表存满了也不能存了
  3. 从后往前的移动元素
  4. 判断条件
//在顺序表 L 的第 i 个位置插入新元素 e。若 i 的输入不合法,则返回 false,表示插入失败;否则,将第 i 个元素及
//其后的所有元素依次往后移动一个位置,腾出一个空位置插入新元素 e,顺序表长度增加 1,插入成功,返回 true。
bool Insert(SqList &L, int i, int e) {
	if (i<1 || i>L.length+1) {
		return false;
	}
	if (L.length == Maxsize) {
		return false;
	}
	for (int j = L.length; j > i-1; j--) {
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;
	L.length++;
	return true;
}
06 已知一个顺序表 L,其中的元素递增有序排列,设计一个算法在插入元素 x(x 为 int 型)后保持该顺序表仍然递增有序排列,假设c插入操作肯定成功,插入成功后返回插入元素所在位置。

分析

  1. 先找出位置

  2. 插入元素

  3. 注意:要返回插入元素位置,i的定义要放在for循环外

  4. 举例(从后往前移动元素,第一行为顺序表,第二行为下标)

    ①假设x=5,即i=3,初始j=4,判断移动一次,故判断条件为j>i或者j>=i+1

    ②假设x=3,即i=2,初始i=4,判断移动两次,第一次移动条件j=4,i=2,第二次移动j=3,i=2,故判断条件为j>i或者j>=i+1
    

综上,判断条件为j>i或者j>=i+1

int Insert(SqList &L,int x){
    int i;//定义变量 i 记录元素 x 插入位置
    for(i=0; i<L.length; i++){
        if(L.data[i]>x){
            break;
        }
    }
    //也可以换成for(i=0; i<L.length,L.data[i]<=x; i++);
    //自己模拟j的条件(易错)
    for(j=L.length;j>i;j--){
        L.data[j]=L.data[j-1];
    }
    L.data[i]=x;
    L.length++;
    return i;
}
07 删除顺序表 L 中第 i 个位置的元素,若 i 的输入不合法,则返回 false; 否则将被删元素赋给引用变量 e,并将第 i+1 个元素及其后的所有元素依次往前 移动一个位置,返回 true。

分析

  1. 注意i是位置,和下标不一样

  2. 被删元素赋给引用变量 e

  3. 举例

    位置 1 2 3 4 5

    元素 2 5 1 3 4

    下标 0 1 2 3 4

    删除第2个位置,i=2,L.length=4,下标为1,要移动两次(j=2,j=3),判断条件为j<L.length
    
  4. 最后别忘了顺序表长度改变

bool ListDelete(SqList &L, int i, int &e){
    if(i<1||i>L.length){
        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 ture;
}
08 从顺序表 L 中删除最小值元素并由函数返回被删元素的值。(假设顺序表中数据元素全为正值且最小值唯一)

分析

  1. 先找到最小值,在进行删除
  2. 要判断不合理情况,如空的顺序表
  3. 首先定义最小值为下标为0的元素,记录其位置pos
  4. 由于最后需要返回被删元素的值,因此需要有个变量对最小值进行保存,然后删除操作过程中,最小值被删除,此后如果没有保存最小元素的变量,则找不到最小值。
int Delete_min(SqList &L)[
    if(L.length==0){
        return 0;
    }
    //查找最小值
    int min=L.data[0],pos=0;
    for(int i=1;i<L.length;i++){
        if(L.data[i]<min){
            min=L.data[i];
            pos=i;
        }
    }
    //删除操作,首先定义
    //j<L.length-1可以自己模拟出,假设长度为五,假设最小值时,i=pos=3,另j=i,说明只需要移动一次即可,判断条件
    for(int j=pos; j<L.length-1;j--){
        L.data[j]=L.data[j+1];
    }
    //减少长度
    L.length--;
    return min;
    
]
09 对长度为 n 的顺序表 L,编写一个时间复杂度为 O(n)、空间复杂度为 O(1) 的算法,该算法删除顺序表中所有值为 x 的数据元素。
  1. x可能不止一个,因此后面元素前移的数量需要改变
  2. 定义一个变量k用来记录目前已经删除几个元素,k=1表示后面的元素需要前移1个
  3. 元素要保留,需要交换,元素不保留,不需要交换,先本次交换,然后在k再加1.

法一:

void Delete_all_x(SqList &L,int x){
    int k=0;
    for(int i=0;i<L.length;i++){
        if(L.data[i]==x){
            //应该删除
            k++;      
        }
        else{
            //重点
            L.data[i-k]=L.data[i];            
        }
    }
    L.length=L.length-k;
}

法二:

思路:将顺序表需要保存的元素理解为排队,直接用一个变量记录排队位置,

void Delete_all_x(SqList &L,int x){
    int k=0;
    for(int i=0; i<L.length; i++){
        if(L.data[i]!=x){
            //需要保留
            L.data[k]=L.data[i];
            k++;
        }
    }
    //不是k+1,因为排队结束会执行k++的操作
    L.length = k;
}

改成while循环也类似:

void Delete_all_x(SqList &L,int x){
    int k=0;
    int i=0;
    while(i<L.length){
        if(L.data[i]!=x){
            k++;
        }
        i++;
    }
    //不是k+1,因为排队结束会执行k++的操作
    L.length = k;
}
10 从顺序表中删除其值在给定值 s 与 t 之间(包含 s 和 t,要求 s<t)的所有元素,若 s 或 t 不合理或顺序表为空,则返回 false,若执行成功则返回 true。
  1. 和上一题一样,有两种实现方式

法一:

bool Del(SqList &L,int s,int t){
    if(s>=t||L.length==0) //若 s 或 t 输入不合法或顺序表为空,则返回 false
		return false;
	int k=0; //k 用来记录要删除元素的数量,初始时为 0
	for(int i=0;i<L.length;i++){ //遍历顺序表 L
		if(L.data[i]>=s&& L.data[i]<=t) //若元素符合删除条件则 k 加一
		k++;
    }
	else{ //若元素需保留则前移 k 个位置
		L.data[i-k]= L.data[i];
	}
	L.length= L.length-k; //更新顺序表长度
	return true; //执行结束返回 true
}

法二文章来源地址https://www.toymoban.com/news/detail-684382.html

bool Del(SqList &L,int s,int t){
	if(s>=t||L.length==0) //若 s 或 t 输入不合法或顺序表为空,则返回 false
		return false;
	int j=0; //j 用来记录保留元素的排队位置
	for(int i=0;i<L.length;i++){ //遍历顺序表 L
		if(L.data[i]<s||L.data[i]>t){ //判断此次遍历到的元素是否为保留元素
			L.data[j]=L.data[i]; //是保留元素则过去排队
			j++; //新元素排队后需更新排队位置
		}
	}
	L.length= j; //更新顺序表长度
	return true; //执行结束返回 true
}
11 从有序顺序表中删除所有其值重复的元素,使表中所有元素的值均不同。
  1. 本题目是有序顺序表,这个算法和前面两个有所区别,在于从第二个元素开始,每次和前一个元素比较;
  2. 之前是从第一个元素开始,所以记录排队位置是0,这次是第二个元素开始(第一个元素肯定不重复,不需要交换),因此我们可以记录排队位置变量初始设置为1,然后根据这个进行后续代码的改动,还是那句话元素要保留,需要交换,最后注意一下顺序表长度即可。
void Del_Same(SqList &L){ 
	int j=1; // j 用来记录保留元素的排队位置 
	for(int i=1;i<L.length;i++){ //遍历顺序表 L 
		if(L.data[i]!=L.data[j-1]){ //判断此次遍历到的元素是否为保留元素 
			L.data[j]=L.data[i]; //是保留元素则过去排队 
			j++; //新元素排队后需更新排队位置 
		}
    }
	L.length=j; //更新顺序表长度 
}
12 从有序顺序表中删除其值在给定值 s 与 t 之间(包含 s 和 t,要求 s<t)的所有元素,若 s 或 t 不合理或顺序表为空,则返回 false,若执行成功则返回 true。
  1. 这题目的思路是定义两个变量分别去待删元素的起始位置和结束位置,这里需要注意的是左边是小于s,这样最后一次j就来到了待删元素处,右边是小于等于,这样的话最后一次i来到了待删元素的后一个位置。
bool Del_s_t(SqList &L,int s,int t){
	if(s>=t||L.length==0){ //若 s 或 t 输入不合法或顺序表为空则返回 false
		return false;
	}
	int i,j; //定义两个变量 i 和 j 负责记录待删元素的起始位置和结束位置
	for(j=0;j<L.length&&L.data[j]<s;j++); //寻找待删元素起始位置
	if(j==L.length){ //若顺序表中所有元素都比 s 小则没有要删元素
		return false;
	}
	for(i=j;i<L.length&&L.data[i]<=t;i++); //寻找待删元素的结束位置
	for(;i<L.length;i++,j++){ //将结束位置后的保留元素前移至起始位置
		L.data[j]=L.data[i];
	}
	L.length=j; //更新顺序表长度
	return true; //执行结束则返回 true
}
13 将两个有序顺序表 A 和 B 合并为一个新的有序顺序表 C,若合并成功则返回 true,合并失败则返回 false。
  1. 首先判断一下是否有足够空间进行合并,然后需要三个遍历指针进行遍历,最后记得更新C表表长
bool Merge(SeqList A, SeqList B, SeqList& C) {
    if (A.length + B.length > C.Maxsize) //判断 C 存储空间是否能容纳 A 和 B
        return false;
    int i = 0, j = 0, k = 0; //定义三个遍历指针,分别遍历 ABC
    while (i < A.length && j < B.length) { //只有 A 和 B 都没遍历完才可以继续循环
        if (A.data[i] <= B.data[j]) { //若 A 表中值更小则 A 表中遍历元素赋值给 C 表
            C.data[k] = A.data[i];
            k++; //更新 C 表元素插入位置
            i++; //更新 A 表遍历位置
        }
        else { //若 B 表中值更小则 B 表中遍历元素赋值给 C 表
            C.data[k] = B.data[j];
            k++; //更新 C 表元素插入位置
            j++; //更新 B 表遍历位置
        }
    }
    while (i < A.length) { //若循环结束后 A 还有未遍历元素则顺序赋值给 C
        C.data[k] = A.data[i];
        k++;
        i++;
    }
    while (j < B.length) { //若循环结束后 B 还有未遍历元素则顺序赋值给 C
        C.data[k] = B.data[j];
        k++;
        j++;
    }
    C.length = k; //更新 C 表长度
    return true; //执行结束返回 true
}

到了这里,关于数据结构例题代码及其讲解-顺序表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构-查找(顺序查找与二分查找的讲解与代码实现)

    顺序查找概念:从表的另一端开始,一次将记录的和给定值进行比较,若某个记录的和给定的值相等,则查找成功,反之则查找失败。 ASL:平均查找长度 pi查找概率,ci查找次数 eg:序列1,2,3 查找1的次数为1概率为1/3,2为两次概率1/3,3的次数为3概率1/3  将12

    2024年02月06日
    浏览(68)
  • 数据结构队列例题一顺序实现

    仅供个人复习使用

    2024年02月06日
    浏览(43)
  • 数据结构进阶篇 之 【二叉树顺序存储(堆)】的整体实现讲解(赋完整实现代码)

    做人要谦虚,多听听别人的意见,然后记录下来,看看谁对你有意见 3.1 向下调整算法 AdJustDown 3.2 向上调整算法 AdJustUP 3.3 堆的创建 3.3.1 向上建堆 3.3.2 向下建堆 3.3.3 堆的初始化与销毁 3.3.4 堆的插入(压栈) 3.3.5 取堆顶的数据 3.3.6 堆的删除 3.3.7 堆的数据个数 3.3.8 堆的判空

    2024年04月17日
    浏览(72)
  • 数据结构_复杂度讲解(附带例题详解)

    数据结构是计算机科学中研究数据组织、存储、管理和操作的方法和原则。它涉及到各种不同的数据类型和数据组织方式,包括数组、链表、树、图等。数据结构的设计和实现可以影响到程序的效率和可靠性,因此是计算机科学中非常重要的一个领域。 (数据结构是计算机存

    2024年02月07日
    浏览(46)
  • java数据结构(哈希表—HashMap)含LeetCode例题讲解

      目录 1、HashMap的基本方法 1.1、基础方法(增删改查) 1.2、其他方法  2、HashMap的相关例题 2.1、题目介绍 2.2、解题 2.2.1、解题思路 2.2.2、解题图解 2.3、解题代码 HashMap 是一个散列表,它存储的内容是键值(key-value)映射。 HashMap 的 key 与 value 类型可以相同也可以不同,根据定

    2024年02月05日
    浏览(51)
  • 【数据结构与算法】之顺序表及其实现!

    目录 ​编辑 1. 顺序表的概念及结构 2. 接口的实现 2.1 顺序表的初始化 2.2 检查顺序表容量是否已满 2.3 顺序表的尾插 ​编辑 2.4 顺序表的尾删 2.5 顺序表的头插 2.6  顺序表的头删 2.7 顺序表在pos位置插入 2.8  顺序表在pos位置删除 2.9 顺序表的查找 2.10 顺序表的销毁 2.1

    2024年04月28日
    浏览(33)
  • 【数据结构】:顺序表及其通讯录应用

    1.1为什么会存在数据结构? 我们常常接触到诸如生活中的姓名、身份证、网页内的图片、视频等各种各样的信息,这些信息就是我们常说的数据。在使用这些数据时,我们发现随着数据的增加,当我们要单独寻找某一个数据时就会非常困难,就像图书馆内书籍如果没有按一定

    2024年04月26日
    浏览(39)
  • 【数据结构】顺序表 | 详细讲解

    在计算机中主要有两种基本的存储结构用于存放线性表:顺序存储结构和链式存储结构。本篇文章介绍采用顺序存储的结构实现线性表的存储。 线性表的顺序存储结构,指的是一段地址连续的存储单元依次存储链性表的数据元素。 线性表的(,……)的顺序存储示意图如下

    2024年02月04日
    浏览(38)
  • 【数据结构】广度优先遍历(BFS)模板及其讲解

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【勋章】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰 目录   🎁定义 🎁遍历方法  🎁根据题目来理解BFS 🏳️‍🌈走迷宫 🏳️‍🌈思路 🏳️‍🌈代码(BFS模板) 🏳️‍🌈分

    2024年02月06日
    浏览(41)
  • 原神世界中的顺序表:派蒙的趣味数据结构讲解

    派蒙,那个总是带着疑问眼神的小家伙,是原神世界中的小精灵。他总是充满好奇心,无论是对新的冒险者,还是对各种奇妙的现象。而他的另一个身份,则是原神世界中的数据结构大师。 一天,派蒙遇到了旅行者小森,他带着一肚子的疑问和困惑。 小森:“派蒙,我一直

    2024年02月11日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包