《单链表和循环链表》由会员分享，可在线阅读，更多相关《单链表和循环链表（34页珍藏版）》请在金锄头文库上搜索。
1、线性链表 链表是指用一组任意的存储单元依次存放线性表 的结点，这组存储单元即可以是连续的，也可以 是不连续的，甚至是零散分布在内存中的任意位 置。 链表中结点的逻辑次序和物理次序不一定相同。 为了能正确表示结点间的逻辑关系，在存储每个 结点值的同时，还必须存储指示其后继结点的地 址（或位置）信息，这个信息称为指针(pointer) 或链(link)。1 链表中的结点结构 其中：data域是数据域，用来存放结点的值。next是指针域 （亦称链域），用来存放结点的直接后继的地址（或位置） 。 链表通过每个结点的链域将线性表的n个结点按其逻辑次 序链接在一起的。 上述链表的每一个结点只有一个链域，故
2、将这种链表称为 单链表（Single Linked)。 单链表中每个结点的存储地址是存放在其前趋结点的next 域中，而开始结点无前趋，故应设头指针head指向开始结 点。同时，由于终端结点无后继，故终端结点的指针域为 空，即为NULL. 2datanext 例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG )3 通常我们把链表画成用箭头相链接的结点的序列 ，结点之间的箭头表示链域中的指针。 单链表可由头指针惟一确定4 C语言类型描述typedef struct nodedatatype data; /*数据元素类型*/struct node *next;
3、/*指针类型*/ node, * lklist; /*结点类型*/ node是结点类型 lklist是指向node类型的指针 lklist p, 声明一个指向node类型的指针 *p由两个域组成的记录，用(*p).data和(*p).next表示， 通常记成p-data和p-next,分别用来存放数据元素的值 和后继结点的地址 5 有时，我们在单链表的第一个结点之前附设一个 结点，称为头结点 头结点的数据域可以不储存任何信息，也可存储 如线性表的长度等附加信息 头结点的指针域存储指向第一个结点的指针。非空表 空表6l单链表上的一些基本操作 1. 初始化 initiate_lklist(l) 定
4、义 建立如右图所示的一个空表 算法 void initiate_lklist(lklist l-next=NULL; 7L头结点、尾结点NULL2. 求表长 length_lklist(l) 定义 求单链表中结点数目 基本思想 从头到尾数一遍 算法 int length_lklist(lklist l) lklist p=l; /*工作指针 p从头结点开始*/int j=0; /*计数器从0开始，因为有头结点*/while (p-next!=NULL) /*p所指结点不是尾结点*/ p=p-next; /*p指向下一个结点，即往下数*/j+; /*计数器加1*/ return (j); 83.
5、 按序号查找 find_lklist(l, i) 定义 查找单链表第i个元素，否则返回NULL 基本思想 从头指针出发，顺链域next逐个往下搜索，直到找到第i个结 点为止9 算法 node *find_lklist(lklist l, int i) lklist p=l; int j=0; /*初始化*/while (p-next!=NULL) /*找下一个*/j+; /*记数器加1*/if (j=i) return(p); /*找到第i个,返回其指针*/else return (NULL);104. 定位 locate_lklist(l,x) 定义 按值查找，返回线性表l中第一个值与x相等
6、的结点序号， 否则为0 基本思想 从头指针出发，顺链域next逐个往下搜索，直到找到值为x 的结点为止11l算法 int locate_lklist(lklist l, datatype x) lklist p=l; int j=0; /*初始化*/while (p-next!=NULL) /*找下一个*/j+; /*记数器加1*/if (p-data=x) return (j); /*找到x,并返回j*/else return (0); /*没找到,返回0*/125.读表元 get_lklist(l,i) 定义 求链表 l 第 i 个结点的值，若找不到返回NULL 基本思想 类似按序号查找1
7、3l算法datatype get_lklist(lklist l ,int i ) lklist p=l; int j=0; /*初始化*/while (p-next!=NULL) /*找下一个*/j+; /*记数器加1*/if (j=i) return (p-data); /*找到第i个*/else printf(“参数i错或单链表不存在“);return (NULL); 146. 插入 insert_lklist(l,x,i)定义 在线性表l的第i个结点前插入一个数值为e的结点 ，使之成为第i个结点 基本思想 找到插入位置 生成一个数值为e的新结点 修改某些结点的链域15La1anNULL
8、aieai-1La1anNULLaiai-1se 算法 void insert_lklist(lklist p=find_lklist(l, i-1); /*p指向第i-1个结点*/if (p!=NULL) /*第i-1个结点存在*/ s=new node; /*生成一个新结点s*/s-data=x; /*新结点的数值是x*/s-next=p-next; /*新结点的后继是原来的第i个结点*/p-next=s; /*第i-1个结点的后继是新结点*/else printf(“不存在第i个位置“); 167. 删除 delete_lklist(l,i) 定义 删除线性表的第i个结点 基本思想 找到
9、第i个结点 从单链表上摘除该结点(修改某些结点的指针域)17La1anNULLai+1aiai-1La1anNULLai+1ai-1 算法void delete_lklist(lklist p=find_lklist(l, i-1); /*p指向第i-1个结点*/if (p!=NULL) /*q指向第i个结点*/p-next=q-next; /*使p的后继结点为第i+1个结点*/delete q; /*释放第i个结点*/else printf(“不存在第i个结点“);18 插入 删除 求表长 初始化 O(1) 按序号查找 定位（按值查找） 读表元19O(n)O(n) 单链表的其它操作 1.建表
10、 create_lklist1 定义 将一个线性表中的数据元素依次输入并建立该线性表的单链 表 基本思想 初始化表l 依次输入各数据元素，并插入到表l中20 算法 void create_lklist1(lklist int i=1; /*插入位置初始化*/int x;scanf(“%d“,while (x!=0) /*遇0停止建表*/ insert_lklist(l,x,i);i+;scanf(“%d“, 21 分析 特点 利用基本运算 时间复杂性 查找 0+1+2+（n-1）=n(n-1)/2 O(n2) 结论 效率不高 原因 每次插入都从头开始查找到表尾 改进 用一个工作指针始终指向表尾
11、（称为尾指针），用它指示链入 位置22void create_lklist2(lklist datatype x; l=new node;p=l; /* 尾指针的初值*/scanf(“%d“, /*输入第一个结点的值*/while (x!=0) q=new node ; /* 创建新结点*/q-data=x;p-next=q; /* 新结点链入表尾*/p=q; /* 工作指针指向尾结点*/scanf(“%d“, /*输入下一个结点的值*/p-next=NULL; /* 尾指针标志*/23 分析方法二 算法较前者复杂 时间效率比前者高，O(n) 结论 要求时间效率，用方法二 无时间要求，用方法一
12、，简单24循环链表 定义 与单链表区别在于其尾结点的链域不是NULL ，而是一 个指向头结点的指针 特点 从表中任一结点出发都能通过后移操作而扫描整个链 表 示意图 25 循环链表类型说明 #define datatype int typedef struct nodedatatype data; /*数据元素类型*/struct node *next; /*指针类型*/ node, * clklist; /*结点类型*/ node是结点类型 cklist是指向node类型的指针26 基本运算在循环表上的实现类似于在单链表上的实现区别：判断表尾条件不同 p-next!=NULL 改成 p-ne
13、xt!=H,其中H为头指针271. 初始化 initiate_clklist(l) 算法void initiate_clklist(clklist l-next=l;282. 求表长 length_clklist( l ) 算法 int length_clklist(clklist l) clklist p=l; /*工作指针p从头结点开始*/int j=0; /*计数器清0*/while (p-next!=l) /*p所指结点不是尾结点*/ p=p-next; /*p指向下一个结点，即往下数*/j+; /*计数器加1*/ return (j); 293. 按序号查找 find_clklist
14、(l,i) 算法 node *find_clklist(clklist l, int i) clklist p=l; int j=0; /*初始化*/while (p-next!=l) /*找下一个*/j+; /*记数器加1*/if (j=i) return(p); /*找到第i个*/else return (NULL);304.定位 locate_clklist(l,x) 算法 int locate_clklist(clklist l, datatype x) clklist p=l; int j=0; /*初始化*/while (p-next!=l) /*找下一个*/j+; /*记数器加1*/if (p-data=x) return ( j ); /*找到x*/else return (0);315. 读表元 get_clklist( l , i) 算法 datatype get_clklist(clklist l ,int i ) clklist p=l; int j=0;
