数据结构第2章3.ppt

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

2、同义。同名是为了表述起来方便。 例如，若结构名为student，其新定义名缩写也最好写成student，因为描述的对象相同，方便阅读和理解。,问2：结构体中间的那个struct Node是何意？ 答2：在“缩写” SLNode还没出现之前，只能用原始的struct Node来进行变量说明。此处说明了指针分量的数据类型是struct Node。,typedef struct student char name; int age; student,*pointer;,3,例： 单链表的建立和输出,例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，z）,请写出C语言程序。,实现思路：先开

3、辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。,先挖“坑”,后种“萝卜”！,4,#include #include typedef struct node char data; struct node *next; node;,将全局变量及函数提前说明：,node *p,*q,*head; /一般需要3个指针变量 int n ; / 数据元素的个数 int m=sizeof(node); /*结构类型定义好之后，每个node类型的长度就固定了，m求一次即可*/,5,新手特别容易忘记！, int i; head=(node*)malloc(m); /m=

4、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( ) /字母链表的生成。要一个个慢慢链入,6,p=head; while (p) /当指针不空时循环（仅限于无头结点的情况） printf(%c,p-data); p=p-next; /让指针不断“顺藤摸瓜” ,讨

5、论：要统计链表中数据元素的个数，该如何改写？,sum+;,sum=0;,void display() /*字母链表的输出*/,7,void main( ) build( ); display( ); 问：上述建立的单链表带头结点吗？,8,二、单链表的操作实现,定义单链表结点的结构体如下:typedef struct Node DataType data; struct Node *next;SLNode; 、初始化 void ListInitiate(SLNode *head)*初始化*/ /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/ if(*head = (SLNode

6、 *)malloc(sizeof(SLNode) = NULL) exit(1); (*head)-next = NULL;/*置链尾标记NULL */ ,9,、求单链表中数据元素的个数int ListLength(SLNode *head)SLNode *p = head;/*p指向头结点*/int size = 0;/*size初始为0*/ while(p-next != NULL) /*循环计数*/p = p-next;size +;return size;,10,在链表中插入一个元素X 的示意图如下：,链表插入的核心语句：,Step 1：q-next=p-next; Step 2：p-

7、next=q ；,p-next,p-next,思考：Step1和2能互换么？,X 结点的生成方式： m=sizeof(SLNode); q=(SLNode *)malloc(m); q-data=X ; q-next= ?,、向单链表中插入一个元素,11,int ListInsert(SLNode *head, int i, DataType x) SLNode *p, *q; int j; p = head;j = -1; while(p-next != NULL 注：此单链表是带头结点的,12,在链表中删除某元素b的示意图如下：,删除动作的核心语句（要借助辅助指针变量q）：,q = p-n

8、ext; /首先保存b的指针，靠它才能找到c； p-next=q-next; /将a、c两结点相连，淘汰b结点； free(q) ； /彻底释放b结点空间,p-next,思考： 省略free(q)语句行不行？ 如果不设辅助指针变量q,行不行?,(p-next) - next,q,、从 单链表中删除一个元素,13,int ListDelete(SLNode *head, int i, DataType *x) SLNode *p, *s;int j; (1) p = head;j = -1;while(p-next != NULL ,14,撤销单链表,void Destory(SLNode *h

9、ead) SLNode *p, *p1; p=*head; while(p!=NULL) p1=p; p=p-next; free(p1); *head=NULL; ,15,三、单链表的操作效率分析,（1） 查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。,时间效率分析,（2） 插入和删除 因线性链表不需要移动元素，只要修改指针，仅就插入或删除而言，时间复杂度为 O(1)。,但是，如果要在单链表中进行在某结点前插或删除操作，因为要从头查找前驱结点，所以一般情况下，单链表插入和删除操作的时间复杂度是 O(n)（同顺序表）。,16,四、应用举例,例、编程实现：

10、建立一个单链表，首先依次输入数据元素,10，然后删除数据元素，最后依次显示当前表中的数据元素。 #include #include #include typedef int DataType; #include LinList.h,重点是链表,17,void main(void) SLNode *head;int i , x; ListInitiate(,18,for(i = 0; i ListLength(head); i+) if(ListGet(head, i, ,19,五、循环单链表,x,head,a0,an,循环链表示意图： 循环单链表是单链表的另一种形式，其结构特点是链表中的最后一

11、个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。 问：带头结点的循环单链表的插入、删除算法如何写？,head,20,循环链表操作,循环链表的操作与单链表类似, 差别就在最后结点的指针值不是NULL，而是head. （1）初始化中， (*head)-next=NULL 应改为？ （2）其它函数的循环判断条件： p-next!=NULL 等应改为？,XXX,head,a0,an-1,head,XXX,head,21,例2：试用C语言编写一个算法，将一循环单链表就地逆置。,操作前：（a1, a2, ai-1，ai, ai+1 ，, an）,操作后：（ an, ai+

12、1 ，ai, ai-1 ，, a2, a1 ）,ai-1,ai,ai+1,p,q,r,22,q=head; p=head-next; /有头结点 while(p!=head) /循环单链表 r=p-next; p-next=q; /前驱变后继 q=p; p=r; /准备处理下一结点 head-next=q; / 以an为首,q=head; p=head-next; /有头结点 while(p!=head) /循环单链表 s=q; q=p; p=p-next; q-next=s; /准备处理下一结点 p-next=q; / 以an为首,（要求同学们根据下面算法的核心语句，编写一个完整算法）算法的核心语句 A 或 B,23,例3： 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a