数据结构学*笔记--单链表

发布于:2021-10-27 02:20:38

中国大学MOOC数据结构的单链表学*笔记
单链表

单链表中节点的定义

#include
#include
#include
typedef char ElemType;
typedef struct LNode//定义单链表节点类型
{
ElemType data;
struct LNode *next;//指针指向后继节点
}LinkList;

单链表的特点是:当访问过一个节点,只能接着访问它的后继节点,而无法访问它的前驱节点。



插入节点操作

插入操作语句描述


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

用图描述或许更直观一点



删除节点操作

操作语句描述


p->next=p->next->next



建立单链表

像顺序表一样,也是整体建立单链表
有两种方法:头插法和尾插法


头插法建表

从一个空表开始,创建一个头节点。
依次读取数组a中的元素,生成新节点。
将新节点插入到当前链表的表头上,直到结束为止。
注意:链表的节点顺序与逻辑次序相反。


void CreateList(LinkList *&L, ElemType a[], int n)
{
LinkList *s;
int i;
L = (LinkList*)malloc(sizeof(LinkList));
L->next = NULL;//创建头节点,将其next域置为NULL
for (i = 0; i < n; i++)
{
s = (LinkList*)malloc(sizeof(LinkList));
s->data = a[i];//创建数据节点*s
s->next = L->next;//将*s插在原开始节点之前,头节点之后
L->next = s;
}
}


尾插法建表

从一个空表开始,创建一个头节点。
依次读取字符数组a中的元素,生成新节点。
将新节点插入到当前链表的表尾上,直到结束为止。
注意:链表的节点顺序与逻辑次序相同。


void CreateListR(LinkList *&L, ElemType a[], int n)
{
LinkList *s, *r;
int i;
L = (LinkList*)malloc(sizeof(LinkList));//创建头节点
r = L;//r始终指向尾节点,开始时指向头节点
for (i = 0; i < n; i++)
{
s = (LinkList*)malloc(sizeof(LinkList));
s->data = a[i];//创建数据节点*s
r->next = s;//将*s插入*r之后
r = s;
}
r->next = NULL;//尾节点next域置为NULL
}


线性表基本运算在单链表上的实现

初始化线性表

void InitList(LinkList *&L)
{
L = (LinkList *)malloc(sizeof(LinkList));
L->next = NULL;
}


销毁线性表

一个节点一个节点地销毁,需要设置前趋节点


void DestroyList(LinkList *&L)
{
LinkList *pre = L, *p = L->next;//pre为指向*p的前趋节点
while (p != NULL)//扫描单链表
{
free(pre);//释放*pre节点
pre = p;//pre和p同步向后移一个节点
p = p->next;
}
free(pre);
}


判断线性表是否为空表

int ListEmpty(LinkList *L)
{
if (L->next == NULL)
return 1;//是空表
else return 0;//不是空表
}


求线性表的长度

int ListLength(LinkList *L)
{
int n = 0;
LinkList *p = L;//p指向头节点,n置为0(即头节点的序号为0)
while (p->next != NULL)
{
n++;
p = p->next;
}
return(n);//循环结束,p指向尾节点,其序号n为节点个数
}


输出线性表

void DisList(LinkList *L)
{
LinkList *p = L->next;//p指向开始节点
while (p != NULL)
{
printf("%d", p->data);
p = p->next;
}
printf("
");
}


求线性表L中位置为i的元素

思路:在单链表L中从头开始找到第i个节点,若存在第i个数据节点,则将其data阈值赋给变量e


int GetElem(LinkList *L, int i, ElemType &e)
{
int j;
LinkList *p = L;//p指向头节点,j置为0
while (j < i&&p != NULL)
{
j++;
p = p->next;
}
if (p == NULL) return 0;
else
{
e = p->data;
return 1;
}
}


按元素值查找

思路:在单链表L从头开始找第1个值域与e相等的节点,若存在这样的节点,则返回位置,否则返回0。


int LocateElem(LinkList *L, ElemType e)
{
int i = 1;
LinkList *p = L->next;//p指向开始节点,i置为1
while (p != NULL && p->data != e)
{
p = p->next; //查找data值为e的节点,其序号为i
i++;
}
if (p == NULL)
return(0);
else return(i);
}


插入数据元素

思路:先在单链表L中找到第i-1个节点*p,若存在这样的节点,将值为e的节点*s插入到其后。


int ListInsert(LinkList *&L, int i, ElemType e)
{
int j = 0;
LinkList *p = L, *s;//p指向头节点,j置为0
while (j < i - 1 && p != NULL)
{
j++;
p = p->next;
}
if (p == NULL)//未找到第i-1个节点
{
return 0;
}
else
{
s = (LinkList*)malloc(sizeof(LinkList));
s->data = e;//创建新节点
s->next = p->next;//将*s插入到*p后
p->next = s;
return 1;
}
}


删除数据元素

思路:先在单链表中L找到第i-1个节点*p,若存在这样的节点,且存在后继节点,则删除该后继节点


int ListDelete(LinkList*&L, int i, ElemType &e)
{
int j = 0;
LinkList*p = L, *q;
while (j < i - 1 && p != NULL)
{
j++;
p = p->next;
}
if (p == NULL)
{
return 0;
}
else
{
q = p->next;
if (q == NULL)
return 0;
e = q->data;
p->next = q->next;
free(q);
return 0;
}
}

该资源来源于中国大学MOOC,仅为个人学*后做的读书笔记,我摘抄下来加深记忆与理解。

相关推荐

最新更新

猜你喜欢