1、空间连续、元素类型相同、通过下标快速访问
2、静态数组：空间一旦确定不能更改（动态数组除外）
3、静态、动态数组 插入删除元素 需要移动大量数据
链表是一种物理存储上非连续，数据元素的逻辑连续通过链表节点中的指针变量保存下个节点的地址，实现的一种线性存储结构。
链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成（malloc，calloc），每个节点包 括两个部分：
数据域：存放节点数据（核心）
指针域：结构体指针变量 保存下一个节点的地址
#include <stdio.h>
//设计节点类型
typedef struct stu
{
//数据域
int num;
char name[32];
float score;
//指针域
struct stu *next;
}STU;
int main(int argc, char const *argv[])
{
//静态链表的节点 不是从堆区申请
STU node1={100, "lucy", 77.7f};
STU node2={101, "bob", 66.7f};
STU node3={102, "tom", 55.7f};
STU node4={103, "hehe", 74.7f};
STU node5={104, "xixi", 73.7f};
//构建成链表
STU *head = NULL;
head = &node1;
node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = &node5;
node5.next = NULL;
//遍历链表(从头节点 逐个节点遍历)
STU *pb = head;
while(pb != NULL)
{
printf("%d %s %f\n", pb->num, pb->name, pb->score);
//移动到下一个节点
pb = pb->next;
}
return 0;
}
增、删、改、查
学生管理系统 讲解链表
帮助信息函数：
void help(void)
{
printf("******************************\n");
printf("* insert:插入链表节点 *\n");
printf("* printf:遍历链表节点 *\n");
printf("* search:查询链表节点 *\n");
printf("* delete:删除链表节点 *\n");
printf("* free:释放链表节点 *\n");
printf("* quit:遍历链表节点 *\n");
printf("******************************\n");
return;
}
STU* insert_link(STU *head, STU tmp)
{
//为插入的节点申请空间
STU *pi = (STU *)calloc(1,sizeof(STU));
//给空间赋值
*pi = tmp;
pi->next = NULL;
//判断链表是否存在
if(NULL == head)//空
{
head = pi;
//return head;
}
else//非空
{
pi->next = head;
head = pi;
//return head;
}
return head;
}
//尾部插入节点
STU* insert_link(STU *head, STU tmp)
{
//为插入的节点申请空间
STU *pi = (STU *)calloc(1,sizeof(STU));
//给空间赋值
*pi = tmp;
pi->next = NULL;
//判断链表是否存在
if(NULL == head)
{
head = pi;
return head;
}
else
{
//寻找尾部节点
STU *pb = head;
while(pb->next != NULL)
pb = pb->next;
//将pi插入到 尾节点后
pb->next = pi;
return head;
}
return head;
}
//有序插入节点
STU* insert_link(STU *head, STU tmp)
{
//为插入的节点申请空间
STU *pi = (STU *)calloc(1,sizeof(STU));
//给空间赋值
*pi = tmp;
pi->next = NULL;
//判断链表是否存在
if(NULL == head)
{
head = pi;
return head;
}
else
{
//寻找插入点
STU *pf = NULL, *pb = NULL;
pf = pb = head;
//从小--->大排序
while((pb->num < pi->num) && (pb->next != NULL))
{
pf = pb;
pb = pb->next;
}
if(pb->num >= pi->num)//头部插入、中部插入
{
if(pb == head)//头部插入
{
pi->next = head;
head = pi;
}
else//中部插入
{
pf->next = pi;
pi->next = pb;
}
}
else if(pb->next == NULL)//尾部插入
{
pb->next = pi;
}
}
return head;
}void printf_link(STU *head)
{
//1、判断链表是否存在
if(NULL == head)
{
printf("链表不存在\n");
return;
}
else//2、链表存在，逐个节点遍历链表
{
STU *pb = head;
while(pb != NULL)
{
printf("%d %s %f\n", pb->num, pb->name, pb->score);
//pb指向下一个节点
pb = pb->next;
}
}
return;
}
STU *search_link(STU *head, char *name)
{
//判断链表是否存在
if(NULL == head)
{
printf("链表不存在\n");
return NULL;
}
else//链表存在
{
//逐个节点查询
STU *pb = head;
while((strcmp(pb->name, name) != 0) && (pb->next != NULL))
{
pb = pb->next;
}
if(strcmp(pb->name, name) == 0)//找到
return pb;
else
{
printf("未找到相关节点信息\n");
return NULL;
}
}
return NULL;
}
STU* delete_link(STU *head, char *name)
{
//判断链表是否存在
if(NULL == head)
{
printf("链表不存在\n");
return head;
}
else
{
STU *pf =NULL, *pb=NULL;
pf = pb = head;
//寻找删除点
while((strcmp(pb->name, name) != 0) && (pb->next != NULL))
{
pf = pb;
pb = pb->next;
}
//找到删除点
if(strcmp(pb->name, name) == 0)
{
if(head == pb)//头部删除
{
head= head->next;
}
else//中尾部删除
{
pf->next = pb->next;
}
//释放pb
if(pb != NULL)
{
free(pb);
pb=NULL;
}
}
else//未找到删除点
{
printf("未找到删除的相关节点信息\n");
}
}
return head;
}STU* free_link(STU *head)
{
//判断链表是否存在
if(NULL == head)
{
printf("链表不存在\n");
return head;
}
else//链表存在
{
STU *pb = head;
while(pb != NULL)
{
//head纪录下一个节点的位置
head = head->next;
//释放pb指向的节点
if(pb != NULL)
{
free(pb);
pb = NULL;
}
//pb指向下一个节点
pb=head;
}
printf("链表节点已经完全释放\n");
}
return head;
}
STU* reverse_link(STU *head)
{
//判断链表是否存在
if(NULL == head)
{
printf("链表不存在\n");
return head;
}
else
{
STU *pb = head->next;
STU *pn = NULL;
//将头结点指针域指向NULL
head->next = NULL;
//逐个节点翻转
while(pb != NULL)
{
//pn纪录pb->next的节点
pn = pb->next;
//进行反向连接
pb->next = head;
//移动head到pb上
head = pb;
//pb指向pb的节点
pb = pn;
}
}
return head;
}
//选择法对链表排序
void sort_link(STU *head)
{
//判断链表是否存在
if(NULL == head)
{
printf("链表不存在\n");
return;
}
else
{
STU *p_i = head, *p_j = head;//int i=0, j=0;
while(p_i->next != NULL)//for(i=0;i<n-1; i++)
{
STU *p_min = p_i;//int min = i;
p_j = p_min->next;//j=min+1
while(p_j != NULL)//j<n
{
if(p_min->num > p_j->num)//if(arr[min] > arr[j])
p_min = p_j;//min = j;
p_j = p_j->next;//j++
}
if(p_i != p_min)//if(i != min)
{
//整体交换
STU tmp = *p_i;
*p_i = *p_min;
*p_min = tmp;
//指针域交换
tmp.next = p_i->next;
p_i->next = p_min->next;
p_min->next = tmp.next;
}
p_i = p_i->next;//i++
}
}
return;
}
