在编程实现线性表时,如何通过顺序存储和链式存储两种方式来实现初始化、查找、插入和删除操作?请提供具体的代码示例。
时间: 2024-11-08 09:31:20 浏览: 35
实现线性表的基本操作时,顺序存储和链式存储各有优劣。顺序存储依赖于数组,能够快速访问元素,但插入和删除操作效率较低;链式存储依赖于节点间的指针,插入和删除操作效率较高,但访问元素需要遍历链表。以下是如何使用两种存储方式实现线性表操作的具体代码示例:
参考资源链接:[线性表详解:从逻辑结构到操作实现](https://wenku.csdn.net/doc/82q7pycqzv?spm=1055.2569.3001.10343)
顺序存储方式:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 // 线性表的最大长度
typedef int ElementType;
typedef struct {
ElementType data[MAXSIZE];
int length;
} SqList;
// 初始化线性表
void InitList(SqList *L) {
L->length = 0;
}
// 查找元素
int GetElem(SqList L, int i, ElementType *e) {
if (i < 1 || i > L.length) return 0; // 检查i的范围
*e = L.data[i-1];
return 1;
}
// 插入元素
int ListInsert(SqList *L, int i, ElementType e) {
if (L->length == MAXSIZE) return 0; // 线性表已满
if (i < 1 || i > L->length + 1) return 0; // 检查i的范围
for (int k = L->length; k >= i; k--) {
L->data[k] = L->data[k-1];
}
L->data[i-1] = e;
L->length++;
return 1;
}
// 删除元素
int ListDelete(SqList *L, int i, ElementType *e) {
if (L->length == 0) return 0; // 线性表为空
if (i < 1 || i > L->length) return 0; // 检查i的范围
*e = L->data[i-1];
for (int k = i; k < L->length; k++) {
L->data[k-1] = L->data[k];
}
L->length--;
return 1;
}
```
链式存储方式:
```c
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node {
ElementType data;
struct Node *next;
} Node, *LinkList;
// 初始化线性表
LinkList InitList() {
return (LinkList)malloc(sizeof(Node));
}
// 查找元素
Node* GetElem(LinkList L, int i) {
Node *p = L;
int j = 0;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) return NULL;
return p;
}
// 插入元素
void ListInsert(LinkList *L, int i, ElementType e) {
Node *p = GetElem(*L, i-1);
if (!p) return;
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = e;
newNode->next = p->next;
p->next = newNode;
}
// 删除元素
void ListDelete(LinkList L, int i, ElementType *e) {
Node *p = GetElem(L, i-1);
if (!p || !p->next) return;
Node *q = p->next;
*e = q->data;
p->next = q->next;
free(q);
}
```
以上代码展示了使用C语言进行线性表操作的顺序存储和链式存储实现。顺序存储使用数组,而链式存储使用节点链。在实现初始化、查找、插入和删除操作时,顺序存储的插入和删除操作需要移动大量元素,而链式存储只需改变节点间的指针。读者可以通过《线性表详解:从逻辑结构到操作实现》一书更深入地学习这些概念和更多细节。
参考资源链接:[线性表详解:从逻辑结构到操作实现](https://wenku.csdn.net/doc/82q7pycqzv?spm=1055.2569.3001.10343)
阅读全文