数据结构

表

Def

线性表是具有n个相同数据类型的有序序列，其中n为表长，当n=0时，称之为空表。

相关概念

前驱元

除第一个元素外，其他任何元素都有唯一前驱，即A[i-1]为A[i]的前驱元。

后驱元

除最后一个元素外，每个元素都有唯一后驱，即A[i+1]为A[i]的后驱元。

基本操作

初始化表，销毁表，插入元素，删除元素，按位查找，按值查找，输出表，表判空，求表长等操作。

顺序表

Def

用顺序存储的方式实现线性表的存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

相关操作

存储结构（数组）

struct Node{
	ElemType data[N];
	int length;
}SqList;

初始化表

void InitList( SqList &L ){
	for( int i = 0 ; i < N ; i++ ) data[i] = 0;
	L.length = 0;
}

插入元素

bool ListInsert( SqList &L, int pos, int num ){
    if( pos == 0 || pos > L.lenghth+1 || L.length >= MAXN ) return FALSE;
    
	for( int i = L.length() ; i >= pos ; i-- ){
        L.data[i] = L.data[pos-1];
    }
    L.data[pos-1] = num;
    L.length++;
    
    return TRUE;
}

删除元素并返回删除元素

bool DeteleList( SqList &L, int pos, int &e ){
    if( pos > L.length || pos == 0 ) return FALSE;
    e = data[pos-1];
    for( int i = pos-1 ; i <= L.length ; i++ ){
        data[pos] = data[pos];
    }
    L.length--;
    return TRUE;
}

按位查找

int GetElem( SqList L, int pos ){
    return data[pos-1];
}

按值查找

int LocateElem( SqList L, int num ){
    for( int i = 0 ; i < L.length ; i++ ){
        if( data[i] == num ) return i+1;
    }
    return 0;
}

链表

Def

链表由一系列不必再内存中相连的结构组成，每一个结构均含有元素和只想包含该元素后继元的结构的指针。

相关操作

单链表存储结构

typedef struct Node{
    Elemtype Element;
    struct Node *next;
}LNode,*LinkList;//LNode->强调是个结点，LinkList强调是个链表

初始化链表

//带头节点
bool InitList( LinkList &L){
	L = (LNode*)malloc(sizeof(LNode));
	if( L == NULL ) return FALSE;
	L->next = NULL;
	return TRUE;
}
/*
bool InitList( LinkList &L ){
	L = NULL;
	return TRUE;
}
*/

按位序插入

bool InertList( LinkList &L, int pos, int num ){
    if( pos < 1 ) return FALSE;
    LNode *p;
    int j = 0;
    p = L;
    while( p->next != NULL && j < pos-1 ){
        p = p->next;
        j++;
    }
    if( p == NULL )	return FALSE;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = num;
    s->next = p->next;
    p->next = s;
    return TRUE;
}
/*
不带头节点的按位序插入
bool InsertList( LinkList &L, int pos, int num ){
	if( pos == 0 ) return FALSE;
	if( pos == 1 ){
		LNode *s;
		s = (LNode *)malloc(sizeof(LNode));
		s->data = num;
		s->next = L;
		L = s;
		return TRUE;
	}
	LNode *p;
	p = L;
	int j = 0;
	while( p != NULL && j < pos-1 ) { p=p->next;j++; }
	if( p == NULL ) return TRUE;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = num;
	s = p->next;
	p->next = s;
	return TRUE;
}
*/

按位序删除并返回值

bool ListDete( LinkList &L, int pos, int &e ){
	if( pos == 0 ) return FALSE;
    LNode *p;
    p = L;
   	int j = pos;
    while( p->next != NULL && j < pos-1 ){ p = p->next; j++; }
    if( p == NULL ) return FALSE;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return TRUE;
}

指定结点后插

bool InertNextNode( LNode *p, ElemType e ){
    if( p == NULL ) return FALSE;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if( s == NULL ) return FALSE;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return TRUE;
}

指定节点前插(p变s，s变p)

bool InertPriorNode( LNode *p, LNode *s){
    if( p == NULL || s == NULL) return FALSE;
    s->next = p->next;
    p->next = s;
    ElemType temp = p->data;
    p->data = s->data;
    s->data = temp;
    return TRUE;
}

指定节点删除

bool DeleteNode( LNode *p ){
	if( p == NULL ) return FALSE;
    LNode *q = p->next;
    p->data = p->next->data;
    p->next = q->next;
    free(q);
    return TRUE;
}

按位查找O(n)

LNode *GetElem( LinkList &L, int pos ){
	if( pos < 0 ) return NULL;
	LNode *p;
	int j = 0;
	p = L;
	while( p != NULL && j < i ){
		p = p->next;
		j++;
	}
	return p;
}

按值查找O(n);

LNode *LocateElem( LinkList L, ElemType e ){
    LNode *p = L->next;
    while( p != NULL && p->data != e ){
        p = p->next;
    }
    return p;
}

求表长

int length( LinkList L ){
	int len = 0;
	LNode *p = L;
	while( p->next != NULL ){
		p = p->next;
		len++;
	}
	return len;
}

尾插法

LinkList List_TailInsert( LinkList &L ){
	int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r = L;
    scanf("%d",&x);
    while( x != END ){
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d",&x);
    }//END 自定义终止
    r->next = NULL;//尾结点为空
    return L;
}

头插法

LinkList List_headInsert( LinkList &L ){
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d",&x);
    while( x != END ){
        s = (LNode)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}
//可以实现链表的逆置

双链表

优势

对比单链表，可以得知前后结点，存储密度更低。

相关操作

代码定义

Typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinkList;

初始化双链表

bool InitDLinkList( DLinkList &L ){
    L = (DNode *)malloc( sizeof(DNode));
    if( L == NULL ) return FALSE;
    L->prior = NULL; // 头结点永远指向NULL
    L->next = NULL;
    return TRUE;
}

插入

bool InsertNextDNode( DNode *p, DNode *s ){
    if( p == NULL && s == NULL ) return FALSE;
    s->next = p->next;
    if( p->next != NULL ) 
        	p->next->prior = s;
    s->prior = p;
    p->next = s;
    return TRUE;
}

删除后继节点

void DeleteNextDNode( DNode *p ){
    if( p == NULL ) return FALSE;
    DNode *q = p->next;
    if( q == NULL ) return FALSE;
    p->next = q->next;
    if( q->next != NULL ) 
        	q->next->prior = p;
   	free(q);
    return TRUE;
}

删除双链表

void DesrtoryList( DLinkList &L ){
    while( L->next != NULL ) DeleteNextDNode(L);
    free(L);//释放头结点
    L = NULL;//头指针指向空
}

遍历

//后向遍历
while( p != NULL ){
    p = p->next;
}
//前向遍历
while( p != NULL ){
    p = p->prior;
}
//前向遍历跳过头节点
while( p->prior != NULL ) p = p->prior;