数据结构之链表

悠悠 2022-03-26 01:36 252阅读 0赞

1、线性链表  
![在这里插入图片描述][2019011421210523.png]  
单链表的定义

typedef struct node
    { 
    	int data;
    	struct node *next;
    }NODE,*LinkList;

在链表存储结构中，只需要一个指针（称为头指针head）指向第一个节点，就可以顺序的访问到表中的任意一个元素。  
2、插入  
在单链表中，若在p所指节点后插入新元素节点（s所指节点，已经生成）基本步骤如下：

（1）s->next=p->next;
    （2）p->next=s;

即先将p所指节点的后继节点指针赋值给s所指节点的指针域，然后将p所指节点的指针域修改为指向s所指节点。  
![在这里插入图片描述][20190115180820654.png]

int Insert_List(LinkList L,int k,int newElem)//L为带头结点单链表的头指针
    { 
    	LinkList p,s;
    	if(k==1) p=L;
    	else
    	{ 
    		p=Find_List(L,k);//此函数见下面介绍；
    	}
    	if(!p) return -1;
    	s=(LinkList)malloc(sizeof(LinkList));
    	if(!s) return -1;
    	s->data=newElem;
    	s->next=p->next;
    	p->next=s;
    	return 0;
    }

3、删除  
在单链表中删除p所指节点的后继节点，步骤如下：

（1）q=p->next;
    （2）p->next=p->next->next;
    （3）free(q)；

![在这里插入图片描述][20190115182405419.png]

int Delete_List(LinkList L,int k,int newElem)//L为带头结点单链表的头指针
    { 
    	LinkList p,q;
    	if(k==1) p=L;
    	else
    	{ 
    		p=Find_List(L,k);//此函数见下面介绍；
    	}
    	if(!p||!p->next) return -1;
    	q=p->next;
    	p->next=q->next;
    	free(q);
    	q=NULL;
    	return 0;
    }

4、查找

LinkList Find_List(LinkList L,int k)//L为带头结点单链表的头指针
    { 
    	LinkList p;int i;
    	i=1;p=L->next;
    	while(p&&i<k)
    	{ 
    		p=p->next;i++;
    	}
    	if(p&&i==k)
    	{ 
    		return p;
    	}
    	else
    	{ 
    		return NULL;
    	}
    }

--------------------

5、双向链表  
若双向链表中节点的front和next指针域分别指示当前节点的直接前驱和直接后驱。  
（1）在双向链表中插入节点s时指针的变化情况如下：

s->front=p->front;
    p->front->next=s;
    s->next=p;
    p->front=s;

![在这里插入图片描述][20190115184724107.png]  
（2）在双向链表中删除节点时指针的变化情况：

p->front->next=p->next;
    p->next->front=p->front;
    free(p);

![在这里插入图片描述][20190115185239973.png]

[2019011421210523.png]: /images/20220326/7be2ee4397744d69a60686786711b411.png
[20190115180820654.png]: /images/20220326/1a911b6b6c3f431ab2010412620c6ceb.png
[20190115182405419.png]: /images/20220326/377d04e0d9104044bea32b415b4503c0.png
[20190115184724107.png]: /images/20220326/9fcc9dbda85c4cd8b054a732749f8aba.png
[20190115185239973.png]: /images/20220326/e28d5703f1b34b50a93513a99e110872.png