第三节 链式存储结构的线性表
把线性表的数据元素存放在非连续的存储单元里，并通过指针把这些存储单元链接起来，用这种方法存储的线性表简称链表。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点至少包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
为了编程的方便，在构建链表时，采用带头结点的双向循环链表最为简单。结构如下图所示。
图中，有2种类型的结点：数据结点和链表结点。观察其中的成员，并为它们定义合适的数据类型，从而定义出链表类型。
在链表操作中，元素的位置使用指针来表示，而不是链表中的下标。
LinkedList.h （链表类型的定义、以及操作的声明）
#ifndef __LINKEDLIST_H__
#define __LINKEDLIST_H__
typedef int ElementType; /* 假设数据元素的类型为整型 */
typedef struct LinkedListNode { /* 链表结点类型定义 */
struct LinkedListNode *prior; /* 前驱指针 */
struct LinkedListNode *next; /* 后继指针 */
ElementType data; /* 数据域 */
} LinkedListNode;
typedef struct LinkedList { /* 链表类型定义 */
LinkedListNode header; /* 头结点 */
int length; /* 链表长度 */
LinkedListNode *iterator; /* 访问链表的迭代器，用于遍历链表 */
} LinkedList;
/* 初始化一个链表 */
/* 成功返回0，失败返回-1 */
int initLinkedeList(LinkedList *list);
/* 获取链表的长度 */
int getLinkedListLength(const LinkedList *list);
/* 判断链表是否为空 */
/* 空则返回true/1，非空返回false/0 */
int isLinkedListEmpty(const LinkedList *list);
/* 往链表中的指定位置插入元素 */
/* 成功则返回新的长度，失败返回-1 */
int insertLinkedListAt(LinkedList *list, int pos, ElementType e);
/* 删除链表中的指定位置元素，被删除的元素通过形参传出 */
/* 成功则返回新的长度，失败返回-1 */
int removeLinkedListAt(LinkedList *list, int pos, ElementType *e);
/* 查找链表中元素是否存在 */
/* 成功则返回0，失败返回-1 */
/* 注意：千万不要在此函数中用printf()函数输出“找到了”“未找到”此类的信息，保证函数功能的单一 */
int findLinkedListElement(const LinkedList *list, ElementType e);
/* 获取链表中的指定位置元素，通过形参传出 */
/* 成功则返回0，失败返回-1 */
int getLinkedListAt(const LinkedList *list, int pos, ElementType *e);
/* 修改链表中的指定位置元素 */
/* 成功则返回0，失败返回-1 */
int setLinkedListAt(LinkedList *list, int pos, ElementType e);
/* 销毁链表 */
void destroyLinkedList(LinkedList *list);
/* 补充几个迭代器的相关操作，以正向迭代为例 */
/* 1.启动迭代器 */
void startIterator(LinkedList *list);
/* 2.判断迭代是否完毕 */
/* 未迭代完，则返回true/1，否则返回false/0 */
int hasNextLinkedList(LinkedList *list);
/* 3. 往前迭代，得到下一个结点的元素 */
void stepNextLinkedList(LinkedList *list, ElementType *e);
#endif在实现上述操作前，回顾一下指针的基本操作。
首先，是结点的分配与删除。针对本章节开始的链表示意图，说明如下。
对于上图红框对应的链表结构体，可以采用定义链表类型的变量来生成静态的链表结构体。
LinkedList list1;对于上图中黄框对应的数据元素结构体，则需要动态分配内存的方式来生成。
LinkedListNode *p = (LinkedListNode *)malloc(sizeof(LinkedListNode));其次，双向链表中，结点的插入与删除操作。在指针p指向的结点之后，插入指针s所指向的结点，需要如下4个步骤：
删除指针p所指向的结点，需要如下步骤：
LinkedList.c （链表操作的定义）
#include <stdlib.h> /* for malloc(), free() */
#include “LinkedList.h”
/* 初始化一个容量为n的链表 */
/* 成功返回0，失败返回-1 */
int initLinkedList(LinkedList *list)
{
/**
初始化成员变量
*/
return 0;
}
/* 获取链表的长度 */
int getLinkedListLength(const LinkedList *list)
{
return 0;
}
/* 判断链表是否为空 */
/* 空则返回true/1，非空返回false/0 */
int isLinkedListEmpty(const LinkedList *list)
{
return 0;
}
/* 往链表中的指定位置插入元素，为了与顺序表的位置一致，有效位置从0开始 */
/* 成功则返回新的长度，失败返回-1 */
int insertLinkedListAt(LinkedList *list, int pos, ElementType e)
{
/**
定位到pos位序对应的前驱结点
生成一个新结点，存储元素e，并插入链表中
更新链表长度
*/
return 0;
}
/* 删除链表中的指定位置元素，被删除的元素通过形参传出 */
/* 成功则返回新的长度，失败返回-1 */
int removeLinkedListAt(LinkedList *list, int pos, ElementType *e)
{
/**
定位到pos位序对应的结点，用指针p来指向
*e = p->data
删除p指向的结点
更新链表长度
*/
return 0;
}
/* 定位链表中元素的位置。内部函数，供查找元素使用 */
/* 成功则返回第一次出现的位置，失败返回NULL */
/* 注意：千万不要在此函数中用printf()函数输出“找到了”“未找到”此类的信息，保证函数功能的单一 */
LinkedListNode* locateLinkedListElement(const LinkedList *list, ElementType e)
{
return NULL;
}
/* 查找链表中元素是否存在 */
/* 成功则返回0，失败返回-1 */
/* 注意：千万不要在此函数中用printf()函数输出“找到了”“未找到”此类的信息，保证函数功能的单一 */
int findLinkedListElement(const LinkedList *list, ElementType e)
{
return 0;
}
/* 获取链表中的指定位置元素，通过形参传出 */
/* 成功则返回0，失败返回-1 */
int getLinkedListAt(const LinkedList *list, int pos, ElementType *e)
{
return 0;
}
/* 修改链表中的指定位置元素 */
/* 成功则返回0，失败返回-1 */
int setLinkedListAt(LinkedList *list, int pos, ElementType e)
{
return 0;
}
/* 销毁链表 */
void destroyLinkedList(LinkedList *list)
{
}
/* 补充几个迭代器的相关操作，以正向迭代为例 */
/* 1.启动迭代器 */
void startIterator(LinkedList *list)
{
}
/* 2.判断迭代是否完毕 */
/* 未迭代完，则返回true/1，否则返回false/0 */
int hasNextLinkedList(LinkedList *list)
{
return 0;
}
/* 3. 往前迭代，得到下一个结点的元素 */
void stepNextLinkedList(LinkedList *list, ElementType *e)
{
}
按第一章介绍的三层结构，链表的定义放在访问层，表示层和业务层主要体现在main()函数中。
#include <stdio.h>
#include “LinkedList.h” /* 引入链表 */
/* 以下是业务相关代码 */
int main()
{
int i;
LinkedList list1, list2; /* 定义了2个链表 */
ElementType e;
/* 初始化链表 */
initLinkedList(&list1); /* */
initLinkedList(&list2); /* */
for (i=0; i<10; i++) {
insertLinkedListAt(&list1, i, i);
insertLinkedListAt(&list2, 0, 2*i);
}
printf(“find 10 in list2: ”);
i = findLinkedListElement(&list2, 10);
if (i == -1) {
printf(“NOT Found!\n”);
}
else {
printf(“Found\n”);
}
printf(“list1[len=%d]: ”, getLinkedListLength(&list1));
/* 遍历链表 */
for (startIterator(&list1); hasNextLinkedList(&list1); ) {
stepNextLinkedList(&list1, &e);
printf(“%d ”, e);
}
printf(“\n”);
printf(“Remove list2: ”);
while(!isLinkedListEmpty(&list2)) {
removeLinkedListAt(&list2, 0, &e);
printf(“%d ”, e);
}
printf(“\n”);
/* 销毁2个链表，释放资源 */
destroyLinkedList(&list1);
destroyLinkedList(&list2);
return 0;
}
【思考：应用中同时用到2个链表，它们的元素类型不一样，怎么办？】
总结：顺序表与链表的优缺点对比
它们的主要特点【由讯飞星火生成】：
· 顺序表：
o 优点：
o 尾插效率高，便于随机访问；
o CPU缓存利用率高；
o 存取速度高效，通过下标来直接存储。
o 缺点：
o 不利于插入和删除操作；
o 不可以增长长度。
· 链表：
o 优点：
o 物理存储单元上非连续，而且采用动态内存分配，能够有效的分配和利用内存资源；
o 节点删除和插入简单，不需要内存空间的重组。
o 缺点：
o 不能进行索引访问，只能从头结点开始顺序查找；
o 数据结构较为复杂，需要大量的指针操作，容易出错。
补充：指针的认识。
int a=10;
int *p = &a;
printf(“%d 0x%x\n”, a, &a);
printf(“%d 0x%x 0x%x\n”, *p, p, &p);指向结构体的指针
typedef struct Stu {
char name[20];
int score;
} Stu;
Stu s1 = {“Zhangsan”, 80};
Stu *p = &s1;
printf(“%s : %d\n”, s1.name, s1.score);
printf(“%s : %d\n”, (*p).name, (*p).score);
printf(“%s : %d\n”, p->name, p->score);