C第8章简单链表及其应用.ppt

简单链表及其应用 链表 思考：如何描述一个班的学生基本信息（学号、姓名、年龄等）？ struct student{ int ID; char Name[20]; int age; }stu[30]; 链表 将若干个同类型的结构体类型数据按一定的原则连接起来。 链表的特点 couthead-ID; student *p=head; coutp-Name; p=p-next; coutp-age; 链表的特点 结点可不连续存储 操作灵活，便于扩充（动态分配空间） 链表的特点 链表的操作之建立无序链 链表为空(head==0) head=p1; p2=p1; 链表的操作之建立无序链 链表为空(head==0) head=p1; p2=p1; 链表不为空 p2-next=p1; p2=p1; p1用来指向新结点 p2用来指向链表当前尾结点 链表的操作之输出链表上各个结点的值 遍历链表结点（“看”一个输出一个） p=head; coutp-data; p=p-next; coutp-data;…… p=p-next; //p=NULL(遍历的终止条件) 链表的操作之删除某结点 先找到要删除结点 －－如果是头结点 p1=head; head=head-next; delete p1; 链表的操作之删除某结点 先找到要删除结点 －－以“找到”或“到尾找不到”为终止条件的遍历 p2=head; while(p2-data!=data3 p2-next!=NULL) p2=p2-next; 链表的操作之删除某结点 p1-next=p2-next; //p2指向要删除结点，p1指向要删除结点的前驱结点 delete p2; 先找到要删除结点（包括其前驱结点），再删除 链表的操作之删除整个链 遍历链表（“看”一个删一个） p1=head; head=head-next; //或head=p1-next; delete p1; 链表的操作之删除整个链 遍历链表（“看”一个删一个） while(head!=NULL){ p1=head; head=head-next; //或head=p1-next; delete p1; } 链表的操作之插入结点保持有序 p-next=head; head=p; 链表的操作之插入结点保持有序 p2-next=p; p-next=0; 链表的操作之插入结点保持有序 p-next=p2; p1-next=p; 先找到插入点！ 链表的操作之总结 链表的操作主要依靠指针和动态空间实现 头指针是链表的访问依据 改变部分链表的函数（插入、删除结点等）需要返回改变后的链表（通过头指针） 课堂练习 设计函数统计链表的结点个数 遍历链表，“看”一个，计数器累加一次 返回值为结点的个数，整型 int count(const node *head) { const node *p=head;int n=0; while(p!=NULL) {n++;p=p-next;} retrun n; } 课堂练习 将一无序链表按升序排序 冒泡排序 if(p-data p-next-data) {temp=p-data, p-data= p-next-data, p-next-data =temp｝ 课堂练习 将一无序链表按升序排序 冒泡排序 if(p-data p-next-data) {temp=p-data, p-data= p-next-data, p-next-data =temp｝ p=p-next; 课堂练习 将一无序链表按升序排序 冒泡排序 if(p-data p-next-data) {temp=p-data, p-data= p-next-data, p-next-data =temp｝ p=p-next; 课堂练习 将一无序链表按升序排序 冒泡排序 if(p-data p-next-data) {temp=p-data, p-data= p-next-data, p-next-data =temp｝ p=p-next; 课堂练习 void sort(node * head) { node *p=head; for(int i=0;icount(head)-1;i++){ for(int j=0;jcount(head)-i-1;j++) { if(p-data p-next-data) {temp=p-data;p-data= p-next-data; p-next-data =temp;} p=p-next; } p=head;} } * * 1001 张 18 1002 李 19 10