数据结构 | 单链表增删改查

头插法

#include <iostream>
using namespace std;
#define STOP -999
typedef int Element;
typedef struct lnode
{
    Element data;
    struct lnode *next;
}LNode;
void show(LNode *L);
LNode *create_list_H()
{
    //(A)创建只有头结点head的: '空单链表'
    LNode *head,*p;
    head = new LNode;
    head->next=NULL;
    //(B)录入链表各结点的数据, 并钩链
	Element data;
    while(true){
        //(a)键盘输入一个链表结点数据-->data
        cin >> data;
        //(b)若录入数据data == '数据录入'结束标志END_CODE,则完成链表创建！
        if (data == STOP)
        {   
            break;
        }
        //(c)录入的链表结点数据'data'有效, 则创建一个链表结点存储此数据
        p = new LNode;
        p->data=data;
  
        //(d)钩链: 新创建的结点q总是作为第一个结点
        p->next = head->next;
        head->next=p;
        //(e)信息提示: 结点创建成功! 并显示当前链表的内容信息！！！
        cout << "创建节点" << p->data << "成功在表头";
		show(head);
    }
    //(C)返回此单链表的'头结点head'
    return head;
}
void show(LNode *L)
{
	if(L->next ==NULL)
	{
		return;
	}
	LNode *p =L->next;
	while (p!=NULL)

	{
		cout << "-> " << p->data;
		p=p->next;
	}
	cout <<endl;
}
int main()
{
    LNode *head =  create_list_H();
	show(head);   
    return 1;
}

头插法逻辑

  1. 创建一个空链表，需要维护住头指针、末尾指针指向空

  2. 创建新的LNode指针，传入需要插入的数据

  3. 钩链，为什么要钩链，钩链的目的是为了组成一个链式结构，相当于数组。总是以head头指针去钩住插入LNode类型数据便于维护和读取该链表。

思考总结：头插法需要维护中head头指针

尾插入法

#include <iostream>
#define STOP -999
using namespace std;

typedef int element;
typedef struct lnode
{
	element data;
	struct lnode *next;
}LNode;
void show(LNode *L);
LNode *create_chain_e()
{
	LNode *head,*q,*p;
	//初始化空链表，尾节点p指向head
	head = p = new LNode;
	head->next = NULL;
	element data;

	while (true)
	{
		cin >> data;
		if (data == STOP)
		{
			break;
		}
		q= new LNode;
		q->data = data;
		//钩链：新创建的节点总是在尾部
		q->next = p->next;
		p->next =q;
		p=q;
		cout << "成功插入" << q->data << "尾部";
		show(head);
	}
	return (head);
}
void show (LNode *L)
{
	if(L->next==NULL)
	{
		return;
	}
	LNode *p=L->next;
	while (p!=NULL)
	{
		/* code */
		cout <<  p->data << "<-";
		p=p->next;
	}
	cout <<endl;
	
}

int main()
{
	LNode *head = create_chain_e();
	show(head);
	return 1;
}

尾插入法逻辑

  1. 新建三个指针分别是头指针、尾指针、插入指针

  2. 首先头指针head与尾指针p指向同一块内存地址

  3. 操作尾指针p与插入指针q地址，q->next=p->next使q连接null，p->next = q (左连接插入的指针)，p=q交换指针位置使p继续为尾节点(这样head指针就能指向插入的数据)

    思考总结：这里体现了链表从右向左操作逻辑，还有需要注意的是head与p添加节点之前是指向同一块内存地址，这样相当于有固定头结点的功能。

1569736296836

单链表查找

按序号查找

element get_ElemByid(LNode *L, int i)
{	
	//如果链表首节点或下一个节点位空，则判断该链表为空
	if (L ==NULL && L->next ==NULL)
	{
		return STOP;
	}
	//赋值定义p指向p下一个节点,因为首节点为null所以指向下一个
	LNode *p = L->next;
	int j =1;

	while (p!=NULL && j<i)
	{
		p = p->next;
		j++;
	}
	//判断是否找到第i个节点
	if(j!=i)//i太大不给看
	{
		return STOP;
	}else
	{
		return (p->data);
	}
}

按序号查找逻辑： 遍历指针指向第i的位置

需要注意需要查询是位于链表下一个元素当做首节点，

1569746509054

按值查找

LNode *get_ElemByvalue(LNode *L,element i)
{
	LNode *p = L->next;
	if (L == NULL && L->next == NULL)
	{
		return NULL;
	}
	while (p!=NULL && p->data !=i)
	{
		p=p->next;

	}
	if(p != NULL){
		return p;
	}else
	{
		return NULL;
	}
	
}

按值查找逻辑：也是通过遍历指针，条件替换为值的比较。

1569746361295

插入

bool insertElement(LNode *L,int i,element data)
{
	//定义p游标头，q插入的指针
	LNode *p,*q;
	if (L == NULL && L->next ==NULL)
	{
		return false;
	}
	p=L;//指向p头结点，可能会插到头节点位置
	int j = 0;
	// 防止超出链表长度,游标指向第i-1节点
	while (p -> next !=NULL&& j<i-1)
	{
		p=p->next;
		j++;
	}
	if (j!=i-1){//i太大
		return false;
	}else
	{
		q = new LNode;
		q->data=data;
		q->next = p->next;
		p->next =q;
		return true;		
	}
}

插入逻辑和注意点

  1. 游标遍历时候需要注意是否会超出链表长度,以null判断

  2. 勾链操作类似新建链表

  3. 头结点head在组链表时候已经明确为空了，所以若插入在第一个节点，其实前面还有个值为null的节点。

    1569746327282

删

删除指定位置的节点

bool deleteByid(LNode *L,int i)
{
	if (L ==NULL && L->next ==NULL)
	{
		return false;
	}
	//q为游标，p为指向第i个待删除的节点
	LNode *q,*p;
	q = L;
	p=L->next;
	int j =0;
    //p下一个节点不能为空，为空说明已经是在最后一个节点
	while (p->next!=NULL && j<i-1)
	{
		/* code */
		//p与q指针交换位置,这样调整p指针也能够移动q
		q=p;
		p=p->next;
		j++;
	}
	if(j!=i-1)
	{
		return false;
	}else
	{	//直接钩住待删除第i个节点的下一个
		q->next = p->next;
		//删除p->next前继
		delete(p);
		return true;
	}	
}

思考总结：定义游标、待删指针。指针的移动可以通过地址迭代遍历，分别移动游标和待删指针

1569746264172

删除指定x第一个节点

bool deleteByvar_1(LNode *L,element data)
{
	if (L == NULL && L->next ==NULL)
	{
		return false;
	}
	LNode *q,*p;
	q=L;
	p=L->next;
	while (p!=NULL && p->data != data){
		q=p;
		p=p->next;
	}
	if(p != NULL && p->data == data)
	{
		q->next = p->next;
		delete(p);
		return true;
	}else
	{
		return false;
	}
	
}

思考总结：类比前面

1569746218114

删除链表中所有重复的节点x

void deleteByvar_n(LNode *L,element data)
{
	if(L==NULL)
	{
		return;
	}
	LNode *q,*p;
	q=L;
	p=L->next;
	while(p!=NULL)
	{
		if(p->data == data)
		{
			q->next = p->next;
			delete(p);

			p=q->next;//待删除点继续跟在游标后
		}
		else
		{
			q=p;
			p = p->next;
		}
		
	}
}

注意点：删除后，必须把待删节点继续接在游标后，否则p变量不存在,可能会随机分配p的值。

1569746195714