寒光博客

[数据结构]第二章 顺序表
为了更透彻的理解细节原理 熟悉顺序存储 所以手敲了一遍 8个步骤 整数型顺序表 /** * 整数型顺序表 **...
扫描右侧二维码阅读全文
20
2019/09

[数据结构]第二章 顺序表

为了更透彻的理解细节原理 熟悉顺序存储 所以手敲了一遍
8个步骤

整数型顺序表

/**
 * 整数型顺序表
**/
#include "pch.h"
#include <iostream>

#define op(x) cout<<x<<endl

using namespace std;
//为什么用 exit(1)

//1.顺序表结构
const int MAXSIZE = 100;
typedef struct
{
    int data[MAXSIZE];
    int length;
} SeqList;

//2.创建空表
void InitList_Seq(SeqList &L)
{
    L.length = 0;
}
//3.创建长度为n的表的顺序表

void CrateList_Seq(SeqList &L, int a[], int n)
{
    if (n > MAXSIZE)
    {
        cout << "参数超出顺序表最大容量" << endl;
        return;
    }
    L.length = 0;
    for (int i = 0; i < n; i++)
    {
        L.data[L.length++] = a[i];
    }
}
//4.遍历顺序表
void Show_Seq(SeqList &L)
{
    for (int i = 0; i < L.length; i++)
        cout << "[" << L.data[i] << (i == L.length-1 ? "]" : "],");
    cout << endl;
}
//5.求顺序表的长度

int ListLength_Seq(SeqList &L)
{
    return L.length;
}
//6.顺序表查找元素
int LocateElem_Seq(SeqList &L, int e) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e)
            return i + 1;
    return -1;
}
//7.顺序表插入元素
void ListInsert_Seq(SeqList &L, int i, int e)
{
    if (L.length == MAXSIZE)//已经是最大空间了
    {
        cout << "顺序表已满" << endl;
        return;
    }
    if (i<0 || i>L.length)
    {
        cout << "插入序号i不合法" << endl;
        return;
    }
    for (int j = L.length; j >= i; --j)//注意 是j>=i 因为i是序号 所以后移到 i-1
    {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;


}
//8.顺序表删除元素
void ListDelete_Seq(SeqList &L, int i, int &e)
{
    if (i<1 || i>L.length)
    {
        cout << "删除序号i不合法" << endl;
        return;
    }
    e = L.data[i - 1];//把要删的保存下来
    for (int j = i; j < L.length; ++j)
    {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
}
int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,0 };
    SeqList one;
    InitList_Seq(one);//创建
    CrateList_Seq(one,arr,10);//把arr放入顺序表中
    Show_Seq(one);//遍历顺序表
    op(ListLength_Seq(one));//顺序表长度
    op(LocateElem_Seq(one, 7));//查找元素的序号
    int e = -1;
    ListInsert_Seq(one, 6, -1);//在序号6处插入 -1
    Show_Seq(one);//遍历顺序表
    ListDelete_Seq(one, -1, e);//删除指定序号的数字
    ListDelete_Seq(one, 5, e);
    Show_Seq(one);//遍历顺序表

    op("删除的数字是:"); op(e);

    return 0;
}

顺序表优化

数据类型任意 通用性,数组大小(灵活性) 适用性提高

/**
 * 整数型数据表
**/
#include "pch.h"
#include <iostream>

#define op(x) cout<<x<<endl

using namespace std;

//1.顺序表结构

typedef int ElemType;
typedef struct
{
    ElemType *data;
    int length;
    int MAXSIZE;
} SeqList;

//2.创建空表
void InitList_Seq(SeqList &L,int size)
{
    L.data = new ElemType[size];
    L.MAXSIZE = size;
    L.length = 0;
}
//3.创建长度为n的表的顺序表

void CrateList_Seq(SeqList &L, int size,ElemType a[], int n)
{
    //if (n > L.MAXSIZE)
    //{
        //cout << "参数超出顺序表最大容量" << endl;
        //return;
    //}
    L.data = new ElemType[size];
    L.MAXSIZE = size;
    L.length = 0;
    for (int i = 0; i < n; i++)
    {
        L.data[L.length++] = a[i];
    }
}
//4.遍历顺序表
void Show_Seq(SeqList &L)
{
    for (int i = 0; i < L.length; i++)
        cout << "[" << L.data[i] << (i == L.length - 1 ? "]" : "],");
    cout << endl;
}
//5.求顺序表的长度

int ListLength_Seq(SeqList &L)
{
    return L.length;
}
//6.顺序表查找元素
int LocateElem_Seq(SeqList &L, ElemType e) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e)
            return i + 1;
    return -1;
}
//7.1 插入时 空间不足 空间扩展函数
void increment(SeqList &L, int inerementsize)
{
    ElemType  *a;
    L.MAXSIZE += inerementsize;
    a = new ElemType[L.MAXSIZE];
    for (int i = 0; i < L.length; i++)
        a[i] = L.data[i];
    delete L.data;
    L.data = a;
    a = NULL;
}

//7.顺序表插入元素
void ListInsert_Seq(SeqList &L, int i, ElemType e)
{
    if (L.length >= L.MAXSIZE)//已经是最大空间了
    {
        increment(L, 10);
        cout << "顺序表已满,所以增加十个空间" << endl;
        return;
    }
    if (i<0 || i>L.length+1)//注意 i 是序号 不是索引
    {
        cout << "插入序号i不合法" << endl;
        exit(1);
    }
    for (int j = L.length; j >= i; --j)//注意 是j>=i 因为i是序号 所以后移到 i-1
    {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;


}

//8.顺序表删除元素
void ListDelete_Seq(SeqList &L, int i, ElemType &e)
{
    if (i<1 || i>L.length)
    {
        cout << "删除序号i不合法" << endl;
        return;
    }
    e = L.data[i - 1];//把要删的保存下来
    for (int j = i; j < L.length; ++j)
    {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
}
//9.增加的操作 释放空间
void DestoryList_Seq(SeqList &L)
{
    delete[] L.data;
    L.MAXSIZE = 0;
    L.length = 0;
}

int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,0 };
    SeqList one;
    InitList_Seq(one,10);//创建
    CrateList_Seq(one,10,arr, 10);//把arr放入顺序表中
    Show_Seq(one);//遍历顺序表
    op(ListLength_Seq(one));//顺序表长度
    op(LocateElem_Seq(one, 7));//查找元素的序号
    int e = -1;
    ListInsert_Seq(one, 6, -1);//在序号6处插入 -1
    Show_Seq(one);//遍历顺序表
    ListDelete_Seq(one, -1, e);//删除指定序号的数字
    ListDelete_Seq(one, 5, e);
    Show_Seq(one);//遍历顺序表

    op("删除的数字是:"); op(e);

    return 0;
}
本文作者:Author:     文章标题:[数据结构]第二章 顺序表
本文地址:https://dxoca.cn/dataStructure/277.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:September 21st, 2019 at 12:43 am
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment