主要内容,普通高等教育“十一五”国家级规划教材,第3章 链接表,3.1 链表 3.2 链栈 3.3 链队列,返回目录,,,,,3.4 字符串的链式存储 3.5 链表应用举例,,,3.1链表,3.1.1 单链表 3.1.2 循环链表 作业,,,,3.1.1 单链表,typedef struct node { datatype data; struct node *next; }lnode ,*linklist ;,1. 单链表的定义和存储结构,定义：一个链表由n个结点组成,每个结点中有一个存储数据的值域和一个存储另一个结点地址的指针域通常用头指针head来标识一个单链表的开始头结点:表的第一个结点的data域不存数据 空表:head-next=NULL（也可用∧表示空NULL） 存储空间动态分配:p=malloc(sizeof(linklist)) 释放 p 所指的结点:free(p),,,单链表的链式存储结构示意图,2. 单链表的基本操作 (1)建立单链表 方法一：从表头到表尾顺序建立 方法二：从表尾到表头逆向建立void creat(lnode *head, list la) { lnode *p; int i; head=malloc(sizeof(lnode)); head-next=NULL; for(i=la.last;i=1;i--) { p=malloc(sizeof(lnode)); p-data=la.data[i]; p-next=head-next;head-next=p; } },性表la中存放数据（5,4,8,6）,时间复杂度为O(n),⑵ 插入运算 方法一:在指定位置进行插入。
方法二:根据所给条件找到位置再进行插入 void insert(linklist head,int i,datatype x) { linklist p,s;int j=1; p=head; while(p } },,head,,,,… …,,时间复杂度为O(n),void insert(linklist head,int i,datatype x) { linklist p,s;int j=1; p=head; while(p } },单链表中插入元素示意图,p,(3)按值查找,算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于x，若是，返回该结点的地址，否则继续向后查找，直到链表结束为止找不到时返回空时间复杂度为O(n)lnode *locate( linklist head, datatype x) { lnode *p=head-next; while( p!=NULL },⑷ 删除运算 方法一:在指定位置进行删除 方法二:根据所给条件找到位置再进行删除 void del(linklist head,int i) { linklist p,q;int j=1; p=head; while(p } },算法演示,时间复杂性为O(n) 。
void del(linklist head,int i) { linklist p,q;int j=1; p=head; while(p } },3.1.2 循环链表,1. 循环单链表：对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头结点地址存于该指针域，则使得链表头尾结点相连，就构成了循环单链表空表,非空表,2. 循环双向链表,结点,空表,非空表,循环双向链表：将最后一个结点的空指针域（next域）用来保存头结点地址，而用头结点的prior域保存最后一个结点的地址，用这种结点组成的链表称为循环双向链表3. 静态链表,对于某些高级语言若没有指针类型，就不能动态生成结点，此时也可以借助一维数组来描述线性链表define MAX 链表的最大长度 typedef struct { datatype data; int next; }snode; /*结点类型*/ snode sl[MAX];,该数组的定义如下：,静态链表,数组sl就表示一种链表，该链表的结点中也有数据域data和指针域next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址(数组的下标)，称之为静态指针，这种链表就称之为静态链表，空指针用0表示，而sl.next[0]中存放的是第一个结点的起始地址。
静态链表如图所示,作业,1.简述链表的定义和链表的分类 2.做教材习题中的以下题目 单项选择题：(1),(2),(3),(8),(9),(10) 填空题：(1),(2) ,(3),(5),(6),(7),(9),(10) 应用题：(1),3.2 链栈,1.链栈的定义 链栈：用链式存储结构实现的栈只允许在表头进行插入和删除运算的单链表) 栈顶指针:单链表的头指针链栈的类型定义如下： typedef struct node { datatype data; struct node *next; }*linkstack ; linkstack hs; /*hs为链栈栈顶指针*/,2. 链栈的运算 ⑴ 进栈,进栈的算法: void push(linkstack hs, datatype x) { linkstack s; s=malloc(sizeof(linkstack)); s-data=x; s-next=hs; hs=s; },,hs,,,s,,,x,an+1,hs,⑵ 出栈,void pop(linkstack hs, datatype *x) {linkstack p; if(hs==NULL) printf(“栈空“); else{ *x=hs-data; p=hs; hs=hs-next; free(p); } },,,an,,,,,.,,,,hs,d,an+1,,,*X=d,,p,,hs,作业,1.简述链栈的定义。
2.做教材习题中的以下题目 单项选择题：(4),(6) 填空题：(4) 应用题：(2),3.3 链队列,1.链队列的定义 链队列：链式存储的队列 (只允许在表尾进行插入和在表头进行删除运算的单链表) 头指针：front 尾指针：rear,typedef struct node { datatype data; struct node *next; }linkqueue; typedef struct { linkqueue *front,*rear; }lqueue; lqueue *hq; /*hq链队列指针变量*/,链队列的类型定义如下：,2.链队列的运算,void insertq(lqueue *hq ,datatype x) { linkqueue *p; p=malloc(sizeof(linkqueue)); p-data=x;p-next=NULL; if(hq-rear==NULL) { hq-front=p;hq-rear=p; } else{ hq-rear-next=p; hq-rear=p; } },,,,… …,,an,∧,,front,rear,,,,p,,hp,⑴进队,⑵出队,void deleteq(lqueue *hq ,datatype *x) { linkqueue *p; if(hq-front==NULL) printf (“队空“); else{ p=hq-front; hq-front=p-next; *x=p-data; free(p); if(hq-front==NULL) hq-rear=hq-front; } },,,… …,,an,∧,,front,rear,,,hp,,,*X= a1,作业,1.简述链队列的定义。
2.做教材习题中的以下题目 单项选择题：(5),(7) 填空题：(8) 应用题：(3),3.4 字符串的链式存储,typedef struct node { char ch; struct node *next; }linkstring ;,由于串结构的特殊性——结构中的每个数据元素是一个字符，所以在用链表存储字符串时，存在一个结点大小的问题，每个结点可以存放一个字符，也可以存放多个字符块链结构:下图是结点大小为4的链表由于字符串的长度不一定是结点大小的整倍数，则链表的最后一个结点不一定会占满，此时补上‘#’或其他非串字符值（通常‘#’不属于串的字符集，是一个特殊的符号）尾指针tail：指示最后一个结点 len：存储串的实际长度,#define MAX 结点块的最大值 typedef struct node { char ch[MAX]; struct node *next; } cnode; typedef struct { int len; cnode *head,*tail; }lstring;,块链结构的结点描述如下：,结点存储密度 = ───────────,结点存储密度,结点大小选择的是否合理，直接影响存储空间的利用率。
串所占存储空间,结点实际分配的存储空间,作业,1.1个字符串用链式结构存储有几种方式？ 2.做教材习题中的以下题目 应用题：(5),3.5 链表应用举例,例3-1 有一单链表l，其头结点指针head，编写一算法将其倒置即实现如下图的操作a)为倒置前，(b)为倒置后a),(b),算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束void reverse(linklist head) { linklist p,q; p=head-next; head-next=NULL; while(p) { q=p; p=p-next; q-next=head-next; head-next=q; } },例3-2 已知单链表h，写一算法，删除其中所有重复的结点 算法思路：用指针p指向第一个数据结点，从它的后继结点开始到表的结束，找与其值相同的结点并删除之；p指向下一个；依此类推，p指向最后结点时算法结束 参考算法如下：,void del(linklist h) { lnode *p,*q,*r; p=h-next; if(p==NULL) return; while(p) { q=p; while (q-next) { if(q-next-data==p-data) { r=q-next; q-next=r-next; free(r); } else q=q-next; } p=p-next; } },例3-3 设有两个单链表a、b，其中元素递增有序，编写算法将a、b归并成一个按元素值递减（允许有相同值）有序的链表c，要求用a、b中的原结点形成，不能重新申请结点。
算法思路：利用a、b两表有序的特点，依次进行比较，将当前值较小者取出，插入到c表的头部，得到的c表则为递减有序的 参考算法如下：,linklist merge(linklist a,linklist b) { linklist c; lnode *p,*q; p=a-next; q=b-next; c=a; /*C表的头结点*/ c-next=NULL; free(b); while(p } },作业,1.做教材习题中的以下题目 应用题：(4),。