线性结构思维导图

U621655065

2022-12-22

浏览量: 26

线性表

栈和队列

数组与广义表

矩阵的压缩存储

模式匹配算法

稀疏矩阵

树图思维导图提供《线性结构》在线思维导图免费制作，点击“编辑”按钮，可对《线性结构》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：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;

进阶面试题总结思维导图