免费舆情信息网站,域名大全 二级域名,网站开发排期表,深圳大胜上海数据结构与算法 #x1f388;1.线性表#x1f50e;1.1基本操作#x1f50e;1.2线性表的存储结构 #x1f388;2.线性表的顺序表示和实现#x1f50e;2.1线性表的顺序存储表示#x1f52d;2.1.1静态顺序表#x1f52d;2.1.2动态顺序表 #x1f50e;2.2顺序表基本操作的实… 数据结构与算法 1.线性表1.1基本操作1.2线性表的存储结构 2.线性表的顺序表示和实现2.1线性表的顺序存储表示2.1.1静态顺序表2.1.2动态顺序表 2.2顺序表基本操作的实现2.2.1线性表顺序存储的类定义2.2.2顺序表的初始化2.2.3销毁顺序表2.2.4查找操作2.2.5插入操作2.2.6删除操作2.2.7倒置操作2.2.8合并操作2.2.9打印操作2.2.10全部代码 1.线性表 线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就是说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理存储时通常以数组和链式结构的形式存储。 1.1基本操作
//构造一个空的线性表
InitList(L)//初始条件线性表L已经存在
//操作结果销毁线性表L
DestroyList(L)//初始条件线性表L已经存在
//操作结果将线性表L置为空表
ClearList(L)//初始条件线性表L已经存在
//操作结果若线性表L为空表则返回TURE,否则返回FALSE
ListEmpty(L)//初始条件线性表L已经存在
//操作结果返回线性表L中的数据元素个数
ListLength(L)//初始条件线性表L已经存在,1iListLength(L)
//操作结果用e返回线性表L中的第i个数据元素的值
GetElem(L,i,e)//初始条件线性表L已经存在,compare()是数据元素判定函数
//操作结果返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0.
LocateElem(L,e,compare())//初始条件线性表L已经存在
//操作结果若cur_e是L的数据元素且不是第一个则用pre_e返回它的前驱否则操作失败pre_e无意义
PriorElem(L,cue_e,pre_e)//初始条件线性表L已经存在
//操作结果若cur_e是L的数据元素且不是最后一个则用next_e返回它的后继否则操作失败next_e无意义
NextElem(L,cue_e,next_e)//初始条件线性表L已经存在,1iListLength(L)
//操作结果在L的第i个位置之前插入新的元素eL的长度1
ListInsert(L,i,e)//初始条件线性表L已经存在,1iListLength(L)
//操作结果删除L的第i个数据元素并用e返回其值L的长度-1
ListDelete(L,i,e)//初始条件线性表L已经存在
//操作结果 依次对线性表中每个元素调用visited()
ListTraverse(L,visited())1.2线性表的存储结构 在计算机内线性表有两种基本的存储结构顺序存储结构和链式存储结构 2.线性表的顺序表示和实现 线性表的顺序表示又称顺序存储结构或顺序映像。 2.1线性表的顺序存储表示 顺序存储定义把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。 线性表的第1个数据元素a1的存储位置称为线性表的起始位置或基地址。
注线性表的顺序存储结构占用一片连续的存储空间知道某个元素的存储位置就可以计算其他元素的存储位置。
假设线性表的每个元素需占l和存储单元那么第i1个元素的存储位置和第i个元素的存储位置之间满足关系Loc(ai1)Loc(ai)l. 由此所有数据元素的存储位置均可由第一个数据元素是存储位置得到Loc(ai)Loc(a1)(i-1)*l,这里的Loc(a1)称为基地址。
通过上面的学习我们发现顺序表中元素具有以下特点地址连续依次存放随机存取类型相同。这些让我们想到了一维数组但是我们也发现了线性表的长可变存在插入和删除操作而数组长度不可动态定义。因此我们需要用一个变量表示顺序表的长度属性。
#define List_Init_Size 100//线性表存储空间的初始分配量
typedef struct
{ElemType elem[List_Init_Size];int length;//当前长度
}SqList;顺序表一般可以分为
静态顺序表使用定长数组存储元素动态顺序表使用动态开辟的数组存储
2.1.1静态顺序表
//顺序表的静态存储
#define N 1000
typedef double SLDataType;
typedef struct SeqList
{SLDataType arr[N];//定长数组int size;//有效数据的个数//表示数组中存储了多少个数据
}SL;2.1.2动态顺序表
//顺序表的动态存储
typedef struct SeqList
{SLDataType* arr;//指向动态开辟的数组int size;//表示数组中存储了多少个数据int capacity;//数组实际能存数据的空间容量是多大
}SL;
SL L;
L.arr (SLDataType*)malloc(sizeof(SLDataType)*MaxSize);补充C语言的内存动态分配
malloc(m)函数开辟m字节长度的地址空间并返回这段空间的首地址。sizeof(x)运算计算变量x的长度free (p函数释放指针p所指向变量的存储空间即彻底删除一个变量。
注需要添加头文件#include stdlib.h!
补充C的内存动态分配
new 类型名T 初值列表
//功能申请用于存放T类型对象的内存空间并依初值列表赋以初值
//结果值
//成功T类型的指针指向新分配的内存
//失败0NULL
int *p1 new int;
//或者 int *p1 new int(10);delete 指针p
//功能释放指针p所指向的内存p必须是new操作的返回值。
delete p1;补充C中的参数传递
函数调用时传送给形参表的实参必须与形参三个一致类型、个数、顺序参数传递有两种方式传值参数为整型、实型、字符型以及传址参数为指针变量、引用类型、数组名 2.2顺序表基本操作的实现
//初始化操作建立一个空的线性表L
InitList(L)//摧毁已存在的线性表L
DestroyList(L)//将线性表清空
ClearList(L)//在线性表L中第i个位置插入新元素e
ListInsert(L,i,e)//删除线性表L中第i个位置元素用e返回
ListDelete(L,i,e)//若线性表为空返回1,否则返回0
ListEmpty(L)//返回线性表L的元素个数
ListLength(L)//L中查找与给定值e相等的元素若成功返回该元素在表中的序号否则返回0
LocateElem(L,e)//将线性表L中的第i个位置元素返回给e
GetElem(L,i,e)2.2.1线性表顺序存储的类定义
#define initlistsize 100
#define increment 10
class Sqlist
{
private:ElemType* elem;int listsize;int length;
public:Sqlist();//构造函数初始化顺序表建立一个空表~Sqlist();//析构函数销毁一个顺序表void InitList(int n);//创建n个元素的空表int LocateList(ElemType x);//查找值等于x的结点若存在返回下标否则返回-1void InsertList(int pos, ElemType e);//在顺序表的第pos位置上插入元素evoid DeleteList(int pos, ElemType e);//删除第pos位置上的元素且把值赋给evoid TurnList();//顺序表的倒置void MergeList(Sqlist la, Sqlist lb);//两个顺序表合并void print();//打印顺序表
};2.2.2顺序表的初始化
Sqlist::Sqlist()//构造函数创建一个长度为0容量为initlistsize的空表
{elem new ElemType[initlistsize];//申请大小为inilistsize的空表listsize initlistsize;//设置当前顺序表空间大小length 0;//设置当前顺序表的元素个数为0
}该算法中无循环语句算法的时间复杂度为O(1). 2.2.3销毁顺序表
Sqlist::~Sqlist()
{delete[]elem;//释放顺序表所占有的存储空间listsize 0;length 0;
}该算法中无循环语句算法的时间复杂度为O(1). 2.2.4查找操作 在顺序表中查找第一个值等于x的元素找到后返回该元素的下标。若元素不存在则返回-1. int Sqlist::LocateList(ElemType x)
{int i 0;for (i 0; i length; i){if (x elem[i])return i;return -1;}
}本算法中存在for循环时间复杂度为O(length). 2.2.5插入操作 该基本操作是在顺序表第pos1poslength1个位置上插入新元素e若pos位置不正确则出错处理若当前存储空间已满时需重新申请新空间并作相应处理否则将顺序表原来第pos个元素开始后移一个位置。移动顺序从右向左腾出一个位置插入新元素最后顺序表元素个数1具体图示如下 void Sqlist::InsertList(int pos, ElemType e)
{if (pos1 || poslength 1)//pos位置不正确则出错处理return;if (length listsize){ElemType *elem1 new ElemType[initlistsize increment];//顺序表已满申请新空间int i 0;for (i 0; i length; i){elem1[i] elem[i];//复制元素}delete[]elem;//释放旧空间elem elem1;listsize increment;//调整顺序表空间大小}ElemType* p elem[pos - 1];//注意这里的取地址ElemType* q elem[length - 1];for (; p q; q--)//从右往左移{*(q 1) *q;}*p e;//插入元素length;//长度1
}本算法的时间复杂度主要处决于元素的移动次数假设该顺序表共有n个元素当我们要插入的位置是第一个那么我们需要移动n次当我们插入的位置为n1时那么需要移动的次数是0次。此时时间复杂度为O(n). 2.2.6删除操作 该基本操作是在顺序表中删除第pos(1poslength)位置上的数据元素并把值赋给e。若pos位置不正确则出错处理否则将顺序表第pos个元素之后的所有元素向前移动一个位置。移动顺序为从左往右最后顺序表元素个数-1删除顺序表的变化过程如下图所示 void Sqlist::DeleteList(int pos, ElemType e)
{if (pos1 || poslength)//删除位置不合理出错处理return;ElemType* p elem[pos - 1];//注意这里的取地址ElemType* q elem[length - 1];e *p;//把删去的元素的值赋给efor (; p q; p)//从左往右移{*p *(p1);}length--;//长度-1
}本算法的时间复杂度主要处决于元素的移动次数假设该顺序表共有n个元素当我们要删除的位置是第一个那么我们需要移动n-1次当我们删除的位置为n时那么需要移动的次数是0次。因此时间复杂度为O(n). 2.2.7倒置操作 该基本操作是顺序表的倒置基本思想是第1个数据元素与最后一个数据元素进行交换第2个数据元素与最后第2个元素交换以此类推直到所有元素交换完为止。 void Sqlist::TurnList()
{ElemType* p elem;ElemType* q elem[length - 1];ElemType* temp new ElemType;for (; p q; p, q--){*temp *p;*p *q;*q *temp;}
}本算法时间复杂度为O(n). 2.2.8合并操作 已知2个顺序表la和lb按值非递减有序排列把这两个顺序表合并成一个新的顺序表lc,且lc中元素仍然按值非递减排列注lc中元素存放在私有成员elem指向的存储空间中。 void Sqlist::MergeList(Sqlist la, Sqlist lb)
{length la.length lb.length;ElemType* pa la.elem, * pa_last elem[la.length - 1];ElemType* pb lb.elem, * pb_last elem[lb.length - 1];ElemType* pc elem;while (pa pa_last pb pb_last)//按值非递减合并la和lb{if (*pa *pb){*pc *pa;}else{*pc *pb;}}while (pb pb_last)//合并顺序表lb的剩余元素{*pc *pb;}while (pa pa_last)//合并顺序表la的剩余元素{*pc *pa;}
}2.2.9打印操作
void Sqlist::print()
{int i 0;for (i 0; i length; i){cout elem[i] ;}cout endl;
}本算法时间复杂度为O(length). 2.2.10全部代码
#include iostream
using namespace std;
#define initlistsize 100
#define increment 10
typedef int ElemType;
class Sqlist
{
private:ElemType* elem;int listsize;int length;
public:Sqlist();//构造函数初始化顺序表建立一个空表~Sqlist();//析构函数销毁一个顺序表void InitList(int n);//创建n个元素的空表int LocateList(ElemType x);//查找值等于x的结点若存在返回下标否则返回-1void InsertList(int pos, ElemType e);//在顺序表的第pos位置上插入元素evoid DeleteList(int pos);//删除第pos位置上的元素且把值赋给evoid TurnList();//顺序表的倒置void MergeList(Sqlist la, Sqlist lb);//两个顺序表合并void print();//打印顺序表
};
Sqlist::Sqlist()//构造函数创建一个长度为0容量为initlistsize的空表
{elem new ElemType[initlistsize];//申请大小为inilistsize的空表listsize initlistsize;//设置当前顺序表空间大小length 0;//设置当前顺序表的元素个数为0
}
Sqlist::~Sqlist()
{delete[]elem;//释放顺序表所占有的存储空间listsize 0;length 0;
}
void Sqlist::InitList(int n)
{length n;int i 0;for (i 0; i n; i){cin elem[i];}
}
int Sqlist::LocateList(ElemType x)
{cout 查找 x 所在位置 endl;int i 0;for (i 0; i length; i){if (x elem[i])cout 找到了是第 i 1 个元素 endl;}return -1;
}
void Sqlist::InsertList(int pos, ElemType e)
{if (pos1 || poslength 1)return;if (length listsize){ElemType *elem1 new ElemType[initlistsize increment];//顺序表已满申请新空间int i 0;for (i 0; i length; i){elem1[i] elem[i];//复制元素}delete[]elem;//释放旧空间elem elem1;listsize increment;//调整顺序表空间大小}ElemType* p elem[pos - 1];//注意这里的取地址ElemType* q elem[length - 1];for (; p q; q--)//从右往左移{*(q 1) *q;}*p e;//插入元素length;//长度1
}
void Sqlist::DeleteList(int pos)
{ElemType* e new ElemType;if (pos1 || poslength)//删除位置不合理出错处理return;ElemType* p elem[pos - 1];//注意这里的取地址ElemType* q elem[length - 1];*e *p;//把删去的元素的值赋给efor (; p q; p)//从左往右移{*p *(p1);}length--;//长度-1cout 删除的元素是 *eendl;
}
void Sqlist::TurnList()
{ElemType* p elem;ElemType* q elem[length - 1];ElemType* temp new ElemType;for (; p q; p, q--){*temp *p;*p *q;*q *temp;}
}
void Sqlist::MergeList(Sqlist la, Sqlist lb)
{length la.length lb.length;ElemType* pa la.elem, * pa_last la.elem[la.length - 1];ElemType* pb lb.elem, * pb_last lb.elem[lb.length - 1];ElemType* pc elem;while (pa pa_last pb pb_last)//按值非递减合并la和lb{if (*pa *pb){*pc *pa;}else{*pc *pb;}}while (pb pb_last)//合并顺序表lb的剩余元素{*pc *pb;}while (pa pa_last)//合并顺序表la的剩余元素{*pc *pa;}int i 0;for (i 0; i length; i){cout elem[i] ;}
}
void Sqlist::print()
{int i 0;for (i 0; i length; i){cout elem[i] ;}cout endl;
}
int main()
{Sqlist L,la,lb,lc;L.InitList(10);L.print();L.LocateList(5);cout 倒置前;L.print();L.TurnList();cout 倒置后;L.print();L.InsertList(5, 9);cout 在下标为5的位置插入9后;L.print();L.DeleteList(3);cout 删除第3个元素后;L.print();cout 线性表la的元素为;la.InitList(5);cout 线性表lb的元素为;lb.InitList(5);cout 合并后的线性表为;lc.MergeList(la, lb);return 0;}✅ 运行示例 好啦关于顺序表的知识点到这里就结束啦后期会继续更新数据结构与算法的相关知识欢迎大家持续关注、点赞和评论❤️❤️❤️
