首页 > 代码库 > 数据结构与算法-学习笔记6
数据结构与算法-学习笔记6
单链表的整表创建、删除
单链表的整表创建
思路：
-声明一个结点p和计数器变量i
-初始化一个空链表L
-让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
-循环实现赋值和插入
头插法建表
从一个空表开始，生成新结点，读取数据存放到新节点的数据域中，然后将新节点插入到当前链表的表头上，直到结束为止。
如，我们将hello插入链表中
代码：
void CreateListHead(LinkList *L,int e)
{
LinkList p;
int i;
srand(time(0));//随机种子,与time结合模拟随机数的效果
*L = (LinkList)malloc(sizeof(Node));//malloc生成一个结点
(*L)->next = NULL;
for(i = 0;i<n;i++)
{
p = (LinkList)malloc(sizeof(Node));
p->data = http://www.mamicode.com/rand()%100+1;//rand产生随机数，%100生成0~99的数
p->next = (*L)->next;
(*L)->next = p;
}
}
尾插法
与头插法相反
void CreateListHead(LinkList *L,int e)
{
LinkList p，r;
int i;
srand(time(0));//随机种子,与time结合模拟随机数的效果
*L = (LinkList)malloc(sizeof(Node));//malloc生成一个结点
r = *L;
for(i = 0;i<n;i++)
{
p = (Node *)malloc(sizeof(Node));
p->data = http://www.mamicode.com/rand()%100+1;//rand产生随机数，%100生成0~99的数
p->next = p;
r = p; //更改节点名的过程
}
p->next = NULL;
}
单链表的整表删除
思路：
-声明结点p和q
-将第一个结点赋值给p，下一个结点赋值给q
-循环执行释放p和q赋值给p的操作
代码：
status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next;
while(p)
{
q = p->next;
free(p);
p =q;
}
(*L)->next = NULL;
return OK;
}
单链表与顺序表存储结构优缺点
| 存储方式 | 时间性能 | 空间性能 | |
| 顺序存储 | 连续存储单元依次存储 线性表的数据元素 | 插入：O(1) 插入和删除：平均移动 表长的一半元素，时间 为O(n) | 容易溢出 |
| 单链表 | 用一组任意的存储单元 存放元素 | 插入：O(n) 插入和删除：计算位置 指针，时间仅为O(1) | 不需要分配存储空间 |
若线性表需要频繁查找，很少插入和删除，宜采用顺序存储结构
若线性表频繁插入和删除时，宜采用单链表结构
数据结构与算法-学习笔记6