学习笔记：链表

链表结构

一种常见的链表结构定义：

1
2
3
4
5
6
struct List
{
    int num;
    struct List *nextPtr;
};
typedef struct List LIST;

其中，包含有其存储的数值num（数据域），以及一个指向与自身同一个类型结构的指针（指针域），指向该链式结构的下一个单元

链表的构建

  1. 声明表头指针
  2. 节点内存动态分配
  3. 链接各单元
  4. 循环

对于构建链表与读入、存储数据的一种代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int inputnum;
scanf("%d", &inputnum); //读入第一个数据
LIST *headPtr = NULL, *nowPtr = NULL, *lastPtr = NULL;
while(inputnum!=-1)
{
    nowPtr = malloc(sizeof(LIST *)); //节点内存动态分配
    nowPtr->num = inputnum;
    if(headPtr==NULL)
    {
        headPtr = nowPtr;
        lastPtr = nowPtr;
    }
    else
    {
        lastPtr->nextPtr = nowPtr;
        lastPtr = nowPtr;
    }
    scanf("%d", &inputnum); //循环读入数据
}
lastPtr->nextPtr = NULL;

逐项读取/输出链表内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void outputLIST(LIST *headPtr)
{
    LIST *currentPtr = headPtr, *frontPtr = headPtr;
    printf("The new list is:");
    while (1)
    {
        if(currentPtr!=headPtr)
            printf(" ");
        if(currentPtr!=NULL)
        {
            printf("%d", currentPtr->num);
            frontPtr = currentPtr;
            currentPtr = currentPtr->nextPtr;
        }
        if(currentPtr==NULL)
        {
            printf("\n");
            break;
        }
    }
    return;
}

释放链表结点内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void freeLIST(LIST *heatPtr)
{
    LIST *currentPtr, *frontPtr;
    currentPtr = heatPtr;
    while (1)
    {
        frontPtr = currentPtr;
        if(currentPtr->nextPtr!=NULL)
            currentPtr = currentPtr->nextPtr;
        else
            break;
        free(frontPtr);
    }
    return;
}

对于链表内容的排序

  • 变量num来自于创建链表时记录的结点数量
  • LIST **headPtr是头结点的地址&headPtr（传递其地址指针）。因为需要对头结点指向的第一个结点（头结点的数值）进行修改
  • 使用哨兵结点（第一个结点数值为空），避免修改具有数值的第一个结点时判断、修改头结点的琐碎操作 但是在这里并没有实现
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
void orderLIST(LIST **headPtr,int num)
{
    LIST *beforePtr, *nowPtr, *afterPtr;
    LIST *cache;
    int i;
    if(num==1||num==2)
    {
        if(num==1)
            return;
        if(num==2)
        {
            beforePtr = *headPtr;
            nowPtr = beforePtr->nextPtr;
            if(beforePtr->num > nowPtr->num)
            {
                cache = beforePtr;
                beforePtr->nextPtr = nowPtr->nextPtr;
                nowPtr->nextPtr = cache;
                *headPtr = nowPtr;
            }
            return;
        }
    }
    for (i = 1; i <= num;i++)
    {
        beforePtr = *headPtr;
        nowPtr = beforePtr->nextPtr;
        afterPtr = nowPtr->nextPtr;
        if(beforePtr->num > nowPtr->num)
        {
            cache = beforePtr;
            beforePtr->nextPtr = nowPtr->nextPtr;
            nowPtr->nextPtr = cache;
            *headPtr = nowPtr;
        }
        beforePtr = *headPtr;
        nowPtr = beforePtr->nextPtr;
        afterPtr = nowPtr->nextPtr;
        while(1)
        {
            if(nowPtr->num > afterPtr->num)
            {
                cache = afterPtr->nextPtr;
                beforePtr->nextPtr = afterPtr;
                afterPtr->nextPtr = nowPtr;
                nowPtr->nextPtr = cache;
            }
            beforePtr = beforePtr->nextPtr;
            nowPtr = beforePtr->nextPtr;
            afterPtr = nowPtr->nextPtr;
            if(afterPtr==NULL)
                break;
        }
    }
    return;
}