C++常⽤数据结构                                                                                  常⽤数据结构
1.线性表
定义：
由n个具有相同性质的数据元素组成的有穷序列。
特点：
（⼀对⼀的关系）
存在唯⼀⼀个称为”第⼀个“的数据元素，它没有直接的前驱。
存在唯⼀⼀个称为“最后⼀个”的元素，他没有直接后驱。
除第⼀个数据元素以外，表中的每个数据元素有且仅有⼀个直接前驱。
除第⼀个数据元素以外，表中的每个数据元素有且仅有⼀个直接后驱。
1.1顺序表
定义：
特点：
实现：c语言listinsert函数
c语⾔实现：
c++实现：
template <typename T>
class sqlist{
public:
sqlist(int maxsize=10):Maxsize(maxsize)
{
elements=new T[maxsize];
length=0;
}
private:
int  Maxsize;//最⼤容量
T *elements;//元素初始地址
int length;//当前有效长度
};
基本操作：
}
求顺序表中当前元素的个数
//顺序表的长度
int ListLength(SqList * L)
{
return  L->length;
}
判断顺序表是否为空
//判断顺序表是否为空
bool ListEmpty(SqList *L)
{
if(L->length==0)
return true;
else
return false;
}
向顺序表中插⼊数据元素
//向顺序表中插⼊数据元素
bool ListInsert(SqList *L,int pos,int item)
{
int i;
if(L->length==LISTSIZE)
{
printf("顺序列表已满，⽆法进⾏插⼊操作");        return false;
}
if(pos<1||pos>L->length+1)
{
printf("插⼊位置不合法");
return false;
}
for(i=L->length-1;i>=pos-1;i--)
{
L->items[i+1]=L->items[i];
}
L->items[pos-1]=item;
L->length++;
return true;
}
删除顺序表中的元素
//删除顺序表中的元素
bool ListDelete(SqList *L,int pos,int *item)
{
int i;
if(L->length==0)
{
printf("顺序表为空表");
return false;
}
if(pos<1||pos>L->length)
if(pos<1||pos>L->length)
{
printf("删除位置⽆效");
}
*item=L->items[pos-1];
for(int i=pos-1;i<L->length-1;i++)
{
L->items[i]=L->items[i+1];
}
L->length--;
return true;
}
查指定元素在顺序表中的位置
//查制定元素在顺序表中的位置
int Find(SqList L,int item)
{
int pos=0;
if(ListEmpty(&L))
{
printf("顺序表为空表，⽆法进⾏查操作");        return 0;
}
while(pos<L.length&&L.items[pos]!=item)
{
pos++;
}
if(pos<L.length)
return pos+1;
else
return 0;
}
获取顺序表中指定位置上的数据元素
//获得顺序表中指定位置上的数据元素
int GetElem(SqList *L,int pos,int *item)
{
if(ListEmpty(L))
return 0;
if(pos<1||pos>L->length)
return 0;
*item=L->items[pos-1];
return 1;
}
遍历顺序表
//遍历顺序表
void TravereList(SqList *L)
{
int pos =0;
while(pos<L->length)
{
printf("item1: %d",L->items[pos]);
pos++;
}
}
c语⾔版本：
c语⾔版本：
#include <iostream>
using namespace std;
#define LISTSIZE 100
typedef struct {
int items[LISTSIZE];
int length;
} SqList;
//初始化顺序表，表的长度设置为0
void InitList(SqList *L)
{
L->length=0;
}
//顺序表的长度
int ListLength(SqList * L)
{
return  L->length;
}
//判断顺序表是否为空
bool ListEmpty(SqList *L)
{
if(L->length==0)
return true;
else
return false;
}
//向顺序表中插⼊数据元素
bool ListInsert(SqList *L,int pos,int item)
{
int i;
if(L->length==LISTSIZE)
{
printf("顺序列表已满，⽆法进⾏插⼊操作");        return false;
}
if(pos<1||pos>L->length+1)
{
printf("插⼊位置不合法");
return false;
}
for(i=L->length-1;i>=pos-1;i--)
{
L->items[i+1]=L->items[i];
}
L->items[pos-1]=item;
L->length++;
return true;
}
//删除顺序表中的元素
bool ListDelete(SqList *L,int pos,int *item)
{
int i;
if(L->length==0)
{

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。