线性表

线性表是一种逻辑结构，是有序的，所有元素类型相同。

它可以由顺序表和链表（存储结构）来实现。

顺序表

  1. 结构：

    数组（空间）。ElemType data[MaxSize];

    当前长度。int len;

插入，删除

初始化顺序表（顺序表中元素为整型），里边的元素是1,2,3，然后通过scanf读取一个元素（假如插入的是6），插入到第2个位置，打印输出顺序表，每个元素占3个空格，格式为1 6 2 3，然后scanf读取一个整型数，是删除的位置（假如输入为1），然后输出顺序表 6 2 3，假如输入的位置不合法，输出false字符串。

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
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MaxSize 50
#define ElemType int
typedef struct {
	ElemType data[MaxSize];
	int len;
} SqList;

void Print(SqList l) {
	for (int i = 0; i < l.len; i++) {
		printf("%3d", l.data[i]);
	}
	printf("\n");
}

bool Insert(SqList& l, ElemType e, int n) {
	//判断插入位置是否合法
	if (n<1 || n>l.len) {
		return false;
	}
	//判断插入后是否超出SqList的最大长度
	if (l.len == MaxSize) {
		return false;
	}
	//将从1开始的数，全-1，变成从0开始
	int len = l.len - 1;
	n = n - 1;
	for (int i = len; i >= n; i--) {
		l.data[i + 1] = l.data[i];
	}
	l.data[n] = e;
	l.len++;
	return true;
}

bool Delete(SqList& l, int n, ElemType &e) {
	if (n<1 || n>l.len) {
		return false;
	}
	//整理序号
	n--;
	int len = l.len - 1;

	e = l.data[n];
	for (int i = n; i < len; i++) {
		l.data[i] = l.data[i + 1];
	}
	l.len--;
	return true;
}

链表

链表的大小在程序运行时动态创建。

  1. 结构

    当前节点数据

    指向下一个节点的指针（地址）

  2. 头节点（下面的链表都有头节点）

    我们只记录链表的头节点地址，称头指针。并且，头节点不存放数据

头插法（逆向建立链表）

头插法需要运用到插入操作。

1
2
s->next = l->next;
l->next = s;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
LinkList Create_List_1(LinkList& l) {
	//创建头结点
	l = (LNode*)malloc(sizeof(LNode));
	l->next = NULL;
	//s用于指向新节点
	LNode* s;
	ElemType i;
	scanf("%d", &i);
	while (i != 9999) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = i;
		s->next = l->next;
		l->next = s;
		scanf("%d", &i);
	}
	return l;
}

尾插法（正向建立链表）

要新建一个额外的指针，指向尾节点，这样可以不断往后放。最后把尾节点的next==NULL

1
2
//拼接节点	 r->next = s;
//更新尾节点	 r = s;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LinkList Create_List_2(LinkList& l) {
	//新建头节点
	l = (LNode*)malloc(sizeof(LNode));
	l->next = NULL;
	//新节点
	LNode* s, *r=l;//r指向尾节点
	ElemType i;
	scanf("%d", &i);
	while (i!=9999)
	{
		s = (LNode*)malloc(sizeof(LNode));
		s->data = i;
        //拼接节点
		r->next = s;
		//更新尾节点
		r = s;
		scanf("%d", &i);
	}
	r->next = NULL;
	return l;
}

查找($$$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//按序号查找
LinkList GetElem(LinkList l, int i) {
	LNode* p = l->next;//让p指向第一个元素(头节点的下一个)
	int j = 1;//计链表的序号

	if (0 == i) {	//第0元素（头节点）
		return l;
	}
	if (i < 0) {//i无效
		return NULL;
	}
	
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	return p;//返回节点指针，如果超过链表长度，返回NULL
}

插入

要注意的一个点是：原来的链一定要放到最后断开，否则，后面的节点就找不到了。

1
2
3
4
5
6
7
8
9
10
11
12
//插入
bool FrontInsert(LinkList l,ElemType e, int i) {
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	LNode *p=GetElem(l, i-1);//获取要插入的前一个节点的指针
	if (NULL == p) {
		return false;
	}
	s->next = p->next;
	p->next = s;
	return true;
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
//删除
bool Delete(LinkList l, int i) {
	LNode* p = GetElem(l, i-1);//获得要删除元素的前一个节点
	if (NULL == p) {
		return false;
	}
	LNode* s = p->next;//指向要删除元素，以便free
	//链接好删除后的元素
	p->next = s->next;
	free(s);
	s = NULL;
	return true;
}

双向链表

1
2
3
4
5
typedef struct DNode {
	ElemType data;
	struct DNode* prior;
	struct DNode* next;
}DNode, * DLinkList;

头插法（逆向建立链表）

原来的链一定要放到最后断开，否则，后面的节点就找不到了。

判断dl->next不为空时，才让下一个节点的prior指向新节点if (dl->next){dl->next->prior = s;}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
DLinkList Dlist_head_insert(DLinkList& dl) {
	//创建头节点
	dl = (DNode*)malloc(sizeof(DNode));
	dl->prior = dl->next = NULL;
	//创建新节点
	ElemType e;
	scanf("%d", &e);
	while (e != 9999)
	{
		DNode* s = (DNode*)malloc(sizeof(DNode));
		s->data = e;
		s->next = dl->next;
		s->prior = dl;
		if (dl->next)
		{
			dl->next->prior = s;
		}
		dl->next = s;//断链一定要放最后
		scanf("%d", &e);//循环读入
	}
	return dl;
}

Tips

  • 当我们遇到序号从0开始，和序号从1开始时，我们怎么把他们变成相同的序号。

    我们可以把将从1开始的全部序号-1，那么从1开始的序号就变成了从0开始。

    or

    把将从0开始的全部序号+1，那么从0开始的序号就变成了从1开始。

  • 数据结构的基本操作

    所有的数据结构的基本操作都大致相同，都是4种。增，删，改，查