C语言学习----链表及链表的基本操作

关于链表的TIPS**

链表中各结点在内存中可以不是连续存放的
在链表结点的数据结构中，结构体内的指针域的数据类型可以使用未定义成功的数据类型，这是C语言中唯一规定可以先使用后定义的数据结构
头指针：存放一个地址(头结点地址），指向第一个结点（一定不要把头结点当做头指针，头指针只不过是储存头结点的地址而已，我在学的时候这里总出错）
具体链表的结构体建立，包括链表的指针域和数据域如下：

struct student
{
  int num;
  float score;
  student *next;
};

建立单链表的一些约定
- 每个结点类型用LinkList表示
- 数据域 data（类型：通用类型标识符 ElemType）
- 指针域 next

 typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LinkList;

创建单链表

头插法
新产生的结点作为新的表头插入链表

（第一次执行②的作用是确定尾指针NULL）

#include<stdio.h>

LinkList*CreateListF(ElemType a[],int n)
{
    LinkList*head,*s;
    int i;
    head = (LinkList*)malloc(sizeof(LinkList));    //创建头结点
    head->next = NULL;
    for(i=0;i<n;i++)
    {
        s = (LinkList*)malloc(sizeof(LinkList));    //创建新结点
        s->data=a[i];
        s->next=head->next;    //第一次执行时是为了确定尾指针NULL
        head->next=s;    //将*s插在原开始结点之前、头结点之后
    }
    return head;
}

2.尾插法（一句话，相当于不断开创新的结点，然后不断将新的结点的地址当做尾结点。尾结点不断后移，而新创的结点时按照创建的先后顺序而连接的。先来先到）

Linklist Creat_list(Linklist head) {
    head = (Linklist)malloc(sizeof(Lnode));          //  为头指针开辟内存空间
    Linklist node = NULL;           //  定义结点
    Linklist end = NULL;            //  定义尾结点
    head->next = NULL;              //  初始化头结点指向的下一个地址为 NULL
    end = head;                     //  未创建其余结点之前，只有一个头结点
    int count = 0 ;                 //  结点个数
    printf("Input node number: ");
    scanf("%d", &count);
    for (int i = 0; i < count; i++) {
        node = (Linklist)malloc(sizeof(Lnode));          //  为新结点开辟新内存
        node->data = i;                                  //  新结点的数据域赋值
        end->next = node;                              
        end = node;
    }
    end->next = NULL;
}

尾插法的详解：

主要思路：新的结点插入到当前链表的表尾，使其成为当前链表的尾结点（以下以两个结点的创建为例，其余的读者可以自己思考推导一下）
尾插法创建第一个结点
1. 刚开始为头结点开辟内存空间，接着将头结点的指针域 head->next 的地址赋为 NULL。
2. 此时，整个链表有且只有一个头结点，所以这时head既是头结点，又是尾结点。将头结点的地址赋给尾结点end后：end = head。（end->next 也自然指向的是 NULL啦。）
尾插法创建第二个结点
1. 创建完第一个结点之后，我们开始创建第二个结点。第一个结点，end 和 head 共用一块内存空间。现在开辟出一块内存给 node，将 node 的数据域赋值后，此时 end 中存储的地址是 head 的地址。此时，end->next 代表的是头结点的指针域，因此 end->next = node 代表的就是将上一个，也就是新开辟的 node 的地址赋给 head 的下一个结点地址。
2. 此时，end->next 的地址是新创建的 node 的地址，而此时 end 的地址还是 head 的地址。因此 end = node ,这条作用就是将新建的结点 node 的地址赋给尾结点 end。此时 end 的地址不再是头结点，而是新建的结点 node。
最后，当结点创建完毕，不会有新的结点来替换 end ，所以最后需要加上一条 end->next = NULL。将尾指针的指向为 NULL。

单链表的基本运算

初始化链表InitList

LinkList*InitList()
{
    LinkList*head;
    head=(LinkList*)malloc(sizeof(LinkList));
    head->next=NULL;
    return head;
}

销毁链表
逐一释放全部结点空间

void DestroyList(LinkList*head)
{
    LinkList*p=head,*q;
    while(p!=NULL)
    {
        q=p;
        p=p->next;
        free(q);
    }
}

3.求链表长度

int ListLength(LinkList*head)
{
    LinkList*p=head;
    int i=0;
    while(p!=NULL)
    {
        i++;
        p=p->next;
    }
    return(i);
}

4.判定链表是不是空表

int ListEmpty(LinkList*head)
{
    return(head->next==NULL);
}

5.输出链表

void DispList(LinkList*head)
{
    LinkList*p=head;
    while(p!=NULL)
    {
        printf("%c",p->data);
        p=p->next;
    }
    printf("\n");
}

6.求指定位置的某个数据元素(在链表中从头开始找到第i个数据结点，若存在，则将其data域值通过变量e带回）

int GetELem(LinkList*head,int i,Elem Type*e)
{
    int j=1;
    LinkList*p=head->next;
       while(p!=NULL&&j<i)
        {
            j++;
            p=p->next;
        }
        if(p==NULL)
            return 0;
        else
            {
                *e=p->data;
                return 1;    //表示代码执行成功
            }
}

7.按元素值定位查找（在链表中从头开始找第一个值域与e相等的结点，若存在，则返回其次序，否则返回0）

int LocateElem(LinkList*head,Elem Type e)
{
    int n=1;
    LinkList*p=head->next;
    while(p!=NULL&&p->data!=e)
    {
        n++;
        p=p->next;
    }
    if(p=NULL)
        return 0;
    else
        return n;
}

8.插入数据元素（先在链表中找到第i个结点p，若存在，将值为e分结点s插入其后）

int ListInsert(LinkList*head,int i,ElemType e)
{
    int j=0;
    LinkList*p=head,*s;
    while(p!=NULL&&j<i-1)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return 0;
    else
    {
        s=(LinkList*)malloc(sizeof(LinkList));
        s->data=e;
        s->next=p->next;
        p->next=s;
        return 1;
    }
}

9.删除数据元素

int ListDelete(LinkList*head,int i,ElemType e)
{
    int j=0;
    LinkList*p=head,*q;
    while(p!=NULL&&j<i-1)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return 0;
    else
    {
        q=p->next;
        if(q==NULL)
            return 0;
            p->next=q->next;
            free(q);
            return 1;
    }
}

2020.4.25 疫情期间小陈的第一篇C语言笔记
下次更新链表的几个比较难懂的操作，本人还在认真研究。