C语言：链表
链表是一种常见的基础数据结构，它由一系列节点（Node）组成。每个节点包含两部分：数据域（存储数据）和指针域（存储下一个节点的地址）。链表的特点是元素在内存中不一定连续存储，而是通过指针连接起来。
以下是链表的一些基本特点：
- 动态性：链表的长度可以动态变化，不需要在创建时指定大小。
- 灵活性：链表可以方便地插入和删除元素，不需要像数组那样进行大量元素的移动。
- 多样性：链表有多种形式，如单向链表、双向链表、循环链表等。
以下是链表的主要类型：
- 单向链表：每个节点只有一个指针，指向下一个节点。
- 双向链表：每个节点有两个指针，一个指向前一个节点，另一个指向下一个节点。
- 循环链表：链表中最后一个节点的指针指向第一个节点，形成一个环。
1. 链表操作简介
在操作链表之前，要先来设计链表中每个结点的数据结构。我们设计一个学生的结构体变量，用来存放学生的学号和分数。
struct ST{int n;int score;struct ST *next;
};在 C 语言中，指针必须指定它所指向的数据类型。由于
next需要指向链表中的下一个struct ST类型的节点，因此它的类型必须是struct ST *。另外，为了处理方便，通常都是在线性单向链表的第一个结点之前额外增加一个结点，称之为“头结点”。
2. 空链表的建立
这里所说的空链表，是指只含有一个头结点的链表。
struct ST *createNullList()
{struct ST* head;head=(struct ST*)malloc(sizeof(struct ST));if(head!=NULL)head->next=NULL;elseprintf("Out of space!\n");return head;
}动态内存分配有可能失败，因此需要检查head中 所存的值是否为NULL。若为NULL，表示空间分配失败，若不为NULL，则表示头结点已经成功分配。由于空链表没有实际结点，因此头结点的指针域应该存为NULL。
3. 判断链表是否为空
int isNullList(struct ST* head) //传进去头指针
{return head->next==Null; //判断语句
}4. 在链表最后添加一个结点
int append(struct ST* head, int n, int s)
{struct ST* p,*pnew;pnew = (struct ST*)malloc(sizeof(struct ST));if(pnew==NULL){printf("Out of space!");return 0;}else{pnew->n=n;pnew->sorce=s;p=head; //p先指向头结点while(p->next!=NULL) //若p所指不是链尾p=p->next; //p后移一个结点p->next=pnew; //链尾的next存储新结点指针pnew->next=NULL; //使新结点成为链尾}return 1;
}5. 求某结点的指针
例如，要查找链表中学号为n的结点的指针。
查找要从链表的第一个结点开始，依次将每个结点的学号与n比较，若找到该同学，返回其地址，若找不到，则返回NULL。
struct ST* locate(struct ST* head, int n)
{struct ST* p;p=head->next; //将头结点的next域赋值给P,使指向第一个结点while(p!=NULL&&p->n!=n) //如果p存的不是NULL(表示P指向一个实际存在的结点)p=p->next;return p;
}6. 求p所指结点的前驱（前一个结点）
struct ST* locatePre(struct ST* head, struct ST* p)
{struct ST* ptemp;ptem=head;while(ptemp!=NULL&&ptemp->next!=p)ptemp=ptemp->next;return ptemp;
}判断ptemp是不是等于NULL以及ptemp->next是不是等于p；
若两者都不是，则执行ptemp=ptemp->next，重复上一个步骤；
若ptemp等于NULL，表示已经找遍所有结点但没有找到p所指的结点，退出循环，返回NULL。若ptemp->next=p，则ptemp所指结点就是p所指结点的前驱，退出循环，返回ptemp。
7. 在某结点之后插入一个新结点
int insert(struct ST* head, struct ST* p, int n, float score)
{struct ST* pnew=(struct ST*)malloc(sizeof(struct ST));if(pnew==NULL){printf("Out of space!\n");return 0;}pnew->num=n;pnew->score=score;pnew->next=p->next;p->next=pnew;return 1;
}8. 结点的删除
int delete(struct ST* head, int n)
{struct ST *p1,*p2;p1=head;//下面用循环来查找学号为n的结点的前驱while(p1->next!=NULL&&p1->next!=n)p1=p1->next;if(p1->next==NULL){printf("Not exist!\n");return 0;}p2=p1->next;p1->next=p2->next;free(p2);return 1;
}