当前位置：网站首页>Linear list (sequential storage, chain storage) (linked list of leading nodes, linked list of non leading nodes)
Linear list (sequential storage, chain storage) (linked list of leading nodes, linked list of non leading nodes)
2022-07-27 08:41:00 【Madness makes freedom】
The basic operation of linear table ：
List MakeEmpty(): Initialize a new empty linear table ;
ElementType FindKth(List L,int i): Given the specified bit order , return L The corresponding element in ai;
Position Find(List L,ElementType X) ： It is known that X, Return to linear table L China and X The same first element
The location of , If it does not exist, an error message is returned ;
bool Insert(List L,ElementType X,int i): stay L The specified bit order of i Insert an element before X, Return on success true,
Otherwise return to false;
bool Delect(List L,int i): from L Delete the specified bit order i The elements of , Return on success true, Otherwise return to false;
bool Length(List L): Return to linear table L The length of ;
/**
1) Linear table sequential storage implementation ：
*/
/**
The basic operation of linear table ：
List MakeEmpty(): Initialize a new empty linear table ;
ElementType FindKth(List L,int i): Given the specified bit order , return L The corresponding element in ai;
Position Find(List L,ElementType X) ： It is known that X, Return to linear table L China and X The same first element
The location of , If it does not exist, an error message is returned ;
bool Insert(List L,ElementType X,int i): stay L The specified bit order of i Insert an element before X, Return on success true,
Otherwise return to false;
bool Delect(List L,int i): from L Delete the specified bit order i The elements of , Return on success true, Otherwise return to false;
bool Length(List L): Return to linear table L The length of ;
*/
/**
1) Linear table sequential storage implementation ：
*/
/**
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define error -1
const int MAXSIZE = 100;
typedef int ElementType;
typedef int Position;
typedef struct LNode * PtrToLNode;
// The position here is the integer subscript of the array , from 0 Start , The bit order mentioned above refers to the number , from 1 Start
struct LNode
{
ElementType Data[MAXSIZE];
Position Last;
};
typedef PtrToLNode List;
List MakeEmpty();
ElementType FindKth(List L,int i);
Position Find(List L,ElementType X);
bool Insert(List L,ElementType X,int i);
bool Delect(List L,int i);
int Length(List L);
int main()
{
List L=MakeEmpty();
for(int i=1;i<15;++i)
Insert(L,i,i);
cout << "Insert:\n";
for(int i=0;i<=L->Last;++i)
cout << L->Data[i] << ' ';
cout << endl;
int K=20;
if(FindKth(L,K)!=error)
{
printf("\n The first %d Location found ：\n",K);
cout << " This element is " << FindKth(L,K) << endl;
}
else
printf("\n This linear table does not exist %d Element of sign \n",K);
printf(" The number of elements of the linear table is %d individual \n",Length(L));
for(int i=5;i<10;++i)
Delect(L,i);
cout << "Insert:\n";
for(int i=0;i<=L->Last;++i)
cout << L->Data[i] << ' ';
K=5;
if(FindKth(L,K)!=error)
{
printf("\n The first %d Location found ：\n",K);
cout << " This element is " << FindKth(L,K) << endl;
}
else
printf(" This linear table does not exist %d The elements of \n",K);
printf(" The number of elements of the linear table is %d individual \n",Length(L));
return 0;
}
List MakeEmpty()
{
List L;
L=(List) malloc(sizeof(LNode));
L->Last=-1;
return L;
}
ElementType FindKth(List L,int i)
{
if(i<1||i>L->Last)
{
printf(" There is no such thing as %d Element of sign \n",i);
return error;
}
else
return L->Data[i-1];
}
Position Find(List L,ElementType X)
{
Position i=0;
while(i<L->Last&&L->Data[i]!=X)
++i;
if(i>=L->Last)
return error;
else
return i;
}
bool Insert(List L,ElementType X,int i)
{
if(L->Last==MAXSIZE-1)
{
printf(" Table full \n");
return false;
}
if(i<1||i>L->Last+2)
{
printf(" Illegal bit order \n");
return false;
}
for(Position j=L->Last;j>=i-1;--j)
L->Data[j+1]=L->Data[j];
L->Data[i-1]=X;
++L->Last;
return true;
}
bool Delect(List L,int i)
{
if(L->Last<0)
{
printf(" Table empty \n");
return false;
}
if(i<1||i>L->Last+1)
{
printf(" A sequence %d There is no element \n",i);
return false;
}
for(Position j=i;j<=L->Last;++j)
L->Data[j-1]=L->Data[j];
--L->Last;
return true;
}
int Length(List L)
{
return L->Last+1;
}
*/2) Linear table chain storage implementation
Create a linked list without leading nodes , Insert , Delete
/**
2) Linear table chain storage implementation
Create a linked list without leading nodes , Insert , Delete
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define error NULL
const int MAXSIZE = 100;
typedef int ElementType;
const ElementType inf=1e9;
typedef struct LNode * PtrToLNode;
// The position here is the integer subscript of the array , from 0 Start , The bit order mentioned above refers to the number , from 1 Start
struct LNode
{
ElementType data;
PtrToLNode next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
List MakeEmpty();
ElementType FindKth(List L,int i);
Position Find(List L,ElementType X);
List Insert(List L,ElementType X,int i);
List Delect(List L,int i);
int Length(List L);
int main()
{
List L=MakeEmpty();
for(auto p=L;p;p=p->next)
cout << p->data << ' ' ;
cout << endl;
for(int i=1;i<15;++i)
{
auto tem=Insert(L,i,i);
if(tem!=error)
L=tem;
}
cout << "insert:\n";
for(auto p=L;p;p=p->next)
cout << p->data << ' ' ;
cout << endl;
printf(" The number of elements of the linear table is %d individual \n",Length(L));
int K=20;
if(FindKth(L,K)!=inf)
{
printf("\n The first %d Location found ：\n",K);
cout << " This element is " << FindKth(L,K) << endl;
}
else
printf("\n This linear table does not exist %d Element of sign \n",K);
K=5;
if(FindKth(L,K)!=inf)
{
printf("\n The first %d Location found ：\n",K);
cout << " This element is " << FindKth(L,K) << endl;
}
else
printf(" This linear table does not exist %d The elements of \n",K);
printf(" The number of elements of the linear table is %d individual \n",Length(L));
for(int i=5;i<10;++i)
{
auto tem=Delect(L,i);
if(tem!=error)
L=tem;
}
cout << "delect:\n";
for(auto p=L;p;p=p->next)
cout << p->data << ' ' ;
cout << endl;
printf(" The number of elements of the linear table is %d individual \n",Length(L));
auto tem=Delect(L,1);
if(tem!=error)
L=tem;
cout << "delect first node:\n";
for(auto p=L;p;p=p->next)
cout << p->data << ' ' ;
cout << endl;
printf(" The number of elements of the linear table is %d individual \n",Length(L));
return 0;
}
// Create a linked list without leading nodes ：
List MakeEmpty()
{
List L;
L=(List) malloc(sizeof(LNode));
L=NULL;
return L;
}
ElementType FindKth(List L,int i)
{
Position p;
int cnt=1;
p=L;
while(p&&cnt<i)
{
p=p->next;
++cnt;
}
if(p&&cnt==i)
return p->data;
else
return inf;
}
Position Find(List L,ElementType X)
{
Position p=L;
while(p&&p->data!=X)
p=p->next;
if(!p)
return error;
else
return p;
}
List Insert(List L,ElementType X,int i)
{
Position pre,tem;
tem=(Position) malloc(sizeof (LNode));
tem->data=X;
if(i==1)
{
tem->next=L;
return tem;
}
else
{
int cnt=1;
pre=L;
while(pre&&cnt<i-1)
{
pre=pre->next;
++cnt;
}
if(pre==NULL||cnt!=i-1)
{
printf(" Input position parameter error \n");
free(tem);
return error;
}
else
{
tem->next=pre->next;
pre->next=tem;
return L;
}
}
}
List Delect(List L,int i)
{
Position pre=L,tem;
if(i==1)
{
pre=L;
tem=pre->next;
free(pre);
return tem;
}
else
{
int cnt=1;
while(pre&&cnt<i-1)
{
pre=pre->next;
++cnt;
}
if(pre==NULL||cnt!=i-1)
{
printf(" Input position parameter error \n");
free(tem);
return error;
}
else
{
tem=pre->next;
pre->next=tem->next;
return L;
}
}
}
int Length(List L)
{
Position p=L;
int len=0;
while(p)
{
p=p->next;
++len;
}
return len;
}
3) Linear table chain storage implementation
Create the linked list of the leading node , Insert , Delete
/**
3) Linear table chain storage implementation
Create the linked list of the leading node , Insert , Delete
*/
/**
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define error NULL
const int MAXSIZE = 100;
typedef int ElementType;
const ElementType inf=1e9;
typedef struct LNode * PtrToLNode;
// The position here is the integer subscript of the array , from 0 Start , The bit order mentioned above refers to the number , from 1 Start
struct LNode
{
ElementType data;
PtrToLNode next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
List MakeEmpty();
ElementType FindKth(List L,int i);
Position Find(List L,ElementType X);
bool Insert(List L,ElementType X,int i);
bool Delect(List L,int i);
int Length(List L);
int main()
{
List L=MakeEmpty();
for(auto p=L->next;p;p=p->next)
cout << p->data << ' ' ;
cout << endl;
for(int i=1;i<15;++i)
Insert(L,i,i);
cout << "insert:\n";
for(auto p=L->next;p;p=p->next)
cout << p->data << ' ' ;
cout << endl;
printf(" The number of elements of the linear table is %d individual \n",Length(L));
int K=20;
if(FindKth(L,K)!=inf)
{
printf("\n The first %d Location found ：\n",K);
cout << " This element is " << FindKth(L,K) << endl;
}
else
printf("\n This linear table does not exist %d Element of sign \n",K);
K=5;
if(FindKth(L,K)!=inf)
{
printf("\n The first %d Location found ：\n",K);
cout << " This element is " << FindKth(L,K) << endl;
}
else
printf(" This linear table does not exist %d The elements of \n",K);
printf(" The number of elements of the linear table is %d individual \n",Length(L));
for(int i=5;i<10;++i)
Delect(L,i);
cout << "delect:\n";
for(auto p=L->next;p;p=p->next)
cout << p->data << ' ' ;
cout << endl;
printf(" The number of elements of the linear table is %d individual \n",Length(L));
Delect(L,1);
cout << "delect first node:\n";
for(auto p=L->next;p;p=p->next)
cout << p->data << ' ' ;
cout << endl;
printf(" The number of elements of the linear table is %d individual \n",Length(L));
}
// Create the linked list of the leading node ：
List MakeEmpty()
{
List L;
L=(List) malloc(sizeof(LNode));
L->next=NULL;
return L;
}
ElementType FindKth(List L,int i)
{
Position p;
int cnt=1;
p=L->next;
while(p&&cnt<i)
{
p=p->next;
++cnt;
}
if(p&&cnt==i)
return p->data;
else
return inf;
}
Position Find(List L,ElementType X)
{
Position p=L->next;
while(p&&p->data!=X)
p=p->next;
if(!p)
return error;
else
return p;
}
bool Insert(List L,ElementType X,int i)
{
Position pre,tem;
int cnt=1;
pre=L;
while(pre&&cnt<i)
{
pre=pre->next;
++cnt;
}
if(pre==NULL||cnt!=i)
{
printf(" Insert position parameter error \n");
return false;
}
else
{
tem=(Position) malloc(sizeof (LNode));
tem->data=X;
tem->next=pre->next;
pre->next=tem;
return true;
}
}
bool Delect(List L,int i)
{
Position pre=L,tem;
int cnt=1;
while(pre&&cnt<i)
{
pre=pre->next;
++cnt;
}
if(pre==NULL||cnt!=i||pre->next==NULL)
{
printf(" Input position parameter error \n");
return false;
}
else
{
tem=pre->next;
pre->next=tem->next;
free(tem);
return true;
}
}
int Length(List L)
{
Position p=L->next;
int len=0;
while(p)
{
p=p->next;
++len;
}
return len;
}
*/边栏推荐
猜你喜欢
How to upload qiniu cloud
redis的string类型及bitmap
Alibaba cloud international receipt message introduction and configuration process
说透缓存一致性与内存屏障
Flask request data acquisition and response
网络IO总结文
Sliding conflict of view
“寻源到结算“与“采购到付款“两者有什么不同或相似之处？
Eval and assert execute one sentence Trojan horse
Initial summary of flask framework creation project
随机推荐
Openresty + keepalived 实现负载均衡 + IPV6 验证
缓存一致性与内存屏障
Iterators and generators
Management of product pictures
4279. Cartesian tree
User management - restrictions
VS Code中＃include报错（新建的头文件）
Zhongang Mining: the new energy industry is developing rapidly, and fluorine chemical products have a strong momentum
It's better to be full than delicious; It's better to be drunk than drunk
Realization of backstage brand management function
Using ecological power, opengauss breaks through the performance bottleneck
Blueprint class view method
P7 Day1 get to know the flask framework
Flask one to many database creation, basic addition, deletion, modification and query
面试官：什么是脚手架？为什么需要脚手架？常用的脚手架有哪些？
Fluent rendering mechanism - GPU thread rendering
03.使用引号来监听对象嵌套值的变化
低成本、低门槛、易部署，4800+万户中小企业数字化转型新选择
Have a good laugh
Supervisor 安装与使用