《数据结构》2.5线性表的其他表示形式

2018-06-18 04:17:50来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

 1 //单循环链表(对两个单循环链表L1、L2进行连接操作,即将L2的第一个数据元素节点连接到L1的尾节点之后,时间复杂度O(n)优化为O(1))
 2 q = r1->next;                //保存L1的头节点指针
 3 r1->next = r2->next->next;  //L1与L2尾头连接
 4 free(r2_>next);                //释放L2表的头节点
 5 r2->next = q;                //组成循环链表
 6 
 7 //双向链表
 8 //定义双向链表节点
 9 typedef struct dunode
10 {
11     datatype data;
12     struct dunode *prior, *next;
13 }DulNode, *DulLinkList;
14 //插入操作(设q指向双向链表中某节点,s指向待插入的值为e的新节点,将*s插入*q的前面)
15 s->prior = q->prior;        //(1)
16 q->prior = s;                //(2) (1)(2)的顺序不能改变,否则*q的直接前驱节点指针就会丢掉
17 q->prior->next = s;
18 s->nsxt = q;
19 //删除操作(设q指向双向链表中某节点,删除*q)
20 q->next->prior = q->prior;    //(1)
21 q->prior->next = q->next;    //(2) (1)(2)顺序可以改变
22 free(q);
23 
24 //静态链表
25 //定义数组S
26 #define MAXSIZE 1000
27 typedef struct
28 {
29     datatype data;
30     int next;
31 }SNode;                        //节点类型
32 SNode S[MAXSIZE];
33 int SL, SX;                    //两个头指针变量,SL头指针代表用户的线性表,SX头指针指向空闲节点组成的链表
34 //申请节点空间(向SX空闲链表申请,不能调用系统函数malloc())
35 if(SX != -1)                //当SX为非空时
36 {
37     t = SX;                    //分配的节点地址(下标)存入t中
38     SX = S[SX].next;        //取下一个节点给用户后,SX指针移到下一个节点位置
39 }
40 //回收节点空间(通过该节点的相地址t回收给SX,不能调用系统函数free())
41 s[t].next = SX;
42 SX = t;
View Code

说明:
1.单循环链表
    将单链表最后一个节点的指针域不再为空指针而改成指向头节点,使链表头、尾节点相连,就构成了单循环链表;
    若对单链表常做的操作是在表尾、表头进行的,则可以改变链表的标识方法,即不用头指针h而用一个指向尾节点的
    指针r来标识循环链表,使操作效率提高。
2.双向链表
    每个节点再增加一个指向直接前驱的指针域,这种节点组成的链表称为双向链表。
3.静态链表
    用一维数组来描述线性链表,数组属于静态存储结构,则这种方式下描述的链表称为静态链表。
    指针域记录的是逻辑上相邻的下一个数据元素的相对地址(此结构中即为数组的下标),称为静态指针;由于C语言
    定义的数组没有下标为-1的单元,则空指针用-1表示。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:linux C Obstack

下一篇:redis 源码阅读 数值转字符 longlong2str