简单贴一下链表的建立等常用操作

链表定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

源代码

#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct Student)

//输入格式   1   89
//           2   99
//           0   0
struct Student {
    long num;
    float score;
    struct Student *next;
};
int n;
struct Student *creat();
struct Student *del(struct Student *head,long num);
struct Student *insert(struct Student *head,struct Student *stu);
void print(struct Student *head);
int main() {

    struct Student *head,*stu;
    long del_num;
    printf("请输入数据:\n");
    head=creat();
    print(head);
    printf("请输入要删除的数字:\n");
    scanf("%ld",&del_num);
    while(del_num!=0) {            //当输入的学号为0时结束循环
        head=del(head,del_num); //删除结点后返回链表的头地址
        print(head);            //输出全部结点
        printf("请输入要删除的数字:\n");
        scanf("%ld",&del_num);
    }
    printf("请输入要添加的数据:\n");
    stu=(struct Student *)malloc(LEN);  //开辟一个新结点
    scanf("%ld %f",&stu->num,&stu->score);
    while(stu->num!=0) {            //当输入的学号为0时结束循环
        head=insert(head,stu);    //返回链表的头地址，赋值给head
        print(head);            //输出全部结点
        printf("请输入要添加的数据:\n");
        stu=(struct Student *)malloc(LEN);  //开辟一个新结点
        scanf("%ld %f",&stu->num,&stu->score);
    }
    return 0;
}

struct Student *creat(void) { //返回一个指向链表头的指针
    struct Student *head;
    struct Student *p1,*p2;
    n=0;
    p1=p2=(struct Student *)malloc(LEN);//开辟一个新的结点使p1，p2指向它
    scanf("%ld %f",&p1->num,&p1->score);//输入第1个学生的学号和成绩
    head=NULL;
    while(p1->num!=0) {
        n=n+1;
        if(n==1) {    //如果这个结点是头结点，那么就把head指向p1
            head=p1;
        } else {
            p2->next=p1;  //如果不是，则使这个结点的next指向新开辟结点
        }
        p2=p1;            //使p2指向刚才建立的结点
        p1=(struct Student *)malloc(LEN);//生成新的结点 ，使p1指向它
        scanf("%ld %f",&p1->num,&p1->score);
    }
    p2->next=NULL;    //当p2是表尾时，把NULL赋值给next，结束链表建立
    return(head);
}

void print(struct Student *head) {
    struct Student *p;
    printf("\nNow,These %d records are:\n",n);
    p=head;
    if(head!=NULL) {
        do {
            printf("%ld %5.1f\n",p->num,p->score);
            p=p->next;
        } while(p!=NULL);
    }
}

struct Student *insert(struct Student *head,struct Student *stu) {
    struct Student *p0,*p1,*p2;
    p1=head;        //使p1指向头结点
    p0=stu;            //指向要插入的结点
    if(head==NULL) { //原来的链表是空表
        head=p0;
        p0->next=NULL;
    } else {
        while((p0->num>p1->num)&&(p1->next!=NULL)) {
            p2=p1;        //使p2指向刚才p1指向的结点
            p1=p1->next;//p1后移一个结点
        }
        if(p0->num<p1->num) {
            if(head==p1) {
                head=p0;    //插到原来第1个结点之前
            } else {
                p2->next=p0;//插到p2指向的结点之后
                p0->next=p1;
            }
        } else {
            p1->next=p0;
            p0->next=NULL;  //插到最后的结点之后
        }
    }
    n=n+1;
    return(head);        //结点数+1
}

struct Student *del(struct Student *head,long num) {
    struct Student *p1,*p2;
    if(head==NULL) {
        printf("这是一张空表\n");
        return(head);
    }
    p1=head;               //使p1指向第1个结点
    while(num!=p1->num&&p1->next!=NULL) { //p1指向的不是所要找的结点且后面还有结点
        p2=p1;
        p1=p1->next;       //p1向后移一个结点
    }
    if(num==p1->num) {      //找到了
        if(p1==head) {      //若p1指向的是首结点，把第2个结点地址赋予head
            head=p1->next;
        } else {             //否则将下一个结点地址赋给前一结点地址
            p2->next=p1->next;
        }
        printf("删除:%ld\n",num);
        n=n-1;
    } else {
        printf("%ld没有找到\n",num);//找不到该结点
    }
    return(head);

}