C/C++线性表---顺序表算法全解析

2024-09-05 06:58
文章标签 算法 c++ 解析 顺序 线性表

本文主要是介绍C/C++线性表---顺序表算法全解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

课程笔记来源：

MOOC网

郝斌数据结构

之前学过一遍数据结构，面试时候真的忘光了，之前去华环让写一个简单的链表删除算法也是没有写出来，想做CS，必须把数据结构学好了，还是再来一遍吧。

--------------------------------------------------------------------------------------------------------------------------------------------------------------------

顺序表定义

顺序表就是把线性表中的所有元素按照逻辑顺序，依次存储到从计算机存储器中指定存储位置开始的一块连续存储空间中。

顺序表的存储类型：线性表的首地址，线性表的总长度，线性表的有效长度。

优点：任意元素可以随机存取

缺点：插入和删除操作时候，需要移动大量元素

typedef struct Arr
{int *pBase; //线性表基地址相当于数组首地址int len;  //线性表的总长度int cnt;  //线性表总有效元素
}SqList;

顺序表的基恩算法
初始化顺序表
构造一个空的顺序表，给线性表分配 len 个长度，有效长度 cnt 为0个。
注意：malloc分配时候，要进行成功与否的判断。 
void InitArr(SqList *pArr,int len)
{pArr->pBase = (int*)malloc(sizeof(int)*len);if(NULL == pArr){printf("分配失败\n");exit(-1);}pArr->cnt = 0;pArr->len = len;
}
判断顺序表是否为空
如果线性表的有效长度为 0 ，则线性表为空。 
int is_empty(SqList *pArr)
{if( 0 == pArr->cnt)return true;elsereturn false;
}
判断线性表是否为满
如果线性表的有效长度为 len ，则线性表为满。 
int is_full(SqList *pArr)
{if(pArr->cnt == pArr->len)return true;elsereturn false;
}
线性表的遍历
如果线性表为空，则无需输出，否则用 for 循环遍历输出。 
void showArr(SqList *pArr)
{int i;if( true ==is_empty(pArr)){printf("线性表元素为空\n");}else{for(i=0;i<pArr->cnt;i++)printf("%d\t",pArr->pBase[i]);puts("\n");}
}
线性表追加元素
如果线性表已经满了，则无法添加；否则，添加元素，有效元素加1。
注意：添加完元素后，有效位加1。
  
void appendArr(SqList *pArr,int ele)
{if(is_full(pArr))printf("线性表已经满了\n");else{pArr->pBase[pArr->cnt] = ele;pArr->cnt++;}
}
删除指定位置元素
判断是否为空，逻辑位置必须大于等于1，还必须小于等于cnt。从指定位置pos到cnt，依次向前移动一位。
注意：输入的是逻辑位置，必须和ele下标位置区分开。可以举个例子很好的区分开。 

void deleteArr(SqList *pArr,int pos)
{int i;if(true == is_empty(pArr))printf("线性表是空\n");if(pos < 1 || pos > pArr->cnt)printf("输入位置无效\n");else{for(i=pos;i<pArr->cnt;i++)pArr->pBase[i-1] = pArr->pBase[i];pArr->cnt--;}}

指定位置添加元素

判断是否为满，位置必须在1和cnt+1 

void insertEle(SqList *pArr,int pos,int ele)
{int i;if(is_full(pArr))printf("线性表已满\n");if(pos<1 || pos > pArr->cnt+1)printf("删除的位置无效\n");else{for(i= pArr->cnt-1;i>=pos-1;i--)pArr->pBase[i+1] = pArr->pBase[i];pArr->pBase[pos-1] =ele;pArr->cnt++;}
}


总体的C代码： 
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include <time.h>#define ListMax 10
#define true     1
#define false    0typedef struct Arr
{int *pBase; //线性表基地址相当于数组首地址int len;  //线性表的总长度int cnt;  //线性表总有效元素
}SqList;//线性表初始化
void InitArr(SqList *pArr,int len)
{pArr->pBase = (int*)malloc(sizeof(int)*len);if(NULL == pArr){printf("分配失败\n");exit(-1);}pArr->cnt = 0;pArr->len = len;
}
//判断是否为空
int is_empty(SqList *pArr)
{if( 0 == pArr->cnt)return true;elsereturn false;
}
//判断是否满了
int is_full(SqList *pArr)
{if(pArr->cnt == pArr->len)return true;elsereturn false;
}
//线性表元素遍历
void showArr(SqList *pArr)
{int i;if( true ==is_empty(pArr)){printf("线性表元素为空\n");}else{for(i=0;i<pArr->cnt;i++)printf("%d\t",pArr->pBase[i]);puts("\n");}
}
//线性表追加
void appendArr(SqList *pArr,int ele)
{if(is_full(pArr))printf("线性表已经满了\n");else{pArr->pBase[pArr->cnt] = ele;pArr->cnt++;}
}
//删除线性表
void deleteArr(SqList *pArr,int pos)
{int i;if(true == is_empty(pArr))printf("线性表是空\n");if(pos < 1 || pos > pArr->cnt)printf("输入位置无效\n");else{for(i=pos;i<pArr->cnt;i++)pArr->pBase[i-1] = pArr->pBase[i];pArr->cnt--;}}
//指定位置pos添加元素ele
//元素pos的位置是从 1 到 pArr->len
void insertEle(SqList *pArr,int pos,int ele)
{int i;if(is_full(pArr))printf("线性表已满\n");if(pos<1 || pos > pArr->cnt+1)printf("删除的位置无效\n");else{for(i= pArr->cnt-1;i>=pos-1;i--)pArr->pBase[i+1] = pArr->pBase[i];pArr->pBase[pos-1] =ele;pArr->cnt++;}
}
//得到指定位置的值
int getArr(SqList *pArr,int pos)
{if(true == is_empty(pArr))printf("线性表是空\n");if(pos < 1 || pos > pArr->cnt)printf("输入位置无效\n");return pArr->pBase[pos-1];
}
//查找第一个元素等于ele的逻辑号
int locateEle(SqList *pArr, int ele)
{int i=0;while(i<pArr->cnt && pArr->pBase[i]!= ele) i++;if(i >=pArr->cnt) return 0;else   return i+1;
}
//线性表元素倒置
void inversionArr(SqList *pArr)
{int i=0;int j=pArr->cnt-1;int temp;while(i<j){temp = pArr->pBase[i];pArr->pBase[i] = pArr->pBase[j];pArr->pBase[j] = temp;i++;j--;}
}
//线性表排序
void sortArr(SqList *pArr,int m)
{switch(m){case 1:  //冒泡排序{int i,j,temp;for(i=0;i<pArr->cnt-1;i++){for(j=i+1;j<pArr->cnt;j++){if(pArr->pBase[i] > pArr->pBase[j]){temp = pArr->pBase[i];pArr->pBase[i] = pArr->pBase[j];pArr->pBase[j] = temp;}}}break;}case 2:  //选择排序{int n = pArr->cnt;while(n >1){int i,temp,pos=0;int max=pArr->pBase[0];for(i=0;i<n;i++){if(max < pArr->pBase[i]){max = pArr->pBase[i];pos = i;}}temp = pArr->pBase[pos];pArr->pBase[pos] = pArr->pBase[n-1];pArr->pBase[n-1] = temp;n--;}break;}case 3: //插入排序{int i;for(i=1;i<pArr->cnt;i++){int temp = pArr->pBase[i];while(i>0 && pArr->pBase[i-1] > temp){pArr->pBase[i] = pArr->pBase[i-1];i--;}pArr->pBase[i] = temp;}}}
}
void main()
{int i;SqList arr;srand( (unsigned)time( NULL ) );InitArr(&arr, ListMax);for(i=0;i<7;i++)appendArr(&arr,rand()%100+1);showArr(&arr);insertEle(&arr,8,11);showArr(&arr);deleteArr(&arr,6);showArr(&arr);printf("%d\n",getArr(&arr,5));printf("%d\n",locateEle(&arr,4));inversionArr(&arr);sortArr(&arr,3);showArr(&arr);
}

C++代码：

使用了模板类，实现泛函，增强代码的重复性。 
#include<iostream>
#include<stdlib.h>
#include<time.h>#define MAXSIZE 20
using namespace std;//使用模板类是为了实现泛型，
//使用模板类可以使用不同的数据类型
template <class T>
class SqList
{
public:SqList(){cnt = 0;}//无参构造函数SqList(T a[],int len);//有参构造函数~SqList(){} //析构函数bool isEmpty();//是否为空bool isFull(); //是否满了void showArr();  //顺序表遍历T    getArr(int pos); //得到指定位置元素 elevoid appendArr(T ele);//顺序表追加void deleteArr(int pos);//删除指定位置元素void insertEle(int pos,T ele); //指定位置添加元素ele
private:T data[MAXSIZE]; //顺序表首地址int cnt; //顺序表的有效长度
};
//顺序表的无参初始化
template <class T>
SqList<T>::SqList(T a[],int len)
{if(len>MAXSIZE)cout<<"参数无效"<<endl;for(int i =0 ;i<len;i++)data[i] = a[i];cnt = len;
}template <class T>
void SqList<T>::showArr()
{for(int i=0;i<cnt;i++)cout<<data[i]<<" ";cout<<endl;
}
template <class T>
bool SqList<T>::isEmpty()
{if(cnt == 0)return true;elsereturn false;
}
template <class T>
bool SqList<T>::isFull()
{if(cnt == MAXSIZE)return true;elsereturn false;
}
template <class T>
void SqList<T>::appendArr(T ele)
{if(isFull())cout<<"顺序表已经满了"<<endl;else{data[cnt] = ele;cnt++;}}
template <class T>
void SqList<T>::deleteArr(int pos)
{if(isEmpty())cout<<"顺序表为空"<<endl;if(pos<1||pos>cnt)cout<<"输入无效"<<endl;else{for(int i=pos;i<cnt;i++){data[i-1] = data[i];}cnt--;}
}
template <class T>
T SqList<T>::getArr(int pos)
{if(pos<1 || pos>cnt){cout<<"位置无效"<<endl;return -1;}else{return data[pos-1];  //逻辑位置和ele下标相互转化}
}
template <class T>
void SqList<T>:: insertEle(int pos,T ele)
{if(isEmpty())cout<<"顺序表为空"<<endl;if(pos<1||pos>cnt)cout<<"输入无效"<<endl;else{for(int i =cnt;i>=pos; i--){data[i] = data[i-1];}data[pos-1] = ele;cnt++;}
}
int main()
{int a[10];for(int i=0;i<10;i++)a[i]=rand()%100+1;SqList<int> arr(a,10);arr.showArr();arr.appendArr(9);arr.appendArr(39);arr.showArr();arr.deleteArr(12);arr.deleteArr(1);arr.showArr();cout<<arr.getArr(8)<<endl;arr.insertEle(10,0);arr.insertEle(11,20);arr.showArr();return 0;
}


















这篇关于C/C++线性表---顺序表算法全解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1138264。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2