数据结构

图的基本概念图G由顶点V和边E组成，记为G=(V,E)，V一定非空，E可以空。V={v1,v2,……,vn}，|V|表示顶点个数E={(u,v)|u∈V,v∈V}，|E|表示边的条数 有向图<v,w>称为从v到w的弧，也称v邻接到w。v为弧尾，w为弧头。 无向图(v,w)或者(w,v)说，w与v互为邻接点 简单图与多重图简单图：1-不存在重复边（两个顶点的边数不多于一条）；2-不存在到自身的边多重图：反之 完全图若图的顶点数为n，如果|E|=n*(n-1)/2，称为无向完全图；如果|E|=n*(n-1)，称为有向完全图。 子图设有两个图G=(V,E)，G’=(V’,E’)，若V’∈V，E’∈E,则称G’是G的子图。 生成子图若满足V(G’) =...

二叉树的存储结构顺序存储即用数组来存储，从上到下，从左到右，将编号为i的结点存在数组下标为i-1的位置上。适合于完全二叉树与满二叉树；对一般二叉树不友好，浪费空间。 链式存储1234typedef struct BiTNode{ element data; struct BiTNode *left , *right;}BiTNode,*BiTree; 二叉树的遍历与线索二叉树先序遍历的递归操作1234567void PreOrder(BiTree T){ if(T != NULL){ visit(T); PreOrder(T->lchild); PreOrder(T->rchlid); }} 中序遍历的递归操作1234567void InOrder(BiTree T){ if(T != NULL){ InOrder(T->lchild); visit(T); ...

串（String）逻辑结构：受限线性表存储结构：定长顺序存储表示12345#define Max 255typedef struct{ char ch[Max]; int length;}SString; 堆分配存储表示1234typedef struct{ char *ch; int length;}HString; 链式存储表示123456//size被自定义，表示一个结构体中存放多少个字符#define size 4typedef struct{ char ch[size]; LString *next;}LString; 串的简单模式匹配123456789101112131415161718192021222324int SMatch(char a[], char b[]) { char *ptra = a; char *temp = ptra; char *ptrb = b; while (*ptra !=...

栈 是只允许在一端进行插入或者删除的线性表 每接触一种新的数据结构，要从其逻辑结构，存储结构，运算三方面着手。 n个不同元素进栈，出栈的方式有卡特兰数个。 栈的顺序存储方式12345#define Max 100typedef struct Stack{ ELementType data[Max]; int top;}SqStack; 栈空：S.top=-1。栈满：S.top==Max-1。或者分别为0与Max。 顺序栈的基本操作 初始化（设置top值） 入栈 出栈 读栈顶元素 判断空栈 销毁栈 队列 队头：出队列的一端 队尾：入队列的一段 顺序队列的存储方式123456#define Max 100#define element inttypedef struct Queue{ element data[Max]; int...

1. 12345678910111213141516void Del(LinkList *L，int x){ LinkList *p = L->next; LinkList *pre = L; LinkList *temp; while(p != null){ if(p ->data == x){ temp = p;//temp指向被删节点 p=p->next; pre->next = p; free(temp); }else{ pre = p; p = p->next; } }} 其中的if(p ->data == x)可以被替换为任何条件 2. 123456789101112131415void Del(LinkList *L){ ...

折半查找1234567891011121314151617int Search(int a[],int x,int arraySize){ int low = 0 , high = arraySize-1; int mid = (high - low) / 2 + low; while(low <= high){ //注意这里为什么是等于，因为low与high始终在闭区间内运算，当low=high时，仍有一个值没有运算。 if(a[mid] == x){ return x; }else{ if(a[mid] < x){ mid = low +1 ; } if(a[mid] > x){ mid = high - 1; } }...

对长度为n的顺序表L，编写一个时间复杂度为 O（n）、空间复杂度为 O（1）的算法，该算法删除顺序表中所有值为x的数据元素。 时间复杂度为 o（n^2）的暴力算法，即两个for循环。 记录不等于x的元素的个数相比较与粘图片，还是使用福昕pdf复制，我觉得还是手打吧，因为我实在是看不上前两种方式 法一：记录不等于x的个数，直接替换 12345678910void del(SeList *L,Element x){ int k = 0;//记录不等于x的个数 for(int i = 0 ; i < L->length;i++){ if (L->data[i] != x){ L->data[k] = L->data[i]; k++; } } L->length = k ;} 法二：记录等于x的个数，整体移位 1234567891011void del(SeList *L,Element...

线性表 线性表的定义：相同数据类型、有限、序列（有前驱与后继）。 线性表由相同数据类型的有限数据元素组成，数据元素由数据项组成。 顺序表 分为1-静态分配存储空间；2-动态分配存储空间。 优缺点 随机访问，存储密度高 插入、删除难，不够灵活 链表 结点类型描述 1234typedef struct LNode{ ElementType data, struct LNode *next,}LNode,*LinkList - LNode *L 等价于 LinkList L 头结点与头指针的关系 头指针始终指向链表中第一个节点，头节点时带头节点链表中第一个结点，通常不存储信息。 引入头结点所带来的好处 统一了空表与非空表操作 在链表第一个位置上的操作与其他位置一致 单链表的初始化 1234567891011/*说明：初始化链表，返回头节点*/ LinkList InitList() { LinkList L = (LNode*)malloc(sizeof(LNode)); // 创建头节点 if...

逻辑结构 集合 线性结构 树形结构 图状结构或网状结构 1 顺序表和链表都是线性结构，它们的逻辑结构相同。 栈和队列虽然都是线性结构，但它们的操作规则不同，逻辑结构不完全相同。（存在争议）