小吃网站建设,58同城网站推广,怎样在工商局网站上做变更,做展示类网站数据结构干货总结#xff08;一#xff09;基础线性表的顺序表示线性表的链式表示单链表双链表循环链表循环单链表循环双链表栈顺序存储链式存储队列队列的定义队列的常见基本操作队列的顺序存储结构顺序队列循环队列队列的链式存储结构树概念二叉树二叉树的创建基础
数据一基础线性表的顺序表示线性表的链式表示单链表双链表循环链表循环单链表循环双链表栈顺序存储链式存储队列队列的定义队列的常见基本操作队列的顺序存储结构顺序队列循环队列队列的链式存储结构树概念二叉树二叉树的创建基础
数据计算机存储的能被计算机识别处理的(音频、视频) 结构数据和数据之间的关系。 算法实现特定功能的求解的描述。 数据元素也称顶点结点或记录。数据的基本单位。 数据项最小单位。 1、数据结构包括数据的逻辑结构 存储结构 数据的运算。 2、计算机解决问题的步骤分析问题 设计相应的算法 编写程序 调试并得到正确结果 3、存储结构 顺序存储 -------数据在计算机内的物理存储 链式存储---------用指针表达数据元素之间的逻辑关系 散列存储/索引存储 -------哈希 4、逻辑结构逻辑结构数据元素关系 ---------描述的数据与数据之间的关系 一对一线性 一对多树形 多对多集合 5、对数据的操作增删改查
线性表的顺序表示
1、静态分配
#define MaxSize 50 //宏定义线性表最大长度为50
typedef struct{ //定义一个结构体ElemType data{maxSize}; //顺序表的元素数组int length; //顺序表当前长度
}SqList; //结构体名2、动态分配
#define InitSize 50 //表长度的初始定义
typedef struct{ //定义一个结构体ElemType *data; //动态分配数组的指针int MaxSize,length; //顺序表最大容量当前个数
}SeqList; //结构体名动态分配和静态分配最主要的区别在于静态分配的是数组动态分配的是指针。指针存储地址当需要用到数据存储的时候再申请空间。 C语言动态分配语句
L.data(ElemType*)malloc(sizeof(ElemType)*InitSize);3、插入
bool ListInsert(SqList L,int i,ElemType e){
//设置成bool类型函数若插入成功返回true否则返回falseif(i1||iL.length1)//判断i的范围是否有效return false;if(L.lengthMaxSize)//当前存储空间已满不能插入return false;for(int jL.length;ji;j--)//将第i个元素之后的元素后移L.data[j]L.data[j-1];L.data[i-1]e; //在位置i处放入eL.length; //线性表长度加1return true;
}4、删除
bool ListDelete(SqList L,int i,Elemtype e){//引用e将删除的数赋值给eif(i1||iL.length)//判断i的范围是否有效return false;eL.data[i-1]; //将被删除的元素赋值给efor(int ji;jL.length;j)//将i位置后的元素前移L.data[j-1]L.data[j];L.length--; //线性表长度减1return true;
}5、查找
int LocateElem(SqList L,ElemType e){int i;for(i0;iL.length;i)if(L.data[i]e)return i1;//i是数组下标i1是位序return 0;//查找失败退出循环
}线性表的链式表示
由于顺序表的插入、删除操作需要移动大量的元素影响了运行效率由此引入了线性表的链式存储。链式存储线性表时不需要使用地址连续的存储单元即它不要求逻辑上相邻的两个元素在物理位置上也相邻它是通过 “ 链 ” 建立起数据元素之间的逻辑关系因此对线性表的插入、删除不需要移动元素而只需要修改指针。
线性表的链式存储又称为单链表它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立起数据元素之间的线性关系对每个链表结点除了存放元素自身的信息之外还需要存放一个指向其后继的指针。单链表结点结构如下图其中data 为数据域存放数据元素next 为指针域存放其后继结点的地址。
单链表
头插法建立单链表
LinkList CreateList1(LinkList L){//从表尾到表头逆向建立单链表 L 每次均在头结点之后插入元素LNode *s ;int x ;L ( LinkList ) malloc ( sizeof( LNode ) ) ; // 创建头结点L-next NULL ; // 初始为空链表scanf ( %d , x) ; // 输入结点的值while( x! 9999){ // 输入9999 表示结束s ( LNode * ) malloc ( sizeof( LNode ) ) ; // 创建新结点s-data x ;s-next L-next; // 将新结点插入表中L为头指针L-next s ;scanf ( %d , x) ; } // while 结束return L;}采用头插法建立单链表读入数据的顺序与生成的链表中元素的顺序是相反的。每个结点插入的时间为 O(1) 设单链表长为 n 则总的时间复杂度为 O( n ) 。
采用尾插法建立单链表
LinkList CreateList2( LinkList L){// 从表头到表尾正向建立单链表 L 每次均在表尾插入元素int x ; // 设置元素类型为整型L ( LinkList ) malloc( sizeof( LNode ) ) ;LNode *s , *r L ; // r 为表尾指针scanf( %d , x ) ; // 输入结点的值while( x! 9999){ // 输入 9999 表示结束s ( LNode * ) malloc(sizeof( LNode ) ) ;s-data x;r-next s ;r s ; // r 指向新的表尾结点scanf( %d , x ) ;}r-next NULL; // 尾结点指针置空return L ;}按序号查找结点值 LNode * GetElem( LinkList L , int i ){// 本算法取出单链表 L 带头结点中第 i 个位置的结点指针int j 1 ; // 计数初始为1即指向第一个结点LNode * p L-next ; // 头结点指针赋给 pif ( i 0 ){return L; // 如果 i 等于 0 则返回头结点}if ( i 1 ){return NULL; // 若 i 无效则返回 NULL}while( p j i ){p p-next ;j;}return p ; // 返回第 i 个结点的指针如果 i大于表长}
按值查找结点
LNode * LocateElem ( LinkList L , ElemType e ){//本算法直接查找单链表 L 带头结点中数据域值等于 e 的结点指针否则返回 NULLLNode * p L-next ;while( p ! NULL P-data ! e){ // 从 第 1 个结点开始查找 data 域为 e 的结点p p-next ;}return p ; // 找到返回该结点指针否则返回 NULL}
插入结点操作 // 将 *s 结点插入到 *p 之前的主要代码片段s-next p-next ; // 修改指针域不能颠倒p-next s ;temp p-data ; // 交换数据域部分p-data s-data ;s-data temp ;删除结点操作 q p-next ; // 令 q 指向 *p 的后继结点p-data p-next-data; // 用后继结点中的数据覆盖要删除结点的数据p-next q-next ; // 将 *q 结点从链中 “ 断开 ”free( q ) ; // 释放后继结点的存储空间双链表
单链表结点中只有一个指向其后继的指针这使得单链表只能从头结点依次顺序地向后遍历。 若要访问某个结点的前驱结点插入、删除操作时只能从头开始遍历访问后继结点的时间复杂度为 O(1) 访问前驱结点的时间复杂度为 O( n ) 。为了克服单链表的删除缺点引入了双链表双链表结点中有两个指针 prior 和 next 分别指向其前驱结点和后继结点。 typedef struct DNode { // 定义双链表结点类型ElemType data ; // 数据域struct DNode *prior , * next ; // 前驱和后继指针}DNode , * DLinkList ;双链表的插入操作 双链表的删除操作
循环链表
循环单链表
循环单链表和单链表的区别在于表中最后一个结点指针不是 NULL 而改为指向头结点从而整个链表形成了一个环如下图所示 在循环单链表中表尾结点 *r 的 next 域指向 L 故表中没有指针域为 NULL 的结点因此循环单链表的判空条件不是头结点的指针是否为空而是它是否等于头指针。 循环单链表的插入、删除算法与单链表几乎一样所以不同的是如果操作是在表尾进行则执行的操作不同以让单链表继续保持循环的性质。当然正是因为循环单链表是一个 “ 环 ” 因此在任何一个位置的插入和删除操作都是等价的无须判断是否是表尾。在单链表中只能从表头结点开始往后顺序遍历整个链表而循环单链表可以从表中的任一结点开始遍历整个链表。有时对单链表常做的操作是在表头和表尾进行的此时可以对循环单链表不设头指针而仅设尾指针从而使得操作效率更高。其原因是若设的是头指针对表尾进行操作需要 O( n ) 的时间复杂度而如果设的是尾指针 r r-next 即为头指针对于表头与表尾进行 操作都只需要 O( 1 ) 的时间复杂度。
循环双链表
由循环单链表的定义不难推出循环双链表不同的是在循环双链表中头结点的 prior 指针还要指向表尾结点如下图所示
栈
栈是一种特殊的线性表仅允许在表的一端进行插入和删除运算。这一端被称为栈顶top相对地把另一端称为栈底bottom。向一个栈插入新元素又称作进栈、入栈或压栈push它是把新元素放到栈顶元素的上面使之成为新的栈顶元素从一个栈删除元素又称作出栈或退栈pop它是把栈顶元素删除掉使其相邻的元素成为新的栈顶元素。所以栈具有“后入先出”的特点LIFO。
顺序存储
一般的把数组的第一个位置[0]作为栈底再单独定义一个变量指示栈顶
/* 顺序栈结构 */
typedef int SElemType;
typedef struct
{SElemType data[MAXSIZE];int top; /* 用于栈顶指针 */
}SqStack;/* 构造一个空栈S */
Status InitStack(SqStack *S)
{ /* S.data(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */S-top-1;return OK;
}/* 把S置为空栈 */
Status ClearStack(SqStack *S)
{ S-top-1;return OK;
}/* 若栈S为空栈则返回TRUE否则返回FALSE */
Status StackEmpty(SqStack S)
{ if (S.top-1)return TRUE;elsereturn FALSE;
}/* 返回S的元素个数即栈的长度 */
int StackLength(SqStack S)
{ return S.top1;
}/* 若栈不空则用e返回S的栈顶元素并返回OK否则返回ERROR */
Status GetTop(SqStack S,SElemType *e)
{if (S.top-1)return ERROR;else*eS.data[S.top];return OK;
}/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{if(S-top MAXSIZE -1) /* 栈满 */{return ERROR;}S-top; /* 栈顶指针增加一 */S-data[S-top]e; /* 将新插入元素赋值给栈顶空间 */return OK;
}/* 若栈不空则删除S的栈顶元素用e返回其值并返回OK否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{ if(S-top-1)return ERROR;*eS-data[S-top]; /* 将要删除的栈顶元素赋值给e */S-top--; /* 栈顶指针减一 */return OK;
}/* 从栈底到栈顶依次对栈中每个元素显示 */
Status StackTraverse(SqStack S)
{int i;i0;while(iS.top){visit(S.data[i]);}printf(\n);return OK;
}链式存储
在栈的链式结构实现中一般把链表的头指针做为栈顶按照先后顺序来看的这种定义与数组正好是反过来的这是由于在顺序结构中查找是非常方便的插入和移动不方便。但是链式结构只知道头指针查找不方便但是插入方便而对于栈而言我们需要知道栈顶的位置所以就干脆把链表头指针作为栈顶吧同时由于插入方便每次在链的开头插入一个结点很容易。
typedef int SElemType;
/* 链栈结构 */
typedef struct StackNode
{SElemType data;struct StackNode *next;
}StackNode,*LinkStackPtr;/* 构造一个空栈S */
Status InitStack(LinkStack *S)
{ S-top (LinkStackPtr)malloc(sizeof(StackNode));if(!S-top)return ERROR;S-topNULL;S-count0;return OK;
}/* 把S置为空栈 */
Status ClearStack(LinkStack *S)
{ LinkStackPtr p,q;pS-top;while(p){ qp;pp-next;free(q);} S-count0;return OK;
}/* 若栈S为空栈则返回TRUE否则返回FALSE */
Status StackEmpty(LinkStack S)
{ if (S.count0)return TRUE;elsereturn FALSE;
}/* 返回S的元素个数即栈的长度 */
int StackLength(LinkStack S)
{ return S.count;
}/* 若栈不空则用e返回S的栈顶元素并返回OK否则返回ERROR */
Status GetTop(LinkStack S,SElemType *e)
{if (S.topNULL)return ERROR;else*eS.top-data;return OK;
}/* 插入元素e为新的栈顶元素 */
Status Push(LinkStack *S,SElemType e)
{LinkStackPtr s(LinkStackPtr)malloc(sizeof(StackNode)); s-datae; s-nextS-top; /* 把当前的栈顶元素赋值给新结点的直接后继见图中① */S-tops; /* 将新的结点s赋值给栈顶指针见图中② */S-count;return OK;
}/* 若栈不空则删除S的栈顶元素用e返回其值并返回OK否则返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{ LinkStackPtr p;if(StackEmpty(*S))return ERROR;*eS-top-data;pS-top; /* 将栈顶结点赋值给p见图中③ */S-topS-top-next; /* 使得栈顶指针下移一位指向后一结点见图中④ */free(p); /* 释放结点p */ S-count--;return OK;
}
/* 从栈底到栈顶依次对栈中每个元素显示 */
Status StackTraverse(LinkStack S)
{LinkStackPtr p;pS.top;while(p){visit(p-data);pp-next;}printf(\n);return OK;
}队列
队列的定义
队列queue 是只允许在一端进行插入操作而在另一端进行删除操作的线性表。 队列是一种先进先出First In First Out的线性表简称FIFO。允许插入的一端称为队尾允许删除的一端称为队头。 队头Front允许删除的一端又称队首。 队尾Rear允许插入的一端。 空队列不包含任何元素的空表。
队列的常见基本操作
InitQueue(Q)初始化队列构造一个空队列Q。 QueueEmpty(Q)判队列空若队列Q为空返回true否则返回false。 EnQueue(Q, x)入队若队列Q未满将x加入使之成为新的队尾。 DeQueue(Q, x)出队若队列Q非空删除队头元素并用x返回。 GetHead(Q, x)读队头元素若队列Q非空则将队头元素赋值给x。
队列的顺序存储结构
顺序队列
队列的顺序实现是指分配一块连续的存储单元存放队列中的元素并附设两个指针队头指针 front指向队头元素队尾指针 rear 指向队尾元素的下一个位置。
#define MAXSIZE 50 //定义队列中元素的最大个数
typedef struct{ElemType data[MAXSIZE]; //存放队列元素int front,rear;
}SqQueue;
初始状态队空条件Q-front Q-rear 0。 进队操作队不满时先送值到队尾元素再将队尾指针加1。 出队操作队不空时先取队头元素值再将队头指针加1。
循环队列
解决假溢出的方法就是后面满了就再从头开始也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。 当队首指针Q-front MAXSIZE-1后再前进一个位置就自动到0这可以利用除法取余运算%来实现。 初始时Q-front Q-rear0。 队首指针进1Q-front (Q-front 1) % MAXSIZE。 队尾指针进1Q-rear (Q-rear 1) % MAXSIZE。 队列长度(Q-rear - Q-front MAXSIZE) % MAXSIZE。 出队入队时指针都按照顺时针方向前进1如下图所示 循环队列队空和队满的判断条件 队满条件 (Q-rear 1)%Maxsize Q-front 队空条件仍 Q-front Q-rear 队列中元素的个数 (Q-rear - Q -front Maxsize)% Maxsize 类型中增设表示元素个数的数据成员。这样队空的条件为 Q-size O 队满的条件为 Q-size Maxsize 。这两种情况都有 Q-front Q-rear 类型中增设tag 数据成员以区分是队满还是队空。tag 等于0时若因删除导致 Q-front Q-rear 则为队空tag 等于 1 时若因插入导致 Q -front Q-rear 则为队满。
循环队列常见基本算法
1循环队列的顺序存储结构
typedef int ElemType; //ElemType的类型根据实际情况而定这里假定为int
#define MAXSIZE 50 //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct{ElemType data[MAXSIZE];int front; //头指针int rear; //尾指针,若队列不空指向队列尾元素的下一个位置
}SqQueue;
2循环队列的初始化
/*初始化一个空队列Q*/
Status InitQueue(SqQueue *Q){Q-front 0;Q-rear 0;return OK;
}
3循环队列判队空
/*判队空*/
bool isEmpty(SqQueue Q){if(Q.rear Q.front){return true;}else{return false;}
}
4求循环队列长度
/*返回Q的元素个数也就是队列的当前长度*/
int QueueLength(SqQueue Q){return (Q.rear - Q.front MAXSIZE) % MAXSIZE;
}
5循环队列入队
/*若队列未满则插入元素e为Q新的队尾元素*/
Status EnQueue(SqQueue *Q, ElemType e){if((Q-rear 1) % MAXSIZE Q-front){return ERROR; //队满}Q-data[Q-rear] e; //将元素e赋值给队尾Q-rear (Q-rear 1) % MAXSIZE; //rear指针向后移一位置若到最后则转到数组头部return OK;
}
6循环队列出队
/*若队列不空则删除Q中队头元素用e返回其值*/
Status DeQueue(SqQueue *Q, ElemType *e){if(isEmpty(Q)){return REEOR; //队列空的判断}*e Q-data[Q-front]; //将队头元素赋值给eQ-front (Q-front 1) % MAXSIZE; //front指针向后移一位置若到最后则转到数组头部
}
队列的链式存储结构
链队列 队列的链式存储结构表示为链队列它实际上是一个同时带有队头指针和队尾指针的单链表只不过它只能尾进头出而已。 空队列时front和real都指向头结点。 链队列常见基本算法 1链队列存储类型
/*链式队列结点*/
typedef struct {ElemType data;struct LinkNode *next;
}LinkNode;
/*链式队列*/
typedef struct{LinkNode *front, *rear; //队列的队头和队尾指针
}LinkQueue;
当Q-front NULL 并且 Q-rear NULL 时链队列为空。 2链队列初始化
void InitQueue(LinkQueue *Q){Q-front Q-rear (LinkNode)malloc(sizeof(LinkNode)); //建立头结点Q-front-next NULL; //初始为空
}
3链队列入队
Status EnQueue(LinkQueue *Q, ElemType e){LinkNode s (LinkNode)malloc(sizeof(LinkNode));s-data e;s-next NULL;Q-rear-next s; //把拥有元素e新结点s赋值给原队尾结点的后继Q-rear s; //把当前的s设置为新的队尾结点return OK;
}
4链队列出队 出队操作时就是头结点的后继结点出队将头结点的后继改为它后面的结点若链表除头结点外只剩一个元素时则需将rear指向头结点。
/*若队列不空删除Q的队头元素用e返回其值并返回OK否则返回ERROR*/
Status DeQueue(LinkQueue *Q, Elemtype *e){LinkNode p;if(Q-front Q-rear){return ERROR;}p Q-front-next; //将欲删除的队头结点暂存给p*e p-data; //将欲删除的队头结点的值赋值给eQ-front-next p-next; //将原队头结点的后继赋值给头结点后继//若删除的队头是队尾则删除后将rear指向头结点if(Q-rear p){ Q-rear Q-front;}free(p);return OK;
}
树
概念
【树形结构】元素之间存在一对多的关系 【树】树是由根结点和若干棵子树构成的树形结构 【节点】结点是树中的数据元素 【父亲节点】当前结点的直接上级结点 【孩子节点】定义孩子结点是指当前结点的直接下级结点 【兄弟节点】定义兄弟结点是有相同父结点的结点 【堂兄弟节点】定义:堂兄弟结点是父结点在同一层的结点 【祖先节点】定义: 祖先结点是当前结点的直接及间接上级结点 【子孙节点】定义: 子孙结点是当前结点的直接及间接下级结点 【根结点】定义: 根结点是没有父结点的结点 【结点的度】该结点有多少个子树 【树的度】结点度的最大值。 【叶子节点】定义: 叶结点是度为0的结点 【分支节点】定义: 分支结点是度不为0的结点 【节点的度】结点的度是结点含有子树的个数 【节点的层次】定义: 结点的层次是从根结点到某结点所经路径上的层次数 【树的度】定义: 树的度是树内各结点度的最大值 【树的深度】定义: 树的深度是树中所有结点层次的最大值
二叉树
定义 每个节点最多有两棵子树并且严格区分左右的树形结构 二叉树的概念 【左子树】左子树是以当前结点的左孩子结点作为根节点的子树 【右子树】右子树是以当前结点的右孩子结点作为根节点的子树 【满二叉树】满二叉树是最后一层是叶子结点其余结点度是2的二叉树 在不增加层次的基础上不能在添加节点的二叉树 【完全二叉树】完全二叉树是在一棵满二叉树基础上自左向右连续增加叶子结点得到的二叉树 完全二叉树是在一棵满二叉树基础上自右向左连续删除叶子结点得到的二叉树 叶子节点只出现在最下两层最下层的叶子节点都是左连续出现的如果倒数第二层有叶子节点 一定是右侧连续的 满二叉树一定是完全二叉树完全二叉树不一定的满二叉树。 二叉树形态 二叉树的性质 第i层最多有2^i-1个结点 有i层的二叉树最多能有2^i-1个结点 假定度0的结点数为N0度为1的结点数为N1度为2的结点数为N2 总度数N12N2 总结点数N0N1N2N12N21 N0N21 叶子结点的个数度为2的节点个数1
二叉树的创建
typedef struct node
{
char data;
struct node *left;
struct node *right;
}node;#include tree.h
//创建结点
node *create_node(char data)
{
node *p(node*)malloc(sizeof(node));
p-datadata;
return p;
}
//创建二叉树
node *create_tree()
{
//实现通过终端输入#表示子树结束
char c\0;
scanf(%c,c);
getchar();//吸收垃圾字符
if(c#)
{
return NULL;
}
//如果传入的数据有意义就创建结点
node *Tcreate_node(c);
//二叉树的每棵子树都要调用创建树的函数
T-leftcreate_tree();
T-rightcreate_tree();
return T;
}
//先序遍历:根左右
void pri_node(node *T)
{
if(TNULL)
{
return;
}
printf(%c,T-data);
pri_node(T-left);
pri_node(T-right);
}
//中序遍历
void in_order(node *T)
{
if(TNULL)
{
return;
}
in_order(T-left);
printf(%c,T-data);
in_order(T-right);
}
//后序遍历
void post_node(node *T)
{
if(TNULL)
{
return;
}
post_node(T-left);
post_node(T-right);
printf(%c,T-data);
}
