数据结构---线性表-创新互联

刘佳瑜*，王越 *, 黄扬* , 张钊*

建网站原本是网站策划师、网络程序员、网页设计师等，应用各种网络程序开发技术和网页设计技术配合操作的协同工作。创新互联专业提供成都网站制作、网站建设,网页设计,网站制作(企业站、成都响应式网站建设、电商门户网站)等服务,从网站深度策划、搜索引擎友好度优化到用户体验的提升,我们力求做到极致!

(淮北师范大学计算机科学与技术学院，安徽 淮北)

*These authors contributed to the work equllly and should be regarded as co-first authors.

🌞欢迎来到数据结构的世界 
🌈博客主页：卿云阁

💌欢迎关注🎉点赞👍收藏⭐️留言📝

🌟本文由卿云阁原创！

🙏作者水平很有限，如果发现错误，请留言轰炸哦！万分感谢！

---

目录

🍈 线性表的定义

🍉顺序表

存储结构

定义和初始化

插入

删除

查找

🍊单链表

建立单链表

查找运算

插入运算

删除运算

​编辑

求表长运算

🍋双向链表 

🥥循环链表 

🍇静态链表 

---

🍈 线性表的定义

---

🍉顺序表 存储结构

定义和初始化

静态分配

#define MAXSIZE 10
typedef int DateType; 
typedef struct
{
  DateType data[MAXSIZE];
  int length;
}SqList;
void InitList(SqList &L)
{
  L.length=0;
}
int main() 
{
  SqList L;
  InitList(L);
  return 0;
}

动态分配

#include#include#define MAXSIZE 5       //MAXSIZE是根据实际问题定义的足够大的整数常量
typedef int DataType;
typedef struct{ 
   DataType  *data;//定义了一个指针变量存放地址
   int  length; 
 }SqList;       //定义顺序表类型
 
int main() {
 SqList L;
L.data=(DataType*)malloc(sizeof(DataType)*MAXSIZE);//在C++中也可以使用new,和delete
free(L.data);  //释放空间
L.data=NULL;
  return 0;
}

增加数组空间的长度 

#include#include#define INITSIZE 10       
typedef int DataType;
typedef struct{ 
   DataType  *data;
   int  length; 
   int maxsize;
 }SqList;       //定义顺序表类型
void InitSqList(SqList &L,int initsize)
{   printf("%d\n",initsize);
    L.data=(DataType *)malloc(sizeof(DataType )*initsize);
    L.length=0;
    L.maxsize=initsize;
}
//增加动态数组的长度
void IncreaseSize(SqList &L,int len)
{
  int *p=L.data;
  int i;
  L.data=(DataType *)malloc(sizeof(DataType )*(INITSIZE+len));
  for(i=0;i

插入

#include#define MAXSIZE 5       //MAXSIZE是根据实际问题定义的足够大的整数常量
typedef int DataType;
typedef struct{ 
   DataType  data[MAXSIZE];
   int  length; 
 }SqList;       //定义顺序表类型
void InitSqList(SqList &L)
{
    L.length=3;
    L.data[0]=0;
    L.data[1]=1;
    L.data[2]=3;
 
}
void InsertSqList(SqList &L,int  i,DataType  x)
{  int j; 
    if(L.length==MAXSIZE)
    {   printf("\n顺序表是满的,无法插入元素!");
        exit(1);
    } 
    if(i<1||i>L.length+1)
    {  printf("\n指定的插入位置不存在!");
        exit(1);
    } 
    for(j=L.length-1;j>=i-1;j--) 
        L.data[j+1]=L.data[j]; 
    L.data[i-1]=x;
    L.length++; 
}
int main() {
  SqList L;
  InitSqList(L);
  int i=3;
  int x=2;
  InsertSqList(&.L,i,x);
  return 0;
}

删除

#include#include#define MAXSIZE 5       //MAXSIZE是根据实际问题定义的足够大的整数常量
typedef int DataType;
typedef struct{ 
   DataType  data[MAXSIZE];
   int  length; 
 }SqList;       //定义顺序表类型
void InitSqList(SqList &L)
{
    L.length=4;
    L.data[0]=0;
    L.data[1]=1;
    L.data[2]=4;
    L.data[3]=2;
}
void DeleteSqList(SqList &L,int  i)
{  int j;
  if(L.length==0) 
    {  printf("\n顺序表是空的,无法删除元素!");
        exit(1);
    }
    if(i<1||i>L.length)
    {  printf("\n指定的删除位置不存在!");
        exit(1);
    }
    for(j= i;j< L.length;j++) 
        L.data[j-1]=L.data[j]; 
    L.length--; 
}

int main() {
  SqList L;
  InitSqList(L);
  int x=3;
  DeleteSqList(L,x);
  return 0;
}

查找

按位查找

#include#include#define MAXSIZE 5       //MAXSIZE是根据实际问题定义的足够大的整数常量
typedef int DataType;
typedef struct{ 
   DataType  data[MAXSIZE];
   int  length; 
 }SqList;       //定义顺序表类型
void InitSqList(SqList &L)
{
    L.length=4;
    L.data[0]=0;
    L.data[1]=1;
    L.data[2]=4;
    L.data[3]=2;
}
DataType GetElem(SqList L,int i)
{
  return L.data[i-1];
}

int main() {
  SqList L;
  int a;//接受查找到的元素
  InitSqList(L);
  a=GetElem(L,3);
  printf("this:%d",a);
  return 0;
}

按值查找

#include#define MAXSIZE 5       //MAXSIZE是根据实际问题定义的足够大的整数常量
typedef int DataType;
typedef struct{ 
   DataType  data[MAXSIZE];
   int  length; 
 }SqList;       //定义顺序表类型
void InitSqList(SqList L)
{
    L.length=4;
    L.data[0]=0;
    L.data[1]=1;
    L.data[2]=4;
    L.data[3]=2;
}
int  LocationSqList(SqList L, DataType x)
{ int i;
  for (i=0; i

---

🍊单链表

节点的结构

不带头结点的单链表

#include#define MAXSIZE 5  
typedef int DataType;
typedef struct Node
{ 
    DataType  data;
    struct Node *next;
}LNode , *LinkList;
bool InitList(LinkList &L)
{
  L=NULL;
  return true;
}
bool Empty(LinkList L)
{
  return (L==NULL);
}
int main() 
{
  LinkList L;
  InitList(L);
  return 0;
}

带头结点的单链表

#include#include#define MAXSIZE 5  
typedef int DataType;
typedef struct Node
{ 
    DataType  data;
    struct Node *next;
}LNode , *LinkList;
bool InitList(LinkList &L)
{
  L=(LNode *)malloc(sizeof(LNode));
  if (L==NULL)
      return false;
  L->next=NULL;
  return true;
}
bool Empty(LinkList L)
{
  if (L->next==NULL)
      return true;
  else
      return false;
}
int main() 
{
  LinkList L;
  InitList(L);
  return 0;
}

建立单链表

头插法

#define flag -1
#include#include#define MAXSIZE 5  
typedef int DataType;
typedef struct Node
{ 
    DataType  data;
    struct Node *next;
}LNode , *LinkList;
bool InitList(LinkList &L)
{
  L=(LNode *)malloc(sizeof(LNode));
  if (L==NULL)
      return false;
  L->next=NULL;
  return true;
}
bool Empty(LinkList L)
{
  if (L->next==NULL)
      return true;
  else
      return false;
}
int CreatLinkList(LinkList &L) 
{
	LNode *s;
	DataType x;
	int count=0;//记录输入的节点的个数 
	printf("请输入第一个节点的值：\n");
	scanf("%d",&x);
	while(x!=flag)
	{
		s=(LinkList)malloc(sizeof(LNode));
		s->data=x;
		s->next=L->next;
		L->next=s;
		count++;
		printf("请输入下一个节点的值：\n");
		scanf("%d",&x);
	}
	return count; 
}
void printLinkList(LinkList &L,int count)
{
	int i;
	LNode *s=L->next; 
	for(i=0;idata));
		s=s->next;
	}
}
int main() 
{
  printf("使用头插法建立单链表\n");
  int count;
  LinkList L;
  InitList(L);
  count=CreatLinkList(L);
  printLinkList(L,count);
  return 0;
}

尾插法

#define flag -1
#include#include#define MAXSIZE 5  
typedef int DataType;
typedef struct Node
{ 
    DataType  data;
    struct Node *next;
}LNode , *LinkList;
bool InitList(LinkList &L)
{
  L=(LNode *)malloc(sizeof(LNode));
  if (L==NULL)
      return false;
  L->next=NULL;
  return true;
}
bool Empty(LinkList L)
{
  if (L->next==NULL)
      return true;
  else
      return false;
}
int CreatLinkList(LinkList &L) 
{
	LNode *s,*r;
	DataType x;
	int count=0;//记录输入的节点的个数 
	r=L;
	printf("请输入第一个节点的值：\n");
	scanf("%d",&x);
	while(x!=flag)
	{
		s=(LinkList)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r=s;
		count++;
		printf("请输入下一个节点的值：\n");
		scanf("%d",&x);
	}
	r->next=NULL;
	return count; 
}
void printLinkList(LinkList &L,int count)
{
	int i;
	LNode *s=L->next; 
	for(i=0;idata));
		s=s->next;
	}
}
int main() 
{
  printf("使用尾插法建立单链表\n");
  int count;
  LinkList L;
  InitList(L);
  count=CreatLinkList(L);
  printLinkList(L,count);
  return 0;
}

查找运算

按位查找&按值查找

#define flag -1
#include#include#define MAXSIZE 5  
typedef int DataType;
typedef struct Node
{ 
    DataType  data;
    struct Node *next;
}LNode , *LinkList;
bool InitList(LinkList &L)
{
  L=(LNode *)malloc(sizeof(LNode));
  if (L==NULL)
      return false;
  L->next=NULL;
  return true;
}
bool Empty(LinkList L)
{
  if (L->next==NULL)
      return true;
  else
      return false;
}
int CreatLinkList(LinkList &L) 
{
	LNode *s,*r;
	DataType x;
	int count=0;//记录输入的节点的个数 
	r=L;
	printf("请输入第一个节点的值：\n");
	scanf("%d",&x);
	while(x!=flag)
	{
		s=(LinkList)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r=s;
		count++;
		printf("请输入下一个节点的值：\n");
		scanf("%d",&x);
	}
	r->next=NULL;
	return count; 
}
void printLinkList(LinkList &L,int count)
{
	int i;
	LNode *s=L->next; 
	for(i=0;idata));
		s=s->next;
	}
}
LNode *GetLinkList(LinkList L,int i)
{
	LinkList p=L;
	int j=0;//表示当前查找的位置 
	while(p->next!=NULL&&jnext;
		j++;
	}
	return p;
 } 
 LNode *LocationLinkList(LinkList L,DataType x) 
{
	LinkList p=L->next;
	while(p->next!=NULL&&p->data!=x)
	{
		p=p->next;
	}
	return p;
 } 
int main() 
{
  printf("使用尾插法建立单链表\n");
  int count;
  LNode *p1,*p2;//接受查找的结果 
  LinkList L;
  InitList(L);
  count=CreatLinkList(L);
  printf("建立单链表如下\n");
  printLinkList(L,count);
  printf("查找第3个元素的值：\n");
  p1=GetLinkList(L,3);
  printf("查找第3个元素的值：%d\n",p1->data);
  printf("4在链表中的地址：\n");
  p2=LocationLinkList(L,4); 
  printf("4在链表中的地址%d\n",p2 );
  return 0;
}

插入运算

#define flag -1
#include#include#define MAXSIZE 5  
typedef int DataType;
typedef struct Node
{ 
    DataType  data;
    struct Node *next;
}LNode , *LinkList;
bool InitList(LinkList &L)
{
  L=(LNode *)malloc(sizeof(LNode));
  if (L==NULL)
      return false;
  L->next=NULL;
  return true;
}
bool Empty(LinkList L)
{
  if (L->next==NULL)
      return true;
  else
      return false;
}
int CreatLinkList(LinkList &L) 
{
	LNode *s,*r;
	DataType x;
	int count=0;//记录输入的节点的个数 
	r=L;
	printf("请输入第一个节点的值：\n");
	scanf("%d",&x);
	while(x!=flag)
	{
		s=(LinkList)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r=s;
		count++;
		printf("请输入下一个节点的值：\n");
		scanf("%d",&x);
	}
	r->next=NULL;
	return count; 
}
void printLinkList(LinkList &L,int count)
{
	int i;
	LNode *s=L->next; 
	for(i=0;idata));
		s=s->next;
	}
}
LNode *GetLinkList(LinkList L,int i)
{
	LinkList p=L;
	int j=0;//表示当前查找的位置 
	while(p!=NULL&&jnext;
		j++;
	}
	return p;
 } 
 LNode *LocationLinkList(LinkList L,DataType x) 
{
	LinkList p=L->next;
	while(p->next!=NULL&&p->data!=x)
	{
		p=p->next;
	}
	return p;
 } 
 void InsertLinkList(LinkList L,int i,DataType x)
 {
 	LNode *p,*s;
 	p=GetLinkList(L,i-1);
 	if (p==NULL)
 	{
 		printf("插入的位置不合法：\n");
 		exit(1);
	 }
	else
	{
	s=(LNode *) malloc(sizeof(LNode));
	s->data=x;
 	s->next=p->next;
 	p->next=s;	
	}

 }
int main() 
{
  printf("使用尾插法建立单链表\n");
  int count;
  LNode *p1,*p2;//接受查找的结果 
  LinkList L;
  InitList(L);
  count=CreatLinkList(L);
  printf("建立单链表如下\n");
  printLinkList(L,count);
  InsertLinkList(L,3,2);
  printf("插入2后的单链表如下：\n");
  printLinkList(L,count+1);
  return 0;
}

删除运算

#define flag -1
#include#include#define MAXSIZE 5  
typedef int DataType;
typedef struct Node
{ 
    DataType  data;
    struct Node *next;
}LNode , *LinkList;
bool InitList(LinkList &L)
{
  L=(LNode *)malloc(sizeof(LNode));
  if (L==NULL)
      return false;
  L->next=NULL;
  return true;
}
bool Empty(LinkList L)
{
  if (L->next==NULL)
      return true;
  else
      return false;
}
int CreatLinkList(LinkList &L) 
{
	LNode *s,*r;
	DataType x;
	int count=0;//记录输入的节点的个数 
	r=L;
	printf("请输入第一个节点的值：\n");
	scanf("%d",&x);
	while(x!=flag)
	{
		s=(LinkList)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r=s;
		count++;
		printf("请输入下一个节点的值：\n");
		scanf("%d",&x);
	}
	r->next=NULL;
	return count; 
}
void printLinkList(LinkList &L,int count)
{
	int i;
	LNode *s=L->next; 
	for(i=0;idata));
		s=s->next;
	}
}
LNode *GetLinkList(LinkList L,int i)
{
	LinkList p=L;
	int j=0;//表示当前查找的位置 
	while(p!=NULL&&jnext;
		j++;
	}
	return p;
 } 
 LNode *LocationLinkList(LinkList L,DataType x) 
{
	LinkList p=L->next;
	while(p!=NULL&&p->data!=x)
	{
		p=p->next;
	}
	return p;
 } 
 void InsertLinkList(LinkList L,int i,DataType x)
 {
 	LNode *p,*s;
 	p=GetLinkList(L,i-1);
 	if (p==NULL)
 	{
 		printf("插入的位置不合法：\n");
 		exit(1);
	 }
	else
	{
	s=(LNode *) malloc(sizeof(LNode));
	s->data=x;
 	s->next=p->next;
 	p->next=s;	
	}

 }
 void DeleteLinkList(LinkList L,int i)
 {
 	LNode *p,*q;
 	p=GetLinkList(L,i-1);
 	if (p==NULL)
 	{
 		printf("删除的位置不合法：\n");
 		exit(1);
	 }
	else
	{
	  if(p->next==NULL) 
	  	{
 		printf("删除的位置不合法：\n");
 		exit(1);
	   }
	   else
	   {
	   	q=p->next;
	   	p->next=p->next->next;
	   	free(q);
	   }
	}
 }
int main() 
{
  printf("使用尾插法建立单链表\n");
  int count;
  LNode *p1,*p2;//接受查找的结果 
  LinkList L;
  InitList(L);
  count=CreatLinkList(L);
  printf("建立单链表如下\n");
  printLinkList(L,count);
  InsertLinkList(L,3,2);
  printf("删除第3个节点的单链表如下：\n");
  DeleteLinkList(L,3);
  printLinkList(L,count-1);
  return 0;
}

求表长运算

#define flag -1
#include#include#define MAXSIZE 5  
typedef int DataType;
typedef struct Node
{ 
    DataType  data;
    struct Node *next;
}LNode , *LinkList;
bool InitList(LinkList &L)
{
  L=(LNode *)malloc(sizeof(LNode));
  if (L==NULL)
      return false;
  L->next=NULL;
  return true;
}
bool Empty(LinkList L)
{
  if (L->next==NULL)
      return true;
  else
      return false;
}
int CreatLinkList(LinkList &L) 
{
	LNode *s,*r;
	DataType x;
	int count=0;//记录输入的节点的个数 
	r=L;
	printf("请输入第一个节点的值：\n");
	scanf("%d",&x);
	while(x!=flag)
	{
		s=(LinkList)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r=s;
		count++;
		printf("请输入下一个节点的值：\n");
		scanf("%d",&x);
	}
	r->next=NULL;
	return count; 
}
void printLinkList(LinkList &L,int count)
{
	int i;
	LNode *s=L->next; 
	for(i=0;idata));
		s=s->next;
	}
}
LNode *GetLinkList(LinkList L,int i)
{
	LinkList p=L;
	int j=0;//表示当前查找的位置 
	while(p!=NULL&&jnext;
		j++;
	}
	return p;
 } 
 LNode *LocationLinkList(LinkList L,DataType x) 
{
	LinkList p=L->next;
	while(p!=NULL&&p->data!=x)
	{
		p=p->next;
	}
	return p;
 } 
int LengthLinkList(LinkList L)
{
	int len=0;
	LNode *p=L;
	while(p->next)
	{
		len++;
		p=p->next;
	}
   return len;
}
int main() 
{
  printf("使用尾插法建立单链表\n");
  int count;
  int length;
  LNode *p1,*p2;//接受查找的结果 
  LinkList L;
  InitList(L);
  count=CreatLinkList(L);
  printf("建立单链表如下\n");
  printLinkList(L,count);
  length=LengthLinkList(L);
  printf("单链表的长度是%d\n",length);
  return 0;
}

---

🍋双向链表 

---

 🥥循环链表 

---

 🍇静态链表 

Institutional Review Board Statement: Not applicable.

Informed Consent Statement: Not applicable.

Data Availability Statement: Not applicable.

Author Contributions:All authors participated in the assisting performance study and approved the paper.

Conflicts of Interest: The authors declare no conflict of interest

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧