[数据结构与算法]数据结构之单链表的增与删

目录

单链表的增

单链表的删

单链表的增

思路：1.检查插入点位置是否合法 ? 2.遍历单链表找到插入位的前结点?? 3.检查是否为空指针?? 4.若不为空指针，则创建新结点并插入

图解过程：

?

?

?解析：线性表的遍历只能从前往后遍历，所以如果要插入新结点，则只能将前结点的指针指向待插入结点，然后将待插入结点的指针指向后结点。

代码如下：

?

int InsertList(LinkList L, unsigned int i, ElemType *ee){
	if((L == NULL) && (ee == NULL)){
		printf("该链表不存在！");
		return 0;
	}
	if(i<1){
		printf("插入位置不合法！");
		return 0;
	}
	
	LNode *p=L;     //定义新指针，作遍历用
	int k=0;          //做计数用，用来标记找到待插入结点的前结点	
	while(p != NULL && k<i-1){
		p=p->next;  //指针向下遍历
		k++;
	}
	
	if(p == NULL){
		printf("插入位置不合法，超过了链表长！");
		return 0;
	}
	//如果未报错，则此时的p地址就是待插入结点的前结点
	
	LNode *tmp = (LNode *)malloc(sizeof(LNode));  // 分配一个结点。
	// 考虑数据元素为结构体的情况，这里采用了memcpy的方法而不是直接赋值。
  	memcpy(&tmp->data,ee,sizeof(ElemType));

  	// 处理next指针。
  	tmp->next=p->next;
  	p->next=tmp;
}

?单链表的增

单链表的删

思路与增加相似，代码类似

思路：1.检查删除点位置是否合法 ? 2.遍历单链表找到删除位的前结点?? 3.检查是否为空指针?? 4.若不为空指针，则删除。

图解：

?

?

?删除时，待删除结点的前结点的指针位直接指向待删除结点的后结点即可，类似于一个跳跃的操作，然后直接将待删除结点free。

代码：

int  DeleteNode(LinkList L, unsigned int i)  
{
  if (L == NULL){ 
    printf("链表LL不存在。\n"); 
    return; 
    } // 判断链表是否存在。

  // 判断删除位置是否合法
  if (i < 1){ 
    printf("删除位置（%d）不合法，应该在大于0。\n",i);
    return 0; 
    }

  // 要删除位序ii结点，必须找到ii-1结点。
  LNode *p=L;  
  int k=0;      

  while ( (p != NULL) && (k < ii-1) )
  {
    pp=pp->next; 
    k++;
  }
    //与增加非常类似
  
  if ( p->next==NULL ){ 
    printf("位置（%d）不合法，超过了表长。\n",i); 
    return 0; 
    }

  LNode *tmp=p->next;  // tmp为将要删除的结点。
  p->next=tmp->next

  free(tmp);

  return 1;
}

ps：作图软件为xmind。