8.0、C语言数据结构——线性表 (4)
单链表的整表创建 ->
? ? ? ? 1. 对于顺序存储结构的线性表的整表创建，我们可以用数组的初始化来直观理解；
? ? ? ? 2.而单链表和顺序存储结构就不一样了，它不像顺序存储结构数据这么集中，他的数据可以使分散在内存各个角落的，他的增长是动态的；
? ? ? ? 3. 对于每个链表来说，他占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求及时生成；
? ? ? ??
单链表的创建 ->?
? ? ? ? 1. 创建单链表的过程是一个动态生成链表的过程，从空表的初始状态起，依次创建各元素结点并逐个插入链表；
? ? ? ? 2. 所以单链表整表创建的算法思路如下：
? ? ? ? - 声明一结点 p 和计数器变量 i;
? ? ? ? - 初始化一个空表 L ；
? ? ? ? - 让 L 的头结点的指针指向 NULL ，即建立一个带头结点的单链表；
? ? ? ? - 循环实现后继结点的赋值和插入；
?
1. 头插法建立表单
? ? ? ? 1. 头插法从一个空表开始，生成新结点，读取数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，知道结束为止；
? ? ? ? 2. 简单来说，就是把新加进的元素放在表头后的第一个位置；
? ? ? ? - 先让新结点的 next 指向头结点之后；
? ? ? ? - 然后让表头的 next 指向新结点；
? ? ? ? 3. 用现实环境模拟的话就是插队的方法，始终让新结点插在第一的位置；
void CreateListHead(LinkList* L , int n) {
LinkList p;
int i;
srand(time(0)); //初始化随机数种子
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
for(i = 0;i < n;i++) {
p = (LinkList)malloc(sizeof(Node));//生成新结点
p->data = rand()%100 + 1;
p->next = (*L)->next;
(*L) -> next = p;
}
}
2. 类比头插法 来看看 尾插法：
头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入和顺序相反；
那我们把思维逆转 -> 把新结点都插入到最后，这种算法称为 尾插法；
void CreateListTail(LinkList* L , int n) {
LinkList p , r;
int i;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for(i = 0;i < n;i++) {
p = (Node *)malloc(sizeof(Node));
p -> data = rand()%100 + 1;
r->next = p;
r = p;
}
r -> next = NULL;
}
????????1. 规定：变量 r 永远指向末尾元素；
????????2. 比如在数据 ai-1 后面插入一个ai 那么未插入前 r 指向 ai-1 ，当 ai 插入后将 变量 p 指向?ai，最后让 r 指向 p 然后将 r 指向 ai （因为此时 ai 是末尾元素）；
????????3. 再插入 ai + 1 同理此时 r 一定是指向 ai 的，然后将变量 p 指向 ai + 1，最后将 r 指向 p 然后将 r 指向 ai + 1（因为此时 ai + 1 是末尾元素）;
? ? ? 我们分别从存储分配方式、时间性能、空间性能 三个方面来做对比；
存储分配方式 ->
? ? ? ? - 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；
? ? ? ? - 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素；
时间性能 ：
查找->
? ? ? ? - 顺序存储结构 O(1);
? ? ? ? - 单链表 O(n)；
插入和删除->
? ? ? ? - 顺序存储结构需要平均移动表长一半的元素，时间为 O(n)；
? ? ? ? - 单链表在计算出某位置的指针后，插入和删除时间仅为 O(1)；
空间性能：
? ? ? ? - 顺序存储结构需要预分配存储空间，分大了，容易造成空间浪费，分小了，容易发生溢出；
? ? ? ? - 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制；
?综上所述对比：
? ?? ? ?- 我们可以得出 -> 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构；
? ? ? ? - 若需要频繁插入和删除时，宜采用单链表结构；?
|