线性结构思维导图_编号p1787604-TreeMind树图

笔灵AI论文写作三步搞定，GO>>

当前位置:树图

思维导图模板

IT互联网

互联网干货

线性结构思维导图

免费下载

免费使用文件

U621655065

浏览量：26

2022-12-22 19:50:09

已被使用1次

查看详情

树图思维导图提供线性结构在线思维导图免费制作，点击“编辑”按钮，可对线性结构进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：1e7635b09a21341ad6cbda8950fa027f

线性表栈和队列数组与广义表矩阵的压缩存储模式匹配算法稀疏矩阵

举报/反馈

思维导图大纲

线性结构思维导图模板大纲

线性表

类型定义

定义

由n(n>=0)个数据元素组成的有限并且有序的序列

逻辑结构

只有一个表头元素

只有一个表尾元素

表头元素没有前驱，表尾元素没有后继

除表头元素其余元素都有唯一前驱；除表尾元素其余元素都有唯一后继

储存结构

顺序储存结构

把线性表中的元素，按照逻辑顺寻依次存储，地址连续存储。

链式储存结构

用一组物理位置任意的存储单元来存放线性表的数据结构

基本操作

结构体定义

顺序表

typedef struct{ Elemtype *elem; //数组指针，指示线性表的基地址 int length; //线性表当前长度 int listsize; //当前分配的存储容量 }SqList;

单链表

typedef struct LNode{ Elemtype data; //数据元素的类型 struct LNode *next; //指示结点地址的指针 }LNode,*LinkList;

双向链表

typedef struct DuLNode{ Elemtype data; struct DuLNode *prior,*next; }DuLNode,*DuLinkList;

顺序表操作

初始化

把顺序表的初始长度定义为0：L.length=0

按元素内容查找

顺序遍历：for(i=0;i<L.length ;i++)；逐一判断：if(e==L.data[i])

指定位置返回

顺序指定位置与下标一致：e=L.data[p]；

插入元素

判断插入位置是否达到上限：if(p<0||p>L.length||L.length>MaxSize)；按照顺序查找到需要插入的位置，查找到后表长需要+1： for(j=L.length;j>=i;j--) { L.data[j+1]=L.data[j]; L.data[p]=e; L.length++}；

删除元素

判断能否插入：if(p<0||p>L.length)；从删除位置开始逐渐前移并且修改表长：for(j=i;j<=L.length-1;j++){ L.data[j]=L.data[j+1]; L.length--;}

单链表操作

头插法

head=(Link)malloc(sizeof(Node)); head->next=NULL;

for(int i=0;i<n;i++){ node=(Link)malloc(sizeof(Node)); node->data=a[i]; node->next=head->next; head->next=node; }

尾插法

head=(Link)malloc(sizeof(Node)); head->next=NULL; rear=head;

for(int i=0;i<n;i++){ node=(Link)malloc(sizeof(Node)); node->data=a[i]; rear->next=node; rear=node; } rear->next=NULL;

查找指定结点

while(p){ //遍历这个链表 if(p->next->data==x) //如果指向下一个数据域满足条件 break; //退出遍历 p=p->next; //如果不满足查找下一个 }

指定节点后插入

s->next=p->next; //在p后面插入s p->next=s; //无需遍历，直接插入

删除指定结点

q=p->next; p->next=q->next; free(q);

双链表操作

头插法

Node *node=(Node*)malloc(sizeof(Node)); node->data=data; if(L->data==0){ node->next=L->next; node->pre=L; L->next=node; } else{ node->pre=L; node->next=L->next; L->next->pre=node; L->next=node; }

尾插法

Node *node=L; Node *n=(Node*)malloc(sizeof(Node)); n->data=data; while(node->next) node=node->next; n->next=node->next; node->next=n; n->pre=node;

插入结点

s->next=p->next; s->prior=p; p->next=s; s->next->prior=p; free(p);

删除结点

while(node){ if(node->data==data){ node->pre->next=node->next; node->next->pre=node->pre; free(node); return TRUE; } node=node->next; }

顺序表和链表的比较

顺序表：表长变化不大且可以确定变化范围，插入删除操作较少，按照元素位置访问操作较多（顺序表的操作更便捷简单）链表：长度变化较大或不好确定变化范围，频繁的进行插入和删除

栈和队列

基本概念

定义

栈

定义：限定仅在表尾进行插入或删除操作的的线性表

特点：只在栈顶操作，先进后出

队列

定义：限定在表的一端（表头）插入，另一端（表尾）删除的线性表

特点：先进先出

存储结构

栈

顺序存储

利用一组连续的内存单元一次存放从栈底到栈顶的元素，由栈顶指针的移动带实现插入

链式存储

用不带头结点的链表表示，栈顶指针即为链表的头指针

队列

顺序存储

利用一组地址连续的存储单元依次存放队列中的元素，附加一个队头指针（指向队头元素）和一个队尾指针（指向队尾元素）

链式存储

链队列由一个头指针和一个尾指针唯一确定

基本操作

栈

顺序栈

类型定义

typedef struct{ ElemType *elem; //数组指针，指示线性表的基地址 int length; //当前长度 int listsize; //当前分配的存储容量 }SqList;

基本操作

初始化栈Status InitStack(SqStack &S)

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit 0; //内存分配失败 S.top=S.base; //栈顶分配到基地址 S.stacksize=STACK_INIT_SIZE;//为栈分配内存

取栈顶元素Status GetTop(SqStack S,SElemType &e)

if(S.top==S.base) return ERROR; //对栈进行判空 e=*(S.top-1); //取栈顶元素

插入元素e为栈顶元素Status Push(SqStack &S,SElemType e)

if(S.top-S.base>=S.stacksize){ //判断栈是否满 S.base=(SElemType*) realloc //满了重新分配内存 (S.base,S,stacksize+STACKINCREMENT)*sizeof(SElemType)； if(!S.base) exit 0; //内存分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT } *S.top++=e; //先对栈顶赋值再移动指针

删除栈顶元素Status Pop(SqStack &S,SElemType &e)

if(S.top==S.base) return ERROR; //判空 e=*--S.top; //先移动指针后删除 return OK;

链栈

类型定义

typedef struct StackNode{ SElemType data; struct StackNode *next; }StackNode,*LinkStack;

基本操作

链栈初始化

直接通过指针初始化栈S=NULL

链栈判空

if(S==NULL)

链栈入栈

p=(LinkStack) malloc(sizeof(StackNode)) //建立新的结点 if(!p) exit(OVERFLOW); //分配内存失败 p->data=e; p->next=S; S = p; //插入新结点

链栈出栈

if(S==NULL) return ERROR; //判空 e=S->data; p=S; S=S->next; free(p);

取链栈栈顶元素

栈顶的数据域：S->data

队列

链队列

类型结构

typedef struct QNode { QElemtype data; //数据域 struct QNode *next; //指针域 }Qnode, *QueuePtr; typedef struct { QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 }LinkQueue;

基本操作

链队列初始化Status InitQueue (LinkQueue &Q)

Q.front=Q.rear=(QueuPtr)malloc(sizeof(QNode)); //队头队尾指针指向同一数据域 if(!Q.front) exit(OVERFLOW); //分配内存失败 Q.front->next=NULL;

销毁队列Status DestroyQueue (LinkQueue &Q)

while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; Q.rear=NULL; }

插入元素Status EnQueue(LinkQueue &Q,QElemType e)

p=(QueuePtr)malloc(sizeof (QNode)); //建立一个新结点 if(!p) exit(OVERFLOW); //分配内存失败 p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p;

删除元素Status DeQueue(LinkQueue &Q,QElemType &e)

if(Q.front==Q.rear) return ERROR; //判空 p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free (p); //实现删除

循环队列

类型定义

typedef struct{ QElemType *base; //预分配存储空间 int front; //头指针 int rear; //尾指针 }SqQueue;

基本操作

初始化Status InitQueue(SqQueue &Q)

Q.base=(QElemType *)malloc(MAXQSIZE *sizeof(QElemType)); if(!Q.base) exit(OVERFLOW); //内存分配失败 Q.front = Q.rear = 0; //队头队尾初始化 /*注意：只让 Q.front = Q.rear 不能满足初始化*/

求队列长度Status QueueLength(SqQueue Q)

(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE

插入Status EnQueue(SqQueue &Q, QElemType e)

if((Q.rear+1)%MAXQSIZE==Q.front) //判断队满 return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE;

删除Status DeQueue(SqQueue &Q,ElemType &e)

if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front + 1)%MAXQSIZE;

栈的操作实例

数值转换（十转N）

思路：X=(X/N)*N+X%N越早余出来的数放在前面，满足后进先出的逻辑

括号匹配

while(scanf("%s",str) != EOF && stack != NULL) { //数组循环角标 int index = 0; int errFlag = 0; while(str[index] != '\0') { //这里只要等于(左括号直接入栈 if(str[index] == '(') { push_stack(stack,str[index]); } else if(str[index] == ')') { //当等于右括号的时候，判断栈是否有元素， if(is_empty(stack)) { errFlag = 1;//说明出错了 break; } else { pop_stack(stack); } } index++; } if(is_empty(stack) && errFlag == 0) printf("成功\n"); else { printf("出错\n"); } }

表达式求值

OperandType EvaluateExpression(){ InitStack (OPTR); Push (OPTR InitStack (OPND); ch = getchar( ); while (ch!= '#' || GetTop(OPTR)! = '#'){ if (! In(ch)){ Push(OPND,ch); ch = getchar(); } switch (Precede(GetTop(OPTR),ch=getchar()){ case '<': Push(OPTR, ch); ch = getchar(); break; case '>': Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); case'=': Pop(OPTR,x);ch = getchar(); break; return GetTop(OPND); }

定义

线性结构的特点

存在唯一一个被称作“第一个”的数据元素

存在唯一一个被称作“最后一个的数据元素

除了第一个之外的数据元素均只有唯一一个前驱

除了最后一个之外的数据元素只有唯一一个后继

串

定义

基本定义

串是由零个或多个字符组成的有限序列

空串

不含任何字符的串，串长为0

空格串

仅由一个或者多个空格组成的串

子串

由串中任意个连续的字符组成的子序列

主串

包含子串的串

串的逻辑结构

与线性表一致（但是其数据元素为字符）

串的顺序存储

定长顺序存储

用一组地址连续的存储单元依次存放串中的字符序列

堆分配存储

以一组空间足够大的，地址连续的存储单元依次存放串值字符序列，但它们的存贮空间是在程序执行过程中动态分布的

typedef struct{ char *ch; int length; }HString;

两者存储区别

串的链式存储

串的块链存储

用单链表存储串值

typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk *next; }Chunk; typedef struct{ Chunk *head,*tail; int curlen; }LString;

基本操作

串链接Status Concat(SString &T,SString S1,SString S2)

串T是由串S1和串S2得到的，需要时进行截断（采用定长顺序存储） S1[0]+S2[0]<=MAXSTRLEN //结果正确 T= S1[0]<MAXSTRLEN;S1[0]+S2[0]>MAXSTRLEN //结果S2被截断 S1[0]=MAXSTRLEN //结果T=S1

求子串Status SubString(SString &Sub,SString S,int pos,int len)

if(pos<||pos>S[0]||len<0||len>S[0]-pos+1) return ERROR; Sub[1..len]=S[pos..pos+len-1]; Sub[0]=len; return OK;

串插入Status SteInsert(Hstring &S,int pos,HString T)

if(pos<1||pos>S.length+1) return ERROE //插入位置不合理 if(T.length){ //T非空时，重新分配内存 if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)))) exit(OVERFLOW); for(i=S.length-1;i>=pos;--i) S.ch[i+T.length]=S.ch[i]; S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1]; S.length+=T.length; } return OK;

串赋值Status StrAssign(HString &T, char *chars)

if(T.ch) free(T.ch); //释放chars原有的长度 for(i=0,c=chars;c;++i,++c); //求chars长度 if (!i){ T.ch=NULL; T.length=0; } else{ if(!(T.ch=(char*)malloc(i*sizeof(char)))) exit (OVERFLOW); T.ch[0..i-1]=chars[0..i-1]; T.length=i; } return OK;

模式匹配算法

即子串的定位操作

BF算法

算法思想

将主串S的第pos个字符和模式串T的第一个字符比较，如果相同则继续比较；如果不相等，则从主串S的下一个字符开始重新匹配

实现思路

程序实现

int Index(Sstring S,Sstring T,int pos){ i=pos; j=1; while(i<=S[0]&&j<=T[0]){ if(S[i]=T[j]){ ++i; ++j; } else{ i=i-j+2; j=1; } } if(j>T[0]) return i-T[0]; else return 0; }

时间复杂度

最理想的状态时O(n)【n为模式串的长度】最坏的情况时O(m*n)【n为模式串长度，m为主串长度】

KMP算法

算法思路

让i不用回溯的实现在主串中寻找模式串

实现思路

next数组：最长前缀后缀子串

程序实现

void get_next(SString T, int &next[]){ j=1;k=0; next[1]=0; while(j<T[0]){ if(k==0||T[j]==T[k]){ ++j; ++k; next[j]=k; } else k=next[k]; } }

void get_nextval(SString T, int &nextval[]){ j=1;k=0; nextval[1]=0; while (j<T[0]) { if(k==0||T[j]==T[k]){ ++j; ++k; if(T[j]!=T[k]) nextval[j]=k; else nextval[j]=nextval[k]; } else k = next[k]; } }//对next函数的升级

时间复杂度

O(m+n)：m是模式串长度；n是主串长度

数组与广义表

数组

定义

按照一定格式排列起来的具有相同类型的数据元素的集合

一维数组相当于一个定长的线性表；二维数组可以视为元素为线性表的线性表，以此类推多维

存储结构

一维数组顺序存储

LOC(i)=a, i=0; LOC(i)=LOC(i-1)+l,i>0;

二维数组顺序存储

以行为主序LOC(i,j)=LOC(0,0)+(b2*i+j)*L 以列为主序LOC(i,j)=LOC(0,0)+(b1*i+j)*L

多维数组顺序存储

矩阵的压缩存储

矩阵定义

一个由m*n个元素排成的m行n列的表

矩阵存储特点

矩阵常规存储：将矩阵描述成一个二维数组

特点：可以对其元素进行随机存取；矩阵运算非常简单；存储密度为1

不适宜常规存储的情况：值相同的元素很多而且呈某种规律分布，零元素多

矩阵的压缩存储

为多个相同的非零元素只分配一个存储空间，对零元素不分配（常见的适用矩阵：上/下三角矩阵、对角线矩阵、对称矩阵）

稀疏矩阵

定义

存储结构

三元组顺序表

结构体定义

typedef struct{ int i,j; //非零元素的下标 Elemtype e; //非零元素 }Tripe; typedef struct{ Tripe data[MAXSIZE+1]; int mu,nu,tu; //矩阵的行、列和非零元素个数 }TSMatripe;

优缺点

优点：非零元素再表中按行有序存储，所以便于进行依行顺序处理的矩阵运算

缺点：不能随机存储，若按行号存取某一行的元素，需要从头开始

十字链表

结构体类型定义

typedef struct OLNode{ int i,j; //非零元素的下标 ElementType e; //非零元素 struct OLNode *right,*down; //非零元素所在行表列表的后继链域 }OLNode,*OLink; typedef struct{ OLink *rhead,*chead; //行，列链表的头指针向量基址 int mu,nu,tu; //稀疏矩阵的行数，列数，非零元素个数 }CrossList;

优点

它能够灵活地插入因运算产生的新的非零元素，删除因运算而产生的新的零元素

广义表

定义

基本定义

广义表：是n>=0个元素的有限序列，每一个a或者是原子，或者是原表

性质

广义表中的数据元素有相对次序

广义表的长度定义为最外层所包含元素的个数

广义表的深度定义为该广义表展开后所含的括号重数

广义表可以为其他广义表共享

广义表可以是递归的表

广义表是多层次结构，广义表的元素可以是单元素也可以是子表，而子表的元素可以是单元素或者子表......

基本运算

int GListLength(GList L);//求广义表L的长度 int CopyGList(GList &T,GList L);//由广义表L复制得到广义表T GLNode *GetHead(GList L);//获取广义表L的表头 GLNode *GetTail(GList L);//获取广义表L的表尾 int GListDepth(GList L);//求广义表L的深度 void visit(AtomType e);//遍历函数 Status GListTraverse(GList &L,void(*visit)(AtomType e));//广义表的遍历

广义表运算举例

D = ( E, F ) = ((a, (b, c))，F ) GetHead( D ) = E GetHead( E ) = a GetHead(((b, c))) = (b, c) GetHead((b, c)) = b GetHead((c)) = c GetTail( D ) = ( F ) GetTail( E ) = ((b, c)) GetTail(((b, c))) = ( ) GetTail((b, c)) = (c) GetTail((c)) = ( )

存储结构

首尾链表

typedef enum{ATOM,LIST}ElemTag; //ATOM=0单元素；LIST=1子表 typedef struct{ ElemTag tag; //标志域：用来区分元素结点和表结点 union{ //元素节点和表结点联合的部分 Atomtype atom; //atom为原子节点的值域 struct{ struct GLNode *hp,*tp; //ptr.hp指向表头；ptr.tp指向表尾 }ptr; //ptr是表结点的指针域 }; }*GList;

扩展线性链表

typedef enum{ATOM,LIST}ElemTag; //ATOM=0单元素；LIST=1子表 typedef struct GLNode{ ElemTag tag; //标志域：用来区分元素结点和表结点 union{ //元素节点和表结点联合的部分 Atomtype atom; //atom为原子节点的值域 struct GLNode *hp; //表结点的表头指针 }; struct GLNode *tp; //指向下一个结点 }*GList;

递归算法

求广义表深度int GlistDepth(Glist L)

if (!L) return 1; if (L->tag == ATOM) return 0; for (max=0, pp=L; pp; pp=pp->ptr.tp){ dep = GlistDepth(pp->ptr.hp); if (dep > max) max = dep; } return max + 1;

复制广义表Status CopyGList(Glist &T, Glist L)

if (!L) T = NULL; // 复制空表 else { if ( !(T = new GLNode) ) exit(OVERFLOW); //建表结点 T->tag = L->tag; if (L->tag == ATOM) T->atom = L->atom; // 复制单原子结点 else { 分别复制表头和表尾 } } else return OK;