前言

数据结构可以说是学习算法的前提，我将在寒假前后更新完数据结构相关的内容，同时会更新一些简单的算法，我学习的是mooc上浙大的数据结构

线性表及其实现

线性表定义

“线性表(Linear List)”：由同类型数据元素构成有序序列的线性结构

表中元素个数称为线性表的长度；线性表没有元素时，称为空表；表起始位置称表头，表结束位置称表尾

对线性表的操作

1、List MakeEmpty() 初始化一个空线性表L

2、ElementType FindKth( int K, List L ) 根据位序K，返回相应元素

3、int Find( ElementType X, List L ) 在线性表L中查找X的第一次出现位置

4、void Insert( ElementType X, int i, List L) 在位序i前插入一个新元素X

5、void Delete( int i, List L ) 删除指定位序i的元素；

6、int Length( List L ) 返回线性表L的长度n

线性表的顺序存储实现

建立空的顺序表

1
2
3
4
5
6
List MakeEmpty( ){
    List PtrL;
	PtrL = (List )malloc( sizeof(struct LNode) );
 	PtrL->Last = -1; 
	return PtrL;
}

查找

1
2
3
4
5
6
7
int Find( ElementType X, List PtrL ){
    int i = 0;
 	while( i <= PtrL->Last && PtrL->Data[i]!= X )
 	i++;
 	if (i > PtrL->Last) return -1; /* 如果没找到，返回-1 */
 	else return i; /* 找到后返回的是存储位置 */ 
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Insert( ElementType X, int i, List PtrL ){
    int j;
 	if ( PtrL->Last == MAXSIZE-1 ){ /* 表空间已满，不能插入*/
 	printf(＂表满＂); 
 	return; 
 }
 	if ( i < 1 || i > PtrL->Last+2) { /*检查插入位置的合法性*/
 	printf(＂位置不合法＂);
 	return; 
 }
 	for ( j = PtrL->Last; j >= i-1; j-- )
 	PtrL->Data[j+1] = PtrL->Data[j]; /*将 ai～ an倒序向后移动*/
 	PtrL->Data[i-1] = X; /*新元素插入*/
 	PtrL->Last++; /*Last仍指向最后元素*/
 	return; 
}

删除

1
2
3
4
5
6
7
8
9
10
11
void Delete( int i, List PtrL ){ 
    int j;
 	if( i < 1 || i > PtrL->Last+1 ) { /*检查空表及删除位置的合法性*/
 	printf (“不存在第%d个元素”, i ); 
 	return ; 
 }
 	for ( j = i; j <= PtrL->Last; j++ )
 	PtrL->Data[j-1] = PtrL->Data[j]; /*将 ai+1～ an顺序向前移动*/
 	PtrL->Last--; /*Last仍指向最后元素*/
 	return; 
}

线性表的链式存储实现

定义结构类型

1
2
3
4
5
6
7
typedef struct LNode *List;
struct LNode{ 
 ElementType Data; 
 List Next;
}; 
struct Lnode L;
List PtrL;

求表长

1
2
3
4
5
6
7
8
9
int Length ( List PtrL ){ 
    List p = PtrL; /* p指向表的第一个结点*/
 	int j = 0;
 	while ( p ) { 
 	p = p->Next; 
 	j++; /* 当前p指向的是第 j 个结点*/
 } 
 	return j;
}

查找

（1）按序号查找: FindKth

1
2
3
4
5
6
7
8
9
10
11
12
List FindKth( int K, List PtrL ){ 
    List p = PtrL;
 	int i = 1;
 	while (p !=NULL && i < K ){
 	p = p->Next;
 	i++; 
 }
 	if ( i == K ) return p; 
 	/* 找到第K个，返回指针 */
 	else return NULL; 
 	/* 否则返回空 */
}

（2）按值查找: Find(更常用)

1
2
3
4
5
6
List Find( ElementType X, List PtrL ){ 
 	List p = PtrL;
 	while ( p!=NULL && p->Data != X )
 	p = p->Next; 
 	return p;
}

插入

先做s->Next = p->Next，后做p->Next = s，不要写反了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
List Insert( ElementType X, int i, List PtrL ){ 
    List p, s;
 	if ( i == 1 ) { /* 新结点插入在表头 */
 	s = (List)malloc(sizeof(struct LNode)); /*申请、填装结点*/
 	s->Data = X; 
 	s->Next = PtrL;
 	return s; /*返回新表头指针*/
 }
 	p = FindKth( i-1, PtrL ); /* 查找第i-1个结点 */
 	if ( p == NULL ) { /* 第i-1个不存在，不能插入 */
 	printf(＂参数i错＂);
 	return NULL; 
 }else {
 	s = (List)malloc(sizeof(struct LNode)); /*申请、填装结点*/
 	s->Data = X; 
 	s->Next = p->Next; /*新结点插入在第i-1个结点的后面*/
 	p->Next = s; 
 	return PtrL;
 }

删除

malloc后肯定要free了，下面三个步骤最关键

1
2
3
s = p->Next; /*s指向第i个结点*/
p->Next = s->Next; /*从链表中删除*/
free(s); /*释放被删除结点 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
List Delete( int i, List PtrL ){ 
    List p, s;
 	if ( i == 1 ) { /* 若要删除的是表的第一个结点 */
 	s = PtrL; /*s指向第1个结点*/
 	if (PtrL!=NULL) PtrL = PtrL->Next; /*从链表中删除*/
 	else return NULL;
 	free(s); /*释放被删除结点 */
 	return PtrL;
 }
 	p = FindKth( i-1, PtrL ); /*查找第i-1个结点*/
 	if ( p == NULL ) { 
 	printf(“第%d个结点不存在”, i-1); return NULL; 
 } else if ( p->Next == NULL ){ 
 	printf(“第%d个结点不存在”, i); return NULL; 
 } else {
 	s = p->Next; /*s指向第i个结点*/
 	p->Next = s->Next; /*从链表中删除*/
 	free(s); /*释放被删除结点 */
 	return PtrL;
 }

广义表

广义表是线性表的推广；对于线性表而言， n个元素都是基本的单元素；广义表中，这些元素不仅可以是单元素也可以是另一个广义表

1
2
3
4
5
6
7
typedef struct GNode *GList;
struct GNode{
 int Tag; /*标志域：0表示结点是单元素，1表示结点是广义表 */
 union { /*子表指针域Sublist与单元素数据域Data复用（union类型），即共用存储空间*/
 ElementType Data;
 GList SubList; 
 } URegion;

多重链表

广义表就是多重链表的一种

多重链表中结点的指针域会有多个，如前面例子包含了Next和SubList两个指针域

但包含两个指针域的链表并不一定是多重链表，比如在双向链表不是多重链表

多重链表有广泛的用途： 基本上如树、图这样相对复杂的数据结构都可以采 用多重链表方式实现存储