数据结构 – 线性表

线性表是一种常见的数据结构，逻辑结构的层面上，它代表着一串前后相连，有顺序的数据，在物理结构上，它又有多种表现形式，比如常见的数组就是线性表的顺序存储结构。

线性表的链式存储结构:

链式存储结构中，每一个元素被称作一个节点，节点分成两部分，分别为数据域和指针域，数据域保存着节点的数据，指针域保存着下一个节点对应的地址。换句话就是，知道一个节点的地址，后面所有节点的地址都能获取到。像这种一个节点保存一个指针的称作为单链表，单链表中，一般有一个头结点，头结点的指针域保存着第一个节点的地址，最后一个节点的指针域则为null。单链表的定义如下:

#define MAZSIZE 20
 typedef int ElemType;
 typedef struct Node{
    ElemType data[MAXSIZE];
    Node *next;
 }Node,*LinkList;

单链表的插入: 

单链表的插入过程相对于顺序存储结构简单了很多，比如在i位置插入一个元素，只需要在内存中随机分配一块保存新节点的数据，然后将i前一个元素的指针指向新分配的地址，再将新节点的指针域指向第i个元素的地址

 $new->next = $p->next;
  $p->next = $new;

 代码实现：

// 单链表的插入
/*
 * 1. 声明一点p代表链表的第一个节点，开始遍历，累加初始遍历j
 * 2. 如果到链表的结尾，还没有累加到i，则说明i位置不存在
 * 3. 找到i位置，新建节点s，s->data=e;
 * 4. 前后节点的地址变化
 */
Status ListInsert(LinkList L, int i ,Elem e) {
	L = LinkList->next;
	j = 1;
	while(L && j < i) {
		L = L->next;
		j++;
	}
	if(!L || j > i) 
		return ERROR;
	LinkList s;
	s = (LinkList) malloc (sizeof( Node ));
	s->data = e;
	s->next = L->next;
	L->next = s;
	return OK;
}


// 单链表的删除
/*
 * 1. 声明一点p代表链表的第一个节点，开始遍历，累加初始遍历j
 * 2. 如果到链表的结尾，还没有累加到i，则说明i位置不存在
 * 3. 找到i位置，前后节点的地址变化
 */
 Status NodeDelete(LinkList L, int i ,Elem *e) {
 int j = 1;
 L = L->next;
 while (L && j < (i-1)) {
 L = L->next;
 j++;
 }
 if(!L || ++j > i) 
 return ERROR;
 q = L->next;
 p = q->next;
 L->next = p;
 *e = q->data;
 free(q);
 return OK;
 }

PHP代码模拟单链表