数据结构第2章-2线性表的单链表存储结构.ppt
1,typedef struct Node DataType data;struct Node*next;SLNode,*LinkList;,对于线性表的单链表存储结构描述:,讨论：,问1：第一行的Node 与最后一行的SLNode是不是一回事？答1：不是。前者Node是结构名，后者SLNode是对整个struct类型的一种“缩写”，是一种“新定义名”，它只是对现有类型名的补充，而不是取代。,请注意：typedef不可能创造任何新的数据类型，而仅仅是在原有的数据类型中命名一个新名字，其目的是使你的程序更易阅读和移植。,2,typedef struct student char name;int age;student,*pointer;,注意：student和student同名但不同意。同名是为了表述起来方便。例如，若结构名为student，其新定义名缩写也最好写成student，因为描述的对象相同，方便阅读和理解。,问2：结构体中间的那个struct Node是何意？答2：在“缩写”SLNode还没出现之前，只能用原始的struct Node来进行变量说明。此处说明了指针分量的数据类型是struct Node。,3,例：单链表的建立和输出,例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，z）,请写出C语言程序。,实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。,先挖“坑”,后种“萝卜”！,4,#include#includetypedef struct nodechar 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=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;/单链表尾结点的指针域要置空！,void build()/字母链表的生成。要一个个慢慢链入,6,p=head;while(p)/当指针不空时循环（仅限于无头结点的情况）printf(%c,p-data);p=p-next;/让指针不断“顺藤摸瓜”,讨论：要统计链表中数据元素的个数，该如何改写？,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*)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-next=q；,p-next,s-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-next;/首先保存b的指针，靠它才能找到c；p-next=q-next;/将a、c两结点相连，淘汰b结点；free(q)；/彻底释放b结点空间,p-next,思考：省略free(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,三、单链表的操作效率分析,（1）查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。,时间效率分析,（2）插入和删除 因线性链表不需要移动元素，只要修改指针，仅就插入或删除而言，时间复杂度为 O(1)。,但是，如果要在单链表中进行在某结点前插或删除操作，因为要从头查找前驱结点，所以一般情况下，单链表插入和删除操作的时间复杂度是 O(n)（同顺序表）。,15,四、应用举例,例、编程实现：建立一个单链表，首先依次输入数据元素,10，然后删除数据元素，最后依次显示当前表中的数据元素。#include#include#include typedef int DataType;#include LinList.h,重点是链表,16,void main(void)SLNode*head;int i,x;ListInitiate(,17,for(i=0;i ListLength(head);i+)if(ListGet(head,i,18,五、循环单链表,x,head,a0,an,循环链表示意图：循环单链表是单链表的另一种形式，其结构特点是链表中的最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。问：带头结点的循环单链表的插入、删除算法如何写？,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,.,an）逆置为（an，an-1，.,a1）。参考程序：void inverse(SeqList*L)DataType temp;int i;for(int i=0;isize-1)/2;i+)/循环次数为表长的一半temp=L-listi;L-listi=L-listL-size-i-1;L-listL-size-i-1=temp;,22,
