《数据结构》课程PPT教学课件（2012）第2章 线性表 2.3 线性表的链式表示和实现 2.3.2 链表的实现

教材问题讨论： 教材P28对于线性表的单链表 请注意：Typedef不可能创造 存储结构描述： 任何新的数据类型，而仅仅是 Typedef struct Lnode 在原有的数据类型中命名一个 ElemType data; 新名字，其目的是使你的程序 struct Lnode *next; 更易阅读和移植。 Lnode,*LinkList; Q1:第一行的Lnode与最后一行的Lnode是不是一回事？ A1:不是。前者Lnode是结构名，后者Lnode是对整个 struct类型的一种“缩写”，是一种“新定义名”，它只是 对现有类型名的补充，而不是取代

1 Typedef struct Lnode { ElemType data; struct Lnode *next; }Lnode, *LinkList; 教材P28对于线性表的单链表 存储结构描述: 教材问题讨论： Q1：第一行的Lnode 与最后一行的Lnode是不是一回事？ A1：不是。前者Lnode是结构名，后者Lnode是对整个 struct类型的一种“缩写”，是一种“新定义名”，它只是 对现有类型名的补充，而不是取代。 请注意：Typedef不可能创造 任何新的数据类型，而仅仅是 在原有的数据类型中命名一个 新名字，其目的是使你的程序 更易阅读和移植

Typedef struct student char name; int age; }student,*pointer; Q2: 那为何两处要同名(Lnode和node)?太不严谨了吧？ A2:同名是为了表述起来方便。例如，若结构名为student, 其新定义名缩写也最好写成student,因为描述的对象相同， 方便阅读和理解。 Q3:结构体中间的那个struct Lnode是何意？ A3:在“缩写”Lnodei还没出现之前，只能用原始的 struct Lnode来进行变量说明。此处说明了指针分量的数据 类型是struct Lnode

2 Typedef struct Lnode { ElemType data; struct Lnode *next; }Lnode, *LinkList; Q2： 那为何两处要同名(Lnode和Lnode）？太不严谨了吧？ A2：同名是为了表述起来方便。例如，若结构名为student， 其新定义名缩写也最好写成student，因为描述的对象相同， 方便阅读和理解。 Q3：结构体中间的那个struct Lnode是何意？ A3：在“缩写” Lnode还没出现之前，只能用原始的 struct Lnode来进行变量说明。此处说明了指针分量的数据 类型是struct Lnode。 Typedef struct student { char name; int age; }student,*pointer;

第2章线性表 2.1 线性表的逻辑结构 2.2线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.4应用举例 3

3 第2章 线性表 2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例

2.3线性表的链式表示和实现 2.3.1链表的表示 2.3.2 链表的实现 2.3.3链表的运算效率分析

4 2.3 线性表的链式表示和实现 2.3.1 链表的表示 2.3.2 链表的实现 2.3.3 链表的运算效率分析

2.3,2链表的实现 (1)单链表的建立和输出 (2)单链表的修改 (3)单链表的插入 （4)单链表的删除 5

5 2.3.2 链表的实现 （1） 单链表的建立和输出 （2） 单链表的修改 （3） 单链表的插入 （4） 单链表的删除

(1)单链表的建立和输出 例：用单链表结构来存放26个英文字母组成的线 性表(a,b, c,.,Z),请写出C语言程序。 实现思路：先开辟头指针，然后陆续为每个结点开辟存储 空间并及时赋值，后继结点的地址要提前送给前面的指针。 先挖“坑”，后种“碧 6

6 （1） 单链表的建立和输出 例：用单链表结构来存放26个英文字母组成的线 性表（a，b，c，.，z）,请写出C语言程序。 实现思路：先开辟头指针，然后陆续为每个结点开辟存储 空间并及时赋值，后继结点的地址要提前送给前面的指针。 先挖“坑” ,后种“萝 卜”！

将全局变量及函数提前说明： #include #include typedef struct node char data; struct node *next; }node; node *p,*q,*head; /一般需要3个指针变量 intn; /数据元素的个数 intm=sizeof(node);/结构类型定义好之后，每个node类型的 长度就固定了，求一次即可*/

7 #include #include typedef struct node{ char data; struct node *next; }node; 将全局变量及函数提前说明： node *p,*q,*head; //一般需要3个指针变量 int n ; // 数据元素的个数 int m=sizeof(node); /*结构类型定义好之后，每个node类型的 长度就固定了，m求一次即可*/

void build( /字母链表的生成。要一个个慢慢链入 int i; head=(node*)malloc(m); /m=sizeof(node)前面a求出 p=head; for(i=1;idata=it‘a'-l; /第个结点值为字符a p>next-(node*)malloc(m);/为后继结点"挖坑”！ p=p->next; /让指针变量P指向后一个结点 p->data=it‘a’-l; 最后一个元素要单独处理 p->next=NULL ; /单链表尾结点的指针域要置空！ 新手特别容易忘记！！ 8

8 新手特别容易忘记！！ { int i; head=(node*)malloc(m); //m=sizeof(node) 前面已求出 p=head; for( i=1; idata=i+‘a’-1; // 第一个结点值为字符a p->next=(node*)malloc(m); //为后继结点“挖坑”！ p=p->next；} //让指针变量P指向后一个结点 p->data=i+‘a’-1; //最后一个元素要单独处理 p->next=NULL ;} //单链表尾结点的指针域要置空！ void build( ) //字母链表的生成。要一个个慢慢链入

void display() /*字母链表的输出*/ {p=head; sum=0; while (p) /当指针不空时循环（仅限于无头结点的情况） {printf("%c",p->data); p=p->next; /让指针不断“顺藤摸瓜” sum++; 讨论：要统计链表中数据元素的个数，该如何改写？ 9

9 {p=head; while (p) //当指针不空时循环（仅限于无头结点的情况） {printf("%c",p->data); p=p->next; //让指针不断“顺藤摸瓜” } } 讨论：要统计链表中数据元素的个数，该如何改写？ sum++; sum=0; void display() /*字母链表的输出*/

（2)单链表的修改（或读取） Status含 思路：要修改第个数据元素，必须从头指针起一直州 义见P10 的指针p,然后才能执行p->data=now de. 修改第个数据云素床作函数可写为 Status GetElem L(LinkList L,int i,ElemType &e) {p-L->next;-1;/带头结点的链表 while(p&&jnext;++j;} if(!p j>i)return ERROR; p->data=e;/若是读取则为：e=p->data; return OK;//GetElem L 缺点：想寻找单链表中第个元素，只能从头指针开始逐一查 询（顺藤摸瓜），无法随机存取。 10

10 （2） 单链表的修改(或读取） 思路：要修改第i个数据元素，必须从头指针起一直找到该结点 的指针p，然后才能执行p->data=new_value 。 修改第i个数据元素的操作函数可写为： Status GetElem_L(LinkList L, int i, ElemType &e) {p=L->next; j=1; //带头结点的链表 while(p&&jnext; ++j;} if( !p || j>i ) return ERROR; p->data =e; //若是读取则为：e=p->data; return OK;}// GetElem_L 缺点：想寻找单链表中第i个元素，只能从头指针开始逐一查 询（顺藤摸瓜），无法随机存取 。 Status含 义见P10