线性表的链式存储结构

您所在的位置：网站首页 › 线性表的链表实现 › 线性表的链式存储结构

线性表的链式存储结构

2023-08-12 01:59| 来源: 网络整理| 查看: 265

文章目录 1.单链表的建立1.1头插法1.2尾插法 2.链表基本操作

1.单链表的建立 1.1头插法

1)从一个空表开始，创建一个头结点。

2)依次读取数组a中的元素，生成新节点。

3)将新节点插入到当前链表的表头上，直到结束为止，插入过程如下图所示。

在这里插入图片描述

首先定义单链表节点类型，LinkNode类型声明如下：

typedef struct LNode { int data; struct LNode *next;//存储后继节点位置的指针域，用next表示 }LinkNode;

头插法代码如下，由数组元素a创建单链表L

void CreatListF(LinkNode * &L,int a[],int n) //头插法建立单链表 { LinkNode *s; L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点并将其next域置位NULL L->next=NULL; for(int i=0;i LinkNode *s,*r; L=(LinkNode *)malloc(sizeof(LinkNode)); r=L; //r始终指向尾节点，初始时指向头结点 for(int i=0;i L=(LinkNode *)malloc(sizeof(LinkNode));//创建一个空的单链表 L->next=NULL; }

2)销毁链表

该运算会释放L所占的内存空间，其过程是让pre，p指向两个相邻的节点，

当p不为空时循环，释放pre，然后p，pre同步后移一个节点，如下图所示。在这里插入图片描述实现销毁操作如下

void DestoryList(LinkNode * &L)//销毁线性表 { LinkNode *pre=L,*p=L->next; //pre指向p的前驱节点 while(p!=NULL) //扫描单链表 { free(pre); //释放pre节点 pre=p; //pre,p同步后移一个节点 p=pre->next; } }

3)判断链表是否为空

bool ListEmpty(LinkNode *L)//判断链表是否为空 { return(L->next==NULL); }

4)求链表的长度

由于链表没有存放节点个数的信息，所以需要遍历链表，用n来记录节点个数

int ListLength(LinkNode *L)//求链表长度 { int n=0; LinkNode *p=L;//p指向头结点，n置为0 while(p->next!=NULL) { n++; p=p->next; } return n; }

5)输出链表

void DispList(LinkNode *L) { LinkNode *p=L->next;//p指向首节点 while(p!=NULL) { printf("%d ",p->data); p=p->next; //p移向下一节点 } printf("\n"); }

6)查找链表第i个元素值

从头结点开始遍历，用 j 来累计遍历过的节点个数，直到第i个节点，将元素值赋给tmp。

bool GetElem(LinkNode * &L,int i,int &tmp)//求链表第i个元素值 { int j=0; LinkNode *p=L;//p指向头结点 if(i tmp=p->data; return true;//提取值成功，返回true } }

6)插入数据节点

遍历单链表找到第 i-1 个节点 p ，将元素值为e的节点*s插入到其后在这里插入图片描述实现如下：

bool ListInsert(LinkNode * &L,int i,int e)//插入数据元素 { int j=0; LinkNode *p=L,*s; while(j s=(LinkNode *)malloc(sizeof(LinkNode)); //将s节点插入 s->data=e; s->next=p->next; p->next=s; return true; } }

7)删除数据节点

遍历单链表找到第 i-1 个节点 p，若存在这样的节点也存在后继节点，则删除该后继节点在这里插入图片描述实现如下：

bool ListDelete(LinkNode * &L,int i) { int j=0; LinkNode *p=L,*q; while(j q=p->next; if(q==NULL) return false; p->next=q->next;//删除q节点 free(q); return true; } }

【本文地址】

线性表的链式存储结构

线性表的链式存储结构

今日新闻

推荐新闻