单链表
2018-09-11 本文已影响6人
qianranow
0. 顺序存储结构
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
typedef struct Node {
int Data[MAXSIZE];
int Last;
}LNode, *List;
List MakeEmpty() {
List PtrL;
PtrL = (List)malloc(sizeof(LNode));
PtrL -> Last = -1;
return PtrL;
}
int Find(int X, List PtrL) {
int i = 0;
while (i <= PtrL -> Last && PtrL -> Data[i] != X) { // 根据索引找元素
i++;
}
if (i > PtrL -> Last) { // 没有找到返回 -1
return -1;
} else { // 找到后返回存储位置
return i;
}
}
void Insert(int X, int i, List PtrL) {
if (PtrL -> Last == MAXSIZE - 1) {
printf("表满");
return;
}
if (i < 1 || i > PtrL -> Last + 2) {
printf("插入位置不合法");
return;
}
for (int j = PtrL -> Last; j >= i - 1; j--) {
// 元素倒叙向后移动
PtrL -> Data[j + 1] = PtrL -> Data[j];
}
// 新元素插入
PtrL -> Data[i - 1] = X;
PtrL -> Last++;
return;
}
void Delete(int i, List PtrL) {
if (i < 1 || i > PtrL -> Last + 1) {
printf("不存在第 %d 个元素\n", i);
return;
}
for (int j = i; j <= PtrL -> Last; j++) {
PtrL -> Data[j - 1] = PtrL -> Data[j];
}
PtrL -> Last--;
return;
}
1. 链式存储结构
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int Data;
struct Node *Next;
}LNode, *List;
int Length(List PtrL) {
// 第一个结点
List p = PtrL;
int i = 0;
while (p) {
p = p -> Next;
i++;
}
return i;
}
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;
} else {
return NULL;
}
}
List Find(int X, List PtrL) {
List p = PtrL;
while (p != NULL && p -> Data != X) {
p = p -> Next;
}
return p;
}
List Insert(int X, int i, List PtrL) {
List p, s;
if (i == 1) { // 插在头指针
s = (List)malloc(sizeof(LNode));
s -> Data = X;
s -> Next = PtrL;
return s;
}
// 查找第 i - 1 位置结构体指针
p = FindKth(i - 1, PtrL);
if (p == NULL) {
printf("参数 i 错误");
return NULL;
} else {
s = (List)malloc(sizeof(LNode));
s -> Data = X;
s -> Next = p -> Next;
p -> Next = s;
return PtrL;
}
}
List Delete(int i, List PtrL) {
List p, s;
if (i == 1) {
s = PtrL;
if (PtrL != NULL) {
PtrL = PtrL -> Next;
} else {
return NULL;
}
free(s);
return PtrL;
}
p = FindKth(i - 1, PtrL);
if (p == NULL) {
printf("第 %d 个结点不存在", i - 1);
return NULL;
} else if (p -> Next == NULL) {
printf("第 %d 个结点不存在", i);
return NULL;
} else {
s = p -> Next;
p -> Next = s -> Next;
free(s);
return PtrL;
}
}
