【单链表】基于C++链式存储结构的实现

1.数据结构中，线性表的储存是最重要的，有顺序存储的顺序表，和链式存储的单链表（当然还有双链表，循环链表，此处只讨论单链表）。顺序表是基于数组实现的，而单链表主要是居于链式存储实现的。下面我们来看看单链表的创建。

2.主要思想：

创建一个链表，一般结构体中需要两个属性：指针（必不可少）、存放的数据类型（不是必须的，但基本会使用到，以整形为例）。创建好头节点（主要是为了方便操作）,将其他的节点链接在头节点的后面，这时出现了两种思想：头插法，和尾插法。

a.头插法

【单链表】基于C++链式存储结构的实现

将创建的第一个节点链接在头节点之后，当第二个节点创建后，将它继续链接到头节点之后，第一个节点之前，如此循环下去，即每一个当前创建的新节点总是连接到头节点之后和之前之个节点之前。

代码如下:

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//创建结构体
typedef struct LNode{
int data;
struct LNode *next;
} LNode,*LNodep;

//函数声明
LNodep create_list(void);
void traverse_list(LNodep pHeader);

int main(void){
LNodep pHeader=NULL;
pHeader=create_list();
traverse_list(pHeader);
return 0;
}

LNodep create_list(void){
int len;
int i;
int val;

LNodep pHeader=(LNodep)malloc(sizeof(LNode));
pHeader->next=NULL;
if(pHeader==NULL){
printf("内存分配失败，程序终止\n");
exit(-1);
}
printf("请输入要创建的长度 len=");
scanf("%d",&len);
for(i=0;i<len;++i){
printf("请输入第%d个节点的值",i+1);
scanf("%d",&val);

LNodep Newp=(LNodep)malloc(sizeof(LNode));
if(Newp==NULL){
printf("分配失败，程序终止\n");
exit(-1);
}
Newp->data=val;
Newp->next=pHeader->next;
pHeader->next=Newp;

}

return pHeader;
}

void traverse_list(LNodep pHeader){
LNodep p=pHeader->next;

while(p!=NULL){

printf(" %d",p->data);
p=p->next;
}
printf("\n");

}

结果展现：

【单链表】基于C++链式存储结构的实现

插入节点似乎有‘栈’的味道，最先插入的节点被放置在表尾，最后插入的在表头。

每个节点插入的时间为O(1),若整个链表长度为n,时间复杂度O(n)

b.尾插法：

【单链表】基于C++链式存储结构的实现

在创建头节点后，对新创建的节点链接在头节点之后，然后指针后移，将一下创建的节点继续链接在上一个节点之后。

核心代码如下：

LNodep pHeader=(LNodep)malloc(sizeof(LNode));
LNodep pTail=pHeader; //pTail 是指向头节点的指针

pTail->next=NULL;

if(pHeader==NULL){
printf("内存分配失败，程序终止\n");
exit(-1);
}
printf("请输入要创建的长度 len=");
scanf("%d",&len);
for(i=0;i<len;++i){
printf("请输入第%d个节点的值",i+1);
scanf("%d",&val);

LNodep Newp=(LNodep)malloc(sizeof(LNode));
if(Newp==NULL){
printf("分配失败，程序终止\n");
exit(-1);
}
Newp->data=val;
pTail->next=Newp;
Newp->next=NULL;
pTail=Newp;
}

return pHeader;

}

结果展示

【单链表】基于C++链式存储结构的实现

结果很类似‘队列‘，先插入的表头，后插入的在表尾。

整个链表长度为n,时间复杂度O(n);

写在最后（不一定正确，但是会很好理解）：

很多人在创建的时候，不能把握指针该如何指向的，什么时候指

Newp->next=pHeader->next // 此时'='作用是赋值，把一个指针赋值给另一个指针

pTail->next=Newp //此时'='是指向，即pTail指向Newp

头插法只是使用了本身的指针而已，让指针后移。

尾插法则是使用了一个指向头指针的指针，再让其后移。

【单链表】基于C++链式存储结构的实现

相关推荐