- 什么是线性表
零个或多个元素的有限序列
- 线性表的长度、直接前驱元素、直接后继元素、位序
线性表的元素个数即为长度（大于或等于0）；（a1,a2,a3,...,an-1，an）称an-1是an的直接前继元素，an是an-1的直接后继元素。n为位序。
- 线性表顺序存储结构的增删改查算法步骤和代码实现
插入：如果要插入的位置ith小于1或者大于最后一个元素的下一位置，抛异常或者返回错误。如果数组已经满，抛异常或者退出。从最后一个元素开始到第ith个元素，逐个向后移动一位。将数据插入第ith位置。数组长度加1.返回成功
删除：如果要删除的位置ith小于1或者大于最后一个元素，抛异常或者返回错误。如果数组已经空，抛异常或者退出。取出第ith个元素放到data中，表明删除了什么。从第ith+1个元素开始到最后一个元素，逐个向前移动一位覆盖。数组长度减1.返回成功
查询：如果要查询的位置ith小于1或者大于最后一个元素，抛异常或者返回错误。将第ith个元素的数据放到入参指针data指向的地址中。返回成功。
更改：如果要更改的位置ith小于1或者大于最后一个元素，抛异常或者返回错误。将入参data放入第ith个元素的数据中。返回成功。
复制代码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/**/ #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define SIZE 10 /*数组实现顺序存储*/ typedef int ElemType; typedef struct { ElemType Data[SIZE]; int length; }SqList; /*顺序存储结构插入*/ /*初始条件：线性表SqL已经存在，1<=ith<=length+1,data传入要插入的数据*/ /*操作结果：在ith位置之前插入数据data，长度length加1*/ int InsertSqlist(SqList* SqL, int ith, ElemType data) { if (ith<1|| ith>SqL->length+1 || SqL->length == SIZE)/*如果请求插入位置比1小或者比最后一位的下一位还大，或者数组已满*/ { return ERROR; } for (int i = SqL->length - 1; i > ith - 1 - 1; i--)/*从最后一位到第ith位，依次向后移动*/ { SqL->Data[i + 1] = SqL->Data[i]; } SqL->Data[ith - 1] = data; SqL->length++; return OK; } /*顺序存储结构删除,并接收删除内容*/ /*初始条件：SqL已经存在，1<=ith<=length。*/ /*操作结果：删除第ith个元素，并将内容放在data中，长度减小1*/ int DeleteSqList(SqList* SqL, int ith, ElemType* data) { if (ith <1 || ith > SqL->length)/*如果删除位置比1小或者比最后一位大或数组已空*/ { return ERROR; } *data = SqL->Data[ith - 1]; for (int i = ith - 1; i < SqL->length ; i++)/*从第ith位到最后一位，依次前移*/ { SqL->Data[i] = SqL->Data[i + 1]; } SqL->length--; return OK; } /*顺序存储的查询操作*/ /*初始条件：SQL已存在，1<=ith<=length.*/ /*操作结果：将查询结果第ith个元素放到data中*/ int getElem(SqList* SqL, int ith, ElemType* data) { if (ith <1 || ith > SqL->length)/*如果查询位置比1小或者比最后一个位置大或数组已空*/ { return ERROR; } *data = SqL->Data[ith - 1]; return OK; } /*顺序存储的更改操作*/ /*初始条件：SQL已存在，1<=ith<=length.*/ /*操作结果：第ith个元素更改为data*/ int setElem(SqList* SqL, int ith, ElemType data) { if (ith <1 || ith > SqL->length)/*如果查询位置比1小或者比最后一个位置大或数组已空*/ { return ERROR; } SqL->Data[ith - 1] = data; return OK; } void ShowList(SqList SqL) { for (int i = 0; i < SqL.length; i++) { printf("data[%d]=%dt", i, SqL.Data[i]); } printf("n"); return; } int main() { SqList testlist; testlist.Data[0] = 0; testlist.length = 1; for (int i = 5; i >=1; i--) { InsertSqlist(&testlist, 1, i); } ShowList(testlist); printf("数组长度=%dn",testlist.length); printf("第6位改为6.n"); setElem(&testlist,6,6); ShowList(testlist); ElemType temp; getElem(&testlist, 6, &temp); printf("获取第6位=%dn",temp); DeleteSqList(&testlist, 3, &temp); printf("删除第3位=%dn",temp); printf("删除之后数组：n"); ShowList(testlist); printf("在第2位插入77后数组为：n"); InsertSqlist(&testlist,2,77); ShowList(testlist); printf("删除最后一位，数组为：n"); DeleteSqList(&testlist, testlist.length, &temp); ShowList(testlist); printf("在表尾部插入99后n"); InsertSqlist(&testlist,testlist.length+1,99); ShowList(testlist); system("Pause"); return 0; }注意for循环范围。
- 线性表链式存储结构的增删改查算法步骤和代码实现
链式存储使用结构体和结构体指针抽象数据。
复制代码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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166#include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define SIZE 10 /*带有指针的结构体实现节点，结构体指针实现链表*/ typedef struct Node{ ElemType Data; struct Node * next; }Node; typedef Node* LinkedList; /*查询链表中第i个元素*/ /*前提条件：存在链表*/ /*操作结果：将查询到的结果放在形参指针rs指向的地址中*/ /* 步骤：1.头指针指向头结点2.指针每向后移动一次，计数加一3.直到指针为空或者计数不小于ith 4.将查询内容放入rs指针5.返回状态码*/ int getElem(LinkedList L,int ith,ElemType* rs) { int counter = 1; LinkedList p = L->next;/*指向第一个节点*/ while (p&&counter<ith)/*当指针没有指向尾结点的下一节点（NULL）并且数小于ith时，移动指针并计数加一*/ { p = p->next; counter++; } if (!p) { return ERROR; } *rs = p->Data; printf("节点数据=%dt", *rs); printf("地址=%xt",p); printf("next指针=%xn",p->next); return OK; } ///**************************************************************************** /// @data : /// @input :L 链表指针；ith 插入位置；data 需要插入的数据 /// @output : OK 操作成功 ERROR 操作失败 /// @brief : 1<=ith<=length，操作后链表在第ith位置处增加一个节点 ///**************************************************************************** int InsertLinkedList(LinkedList* L,int ith,ElemType _data) { int counter = 1; LinkedList p = *L;/*指向头结点*/ while (p &&counter < ith)/*当指针没有指向尾结点的下一节点（NULL）并且小于第i个节点的直接前继时，移动指针并计数加一*/ { p = p->next; counter++; } if (!p) { return ERROR; } /*此时已经指向第i个节点的直接前继*/ LinkedList NewNode = (LinkedList)malloc(sizeof(Node));/*开辟内存，创建新的节点*/ NewNode->Data = _data;/*传入数据*/ NewNode->next = p->next;/*新节点next指针指向原来的第i个节点*/ p->next = NewNode;/*第i个节点的直接前继的next指针重定向到新节点*/ return OK; } ///**************************************************************************** /// @data : /// @input :L 链表指针；ith 删除第i个节点；data 需要插入的数据 /// @output : OK 操作成功 ERROR 操作失败 /// @brief : 1<=ith<=length，操作后链表在第ith位置处增加一个节点 ///**************************************************************************** int DeleteLinkedList(LinkedList* L, int ith, ElemType* _data) { int counter = 1; LinkedList p = *L; while (p && counter < ith ) { p = p->next; counter++; } if (!p) { return ERROR; } /*此时p已经指向第i个节点的直接前继*/ LinkedList pDel = p->next;/*指向第i个要删除的节点*/ p->next = pDel->next;/*第i个节点的直接前继节点的next指针，指向直接后继*/ *_data = pDel->Data;/*传出要删除的数据*/ free(pDel);/*删除第i个节点*/ return OK; } ///**************************************************************************** /// @data : /// @input : n：节点数量 /// @output :OK Error /// @brief :使用头插法，创建一个内容data从1到n 的链表，作为检验上述增删改查的数据 ///**************************************************************************** int CreatesqLinkList(LinkedList* L,int n) { for (int i = n; i > 0; i--) { if(!InsertLinkedList(L, 1, i)) return ERROR; } return OK; } ///**************************************************************************** /// @data : /// @input :L 头指针的地址 n要创建的节点数量 /// @output :返回创建操做是否成功OK、ERROR /// @brief :使用尾插法，对空链表进行整表创建。前提已经存在空链表，传入一个空链表的头指针地址。 ///**************************************************************************** void CreatBackpushLinkList(LinkedList*L,int n) { LinkedList p = *L; srand(time(0)); for (int i = 0; i < n; i++) { LinkedList NewNode = (LinkedList)malloc(sizeof(Node)); NewNode->Data = rand() % 10; NewNode->next = p->next; p->next = NewNode; } return; } void showLinkedList(LinkedList L) { int i = 1; L = L->next; while (L) { printf("第%d个节点=%dt",i,L->Data); printf("地址=%xt", L); printf("next指针=%xn", L->next); ++i; L = L->next; } printf("n"); } void test2() { LinkedList L = (LinkedList)malloc(sizeof(Node)); L->next = NULL;/*创建一个带头节点的链表*/ CreatesqLinkList( &L, 5);//头部插入5个节点 showLinkedList(L); InsertLinkedList(&L, 1, 12);/*在第2个位置插入元素12*/ printf("在第1个位置插入元素12n"); showLinkedList(L); int rs; DeleteLinkedList(&L,6,&rs); printf("删除在第6个位置，删除的内容为：%dn",rs); showLinkedList(L); printf("尾插法创建整表n"); CreatBackpushLinkList(&L,5); showLinkedList(L); system("Pause"); } int main() { //test1(); test2(); } - 头指针、头节点的异同
头指针：头指针用来标识链表，必须存在，一般指向头节点。
头结点：可有可无，一般头节点放在第一个节点前，用于统一对链表的插入和删除操作。数据域一般没有意义。 - 顺序存储和链式存储的优缺点
顺序存储用于很少插入和删除，但是频繁查询。
链式存储用于很少查询，但是频繁插入和删除的场合。且避免内存碎片问题。
最后
以上就是缥缈季节最近收集整理的关于大话数据结构学习笔记2的全部内容，更多相关大话数据结构学习笔记2内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复