This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.
I. Abstract Data Type Description of Linear Lists
Type name: Linear List (List) Data object set: A linear list is an ordered sequence (a1, a2, …, an) composed of n (>=0) elements. Operation set: Linear list L belongs to List, integer i represents position, element X belongs to ElementType.
II. Sequential List
1. Definition
struct LNode {
ElementType Data[MAXSIZE];//存了一个数组，其最多能存MAXSIZE个元素
int Last;//最后一个元素的下标！
};
typedef struct LNode *List;Accessing element at index i: L.Data[i] or PtrL->Data[i] Length of the linear list: L.Last+1 or PtrL->Last+1;
2. Operations
The basic operations are:
1.List MakeEmpty();//Initialize an empty linear list 2.ElementType FindKth(int K, List Ptrl);//Return the element at index K 3.int Find(ElementType X, List Ptrl);//Find the first occurrence position of X in linear list L 4.void Insert(ElementType X, int i, List Ptrl);//Insert a new element X before position i 5.void Delete(int i, List Ptrl);//Delete the element at position i 6.int Length(List Ptrl);//Return the length n of the linear list**
Let’s go through them one by one
(1) Creating an Empty List
List MakeEmpty() {
List PtrL;
PtrL = (List)malloc(sizeof(struct LNode));
PtrL -> Last = -1;
return PtrL;
}(2) Finding the Element at Index K
Returns the corresponding element at index K.
ElementType FindKth(int K, List Ptrl) {
return Ptrl->Data[K];
}(3) Finding Element X
Returns the index; returns -1 if not found.
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;//找到后返回的是存储位置 即下标
}(4) Insertion
Insert a new element with value X at the i-th (1 <= i <= n+1) position.
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];
Ptrl->Data[i-1] = X;
Ptrl->Last++;//last仍指向最后元素！
return;
}(5) Deletion
Delete the i-th element (index i-1).
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];
Ptrl->Last--;
return;
}(6) Returning the Length n of the Linear List
Delete the i-th element (index i-1).
int Length(List Ptrl){
return Ptrl->Last + 1;
}3. Complete Code Demonstration
//顺序表
#include <iostream>
using namespace std;
typedef int ElementType;
const int MAXSIZE = 1000;
// 1.定义部分
struct LNode {
ElementType Data[MAXSIZE]; //存了一个数组，其最多能存MAXSIZE个元素
int Last; //最后一个元素的下标！
};
typedef LNode *List;
// 2.操作函数
//(1) 建立空线性表
List MakeEmpty() {
List Ptrl; //建立
Ptrl = new struct LNode; //为其分配第一个结点的空间
Ptrl->Last = -1; //还未存数据，下边设为-1
return Ptrl; //返回该指针
}
//(2) 查找下标为K的元素 返回下标K的相应元素
ElementType FindKth(int K, List Ptrl) {
return Ptrl->Data[K];
}
//(3) 查找元素X 返回下标 未找到返回-1
int Find(ElementType X, List Ptrl) {
int i = 0;
while (i <= Ptrl->Last && Ptrl->Data[i] != X) {
i++;
}
if (i > Ptrl->Last)
return -1;
else
return i;
}
//(4) 插入元素X 在第i(1 ≤ i ≤ n+1)个位置上插入一个值为X的新元素
void Insert(ElementType X, int i, List Ptrl) {
if (Ptrl->Last == MAXSIZE - 1) { //表空间已满，则不能插入
printf("表满");
return;
}
if (i < 1 || i > Ptrl->Last + 2) { //检查输入是否合法
printf("位置不合法");
return;
}
int j;
for (j = Ptrl->Last; j >= i - 1; j--) //注意这里顺序不能从前往后
Ptrl->Data[j + 1] = Ptrl->Data[j];
Ptrl->Data[i - 1] = X;
Ptrl->Last++; // last仍指向最后元素！
return;
}
//(5) 删除 删除第i个元素（下标为i-1）
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];
Ptrl->Last--;
return;
}
//(6) 返回线性表的长度n
int Length(List Ptrl){
return Ptrl->Last + 1;
}
int main() {
List P;
P = MakeEmpty();
for(int i = 0; i < 10; i++){
Insert(i,i+1,P);
}
cout << "该顺序表长度为：" << Length(P) << endl;
cout << "第5个元素为：" << FindKth(4,P) << endl;
cout << "--删除第4个元素--" << endl;
Delete(4,P);
cout << "删除后第5个元素为：" << FindKth(4,P) << endl;
cout << "表中是否有元素3(有则显示其下标无则显示-1)：" << Find(3,P) << endl;
cout << "表中是否有元素5(有则显示其下标无则显示-1)：" << Find(5,P) << endl;
delete [] P;
return 0;
}Output results:
Sequential list length: 10 5th element: 4 —Delete 4th element— 5th element after deletion: 5 Does element 3 exist (show index if yes, -1 if no): -1 Does element 5 exist (show index if yes, -1 if no): 4
III. Linked Storage of Linear Lists
Important! A linked list does not require logically adjacent elements to be physically adjacent; it establishes logical relationships between data elements through “links.” Its insertion and deletion operations do not require moving data elements, only modifying links.
1. Definition
typedef struct LNode *List;
struct LNode {
ElementType Data;
List Next;//存放指向下一个结点的指针
}L;
List PtrL;2. Operations
The basic operations are:
1.List Insert(ElementType X, int i, List PtrL);//Insert (insert a new node with value X after the (i-1)-th (1<=i<=n+1) node) 2.List FindKth(int K, List PtrL);//Search by index: find the K-th element in the linked list List Find(ElementType X, List PtrL);//Search by value: find element K 3.List Delete(int i, List PtrL);//Delete (delete the node at position i in the linked list) 4.int Length(List PtrL)//Get list length
(1) Insertion Operation
Insert a new node with value X after the (i-1)-th (1 <= i <= n+1) node. (1) First construct a new node, point s to it // malloc to allocate space, assign s’s Data to X (2) Then find the (i-1)-th node in the linked list, point p to it (3) Then modify pointers to insert the node (insert new node s after p) // First assign p’s original Next to s’s Next pointer, then point p’s Next to s
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 = Find(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;
}
}(2) Search
Returns a pointer to the found node, or NULL if not found.
1. Search by Value: Find
Search by value: find element K
List Find(ElementType X, List PtrL) {
List p = PtrL;
while(p != NULL && p->Data != X)
p = p->Next;
if(p == NULL) {
cout << "找不到该元素" << endl;
return NULL;
} else return p;
}2. Search by Index: FindKth
Search by index: find the K-th element in the linked list
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 { //否则返回空指针
cout << "找不到该元素" << endl;
return NULL;
}
}(3) Deletion Operation
Delete the node at position i in the linked list. (1) First find the (i-1)-th node, point p to it; // Find(i-1, PtrL); (2) Then use pointer s to point to the node to be deleted (the node after p) // s = p->Next; (3) Then modify the pointer to delete the node pointed to by s // p->Next = s->Next; (4) Finally free the space of the node pointed to by s! // free(s)
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;
}
}(4) Get List Length
int Length(List PtrL) {
List p = PtrL;//p指向表的第一个节点
int j = 0;
while(p) {
p = p->Next;
j++;
}
return j;
}3. Complete Code Demonstration
//链表
#include <iostream>
using namespace std;
typedef int ElementType;
const int MAXSIZE = 1000;
// 1.定义部分
struct LNode;
typedef LNode *List;
struct LNode {
ElementType Data;
List Next; //存放指向下一个结点的指针
};
List Insert(ElementType X,int i,List PtrL);
//插入(在第i-1(1<=i<=n+1)个结点后插入一个值为X的新结点)
List FindKth(int K, List PtrL); //按序号查找查找 查找链表中第K个元素
List Find(ElementType X, List PtrL); //按值查找: 查找元素K
List Delete(int i, List PtrL); //删除操作(删除链表第i个位置上的结点)
int Length(List PtrL); //求表长
// 2.操作函数
//(1) 插入操作 在第i-1(1 ≤ i ≤ n+1)个结点后插入一个值为X的新结点
List Insert(ElementType X, int i, List PtrL) {
List p, s;
if (i == 1) { //新节点插入到表头
s = new struct LNode; //申请、填装节点
s->Data = X;
s->Next = PtrL;
return s; //返回新表头指针
}
p = Find(i - 1, PtrL); //查找第i-1个结点
if (p == NULL) { //第i-1个不存在 无法插入
printf("参数i错");
return NULL;
} else {
s = new struct LNode; //申请、填装结点
s->Data = X;
s->Next = p->Next; //新节点插入在第i-1个节点的后面
p->Next = s;
return PtrL;
}
}
//(2) 查找 找到则返回指向该结点的指针，找不到返回NULL
List Find(ElementType X, List PtrL) {//按值查找 查找元素X
List p = PtrL;
while(p != NULL && p->Data != X)
p = p->Next;
if(p == NULL) {
cout << "找不到该元素" << endl;
return NULL;
} else return p;
}
List FindKth(int K, List PtrL) {//按序号查找 查找第K个元素
List p = PtrL;
int i = 1;
while (p != NULL && i < K) {
p = p->Next;
i++;
}
if(i == K) return p;//找到第K个返回指针
else { //否则返回空指针
cout << "找不到该元素" << endl;
return NULL;
}
}
//(3) 删除 删除链表第i个位置上的结点
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;
delete [] 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; //从链表中删除
delete [] s; //释放被删除结点的空间
return PtrL;
}
}
//(4) 求表长
int Length(List PtrL) {
List p = PtrL;//p指向表的第一个节点
int j = 0;
while(p) {
p = p->Next;
j++;
}
return j;
}
int main() {
List P = NULL;
for (int i = 0; i < 10; i++) {
P = Insert(i, 1, P);// 头插法 插入元素在表头
}
List s;
cout << "该链表长度为：" << Length(P) << endl;
cout << "第4个元素为：";
s = FindKth(4, P);
if(s) cout << s->Data << endl;
cout << "--删除第4个元素--" << endl;
Delete(4, P);
cout << "删除后第4个元素为：" ;
s = FindKth(4, P);
if (s) cout << s->Data << endl;
cout << "表中是否有元素6：";
s = Find(6, P);
if (s) cout << s->Data << endl;
cout << "表中是否有元素5：";
s = Find(5, P);
if (s) cout << s->Data << endl;
delete[] P;
return 0;
}Output results:
Linked list length: 10 4th element: 6 —Delete 4th element— 4th element after deletion: 5 Does element 6 exist: Element not found Does element 5 exist: 5
喜欢的话，留下你的评论吧～