线性结构
顺序表
/*
malloc(m)函数:开辟m字节长度的地址空间,并返回这段空间的首地址
sizeof(x)函数:计算变量x的长度
free(*p)函数:释放指针p所指变量的存储空间,即彻底删除一个变量
*/
#include <stdio.h>
#include <stdlib.h>
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAX_SIZE 1000 //顺序表初始长度
typedef int Status; //Status 是函数的类型,其值是函数结果状态代码
typedef int ElemType; //ElemType 是元素类型
//顺序表存储结构(静态数组实现)
// typedef struct {
// ElemType e[MAX_SIZE]; //数据
// int length; //当前长度
// } SqList;
//顺序表存储结构(动态数组实现)
typedef struct {
ElemType *e; //元素数据
int length; //当前长度
} SqList;
//初始化顺序表
Status initList(SqList *list) {
list->e = (ElemType*)malloc(sizeof(ElemType) * MAX_SIZE);
if (!list->e) {
printf("分配内存失败\n");
exit(OVERFLOW);
}
list->length = 0;
printf("初始化顺序表成功\n");
return OK;
}
//销毁顺序表
void distroyList(SqList *list) {
if (list->e) {
free(list->e); //free释放指针指向的空间
printf("销毁成功\n");
}
}
//清空顺序表,顺序表将从头开始存储(覆盖),但并不销毁原有空间
void clearList(SqList *list) {
list->length = 0; //长度重置为0
printf("清空成功\n");
}
//求顺序表长度
int getLength(SqList *list) {
return list->length;
}
//判断顺序表是否为空
bool isEmpty(SqList *list) {
return list->length ? 0 : 1; //1为空,0为不空
}
//获取第k个元素,平均时间复杂度:O(1)
int getElem(SqList *list, int k) {
if (k < 1 || k > list->length) return ERROR;
return list->e[k - 1]; //第k - 1个单元存储着第k个数据
}
//查找元素x, 平均时间复杂度:O(n)
int locateElem(SqList *list, ElemType x) {
for(int i = 0; i < list->length; i ++ )
if (list->e[i] == x) return i + 1; //查找成功,返回序号
return 0; //查找失败
}
//在第k个位置插入元素, 平均时间复杂度:O(n)
Status insertElem(SqList *list, int k, ElemType x) {
// n + 1的位置是可以插入的,为最后的位置
if (k < 1 || k > list->length + 1 || list->length == MAX_SIZE) return ERROR;
for (int i = list->length - 1; i >= k - 1; i -- ) {
list->e[i + 1] = list->e[i];
}
list->e[k - 1] = x;
list->length ++ ;
printf("[%d]=%d,插入成功\n", k - 1, x);
return OK;
}
//删除第k个位置的元素, 平均时间复杂度:O(n)
Status delElem(SqList *list, int k) {
if (k < 1 || k > list->length) return ERROR;
for (int i = k - 1; i < list->length; i ++ )
list->e[i] = list->e[i + 1];
list->length --;
return OK;
}
int main() {
SqList list;
initList(&list);
insertElem(&list, 1, 520);
insertElem(&list, 2, 1314);
delElem(&list, 1);
printf("顺序表第1个元素:%d\n", getElem(&list, 1));
printf("顺序表长度为:%d\n", getLength(&list));
printf("顺序表是否为空(1为空,0为不空):%d\n", isEmpty(&list));
printf("查找元素1314的位置:%d\n", locateElem(&list, 1314));
clearList(&list);
distroyList(&list);
return 0;
}
单链表
#include <stdio.h>
#include <stdlib.h>
typedef int E;
//单链表存储结构
typedef struct Node {
E data;
struct Node *next;
}Node, *LinkList;
//初始化结点,并返回结点地址
LinkList init(int x = 0) {
LinkList node = (LinkList)malloc(sizeof(Node));
node->next = NULL;
node->data = x;
}
//在第k个位置插入数据x
void insert(LinkList l, int k, E x) {
LinkList p = l;
int j = 0;
while (p && j < k - 1) p = p->next, j ++ ;
if (!p || j != k - 1) return;
LinkList q = init(x);
q->next = p->next;
p->next = q;
}
//查找第k个元素, 找不到则返回-1
E getK(LinkList l, int k) {
int j = 0;
LinkList p = l->next;
while (p && j < k - 1) p = p->next, j ++ ;
if (!p || j != k - 1) return -1;
return p->data;
}
//按值查找, 查找值为x的位置,返回结点地址
LinkList locateE(LinkList l, E x) {
LinkList p = l->next;
while (p && x != p->data) p = p->next;
if (!p || x != p->data) return NULL;
return p;
}
//删除第k个元素
void delK(LinkList l, int k) {
LinkList p = l;
int j = 0; //从头结点开始
while (p->next && j < k - 1) p = p->next, j ++ ; //走到k - 1的位置上
if (!(p->next) || j != k - 1) return ;
p->next = p->next->next;
}
//生成数据
void randomData(LinkList l) {
for (int i = 1; i <= 100; i ++ ) {
insert(l, i, i);
}
}
//遍历链表,输出链表
void printList(LinkList l) {
int i = 0;
while (l) {
// if (i == 1) printf("(0x%X)", l); //测试按值查找的地址
printf("%d->", l->data);
l = l->next;
i ++ ;
}
printf("NULL\n");
}
int main() {
LinkList list = init(-1);
randomData(list);
printf("第50个元素:%d\n", getK(list, 50));
LinkList t = locateE(list, 1);
printf("链表值为1的地址:0x%X\n", t);
delK(list, 50);
printList(list);
return 0;
}
双链表
#include <stdio.h>
#include <stdlib.h>
typedef int E;
typedef struct Node {
E data;
struct Node *l;
struct Node *r;
}Node, *PNode;
//初始化一个结点, 并返回起始地址
PNode init(E x = 0) {
PNode t = (PNode)malloc(sizeof(Node));
t->data = x;
t->l = t->r = NULL;
return t;
}
//输出所有值
void printNode(PNode node) {
while (node) {
printf("%d->", node->data);
node = node->r;
}
printf("NULL\n");
}
//插入操作, 第k个位置前插入x
void insert(PNode node, int k, E x) {
PNode p = node;
int j = 0;
while (p && j < k - 1) p = p->r, j ++ ;
// printf("j=%d, k=%d\n", j, k - 1);
// printNode(node);
if (!p || j != k - 1) return ;
PNode t = init(x);
if(p->r) p->r->l = t;
t->r = p->r;
p->r = t;
t->l = p;
}
//删除第k个位置的元素
void delNode(PNode node, int k) {
PNode p = node;
int j = 0;
while (p && j < k - 1) p = p->r, j ++ ;
if (!p || j != k - 1) return;
p->r->l = p;
p->r = p->r->r;
}
void randomData(PNode node) {
for (int i = 1; i <= 50; i ++ )
insert(node, i, i);
}
int main() {
PNode p = init(-1);
randomData(p);
delNode(p, 25);
insert(p, 25, 5201314);
printNode(p);
return 0;
}
顺序栈
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define E int
//顺序栈结构体
typedef struct stack {
E *top; //栈顶地址
E *base; //栈底地址
int maxsize; //最大高度
} Stk;
//初始化一个栈
void init(Stk *stk) {
stk->base = (E*)malloc(sizeof(E) * MAXSIZE); //(栈低开始)开辟一段连续空间
if (!stk) printf("分配失败\n");
stk->top = stk->base; //栈顶等于栈底
stk->maxsize = MAXSIZE;
}
//判断栈是否为空
bool empty(Stk stk) {
return stk.top == stk.base ? true : false;
}
//清空栈
void clear(Stk *stk) {
stk->top = stk->base;
}
//销毁栈
void destory(Stk *stk) {
if (stk->base) {
free(stk->base);
stk->maxsize = 0;
stk->base = stk->top = NULL;
}
}
//入栈
void push(Stk *stk, E e) {
if (stk->top - stk->base == stk->maxsize) return; //栈满, 上溢
*(stk->top) = e; //入栈
stk->top ++; //栈顶后移
}
//获取栈顶元素
E top(Stk stk) {
if (stk.top == stk.base) return -1;
return *(stk.top - 1);
}
//出栈
void pop(Stk *stk) {
if (stk->top == stk->base) return ; //栈空, 下溢
stk->top --;
}
int main() {
Stk stk;
init(&stk);
push(&stk, 1);
push(&stk, 2);
pop(&stk);pop(&stk);
printf("栈顶元素:%d\n", top(stk));
// printf("%d\n", stk.maxsize);
// printf("%X\n", stk.top);
// printf("%X\n", stk.base);
// printf("%d\n", empty(stk));
return 0;
}
链栈
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define E int
//链栈是运算受限的单链表, 只能在链表头部进行操作
typedef struct stkNode {
E data;
struct stkNode *next;
}stkNode, *LinkStk;
//判断链栈是否为空
int empty(LinkStk s) {
return s == NULL;
}
//入栈
void push(LinkStk *s, E e) {
stkNode *p = (LinkStk)malloc(sizeof(stkNode));
p->data = e;
p->next = *s;
*s = p;
}
//栈顶元素
E top(LinkStk s) {
if (s == NULL) return -1;
return s->data;
}
//出栈
void pop(LinkStk *s) {
if (*s == NULL) return;
*s = (*s)->next;
}
int main() {
LinkStk s = NULL; //初始化一个链栈, 不需要虚拟头结点
push(&s, 1);
push(&s, 2);
pop(&s);
printf("栈顶元素:%d\n", top(s));
return 0;
}
顺序队列(循环队列)
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 2 //最大队列长度
#define E int //元素类型
//队列的存储结构
typedef struct {
E *base; //队列存储空间
int front; //头指针
int rear; //尾指针
}SqQueue;
//初始化队列
void init(SqQueue *q) {
q->base = (SqQueue*)malloc(sizeof(SqQueue) * MAXSIZE);
if (!q->base) return;
q->front = q->rear = 0;
}
//队列长度(循环队列), 下表从0开始
int getLength(SqQueue q) {
return (q.rear - q.front + MAXSIZE) % MAXSIZE;
}
//入队, 尾指针会指向到下一次存储的位置, 注意需要多开一个空间
void push(SqQueue *q, E x) {
if ((q->rear + 1) % MAXSIZE == q->front) {
printf("队满\n");
return;
}
q->base[q->rear] = x;
q->rear = (q->rear + 1) % MAXSIZE;
}
//出队
E pop(SqQueue *q) {
if (q->front == q->rear) {
printf("队空\n");
return;
}
E x = q->base[q->front];
q->front = (q->front + 1) % MAXSIZE;
return x;
}
//取队头元素
E getHead(SqQueue *q) {
if (q->front != q->rear) return q->base[q->front];
return -1;
}
int main() {
SqQueue q;
init(&q);
push(&q, 1);
// int a = pop(&q); int b = pop(&q);
// printf("a = %d\n", a);
push(&q, 2);
printf("队头元素为: %d\n", getHead(&q));
printf("长度为:%d\n", getLength(q));
return 0;
}
链式队列
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
#define E int
//链式队列存储结构
typedef struct Node{
E data;
struct Node *next;
}QNode, *PQNode;
//头尾指针结构体
typedef struct {
PQNode front; //指向存储结构
PQNode rear;
}Queue, *LinkQueue;
//初始化链式数列
void init(LinkQueue q) {
q->front = q->rear = (PQNode)malloc(sizeof(QNode)); //初始化队头队尾
if (!q->front) return;
q->front->next = NULL; //头结点指向空
}
//入队, 操作队尾
void push(LinkQueue q, E x) {
PQNode t = (PQNode)malloc(sizeof(QNode));
t->data = x;
t->next = NULL;
q->rear->next = t; //队尾加入元素
q->rear = t; //走到队尾
}
//出队, 操作队头
void pop(LinkQueue q) {
if (q->front == q->rear) return ; //空队
PQNode t = q->front->next; //头指针指向的元素
q->front->next = t->next;
if (q->rear == t) q->rear = q->front; //最后一个元素出队后, 尾指针指向头指针
}
//取出队头元素
E getHead(LinkQueue q) {
if (q->front != q->rear)
return q->front->next->data;
return -1;
}
int main() {
LinkQueue q = (LinkQueue)malloc(sizeof(Queue));
init(q);
push(q, 1);
printf("队头:%d\n", getHead(q));
pop(q);
push(q, 2);
printf("队头:%d\n", getHead(q));
return 0;
}
顺序串
链串
块链串
非线性结构