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。

相关文章

C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
C++ vector的常见用法超详细讲解

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》：本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve
阅读更多...
MySQL中FIND_IN_SET函数与INSTR函数用法解析

MySQL中FIND_IN_SET函数与INSTR函数用法解析

《MySQL中FIND_IN_SET函数与INSTR函数用法解析》：本文主要介绍MySQL中FIND_IN_SET函数与INSTR函数用法解析,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一... 目录一、功能定义与语法1、FIND_IN_SET函数2、INSTR函数二、本质区别对比三、实际场景案例分
阅读更多...
如何高效移除C++关联容器中的元素

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...
Python获取C++中返回的char*字段的两种思路

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串，目前我找到两种解决问题的思路，具体实现如下：
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...
Java图片压缩三种高效压缩方案详细解析

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,：本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点：适用场景：二、JPEG质量参数压缩关键技术：压缩效果对比
阅读更多...
Java调用C++动态库超详细步骤讲解(附源码)

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,：本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步：动态库生成（vs2017+qt5.12.10）第二步：Java调用C++
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2