第2章线性表 2.3链表的实现《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第二章 线性表 2.3.2 链表的实现 1. 单链表的建立和输出 2. 单链表的修改 3. 单链表的插入 4. 单链表的删除 5. 应用举例 6. 其它链表形式 1. 单链表的建立和输出 实例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z）,请写出C语言程序。 难点分析：每个数据元素在内存中是“零散”存放的，其首地址怎么找？又怎么一一链接？ 实现思路：先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将地址送给前面的指针。 将全局变量及函数提前说明： #include<stdio.h> #include<stdlib.h> typedef struct node { char data; //数据域 struct node *next; //指针域 }linklist; linklist *head, *p, *q; //一般需要3个指针变量 int m ; // 数据元素的个数 int m=sizeof(linklist); /* 结构类型定义好之后，每个变量的长度就固定了，m求一次即可 */ void build() { //字母链表的生成。要一个一个链入 int i; head=(linklist *)malloc(m); //前面已求出m值 p=head; for(i=1;i<26;i++) //因尾结点要特殊处理，故i≠26 { p->data=i+‘a’-1; // 第一个结点值为字符a p->next=(linklist *)malloc(m); //为后继结点开新空间！ p=p->next； //让指针变量P改为指向后继结点 } p->data=‘z’; //最后一个元素要单独处理 p->next=NULL ;} //不要忘记单链表尾结点的指针域要置空！ void display() { /*字母链表的输出*/ p=head->NEXT; while (p!=NULL) /* 只要没到最后一个元素，就不停地“顺藤摸瓜”输出*/ { printf("%c", p->data); p=p->next; } } 讨论：要统计链表中数据元素的个数，该如何改写？ sum ++; 2. 单链表的读取(或修改） 启发：要修改第i个数据元素，关键是要先找到该结点的指针p，然后用p->data=new_value 即可。 思考：如何实现按值查找？ 难点：单链表中想取得第i个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取 。 datatype Get(linklist *L, int i) { p=L->next; j=1; while( j<i ){p=p->next; ++j;} if(!p||j>i)return NULL; e=p->data; return e; } p&&j<i 3. 单链表的插入——后插法 在链表中(*p)结点后插入一个元素的示意图如下： x s b a p a b p 插入步骤（即核心语句）： Step 1：s->next=p->next; Step 2：p->next=s ； p->next s->next 元素x结点应预先生成： S=(linklist*)malloc(m); S->data=x; void INSERTAFTER( linklist * p, datatype x) { linklist *s; s=(LinkList *)malloc(sizeof(linklist)); s->data=x; s->next=p->next; p->next=s; } 单链表结点插入的演示 3. 单链表的插入——前插法 即：在链表中(*p)结点前面插入一个元素。 思考： 1、如何实现？（p25:INSERTBEFORE()函数） 必须找到(*p)结点的直接前趋结点(*q)，并借助此结点完成插入操作。 2、如何改进？ （p25:INSERTBEFORE1()函数） 先实现后插操作，再交换结点的关键字值。 4. 单链表的删除 －－－在链表中删除(*p)结点的直接后继结点 c a b p 删除步骤（即核心语句）： q = p->next; //保存b的指针，后面释放时有