数据结构
线性表
顺序表
//
// Created by Administrator on 2022/10/7.
// 描述顺序线性表这种常用的数据结构
//
#include <stdio.h>
#define MAXSIZE 100
#define ElemType int
#define OK 1
#define ERROR 0
typedef int Status;
// 定义一个存储整形int的顺序表,最大长度为100,实际长度为length
typedef struct {
ElemType data[MAXSIZE];
int length;
} SqList;
// 初始化线性表
int initSqList(SqList *L, ElemType a[], int n) {
if (n > MAXSIZE) {
printf("failed!");
return ERROR;
}
for (int i = 0; i < n; i++)
L->data[i] = a[i];
L->length = n;
return OK;
}
// 获取元素
// 获取L的第i个元素,并用e返回值
Status GetElem(SqList L, int i, ElemType *e) {
if (L.length == 0 || i < 1 || i > L.length)
return ERROR;
*e = L.data[i - 1];
return OK;
}
// 插入元素
// 在L的第i个位置,插入元素e,L长度加一
Status InsertElem(SqList *L, int i, ElemType e) {
int k;
if (L->length == MAXSIZE)
return ERROR;
if (i < 1 || i > L->length + 1)
return ERROR;
if (i <= L->length) {
for (k = L->length - 1; k >= i - 1; k--)
L->data[k + 1] = L->data[k];
}
L->data[i - 1] = e;
L->length++;
return OK;
}
// 打印线性表
void PrintElem(SqList *L) {
for (int i = 0; i < L->length; i++) {
printf("%d\t", L->data[i]);
}
printf("\n");
}
// 删除元素
// 删除L的第i个元素,并且e返回值,L的长度减1
Status DeleteElem(SqList *L, int i, ElemType *e) {
int k;
if (L->length == 0) {
return ERROR;
}
if (i > L->length || i < 1) {
return ERROR;
}
*e = L->data[i - 1];
if (i < L->length) {
for (k = i; k < L->length; k++) {
L->data[k - 1] = L->data[k];
}
}
L->length--;
return OK;
}
// 修改元素
// 修改L的第i个元素为e
Status UpdateElem(SqList *L, int i, ElemType e) {
if (L->length == 0)
return ERROR;
if (i > L->length || i < 1)
return ERROR;
L->data[i - 1] = e;
return OK;
}
int main() {
SqList L;
ElemType e;
int data[] = {1, 10, 2, 3, 1, 5};
initSqList(&L, data, 6);
PrintElem(&L);
GetElem(L, 3, &e);
printf("获取到了元素:%d\n", e);
InsertElem(&L, 5, 10);
PrintElem(&L);
DeleteElem(&L, 1, &e);
printf("删除了元素:%d\n", e);
PrintElem(&L);
UpdateElem(&L,2,100);
PrintElem(&L);
}
单链表
//
// Created by Administrator on 2022/10/9.
//
#include <stdio.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
typedef int DataType;
typedef int Status;
typedef struct Node {
DataType data;
struct Node *next;
} Node;
// 初始化链表
Node *InitList() {
Node *first = (Node *) malloc(sizeof(Node));
first->next = NULL;
return first;
}
// 输出链表
void PrintNode(Node *first) {
Node *p = first->next;
printf("Node:");
while (p != NULL) {
printf("%d->", p->data);
p = p->next;
}
printf("\n");
}
// 求链表长度
int length(Node *first) {
Node *p = first->next;
int count = 0;
while (p != NULL) {
p = p->next;
count++;
}
return count;
}
// 头插法建立单链表
Node *CreateList_head(DataType a[], int n) {
Node *s = NULL;
Node *first = (Node *) malloc(sizeof(Node));
first->next = NULL; // 初始化头结点
for (int i = 0; i < n; i++) {
s = (Node *) malloc(sizeof(Node)); // 申请内存
s->data = a[i];
s->next = first->next; // 将结点s插入头结点之后
first->next = s;
}
return first;
}
// 尾插法建立单链表
Node *CreateList_end(DataType a[], int n) {
Node *s = NULL;
Node *r = NULL;
Node *first = (Node *) malloc(sizeof(Node)); // 生成头结点
r = first; // 尾指针初始化
for (int i = 0; i < n; i++) {
s = (Node *) malloc(sizeof(Node));
s->data = a[i];
r->next = s; // 将结点s插到尾指针之后
r = s;
}
r->next = NULL; // 单链表建立完毕,将尾指针指针域置空
return first;
}
// 插入元素
Status Insert(Node *first, int i, DataType x) {
Node *s = NULL;
Node *p = first; // 指针初始化,指向头结点
int count = 0;
while (p != NULL && count < i) { // 查找第i-1个节点
p = p->next;
count++;
}
if (p == NULL) {
printf("error location cannot insert!\n");\
return 0;
} else {
s = (Node *) malloc(sizeof(Node)); // 创建一个新节点
s->data = x;
s->next = p->next; // 将结点插入到p之后
p->next = s;
return OK;
}
}
// 删除元素
Status Delete(Node *first, int i, DataType *ptr) {
Node *p = first; // 指针指向头结点
Node *q = NULL;
int count = 0;
while (p != NULL && count < i - 1) { // 查找第i-1个节点
p = p->next;
count++;
}
if (p == NULL || p->next == NULL) { // p节点或者p的后置节点不存在
printf("ERROR location!");
} else { // 找到i节点并删除,通过指针*ptr返回删除后的数据
q = p->next;
*ptr = q->data;
p->next = q->next;
free(q);
return OK;
}
}
// 删除单链表
Status Destory(Node *first) {
Node *p = first;
while (p != NULL) {
first = first->next;
free(p);
p = first;
}
}
// 判断链表是否为空
Status isEmpty(Node *first) {
if (first->next == NULL) {
return OK;
} else {
return ERROR;
}
}
// 按值查找位置
int locate(Node *first, DataType x) {
Node *p = first->next;
int count = 1;
while (p != NULL) {
if (p->data == x) {
return count;
}
p = p->next;
count++;
}
return 0;
}
// 按照位置查找
int Get(Node *first, int i, DataType *ptr) {
Node *p = first->next;
int count = 1;
while (p != NULL && count < i) {
p = p->next;
count++;
}
if (p == NULL) {
printf("error location!");
} else {
*ptr = p->data;
return OK;
}
}
int main() {
DataType x;
int data[5] = {1, 2, 3, 4, 5};
Node *first = CreateList_head(data, 5);
Node *last = CreateList_end(data, 5);
PrintNode(first);
printf("链表的长度为:%d\n", length(first));
PrintNode(last);
printf("链表的长度为:%d\n", length(last));
Insert(first, 1, 10);
PrintNode(first);
Delete(first, 3, &x);
PrintNode(first);
return 0;
}
循环链表
双向链表
队列
栈
二叉树
堆