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

简单链表及其应用,链表,思考：如何描述一个班的学生基本信息（学号、姓名、年龄等）？ struct student int ID; char Name20; int age; stu30;,分配固定长度连续空间，操作没有灵活性 如何添加新转入学生信息？,链表,将若干个同类型的结构体类型数据按一定的原则连接起来。,struct student int ID; char Name20; int age; student *next; ;,链表的特点,coutID; student *p=head; coutName; p=p-next; coutage;,链表的特点,结点可不连续存储 操作灵活，便于扩充（动态分配空间）,NULL,链表的特点,链表的操作之建立无序链,链表为空(head=0) head=p1; p2=p1;,head,data1,链表的操作之建立无序链,链表为空(head=0) head=p1; p2=p1; 链表不为空 p2-next=p1; p2=p1; p1用来指向新结点 p2用来指向链表当前尾结点,head,data1,链表的操作之输出链表上各个结点的值,遍历链表结点（“看”一个输出一个） p=head; coutdata; p=p-next; coutdata; p=p-next; /p=NULL(遍历的终止条件),链表的操作之删除某结点,先找到要删除结点 如果是头结点 p1=head; head=head-next; delete p1;,head,data4,链表的操作之删除某结点,先找到要删除结点 以“找到”或“到尾找不到”为终止条件的遍历 p2=head; while(p2-data!=data3 ,head,data4,链表的操作之删除某结点,p1-next=p2-next; /p2指向要删除结点，p1指向要删除结点的前驱结点 delete p2; 先找到要删除结点（包括其前驱结点），再删除,head,data4,链表的操作之删除整个链,遍历链表（“看”一个删一个） p1=head; head=head-next; /或head=p1-next; delete p1;,head,data4,链表的操作之删除整个链,遍历链表（“看”一个删一个） while(head!=NULL) p1=head; head=head-next; /或head=p1-next; delete p1; ,head,链表的操作之插入结点保持有序,p-next=head; head=p;,head,5,链表的操作之插入结点保持有序,p2-next=p; p-next=0;,head,5,链表的操作之插入结点保持有序,p-next=p2; p1-next=p; 先找到插入点！,head,5,链表的操作之总结,链表的操作主要依靠指针和动态空间实现 头指针是链表的访问依据 改变部分链表的函数（插入、删除结点等）需要返回改变后的链表（通过头指针）,课堂练习,设计函数统计链表的结点个数 遍历链表，“看”一个，计数器累加一次 返回值为结点的个数，整型 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(i