贺老师教学链接  C语言及程序设计进阶 本课讲解

回顾：动态分配和撤销内存

#include <stdio.h>
#include <malloc.h>
struct Student
{
    int num;
    float score;
    struct Student *next;
};


int main( )
{
    struct Student *p;
    p=malloc(sizeof(struct Student));
    p->num=31001;
    p->score=89.5;
    printf("%d  %.1f\n", p->num, p->score);
    free(p);
    return 0;
}

遍历链表

void traverse(Node *h)
{
    Node *p;
    p = h;  /*p指向头结点*/
    while(p!=NULL)  
    {
        printf("%-5d", p->data);  /*“访问”结点，此处用最简单的操作：读取输出*/
        p = p->next; /*p指向下一个结点，继续处理*/
    }
    printf("\n");
    return;
}

创建一个链表

#include <stdio.h>
#include <malloc.h>
typedef struct NODE
{
    int data;
    struct NODE *next;
} Node;
Node *createLinkList(int n);
void traverse(Node *h);


int main( )
{
    Node *head;
    head = createLinkList(5);
    traverse(head);
    return 0;
}


Node *createLinkList(int n)
{
    Node *h=NULL, *p, *last;  /*h指向头结点，p指向新增结点，last指向尾结点*/
    int d;   /*用于输入要插入的元素的值*/
    int i;
    for(i=0; i<n; i++)
    {
        scanf("%d", &d);
        p = (Node *)malloc(sizeof(Node));  /*p指向新增的结点*/
        p->data = d;    /*为数据域赋值*/
        p->next = NULL;   /*指针域为空*/
        if (h==NULL) /*如果h==NULL为真，说明p为第一个结点，由h指向该结点*/
            h = p;
        else  /*否则，原最后一个结点指向新增的结点，新结点加在链表尾*/
            last->next = p;
        last= p;   /*last保持指向最后一个结点的角色*/
    }
    return h;
};


void traverse(Node *h)
{
    Node *p;
    p = h;  /*p指向头结点*/
    while(p!=NULL)
    {
        printf("%-5d", p->data);  /*“访问”结点，此处用最简单的操作：读取输出*/
        p = p->next; /*p指向下一个结点，继续处理*/
    }
    printf("\n");
    return;
}

插入结点应用——建立有序链表

#include <stdio.h>
#include <malloc.h>
typedef struct NODE
{
    int data;
    struct NODE *next;
} Node;
Node *insertNode(Node *h, int b);
void traverse(Node *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;
}
Node *insertNode(Node *h, int b)
{
    Node *q1=h,*q2,*p;
    p=(Node*)malloc(sizeof(Node));  /*生成新结点*/
    p->data=b;
    if(h==NULL)   /*当前链表为空，p作为首结点*/
    {
        h=p;     /*头结点就是p，将p赋值给h*/
        p->next=NULL;  /*p的指针域赋值为空，表示尚无下一个结点*/
    }
    else if(p->data<h->data) /*要插入的元素值小于首结点元素，插入结点作为首结点*/
    {
        h=p;  /*将头结点h赋值为p*/
        p->next=q1; /*p的下一个结点是原先的首结点（见q1的初始化，其值为h）*/
    }
    else  /*在中间找到插入p的位置，将其插入*/
    {
        /*先找到合适的位置，q1的初值是h，即从头结点开始考察*/
        while((q1!=NULL&&p->data>=q1->data))
        {
            q2=q1;         /*q2记录q1的值*/
            q1=q1->next;   /*q1继续向后试探，直到a1*/
        }
        /*将新结点p插在q2后*/
        p->next=q2->next;  /*p的下一个结点为当前q2的下一结点，即p1*/
        q2->next=p;    /*q2的下一个结点y变为p，不再是q1*/
    }
    return h;
}


void traverse(Node *h)
{
    Node *p;
    p = h;  /*p指向头结点*/
    while(p!=NULL)
    {
        printf("%-5d", p->data);  /*“访问”结点，此处用最简单的操作：读取输出*/
        p = p->next; /*p指向下一个结点，继续处理*/
    }
    printf("\n");
    return;
}

删结点应用——在有序表中删除

#include <stdio.h>
#include <malloc.h>
typedef struct NODE
{
    int data;
    struct NODE *next;
} Node;
Node *insertNode(Node *h, int b);
Node *deleteNode(Node *h, int b);
void traverse(Node *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, 43);
    traverse(head);
    head=deleteNode(head, 78);
    traverse(head);
    return 0;
}
Node *insertNode(Node *h, int b)
{
    Node *q1=h,*q2,*p;
    p=(Node*)malloc(sizeof(Node));  /*生成新结点*/
    p->data=b;
    if(h==NULL)   /*当前链表为空，p作为首结点*/
    {
        h=p;     /*头结点就是p，将p赋值给h*/
        p->next=NULL;  /*p的指针域赋值为空，表示尚无下一个结点*/
    }
    else if(p->data<h->data) /*要插入的元素值小于首结点元素，插入结点作为首结点*/
    {
        h=p;  /*将头结点h赋值为p*/
        p->next=q1; /*p的下一个结点是原先的首结点（见q1的初始化，其值为h）*/
    }
    else  /*在中间找到插入p的位置，将其插入*/
    {
        /*先找到合适的位置，q1的初值是h，即从头结点开始考察*/
        while((q1!=NULL&&p->data>=q1->data))
        {
            q2=q1;         /*q2记录q1的值*/
            q1=q1->next;   /*q1继续向后试探，直到a1*/
        }
        /*将新结点p插在q2后*/
        p->next=q2->next;  /*p的下一个结点为当前q2的下一结点，即p1*/
        q2->next=p;    /*q2的下一个结点y变为p，不再是q1*/
    }
    return h;
}


Node *deleteNode(Node *h, int b)
{
    Node *p, *q;
    p=h;   /*p首先指向头结点*/
    if(h==NULL)  /*链表为空时不能删除*/
        printf("List is null, delete fail.\n");
    else
    {
        /*首先找到要删除的结点*/
        while(b!=p->data&&p->next!=NULL)
        {
            q=p;    /*q记录p的值*/
            p=p->next;   /*p接着指向下一个结点，q一直保持是p的上一个结点*/
        }
        if(b==p->data)   /*要删除的结点p在链表中存在*/
        {
            if(p==h) /*要删除的结点就是头结点时，令h指向p的下一个结点即可*/
                h = p->next;
            else   /*否则，删除q的下一个结点p*/
                q->next = p->next;
            free(p);  /*释放p结点*/
        }
        else
            printf("%d not found, delete fail.\n", b);
    }
    return h;
}


void traverse(Node *h)
{
    Node *p;
    p = h;  /*p指向头结点*/
    while(p!=NULL)
    {
        printf("%-5d", p->data);  /*“访问”结点，此处用最简单的操作：读取输出*/
        p = p->next; /*p指向下一个结点，继续处理*/
    }
    printf("\n");
    return;
}