欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

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

程序员文章站 2022-06-05 14:59:29
...

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

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

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

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

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

单链表的结构定义：

#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;
}

测试结果：

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

链表反转的测试以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之后：

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

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

1)s->prior = p;

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

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

4)p->next =s;


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

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

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

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

相关标签： 线性链表链式存储 双向链表的插入删除

上一篇： 链式存储结构

下一篇： Yahoo! 的 PHP Developer Center

推荐阅读