寒假阶段学习总结

线性表：n个数据元素的有限序列（数据元素是同一个类型

链表：优点：内存动态化

栈：先进后出原则(类似弹夹)

队列：先进先出

二叉树：子树：树枝  节点：树叶  节点的度：叶子数目

哈夫曼树： 带权路径长度最短（带权路径长度：树中所有的叶结点的权值乘上其到根结点的路径长度

dfs/bfs

数据结构代码(self)

#include<stdio.h> #include<stdlib.h> //双向链表 typedef int elemtype;//链表存储结构 typedef struct Node{ int data; struct node* next; struct node*prev; }node; node* init(){//初始化 node* head = (node*)malloc(sizeof(node)); head->data = 0; head->prev = NULL; head->next = NULL; return head; } int inserthead(node* L, elemtype e) {//头插法 node* p = (node*)malloc(sizeof(node)); p->data = e; p->prev = L; p->next = L->next; if (L->next != NULL) { L->next->prev = p; L->next = p; return 1; } } node* gettail(node* L) {//获取尾结点 node* p = L; while (p->next != NULL) { p = p->next; } return p; } node* inserttail(node* tail, elemtype e) {//尾插法 node* p = (node*)malloc(sizeof(node)); p->data = e; p->prev = tail; tail->next = p; p->next = NULL; return p; } int insertnode(node* L, int pos, elemtype e) {//指定位置插入 node* p = L; int i = 0; while (i < pos - 1) { p = p->next; i++; if (p = NULL) { return 0; } } } int delectnode(node* L, int pos) {//删除指定位置节点 node* p = L;int i = 0; while (i < pos - 1) { p->next; i++; if (p = NULL) { return 0; } } if (p->next = NULL) { printf("位置错误"); return 0; } node* q = p->next; p->next = q->next; free(q); return 1; } void listnode(node* L) {//遍历 node* p = L->next; while (p != NULL) { printf("%d", p->data); p = p->next; } printf("\n"); } int listlength(node* L) {//获取链表长度 node* p = L; int len = 0; while (p != NULL) { p = p->next; len++; } return len; } void freelist(node* L) {//释放链表 node* p = L->next; node* q; while (p != NULL) { q = p->next; free(p); p = q; } L->next = NULL; } //栈 //栈的顺序结构实现 #define max 100//初始化 typedef int elemtype; typedef struct { elemtype data[max]; int top; }stack; void initlist(stack* s) { s->top = -1; } int isempty(stack* s) {//判断栈是否为空 if (s->top = -1) { printf("空");return 1; } else { return 0; } } int pop(stack* s, elemtype *e) {//出栈 if (s->top = -1) { printf("空\n"); return 0; } *e = s->data[s->top]; s->top--; return 1; } int push(stack* s, elemtype e) {//进栈 if (s->top >= max - 1) { printf("满了\n"); return 0; } s->top++; s->data[s->top] = e; return 1; } //栈的链式结构实现 typedef int elemtype;//初始化 typedef struct Stack { elemtype data; struct stack* next; }stack; stack* init() { stack* s = (stack*)malloc(sizeof(stack)); s->data = 0; s->next = NULL; return s; } int push(stack* s, elemtype e) {//进栈 stack* p = (stack*)malloc(sizeof(stack)); p->data = e; p->next = s->next; s->next = p; return 1; } int pop(stack* s, elemtype* e) {//出栈 if (s->next = NULL) { printf("空\n"); return 0; } *e = s->next->data; stack* q = s->next; s->next = q->next; free(q); return 1; } int gettop(stack* s, elemtype* e) {//获取栈顶元素 if (s->next = NULL) { printf("空\n"); return 0; } *e = s->next->data; return 1; } //队列 #define max 100 typedef int elemtype; typedef struct {//顺序结构—初始化 elemtype data[max]; int front;int rear; }queue; void initqueue(queue* q) { q->front = 0; q->rear = 0; } int isempty(queue* q) {//判断队列是否为空 if (q->front = q->rear) { printf("空\n");return 1; } else { return 0; } } elemtype dequeue(queue* q) {//出队 if (q->front == q->rear) { printf("空\n");return 0; } elemtype e = q->data[q->front]; q->front++; return e; } int equeue(queue* q, elemtype e) {//入队 if (q->rear >= max) { if (!queuefull(0)) { return 0; } } q->data[q->rear] = e; q->rear++; return 1; } int queuefull(queue* q) {//队列满了，调整队列 if (q->front > 0) { int step = q->front; for (int i = q->front;i <= q->rear;++i) { q->data[i - step] = q->data[i]; } q->front = 0; q->rear = q->rear - step; return 1; } else { printf("已满\n"); return 0; } } int gethead(queue* q, elemtype* e) {//获取队头数据 if (q->front == q->rear) { printf("空\n");return 0; } *e = q->data[q->front]; return 1; } typedef struct {//动态内存分配 elemtype* data; int front;int rear; }queue; queue* initqueue() { queue* q = (queue*)malloc(sizeof(queue)); q->data = (elemtype*)malloc(sizeof(int) * max); q->front = 0; q->rear= 0; return q; } //循环队列 int equeue(queue* q, elemtype e) {//入队 if ((q->rear + 1) % max = q->front) { printf("满\n"); return 0; } q->data[q->rear] = e; q->rear = (q->rear + 1) % max; return 1; } int dequeue(queue* q, elemtype* e) {//出队 if (q->front = q->rear) { printf("空\n"); return 0; } *e = q->data(q->front); q->front = (q->front + 1) % max; return 1; } //链式结构 typedef struct queuenode { elemtype data; struct queuenode* next; }queuenode; typedef struct { queuenode* front; queuenode* rear; }queue; queue* initqueue() {//初始化 queue* q = (queue*)malloc(sizeof(queue)); queuenode* node = (queuenode*)malloc(sizeof(queuenode)); node->data = 0; node->next = NULL; q->front = node; q->rear = node; return q; } int isempty(queue* q) {//判断队列是否为空 if (q->front = q->rear) { printf("空\n"); return 1; } else { return 0; } } void equeue(queue* q, elemtype e) {//入队尾插法 queuenode* node = (queuenode*)malloc(sizeof(queuenode)); node->data = e; node->next = NULL; q->rear->next = node; q->rear = node; } int dequeue(queue* q, elemtype* e) {//出队 queuenode* node = q->front->next; *e = node->data; q->front->next = node->next; if (q->rear = node) { q->rear = q->front; } free(node); return 1; } //递归 int fun(int n) {//计算1—n的和 if (n == 1) { return 1; } else { return fun(n - 1) + n; } } //二叉树 typedef char elemtype;//便于快速改变数据类型 typedef struct Treenode {//存储结构——链式结构 elemtype data; Treenode * lchild; Treenode * rchild; }treenode; typedef treenode* bitree; void preorder(bitree t) {//前序遍历 if (t = NULL) { return; } printf("%c", t->data); preorder(t->lchild); preorder(t->rchild); } void inorder(bitree t) {//中序遍历 if (t = NULL) { return; } inorder(t->lchild); printf("%c", t->data); inorder(t->rchild); } void postorder(bitree t) {//后序遍历 if (t = NULL) { return; } postorder(t->lchild); postorder(t->rchild); printf("%c", t->data); } void iterpreorder(stack* s, bitree t) {//非递归前序遍历 while (t != NULL || isempty(s) != 0) { while (t != NULL) { printf("%c", t->data); push(s, t); t = t->lchild; } pop(s, &t); t = t->rchild; } } //线索二叉树 typedef char elemtype; typedef struct threadnode {//存储结构 char data; struct threadnode* lchild; struct threadnode* rchild; int ltag; int rtag; }threadnode; typedef threadnode* threadtree; void threading(threadtree t) {//具体线索化 if (t != NULL) { threading(t->lchild); if (t->lchild = NULL) { t->ltag = 1;t->lchild = prev; } if (prev->rchild = NULL) { prev->rtag = 1;prev->rchild = t; } prev = t; threading(t->rchild); } } void inorder(threadtree t) {//使用线索进行遍历 threadtree curr; curr = t->lchild; while (curr != t) { while (curr->ltag = 0) { curr = curr->lchild; } printf("%c", curr->data); while (curr->rtag = 1 && curr->rchild != t) { curr = curr->rchild; printf("%c", curr->data); } curr = curr->rchild; } printf("\n"); } //哈夫曼树 void huffmancoding(huffmantree ht, huffmancode* hc, int n) { *hc = (huffmancode)malloc((n + 1) * sizeof(char*)); char* cd = (char*)malloc(n * sizeof(char)); cd[n - 1] = '\0'; for (int i = 0;i < n;i++) { int start = n - 1; int c = i; int j = ht[i].parent; while (j != 0) { if (ht[j].left == c) cd[--start] = '0'; else cd[--start] = '1'; c = j; j = ht[j].parent; } (*hc)[i] = (char*)malloc((n - start) * sizeof(char)); strcpy((*hc)[i], &cd[start]); } free(cd); } //二分查找——递归 int recursion_binarysearch(int* a, const int& x, int left, int right) { int middle = (left + right) / 2; if (x = a[middle]) { return middle; } if (left = right) { return 0; } else if (x > a[middle]) { return recursion_binarysearch(a, x, middle + 1, right); } else if (x < a[middle]) { return recursion_binarysearch(a, x, left, middle - 1); } return 0; } //图 #define max 100 typedef struct {//邻接矩阵 char vex[max]; int edge[max][max]; int vexnum, arcnum; }mgraph; #define max 100//带权图/网 #define infintity typedef char vertextype; typedef int edgetype; typedef struct { char vex[max]; int edge[max][max]; int vexnum, arcnum; }mgraph;