数据结构第2章 线性表__C版.ppt

* 练习题 1.说出头指针、头结点、首元结点的区别 2.简述线性表的两种存储结构：顺序表和链表的优缺点。 3.已知L是带表头结点的单链表，且P是指向表中某个结点的指针，试写出在P所指结点前插入指针S所指结点的语句序列。 * 练习题 4.简述以下算法的功能： status A(LinkList L){//L是无表头结点的单链表 if(LL-next){ Q=L;L=L-next;p=L; while(p-next)p=p-next; p-next=Q;Q-next=NULL; } return OK; } void hello(){printf(hello world!\n);} void runFun(void (*pFun)()){pFun();}void main() { runFun(hello);} * * * 例1、线性表:(Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ)的单链表示意图如下： 地址 data next 100 C 198 120 F NULL 128 B 100 147 E 120 158 A 128 198 D 147 158 头指针Ｌ * 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。 用C语言描述的单链表如下： Typedef char ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; * LNode *p,t; LinkList q; 注意区分指针变量和结点变量这两个不同的概念。 P为指针变量，它的赋值只能通过两种情况实现： 1. 动态申请空间 p=(LinkList) malloc(sizeof(LNode)); 函数malloc分配了一个类型为LNode的结点变量的 空间，并将其首地址放入指针变量p中。一旦p所指 的结点变量不再需要了，可通过函数free p释放所指 的结点变量空间。 2. 将另一个指针型变量赋值给p 如：p=q; * 有时为了处理方便，在第一个结点之前附加一个“头结点”，其数据域可以不存储任何信息，也可以存储线性表的长度等附加信息。其指针域指向第一个元素结点，并令头指针指向头结点。 带头结点的空链表 注意区分：头指针、头结点、首元结点！ * 二、单链表上的基本操作(带头结点) 1. 初始化操作 建立一个空的链表即建立一个只有头结点的 链表。 void InitList(LinkList L )　{　　// 创建一个带头结点的空链表,L 为指向头结点的指针　　L = (LinkList) malloc(sizeof(LNode));　　if (!L) exit(1); 　// 存储空间分配失败　　L-next = NULL;　} 算法的时间复杂度为O (1)。 * 2.销毁结构 void DestroyList(LinkList L){// 销毁以L为头指针的单链表，释放链表中所有结点空间　　while (L)　　{　　　p = L;　　　L = L-next;　　　free p;　　} 　　L = NULL;　}  算法的时间复杂度为O (Listlength(L))。 * 分析：单链表是非随机存取的存储结构，为取第 i 个元素，首先必须先找到第 i-1 个元素。因此不论 i 值为多少，都必须从头结点开始起“点数”，数到第 i 个为止。头结点可看成是第0个结点。 3.取第i个元素 点数： 0 1 2 ........ * Status GetElem_L(LinkList L, int i, ElemType e ){ // 若1≤i≤LengthList(L)，则用 e 带回指针L指向头结点的单链表中第 i 个元素的值且返回函数值为OK,否则返回函数值为ERROR　　p = L; j =0; // p 指向第一个结点　　while ( p j i )　　{ // 顺指针向后查找，直至p指到第i 个结点或 p 为空止　　　p = p-next; ++j;　　} 　　if ( !p || ji ) return ERROR; //第i 个结点不存在　　e = p-data; // 取第i 个元素　　return OK;　}  * 4.插入元素操作 分析：在线性表中“插入”一个元素时，使元素之间 的关系 ai-1, ai 改变为 ai-1,e 和 e, ai 。当