数据结构 – 线性表

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

线性表的链式存储结构:

链式存储结构中,每一个元素被称作一个节点,节点分成两部分,分别为数据域和指针域,数据域保存着节点的数据,指针域保存着下一个节点对应的地址。换句话就是,知道一个节点的地址,后面所有节点的地址都能获取到。像这种一个节点保存一个指针的称作为单链表,单链表中,一般有一个头结点,头结点的指针域保存着第一个节点的地址,最后一个节点的指针域则为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代码模拟单链表

发表评论

电子邮件地址不会被公开。 必填项已用*标注