实现顺序表的各种基本运算

这期我把它同时塞到了数据结构和练习程序两个收藏里

因为正好课后的实验题跟这里内容几乎完全重叠

就打算放在这里一起讲了


数据元素到底可以是什么?

前面我们特意讲到了C结构体和C++结构体和类三者的区别

就是因为这一个问题,我们到底用什么来去表示元素

数据元素它到底是个什么玩意?

参考文献(特别感谢snowylake ,垃圾必应中文搜索确实不大行)

C/C++里面能实现表到数据结构的转化的

应该是只有结构体和类两种方法了

不过这两种确实也已经够呛了


顺序表是什么?

顺序表是在计算机内存中以数组的形式保存的线性表,

是指用一组地址连续的存储单元依次存储数据元素的线性结构。

在C/C++里面就是借助数组类型来实现顺序表的

数组大小要大于线性表的长度

同时下标位置和逻辑顺序也和数组一样是错位的

第一个元素A1是存储在对应下标为0的位置上


顺序表的特点

只要确定了任一元素的位置

剩下的元素都能通过下标计算出位置

线性表里我们提到过顺序存储结构的特点

就是像数组一样元素紧密连接

假设知道了A1的位置

那么剩下所有的位置都可以通过下标来推

Loc(ai)=Loc(a1)+(i−1)∗L,1≤i≤n


代码怎样写才算顺序表

顺序表有没有相对规范的代码实现呢

我们说到算法是有优劣之分的

实现顺序表并没有什么标准答案

原则上说你只要实现了线性表的顺序存储结构

并且通过函数封装实现了顺序表的基本操作

这样的代码就可以算作顺序表


顺序表的定义

某种意义上我们可以把顺序表理解为数组的再封装

顺序表的实现需要依托数组

所以需要根据元素的数量去定义一个常量

作为数组的大小

一般会用预处理语句在程序开头去进行定义

#define MaxSize 100

或者 const MaxSize = 100;

关于定义等计算之后都会给出C和C++两种说明

//C结构体的写法

//以下是书上讲的写法

typedef struct
{    Elemtype data[MaxSize];
     int length;
}SqList;

typedef作为一个关键字本身的作用是

为一个数据类型赋予新的名字

方便记忆和后续的重复使用

在这里放在结构体定义的前面

在主函数声明结构体变量的时候就不用加上struct了

同时定义函数的时候也只需要结构体变量名就可以了

Elemtype是一个实际上并不存在的东西

它的意思是元素的类型

也就是说这里应该int double之类的类型

一种结构中的类型是多样的

为了方便说明所以数据结构书上会用这个来代指

除了特别的说明以为默认都是int类型

为什么又定义了一个length呢?

不是已经有了MaxSize了吗

前面已经说过了,顺序表和数组关系紧密但不代表它就是数组

数组里存放的是顺序表里的元素,顺序表本身也需要大小的限定

//动态数组的写法

typedef struct Table{
    int * head;//声明了一个名为head的长度不确定的数组,也叫“动态数组”
    int length;//记录当前顺序表的长度
    int size;//记录顺序表分配的存储容量
}table;

//C++类的写法

class SqList{
    public:
        SqList();
    private:
        Elemtype data[Maxsize];
        ing length;
};

public里面除了构造函数应该还有其它函数的定义的

这里因为图方便所以就把它省略掉了


顺序表的初始化和各种运算

因为作为一个整体会比较好理解

所以我分别把几种写法分开并且写上注释

//书上的代码实现

(这里一定要提的是书上的方法会比较的复杂)

(这种半C半C++的写法不能说它有什么毛病)

(但是这么杂糅的话不太好理解,可能之后水平提高后能更好掌握这种方法)

(总之现阶段我并不推荐使用书上的写法)

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
typedef char Elemtype;

typedef struct{
    Elemtype data[MaxSize];
    int length;
}SqList;

void InitList(SqList *&L){
    L=(SqList *)malloc(sizeof(SqList));
    //分配存放线性表的空间
    L->length = 0;//线性表长度清零 
}//初始化顺序表 

//采用顺序表指针方便了释放算法的设计 
//在函数之间传递顺序表指针时会节省为形参分配的空间 

void CreatList(SqList *&L,Elemtype a[],int n){
    //用了另一个新数组a往顺序表里传入0~n-1对应的几个元素 
    int i=0,k=0;//k是L中元素的个数,其实就是顺序表的长度 
    L=(SqList *)malloc(sizeof(SqList));
    //分配存放线性表的空间
    //malloc函数放在之后讲 
    while(i<n){
        L->data[i] = a[i];
        k++;
        i++; 
    }
    //填充L对应的数组data 
    L->length = k;//更新线性表的长度 
}//创建顺序表 

void DestroyList(SqList *&L){
    free(L);
}//释放内存 

bool ListEmpty(SqList *L){
    return(L->length == 0);
}//判断线性表是不是空表 

int ListLength(SqList *L){
    return(L->length);
}//返回顺序表的长度 

void DisList(SqList *L){
    for(int i=0;i<L->length;i++){
        printf("%c", L->data[i]);
        printf("\n");
    }
}//输出顺序表的元素

bool GetElem(SqList *L,int i,Elemtype &e){
    if(i<1||i>L->length){
        return false;
    }
    e = L->data[i-1];
    return true;
}//求线性表中某个数据的元素值 

int LocateElem(SqList *L,Elemtype e){
    int i=0;
    while(i<L->length && L->data[i]!=e){
        i++;
        if(i<=L->length){
            return 0;
        }else{
            return i+1;
        }
    }
}
//按元素值查找元素,如果找不到就返回0
//找到了返回逻辑序号(不是下标) 

bool ListInsert(SqList *&L,int i,Elemtype e){
    int j;
    if(i<1||i>L->length+1){
        return false;
    }//错误筛查 
    i--;//逻辑序号转化为下标 
    for(j=L->length;j>i;j--){
        L->data[j]=L->data[j-1];
    }//在插入位置后的元素全部后移一个位置 
    L->data[i]=e;//插入元素 
    L->length++;//顺序表长度+1 
    return true;
}//插入数据元素

bool LiseDelete(SqList *&L,int i,Elemtype &e){
    int j;
    if(i<1||i>L->length){
        return false;
    }//错误判断
    i--;//转化下标 
    e = L->data[i];
    for(j=i;j<L->length;j++){
        L->data[j]=L->data[j+i];
    }//对应位置之后的元素直接向前覆盖 
    L->length--;//顺序表长度减一 
    return true;
}//删除第i个元素的值 

int main(){
    SqList L;
    SqList *P = &L;
    
    char a[6]={'a','b','c','d','e','\0'};
        
    InitList(P);	
    CreatList(P,a,5);
    DisList(P);
    
    return 0;
} 

malloc函数到底是什么呢?

单看文档对api的解释是

分配所需的内存空间

并返回一个指向它的指针

L=(SqList *)malloc(sizeof(SqList));

L是一个指针,指向的结构体

malloc函数给这个结构体分配了对应大小的空间

sizeof运算符在这里返回了SqList所占的空间

 

//C++类的实现方法

(因为是我个人写的所以并不是很好不过可以帮助理解)

#include<iostream>
using namespace std;
#define MaxSize 100
typedef char Elemtype;

class SqList {
    public:
        SqList();
        void InsertElem(); 
        void OutputElem();
        void OutputLength();
        void BoolEmpty();
        void OutputOneElem(int e);
        void OutputLocation(Elemtype a);
        void InsertToLocation(int n,Elemtype f);
        void DeleteInLocation(int n);
        void ReleaseSqlist();
    private:
        Elemtype data[MaxSize];
        int length;	
        
};

SqList::SqList(){
    length = 0;
}//初始化 

void SqList::InsertElem(){
    cout<<"要插入多少个元素呢?"<<endl;
    cin>>length;
    for(int i=0;i<length;i++){
        cout<<"请输入第"<<i+1<<"个元素"<<endl;
        cin>>data[i];
    }
}//插入元素 

//void SqList::InsertElem(char a[],int n){
    //for(int i=0;i<n;i++){
        //data[i]=a[i];
    //}
//}

//插入元素的另一种写法,是书上的那种
//把另外一个数组拷贝到结构体中定义的数组里 

void SqList::OutputElem(){
    for(int i=0;i<length;i++){
        cout<<data[i]<<" ";
    }
    cout<<endl;
}//输出元素 

void SqList::OutputLength(){
    cout<<"顺序表的长度为"<<length<<endl; 
}//输出长度

void SqList::BoolEmpty(){
    if(length != 0){
        cout<<"顺序表不为空"<<endl;	
    }else{
        cout<<"顺序表为空"<<endl;
    }
}//判断是否为空 

void SqList::OutputOneElem(int e){
    cout<<"第"<<e<<"个元素的值为"<<data[e-1]<<endl; 
}//输出第e个元素的值 

void SqList::OutputLocation(Elemtype a){
    bool ElemTrue = false;
    int i=0;
     
    for(i=0;i<length;i++){
        if(data[i] == a){
            ElemTrue = true;
            break;
        }
    }
    if(ElemTrue){
        cout<<"该元素是第"<<i+1<<"个元素"<<endl;
    }else{
        cout<<"未找到该元素"<<endl;
    }
    
}//输出元素a的位置

void SqList::InsertToLocation(int n,Elemtype f){
    for(int i=length;i>n-1;i--){
        data[i]=data[i-1];
    }
    data[n-1]=f;
    length++;
}//在第n个位置上插入元素f

void SqList::DeleteInLocation(int n){
    for(int i=n-1;i<length-1;i++){
        data[i]=data[i+1];
    }
    length--;
}//删除顺序表的第n个元素

void SqList::ReleaseSqlist(){
    
}

int main(){
    SqList L;
    L.InsertElem();
    L.OutputElem();
    L.OutputLength();
    L.BoolEmpty();
    L.OutputOneElem(3);
    L.OutputLocation('c');
    L.InsertToLocation(4,'f');
    L.OutputElem();
    L.DeleteInLocation(3);
    L.OutputElem();
    
    return 0;
}

 

//类模板的实现方法

这里打算直接贴网址了

https://blog.csdn.net/pipihan21/article/details/104399591


参考文献

http://data.biancheng.net/view/158.html

https://blog.csdn.net/mpp_king/article/details/70229150

https://blog.csdn.net/pipihan21/article/details/104399591

https://blog.csdn.net/wanzhen4330/article/details/81627034

《实现顺序表的各种基本运算》有1个想法

  1. Pingback: 数据结构第五版——第二章课后实验题 – 海星peter的海滩

发表评论

您的电子邮箱地址不会被公开。