链式存储结构的线性表：
除了要存储数据元素的信息外还要存储它的直接后继元素的存储地址。
链式存储结构线性表的定义
链式存储结构的线性表除了要哦存储其本身的信息以外还要存放一个指示其直接后继元素存储地址的指针，我们将存储数据元素信息的域叫做数域，把存储直接后继元素的域叫做指针域。这两部分信息的组合称作线性表的一个结点（Node）。
n个结点链接成一条链表，因为链表中每一个结点只包含一个指针域我们称之为单链表。链表中第一个结点的存储位置叫做头指针。为了方便对链表进行一些操作，我们一般会在单链表的第一个结点前面加上一个结点，即头结点。头结点的数据域可以不存放任何数据，头结点的指针域才能放第一个结点的指针。
头指针&&头结点
头指针
- 头指针是指链表指向第一个结点的指针，若链表有头结点，那么头指针是指向头结点的指针；
- 头指针具有标识作用，所以常用头指针冠以链表的名字；
- 无论链表为不为空，头指针均不为空。头指针是链表的必要元素。
头结点
- 头结点的设立仅仅是为了方便人们操作链表，放在链表第一个元素之前，它的数据域一般没有意义；
- 头结点并不一定是链表必要的元素。
链式存储结构线性表的代码描述
对于单链表，我们可以用C语言中的结构指针来描述：
定义一个链式存储结构的线性表
typedef struct Node
{
int data; //数据域
struct Node *next; //指针域
}Node;
typedef struct Node *inkeList;//定义一个单链表
//结点由存放数据元素的数据域和存放后继元素结点指针的指针域组成
单链表的读取操作
-读取单链表第i个元素
处理思路
- 声明一个指针p指向链表的第一个结点，初始化j = 1；
- 当j < i时，遍历链表，p向后移动，不断指向下一个结点，j++；
- 若到链表末尾p为空，则说明第i结点不存在；
- 否则查找成功，返回结点p的数据
根据以上思路不难写出如下代码：
int getElement(linkedList *l,int i){
int j = 1;
linkedList * p;
p = l -> next; //p指向l的第一个结点
while(p && j < i){
p = p -> next;//p指向下一个结点
j ++;
}
if (!p || j > i){
return -1;//查找失败
}else{
return p -> data;//查找成功
}
}
单链表的插入与删除操作
单链表的插入
先来看下思路
- 声明一个指针p指向链表的第一个结点，初始化j = 1；
- 当j < i时，遍历链表，p向后移动，不断指向下一个结点，j++；
- 若到链表末尾p为空，则说明第i结点不存在；
- 否则查找成功，在系统中生成一个空结点s;
- 将要插入的数据元素赋值给s -> data;
- 单链表的插入标准语句s -> next = p -> next; p -> next = s;
- 返回成功
根据上面的思路不难写出如下代码:
int insertList(linkedList *l,int i,int e){
int j = 1;
linkedList * p,s;
p = *l;
while(p && j < i){
p = p -> next;//p指向下一个结点
j ++;
}
if (!p || j > i){
return -1;//插入失败
}else{
s = (linkedList)malloc(sizeof(Node));//生成一个新的结点
s -> data = e;
s -> next = p -> next;
p -> next = s;
return 0;//插入成功
}
}
删除操作也是很简单的
同样我们看下删除操作的思路：
- 声明一个指针p指向链表的第一个结点，初始化j = 1；
- 当j < i时，遍历链表，p向后移动，不断指向下一个结点，j++；
- 若到链表末尾p为空，则说明第i结点不存在；
- 否则查找成功，将将要删除的结点p -> next赋值给q;
- 单链表的删除标准语句p -> next = q -> next;
- 释放q结点
- 返回成功
同样不难写出如下代码：
int deleteList(linkedList *l,int i){
int j = 1;
linkedList * p,q;
p = *l;
while(p && j < i){
p = p -> next;//p指向下一个结点
j ++;
}
if (!(p -> next) || j > i){
return -1;//删除失败
}else{
q = p -> next;
p -> next = q -> next;
free(q);
return 0;//删除成功
}
}
