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

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;
}

百度已收录

Last modification：September 21st, 2019 at 12:43 am