数据结构系列－线性表的链式存储及基本操作

拼搏现实的明天。 2022-05-30 11:07 229阅读 0赞

线性表的链式存储，是用一组任意的单元存储线性表的数据元素，这组单元可以连续，也可以不连续。

每个链表元素除了要存储数据信息，还要存储它的后继元素的存储地址，也就是它的数据域、指针域。

通常在单链表的第一个结点前附加一个结点，成为头结点，头结点的数据域可以不存储任何信息，也可以存储链表长度等附加信息，头结点的指针域存储的是指向第一个结点的指针。

还有一个概念是头指针，指向链表的第一个结点的存储位置，整个链表的存取操作都是从头指针开始的。如果有头结点，头指针就指向头结点。

对一个链表来说，头结点可有可无，但是头指针一定是存在的。

单链表的结构定义：

#include "stdio.h"
    #include "string.h"
    #include "ctype.h"
    #include "stdlib.h"
    #include "io.h"
    #include "math.h"
    #include "math.h"
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    #define MAXSIZE 20
    typedef int Status;//表示函数类型
    typedef int ElemType;//表示数据类型
    
    //链式存储结构
    typedef struct Node{
    	ElemType data;
    	struct Node *next;
    }Node;
    typedef struct Node *LinkList;//定义结构体类型的变量,并且是指针类型

单链表的基本操作：

//访问元素
    Status visit(ElemType val){
    	printf("%d ,",val);
    	return OK;
    }
    
    //初始化线性链表
    Status InitList(LinkList *L){
    	*L=(LinkList)malloc(sizeof(Node));//创建头结点，
    	if(!(*L)){
    		return ERROR;//存储空间分配失败
    	}
    	(*L)->next = NULL;//头指针的next为null，因为目前还是空链表
    	return OK;
    }
    
    //判断链表是否为null
    Status ListEmpty(LinkList L){
    	if(L->next){
    		return FALSE;
    	}else{
    		return TRUE;
    	}
    }
    
    //清空链表，如果需要对链表做出修改，这里的参数就是指向指针的指针变量，
    //前一个方法listEmpty只是判断非null，所以直接用结构体指针变量即可。
    Status ClearList(LinkList *L){
    	LinkList p,q;
    	p = (*L)->next;//p指向第一个节点
    	while(p){
    		q= p->next;
    		free(p);
    		p=q;
    	}
    	(*L)->next =NULL;//头指针的指针域置为null
    	return OK;
    }
    
    //获取链表的长度
    int ListLength(LinkList L){
    	int i=0;
    	LinkList p = L->next;//p指向第一个节点，因为L通常是传的头指针
    	while(p){
    		i++;
    		p=p->next;
    	}
    	return i;
    }
    
    //返回链表元素,i表示第几个元素
    Status GetElem(LinkList L,int i,ElemType *e){
    	int j =1;
    	LinkList p = L->next;
    	//循环条件，p不为null,且j没等于i
    	while(p && j<i){
    		p=p->next;
    		++j;
    	}
    	if(!p || j>i)
    		return ERROR;
    	*e = p->data;//用e返回查找的数据
    	return OK;
    }	
    
    //判断链表中是否存在某个元素,如果存在就返回其是链表的第几个元素
    int LocateElem(LinkList L,ElemType e){
    	int i =0;
    	LinkList p = L->next;
    	while(p){
    		i++;
    		if(p->data  == e)
    			return i;
    		p= p->next;
    	}
    	return 0;
    }
    
    //在指定位置前插入新的元素
    Status ListInsert(LinkList *L,int i,ElemType e){
    	int j;
    	LinkList p,s;
    	p = *L;//p指向头指针
    	j=1;
    	//查找插入位置，当j==i时，这时的p是p的next，所以接下来的插入位置是在p节点之后
    	while(p && j<i){
    		p = p->next;
    		++j;
    	}
    	if(!p || j>i)
    		return ERROR;
    	//创建新的节点
    	s = (LinkList)malloc(sizeof(Node));
    	s->data = e;
    
    	//执行插入操作
    	s->next = p->next;//s的后继指向p的后继
    	p->next =s;//p的后继指向s
    	return OK;	
    }
    
    //删除指定位置的元素，e表示删除的数据
    Status ListDelete(LinkList *L,int i,ElemType *e){
    	int j;
    	LinkList p,q;
    	p= *L;
    	j =1;
    	//查找删除的位置,从第一个节点开始判断非null,跟插入操作中的判断有的区别
    	//查找开始时p还是指向的头指针，当查找结束后，p->next是要删除的元素,p是要删除节点的前一个节点
    	while(p->next && j<i){
    		p= p->next;
    		++j;
    	}
    	if(!(p->next) || j>i)
    		return ERROR;
    
    	q= p->next;
    	//让p的指针域指向p的后继的后继
    	p->next =q->next;
    
    	*e = p->data;
    	free(q);	
    	return OK;
    }
    
    //遍历链表的元素
    Status ListTraverse(LinkList L){
    	LinkList p = L->next;
    	while(p){
    		visit(p->data);
    		p=p->next;
    	}
    	printf("\n");
    	return OK;
    }

//链表逆序
    LinkList* ReverseLinkList(LinkList *L){
    	LinkList prev,cur,latter;
    	prev = NULL;//第一个结点的前续先置为null
    	cur = (*L)->next;//当前节点，先指向第一个结点
    	latter = cur->next;//第一个结点的后继结点
    	while(cur){
    		cur->next = prev;//当前节点的后继指向前一个结点
    		prev =cur;//结点指向依次后移，前一个结点现在指向当前结点
    		cur = latter;//结点指向依次后移，当前结点指向后一个结点
    		if(cur != NULL){
    			latter = cur->next;//结点指向依次后移，后一个结点指向当前结点的下一个
    		}
    	}
    	(*L)->next =prev;	//修改头指针的指向。
    	
    	return L;
    }

//创建链表，从头部插入n个元素
    void CreateListHead(LinkList *L,int n){
    	LinkList p;
    	//设置随机数的种子
    	srand(time(0));
    	//创建头结点
    	*L = (LinkList)malloc(sizeof(Node));
    	(*L)->next =NULL;
    
    	for(int i =0; i<n; i++){
    		p= (LinkList)malloc(sizeof(Node));
    		p->data = rand()%100+1;//生成１～１００之间的数字
    		p->next = (*L)->next;
    		(*L)->next =p; //让插入的节点成为第一个节点
    	}
    }
    
    //创建链表，从尾部插入ｎ个元素
    void CreateListTail(LinkList *L,int n){
    	LinkList p,r;
    	srand(time(0));
    	*L = (LinkList)malloc(sizeof(Node));
    	r=(*L);//ｒ表示最后一个节点
    
    	for(int i =0; i<n; i++){
    		p=(LinkList)malloc(sizeof(Node));
    		p->data = rand()%100+1;
    		r->next =p; //尾部节点的指针域执行新的节点
    		r=p;//让新的节点变成表尾
    	}
    	r->next = NULL;
    }

测试代码：

int main(){
    	LinkList Head;
    	ElemType e;
    	Status i;
    	int j,k;
    	i = InitList(&Head);
    	printf("初始化Head后，ListLength(L)=%d\n",ListLength(Head));
    
    	for(j =1; j<=5; j++){
    		i = ListInsert(&Head,i,j);
    	}
    	printf("在Head的表头插入１，２，３，４，５后：");
    	ListTraverse(Head);
    	
    	i= ClearList(&Head);
    	printf("\n清空表后，ListLength(Head)=%d \n",ListLength(Head));
    
    	CreateListHead(&Head,10);
    	printf("从表头插入１０个元素：");
    	ListTraverse(Head);
    
    	i=ClearList(&Head);
    	
    	CreateListTail(&Head,30);
    	printf("从表尾插入３０个元素：");
    	ListTraverse(Head);
    	return 0;
    }

测试结果：

![20180311210517244][]

链表反转的测试以20个元素为例：

LinkList *Rev = ReverseLinkList(&Head);
        ListTraverse(Head);

42 ,24 ,72 ,13 ,31 ,16 ,28 ,40 ,24 ,39 ,86 ,43 ,90 ,16 ,79 ,38 ,19 ,77 ,64 ,43 ,  
43 ,64 ,77 ,19 ,38 ,79 ,16 ,90 ,43 ,86 ,39 ,24 ,40 ,28 ,16 ,31 ,13 ,72 ,24 ,42 ,

二，静态链表，

线性表的链式存储结构中，是用指针来表示后继节点的位置，如果一种编程语言中没有指针，也没有类似指针的引用机制，就无法使用上面的链式存储结构来表示链表了，这才有了静态链表－就是用数组来描述的链表，用数组来代替指针。

就是让数组的元素有两个数据域组成，data域和ptr域，data来存放数据，ptr来存放元素的后继在数组中的小标。

这种表示方法并不是很常用，只是在某些没有指针机制的语言中才会用。

三，循环链表

将单向链表的尾节点的指针域改为指向头结点，这种头尾相接的链表就称为单循环链表，也成循环链表。

单链表中的循环只能有一个方向，每次只能从头结点开始遍历，如果想反向查找是无法实现的。

所以有了双向链表。

四，双向链表

在单链表的每个结点中，在设置一个指向其前驱结点的指针域，就构成了双向链表。每个结点有两个指针域，一个指向后继，一个指向前驱。

结构定义

//双向链表
    typedef struct DulNode{
    	ElemType data;
    	struct DulNode *prior;//指向前驱
    	struct DulNode *next;//指向后继
    }DulNode;

双向链表的插入操作，将结点s插入到节点p之后：

![20180311213409632][]

这个过程的处理，顺序很重要，先把s节点的前驱、后继指好，再处理原链表节点的指针指向。

1)s->prior = p;

2)s->next =p->next;

3)p->next->prior=s;

4)p->next =s;

双向链表的删除，相对插入就简单多了

![2018031121395497][]

１）p->prior->next = p->next;

2) p->next->prior = p->prior;

[20180311210517244]: /images/20220530/3c7b6207fa674dcaaee8a78312d49f4c.png
[20180311213409632]: /images/20220530/061a30dcd35f4c6895b7ec5af0b586b0.png
[2018031121395497]: /images/20220530/6c82bba6e9c248e386c8fe396693ceba.png