chap11-指针进阶.ppt

11.3 用链表构建学生信息库 11.3.1 程序解析 11.3.2 链表的概念 11.3.3 单向链表的常用操作 11.3.1 程序解析 例11-10 建立一个学生成绩信息（包括学号、姓名、成绩）的单向链表，学生记录按学号由小到大顺序排列，要求实现对成绩信息的插入、修改、删除和遍历操作。 main Create_Stu_Doc InsertDoc DeleteDoc Print_Stu_Doc InsertDoc 11.3.1 程序解析 struct stud_node{ /*链表结点类型*/ int num; char name[20]; int score; struct stud_node *next; }; struct stud_node * Create_Stu_Doc(); /* 新建链表 */ struct stud_node * InsertDoc(struct stud_node * head, struct stud_node *stud); /* 插入 */ struct stud_node * DeleteDoc(struct stud_node * head, int num); /* 删除 */ void Print_Stu_Doc(struct stud_node * head); /* 遍历 */ 11.3.2 链表的概念 链表是一种常见而重要的动态存储分布的数据结构。它由若干个同一结构类型的“结点”依次串接而成。链表分单向链表和双向链表。 头指针 结点 尾结点 头结点 11.3.2 链表的概念 通常使用结构来定义单向链表结点的数据类型： struct stud_node{ int num; char name[20]; int score; struct stud_node *next; }; 结构的递归定义 11.3.2 链表的概念 与数组比较 在用数组存放数据时，一般需要事先定义好固定长度的数组，在数组元素个数不确定时，可能会发生浪费内存空间的情况。 链表是动态存储分布的数据结构。根据需要动态地开辟内存空间，可以比较自由方便地插入新元素（结点），故使用链表可以节省内存，操作效率高。 11.3.2 链表的概念 动态分配相关函数 void *malloc(unsigned size) 功能：在内存的动态存贮区中分配一块长度为size的连续空间。 返回值：指针，存放被分配内存的起始地址。若未申请到空间，则返回 NULL( 0 )。 例如：(int *) malloc(sizeof(int)) (struct student *) malloc(sizeof(struct student)) void free(void *ptr) 功能：释放由malloc()申请的动态内存空间，ptr存放该空间的首地址。 返回值：无。 例如：free(p); 11.3.3 单向链表的常用操作 1. 链表的建立 2. 链表的遍历 3. 插入结点 4. 删除结点 11.3.3 单向链表的常用操作 1. 链表的建立 11.3.3 单向链表的常用操作 1. 链表的建立 head = tail = NULL; scanf(%d%s%d, num,name, score); while(num != 0){ p = (struct stud_node *) malloc(size); p-num = num; strcpy(p-name, name); p-score = score; p-next = NULL; if(head == NULL) head = p; else tail-next = p; tail = p; scanf(%d%s%d, num, name, score); } 头部插入法： p-next=head; head=p; 尾部插入 11.3.3 单向链表的常用操作 2. 链表的遍历 for(ptr = head; ptr!=NULL; ptr = ptr-next) printf(%d\