喵喵爱编程

这个屌丝很懒，什么也没留下！

热门标签

数据结构例题代码及其讲解-顺序表_顺序表操作完整例题

作者：喵喵爱编程 | 2024-07-15 12:07:29

踩

顺序表操作完整例题

顺序表

静态分配内存及初始化

#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
}
1
2
3
4
5
6
7
8
9
10
11

动态分配内存及初始化

//动态
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;
}                                                                                               
1
2
3
4
5
6
7
8
9
10
11

01 对顺序表L进行遍历并输出每个数据元素的数据值

//对顺序表L进行遍历并输出每个数据元素的数据值
void print(SqList &L){
    for(int i=0;i<L.length;i++){
        printf("%d",L.data[i]);
    }
}
1
2
3
4
5
6

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;
}
1
2
3
4
5
6
7
8

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;//越界
}
1
2
3
4
5
6
7

①注意越界的判断

04 设计一个高效算法，将顺序表 L 的所有元素逆置，要求算法的空间复杂度为 O(1) 。

逆置：实现头和尾的转换
空间复杂度O(1)：不能去定义数组啥的，只能用常量级别解决。
4个元素，交换两次，5个元素也交换两次，交换次数规律是length/2向下取整，而计算机中自动向下取整，这里大家可以自己去试着模拟一下，i < L.length/2，如果取等号，偶数个元素的顺序表，中间的两个元素会重新换回来（i多走了一步）。
逆置时用下标找规律。

//设计一个高效算法，将顺序表 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;
	}
}
1
2
3
4
5
6
7
8
9

05 在顺序表 L 的第 i 个位置插入新元素 e。若 i 的输入不合法，则返回 false，表示插入失败；否则，将第 i 个元素及其后的所有元依次往后移动一个位置，腾出一个空位置插入新元素 e，顺序表长度增加 1，插入成功，返回 true。

注意插入的位置可以是1~length+1；
顺序表存满了也不能存了
从后往前的移动元素
判断条件

//在顺序表 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

06 已知一个顺序表 L，其中的元素递增有序排列，设计一个算法在插入元素 x(x 为 int 型)后保持该顺序表仍然递增有序排列，假设c插入操作肯定成功，插入成功后返回插入元素所在位置。

分析

先找出位置
插入元素
注意：要返回插入元素位置，i的定义要放在for循环外
举例（从后往前移动元素，第一行为顺序表，第二行为下标）

①假设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
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

07 删除顺序表 L 中第 i 个位置的元素，若 i 的输入不合法，则返回 false；否则将被删元素赋给引用变量 e，并将第 i+1 个元素及其后的所有元素依次往前移动一个位置，返回 true。

分析

注意i是位置，和下标不一样
被删元素赋给引用变量 e

举例

位置 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
1

最后别忘了顺序表长度改变

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;
}
1
2
3
4
5
6
7
8
9
10
11
12

08 从顺序表 L 中删除最小值元素并由函数返回被删元素的值。(假设顺序表中数据元素全为正值且最小值唯一)

分析

先找到最小值，在进行删除
要判断不合理情况，如空的顺序表
首先定义最小值为下标为0的元素，记录其位置pos
由于最后需要返回被删元素的值，因此需要有个变量对最小值进行保存，然后删除操作过程中，最小值被删除，此后如果没有保存最小元素的变量，则找不到最小值。

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;
    
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

09 对长度为 n 的顺序表 L，编写一个时间复杂度为 O(n)、空间复杂度为 O(1) 的算法，该算法删除顺序表中所有值为 x 的数据元素。

x可能不止一个，因此后面元素前移的数量需要改变
定义一个变量k用来记录目前已经删除几个元素,k=1表示后面的元素需要前移1个
元素要保留，需要交换，元素不保留，不需要交换，先本次交换，然后在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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

法二：

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

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;
}
1
2
3
4
5
6
7
8
9
10
11
12

改成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;
}
1
2
3
4
5
6
7
8
9
10
11
12

10 从顺序表中删除其值在给定值 s 与 t 之间（包含 s 和 t，要求 s<t）的所有元素，若 s 或 t 不合理或顺序表为空，则返回 false，若执行成功则返回 true。

和上一题一样，有两种实现方式