IdeFun

努力不一定成功，但不努力真的很舒服。

0%

数据结构与算法总结

发表于 更新于 分类于 Valine：
本文字数： 17k 阅读时长 ≈ 15 分钟
本文旨在记录数据结构与算法学习中所获(C语言)

数据结构与算法

一.绪论

算法是为了解决实际问题而设计的.数据结构是算法需要处理的问题载体.

基本概念和术语:

  • 数据:数据是指能输入到计算机中并能够被计算机处理的一切对象.

  • 数据元素:数据元素是数据的基本单位.

  • 数据项:一个数据元素可由若干数据项组成.

  • 数据对象:数据对象是具有相同性质的数据元素的集合.

  • 数据结构:数据结构是指互相之间存在着一种或多种关系的数据元素的集合.

逻辑结构:

1.集合结构:数据元素同属一个集合，单个数据元素之间没有任何关系

​ 2.线性结构:类似于线性关系,数据元素之间是一对一的关系

​ 3.树形结构:树形结构中的数据元素之间存在一对多的关系

​ 4.图形结构:数据元素之间是多对多的关系

存储结构(物理结构):

(数据结构种类很多， 甚至你也可以发明自己的数据结构， 但是底层存储无非数组或者链表 ,那些多样化的数据结构， 究其源头， 都是在链表或者数组上的特殊操作 )

1.顺序存储:一段连续的内存空间

  • 优点：随机访问
  • 缺点：插入删除效率低，大小固定

2.链式存储:不连续的内存空间

  • 优点：大小动态扩展，插入删除效率高
  • 缺点：不能随机访问

3.索引:为了方便查找，整体无序，但索引块之间有序，需要额外空间存储索引表

  • 优点：对顺序查找的一种改进，查找效率高

  • 缺点：需额外空间存储索引

4.散列:选取某个函数，数据元素根据函数计算存储位置,可能存在多个数据元素存储在同一位置，引起地址冲突

  • 优点：查找基于数据本身即可找到，查找效率高，存取效率高
  • 缺点：存取随机，不便于顺序查找

队列,栈这两种数据结构既可以使用链表也可以使用数组实现.用数组实现,就要处理扩容缩容的问题; 用链表实现,则没有这个问题,但需要更多的内存空间存储节点指针

图的两种表示方法,邻接表就是链表,邻接矩阵就是二维数组.邻接矩阵判断连通性迅速,并可以进行矩阵运算解决一些问题,但是如果图比较稀疏的话很耗费空间.邻接表比较节省空间,但是很多操作的效率上肯定比不过邻接矩阵。

散列表就是通过散列函数把键映射到一个大数组里,而且对于解决散列冲突的方法,拉链法需要链表特性,操作简单,但需要额外的空间存储指针;线性探查法就需要数组特性,以便连续寻址,不需要指针的存储空间,但操作稍微复些.

影响算法运行时间的因素:

1.运行程序的计算机的机器指令的品质与速度

2.书写程序的语言(一般实现语言级别越高,其执行效率越低)

3.编译程序所生成目标代码的质量

4.问题的规模

大O表示法:用来表示时间复杂度函数的增长率的上界

时间复杂度:嵌套(求积),并列(求和),只关注最高次项

空间复杂度:算法运行所需存储空间:

1.程序本身占用的空间

2.算法的输入,输出占用的空间

3.算法运行中占用的空间

评价一个算法的空间复杂度一般只考虑算法运行中所占用的临时空间.

对于一个算法,其时间复杂度和空间复杂度往往是相互影响的.

二.线性表

线性结构的特点是在数据元素的非空有限集合中,存在唯一的首元素和唯一的尾元素,首元素无直接前驱,尾元素无直接后继,集合中其他数据元素都有唯一的直接前驱和唯一的直接后继.线性表是最简单,最基本,也是最常用的一种线性结构.

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列.

线性表的顺序存储结构:

#define MAXSIZE 20  //存储空间初始分配量
typedef int ElemType; //ElemType类型根据实际情况而定,这里假设为int
typedef struct
{
    ElemType data[MAXSIZE]; //数组存储数据元素,最大值为MAXSIZE
    int length;  //线性表当前长度
}SqList;

线性表顺序存储结构需要三个属性:

  • 存储空间的起始位置
  • 线性表的最大存储容量(数组的长度)
  • 线性表的当前长度(小于等于数组长度)

顺序表的初始化:

SqList *init_SqList()
{
    SqList *L;
    L=(SqList *)malloc(sizeof(SqList)); //动态分配内存空间
    if(!L) exit(1);  //如果存储分配失败,运行exit()函数终止程序运行
    L->length=0;
    return L;
}

顺序表的插入运算:

SqList *Insert_SqList(SqList *L,int i,ElemType x)
{//在顺序表L第i个位置插入值为x的元素
    if(L->length>=MAXSIZE-1)//判断表是否满
    {
        printf("顺序表已满!");
        exit(1);
    }
    if(i<0||i>L->length+1)//判断插入位置是否合理
    {
        printf("插入位置i不合理!");
        exit(1);
    }
    for(int m=L->length-1;m>=i-1;m--)
    {
        L->data[m+1]=L->data[m];//节点后移
    }
    L->data[i-1]=x;//新元素插入
    L->length++;//表长加1
    return L;
}

顺序表的删除运算:

SqList *Delete_SqList(SqList *L,int i,ElemType e)
{//删除顺序表L中第i个元素,删除元素的值保存在e中
    if(i<0||i>L->length)
    {
        printf("插入位置i不合理!");
        exit(1);
    }
    e=L->data[i-1];
    for(i;i<=L->length-1;++i)
        L->data[i-1]=L->data[i];
    L->length--;
    return L;
}

顺序表按值查找运算:

int LocateElem_Sq(SqList *L,ElemType x)
{//在顺序表中查找值为x的元素,查找成功返回元素存储位置
    for(int i=0;i<length;i++)
    {
        if(L->data[i]==x)
            return i;
    }
    return -1;
}

顺序表合并算法:

SqList *Merge_SqList(SqList *A,SqList *B)
{//将两个非递减次序排列的顺序表A和B合并为一个新的有序顺序表C
    SqList *C;
    int i,j,k;
    i=0;j=0;k=0;
    C=(SqList *)malloc(2*MAXSIZE*sizeof(SqList));
    if(!C) exit(1);
    C->length=A->length+B->length;
    while(i<=A->length-1&&j<=B->length)
        if(A->data[i]<B->data[j])
        {
            C->data[k]=A->data[i];k++;i++;
        }
    	else
        {
            C->data[k]=B->data[j];k++;j++;
        }
    //前面部分是先将A,B中较短的填入C,后面再填入另一个
    while(i<=A->length-1)
    {
        C->data[k]=A->data[i];k++;i++;
    }
    while(j<B->length-1)
    {
        C->data[k]=B->data[j];k++;j++;
    }
    return C;
}

线性表的链式存储结构:

1.单链表(动态链表)

静态链表是用类似于数组方法实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针

单链表节点数据类型:

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList;

头插入法建立单链表:

LinkList CreatList_L1()
{
    LinkList L;
    LinkList P;
    int x;
    L=(LinkList*)malloc(sizeof(Node));
    L->next=NULL;
    scanf("%d",&x);
    while(x!=0)
    {
        p=(LinkList*)malloc(sizeof(Node));
        p->data=x;
        p->next=L->next;
        L->next=p;
        scanf("%d",&x);
    }
    return L;
}

尾插入法建立单链表:

LinkList CreatList_L2()
{
    LinkList L,p,r;
    int x;
    r=L=(LinkList*)malloc(sizeof(Node));
    L->next=NULL;
    scanf("%d",&x);
    while(x!=0)
    {
        p=(LinkList*)malloc(sizeof(Node));
        p->data=x;
        p->next=NULL;
        r->next=p;
        r=p;
    }
    return L;
}

求链表长度的算法:

int Listlength(LinkList L)
{
    LinkList p;
    int i=0;
    p=L;
    while(p->next!=NULL)
    {
        i++;
        p=p->next;
    }
    return i;
}

查找操作:

​ 1.按序号查找

LinkList Get_LinkList(LinkList L,int i)
{//在链表L中查找第i个元素,找到返回其指针,否则返回空
    LinkList p;
    p=L;
    int j=0;
    while(p->next!=NULL&&j<i)
    {
        p=p->next;
        j++;
    }
    if(j==i)return p;
    else return NULL;
}

​ 2.按值查找

LinkList Locate_LinkList(LinkList L,ElemType x)
{
    LinkList p;
    p=L;
    while(p->next!=NULL&&p->data!=x)
       p=p->next;
    return p;
}

插入运算:

LinkList ListInsert(LinkList L,int i,ElemType x)
{//在单链表第i个节点前插入新元素x
    LinkList p,s;
    int j=0;
    p=L;
    while(p->next!=NULL&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL||j>i-1)
    {printf("参数i错误!");exit(1);}
    s=(LinkList*)malloc(sizeof(Node));
    s->data=x;
    s->next=p->next;
    p->next=s;
    return L;
}

删除运算:

LinkList ListDelete(LinkList L,int i,ElemType *e)
{//删除单链表L中第i个元素
    LinkList p,q;
    int j=0;
    p=L;
    while(p->next!=NULL&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p->next=NULL||j>i-1)
    {
        printf("参数i错误!");
        exit(1);
    }
    q=p->next;
    p->next=q->next;
    *e=q->data;
    free(q);
    return L;
}

有序链表归并算法:

LinkList Merge_LinkList(LinkList A,LinkList B)
{//A,B均为带头节点的单链表
    LinkList C,p,q,s;
    p=A->next;
    q=B->next;
    free(B);
    C=A;
    C->next=NULL;
    while(p&&q)
    {
        if(p->data<q->data){s=p;p=p->next;}
        else {s=q;q=q->next;}
        s->next=C->next;
        C->next=s;
    }
    if(p==NULL)p=q;
    while(p)
    {
        s=p;
        p=p->next;
        s->next=C->next;
        C->next=s;
    }
}

2.循环链表

1.单向循环链表

单链表尾节点的指针域是空指针.而单向循环链表的最后一个节点的指针指向链表头节点.

对于单链表,从一已知节点只能访问该节点及其后继节点,无法访问该节点之前的节点;而对于单向循环链表,只要知道表中任一节点的地址,就可搜寻到所有其他节点的地址,遍历整个链表.

单向循环链表的数据类型定义与单链表相同.在单循环链表上的操作也与单链表基本相同,二者主要区别在于:判断是否达到表尾的条件不同.在单链表中,用指针域是否为NULL作为判断表尾节点的条件;而在循环链表中,则以节点指针域是否等于表头节点(头指针)作为判断到达表尾的条件.

2.双向链表

双向链表的结构:

typedef struct DuLnode
{
	ElemType data;
    struct DuLnode *prior,*next;
}DuLnode;
typedef DuLnode *DuLinkList;

双向链表的插入运算:

DuLinkList ListInsert_Dul(DuLinkList L,int i,ElemType x)
{//在双向链表的第i个节点前插入一个新元素x
	DuLinkList p,s;
    int j;
    p=L;
    j=0;
    while(p!=NULL&&j<i)
    {p=p->next;j++}
    if(p==NULL||j<i)
    {printf("参数i错误!");exit(1);}
    if(!(s=(DuLinkList*)malloc(sizeof(DuLnode))))
        exit(1);
    s->data=x;
    s->prior=p->prior;p->prior->next=s;
    s->next=p;p->prior=s;
    return L;
}

双向链表的删除运算:

DuLinkList ListDelete_Dul(DuLinkList L,int i,ElemType &e)
{//删除双向链表中第i数据元素
    DuLinkList p;
    int j;
    p=L;
    j=0;
    while(p!=NULL&&j<i)
    {p=p->next;j++;}
    if(p==NULL||j>i)
    {printf("参数i错误!");exit(1);}
    else{
        e=p->data;
        p->prior->next=p->next;
        p->next->prior=p->prior;
        free(p);
        return L;
    }
}

三.栈与队列

栈和队列是在程序设计中被广泛使用的两种数据结构.由于从数据结构角度看,栈和队列是两种特殊的线性表.它们的逻辑结构和线性表相同,只是其运算规则较线性表有更多的限制,因此,也可以将栈和队列称为操作受限的线性表.

栈是限定仅在表尾进行插入和删除操作的线性表.队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表.

栈的定义

  • 栈是一种特殊的线性表,是一种只允许在表的一端进行插入或删除操作的线性表.把栈中允许进行插入,删除操作的一端称为栈顶,栈的另一端称为栈底.
  • 当栈中没有数据元素时,称之为空栈.栈顶是动态的,对栈顶位置的标记称为栈顶指针.栈的插入操作通常称为进栈(入栈或压栈),栈的删除操作通常称为退栈或出栈.
  • 根据栈的定义,每次进栈的数据元素都放在当前栈顶元素之前而成为新的栈顶元素,每次退栈的数据元素都是当前栈顶元素.这样,最后进入栈的数据元素总是最先退出栈,因此,栈具有”后进先出”的特性,所以栈又称为后进先出的线性表,简称LIFO表.

栈的存储结构

栈有两种存储表示方法,即顺序存储和链式存储.顺序存储的栈称为顺序栈,链式存储的栈称为链式栈.

顺序栈

顺序栈的存储结构:

#define StackInitSize 100;
typedef int StackElementType;
typedef struct{
    StackElementType data[StackInitSize];
    int top;
}SeqStack;

顺序栈的初始化:

SeqStack *InitStack()
{
    SeqStack *s;
    s=(SeqStack*)malloc(sizeof(SeqStack));
    if(s!=NULL)
    {s->top=-1;
    return s;}
    else{printf("没有足够的内存空间,申请失败,程序运行终止!");
        exit(1);}
}

判断栈空的函数:

int IsEmpty(SeqStack *s)
{
    return(s->top==-1)?1:0;//栈空返回1,否则返回0
}

销毁栈的函数:

void DestoryStack(SeqStack *s)
{
    free(s);
    printf("栈已销毁!\n");
    return;
}

进栈操作:

void Push(SeqStack *s,StackElementType x)
{
    if(s->top==StackInitSize){
        printf("栈满!栈发生上溢,程序停止运行!\n");
        exit(1);
    }
    else{
        s->top++;
        s->data[s->top]=x;
    }
    return;
}

退栈操作:

StackElementType Pop(SeqStack *s)
{
    StackElementType temp;
    if(IsElpty(s)){
        printf("栈空!栈发生下溢,程序停止运行!\n");
        exit(0);
    }
    else{
        temp=s->data[s->top];
        s->top--;
        return temp;
    }
}

读取栈顶元素:

StackElementType GetTop(SeqStack *s)
{
    if(IsEmpty(s))
    {
        printf("空栈,程序停止运行!");
        exit(0);
    }
    else
        return s->data[s->top];
}

栈浮动技术:

当一个程序中同时使用多个顺序栈时,为了防止上溢错误,需要为每个栈分配较大的存储空间.在多栈使用过程中通常会出现:在某一栈发生上溢的同时,其余栈尚有大量未用空间存在,这样不利于内存空间的共享,会降低内存空间的使用效率.如果将多个栈安排在同一个连续的存储空间中,这样多个栈共享存储空间,并使它们根据实际情况互相调节余缺.如此既节省了存储空间的开销,又降低了上溢现象发生的概率.这种多栈共享空间的技术,通常称为栈浮动技术.

当程序中同时使用两个栈时,两个栈可以共享同一存储空间.此时,将两个栈的栈底分别设在同一存储空间的两端,让两个栈各自向中间延伸.这样只有当整个共享空间被两个栈占满(两个栈的栈顶相遇)时,才会发生上溢.

两栈共享空间的结构:

typedef struct
{
    StackElementType data[StackInitSize];
    int top1;//栈1栈顶指针
    int top2;//栈2栈顶指针
}SqDoubleStack;

对于两栈共享空间的进栈方法,我们除了要插入元素值参数外,还需要有一个判断是栈1还是栈2的栈号参数stackNumber

链式栈

链式栈的存储结构:

typedef int StackElementType;
typedef struct node{
    StackElementType data;
    struct node *next;
}LinkStack;

链式栈的进栈操作:

LinkStack *Push(LinkStack *top,StackElementType x)
{
    LinkStack *p;
    p=(LinkStack *)malloc(sizeof(LinkStack));
    if(p){p->data=x;
         p->next=top;
         top=p;
         return top;}
    else{printf("内存不足,程序运行停止!");
        exit(0);}
}

链式栈的退栈操作:

LinkStack *Pop(LinkStack *top,StackElementType *elem)
{
    LinkStack *temp;
    if(top)
    {
        temp=top;
        *elem=top->data;
        top=top->next;
        free(temp);
        return top;
    }
    else 
        return NULL;
}

链式栈读取栈顶元素:

StackElementType GetTop(LinkStack *top)
{
    return top?top->data:NULL;
}

队列的定义

  • 队列(Queue)是一种只允许在一端进行插入,另一端进行删除的运算受限的线性表,允许删除的一端叫队头(front),允许插入的一端叫队尾(rear).
  • 队列的插入操作通常称为入队,删除操作通常称为出队,当队列中没有元素时称为空队列.
  • 队列具有”先进先出”(FIFO)特性,简称为FIFO表.

队列的存储结构

循环队列(顺序队列)

在顺序队列中,进行入队和出队操作时可能产生溢出现象:

1.”下溢”现象

当队列为空时,进行出队运算产生的溢出现象,称为”下溢”.可通过判断队列是否为空来控制

2.”真上溢”现象

当队列满时,进行入队运算时产生空间溢出的现象,称为”真上溢”.可通过判断队列是否满来控制

3.”假上溢”现象

由于在入队和出队操作中,队头指针与队尾指针只增加不减小,致使被删元素的空间永远无法重新利用.当队列中实际的元素个数远远小于存储空间的规模时,也可能由于队尾指针已超越队列空间的上界而不能做入队操作.这种现象称为”假下溢”.

为防止假溢出现象发生,充分利用存储空间,最巧妙的解决方法就是把队列存储空间看作首尾相连的环,而这种队列的循环顺序存储结构称为循环队列.

循环队列存储结构

#define MaxSize 100;
typedef int QueueElementType;
typedef struct{
    QueueElementType *base;//base指向队列存储区首地址
    int front;
    int rear;
}SeqQueue;

循环队列的特点

  • 队头,队尾指针加1时从MaxSize-1直接进到0,这种变化可用C语言的取模(余数)运算实现
  • 队空与队满时头尾指针均相等,无法通过front==rear来判断队列的”空”和”满”,解决此问题有两种方法:
    1. 另设一个状态标志位来区别”队空”和”队满”
    2. 少用一个存储空间,约定以队头指针在队尾指针的下一位置上作为队列满的标志

采用第二种处理方法:

循环队列空的标志:front==rear

循环队列满的标志:(rear+1)%MaxSize==front

循环队列初始化

SeqQueue InitQueue(){
    SeqQueue Q;
    Q.base=(QueueElementType*)malloc(MaxSize*sizeof(QueueElementType));
    if(!Q.base){
        printf("申请存储空间失败,程序运行终止!");
        exit(0);
    }
    Q.front=0;
    Q.rear=0;
    return Q;
}

判断循环队列为空

int QueueEmpty(SeqQueue Q)
{
    return (Q.front==Q.rear)?1:0;
}

判断循环队列为满

int QueueFull(SeqQueue Q)
{
    return (Q.front==(Q.rear+1)%MaxSize)
}

入队操作

SeqQueue EnQUeue(SeqQueue Q,QueueElementType x){
    if(QueueFull(Q)
       printf("队满!");
    else{
        *(Q.base+Q.rear)=x;
        Q.rear=(Q.rear+1)%MaxSize;
    }  
    return Q;
}

出队操作

SeqQueue DeQueue(SeqQueue Q,QueueElementType *e)
{
	if(QueueEmpty(Q))
        printf("队空!");
    else{
        *e=*(Q.base+Q.front);
        Q.front=(Q.front+1)%MaxSize;
    }
    return Q;
}

读取队头元素

QueueElementType GetHead(SeqQueue Q)
{
    if(QueueEmpty(Q))
    {
        printf("队空!读取失败!");
        return 0;
    }
    else
        return *(Q.base+Q.front);
}

销毁队列

void DestoryQueue(SeqQueue Q)
{
    free(Q.base);
    printf("队列已被销毁!");
    return;
}

队列遍历操作

void QueueDisplay(SeqQueue Q)
{
    if(QueueEmpty(Q))
        printf("队空!队列遍历完成!\n");
    else{
        printf("队列遍历(队头->队尾):\n");
        for(int i=Q.front;i!=Q.rear;i++)
            printf("%d->",*(Q.base+i));
        printf("\b\b \n");
    }
}
链式队列

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

链式队列节点类型定义

typedef int QueueElementType;
typedef struct Node{
    QueueElementType data;
    struct Node *next;
}QueueNode;

链式队列数据类型定义

typedef struct{
    QueueNode *front;
    QueueNode *rear;
}LinkQueue;

链式队列的初始化

LinkQueue InitQueue(){
    LinkQueue Q;
    QueueNode *p;
    p=(QueueNode*)malloc(sizeof(QueueNode));
    if(p){
        Q.front=Q.rear=p;
        Q.front->next=NULL;
        return Q;
    }
    else{
        printf("初始化失败!程序运行终止!");
        exit(0);
    }
}

判断链式队列是否为空

int QueueEmpty(LinkQueue Q)
{
    return (Q.front=Q.rear)?1:0;
}

入队操作

LinkQueue EnQueue(LinkQueue Q,QueueElementType x){
    QueueNode *p;
    p=(QueueNode*)malloc(sizeof(QueueNode));
    if(!p){
        printf("申请空间失败!程序运行终止!");
        exit(0);
    }
    else{
        p->data=x;
        p->next=NULL;//尾节点的next置空
        Q.rear->next=p;
        Q.rear=p;
    }
}

出队操作

LinkQueue DeQueue(LinkQueue Q,QueueELementType *e)
{
    QueueNode *p;
    if(QueueEmpty(Q))
    {
        printf("队列为空!出队失败!\n");
    }
    else{
        p=Q.front->next;
        *e=p->data;
        Q.front->next=p->next;
        if(Q.rear==p)
            Q.rear=Q.front;
        free(p);
    }
    return Q;
}

读取队头操作

QueueElementType GetHead(LinkQueue Q)
{
     if(QueueEmpty(Q))
    {
         printf("队列为空!读取队头失败!\n");
         return 0;
    }
    else
        return (Q.front->next.data);
}

四.矩阵的压缩存储

五.递归

六.树与二叉树

七.图

图形结构是一种比树形结构更复杂的非线性结构.在树形结构中,节点间具有分支层次关系,每一层上的节点只能和上一层中的至多一个节点相关,但可能和下一层的多个节点相关.而在图形结构中,任意两个节点之间都可能相关,即节点之间的邻接关系可以是任意的.

图及其相关概念

  • 图是由顶点(vertex)集合及顶点间的关系组成的一种数据结构.
  • 图分为无向图和有向图.具有n个顶点,n(n-1)/2条边的无向图,称为完全无向图.具有n个顶点,n(n-1)条弧的有向图称为完全有向图.完全无向图和完全有向图统称为完全图.
  • 当一个图接近完全图时,称它为稠密图.相反称为稀疏图.
  • 与边有关的数据信息称为权.带权图又称为网络.如果边是有方向的带权图,则是一个有向网络.
  • 在无向图中,一个顶点依附的边的数目称为该顶点的度.在有向图中,指向顶点的弧的数目称为该顶点的入度(这种弧也称为入弧).从顶点发出的弧的数目称为该顶点的出度.有向图的某个顶点的入度和出度之和称为该顶点的度.
  • 除第一个顶点与最后一个顶点之外,其它顶点不重复出现的回路称为简单回路(简单环).
  • 若G中任意两个顶点都是连通的,则称G为连通图,否则称为非连通图.

图的存储结构

邻接矩阵表示法

在图的邻接矩阵表示中,除用一个一维数组存放顶点本身的信息外,还用一个n×n的矩阵表示各个顶点之间的邻接关系.即若(i,j)或属于边集E,则矩阵中第i行,第j列元素值为1,否则为0.

从无向图的邻接矩阵存储方法可以看出:

  1. 无向图的邻接矩阵一定是一个对称矩阵
  2. 第i行或第i列中1的个数是顶点i的度
  3. 矩阵中1的个数的一半为图中边的数目

从有向图的邻接矩阵存储方法可以看出:

  1. 有向图的邻接矩阵不一定是一个对称矩阵
  2. 第i行中1的个数为顶点i的出度
  3. 第i列中1的个数为顶点i的入度
  4. 矩阵中1的个数为图中弧的数目

从无向网络的邻接矩阵存储方法可以看出:

  1. 无向网络的邻接矩阵一定是一个对称矩阵
  2. 第i行或第i列中非∞元素的个数为顶点i的度
  3. 矩阵中非∞元素的个数的一半为网络中边的数目

从有向网络的邻接矩阵存储方法可以看出:

  1. 有向网络的邻接矩阵不一定是一个对称矩阵
  2. 第i行中非∞元素的个数为顶点i的出度
  3. 第i列中非∞元素的个数为顶点i的入度
  4. 矩阵中非∞元素的个数为网络中弧的数目

邻接矩阵的存储结构:

#define INFINITY 65535 //用65535表示∞
#define MAXVEX 100 //最大顶点数
typedef char VertexType;//顶点类型由用户定义
typedef int EdgeType;//边上的权值类型由用户定义
typedef struct{
    VertexType vexs[MAXVEX];//顶点表
    EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵,可看作边表
    int numVertexs,numEdges;//图中当前的顶点和边数
}Mgraph;

无向网图的邻接矩阵表示:

void CreatMGraph(MGraph *G)
{
    int i,j,k,w;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d",&G->numVertexs,&G->numEdges);
    for(i=0;i<G->numVertexs;i++)
        scanf(&G->vexs[i]);
    for(i=0;i<G->numVertexs;i++)
        for(j-0;j<G->numVertexs;j++)
            G->arc[i][j]=INFINITY;//邻接矩阵初始化
    for(k=0;k<G->numEdges;k++)
    {
        printf("输入边(vi,vj)上的下标i,下标j和权w:\n");
        scanf("%d,%d,%d",&i,&j,&w);
        G->arc[i][j]=w;
        G->arc[j][i]=G->arc[i][j];
    }
}

邻接表表示法

八.查找

九.排序

排序的概念

排序(Sorting)就是按照某种规则,将一组数据对象(记录)排列次序,其主要目的是提高数据检索的效率.

排序的分类

按照排序过程中所使用存储器情况,可将排序方法分为两大类:

1.内部排序

在排序过程中,整个待排序列都是存放于内存中进行处理,无内外存储器之间的数据交换问题.内部排序速度快,适合少量数据的排序处理.

2.外部排序

在排序过程中,由于待排序记录数据量相当大,不可能也不允许全部驻留在内存中,而必须存放在外部存储器上,然后根据排序过程中的要求,不断在内外存之间进行数据交换来完成排序工作.外部排序速度慢,适合大量数据的排序问处理.

内部排序的方法较多,按照实现策略的不同,可以将内部排序分五大类.

  1. 插入排序.直接插入排序,希尔排序.
  2. 交换排序.冒泡排序,快速排序.
  3. 选择排序.直接选择排序,堆排序.
  4. 归并排序.
  5. 基数排序.

假设待排序序列中记录的数据类型定义如下:

#define MaxSize 100
typedef struct{
    int key;
    ElementType otherinfo;//排序记录中的其他所有数据项
}RecordType;
typedef RecordType SeqList[MaxSize+1];

数组的第0个元素既可以用来作暂存空间使用,也可以作”监测哨兵”使用,但不用其存放待排序记录.在本章均要求排成递增序.

插入排序

直接插入排序

思想:

1.将待排序序列分为有序区和无序区,初始时,有序区为[R1],无序区为[R2…Rn],令i指向无序区第一个元素,初值i=2

2.当i<=n时,重复执行:将当前无序区第一个记录插入到有序区合适位置

3.当i>n时,排序结束

算法:

void InsertSort(SeqList R,int length)
{//length为待排序列长度
    int i,j;
    for(i=2;i<=length;i++)
    {
        if(R[i].key<R[i-1].key)
        {
            R[0]=R[i];
            for(j=i-1;R[0].key<R[j].key;j--)
                R[j+1]=R[j];//记录后移
            R[j+1]=R[0];
        } 
    }
}

哨兵的作用:

1.进入查找(插入位置)循环之前,它保存了R[i]的副本,使不至于记录后移而丢失R[i]的内容.

2.在查找循环中”监视”下标j是否越界.

直接插入排序的时间复杂度为O(n^2),空间复杂度为O(1),直接插入排序是稳定的

希尔排序

希尔排序也叫缩小增量排序,是插入排序的一种,在时间复杂度上比直接插入排序好.

思想:

1.先将整个待排序列以d1(d1<n)为步长分成若干子序列,把所有相隔为d1的记录放在同一组

2.在每个分组内进行直接插入排序

3.再将整个待排序记录以d2(d2<d1<n)为步长重新分组,并在每组内进行直接插入排序

4.重复上步,直至dt=1,即所有记录放进一个组中进行直接插入排序,其最终结果为有序序列

算法:

void ShellPass(SeqList R,int length,int d)
{//希尔排序的一次排序,length为待排序列长度,d为当前增量
    int i,j;
    for(i=d+1;i<length;i++)
    {
        if(R[i].key<R[i-d].key){
            R[0]=R[i];
            j=i-d;
            do{
                R[j+d]=R[j];
                j=j-d;
            }while(j>0&&R[0].key<R[j].key)
                R[j+d]=R[0];
        }
    }
}
void ShellSort(SeqList R,int length)
{//对序列R进行希尔排序,length为待排序长度
    int increment=length;
    do{
        increment=(increment+1)/3;
        ShellPass(R,length,increment);
    }while(increment>1);
}

希尔排序时间复杂度可达到O(n^1.25),空间复杂度为O(1),希尔排序不稳定

交换排序

交换排序的基本思想是两两比较待排序记录的关键字,如果发现两个关键字逆序,则将两个记录位置互换,重复此过程,直到该系列所有关键字都有序为止.

冒泡排序

思想:

1.将第一个记录的关键字与第二个记录的关键字比较,若二者为逆序(R[1].key>R[2].key),则交换两记录位置,然后比较第二个记录与第三个记录,若两关键字为逆序,同样交换位置

2.依次类推,直至第n-1个记录与第n个记录比较完为止.上述过程称为第一趟冒泡排序,其结果使n个记录中关键字最大的记录被移动到最后一个位置

3.然后进行第二次冒泡排序,即对前n-1个记录重复与第一趟冒泡排序类似的过程,结果使关键字次大的记录被移到第n-1个记录位置

4.重复上述过程,直到”在一趟排序过程中没有进行交换记录的操作”为止

算法:

void BubbleSort(SeqList R,int length){
    int i,j,exchange=1;//exchange为发生交换的标志
    for(i=length;i>1&&exchange;i--)
    {
        exchange=0;
        for(j=1;j<i;j++){
            if(R[j].key<R[j+1].key)
            {
                R[0]=R[j];
                R[j]=R[j+1];
                R[j+1]=R[0];
                exchange=1;
            }
        }
    }
}

冒泡排序时间复杂度为O(n²),空间复杂度为O(1),且冒泡排序是稳定的

快速排序

快速排序采用一种分治的策略,通常称为分治法.分治的基本思想是:将原问题分解为若干规模更小但将结构与原问题相似的子问题,采用递归方法求解这些子问题,然后将这些子问题的解组合成原问题的解.

思想:

1.从待排序列中任取一个记录(例如)的关键字作为枢轴(pivot),按照枢轴,将整个待排序列划分为左右两个子序列,其中左子序列中所有关键字都小于等于枢轴,而右子序列中所有的关键字都大于枢轴,枢轴记录则排在这两个子序列中间(这也是该记录的最终位置).此过程称为一趟快速排序(或一次划分).

2.对左右两个子序列分别重复实施上述方法,直到所有的记录都排在相应的位置上为止(每个子序列只含一个记录)

算法:

int QuickPass(SeqList R,int b,int e)
{//对R[b],...R[e]作一趟划分,并返回枢轴记录的位置
    int i=b,j=e;
    R[0]=R[i];
    while(i<j){
        while()
    }
}
-------------本文结束感谢您的阅读-------------