数据结构之链表.ppt
SCIE, University of Electronic Science and Technology of China12.1线性表线性表线性表不同的实现方式：2.1.1顺序表 数组存储 顺序表定义 顺序表基本操作： 遍历、插入、删除 顺序表算法分析2.1.2单链表2.1.3双向链表 链接存储2.1.4循环链表SCIE, University of Electronic Science and Technology of China22.1线性表线性表#include stdio.h“struct list_seq int data20; int length;int main() struct list_seq list; int no, i; list.length=0; for(i=0;inext=null;带头节点单链表对链表尾的判断空表： p-next=null;非空表：p-next=null;SCIE, University of Electronic Science and Technology of China92.1.2单链表单链表初始化算法：elemtype initlist(node * * h)*h=(node *)malloc(sizeof(node); (*h)-next=null;三、链表的基本操作访问插入删除SCIE, University of Electronic Science and Technology of China102.1.2单链表单链表n访问操作p问题描述：访问链表的第i个节点p问题分析：输入：链表，i输出：链点指向链点的指针p算法实现分析：只能从链表头开始，一个一个“数”下去，直到第i个。a1anheadtaila2temptemptempSCIE, University of Electronic Science and Technology of China112.1.2单链表单链表从自然语言到算法语言从自然语言到算法语言n如何描述我们找到第i个节点的动作。p 1、先找到链表首结点的地址p 2、通过“地址”，找到链点p 3、在链点中找到后继元素的“地址”p 4、记录这个地址p = list-head;while( )p-data p = p-next;p-next SCIE, University of Electronic Science and Technology of China122.1.2单链表单链表 继续完善描述继续完善描述p 1、先找到链表首结点的地址p 2、通过“地址”，找到链点p 3、在链点中找到后继元素的“地址”p 4、记录这个地址，回到2p = list-head;while(1)p-data p = p-next;p-next ,计数，如果计数到i，就结束counter = 1;counter +;if( counter = i)break;SCIE, University of Electronic Science and Technology of China132.1.2单链表单链表node_type *get_node( list, i )while(counter next;int counter ;node_type * p;return p;if( p = = NULL) return NULL;p = list-head;counter = 1;a1nextaiai+1an pa2逐个“数”的动作counter： 1 23设i 3当in时算法结果怎样？思考SCIE, University of Electronic Science and Technology of China142.1.2单链表单链表n注意1、p = p-next ;沿链表前进2、循环结束条件counter = = i 或 node = = NULLcounter list-length思考如果希望获得值为x的元素，如何实现？while( p-data = x & p != NULL)SCIE, University of Electronic Science and Technology of China152.1.2单链表单链表n链表插入操作p问题描述：在元素ai前插入新的元素new_node ;p问题分析：输入：链表，location，x输出：插入新元素后的链表。p算法实现分析SCIE, University of Electronic Science and Technology of China162.1.2单链表单链表a1aianheadtailai-1.anewa1aianheadtailai-1.anew两个步骤：ai-1-next = anew ;anew-next = ai ;SCIE, University of Electronic Science and Technology of China172.1.2单链表单链表SCIE, University of Electronic Science and Technology of China182.1.22.1.2单链表单链表while( counter next;void insertl（list, new_node , location） 找到ai-1p-next = new_node;new_node-next =?ai-1-next = anew ;anew-next = ai ;a1ai-1aianpnewnodea2p list-header; counter = 1qq = p-next;q;法一SCIE, University of Electronic Science and Technology of China192.1.2单链表单链表while( counter next;void insertl（list, new_node , location） new_node-next = p-next;p-next = new_node;a1ai-1aianpnewnodea2p list-header; counter = 1法二SCIE, University of Electronic Science and Technology of China202.1.2单链表单链表void insertl（list, new_node , location） while( counter next;new_node-next = p-next;p-next = new_node;counter = 1;p = list-head; 初始化list-length +;边界情况：表首插入表尾插入SCIE, University of Electronic Science and Technology of China212.1.2单链表单链表a1ai-1aianlist-headnewnodenew_node-next = a1;list-head;list-head = new_node;SCIE, University of Electronic Science and Technology of China222.1.22.1.2单链表单链表void insertl（list, new_node , location） while( counter next;new_node-next = p-next;p-next = new_node;counter = 1;p = list-head; 初始化if(location = 1)elsenew_node = list-head;list-head = new_node;list-length +;边界情况：表首插入表尾插入SCIE, University of Electronic Science and Technology of China232.1.22.1.2单链表单链表a1ai-1aianlist-head注意当循环执行到表尾时p 的值为NULL（空）p-next是悬空的值while( counter next;new_node-next = p-next;p-next = new_node;p-next != NULL)NULL p因此循环结束应以p-next = NULL为条件当i 链表长度 时会造成系统崩溃表尾插入SCIE, University of Electronic Science and Technology of China242.1.2单链表单链表void insertl（list, new_node , location） while( counter next != NULL)counter = counter + 1;p = p-next;new_node-next = p-next;p-next = new_node;counter = 1;p = list-head; if(location = = 1)elsenew_node-next = list-head;list-head = new_node;list-length +;SCIE, University of Electronic Science and Technology of China252.1.2单链表单链表从插入算法中对链表操作的体会从插入算法中对链表操作的体会n1、链表操作往往从表头开始，逐个找到需要的链点n2、链表操作的有向性 不能回退；n3、链表指针小心使用，谨防丢失。n4、不能访问空指针的成员n5、插入过程没有进行链点内容进行搬移。SCIE, University of Electronic Science and Technology of China262.1.2单链表单链表n链表的删除操作p问题描述：删除元素ai ;p问题分析：输入：链表，location输出：删除元素后的链表。p算法实现分析SCIE, University of Electronic Science and Technology of China272.1.2单链表单链表a1ai+1anheadtailai-1.aiai-1-next = ai-next;即ai-1-next = ai-1-next-next;SCIE, University of Electronic Science and Technology of China282.1.22.1.2单链表单链表找到ai-1执行删除动作ai-1-next = ai-1-next-nextvoid deletel（list, location）注意，从链表上取下的链点ai-1需要挂在一个指针上，否则可能丢失a1ai+1anheadtailai-1.aitempSCIE, University of Electronic Science and Technology of China292.1.2单链表单链表void deletel（list, location） while( counter next;p-next = p-next-next;counter = 1;p = list-head; 初始化if(location = 1)elselist-head = list-head-next;temp = p-next;free(temp);temp = list-head;free(temp);list-length -;从链表删除的链点，一般应该释放其空间SCIE, University of Electronic Science and Technology of China302.1.2单链表单链表n注意:p对被删除删除链点的处理往往需要要free（ ）SCIE, University of Electronic Science and
