学习算法和数据结构的第15天

单链表的实现

顺序表的缺陷

​ 1、空间不够需要扩容，扩容存在消耗

2、头部或中间的位置插入删除，需要挪动，挪动数据也存在消耗；

3、避免频繁的进行扩容，一次扩容一般都是按数倍去扩（2倍），可能存在一定的空间浪费。

优点：

​ 支持随机访问

（有些算法，需要结构支持随机访问，比如：二分查找、优先的快排等）

链表

​ 优点：

1、按需申请空间，不用了就释放空间（更合理的利用空间）

2、头部插入删除数据，不需要挪动数据，不存在空间浪费；

缺点：

​ 每一个数据，都需要存一个指针去链接后面数据节点（用下标直接访问第i个），不支持随机访问

尾插、头插

#include
#include"sList.h"
SLTNode*BuyListNode(SLTDateType x)
{
    SLTNode*newnode=(SLTdate*)malloc(sizeof(SLTNode));
    newnode->date=x;
    newnode->next=NULL;
    return 0;
}
void SListPrint(SLTNode*phead)
{
    SLTNode*cur=phead;
    while(cur!=NULL)
    {
        printf("%d->",cur->date);
        cur=cur->next;
    }
    printf("NULL\n");
}
//尾插
void SListPushBak(SLTNode**pphead,SLTDateTpye x)
    SLTNode*newode=(SLTNode*)malloc(sizeof(SLTNode));
newode->data=x;
newode->next=NULL;
if(*pphead==NULL)
{
    *pphead=newnode;
}
else
{
    //找到结尾点
    SLTNode*tail=*pphead;
    while(tail->next!=NULL)
    {
        tail=tail->next;
    }
    tail->next=nowode;
}
void SListPushFront(SLTNode**pphead,SLTDateTpye x)
{
    SLTNode*newnode=BuyListNode(x);
    newnode->next=*pphead;
    *phead=newnode;
}
//头插
void TestSList2()
{
    SLTNode*plist = NULL;
SListPushBack(&plist,1);
SListPushBack(&plist, 2);
SListPushBack(&plist,3);
SListPushBack(&plist,4);
    
SListPrint(plist);
    
SListPushFront(&plist, 1);
SListPushFront(&plist,2);
SListPushFront(&plist,3);
SListPushFront(&plist,4);
    
SListPrint(plist);
}
int main()
{
    TestSList2();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67