线性表能够表示什么样的数据结构,线性表是一种线性的数据结构
Yyds干货库存
线性列表定义:
由相同数据元素组成的一种线性结构,以形成有序序列。
1.线性表元素的个数称为线性表的长度。
2.当线性表中没有元素时,称为空表。
3.表格的起始位置称为页眉,表格的结束位置称为页脚。
线性表的顺序表示是指一组具有连续地址的存储单元对线性表的数据元素进行顺序存储。(使用数组的连续存储空间顺序来存储线性表的元素)
# # #主要实施操作
我们来回忆一下C语言中一个函数的用法——malloc。
参考链接
创建一个空的序列表。
1.申请一个结构,空间优先
2.将指针指向Last,并将其赋值为-1
3.返回指针
1.需要一个线性表,和线性表结构指针。
2.用循环逐个遍历,比较值是否相等,找到就返回存储位置,找不到就返回-1。
注意:先移动,再插入。
1.判断表是否已满以及插入位置的合法性(即在最大应用空间[数组大小]和表的长度内)
2.以相反的顺序将I后面的元素向后移动,并插入新元素。
向前移动I之后的所有元素。
1.检查删除位置的合法性(是否在表的长度范围内)
2.在我从左向右前进后移动数字。
线性表的链式存储
不要求两个逻辑上相邻的元素在物理上也相邻;通过“链”建立其数据元素之间的逻辑关系
即删除和插入不需要移动数据元素,只需要修改“链”即可。
链表的每个节点都是一个结构。
` ` c
类列表节点//列表节点类定义
类列表节点//列表节点类定义
{
公共:
int数据;//表示节点对应的数据。
ListNode * next//下一个节点next指针的位置
ListNode(){ next=NULL;}
};
# # #主要实施操作
# # # #查找表格长度
因为链表不像顺序表那样类似于数组,我们不知道表的长度是多少,只知道链表的头指针。
1.设置一个指向链表头的临时指针P。
2.然后使用一个循环来遍历链表,每遍历一个长度就加一个。
3.返回长度
在数组中查找指定位置的元素非常方便,直接返回即可,但是我们需要在链表中进行遍历。
1.设置一个指向链表头的临时指针P。
2.设i=1(P指向第一个元素)表示P指向哪个元素。
3.使用循环(表不为空,i k(您正在寻找的位置元素))
1.先构造一个新节点,用s指向它;
2.找到链表的第I-1个节点,用P指向;
3.然后修改指针并插入节点(在P后插入新节点)
` ` c
p-next=s;
s-next=p-next;
1.找到链表的第I-1个节点,用P指向它;
2.然后用S指针指向要删除的节点(P的下一个节点)
3.然后修改指针删除s指向的节点。
` ` c
s=p-next;
p-next=s-next;
删除s;
DS序列表-类实现(创建、插入、删除、查找)
` ` c
//A. DS序列表类实现
#包括iostream
使用命名空间std
#定义ok 0;
#定义错误-1;
//顺序表类定义
类别列表
{
私人:
int * list//元素数组
int maxsize//序列表的最大长度
int大小;//序列表的实际长度
公共:
seq list();//构造函数
~ SeqList();//析构函数
int list _ size(int a);//获取序列表的实际长度
int list_insert(int i,int item);//插入一个元素,参数是插入的值和位置
int list _ del(int I);//删除一个元素,参数是删除的位置
int list _ get(int I);//获取一个元素,参数是获取的位置
void list _ display();//输出
};
SeqList:SeqList()
{
maxsize=1000
大小=0;
list=new int[maxsize];
}
SeqList:~SeqList()
{
删除[]列表;//回收空间
}
int SeqList:list_size(int a)
{
list[size]=a;
尺寸;
返回大小;
}
int SeqList:list_insert(int i,int item)
{
if (i 0 i size 1)
{
cout错误endl
返回0;
}
其他
{
for(int j=size;j I-1;j -)
{
list[j]=list[j-1];
}
list[I-1]=item;
尺寸;
list _ display();
返回0;
}
}
int SeqList:list_del(int i)
{
if (i=0 i大小)
{
cout错误endl
返回0;
}
其他
{
for(int j=I-1;j尺码-1;j)
{
list[j]=list[j 1];
}
尺寸-;
list _ display();
}
返回0;
}
int SeqList:list_get(int i)
{
if (i 0 i=size)
{
cout list[I-1]endl;
返回列表[I-1];
}
其他
{
标准输出错误恩德尔
返回0;
}
}
void SeqList:list_display()
{
标准输出大小
for(int I=0;我尺寸;我)
{
标准输出列表[我]
}
cout结束
}
int main()
{
int n,a;
CIN n;
序列列表S;
for(int j=0;j j)
{
CIN a;
s。list _ size(a);
}
s。list _ display();
int i,item
宫颈癌前病变一号项目;
S.list_insert(i,item);
宫颈癌前病变一号项目;
S.list_insert(i,item);
宫颈癌前病变一世;
s。list _ del(I);
宫颈癌前病变一世;
s。list _ del(I);
宫颈癌前病变一世;
s。list _ get(I);
宫颈癌前病变一世;
s。list _ get(I);
返回0;
}
![屏幕截图20220908 191220 .jpg】(https://s 2.51 CTO。com/images/20220908/1662635642772529。jpg?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type _ zm fuz 3 poz w5 nagvpdgk=/resize,m_fixed,w_750)
![屏幕截图20220908 203923 .jpg】(https://s 2.51 CTO。com/images/20220908/1662640779654281。jpg?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type _ zm fuz 3 poz w5 nagvpdgk=/resize,m_fixed,w_750)
### DS顺序表-连续操作
![屏幕截图20220908 191456 .jpg】(https://s 2.51 CTO。com/images/20220908/1662635706551355。jpg?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type _ zm fuz 3 poz w5 nagvpdgk=/resize,m_fixed,w_750)
` ` c
//DS顺序表-连续操作
#包括输入输出流
使用命名空间标准
#定义ok 0;
#定义错误-1;
//顺序表类定义
类别列表
私人:
int * list//元素数组
int maxsize//顺序表最大长度
(同Internationalorganizations)国际组织大小;//顺序表实际长度
公共:
seq list();//构造函数
~ SeqList();//析构函数
int list _ size(int a);//获取顺序表实际长度
int list_insert(int i,int n,int item[]);//插入一个元素,参数是插入的数值和位置
int list_del(int i,int n);//删除一个元素,参数是删除的位置
void list _ display();//输出
SeqList:SeqList()
maxsize=1000
大小=0;
list=new int[maxsize];
SeqList:~SeqList()
删除[]列表;//回收空间
int SeqList:list_size(int a)
list[size]=a;
尺寸;
返回大小;
int SeqList:list_insert(int i,int n,int item[])
if(I 1 I size 1 I in maxsize)
//cout " error " endl;
返回0;
其他
for(int j=size-1;j=I-1;j -)
list[j n]=list[j];
for(int j=I-1;j I n-1;j)
list[j]=item[j-I 1];
size=n;
list _ display();
返回0;
int SeqList:list_del(int i,int n)
如果(我^ 1 我^ n-1大小 我大小)
//cout " error " endl;
返回0;
其他
for(int j=I-1;j尺寸-n;j)
list[j]=list[j n];
size-=n;
list _ display();
返回0;
void SeqList:list_display()
标准输出大小"";
for(int I=0;我尺寸;我)
标准输出列表【我】”;
cout结束
int main()
int n,a;
CIN n;
序列列表S;
for(int j=0;j j)
CIN a;
s。list _ size(a);
s。list _ display();
int i,f;
宫颈癌前病变一世f;
int * item=new int[f];
for(int I=0;我我)
宫颈癌前病变项目[一];
S.list_insert(i,f,item);
宫颈癌前病变一世f;
S.list_del(i,f);
返回0;
}
鐽顺序表-合并操作
` ` c
//DS顺序表-合并操作
#包括输入输出流
使用命名空间标准
#定义ok 0;
#定义错误-1;
//顺序表类定义
类别列表
{
私人:
int * list//元素数组
int maxsize//顺序表最大长度
(同Internationalorganizations)国际组织大小;//顺序表实际长度
公共:
seq list();//构造函数
~ SeqList();//析构函数
int list _ size(int a);//获取顺序表实际长度
void list_insert(SeqList s1,seq list S2);//插入一个元素,参数是插入的数值和位置
void list _ display();//输出
};
SeqList:SeqList()
{
maxsize=1000
大小=0;
list=new int[maxsize];
}
SeqList:~SeqList()
{
删除[]列表;//回收空间
}
int SeqList:list_size(int a)
{
list[size]=a;
尺寸;
返回大小;
}
撤消序列列表:list _ insert(序列列表S1,序列列表s2)
{
大小=S1。大小S2。尺寸;
int a=0,b=0,I=0;
而(a s1 .尺寸b s2 .尺寸)
{
if (s1.list[a] s2.list[b])
S1。列表[a];
a;
我;
其他
S2。列表[b];
b;
我;
白色(s1 .大小)
S1。列表[a];
a;
我;
while (b s2.size)
S2。列表[b];
b;
我;
list _ display();
}
void SeqList:list_display()
{
标准输出大小
for(int I=0;我尺寸;我)
{
标准输出列表[我]
}
cout结束
}
int main()
{
int n,m,a;
CIN n;
SeqList s1
for(int I=0;我我)
{
CIN a;
S1。list _ size(a);
}
CIN m;
SeqList s2
for(int I=0;我我)
CIN a;
S2。list _ size(a);
序列列表S;
S.list_insert(s1,S2);
返回0;
}
![屏幕截图20220908 203309 .jpg】(https://s 2.51 CTO。com/images/20220908/1662640409298310。jpg?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type _ zm fuz 3 poz w5 nagvpdgk=/resize,m_fixed,w_750)
### DS顺序表之循环移位
![屏幕截图20220908 204216 .jpg】(https://s 2.51 CTO。com/images/20220908/1662640947841589。jpg?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type _ zm fuz 3 poz w5 nagvpdgk=/resize,m_fixed,w_750)
` ` c
//DS顺序表之循环移位
#包括输入输出流
使用命名空间标准
#定义ok 0;
#定义错误-1;
//顺序表类定义
类别列表
私人:
int * list//元素数组
int maxsize//顺序表最大长度
(同Internationalorganizations)国际组织大小;//顺序表实际长度
公共:
seq list();//构造函数
~ SeqList();//析构函数
int list _ size(int a);//获取顺序表实际长度
void list_insert(int d,int t);//插入一个元素,参数是插入的数值和位置
void list _ display();//输出
SeqList:SeqList()
maxsize=1000
大小=0;
list=new int[maxsize];
SeqList:~SeqList()
删除[]列表;//回收空间
int SeqList:list_size(int a)
list[size]=a;
尺寸;
返回大小;
void SeqList:list_insert(int d,int t)
int * temp=new int[size];
for(int I=0;我尺寸;我)
temp[I]=list[I];
如果(d==0)
for(int j=0;j尺寸-t;j)
list[j]=temp[j t];
for(int j=size-t;j尺寸;j)
list[j]=temp[j-(size-t)];
list _ display();
其他
for(int j=t;j尺寸;j)
list[j]=temp[j-t];
for(int j=0;j j)
list[j]=temp[size-t j];
list _ display();
删除[]temp;
void SeqList:list_display()
for(int I=0;我尺寸;我)
标准输出列表【我】”;
cout结束
int main()
int n,m,a;
CIN n;
SeqList s1
for(int I=0;我我)
CIN a;
S1。list _ size(a);
S1。list _ display();
int d,t;
CINdt;
s1.list_insert(d,t);
CINdt;
s1.list_insert(d,t);
返回0;
}
鐽单链表-类实现
` ` c
//vDS单链表-类实现
#包括输入输出流
使用命名空间标准
#定义ok 0;
#定义错误-1;
//链表节点类定义
类别列表节点
{
公共:
(同Internationalorganizations)国际组织数据;
ListNode *下一个
ListNode(){ next=NULL;}
};
//带头结点的单链表类定义
类别链接列表
{
公共:
链表结点头;
int len
//操作定义
LinkList();
~ LinkList();
ListNode LL_index(int t)//返回第我个结点的指针,若不存在返回空
{
if (t 0 t len)返回空
ListNode l=head
for(int I=0;我我)
{
l=l-next;
}
返回l;
}
void init(int n)
{
ListNode node=head
len=n;
整数
while (n -)
{
CIN num;
列表节点l=新的列表节点;
l-data=num;
node-next=l;
node=node-next;
}
}
int LL _ get(int I);//获取第我个元素的数据
int LL_insert(int i,int item);//把数值项目插入第我个位置
int LL _ del(int I);//删除第我个结点
void LL _ display();//输出单链表的内容
};
LinkList:LinkList()
{
head=new ListNode();
len=0;
}
链接列表:~链接列表()
{
ListNode p,* q;
p=头部;
而(p!=空)
{
q=p;
p=p-next;
删除q;
}
len=0;
head=NULL
}
(同Internationalorganizations)国际组织链表* LL _ get(int I)
{
if (i 1 i len)
{
标准输出错误恩德尔
返回空
}
其他
{
cout LL _ index(I)-data endl;
返回LL_index(i)数据;
}
}
(同Internationalorganizations)国际组织链表* LL _ insert(int I,int item)
{
if (i 1 i len 1)
{
标准输出错误恩德尔
return-1;
}
其他
{
列表节点l=LL _ index(I-1);
列表节点ll=新的列表节点;
ll-data=item;
ll-next=l-next;
l-next=ll;
低输入联网(low-entry networking的缩写)
LL _ display();
返回0;
}
}
(同Internationalorganizations)国际组织链表* LL _ del(int I)
{
if (i 1 i len)
{
标准输出错误恩德尔
return-1;
}
其他
{
列表节点l=LL _ index(I-1);
列表节点ll=l-next;
l-next=ll-next;
l=空
len-;
LL _ display();
返回0;
}
}
空的链表* LL _ display()
{
ListNode * p;
p=head-next;
while (p)
{
cout p- data
p=p-next;
}
cout结束
}
int main()
{
int n;
CIN n;
链表l;
我。初始化(n);
长度LL _ display();
int i,item
宫颈癌前病变一号项目;
长度LL_insert(i,item);
宫颈癌前病变一号项目;
长度LL_insert(i,item);
宫颈癌前病变一世;
长度LL_del(一);
宫颈癌前病变一世;
长度LL_del(一);
宫颈癌前病变一世;
长度LL _ get(I);
宫颈癌前病变一世;
长度LL _ get(I);
返回0;
}
![屏幕截图2022-09-09 094451 .jpg】(https://s 2.51 CTO。com/images/202209/91325447037 a 109783459009 a 354503 c 1190 c 0。jpg?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type _ zm fuz 3 poz w5 nagvpdgk=/resize,m_fixed,w_750)
### DS单链表-结点交换
![图片。png](https://s 2.51 CTO)。com/images/202209/14 eeca 246 b 9 facaf 4563518 af 00 c 37 c 497 e 10 c . png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type _ zm fuz 3 poz w5 nagvpdgk=/resize,m_fixed,w_750)
` ` c
//DS单链表-结点交换
#包括输入输出流
使用命名空间标准
#定义ok 0;
#定义错误-1;
//链表节点类定义
类别列表节点
公共:
(同Internationalorganizations)国际组织数据;
ListNode *下一个
ListNode(){ next=NULL;}
//带头结点的单链表类定义
类别链接列表
公共:
ListNode * head
int len
//操作定义
LinkList();
~ LinkList();
ListNode* LL_index(int t)//返回第我个结点的指针,若不存在返回空
if (t 0 t len)返回空
ListNode * l=head
for(int I=0;我我)
l=l-next;
返回l;
void init(int n)
列表节点*节点=头
len=n;
整数
while (n -)
CIN num;
ListNode* l=新的列表节点;
l-data=num;
node-next=l;
node=node-next;
int swap(int pa,int Pb);//pa和平装书表示两个结点在单链表的位置序号
int swap1(ListNode* p,list node * q);//p和q表示指向两个结点的指针
void LL _ display();//输出单链表的内容
LinkList:LinkList()
head=new ListNode();
len=0;
链接列表:~链接列表()
ListNode* p,* q;
p=头部;
而(p!=空)
q=p;
p=p-next;
删除q;
len=0;
head=NULL
(同Internationalorganizations)国际组织链表* swap(int pa,int pb)
if ((pa 1 pa len) (pb 1 pb len))
cout“错误”结束
返回0;
其他
ListNode * p=LL _ index(pa-1);
ListNode * q=LL _ index(p B-1);
if (p- next==q)
p-next=q-next;
q-next=p-next-next;
p-next-next=q;
返回真实的
ListNode * t=p-next;
p-next=q-next;
q-next=t;
t=p-next-next;
p-next-next=q-next-next;
q-next-next=t;
LL _ display();
返回真实的
返回pa,Pb;
空的链表* LL _ display()
ListNode * p;
p=head-next;
while (p)
cout p-data " ";
p=p-next;
cout结束
int main()
int n;
CIN n;
链表l;
我。初始化(n);
长度LL _ display();
int pa,Pb;
CIN pa Pb;
L.swap(pa,Pb);
CIN pa Pb;
L.swap(pa,Pb);
返回0;
}
未完待续.
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。