数据结构笔记(2)--线性表

发表于

线性表

线性表是最常用且最简单的一种数据结构。在稍复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称文件。

线性表是一个相当灵活的数据结构，它的长度可以根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除等。

线性链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

/*************线性链表***********/
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList; //定义别名LinkList，则可以直接LinkList a;

// 按位置查找
Status GetElem_L(LinkList L, int i, ElemType &e){
	// L为带头结点的单链表的头指针
	// 当第i个元素存在时，其值赋给e并返回ok，否则返回error
	p = L->next;
	j = 1;
	while(p && j<i){
		p = p->next;
		j++;
	}
	if(!p || j>i) return ERROR;
	e = p->data;
	return OK;
}

// 在第i个位置前插入e
Status ListInsert_L(LinkList &L, int i, ElemType e){
	p = L;
	j = 0;
	while(p && j<i-1){
		p = p->next;
		j++;
	}
	if(!p && j>i-1) return ERROR;
	s = (LinkList) malloc(sizeof(LNode)); //生成新结点
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

// 删除元素
Status ListDelete_L(LinkList &L, int i, ElemType e){
	p = L;
	j = 0;
	while(p->next && j<i-1){
		p = p->next;
		j++;
	}
	if(!(p->next) || j>i-1) return ERROR;
	q = p->next;
	p->next = q->next;
	e = q->data;
	return OK;
}


// 从表尾到表头逆向建立单链表
void CreatList_L(LinkList &L, int n){
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	for (i=n; i>0; i--){
		p = (LinkList)malloc(sizeof(LNode));
		scanf(&p->data);
		p->next = L->next;
		L->next = p;
	}
}

// 合并有序链表
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){
	pa = La->next;
	pb = Lb->next;
	Lc = pc = La;
	while(pa && pb){
		if(pa->data <= pb->data){
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else{
			pc-next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa?pa:pb;
	free(Lb);
}

静态链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

/**************静态链表**************/
// 借用一维数组来描述线性链表，称为静态链表
// 需预先分配空间，插入删除方便(仅需修改指针)

#define MAXSIZE 1000 //链表最大长度
typedef struct{
	ElemType data;
	int cur;
}component, SLinkList[MAXSIZE];

// 定位函数实现
int LocateElem_SL(SLinkList S, ElemType e){
	// 在静态单链线性表L中查找第1个值为e的元素
	// 若找到，则返回其在L中的次序，否则返回0.
	i = S[0].cur;
	while(i && S[i].data!=e){
		i = S[i].cur;
	}
	return i;
}

// 集合运算(A-B)U(B-A)
// 1. 将整个数组空间初始化一个链表
// 2. 从备用空间取得一个结点
// 3. 将空闲结点链接到备用链表上
void InitSpace_SL(SLinkList &space){
	// 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针
	// "0"表示空指针
	for (int i=0; i<MAXSIZE-1; i++){
		space[i].cur = i+1;
	}
	space[MAXSIZE-1].cur = 0;
}
int Malloc_SL(SLinkList &space){
	// 若备用空间链表非空，则返回分配的结点下标，否则返回0
	int i = space[0].cur;
	if (space[0].cur) space[0].cur = space[i].cur;
	return i;
}
void Free_SL(SLinkList &space, int k){
	// 将下标为k的空闲结点回收到备用链接
	space[k].cur = space[0].cur;
	space[0].cur = k;
}
void difference(SLinkList &space, int &S){
	// 依次输入集合A和B的元素，在一维数组space中建立表示集合(A-B)U(B-A)
	// 的静态链表，S为其头指针。假设备用空间足够大，space[0].cur为其头指针。
	InitSpace_SL(space); //初始化备用空间
	S = Malloc_SL(space); //生成S头结点
	r = S; //r指向S的当前最后结点
	scanf(m,n); //输入A和B的元素个数
	for (int j=1; j<=m; j++){ //建立集合A的链表
		int i = Malloc_SL(space);
		scanf(space[i].data); //输入A的元素值
		space[r].cur = i; //插入到表尾
		r = i;
	}
	space[r].cur = 0; //尾结点指针为空
	for (int j=1; j<=n; j++){
		scanf(b);
		p = S;
		k = space[S].cur; //k指向集合A中第一个结点
		while(k!=space[r].cur && space[k].data!=b){
			p = k;
			k = space[k].cur;
		}
		if(k == space[r].cur){ //说明当前表中不存在该元素，插入在r所指结点之后，且r的位置不变
			i = Malloc_SL(space);
			space[i].data = b;
			space[i].cur = space[r].cur;
			space[r].cur = i;
		} 
		else{ //该元素已在表中，删除之
			space[p].cur = space[k].cur;
			Free_SL(space, k);
			if (r==k) r=p; // 若删除的是r所指结点，则需修改尾指针
		}
	}
}

循环链表

1
2
3
/**************循环链表**************/
// 表中最后一个结点的指针域指向头结点，形成一个环
// 操作与线性列表基本一致，差别仅在于算法中的循环条件不是p或者p->next是否为空，而是在于是否等于头指针。

双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**************双向链表**************/
typedef struct DuLNode{
	ElemType data;
	struct DuLNode *prior;
	struct DulNode *next;
} DuLNode, *DuLinkList;

// 插入
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){
	if(!(p = GetElemP_DuL(L,i))){
		return ERROR; //若p为NULL，说明插入位置不合法
	}
	if(!(s = (DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
	s->data = e;
	s->prior = p->prior; //s->prior = a;
	p->prior->next = s; //p36页 看图理解 a->next = s;
	s->next = p;
	p->prior = s;
	return OK;
}

// 删除
Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e){
	if(!(p = GetElemP_DuL(L,i))) return ERROR; //在L中确定第i个元素的位置指针p
	e = p->data;
	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);
	return OK;
}

实际应用

从实际应用角度出发重新定义线性链表及其基本操作。
https://blog.csdn.net/u013457167/article/details/78543258