第2章_线性表B.ppt

数据结构课程的内容 第2章 线性表 2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例 上堂课要点回顾 2.3 线性表的链式表示和实现 2.3.1 链表的表示 链式存储特点 与链式存储有关的术语 补充：结构数据类型及其C语言表示法 2. 与链式存储有关的术语 何谓头指针、头结点和首元结点？ 例： 讨论3. 头结点的数据域内装的是什么？ 3. 补充结构数据类型及其C语言表示法 ① 类型定义和变量说明可以合写为： typedef struct liuyu { //liuyu是自定义结构类型名称 char data; //定义数据域的变量名及其类型 struct liuyu *next; //定义指针域的变量名及其类型 }test，*head; /*test是liuyu结构类型的变量, *head是liuyu结构类型的头指针*/ 补充：结构类型的C语言表示法 至此应可看懂教材P28对于单链表的抽象描述，和教材P22关于顺序表的抽象定义。 附2：教材P22关于顺序表的抽象定义： 补充：结构类型的C语言表示法 ④ 介绍三个有用的库函数（都在stdlib.h 中）： sizeof(x)——计算变量x的长度； malloc(m) —开辟m字节长度的地址空间，并返回这段空间的首地址； free(p) ——释放指针p所指变量的存储空间，即彻底删除一个变量。 2.3.2 链表的实现 1. 单链表的建立和输出 2. 单链表的修改 3. 单链表的插入 4. 单链表的删除 5. 应用举例 6. 其它链表形式 1. 单链表的建立和输出 实例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z）,请写出C语言程序。 将全局变量及函数提前说明： #includestdio.h #includestdlib.h typedef struct liu{char data; struct liu*next;}test; liu *p,*q,*head; //一般需要3个指针变量 int n ; // 数据元素的个数 int m=sizeof(test); /*结构类型定义好之后，每个变量的长度就固定了，m求一次即可*/ void build() //字母链表的生成。要一个一个慢慢链入 { int i; head=(test*)malloc(m); //m=sizeof(test) 前面已求出 p=head; for(i=1;i26;i++) //因尾结点要特殊处理，故i≠26 { p-data=i+‘a’-1; // 第一个结点值为字符a p-next=(test*)malloc(m); //为后继结点开新空间！ p=p-next；} //让指针变量P改为指向后继结点 p-data=i+‘a’-1; //最后一个元素要单独处理 p-next=NULL ;} //单链表尾结点的指针域要置空！ void display() /*字母链表的输出*/ {p=head; while (p-next!=NULL) /* 只要没到最后一个元素，就不停地“顺藤摸瓜”输出*/ {printf(%c,p-data); p=p-next; } printf(“%c\n”,p-data); //别忘记输出尾结点数据 } 2. 单链表的修改(或读取） 思路：要修改第i个数据元素，关键是要先找到该结点的指针p，然后用p-data=new_value 即可。 3. 单链表的插入 4. 单链表的删除 5.应用举例：两个链表的归并（教材P31） 用链表可表示为： 算法分析： 思考： 6. 其它链表形式 讨论2： 链表能不能首尾相连？怎样实现？ 讨论3： 单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？ 答：能。只要定义一个结构类型（含数据域和指示域）数组，就可以完全描述链表，这种链表称为静态链表。 注：数据域含义与前面相同，指示域相当于前面的指针域。 讨论1： 用一维数组也能存放链表吗？怎样实现？ 静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。 具体实现过程见教材P31-34。 答：能。只要将表中最后一个结点的指针域指向头结点即可 (P-next=head;) 。这种形成环路的链表称为循环链表。 特别