数据结构 – 栈的链式存储结构

同单链表类似,每一个节点都有指向下一个节点的指针域,但是不同于单链表的是,栈只能是top(栈顶)位置的元素在变化, 换句话说,栈的插入和删除都是针对固定的位置,不像单链表,只要位置合理,可以是任意的位置。所以栈的操作,不管是顺序结构还是链式结构,相对来说都简单很多。

定义
typedef struct StackStruct{
    ElemType e;
    SSLP next;
}SSL,*SSLP;

typedef struct LinkList{
    SSLP top;  
}
 插入和删除

和顺序栈不同,这里的top不再是游标,可以理解成一个对象。插入只需将新的结点赋值给top,再讲新节点的next指向原来的top

s->next = S->top;
 S->top = s;

删除也类似,将top指向的结点弹出,top的next变成新的top

S->top = S->top->next

栈的链式存储结构-php代码模拟

 

数据结构 – 栈的顺序存储

栈是一种特殊的线性表。栈遵循后入先出的原则,也就是说,栈只允许在栈顶一段对数据进行操作。

栈的顺序存储

同线性表的顺序存储类似,不过有一个游标去控制数据的插入和删除。先看看定义

typedef struct stack{
    elemType e;
    int top;
 }stack;

顺序栈的插入

Status SLinkListPush(SLinkList *s, SElemType e) {
	if(s->top > MAXSIZE - 1) return ERROR
	s->top++;
	s->data[s->top] = e;
	return OK;
}

顺序栈的弹出

Status SLinkListPop(SLinkList *s, SElemType *e) {
	if(s->top == -1) return ERROR;
	*e = s->data[s->top];
	s->top--;     
	return OK;                                                
}

由代码看,时间复杂度都是O(1),因为只能对栈顶操作,所以栈相对于线性表,还是要简单点。

两栈共享空间

因为顺序栈是由数组实现。所以在长度上就有限制,如果长度分配不当就会出现溢出的现象,就得重新分配新的内存空间。如果两个栈公用一段内存空间呢?

即用一个数组去表示两个栈,假如数组长度为n,那么栈1为空时,top1 = -1,栈2为空,top2 = n,当top1 +1 == top2就表示栈满了,即数组的空间已经用完了。

定义

typedef struct stack{
    elemType e;
    int top1; 
    int top2; // 多了一个控制栈2的游标
 }stack;

具体:顺序栈即两栈共享空间-php代码模拟

线性表 – 静态链表

有的开发语言并没有指针一说,那么就无法实现单链表,于是有人提出可以用数组的形式去描述单链表,称之为静态链表

同单链表的节点类似,数组的每一个元素都保存了两个值,数据和游标,游标类似于指针,其值是后继元素的下标。

静态链表的下标并不像普通数组那样代表顺序,而是每一个元素的cursor代表着顺序,比如要找到第二个元素,并不是下标为2的元素,而是第一个元素的cursor,这个cursor代表着第二个元素的下标值。

既然是数组,那么在分配内存的时候,内存大小是会大于数组大小的,为了防止数组的溢出,所以在静态链表中,有备用链表这么一说,没有保存数据的元素就是备用链表的一员。

同单链表一样,静态链表的第一个和最后一个元素也有着特殊意义,第一个元素的cursor指向的是备用链表的第一个元素的下标值,最后一个元素的cursor指向的是第一个有值的元素的下标。

单链表的定义
typedef struct StaticLinkList{
    ElemType e;
    int cur;
}StaticLinkList

单链表的插入

插入之前,要先做一件事,这个新插入的元素我们把它放在备用链表的第一个元素上,然后链表第一个元素的cursor指向后一个元素下标

int molloc_lls(StaticLinkList L) {
    k = L[0].cursor;
    if(k) {
         L[0].cursor = L[k].cursor;
         return k;
    }
    return 0;
}

下面实现插入的逻辑:

Status listInsert(StaticLinkList L, int i, ElemType e) {
    // 先找到i之前那个元素的下标, k指向第i个之前元素的下标
    k = MAXSIZE - 1;
    for(int j = 0;j < i -1;j++) {
         k = L[k].cursor;
    }
    // i之后元素的下标值
    next = L[k].cursor;
    m = mollac_lls(L);
    L[m].data = e;
    L[m].cursor = next;
    L[k].cursor = m;
    return Ok 
}

静态链表的php模拟

 

数据结构 – 线性表

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

线性表的链式存储结构:

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