C语言进阶-第18讲：单链表的遍历、创建、插入和删除结点

任务和代码：

 

       遍历链表：

void traverse(Node *h){
    Node *p;   //p作为用来遍历的指针
    p=h;
    while(p!=NULL){
        printf("%-5d",p->data); //访问结点信息
        p=p->next;              
    }
    printf("\n");
}

       顺序创建动态链表：

      （一）

/*
返回值：指向头结点的指针
参数：链表长度
说明：新建链表就是不断插入新的结点
*/
Node *createLinkList(int n){
    Node *h=NULL,*p,*last;  //p指向新增结点，last指向尾结点
    int d;                  //要插入结点的元素值
    int i;
    for(i=0;i<n;i++){
        scanf("%d",&d);
        p=(Node*)malloc(sizeof(Node));
        p->data=d;          //添加新增结点的信息
        p->next=NULL;
        if(h==NULL) 
            h=p;            //h为空，p是第一个结点的地址，h指向p
        else
            last->next=p;   //新增结点的前一个结点的指针域是新增结点的地址
        last=p;             //last代表新增的最后一个结点的地址
    }
    return h;
} 

      

      （二）

S *create(int n)  
{  
    S *p,*q,*head;  
    head=p=q=malloc(sizeof(S));  //先建立头结点（头指针不能变，故放在循环体前）
    scanf("%d",&p->date);  
    while(--n)                   //添加后面的n-1个结点
    {  
        p=malloc(sizeof(S));  
        scanf("%d",&p->date);  
        q->link=p;  
        q=p;  
    }  
    q->link=NULL;  
    return head;  
} 

       

        倒序创建动态链表：

Node* make_list(int n){    
    Node *p;  
    h=NULL;  
    printf("输入若干正数（以0或一个负数结束）建立链表：" );  
    scanf("%d", &n);  
    while(n>0){                         //输入若干正数建立链表，输入非正数时，建立过程结束  
        p=(Node*)malloc(sizeof(Node));  //新建结点  
        p->data=n;  
        p->next=h;                      //更改新增结点的指针域使其指向上一个新增结点  
        h=p;                            //将新增结点作为头结点  
        scanf("%d", &n);                //输入下一个数，准备建立下一个结点  
    }  
    return h;  
} 

       

        插入结点应用：

       

/*
功能：将一组无序数建成有序表
返回值：链表的头指针
参数1：链表的头指针
参数2：新读入的一个数
说明：建立有序表的过程就是不断将新增结点插入正确的位置
*/
Node *insertNode(Node *h,int b){
    Node *q1=h,*q2,*p;     //p指向新增结点
    p=(Node*)malloc(sizeof(Node));
    p->data=b;
    if(h==NULL){          //当前链表为空，p为首结点地址
        h=p;              //头指针指向p
        p->next=NULL;     //给p的指针域赋值
    }
    else if(p->data<h->data){ //插入结点是首结点
        h=p;              //头指针指向新的首结点
        p->next=q1;       //p的指针域存放原首结点的地址
    }
    else{
        /*两种情况：新增结点是最大的结点或新增结点在中间
        并找到新增结点最左边的结点*/
        while(q1!=NULL&&p->data>=q1->data){
            /*q1从首结点开始遍历直至链表末尾，p在头结点后，当p中的数据小于q1中的数据停止寻找*/
            q2=q1;        //q2为所找结点（目标结点的前一个结点）
            q1=q1->next;
        }
        /*将新结点p插到p2后*/
        p->next=q2->next; //p的指针域存放q2原来指针域的地址（即p1的地址）
        q2->next=p;       //q2新指针域存放p的地址
        /*注意：上述两条语句不能颠倒，小心上下语句出现左对角一样的情况 */
    }
     return h;
}

int main(){
    int b[]={67,25,78,99,87},i;
    Node *head=NULL;
    for(i=0;i<5;i++)
        head=insertNode(head,b[i]);
    traverse(head);
    return 0;
}

       

        删除结点应用：

       

/*
功能：从有序表中删除指定结点（只能删除第一次出现目标元素的结点）
返回值：链表的头指针
参数1：链表的头指针
参数2：指定要删除的元素
说明：找到元素所在的结点，更改其左结点的指针域并释放其空间
*/
Node *deleteNode(Node *h,int b){
    Node *p,*q;      //p作为遍历的指针寻找目标结点的地址，q是p的左结点
    p=h;
    if(h==NULL)
        printf("List is null,delete fail.\n");
    else{
        /*p从首结点开始遍历到尾结点结束,寻找删除结点*/
        while(b!=p->data&&p->next!=NULL){
            q=p;               //q也是所找结点，目标结点的前一个结点
            p=p->next;         //p为所找结点也是目标结点
        }
        if(b==p->data){
            /*当找到的元素就在首结点中，不经过循环体*/
            if(p==h)
                h=p->next;
            else
                q->next=p->next;
            free(p);
        }
        else
            printf("%d not found,delete fail.\n",b);
    }
    return h;
}

int main(){
    int b[]={67,25,78,99,87},i;
    Node *head=NULL;
    for(i=0;i<5;i++)
        head=insertNode(head,b[i]);
    traverse(head);
    head=deleteNode(head,78);
    traverse(head);
    head=deleteNode(head,43);
    traverse(head);
    return 0;
}

      

/*
功能：从有序表中删除指定结点（可删除出现目标元素的多个结点）
参数1：链表的头指针
参数2：指定要删除的元素
说明：q是遍历指针，用来寻找目标结点，p用来连接每一个非目标结点。
当q是目标结点时，p里的风向标指向下一个结点；当q是目标结点时，p跟着q走。
*/
Node* delete_node(Node *h,int x){  
    Node *p,*q;  
    if (h==NULL)  
        printf("空链表，不能删除\n");  
    else{  
        //判断头结点是否含目标元素，若有一直遍历头指针
        while(h!=NULL&&h->data==x){  //结果有两种：空链表或首结点不含目标元素
            p=h;  
            h=->next;                //遍历h,p跟在后面
            free(p);                 //把确定下来h前的内存空间统统释放
        }  
        if(h!=NULL){  
            p=h;                     //p从头结点开始，代表非目标结点
            q=p->next;               //q从p之后开始找目标
            while(q!=NULL){  
                if(q->data==x){      //q是目标结点  
                    p->next=q->next; //p的风向标指往q之后的结点
                    free(q);  
                }  
                else{      
                    p=q;             //q不是目标结点，p跟着移动
                }  
                q=p->next;           //q是p的下一个结点，q遍历每一个结点
            }  
        }  
    }  
    return h;  
}  

       

知识点总结：

顺序建立链表
核心：更改上一个新增结点的指针域使其指向新增结点

倒序建立链表
核心：更改新增结点的指针域使其指向上一个新增结点，并将新增结点作为头结点

有序插入结点：
首先判断待插结点的位置
该结点可作为头结点，则更改头指针及该结点的指针域
该结点在头结点后，则更改插入结点的指针域及其前一个结点的指针域，遍历得到前一个结点的地址

删除第一个出现的目标结点：
首先遍历结点，找到目标结点的位置（遍历得到目标结点及其左结点）
若目标结点是头结点，则更改头结点的地址
否则，更改其前一个结点的指针域使其指向要删结点的后一个结点，
最后释放删除结点内存

删除出现目标元素的多个结点：
首先遍历头指针，释放所有目标结点的内存空间，确定头结点不含目标元素

遍历头结点之后的所有结点，使所有结点的指针域均不存放目标结点的地址

心得：

       构建链表最重要的就是确定每一个结点的地址以及存放的下一个结点的地址，我的理解就是头指针和各个“风向标”。而函数中定义的指针变量p,q都只是变量，可以被不断重新赋值，但只要与head关联，都是明确的地址。因此，当所有风向标确定下来，一条链表就完成了，而只要给出头指针，该链表的所有信息也均可被访问。
       在创建或形成一条新的链表的时候，除了用一个指针表示指向新增结点或目标结点的指针外，同时还得定义另一个指针，用来形成链表。