第3讲+线性表及其链式存储.ppt

2)尾插法建单链表 算法描述 建一个空链表 反复执行 { 输入学号 如是结束信息则跳出 申请一个新结点 输入数据域予新结点 依尾插法插入链表 } 返回头指针 链表特点：生成的链表中结点的次序与输入的顺序相同 2)尾插法建单链表 在链表尾结点后插入一个结点的示意图如下： x p 插入核心语句(生成3条指针链）： 第1条：p-next=rear-next; 第2条：rear-next=p ； 第3条：rear=p; 1 2 ∧ a head rear ∧ 3 ∧ a head rear 2)尾插法建单链表 算法实现 LinkList CreateList_r( ) { LinkList head,p,rear; int n; head=InitList( ); rear=head; /*增加尾指针*/ while(1) { scanf(%d,n); if(n0) break; p=(LinkList)malloc(sizeof(LinkNode)); p-info.num=n; scanf(%s, p-info.name); scanf(%d, p-info.score); p-next=rear-next; rear-next=p; rear=p; /* 尾插结点*/ } return head; } 3、单链表的遍历 每个结点访问一次 在遍历过程中可以完成一系列操作 输出结点信息 查找合适位置插入结点 找指定值结点并删除 链表的统计计算 …… head ^ p p p p p p p=head-next; while(p!=NULL) {…… p=p-next; } ==NULL 例1：有一个带头结点的学生链表，统计不及格的学生数 形参：单链表头指针 返回值：不及格学生数 算法实现： int count(LinkList head) { int c=0; LinkList p; p=head-next; while (p) { if(p-info.score60) c++; p=p-next; } return c; } 数据类型： typedef struct{ int num; char name[20]; int score; }datatype; typedef struct node{ datatype info; struct node *next; }LinkNode, *LinkList; p!=NULL 例2：有一个带头结点的学生链表中，删除所有不及格的学生 形参：单链表头指针 返回值：无 算法实现： void DeleteNoPass(LinkList head) { LinkList q, p; q=head; p=head-next; while(p) { if(p-info.score=60) { q=p; p=p-next; } 70 head 30 ∧ 80 q p q p p 删除关键语句： (1) q-next=p-next; (2) free(p); (3)p=q-next; 1 2 3 释放 else /*删除p指向的结点*/ { q-next=p-next; free(p); p=q-next ; } }/*end while*/ } /*end function*/ 在链表中查找插入位置并插入结点的示意图如下： 65 p 插入核心语句(生成2条指针链）： 第1条： p-next=v; 1 2 30 head 70 ∧ 80 u v u v 查找插入位置语句 u=head,v=head-next; while(v!=NULL) { if(p-info.scorev-info.score ) { u=v; v=v-next; } else break; } 第2条： u-next=p ； 例3：在一个成绩升序的带头结点的学生链表中，插入一个学生后仍然有序 形参：单链表头指针 ,被插入结点数据域值 返回值：无 算法实现 void insertX(LinkList head, datatype x) { LinkList p,u,v; p=(LinkList