数据结构(1)-引言与线性表
引言
为帮夫人复习数据结构，所以再过一遍数据结构。顺便整理份笔记，方便夫人日后复习。教材还是用的经典的严蔚敏版数据结构。但书中大部分是伪代码，不便于实现。所以本文会把书中所提到的所有代码采用C语言实现，保证可运行。
数据结构本人理解就是数据的结构。传统的编程语言只包含整型、浮点型、bool型、字符型、字符串型等基础数据类型。如果要做大型的软件，比如图书管理系统，或者教务系统。那么我们可能要定义图书类型，或者学生类型。在C语言中我们可以通过struct结构体来定义，在C++、Java等面向对象语言中可以采用Class来定义。这些自定义的数据类型由编程语言原有的基础类型构成，同时数据与数据之间又存在着一定的关系。
而《数据结构》一书就是针对数据与数据之间的线性结构、树形结构、图状或网状结构进行简单介绍。
其实数据结构虽然看上去难，但其实是计算机学科的入门课程。其内容都是非常简单的。其深入可扩展到网络、几何代数论、图论等较深奥的内容。所以，看一名计算机专业学生是否学得好，看他数据结构学的咋样就行。
线性表
先借用下书中的定义:在数据元素的非空有限集合中，(1)存在唯一的一个被称做”第一个”的元素;(2)存在唯一的一个被称做”最后一个”的元素;(3)除第一个之外，集合中的每个数据元素均只有一个前驱;(4)除最后一个之外，集合中每个元素均只有一个后继。
通俗的说，排队就是一种线性表。(1)说的就是排在队伍第一个的那个人。(2)说的就是排在队伍最后的一个人。除了这两个人其他人前面和后面都有一个人也就是前驱与后继
线性表的表示
线性表在现实生活中随处可见，比如排队，学生成绩排名等。但如何将其在计算机中实现出来了? 书中介绍了两种实现方法分别是线性表的顺序表示和线性表的链式表示。
其中顺序线性表的优势是方便查找。而链式线性表的优势是方便插入数据删除数据。
顺序线性表
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表中的数据元素。
代码在创建变量时是随机在内存空间上找个位置，所以每个变量位置不一定连续。只有创建数组时，会在连续的存储单元上去开辟空间。
所以这种类型的线性表是通过数组来实现，其结构体定义如下：1
2
3
4
5
6
7
8
9
10#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100 //线性表创建时给他分配多大的空间。
#define LISTINCREMENT 10 //当线性表不够用时，每次追加的空间
typedef int ElemType; //ElemType是泛指类型，如int char 这里先用int
typedef struct{
ElemType *elem; //指向存储数据的首空间地址
int length; //这个线性表中放了多少元素来
int listsize; //这个线性表总共可以放多少元素
}SqList;
可以看到，顺序线性表的基础单位就是一个线性表。下面线性链表的基础单位是一个结点，由多个结点链接才形成线性表。这也是二者实现的一个区别。
- 顺序线性表的创建
1
2
3
4
5
6
7bool InitList_Sq(SqList &L){
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));//首先给线性表开辟存放数据的空间
if(!L.elem) return false; //分配空间失败
L.listsize = LIST_INIT_SIZE;
L.length = 0;
return true;
} - 顺序线性表插入数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16bool ListInsert_Sq(SqList &L, int index, ElemType e){
if(index<0||index>L.length) //判断插入位置是否合法
return false;
if(L.length>=L.listsize){ //当前顺序线性表放满了，要追加空间了
L.elem = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));
if(!L.elem) return false; //分配空间失败
L.listsize = L.listsize + LISTINCREMENT; //增加总的存储空间
}
//从最后一个元素开始，每个元素后移一位，来把第index位置空出来插入新数据(所以说顺序线性表插入删除不方便，每次都要移动很多数据)
for(int i=L.length;i>=index;i--){ //这里要注意，因为数据是从0号下标开始存的,所以index位置插入其实是在下标index-1处。
L.elem[i] = L.elem[i-1];
}
L.elem[index-1] = e;
L.length += 1;
return true;
} 顺序线性表删除数据
1
2
3
4
5
6
7
8
9bool ListDelete_Sq(SqList &L, int index){
if(index<0||index>=L.length) return false; //判断删除位置是否合法
//从删除位置开始，用前面一个元素覆盖当前元素，最后顺序表长度-1即可
for(int i=index-1;i<L.length-1;i++){
L.elem[i] = L.elem[i+1];
}
L.length -= 1;
return true;
}合并两个升序的顺序线性表
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
26void MergeList(SqList &l,SqList &r,SqList &m){
m.length = l.length + r.length;
int i=0,j=0,k=0;
while(i<l.length&&j<r.length){ //i用于遍历l，j用于遍历r，k用于遍历m
if(l.elem[i]<r.elem[j]){ //判断l和r当前元素谁小 将小的放入m并后移
m.elem[k]=l.elem[i];
k++;
i++;
}else{
m.elem[k]=r.elem[j];
k++;
j++;
}
}
//可能某个线性表已经全部放入m但另外一个还没放完则继续放
while(i<l.length){ //将l后面的放入m
m.elem[k]=l.elem[i];
k++;
i++;
}
while(j<r.length){ //将r后面的放入m
m.elem[k]=r.elem[j];
k++;
j++;
}
}主函数和一些子函数。（将上述代码按顺序拷贝到一个cpp文件即可运行）
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
41void input_Sq(SqList &L,int n){//从输入中接收数据来给顺序线性表赋初值
for(int i=0;i<n;i++){
scanf("%d",&L.elem[i]);
}
L.length = n;
}
void print_Sq(SqList &L){
//打印顺序线性表
for(int i=0;i<L.length;i++){
printf("%d ",L.elem[i]);
}
printf("\n");
}
int main(){
SqList l,r,m;
InitList_Sq(l);
InitList_Sq(r);
InitList_Sq(m);
input_Sq(l,5); //给l赋初值
int i,elem=7,n=5;
ListInsert_Sq(l,3,elem); //在线性表l第三个位置插入元素elem
print_Sq(l);
ListDelete_Sq(l,5); //删除线性表l第五个元素
print_Sq(l);
input_Sq(r,7); //给r赋初值
MergeList(l,r,m); //合并两个升序线性表。注意一定要升序
print_Sq(m); //输出
return 0;
}
/*
输入案例
先输入 1 3 8 10 12
输出 1 3 7 8 10 12
1 3 7 8 12
然后输入 2 3 4 5 6 7 9
*/
输出 1 2 3 3 4 5 6 7 7 8 9 12线性链表
线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，虽然可以很方便的通过下标来直接遍历查找。但插入与删除元素都要移动大量元素。而链式存储结构的线性表，由于它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去来顺序表可随机存储的优点。
线性链表的基础单位是一个结点node 其包含来一个数据域(用来存放数据)和一个指针域(用来指向下一个结点的位置)，从而一个连一个形成线性链表。考虑到Java等高级语言没有指针，因此还有一种采用数组的方式实现链表称为静态链表，而采用指针的链表称为动态链表。此外还有首尾相连形成环的循环链表，以及同时指向前驱和后继的双向链表。动态链表
动态链表结构体定义如下
1
2
3
4
5
6
7#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct LNode{
ElementType data; //数据域
struct LNode* next; //指针域
}LNode, *LinkList;动态链表的顺序创建
这种方式创建的链表，其数据输入顺序就是链表的顺序1
2
3
4
5
6
7
8
9
10
11
12
13
14void CreateLinkList_o(LinkList &L,int n){ //顺序创建动态链表
L = (LinkList)malloc(sizeof(LNode)); //给头指针分配一个空间为头结点，头结点数据域放链表长度，其指向下一个结点为第一个数据结点
L->next = NULL;
L->data = n;
LinkList p,q;
p = L;
while(n--){ //创建n个数据结点
q = (LinkList)malloc(sizeof(LNode)); //创建一个结点空间
scanf("%d",&q->data); //输入数据
q->next = NULL;//指针指空
p->next = q;//将上一个结点的next指向当前结点
p=q;//将p指向当前结点作为下一个结点的上个结点。
}
}动态链表的逆序创建
这种方式创建的链表，其链表顺序与输入顺序相反1
2
3
4
5
6
7
8
9
10
11
12void CreateLinkList_r(LinkList &L, int n){ //逆序创建动态链表
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
L->data = n;
LinkList p;
while(n--){
p =(LinkList)malloc(sizeof(LNode)); //创建一个结点空间
scanf("%d",&p->data); //输入数据
p->next = L->next; //p的next指向前面生成的链表(即将当前创建的结点放在数据结点第一位)
L->next = p; //头结点next指向当前结点。
}
}动态链表的插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17bool ListInsert_L(LinkList &L, int index, ElementType e){// 在index位置插入数据为e的结点
if(index<1||index>L->data) return false; //判断插入位置是否合法
LinkList p,q;
p = L;
q = (LinkList)malloc(sizeof(LNode));
q->data = e;
q->next = NULL;
while(index>1){ //要在index位置插入元素，则p要到index-1位置，因为p是从头结点开始(相当于从0开始)，所以到index-1位置，需要循环index-1次。
index -=1;
p = p->next;
}
//这时候循环结束p指向了index-1位置，
q->next=p->next; //将q结点的next指向原来的第index号结点。
p->next = q;//将原来的index-1号结点的next指向了q结点，这样就相当于把q插入到了index位置。
L->data+=1;//长度+1
return true;
}动态链表的删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16bool ListDelete_L(LinkList &L, int index){ //删除index位置的结点。
if(index<1||index>L->data) return false;
LinkList p,q;
p=L;
//要删除index位置结点，则p要找到index-1位置，因为p是从头结点开始(相当于从0开始)，所以到index-1位置，需要循环index-1次。
while(index>1){
index -= 1;
p = p->next;
}
//这时候循环结束p指向了index-1位置，
q=p->next; //q指向要删除的结点;
p->next = q->next; //index-1位置结点的next指向了index位置结点的next也就是index+1位置的结点,这样原来index位置的结点就从链表中断出去了
free(q); //然后把这个结点空间释放
L->data -= 1; //长度-1
return true;
}两升序动态链表的合并
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
31void MergeList_L(LinkList &l, LinkList &r, LinkList &m){
m = (LinkList)malloc(sizeof(LNode));
m->data = l->data+r->data;
m->next = NULL;
LinkList p,q,k;
p = l->next;
q = r->next;
k = m;
while(p!=NULL&&q!=NULL){
if(p->data<q->data){
k->next = p;
k = k->next;
p = p->next;
}else{
k->next = q;
k = k->next;
q = q->next;
}
}
//类似之前顺序线性表，把剩下没遍历完的加入到m后面。
while(p!=NULL){
k->next = p;
k = k->next;
p = p->next;
}
while(q!=NULL){
k->next = q;
k = k->next;
q = q->next;
}
}- 主函数和一些子函数。（将上述代码按顺序拷贝到一个cpp文件即可运行）
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
31void print_LinkList(LinkList L){ //输出一个动态链表
LinkList p=L->next;
while(p!=NULL){
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
int main(){
LinkList l,r,m;
CreateLinkList_o(l,6); //创建l链表
ListInsert_L(l,4,8); //在l链表第四个位置插入一个元素为8的结点
print_LinkList(l); //打印l链表
ListDelete_L(l,4); //删除l链表第四个位置的结点
print_LinkList(l); //打印l链表
CreateLinkList_o(r,8); //创建r链表
MergeList_L(l,r,m); //合并两个升序链表
print_LinkList(m); //打印m链表
return 0;
}
/*
输入 1 3 5 9 10 12
输出 1 3 5 8 9 10 12
1 3 5 9 10 12
输入 2 3 4 5 6 7 11 15
输出 1 2 3 3 4 5 5 6 7 9 10 11 12 15
*/静态链表
静态链表逻辑上与动态链表一样，只是考虑到一些高级语言没有指针所以通过数组的方式来实习，数据放在一连串的数组中，而它指向下一个结点的指针，则是用下一个结点在数组中的下标来代替
因为静态链表逻辑上与动态链表一样，所以通过一个题目实现静态链表的创建，遍历查找、插入数据、删除数据。
题目：给两个集合A、B,将只存在A或者B中的元素组合成一个静态链表
实现思路，首先输入A的元素，构建一个静态链遍，然后每输入一个B的元素则去A中查找，如果存在相同的元素则删除，如果不存在，则插入到链表中。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#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef int ElementType;
typedef struct component{
ElementType data; //用来放数据
int cur; //用来说明下一个结点在数组中的下标
}component, SLinkList[MAXSIZE];
void initSpace_SL(SLinkList &space){ //初始化一个空静态链表，静态链表中每个单元的cur指向它的下一个单元
for(int i=0;i<MAXSIZE-1;i++){
space[i].cur = i+1; //i结点的下一个结点为i+1
}
space[MAXSIZE-1].cur = 0; //最后一个结点指向了第0号空间
}
int Malloc_SL(SLinkList &space){ //查看静态链表中是否存在空的单元，如果存在返回该单元下标，否则返回0
int i = space[0].cur; //注意这里静态链表的头结点 也就是0号空间的cur并不是指向链表的第一个数据空间下标，而是第一个空单元的。所以i对应位置为第一个空单
if(space[0].cur){ //当space[0].cur = 0时 则表示这个静态链表已经被放满，否则没放满，没放满则i单元被拉出去放数，那么space[0].cur就要指向space[i].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 print_SL(SLinkList &space,int S){ //S为头结点
int i=space[S].cur; //头结点cur指向第一个数据结点
while(i){
printf("%d ",space[i].data);
i = space[i].cur;
}
printf("\n");
}
void difference(SLinkList &space,int &S, int m,int n){ //m为集合A的长度。n为集合B的长度
//依次输入两个集合A和B, 首先用A去创建一个静态链表，然后依次输入B中元素，如果该元素不在A中则加入静态链表，如果已经存在，则从静态链表中删除该元素
int i,j,b;
int p,k; //用于遍历时 p为当前结点 k为其下个结点
initSpace_SL(space); //初始化空静态链表space
S=Malloc_SL(space); //S作为头结点。其cur指向第一个数据结点
int r=S; //r指向A集合的最后一个单元，因为当前是空的所以r=S(注意是A集合最后一个元素，所以当插入新元素时r不动，但删除A中最后一个元素时r要回退)
for(j=1;j<=m;j++){ //输入m个数按顺序插入到静态链表
i = Malloc_SL(space);
scanf("%d",&space[i].data); //输入数据放入当前结点
space[r].cur=i; //之前的最后一个结点的cur指向当前结点
r=i; //r指向新的最后一个结点
}
space[r].cur = 0;//最后一个结点的cur指向0下标
for(j=1;j<=n;j++){ //输入集合B的n个元素
print_SL(space,S); //每次输入一个元素打印下静态链表看下变化
scanf("%d",&b);
p =S;//p从头节点开始
k = space[p].cur; //p的下一个结点,也就是第一个数据结点
while(k!=space[r].cur && space[k].data!=b){ //p没到最后一个结点同时没找到与b相同的数据，则继续
p = k;
k = space[p].cur;
}
if(k == space[r].cur){ //找到最后都没找到，则插入
i = Malloc_SL(space); //取一个空结点
space[i].data =b;
space[i].cur = space[r].cur;
space[r].cur = i;
}else{ //找到等于b的结点，删除 ,即删除k结点
space[p].cur = space[k].cur;
Free_SL(space, k);
if(r == k){
r = p; //如果删除的是最后一个结点，r回退
}
}
}
}
int main(){
int S;
SLinkList space;
difference(space,S,5,7);
print_SL(space,S);
return 0;
}循环链表
是另一种形式的链式存储结构，特点是：尾结点指针域指向头结点形成循环，从环上任何位置结点出发均可找到表中其他结点，操作与其他链表一致，停止条件为当重新指向此结点时。双向链表
双向链表顾名思义就是指向两个方向。原本的链表只有一个next指针指向后一个结点，而双向链表的指针域包含两个指针，一个指针prior指向前驱，一个指针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
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct DuLNode{
ElemType data;
struct DuLNode *next;
struct DuLNode *prior;
}DuLNode, *DuLinkList;
void Create_DuL_o(DuLinkList &L, int n){ //顺序创建。
L = (DuLinkList)malloc(sizeof(DuLNode));
L->data = n;
L->prior = NULL;
L->next = NULL;
DuLinkList p,q; // p用来指向最后一个结点的 。 q用来指向当前创建的结点，然后把q插入到 p后面就行
p = L;
while(n--){
q = (DuLinkList)malloc(sizeof(DuLNode)); //分配空间
scanf("%d", &q->data);//给当前结点q 数据域输入数据
q->next = p->next; //当前结点q的next指向之前最后一个结点p的next 也就是 null
q->prior = p; // 当前结点q的prior指向之前的最后一个结点p。
p->next = q; //之前最后一个结点p的next指向当前结点q
p = q; //p继续指向 最后一个结点 ，也就是当前结点
}
}
void Create_DuL_r(DuLinkList &L, int n){ //逆序创建。
L = (DuLinkList)malloc(sizeof(DuLNode));
L->data = n;
L->prior = NULL;
L->next = NULL;
DuLinkList p;
while(n--){
p = (DuLinkList)malloc(sizeof(DuLNode));
scanf("%d",&p->data); //给数据域输入数据
p->next = L->next; //当前结点p插入到头结点L与之前创建的数据 结点中间。
if(L->next) L->next->prior=p; //如果当前结点p不是第一个数据结点，则将之前数据结点prior指向他
p->prior=L;
L->next = p;
}
}
bool ListInsert_DuL(DuLinkList &L, int index, ElemType e){
if(index<1||index>L->data+1) return false;
DuLinkList q,p = L; // p从头结点开始即0号开始
while(index>1){ //在index位置插入p要跳转到index-1位置。从0开始则要跳index-1次即 index>1
p = p->next;
index -= 1;
}
q = (DuLinkList)malloc(sizeof(DuLNode));
q->data = e;
p->next->prior = q;//后一个结点指向q
q->next = p->next;//q指向后一个结点
p->next = q;//前一个结点的next指向q
q->prior = p;//q的prior指向前一个结点
L->data+=1;//长度+1
return true;
}
bool LinstDelete_DuL(DuLinkList &L, int index){ //删除位置index的结点
if(index <1||index>L->data) return false;
DuLinkList p = L;
//找到 要删除位置前一个 结点
while(index>1){
p = p->next;
index -= 1;
}
DuLinkList q = p->next; //q指向 要删除的结点
//将q 从链表中断开 ，即q的下一个结点的prior指向前一个结点p，前一个结点p的next指向q的next
q ->next->prior = p;
p->next = q->next;
free(q); //释放要删除的 结点
L->data-=1; //长度-1
return true;
}
void Merge_DuL(DuLinkList &l, DuLinkList &r, DuLinkList &m){ // 合并两个升序的双向链表。
m = (DuLinkList)malloc(sizeof(DuLNode));
m->data = l->data+r->data;
m->prior = NULL;
m->next = NULL;
DuLinkList p,q,k;
p = l->next;
q = r->next;
k = m;
while(p!=NULL&&q!=NULL){
if(p->data<q->data){
k->next = p;
p->prior = k;
k = p;
p = p->next;
}else{
k->next = q;
q->prior = k;
k = q;
q = q->next;
}
}
while(p!=NULL){
k->next = p;
p->prior = k;
k = p;
p = p->next;
}
while(q!=NULL){
k->next = q;
q->prior = k;
k = q;
q = q->next;
}
}
void print_DuLink(DuLinkList &L){ // 打印双向线性链表
DuLinkList p = L->next;
while(p!=NULL){
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
int main(){
DuLinkList l,r,m;
Create_DuL_o(l,5); // 创建双向线性链表l
print_DuLink(l);
ListInsert_DuL(l,3,10); //在第三位置插入10
print_DuLink(l);
LinstDelete_DuL(l,3); //删除第三位置结点
print_DuLink(l);
Create_DuL_o(r,8); // 创建双向线性链表l
Merge_DuL(l,r,m);
print_DuLink(m);
return 0;
}以表为单位的链表
书中最后还给了一种链表的构造方法，其实就是将原来的动态链表外面再套了一层，之前有提到顺序线性表的基础单位是一个表，创建一个变量就是一个线性表。而链表不同链表基础单位是一个结点，创建多个结点变量然后连接起来才成了一个线性表。所以就在这个结点外面再套一层来形成一个变量为一个线性表的样子。
这种线性链表的具体优点还没发现，书上是说方便记录其长度，确实多了个数据域存长度，但之前链表实现方法，头结点的数据域也是用来存长度，第二个结点才是第一个数据结点。所以感觉也没提供啥优势。
完整的结构体定义如下，还包含了，顺序创建、逆序创建、插入结点、删除结点、两个升序链表的有序合并。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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct LNode{ //一个结点类型
ElemType data; //数据域
struct LNode *next; //指针域
}*Link, *Position;
typedef struct{ //线性链表类型
Link head,tail; //分别指向表头结点和尾结点
int len; //记录表长度
}LinkList;
void InitList_r(LinkList &L,int n){ //逆序构造一个长度为n的线性链表L
L.len = n;
L.head = L.tail = NULL;
Link p;
while(n--){
p = (Link)malloc(sizeof(LNode));
scanf("%d",&p->data);
if(L.tail == NULL) L.tail = p; //因为是逆序所以第一个创建的结点就是最后一个结点，直接tail指向它，后面tail!=NULL就不会变了
p->next = L.head; //第一个结点会指向空，后面的结点都会指向前一个创建的结点
L.head = p; //头指针指向当前结点
}
}
void InitList_o(LinkList &L, int n){ //顺序构造一个长度为n的线性链表L
L.len = n;
L.head = L.tail = NULL;
Link p,q;
while(n--){
q = (Link)malloc(sizeof(LNode));
scanf("%d",&q->data);
q->next = NULL; // 指空
L.tail = q; //顺序插入 当前结点即为最后一个结点，所以tail指向它
if(L.head == NULL){ // 判断如果head是空，则当前为第一个结点
L.head = q; //head指向它
p=q; //p也指向当前结点也就是下一个结点的上一个结点
}else{
p->next = q; //如果不是第一个结点则用上一个结点p指向当前结点
p=q;
}
}
}
void print_L(LinkList &L){
Link p;
p = L.head;
while(p!=NULL){
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
bool Insert_L(LinkList &L, int index, ElemType e){ //在index位置插入数据为e的结点
if(index<0||index>L.len+1) return false;
Link p = L.head;
for(int i =1;i<index-1;i++){
p=p->next;
}
Link q = (Link)malloc(sizeof(LNode));
q->data = e;
q->next = p->next;
p->next = q;
return true;
}
bool Delete_L(LinkList &L, int index){ //删除index位置的结点
if(index<0||index>L.len) return false;
Link p = L.head;
for(int i=1;i<index-1;i++){
p = p->next;
}
Link q = p->next; //记得重新定义一个指针指向这个要删除的结点
p->next = q->next;
free(q); //这里记得释放指针指向的空间
return true;
}
void MergeList_LinkList(LinkList &l, LinkList &r, LinkList &m){
m.len = l.len + r.len;
Link p,q,k;
p =l.head;
q = r.head;
m.head = k = NULL;
while(p!=NULL&&q!=NULL){
if(p->data<q->data){
if(k==NULL){ //如果是第一个结点则 头指针直接指向p就行
m.head=p;
}else{ //如果不是第一个结点，则k是指向上一个结点的，则k->next指向p,然后k指向p
k->next=p;
}
k = p;
p = p->next;
}else{
if(k==NULL){
m.head=q;
}else{
k->next=q;
}
k=q;
q = q->next;
}
}
while(p!=NULL){
k->next=p;
k=p;
p=p->next;
}
while(q!=NULL){
k->next=q;
k=q;
q=q->next;
}
m.tail=k;
}
int main(){
LinkList L,r,m;
InitList_o(L,5);
print_L(L);
Insert_L(L,3,10);
print_L(L);
Delete_L(L,3);
print_L(L);
InitList_o(r,6);
MergeList_LinkList(L,r,m);
print_L(m);
return 0;
}线性表的应用
书中给出了一个用线性表来存放一元多项式，并且用来做加法运算的例子，原理就是将一元多项式的系数按次幂项从小到大放到线性表对应位置，如果这个一元多项式是个稠密型(比如包含100项从一次项到100次项都有非零系数)。那么直接创建一个101长度的顺序线性表，顺序线性表数组下标用来指引次幂。然后把系数放到对应数组空间就行，比如ax^3 直接在L.elem[3]=a即可。
大大多数一元多项式是悉数型，比如ax+bx^10+cx^100+dx^1000 本身只有四项，但如果要用顺序线性表要创建一个长度为1001的数组，而且大量空间中都放的0。这时候链表反而是一个更好的选择只要四个数据结点就可以存放。
但链表的结点之间只有前后关系，如果还想要有次幂级关系，那么数据域只有一个变量data就不够，因此数据域要有两个变量，一个用来存放次幂，一个用来存放次幂项的系数。
具体代码如下，给出了一元多项式线性链表的结构体、创建、两个一元多项式加法，以及打印。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#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
float coef; //系数
int expn; //指数
struct Node *next; //指向下个结点
}Node, *Polynomial;
void create_poly(Polynomial &l){ //顺序创建一个带表头结点的一元多项式链表
l = (Polynomial)malloc(sizeof(Node));
l->expn = -1;
l->next = NULL;
Polynomial p,q;
p = l;
int expn;
float coef;
while(scanf("%f %d", &coef, &expn)!=EOF&&expn){ //输入指数 系数 EOF 死循环 windows ctrl+z停止 linux mac按ctrl+d停止 当expn输入0停止
q = (Polynomial)malloc(sizeof(Node));
q->coef = coef;
q->expn = expn;
q->next = NULL;
p->next = q;
p = q;
}
}
void AddPoly(Polynomial &l, Polynomial &r, Polynomial &m){
m = (Polynomial)malloc(sizeof(Node));
m->expn = -1;
m->next = NULL;
Polynomial p,q,k;
p = l->next;
q = r->next;
k = m;
float coef;
while(p!=NULL&&q!=NULL){
if(p->expn == q->expn){ //系数相同则做加法
p->coef = p->coef+q->coef;
if(p->coef!=0){ //只有结果不为0时才插入
k->next = p;
k = p;
}
p=p->next;
q=q->next;
}else if(p->expn<q->expn){
k->next = p;
k=p;
p=p->next;
}else{
k->next=q;
k=q;
q=q->next;
}
}
while(p!=NULL){
k->next = p;
k=p;
p=p->next;
}
while(q!=NULL){
k->next=q;
k=q;
q=q->next;
}
}
void print_Poly(Polynomial &l){
Polynomial p = l->next;
while(p!=NULL){
if(p->coef>0) printf("+");
printf("%.0fx^%d",p->coef,p->expn);
p = p->next;
}
printf("\n");
}
int main(){
//创建一个 3x-5x^3+7x^5-12x^8的 一元多项式
Polynomial l,r,m;
create_poly(l);
//创建一个 -2x+3x^2+5x^3-6x^4-5x^5+10x^7 的一元多项式
printf("输入第二个一元多项式:\n");
create_poly(r);
// //求和
AddPoly(l,r,m);
print_Poly(m);
return 0;
}
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！