数据结构单链表的基本操作与运算任务背景是什么

Question

如题所述

Answer 1

，基本运算

1，单链表，双链表的定义：
设计链式存储结构时，每个逻辑节点存储单独存储。

2，单链表的基本结构： 

头节点在前，首节点在后。

3，顺序表与链表间存储密度的差异：
顺序表的存储密度为1，而链表的存储密度小于1。

4，

typedef struct LNode
{
ElemType data; //存放元素值
struct LNode *next; //指向后继节点
}LinkNode //单链表节点类型
登录后复制
一个是数据域部分，一个是指向后继节点的指针域。

5，特点：

6，插入节点：

s→next=p→next
p→next=s
登录后复制
p指针指向一个节点。

如图7所示，删除节点：

p→next=p→next→next
登录后复制
二，基本算法

如图1所示，头插法建表

void CreatListF(LinkNode *&L,ElemType a[],int n)
{
LinkNode *s;
L=(LinkNode *)malloc(sizeof(LinkNode));
L→next=NULL; //创建头节点，其next域置为NULL
for(int i=0;i<n;i++) //循环建立数据节点s
{
s=(LinkNode *)malloc(sizeof(LinkNode));
s→data=a[i]; //创建数据节点s
s→next=L→next; //将s插入到原首节点之前、头节点之后
L→next=s;
}
}
登录后复制

这个算法的时间复杂度为O（N）。

链表的节点顺序和逻辑顺序正好相反。

2，尾插法建表

void CreateListR(ListNode *&L,ElemType a[],int n)
{
LinkNode *s,*r;
L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
r=L; //r始终指向尾结点，初始时指向头结点
for(int i=0;i<n;i++) //循环建立数据结点
{
s=(LinkNode *)malloc(s