数据结构静态链表的插入与删除

绝地灬酷狼 2022-09-19 01:29 167阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    #include <iostream.h>
    
    #define MAXSIZE   100
    #define OK        1
    #define ERROR     0
    #define OVERFLOW  -2
    
    typedef int ElemType;
    
    
    typedef struct
    {
    	ElemType  data;
    	int cur;
    }component, SLinkList[MAXSIZE];
    
    
    void InitSpace_SL(SLinkList &space)
    {//初始化静态链表,space[0].cur为头指针
    	int i;
    	for (i=0; i<MAXSIZE-1; i++)
    	{
    		space[i].cur = i+1;
    	}
    	space[MAXSIZE-1].cur = 0;
    }
    
    
    void Create_SL(SLinkList &space,int n)
    {
    	int i;
    	for (i=1; i<=n; i++)
    	{
    		scanf("%d",&space[i].data);
    	}
    	space[0].cur = n+1;/*space[0].cur 第一个备用空闲的下标*/
    	space[n].cur = 0;/*最后一个元素的cur为0*/
    	space[MAXSIZE-1].cur = 1;/*space[MAXSIZE-1].cur指向第一个元素*/
    }
    
    
    int SL_Length(SLinkList space)
    {
    	int j = 0;
    	int i = space[MAXSIZE-1].cur;
    	while (i)
    	{
    		i = space[i].cur;/*类似于p = p->next */
    		j++;
    	}
    	return j;
    }
    
    void print_SL(SLinkList space)
    {
    	int i = space[MAXSIZE-1].cur;
    	while (i)
    	{
    		printf("%d ",space[i].data);
    		i = space[i].cur;
    	}
    	printf("\n");
    }
    
    
    int Malloc_SL(SLinkList space)
    {/*类似于mallco函数*/
    	int i = space[0].cur;/*space[0].cur 第一个备用空闲的下标*/
    	if (space[0].cur)
    	{/*space[0].cur 始终指向第一个备用空闲的下标*/
    		space[0].cur = space[i].cur ;
    	}
    
    	return i;
    }
    
    int Insert_SL(SLinkList space, int i, ElemType e)
    {//在第i个位置插入e，就是把第i-1个元素的cur指向插入的元素，然后将插入元素的cur指向第i个元素
    	int j,k,l;
    	k = MAXSIZE - 1;//k指向第一个元素的cur
    	if (i < 1 || i > SL_Length(space) + 1)
    	{//i值不合法
    		return ERROR;
    	}
    	j = Malloc_SL(space);//分配一个节点
    	if (j)
    	{
    		space[j].data = e;//插入e
    		for (l=1; l<=i-1; l++)
    		{//找到第i个元素之前的位置
    			k = space[k].cur ;
    		}
    		space[j].cur = space[k].cur ;//把第i个元素之前的cur赋值给新元素的cur
    		space[k].cur = j;//把新元素的下标赋值给第i个元素之前元素的cur
    		return OK;
    	}
    	return ERROR;
    }
    
    
    void Free_SL(SLinkList space, int k)
    {
    	space[k].cur = space[0].cur; //space[k].cur指向下一个备用空闲位置
    	space[0].cur = k;//将第k设置为第一个备用空闲位置
    }
    
    int Delete_SL(SLinkList space, int i)
    {//删除第i个位置上的元素，就是把第i-1个元素的cur指向第i+1个元素或者0
    	int j,k;
    	if (i<1 || i>SL_Length(space))
    	{
    		return ERROR;
    	}
    	k = MAXSIZE - 1;
    	for (j=1; j<=i-1; j++)
    	{
    		k = space[k].cur ;
    	}
    	j = space[k].cur ;
    	space[k].cur = space[j].cur ;
    	Free_SL(space,j);
    	return OK;
    }
    	
    
    
    
    int main()
    {
    	int n,i,e;
    	SLinkList space;
    	InitSpace_SL(space);
    	printf("请输入静态链表的长度:");
    	scanf("%d",&n);
    	printf("请输入 %d 个元素:",n);
    	Create_SL(space, n);
    	printf("打印静态链表:");
    	print_SL(space);
    	printf("请输入您要插入元素的位置:");
    	scanf("%d",&i);
    	printf("请输入您要插入的元素:");
    	scanf("%d",&e);
    	Insert_SL(space, i, e);
    	printf("插入元素后的静态链表是:");
    	print_SL(space);
    	printf("请输入您要删除元素的位置:");
    	scanf("%d",&i);
    	Delete_SL(space, i);
    	printf("删除元素后的静态链表是:");
    	print_SL(space);
    
    
    	return 0;
    }