线性表的链式存储结构
标签（空格分隔）： DS 线性表 链式存储
1.线性表的单链表存储结构
typedef struct Node
{
ElemType data;//数据域
struct Node *next;//指针域
}Node,* pNode;//节点，节点指针
typedef struct Node* LinkList;//头指针指向头节点
2.单链表的读取第i个元素
思路：
1.声明一个指针p指向第一个节点
2.遍历链表，让p不断指向下一个节点直到指向第i个节点
3.若到链表尾都没有指向第i个元素，p=NULL,则说明第i个元素不存在，找不到
4.若找到，返回p的数据
Status GetElem(LinkList L, int i, ElemType *e)
{
pNode p;//声明指向指针
p=L->next;//指向第一个节点
int j=1;//j为计数器，统计指向第几个节点
while(p!=NULL&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i)
return ERROR;//没找着
*e=p->data;//找着了
return OK;
}
3.单链表在第i个节点后插入
思路：
1.首先要找到第i个节点(参考单链表的读取）
1.1如果找到了，生成一个空节点s，将要插入的元素e赋值给s->data,然后把节点s插入链表；
1.2如果没找到，则错误
Status ListInsert(LinkList L, int i, ElemType e)
{
pNode p;
p=L->next;
int j=1;
while(p!=NULL&&j<i)//寻找第i个节点
{
p=p->next;
++j;
}
if(!p||j>i)
return ERROR;
pNode s=(pNode)malloc(sizeof(Node));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
4.单链表删除第i个节点
思路：
1.声明一个节点指针p指向第一个节点，并不断后移，查找第i个节点(p指向第i-1个节点）
1.1结果1：p->next=NULL,则第i个节点不存在
1.2结果2：查找成功
Status ListDelete(LinkList L, int i, ElemType *e)
{
pNode p;//声明指向指针
p=L;//指向头节点
int j=1;//j为计数器，统计指向第几-1个节点
while(p->next!=NULL&&j<i)
{
p=p->next;
++j;
}
if(!(p->next)||j>i)
return ERROR;//没找着
*e=p->next->data;//找着了
q=p->next;//q指向第i个节点
p->next=q->next;//使原本指向第i个节点的指针指向第i+1个节点
free(q);//回收第i个节点的空间
return OK;
5.单链表的整表创建
思路：
1.创建一个空表L并初始化
2.节点指针p依次申请各元素节点空间并初始化
3.将新节点插入表
//头插法
void CreateListHead(LinkList L, int n)
{
L=(LinkList)malloc(sizeof(Node));//L为头指针，指向头节点
L->next=NULL;//初始化头节点
pNode p;
srand(time(0));//初始化随机数种子,
for(int i=0;i<n;i++)
{
p=(pNode)malloc(sizeof(Node));//p指向一块node型空间
p->data=rand()%100+1;//初始化p指向的节点
p->next=L->next;
L->next=p;//头插法
}
}
//尾插法
void CreateListTail(LinkList L, int n)
{
L=(LinkList)malloc(sizeof(Node));//L为头指针，指向头节点
L->next=NULL;//初始化头节点
pNode p,r;//p为新节点指针，r为链表尾指针
r=L;//空表尾指针指向头节点
for(int i=0;i<n;i++)
{
p=(pNode)malloc(sizeof(Node));//p指向一块node型空间
p->data=rand()%100+1;//初始化p指向的节点
r->next=p;
r=p;//尾插法
}
r->next=NULL;//表示当前链表结束
}
6.单链表的整表删除
思路：
1.声明一个指向待删除节点的指针p，和一个定位指针q；
2.p指向第一个节点，q指向下一个节点；
3.释放p指向节点的空间后，p指向q的节点成为下一个待删除的节点，q再指向p的下一个节点
4.直到p=NULL,即全部删除完
5.使空表的指针指向NULL
Status ClearList(LinkList L)
{
pNode p,q;
p=L->next;
while(p)
{
q=p->next;
free(p);
p=q;
}
L->next=NULL;
return OK;