《数据结构中链表及常见操作》由会员分享，可在线阅读，更多相关《数据结构中链表及常见操作（11页珍藏版）》请在金锄头文库上搜索。
1、链表1 定义链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间，而顺序表相应的时间复杂度分别是 O(logn)和 O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。在计算机科学中
2、，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向明上一个或下一个节点的位置的链接（links） 。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接） 。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。2 结构2.1 单向链表链表中最简单的一种是单向链表，它包含两个
3、域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。2.2 双向链表每个节点有两个连接：一个指向前一个节点， （当此“连接”为第一个“连接”时，指向空值或者空列
4、表） ；而另一个指向下一个节点， （当此“连接”为最后一个“连接”时，指向空值或者空列表）双向链表可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。2.3 循环链表在一个循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。指向整个列表的指针可以被称作访问指针。循环链表中第一个节点之前就是最后一个节点，反之亦然。3 链表常见用途常用于组织删除、检索较少，而添加、遍历较多的数据。4 链表和数组的区别数组在内存中是
5、逐个存放的，也就是说倘若数组的第一个元素在地址 A,则数组第 1二个元素就在地址 A+1。而链表则不是，链表每个节点没有相对固定的位置关系。某个节点在地址 A 其后的节点不一定是 A+1,而在内存的其他空闲区域，呈现一种随机的状态。数组一旦显式的被申明后，其大小就固定了，不能动态进行扩充。而链表则可以， 2可以动态生成节点并且添加到已有的链表中。链表灵活，但是空间和时间额外耗费较大；数组大小固定，元素位置固定，但是操 3作不灵活，且容易浪费空间，但是时间耗费较小，尤其是元素变化不大的时候效率很高。双向链表比单向的更灵活，但是空间耗费也更大。从内存存储来看，(静态 )数组从栈中分配空间, 对于程
6、序员方便快速,但是自由度小； 4链表从堆中分配空间, 自由度大但是申请管理比较麻烦。附录：（链表的部分常见操作）1 单向链表/*线性表的单链表存储结构 */typedef struct LNodeElemType data;struct LNode *next;LNode, *LinkList;/*带有头结点的单链表的基本操作 (12 个 )*/void InitList(LinkList *L) /* 操作结果：构造一个空的线性表 L */*L=(LinkList)malloc(sizeof(struct LNode); /* 产生头结点，并使 L 指向此头结点 */if(!*L) /* 存
7、储分配失败 */exit(OVERFLOW);(*L)-next=NULL; /* 指针域为空 */void DestroyList(LinkList *L) /* 初始條件：线性表 L 已存在。操作结果：销毁线性表 L */LinkList q;while(*L)q=(*L)-next;free(*L);*L=q;void ClearList(LinkList L) /* 不改变 L */ /* 初始条件：线性表 L 已存在。操作结果：将 L 重置为空表 */LinkList p,q;p=L-next; /* p 指向第一个结点 */while(p) /* 没到表尾 */q=p-next;f
8、ree(p);p=q;L-next=NULL; /* 头结点指针域为空 */Status ListEmpty(LinkList L) /* 初始条件：线性表 L 已存在。操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */return L-next = NULL;int ListLength(LinkList L) /* 初始条件：线性表 L 已存在。操作结果：返回 L 中数据元素个数 */int i=0;LinkList p=L-next; /* p 指向第一个结点 */while(p) /* 没到表尾 */i+;p=p-next;return i;Status GetEl
9、em(LinkList L,int i,ElemType *e) /* L 为带头结点的单链表的头指针。当第 i 个元素存在时，其值赋给 e 并返回OK，否则返回 ERROR */int j=1; /* j 为计数器 */LinkList p=L-next; /* p 指向第一个结点 */while(p&j next;j+;if(!p|ji) /* 第 i 个元素不存在 */return ERROR;*e=p-data; /* 取第 i 个元素 */return OK;int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,
10、ElemType) /* 初始条件 : 线性表 L 已存在， compare()是数据元素判定函数 (满足为 1，否则为 0) */* 操作结果 : 返回 L 中第 1 个与 e 满足关系 compare()的数据元素的位序。 */* 若这样的数据元素不存在，则返回值为 0 */int i=0;LinkList p=L-next;while(p)i+;if(compare(p-data,e) /* 找到这样的数据元素 */ return i;p=p-next;return 0;Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
11、 /* 初始条件 : 线性表 L 已存在 */* 操作结果 : 若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱， */* 返回 OK；否则操作失败， pre_e 无定义，返回 INFEASIBLE */LinkList q,p=L-next; /* p 指向第一个结点 */while(p-next) /* p 所指结点有后继 */q=p-next; /* q 为 p 的后继 */if(q-data=cur_e)*pre_e=p-data;return OK;p=q; /* p 向后移 */return INFEASIBLE;Status NextElem(Li
12、nkList L,ElemType cur_e,ElemType *next_e) /* 初始条件：线性表 L 已存在 */* 操作结果：若 cur_e 是 L 的数据元素，且不是最后一个，则用 next_e 返回它的后继， */* 返回 OK;否则操作失败， next_e 无定义，返回 INFEASIBLE */LinkList p=L-next; /* p 指向第一个结点 */while(p-next) /* p 所指结点有后继 */if(p-data=cur_e)*next_e=p-next-data;return OK;p=p-next;return INFEASIBLE; Statu
13、s ListInsert(LinkList L,int i,ElemType e) /* 在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e */int j=0;LinkList p=L,s;while(p&j next;j+;if(!p|ji-1) /* i 小于 1 或者大于表长 */return ERROR;s=(LinkList)malloc(sizeof(struct LNode); /* 生成新结点 */s-data=e; /* 插入 L 中 */s-next=p-next;p-next=s;return OK;Status ListDelete(LinkList L,i
14、nt i,ElemType *e) /* 在带头结点的单链线性表 L 中，删除第 i 个元素，并由 e 返回其值 */int j=0;LinkList p=L,q;while(p-next&jnext;j+;if(!p-next|ji-1) /* 删除位置不合理 */return ERROR;q=p-next; /* 删除并释放结点 */p-next=q-next;*e=q-data;free(q);return OK;void ListTraverse(LinkList L,void(*vi)(ElemType)/* vi 的形参类型为 ElemType，与 bo2-1.c 中相应函数的形参
15、类型ElemType&不同 */ /* 初始条件：线性表 L 已存在。操作结果：依次对 L 的每个数据元素调用函数vi() */LinkList p=L-next;while(p) vi(p-data);p=p-next;printf(n);2 双向链表/* 线性表的双向链表存储结构 */typedef struct DuLNodeElemType data;struct DuLNode *prior,*next;DuLNode,*DuLinkList;/*带头结点的双向循环链表的基本操作*/void InitList(DuLinkList *L) /* 产生空的双向循环链表 L */*L=(DuLinkList)malloc(sizeof(DuLNode);if(*L)(*L)-next=(*L)-prior=*L;elseexit(OVERFLOW);void DestroyList(DuLinkList *L) /* 操作结果：销毁双向循环链表 L */DuLinkList q,p=(*L)-next; /* p 指向第一个结点 */while(p!=*L) /* p 没到表头 */q=p-next;free(p);p=q;free(*L);*L=NULL;void ClearList(DuLinkLi
