天天看点
返回

数据结构（c/c++）：3.线性表之静态链表代码实现

文章目录

    • 1.背景
    • 2.实现
        • 1.结点定义
        • 2.静态链表初始化
        • 3.申请和释放函数
        • 4.静态链表的操作
            • 1.建表
            • 2.插入
            • 3.删除
            • 4.表长
            • 5.打印（显示）
    • 3.全部代码
    • 4.总结

1.背景

在上古时期，Basic，Fortan横行的年代，链表中，由于没有指针的存在，人们利用数组来代替指针。所以静态链表是一种用数组描述的链表。

2.实现

1.结点定义 

typedef struct{
	int data;
	int next;//下一个结点的数组下标
}node,StaticLinklist[MAXSIZE];

2.静态链表初始化

首先定义一个大小为MAXSIZE的结构体数组，在数组中的每个结点都有数据域data和一个int型next变量，next代表了下一个结点的数组下标。在该数组中，分成2部分，备用（空闲）链表和链表（已用）. 不妨把数组第一个结点设为备用链表的头结点。设最后一个结点为链表（已用）的头结点，其next为链表的 第一个有数据的 结点的数组下标，开始时next=0代表只有头结点，链表（已用）为空。

初始时将所有结点连起来构成备用（空闲）链表。

具体代码如下：

void InitLinkList(StaticLinklist &A)
{ int i;
  for(i=0;i<MAXSIZE-1;i++)
	   A[i].next=i+1;
	A[MAXSIZE-1].next=0;
}

3.申请和释放函数

对应着动态链表中malloc和free函数，静态链表中也需要有申请和释放函数。

  • 申请（返回申请结点的数组下标）

    先判断是否还有空闲链表结点，有则分配，将这个结点的下一个结点（next值）当成空闲链表首结点，即赋值给A【0】.next；

    从动态链表角度理解是：对于空闲链表头结点p，现在让s=p->next; p->next=p->next->next;

int L_mallc(StaticLinklist &A){
	int i=A[0].next;//返回 申请结点的数组下标 
	if(A[0].next) A[0].next= A[i].next;// 先判断是否还有空闲链表结点，有则分配，将这个结点的下一个结点（next值）当成空闲链表首结点 
	return i;
	
}

  • 释放(释放下标为K的结点)

    从动态链表角度理解是：对于空闲链表头结点p，现在让k->next=p->next; p->next=k;

void L_free(StaticLinklist &A,int k){
	A[k].next=A[0].next;
	A[0].next=k;
	
}

4.静态链表的操作

1.建表

代码用的是头插法建表，其实思想和动态链表思想都是一样一样的。

void L_creat(node* A,int n)
{	int e;
	int k=MAXSIZE-1;
	while(n){
	int p=L_malloc(A);
	cout<<"get e"<<endl;
	cin>>e;
	A[p].data=e;
	A[p].next=A[k].next;	
	A[k].next=p;
	n--;
	}
}

2.插入

在头结点后第i个位置后插入数据元素为e的结点 (i为0则为头插)

int Linsert(node* A,int i,int e){
	int k=MAXSIZE-1;
	if(i<0||i>L_length(A)+1||i>(MAXSIZE-2)) return 0;//MAXSIZE-2：有2个结点要当备用链表头结点和已用链表头结点 
	int p=L_malloc(A); 
	A[p].data=e;
	if(i==0) 
		{A[p].next=A[k].next;	
			A[k].next=p;
			return 1;
		}
	//找到第i个结点的下标
	while(i){
		k=A[k].next;
		i--;

	}
	//插入操作 
	A[p].next=A[k].next;	
	A[k].next=p;
	return 1;
}

3.删除

//删除在头结点后第i个结点 (i从1开始计数)
int L_delete(node* A,int i){
	if(i<1||i>L_length(A)) {cout<<"error"<<endl; return 0;}
	int j; 
	int k=MAXSIZE-1;
	i=i-1;
	//找到第i个结点的前驱结点的数组下标k 
	while(i){
		k=A[k].next;
		i--;
	}
	//删除 
	j=A[k].next;
	A[k].next=A[j].next;
	L_free(A,j);
	return 1;
}

4.表长

int L_length(node* A){
	int L=0;
	int k=A[MAXSIZE-1].next;
	while(k){
		k=A[k].next;
		L++;
	}
	return L;
}

5.打印（显示）

void L_show(node* A){
	int k=A[MAXSIZE-1].next;
	while (k){
		cout<<A[k].data<<",";
		k=A[k].next;
	}
	cout<<endl;
}

3.全部代码 

#include <iostream>
using namespace std;
#define MAXSIZE 20
typedef struct{
	int data;
	int next;//下一个结点的数组下标 
}node;

int L_malloc(node* A){
	int i=A[0].next;//返回 空闲链表头结点的数组下标 
	if(A[0].next) A[0].next= A[i].next;// 先判断是否还有空闲链表结点，有则分配，将这个结点的下一个结点（next值）当成空闲链表首结点 
	return i;
	
}

void L_creat(node* A,int n)
{	int e;
	int k=MAXSIZE-1;
	while(n){
	int p=L_malloc(A);
	cout<<"get e"<<endl;
	cin>>e;
	A[p].data=e;
	A[p].next=A[k].next;	
	A[k].next=p;
	n--;
	}
}

void InitLinkList(node* A)
{ int i;
  for(i=0;i<MAXSIZE-1;i++)
	   {A[i].next=i+1;
	   	A[i].data=-1;
	   }
	A[MAXSIZE-1].next=0;
	
}
 

 
void L_free(node* A,int k){
	A[k].next=A[0].next;
	A[0].next=k;
	
}
int L_length(node* A){
	int L=0;
	int k=A[MAXSIZE-1].next;
	while(k){
		k=A[k].next;
		L++;
	}
	return L;
}

//在头结点后第i个位置后插入数据元素为e的结点 (i为0则头插)
int Linsert(node* A,int i,int e){
	int k=MAXSIZE-1;
	if(i<0||i>L_length(A)||i>(MAXSIZE-2))
	 {cout<<"error"; return 0;}//MAXSIZE-2：有2个结点要当备用链表头结点和已用链表头结点 
	int p=L_malloc(A); 
	A[p].data=e;
	//i为0则头插
	if(i==0) 
		{A[p].next=A[k].next;	
			A[k].next=p;
			return 1;
		}
	//找到第i个结点的下标
	while(i){
		k=A[k].next;
		i--;

	}
	//插入操作 
	A[p].next=A[k].next;	
	A[k].next=p;
	return 1;
}
void L_show(node* A){
	int k=A[MAXSIZE-1].next;
	while (k){
		cout<<A[k].data<<",";
		k=A[k].next;
	}
	cout<<endl;
}
//删除在头结点后第i个结点 (i从1开始计数)
int L_delete(node* A,int i){
	if(i<1||i>L_length(A)) {cout<<"error"<<endl; return 0;}
	int j; 
	int k=MAXSIZE-1;
	i=i-1;
	//找到第i个结点的前驱结点的数组下标k 
	while(i){
		k=A[k].next;
		i--;
	}
	//删除 
	j=A[k].next;
	A[k].next=A[j].next;
	L_free(A,j);
	return 1;
}

int main() {
	node A[MAXSIZE]; 
	InitLinkList(A);
	int n,i,e;
	cout<<"输入表长"<<endl;
	cin>>n; 
	L_creat(A,n);;
	L_show(A);
	//插入操作测试 
	
	cout<<"get i and e"<<endl;
	cin>>i>>e;
	if(!Linsert(A,i,e)) return 0;
	L_show(A);
	
	//删除操作测试 
	cout<<"get i of delete"<<endl;
	cin>>i;
	if(!L_delete(A,i)) return 0; 
	L_show(A);
	return 0; 
}

4.总结

静态链表的思想和动态链表都是类似的，代码有理解不了的地方从动态链表角度思考就会容易的多。说实话，感觉静态链表代码实现起来是真的烦人哦（或许是我比较菜吧~）。

数据结构和算法 数据结构
上一篇: 排序 - 次位优先实现基数排序（C++、静态链表）
下一篇: 静态链表的实现静态链表的实现

继续阅读