C语言【微项目15】—数组-链表联合结构[一种复合数据结构的探索]（采用指针数组实现数-链结构）【2022-01-03】

admin • • C/C++

C语言【微项目15】—数组-链表联合结构[一种复合数据结构的探索]（采用指针数组实现数-链结构）【2022-01-03】

【TDTX】

【C99】

【特注：数据结构使用探索分享】

【编译与运行环境】64位Windows操作系统，TDM-gcc 4.9.2 64bit编译。

【问题描述】让链表可以如同数组一样查找方便（修改某结点数据域方便），让数组如同链表一样添加和删除元素方便。


【数-链结构】（Array-Link）具有数组特性和链表特性，具有数组形态操作、链表形态操作。

【注】
在C语言【微项目14】中已经初步使用了该思想的雏形，现在将其整理成为一种数据结构的完整操作实现。

【思路】

1.在初始化链表的同时，初始化一个指针数组，数组长度是1。该数组0位置存放单链表头结点的地址。
2.在使用尾插法建立链表有效结点时，凡新生成一个结点且入链表立即使用realloc函数重新分配空间，使数组长度刚好等于头结点+有效结点的个数，再将数组最后一个位置放上刚入链的结点地址。
4.在任意合法位置插入结点时，先将指针数组空间增大一个，结点入链完成后，将指针数组对应的位置空出来（将其余元素向后挪动）放上该入链结点的地址。
5.在任意合法位置删除结点时，通过指针数组完成链表指向更改，最后使数组长度减1（realloc重新分配大小）。
6.在查找或获取值时，直接通过数组形态操作即可（通过指针数组）。
7.在遍历【数-链】结构时，只需通过其数组形态遍历即可,也可通过其链表形态遍历。

一、ArrayLinkList.c

#include <stdio.h>
#include <stdlib.h>
typedef struct Lnode
{
	int data;
	struct Lnode* next;
}Lnode;
typedef struct SingleLinkList
{
	int len;//链表有效结点个数记录
	Lnode* H;//链表形态
	int Alen;//数组长度记录（头结点+有效结点）
	Lnode** LAAP;//数组形态的实现，指针数组
}SLinkList;

int init_ArraySLinkList(SLinkList* S)
{
	S->H = (Lnode*)malloc(sizeof(Lnode)*1);
	S->LAAP = (Lnode**)malloc(sizeof(Lnode*)*1);
	if(S->H == NULL || S->LAAP == NULL)
	{
		S->len = -1;
		S->Alen = -1;
		return 0;
	}
	(S->LAAP)[0] = S->H;
	(S->H)->data = -1;
	S->len = 0;
	S->Alen = 1;
	(S->H)->next = NULL;
	puts("初始化【数-链】结构成功！");
	return 1;
}
int Tail_ArraySLinkList(SLinkList* S)
{
	Lnode* p = S->H;
	puts("n开始尾插法建立链表-输入结点值（空格分隔，f结束）：");
	while(1)
	{
		int tdata,i;
		Lnode* t;
		i = scanf("%d",&tdata); 
		if(i == 0)
		{
			break;
		}
		//printf("tdata = %dn",tdata);
		t = (Lnode*)malloc(sizeof(Lnode)*1);
		S->LAAP = (Lnode**)realloc(S->LAAP,sizeof(Lnode*)*(S->Alen+1));
		if(t != NULL && S->LAAP != NULL)
		{
			t->data = tdata;
			t->next = p->next;
			p->next = t;
			p = t;
			(S->len)++;
			(S->Alen)++;
			//printf("nS->Alen = %dn",S->Alen);
			S->LAAP[S->Alen - 1] = t;
			//Traverse_SLinkList(S);
		}
	}
}
int Insert_ArraySLinkList(SLinkList* S,int i,int e)
{
	if(S->H == NULL)
	{
		return -1;
	}
	if(i < 1 || i > S->len + 1)
	{
		puts("n插入元素结点位置不合法！");
		return 0;
	}
	
	Lnode* p = S->H;
	Lnode* t;
	int co = -1;
	t = (Lnode*)malloc(sizeof(Lnode)*1);
	S->LAAP = (Lnode**)realloc(S->LAAP,sizeof(Lnode*)*(S->Alen+1));
	if(t == NULL || S->LAAP == NULL)
	{
		puts("n待插入结点失败！");
		return 0; 
	}
	t->data = e;
	while(p != NULL)
	{
		co++;
		if(co == i - 1)
		{
			t->next = p->next;
			p->next = t;
			(S->len)++;
			(S->Alen)++;
			for(int k = S->Alen - 1;k - 1 >= 0;k--)
			{
				if(k == i)
				{
					(S->LAAP)[k] = t;
					break;
				}
				(S->LAAP)[k] = (S->LAAP)[k - 1];
			}
			return 1;
		}
		p = p->next;
	}
	return 1;
}
int Delete_ArraySLinkList(SLinkList* S,int i,int* e)
{
	if(S->H == NULL)
	{
		return -1;
	}
	if(i < 1 || i > S->len)
	{
		puts("n删除元素结点位置不合法！");
		return 0;
	}
	
	(S->LAAP)[i - 1]->next = (S->LAAP)[i]->next;	
	
	free((S->LAAP)[i]);
	(S->len)--; 
	
	for(int k = i;k + 1 < S->Alen;k++)
	{
		(S->LAAP)[k] = (S->LAAP)[k+1];
	} 
	(S->Alen)--;
	
	S->LAAP = (Lnode**)realloc(S->LAAP,sizeof(Lnode*)*(S->Alen));
	if(S->LAAP == NULL)
	{
		puts("n已经成功删除！但索引指针数组多出一个空间，重新分配失败！");
		return 1;
	}
	puts("n已经成功删除，并正确调整索引指针数组！");
	return 1; 
}
int Traverse_SLinkList(SLinkList* S)
{
	if((S->H) == NULL)
	{
		return -1;
	}
	if((S->H)->next == NULL)
	{
		puts("n通过链表形态遍历：");
		printf("[H,len = 0]:头结点->NULLn");
		return 1;
	}
	Lnode* p = (S->H)->next;
	int flag = 0;
	while(p != NULL)
	{
		if(flag == 0)
		{
			puts("n通过链表形态遍历：");
			printf("[H,len = %d]:头结点->%d",S->len,p->data);
			flag = 1;
		}
		else
		{
			printf("->%d",p->data);
		}
		p = p->next;
	}
	printf("->NULLn");
	return 1;
}
int Traverse_ArraySLinkList(SLinkList* S)
{
	for(int i = 0;i < S->Alen;i++)
	{
		if(i == 0)
		{
			puts("n通过数组形态遍历：");
			printf("[H,len = %d]:头结点",S->len);
			continue;
		}
		printf("->%d",(S->LAAP)[i]->data);
	}
	printf("->NULLn");
	return 1;
}

int Search_ArraySLinkList(SLinkList* S,int e)
{
	for(int i = 1;i < S->Alen;i++)
	{
		if( (S->LAAP)[i]->data == e )
		{
			return i;
		}
	}
	return 0;
}
int Get_ArraySLinkList(SLinkList* S,int n)
{
	if(n >= 1 && n <= S->Alen - 1)
	{
		return (S->LAAP)[n]->data;
	}
	puts("n获取位置不合法！"); 
	return -2147483648;
}
int Close_ArraySLinkList(SLinkList* S)
{
	for(int i = 0;i < S->Alen;i++)
	{
		free((S->LAAP)[i]);
	}
	free(S->LAAP);
	puts("关闭【数-链】结构成功！");
	return 1;
}

int main()
{
	SLinkList S;
	init_ArraySLinkList(&S);
	Traverse_SLinkList(&S);
	Traverse_ArraySLinkList(&S);
	puts("---------------------------------------------------");
	Tail_ArraySLinkList(&S);
	Traverse_SLinkList(&S);
	Traverse_ArraySLinkList(&S);
	puts("---------------------------------------------------");
	
	fflush(stdin);
	int n; 
	puts("输入一个值可以查询其在单链表中的位置（0-不存在）：");
	scanf("%d",&n);
	printf("%d在第%d位置！n",n,Search_ArraySLinkList(&S,n));
	puts("---------------------------------------------------");
	puts("输入一个位置可以获取该位置的值：");
	scanf("%d",&n);
	printf("第%d位置的值：%dn",n,Get_ArraySLinkList(&S,n));
	puts("---------------------------------------------------");
	
	puts("输入插入位置和值（空格分隔）：");
	int locate,value;
	scanf("%d %d",&locate,&value); 
	Insert_ArraySLinkList(&S,locate,value);
	Traverse_SLinkList(&S);
	Traverse_ArraySLinkList(&S);
	puts("---------------------------------------------------");
	
	puts("输入插入位置和值（空格分隔）：");
	scanf("%d %d",&locate,&value); 
	Insert_ArraySLinkList(&S,locate,value);
	Traverse_SLinkList(&S);
	Traverse_ArraySLinkList(&S);
	puts("---------------------------------------------------");
	
	int t;
	puts("输入要删除的位置：");
	scanf("%d",&n); 
	Delete_ArraySLinkList(&S,n,&t);
	Traverse_SLinkList(&S);
	Traverse_ArraySLinkList(&S);
	puts("---------------------------------------------------");
	Close_ArraySLinkList(&S);
	
	return 0;
}

二、 运行结果示例

在这里插入图片描述

------------------------------------------------------第十五次发项目类文章有点激动啊！-----------------------------------------------------
-----------------------------------------------------【C语言—微项目—自编练习】----------------------------------------------------------
----------------------------------------------------------------【TDTX】--------------------------------------------------------------------------

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>