数据结构单链表.ppt
上堂课要点回顾,线性表的抽象数据类型定义顺序表类型定义基本操作实现应用,数据结构课程内容,第 三 次 课,阅读：朱战立，第26-35页练习：作业3,2.3 线性表的链式表示和实现 链表,链式存储结构 定义：用一组任意的存储单元来存放线性表 中的数据元素。特点：逻辑结构上相邻的元素在其存储的物 理位置上不一定相邻。通过指针把链表的存储结点链接成一 个链。,2.3.1 单链表的存储结构,结点结构：链表每个结点中只有一个指针 域指向直接后继结点。,结点类型定义（借用指针类型）typedef int DataType;typedef struct Node DataType data;struct Node*next;/递归定义 SLNode;/*单链表结点结构体类型SLNode*/,SLNode*head;,数据域：元素本身信息指针域：指示直接后继的存储位置,a0,a1,a2,an-1,head,空表：,非空表：,单链表的逻辑状态,首元结点,l1-next=l2;l2-next=l3;l3-next=NULL;,SLNode*l1=(SLNode*)malloc(sizeof(SLNode);SLNode*l2=(SLNode*)malloc(sizeof(SLNode);SLNode*l3=(SLNode*)malloc(sizeof(SLNode);l1-data=7;l2-data=0;l3-data=6;,l1,l2,l3,sizeof(x)计算变量x的所占的字节数malloc(m)开辟m字节长度的地址空间，并返回这段空间的首地址free(p)释放指针p所指变量的存储空间，即彻底删除一个变量,存储结构,带头结点的单链表：非空表：,空表：,满足 head-next=NULL,头结点是在链表的首元结点之前附设的一个结点；其数据域不存储线性表的数据元素，只放表长等信息；其指针域存储首元结点的地址,头结点,初始化单链表,单链表的操作实现,void ListInitiate(SLNode*head)/置以head为头指针的带头结点的单链表为空表*head=(SLNode*)malloc(sizeof(SLNode);(*head)-next=NULL;main()SLNode*head;ListInitiate(.,空表：,读取单链表中第i个结点,思想：从头指针开始，顺着链向后查找。具体：设p为搜索指针，计数器 j 从-1开始计数。初始p指向头结点。循环：p=p-next;j+;直至j=i或至表尾 循环退出后如果j=i 时，p所指结点即为第 i 个结点，否则，表空或 in-1（非法）,a0,a1,an-1,ai,head,int ListGet(SLNode*head,int i,DataType*x)/*在以head为头指针的带头结点的单链表中，读取第i个元素*/SLNode*p;int j;p=head;j=-1;/*从头指针开始查找ai*/while(p-next!=NULL/注意：仅当 p!=NULL时，p-data、p-next才有意义,【单链表取元素算法】,|i0,单链表取元素算法的时间复杂度：上述算法的时间复杂度与while语句的频度有关，最坏情况下搜索完整个链表，因此，对于长度为 n 的单链表而言，算法的时间复杂度为 O(n)。,插入前插,思想：要在第 i 个结点之前插入元素 x，必须先找到第 i-1 个结点的地址，这样，才能将第 i-1 个结点的指针修改指向新插入的结点，而新结点的指针指向第 i 个结点。,q-next=p-next;,注意：两条语句的顺序不能颠倒，否则ai的地址会丢失。,另外，要注意合法 i 值为：0i size 若 isize，则 i 值非法。,ai-1,head,a0,p-next=q;,q-next,p-next,q=(SLNode*)malloc(sizeof(SLNode);q-data=x;,int ListInsert(SLNode*head,int i,DataType x)/*在以head为头指针的带头结点的单链表中的第i个结点之前插入值为x的结点*/SLNode*p,*q;/*p：搜索指针，q：新生成指针*/int j;p=head;j=-1;while(p-next!=NULL,【单链表前插算法】,if(j!=i-1)printf(“n插入位置i不合理!”);return 0;/*产生新结点q*/q=(SLNode*)malloc(sizeof(SLNode);q-data=x;/*插入*/q-next=p-next;p-next=q;/*注意：上面两条语句的次序不能颠倒*/return 1;,思想：要删除第 i 个结点，同样必须找到第 i-1 个结点的地址，这样，才能将第 i-1个结点的指针修改指向第 i+1 个结点。,删除,s=p-next;,ai-1,p-next=p-next-next;,free(s);,an-1,ai+1,另外，要注意合法 i 值为：0i size-1,head,a0,p-next,p-next-next,int ListDelete(SLNode*head,int i,DataType*x)/*删除以head为头指针的带头结点的单链表中的第i个结点*/SLNode*p,*s;/*p：搜索指针，s：缓冲指针*/int j;p=head;j=-1;/*寻找第i-1个结点*/while(p-next!=NULL,【单链表删除算法】,if(j!=i-1)printf(“n删除位置不合理!”);return 0;/*删除*/s=p-next;*x=s-data;p-next=p-next-next;free(s);return 1;,单链表插入删除算法时间复杂度分析：插入、删除算法的时间复杂度均为O(n)。这是因为，虽在单链表中插入或删除元素时无需移动元素，只需修改指针域。但由于它不是随机存取结构，为寻找第i-1个元素，尚需执行ListGet(head,i-1,x)操作，这和顺序存储结构正好相反。,单链表空间复杂度分析：,单链表中每个结点都要增加一个指针域，相当于总共增加了n 个整型变量，空间复杂度为 O(n)。事实上，链表插入、删除运算的快捷是以空间代价来换取时间。,int ListLength(SLNode*head)/求以head为头指针的带头结点的单链表表长 SLNode*p=head;/*p：搜索指针*/int size=0;while(p-next!=NULL)p=p-next;size+;return size;,【单链表求表长算法】,void Destroy(SLNode*head)/释放以head为头指针的带头结点的单链表所占空间 SLNode*p,*p1;p=*head;while(p!=NULL)p1=p;p=p-next;free(p1);*head=NULL;,【撤消单链表算法】,空表：,在单链表中为什么引入头结点？,引入头结点是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。如果不增加头结点，插入和删除操作如何变动？,1）在带头结点单链表第一个数据元素前插入结点,2）删除带头结点单链表第一个数据元素结点,3）在不带头结点单链表第一个数据元素前插入结点,4）在不带头结点单链表其他数据元素前插入结点,5）删除不带头结点单链表第一个数据元素结点,6）删除不带头结点单链表其他数据元素结点,结论：（1）带头结点单链表无论在第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，操作方法不一样（2）删除操作和插入操作类似（3）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表的算法时，头指针参数必须设计成输出型参数（4）因此，带头结点单链表的算法设计简单,2.3.4单链表应用举例 例23（P35）文件 LinList.h(P29-34)文件 LinListExample.c（P35）,作业3,算法设计题：1、补充实现单链表的基本操作1、IsEmpty（）函数实现判断单链表是否为空表。2、InsertFront（）函数实现在单链表首元结点前插入一新结点x。3、InsertEnd（）函数实现在单链表的表尾插入一个新结点x。4、Find()函数实现在单链表中寻找值为x的元素。5、FindPrevious（）函数实现在单链表中寻找值为x的前一个元素。,2、实现带尾指针和表长信息的单链表数据结构1、InsertEnd()函数实现在单链表的表尾插入新结点，但它的运行时间代价为O(n)，因为要从头指针开始遍历整个链表找到尾结点。要求你修改单链表数据结构（包括类型定义和相关函数），使InsertEnd()函数的时间复杂度为O(1)。2、ListLength()函数实现求单链表的表长，但它的运行时间代价为O(n)，因为要从头指针开始遍历整个链表以统计表长。要求修改单链表数据结构（包括类型定义和相关的函数），使ListLength()函数的时间复杂度为O(1)。,作业3（续）,3、p46，2-24 题目“有序顺序表”改为“有序单链表”,作业3（续）,
