数据结构 第2章-2线性表的单链表存储结构.ppt

《数据结构 第2章-2线性表的单链表存储结构.ppt》由会员分享，可在线阅读，更多相关《数据结构 第2章-2线性表的单链表存储结构.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、typedef struct Node DataType data;struct Node *next;SLNode,*LinkList;对于线性表的单链表存储结构描述:讨论：讨论：问问1 1：第一行的：第一行的Node Node 与最后一行的与最后一行的SLNodeSLNode是不是一回事？是不是一回事？答答1 1：不是。前者：不是。前者NodeNode是结构名，后者是结构名，后者SLNodeSLNode是对整个是对整个structstruct类型的一种类型的一种“缩写缩写”，是一种，是一种“新定义名新定义名”，它只，它只是对现有类型名的补充，而不是取代。是对现有类型名的补充，而不是取代。请

2、请注意：注意：typedeftypedef不可能创造不可能创造任何新的数据类型，而仅仅是任何新的数据类型，而仅仅是在原有的数据类型中命名一个在原有的数据类型中命名一个新名字，其目的是使你的程序新名字，其目的是使你的程序更易阅读和移植。更易阅读和移植。1typedef struct student char name;int age;student,*pointer;注意：注意：student和和studentstudent同名但不同意。同名是为了表述起同名但不同意。同名是为了表述起来方便。来方便。例如，若结构名为例如，若结构名为studentstudent，其新定义名缩写也最好写成其新定义名缩

3、写也最好写成studentstudent，因为描述的对象相同，方便阅读和理解。因为描述的对象相同，方便阅读和理解。问问2 2：结构体中间的那个：结构体中间的那个structstruct Node Node是何意？是何意？答答2 2：在：在“缩写缩写”SLNodeSLNode还没出现之前，只能用原始的还没出现之前，只能用原始的structstruct Node Node来来进行变量说明。此处说明了指针分量的数据进行变量说明。此处说明了指针分量的数据类型是类型是structstruct Node Node。2例例：单链表的建立和输出单链表的建立和输出例：用单链表结构来存放例：用单链表结构来存放26

4、个英文字母组成的线个英文字母组成的线性表性表（a，b，c，z）,请写出请写出C语言程序语言程序。实现思路：实现思路：先开辟头指针，然后陆续为每个结点开辟存储先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。空间并及时赋值，后继结点的地址要提前送给前面的指针。先挖先挖“坑坑”,后种后种“萝萝卜卜”！3#include#include#include#include typedef struct nodechar data;struct node*next;node;将全局变量及函数提前说明：将全局变量及函数提前说明：node*p,*q,*head;/一般

5、需要一般需要3 3个指针变量个指针变量int n;/数据元素的个数数据元素的个数int m=sizeof(node);/*/*结构类型定义好之后，每个结构类型定义好之后，每个nodenode类型的长类型的长度就固定了，度就固定了，m m求一次即可求一次即可*/4新手特别容易忘记！新手特别容易忘记！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；

6、/让指针变量让指针变量P指向后一个结点指向后一个结点p-data=i+a-1;/最后一个元素要单独处理最后一个元素要单独处理p-next=NULL;/单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！void build()/字母链表的生成字母链表的生成。要一个个慢慢链入要一个个慢慢链入5p=head;while(p)/当指针不空时循环（仅限于当指针不空时循环（仅限于无头结点无头结点的情况）的情况）printf(%c,p-data);p=p-next;/让指针不断让指针不断“顺藤摸瓜顺藤摸瓜”讨论：要统计链表中数据元素的个数，该如何改写？讨论：要统计链表中数据元素的个数，该如何改写？su

7、m+;sum+;sum=0;sum=0;void display()/*字母链表的输出字母链表的输出*/6void main()void main()build();build();display();display();问：上述建立的单链表带头结点吗？问：上述建立的单链表带头结点吗？7二、单链表的操作实现二、单链表的操作实现定义单链表结点的结构体如下定义单链表结点的结构体如下:t typedef struct Node DataType data;struct Node*next;SLNode;、初始化初始化void ListInitiate(SLNode*head)*初始化*/*如果有内存

8、空间，申请头结点空间并使头指针head指向头结点*/if(*head=(SLNode*)malloc(sizeof(SLNode)=NULL)exit(1);(*head)-next=NULL;/*置链尾标记NULL*/8、求单链表中数据元素的个数、求单链表中数据元素的个数intint ListLength(SLNodeListLength(SLNode*head)*head)SLNodeSLNode*p=head;*p=head;/*p/*p指向头结点指向头结点*/intint size=0;size=0;/*size/*size初始为初始为0*/0*/while(p-next!=NULL)

9、/*while(p-next!=NULL)/*循环计数循环计数*/p=p-next;p=p-next;size+;size+;return size;return size;9在链表中插入一个元素在链表中插入一个元素X X 的示意图如下：的示意图如下：X Xqabp链表插入的核心语句：链表插入的核心语句：Step 1Step 1Step 1Step 1：q q q q-next=-next=p-nextp-next;Step 2Step 2Step 2Step 2：p-nextp-next=q=q；p-nexts-next思考：思考：思考：思考：Step1Step1Step1Step1和和和和

10、2 2 2 2能互换么？能互换么？能互换么？能互换么？X X 结点的生成方式：结点的生成方式：m=m=sizeof(SLNode);q=(SLNode*)malloc(m);q-data=X X;q-next=?bap插插插插 入入入入 X X、向单链表中插入一个元素、向单链表中插入一个元素10intint ListInsert(SLNodeListInsert(SLNode*head,*head,intint i,i,DataTypeDataType x)x)SLNodeSLNode*p,*q;*p,*q;intint j;j;p=head;p=head;j=-1;j=-1;while(p-

11、next!=NULL&j next!=NULL&j next;j+;p=p-next;j+;if(j!=i-1)if(j!=i-1)printfprintf(插入位置参数错！插入位置参数错！););return 0;return 0;(2)(2)if(q=(if(q=(SLNodeSLNode*)*)malloc(sizeof(SLNodemalloc(sizeof(SLNode)=NULL)=NULL)exit(1);exit(1);q-data=x;q-data=x;(3)(3)q-next=p-next;q-next=p-next;p-next=q;(4)p-next=q;(4)retu

12、rn 1;return 1;注：此单链表是带头结点的注：此单链表是带头结点的11在链表中删除某元素在链表中删除某元素b b的示意图如下：的示意图如下：c a bp删除动作的核心语句删除动作的核心语句（要借助辅助指针变量（要借助辅助指针变量q q）：）：q=p-next;/首先首先保存保存b b的的指针，靠它才能找到指针，靠它才能找到c c；p-next=q-next;/将将a a、c c两结点相连，淘汰两结点相连，淘汰b b结点；结点；free(q)；/彻底释放彻底释放b b结点空间结点空间p-next思考：思考：省略省略free(q)语句语句行不行？行不行？(p-next)-nextq、从、

13、从 单链表中删除一个元素单链表中删除一个元素12intint ListDelete(SLNodeListDelete(SLNode*head,*head,intint i,i,DataTypeDataType*x)*x)SLNodeSLNode*p,*s;*p,*s;intint j;j;(1)p=head;(1)p=head;j=-1;j=-1;while(p-next!=NULL&p-next-next!=NULL&while(p-next!=NULL&p-next-next!=NULL&j i-1)j next;p=p-next;j+;j+;if(j!=i-1)if(j!=i-1)pri

14、ntfprintf(“(“插入位置参数错！插入位置参数错！”););return 0;return 0;(2)(2)s=p-next;s=p-next;*x=s-data;x=s-data;(3)(3)p-next=p-next-next;p-next=p-next-next;free(s);free(s);return 1;return 1;13三、三、单单链表的操作效率分析链表的操作效率分析（1）查找查找 因线性链表只能顺序存取，即在查找时要从头指针找起，因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为查找的时间复杂度为 O(n)。时间效率分析时间效率分析（2）插入和删

15、除插入和删除 因线性链表不需要移动元素，只要修改指针，仅就插入或删因线性链表不需要移动元素，只要修改指针，仅就插入或删除而言，时间复杂度为除而言，时间复杂度为 O(1)。但是，如果要在单链表中进行在某结点但是，如果要在单链表中进行在某结点前前插或删除操作，插或删除操作，因为要因为要从头查找前驱从头查找前驱结点，所以一般情况下，结点，所以一般情况下，单链表插单链表插入和删除操作入和删除操作的时间复杂度是的时间复杂度是 O(n)（同顺序表）。同顺序表）。14四、应用举例四、应用举例例、编程实现：建立一个单链表，首先依次输入数据元素,10，然后删除数据元素，最后依次显示当前表中的数据元素。#incl

16、ude#include#include typedef int DataType;#include LinList.h重点是链表重点是链表15void main(void)void main(void)SLNodeSLNode*head;*head;intint i,x;i,x;ListInitiate(&headListInitiate(&head););for(i=0;i10;i+)for(i=0;i10;i+)if(ListInsert(headif(ListInsert(head,i,i+1)=0),i,i+1)=0)printfprintf(错误错误!n);return;!n);re

17、turn;if(ListDelete(headif(ListDelete(head,4,&x)=0),4,&x)=0)printfprintf(错误错误!n);!n);return;return;16 for(i=0;i for(i=0;i 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

18、=p-next;q-next=s;/准备处理下一结准备处理下一结点点p-next=q;/以以an为首为首 （要求同学们根据下面算法的核心语句，编写一（要求同学们根据下面算法的核心语句，编写一个完整算法）个完整算法）算法的核心语句算法的核心语句 A A 或或 B B20例例3 3：试写一算法，实现顺序表的就地逆置，即利用原表试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（的存储空间将线性表（a1,a2,.,ana1,a2,.,an）逆置为（逆置为（anan，an-1an-1，.,a1.,a1）。）。参考程序：参考程序：void void inverseinverse(SeqListSeqList*L)*L)DataTypeDataType temp temp;intint i;i;for(for(intint i i=0;=0;i isize-1)/2;size-1)/2;i i+)+)/循环次数为表长的一半循环次数为表长的一半temptemp=L-list=L-listi i;L-list;L-listi i=L-listL-size-=L-listL-size-i i-1;-1;L-listL-size-L-listL-size-i i-1=-1=temptemp;21 22