数据结构 第2章-2数据结构

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

2、*next;Lnode,*LinkList;,注意：student和student同名但不同意。同名是为了表述起来方便。例如，若结构名为student，其新定义名缩写也最好写成student，因为描述的对象相同，方便阅读和理解。,问2：结构体中间的那个structNode是何意？答2：在“缩写”SLNode还没出现之前，只能用原始的structNode来进行变量说明。此处说明了指针分量的数据类型是structNode。,typedefstructstudentcharname;intage;student,*pointer;,3,例：单链表的建立和输出,例：用单链表结构来存放26个英文字母组成

3、的线性表（a，b，c，z）,请写出C语言程序。,实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。,先挖“坑”,后种“萝卜”！,4,#include#includetypedefstructnodechardata;structnode*next;node;,将全局变量及函数提前说明：,node*p,*q,*head;/一般需要3个指针变量intn;/数据元素的个数intm=sizeof(node);/*结构类型定义好之后，每个node类型的长度就固定了，m求一次即可*/,5,新手特别容易忘记！,inti;head=(node*)malloc

4、(m);/m=sizeof(node)前面已求出p=head;for(i=1;idata=i+a-1;/第一个结点值为字符ap-next=(node*)malloc(m);/为后继结点“挖坑”！p=p-next；/让指针变量P指向后一个结点p-data=i+a-1;/最后一个元素要单独处理p-next=NULL;/单链表尾结点的指针域要置空！,voidbuild()/字母链表的生成。要一个个慢慢链入,6,p=head;while(p)/当指针不空时循环（仅限于无头结点的情况）printf(%c,p-data);p=p-next;/让指针不断“顺藤摸瓜”,讨论：要统计链表中数据元素的个数，该如何

5、改写？,sum+;,sum=0;,voiddisplay()/*字母链表的输出*/,7,voidmain()build();display();问：上述建立的单链表带头结点吗？,8,二、单链表的操作实现,定义单链表结点的结构体如下:typedefstructNodeDataTypedata;structNode*next;SLNode;、初始化voidListInitiate(SLNode*head)*初始化*/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/if(*head=(SLNode*)malloc(sizeof(SLNode)=NULL)exit(1);(*head)

6、-next=NULL;/*置链尾标记NULL*/,9,、求单链表中数据元素的个数intListLength(SLNode*head)SLNode*p=head;/*p指向头结点*/intsize=0;/*size初始为0*/while(p-next!=NULL)/*循环计数*/p=p-next;size+;returnsize;,10,在链表中插入一个元素X的示意图如下：,链表插入的核心语句：,Step1：q-next=p-next;Step2：p-next=q；,p-next,s-next,思考：Step1和2能互换么？,X结点的生成方式：m=sizeof(SLNode);q=(SLNode

7、*)malloc(m);q-data=X;q-next=?,、向单链表中插入一个元素,11,intListInsert(SLNode*head,inti,DataTypex)SLNode*p,*q;intj;p=head;j=-1;while(p-next!=NULL注：此单链表是带头结点的,12,在链表中删除某元素b的示意图如下：,删除动作的核心语句（要借助辅助指针变量q）：,q=p-next;/首先保存b的指针，靠它才能找到c；p-next=q-next;/将a、c两结点相连，淘汰b结点；free(q)；/彻底释放b结点空间,p-next,思考：省略free(q)语句行不行？,(p-nex

8、t)-next,q,、从单链表中删除一个元素,13,intListDelete(SLNode*head,inti,DataType*x)SLNode*p,*s;intj;(1)p=head;j=-1;while(p-next!=NULL,14,三、单链表的操作效率分析,（1）查找因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)。,时间效率分析,（2）插入和删除因线性链表不需要移动元素，只要修改指针，仅就插入或删除而言，时间复杂度为O(1)。,但是，如果要在单链表中进行在某结点前插或删除操作，因为要从头查找前驱结点，所以一般情况下，单链表插入和删除操作的时间复杂度是O

9、(n)（同顺序表）。,15,四、应用举例,例、编程实现：建立一个单链表，首先依次输入数据元素,10，然后删除数据元素，最后依次显示当前表中的数据元素。#include#include#includetypedefintDataType;#includeLinList.h,重点是链表,16,voidmain(void)SLNode*head;inti,x;ListInitiate(,17,for(i=0;iListLength(head);i+)if(ListGet(head,i,18,五、循环单链表,x,head,a0,an,循环链表示意图：循环单链表是单链表的另一种形式，其结构特点是链表中的

10、最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。问：带头结点的循环单链表的插入、删除算法如何写？,head,19,例2：试用C语言编写一个算法，将一循环单链表就地逆置。,操作前：（a1,a2,ai-1，ai,ai+1，,an）,操作后：（an,ai+1，ai,ai-1，,a2,a1）,20,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,21,例3：试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,.,a