定义
相对于顺序表而言,“勤拿少取”这是对链表最形象的描述。意指,它需要一个结点,就在内存中分配一块内存单元。比顺序表不足的是,链表的每个结点中,需要一个存储单元保存指向下一个结点的地址。
链表的访问需要从第一个结点(或称头结点)开始寻找,(顺序表可以根据下标直接访问)。链表的插入和删除只需对指定位置的结点操作即可。
常见的链表,根据指向下个链表的指针可分为单向链表,双向链表。根据第一个结点是否存储元素可分为带头结点的链表和不带头结点的链表。再根据末尾结点next指针的指向可分为循环链表和非循环链表。
*下面程序以单向带头结点的非循环链表为例。
实现
定义结构
1 2 3 4 5 6
| typedef int LinkType;
typedef struct linkNode { LinkType key; struct linkNode *next; } LNode, *LinkList;
|
定义LinkType类型,使该链表结构适合更多数据类型。每个链表的结点,包含一个值域key和一个指针域next。这里声明两种类型LNode
和LinkList
。以下两行代码是等价的。
1 2
| LNode* node = (LNode*)malloc(sizeof(LNode)); LinkList node = (LinkList)malloc(sizeof(LNode));
|
定义操作
创建头结点
1 2 3 4 5 6 7 8
|
LinkList createHead_link() { LinkList head = (LinkList) malloc(sizeof(LNode)); head->next = NULL; return head; }
|
这里是动态分配一个内存单元存储头结点,也可以参照顺序表中,使用LNode head
,由系统分配内存。^footnote
插入结点
1 2 3 4 5 6 7 8 9
|
void insertFirst_link(LinkList head, LinkType val) { LinkList node = (LinkList) malloc(sizeof(LNode)); node->key = val; node->next = head->next; head->next = node; }
|
在带头结点的链表中,头插法表示每次将结点插入到头结点的后面。在不带头结点的链表中,将待插入的结点放在链表中第一个结点的前面,代替之成为第一个结点。
1 2 3 4 5 6 7 8 9 10 11 12
|
void insertLast_link(LinkList head, LinkType val) { LinkList temp = head; while (temp->next != NULL) temp = temp->next; LinkList node = (LinkList) malloc(sizeof(LNode)); node->key = val; temp->next = node; node->next = NULL; }
|
对于尾插法而言,不区分带头结点和不带头结点的链表。只将待插入的结点插到链表的最后一个位置。因此需要先循环到链表的末尾。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
void insert_link(LinkList head, int position, LinkType val) { if (position < 0) insertLast_link(head, val); else if (position == 0) insertFirst_link(head, val); else { LinkList temp = head->next; while (temp != NULL && --position > 0) { temp = temp->next; } LinkList node = (LinkList) malloc(sizeof(LNode)); node->key = val; node->next = temp->next; temp->next = node; } }
|
先根据下标找到待插入的位置,然后插入结点。对比顺序表,先移动指定位置的后续结点,再插入新的结点。
删除结点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
void removeNode_link(LinkList head, int index, LinkType &key) { if (index < 0) { printf("指定下标值不正确\n"); return; } LinkList node = head; int i = 0; while (!node->next || i < index) { node = node->next; i++; } if (i == index) { LinkList temp = node->next; node->next = temp->next; temp->next = NULL; key = temp->key; free(temp); } else { printf("没找到指定下标的值"); } }
|
下标从0开始,表示头结点后的第一个结点。先找到待删除的结点,取出key值,再删除该结点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
void removeNode_link(LinkList head, LinkType val) { LinkList node = head; while (!node->next) { if (node->next->key == val) break; node = node->next; } if (node->next != NULL) { LinkList temp = node->next; node->next = temp->next; temp->next = NULL; free(temp); } else { printf("没找到要删除的节点\n"); } }
|
首先根据val值,找到待删除的结点,最后删除之。
销毁链表
1 2 3 4 5 6 7 8 9 10
|
void destory_link(LinkList head) { while (head->next != NULL) { LinkList node = head->next; head->next = node->next; free(node); } }
|
释放掉除头结点之外的所有结点占用的内存。
最后附上,头文件的定义
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
|
#ifndef LINKLIST_H_ #define LINKLIST_H_
typedef int LinkType;
typedef struct linkNode { LinkType key; struct linkNode *next; } LNode, *LinkList;
LinkList createHead_link();
void insertFirst_link(LinkList, LinkType);
void insertLast_link(LinkList, LinkType);
void insert_link(LinkList,int, LinkType);
void removeNode_link(LinkList,int,LinkType&);
void removeNode_link(LinkList,LinkType);
void destory_link(LinkList);
#endif
|