PTA函数题相关接口(未完)

目录​​​​​​​

1.顺序表

顺序表的查找

顺序表的插入 

 顺序表的删除

顺序表有序插入

2.链表

带头结点单链表的查询

带头结点单链表的插入

带头结点单链表的删除

两个有序链表序列的合并

3.栈和队列

顺序栈的基本运算

循环队列出队入队(详细见博客http://t.csdn.cn/S8ep1)

循环队列入队出队操作（详细见博客http://t.csdn.cn/mkfmL）

另类堆栈 

十进制转二进制（顺序栈设计和应用）

进制转换

排队叫号系统

5.二叉树

 求叶子结点个数

后缀表达式

哈夫曼编码

二叉树的遍历

统计二叉树结点个数

求二叉树的深度

6.图

 图的创建（邻接矩阵）

图的创建-邻接表

最小生成树（普里姆算法）

 最短路径（迪杰斯特拉算法）

小岛计数（深度遍历）

广度遍历（邻接表实现）

 拓扑排序1

 拓扑排序2（第二个为参考，手动实现栈的功能）

 求采用邻接矩阵作为存储结构的有向图各顶点的出度

 邻接矩阵存储图的深度优先遍历

邻接表存储图的广度优先遍历

7.查找和排序

折半查找(带#是考点)

 顺序查找(带#是考点)

 快速排序 (带#是考点)

哈希表的创建及查找(线性探查法)

二叉排序树(带#是考点)

基于顺序表的直接插入排序

1.顺序表

顺序表的查找

 本题要求实现一个函数，要求从顺序表中查找指定元素，并返回第一个查找成功的元素在表中的位置序号，若查找失败，则返回0；

int LocateElem(SqList L,ElemType e)
{
    for(int i = 0;i<L.length;i++)
    {
        if(L.elem[i]==-1)return 0;
        if(e == L.elem[i])return i+1;
    }
    return 0;
}

顺序表的插入 

本题要求实现一个函数，在顺序表的第i个位置插入一个新的数据元素e，插入成功后顺序表的长度加1，函数返回值为1；插入失败函数返回值为0；

int ListInsert(SqList &L,int i,ElemType e)
{
    if(L.length == MAXSIZE)
    {
        return 0;
    }
    if(i<1||i>L.length+1)
    {
        return 0;
    }
    int b  = L.length;
    for(;b>i-1;b--)
    {
        L.elem[b] = L.elem[b-1];
    }
    L.elem[b] = e;
    L.length = L.length+1;
    
    return 1;
}

 顺序表的删除

本题要求实现一个函数，要求将顺序表的第i个元素删掉，成功删除返回1，否则返回0；

int ListDelete(SqList &L,int i)
{
    if(i>0&&i<=L.length)
    {
        int k = i-1;
        for(i=k;i<L.length-1;i++)
        {
            L.elem[i] = L.elem[i+1];
        }
        L.length = L.length - 1;
        return 1;
    }
    else
        return 0;
}

顺序表有序插入

 本题要求实现一个函数，要求将指定元素插入到有序表的合适位置，使得插入后仍然保持有序，若插入失败返回0；插入成功则返回1，并且顺序表的长度加1.

int SqInsert(SqList &L,ElemType e)
{
    int i;
    if(L.length==MAXSIZE)return 0;
    for(i=L.length-1;i>=0;i--)
    {
        if(L.elem[i]>e)L.elem[i+1] = L.elem[i];
        else break;
    }
    L.elem[i+1] = e;
    L.length++;
    return 1;
}

2.链表

带头结点单链表的查询

H为单链表的头指针，key为待查找的值（第一个为参考，第二个为准）

int Get_LinkList(LinkList H,ElemType key)
{
    LinkList t;
    int i;
    t = H->next;
    for(i=1;t!=NULL;i++)
    {
        if(t->data == key)
        {
            return i;
        }
        t = t->next;
    }
    if(t == NULL)
    return 0;
}

ElementType FindKth( List L, int K )
{
    int count = 1;
    PtrToLNode p = L;
    
    while(L!=NULL&&count<K)
    {
        p = p->Next;
        count++;
    }
    if(p&&count==K)
        return p->Data;
    else
        return ERROR;
}

带头结点单链表的插入

H为单链表的头指针，i为插入位置，e为新插入的值（第一个为参考，第二个为准）

Status ListInsert(LinkList &H,int i,ElemType e)
{
   LinkList t,pi,n;
   pi = (LinkList)malloc(sizeof(LNode));
   int j = 1;
   t = H->next;
   n = H;
   for(j = 1;j<=i;j++)
   {
       if(j==i)
       {
           pi->data = e;
           pi->next = t;
           n ->next = pi;
       }
       n = t;
       t = t->next;
   }
    return OK;
}

本题要求实现带头结点的单链表插入操作，插入成功返回1，否则返回0。 

int insert_link ( LinkList L,int i,ElemType e)
{
    if(i<=0)return 0;
    
    LinkList p = L;
    LinkList pre = p;
    int count = 1;
    
    if(!L)return 0;
    
    while(p)
    {
        pre = p;
        p = p->next;
        if(count == i)break;
        if(p==NULL)break;
        count++;
    }
    
    if(count!=i)return 0;//插入位置越界检查
    
    LinkList pr = malloc(sizeof(struct LNode));
    pr->data = e;
    
    pre->next = pr;
    pr->next = p;
    return 1;
    
}

带头结点单链表的删除

H为单链表的头指针，i为删除位置（第一个为参考，第二个为准）

Status ListDelete(LinkList &H,int i)
{
    LinkList t,n;
    t = H->next;
    n = H;
    int j;
    for(j=1;j<=i;j++)
    {
        if(j==i)
        {
            n->next = t->next;
        }
        n = t;
        t = t->next;
        
    }
}

本题要求实现删除单链表的第i个元素结点，删除成功返回1，否则返回0。

int delete_link ( LinkList L,int i)
{
   if(i<=0)return 0;
   LinkList p = L;
   int count = 1;
    
    while(p&&count<i)
    {
        p = p->next;
        count++;
    }
    if(p->next == NULL)return 0;
    LNode*pre = p->next;
    p->next = pre->next;
    free(pre);
    return 1;
}

两个有序链表序列的合并

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

 
List Merge( List L1, List L2 ) {
	List pa, pb, pc, L;
	L = (List)malloc(sizeof(struct Node));    //申请一个头结点L.
	pa = L1->Next;    //指针pa指向L1的第一个结点。
	pb = L2->Next;    //指针pb指向L2的第一个结点。
	pc = L;    //指针pc指向上面创立的头结点L.
	while ( pa && pb ) {    //当L1和L2链表都没有遍历完成的时候。
		if ( pa->Data <= pb->Data ) {    //若pa结点的数据小。
			pc->Next = pa;    //把pa串入L中。
			pc = pa;    //pc移向当前最后一个结点pa，这也是尾插。
			pa = pa->Next;    //在L1链表中，更新pa位置。
		} else {
			pc->Next = pb;
			pc = pb;
			pb = pb->Next;
		}
	}
    /*如果L1未遍历完，将L1全部串入L，如果L2未遍历完，将L2全部串入L*/
	pc->Next = pa ? pa : pb;
	L1->Next = NULL;
	L2->Next = NULL;
	
	return L;
}

3.栈和队列

顺序栈的基本运算

编写函数实现顺序栈的初始化、出栈、入栈运算。

 Status iniStack(Sqstack&S)
 {
     S.base = (SElemType*)malloc(100*sizeof(SElemType));
     S.top = S.base;
     S.stacksize = 100;
 }
Status push(Sqstack&S,SElemType x)
{
    if(S.top - S.base >= S.stacksize)
        return 0;
    *S.top = x;
    S.top++;
    return 1;
}
Status pop(Sqstack&S,SElemType &e)
{
    if(S.base == S.top)
        return 0;
    S.top--;
    e =*S.top;
    return 1;
}

循环队列出队入队(详细见博客http://t.csdn.cn/S8ep1)

用一个数组表示循环队列，请编写算法实现循环队列的初始化、入队和出队操作。

void InitQ(SqQueue &Q,int N)
{
    Q.base = (int*)malloc(N*sizeof(int));
    Q.front = 0;
    Q.rear = Q.front;
}

void AddQ(SqQueue &Q,int x)
{
    if((Q.rear+1)%N==Q.front)
    {
        printf("Queue Full\n");
    }
    else{
        Q.base[Q.rear]=x;
        Q.rear=(Q.rear+1)%N;
    }
}
Status DeleteQ(SqQueue &Q,int &e)
{
    if(Q.rear == Q.front)
    {
        printf("Queue Empty\n");
        return 0;
    }
    e = Q.base[Q.front];
    Q.front = (Q.front+1)%N;
    return 1;
}

循环队列入队出队操作（详细见博客http://t.csdn.cn/mkfmL）

Status InitQueue(SqQueue& Q) 
{

	Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
	if (!Q.base)
		exit(OVERFLOW);
	Q.front = Q.rear = 0;
	return OK;
}


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;
	return OK;
}


Status DeQueue(SqQueue& Q, QElemType& e) 
{
	if (Q.front == Q.rear)
		return ERROR;
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXQSIZE;
	return OK;
}

另类堆栈 

在栈的顺序存储实现中，另有一种方法是将Top定义为栈顶的上一个位置。请编写程序实现这种定义下堆栈的入栈、出栈操作。如何判断堆栈为空或者满？

注意：如果堆栈已满，Push函数必须输出“Stack Full”并且返回false；如果队列是空的，则Pop函数必须输出“Stack Empty”，并且返回ERROR。

解题思路：
1、题目中说的上一个，是形式上的上一个，它脑袋顶上的一个而不是前一个。
2、审好题，在pop中如果有值返回的是数。其他的按常规处理，进栈先进后加，出栈先退到前一个再出栈。

bool Push(Stack S,ElementType X)
{
    if(S->Top == S->MaxSize)
    {
        printf("Stack Full\n");
        return false;
    }
    else
    {
        S->Data[S->Top++] = X;
        return true;
    }
}

ElementType Pop(Stack S)
{
    if(S->Top == 0)
    {
        printf("Stack Empty\n");
        return ERROR;
    }
    else
    {
        return S->Data[--S->Top];
    }
}

十进制转二进制（顺序栈设计和应用）

设计一个顺序栈，并利用该顺序栈将给定的十进制整整数转换为二进制并输出。

#define MaxSize 100    /* 栈最大容量 */
int top;        /* 栈顶指针 */
int mystack[MaxSize];    /* 顺序栈 */

/*判栈是否为空，空返回true，非空返回false */
bool isEmpty();

/* 元素x入栈 */
void Push(int x);

/* 取栈顶元素 */
int getTop();

/* 删除栈顶元素 */
void Pop();

bool Push( Stack S, ElementType X ){
	if(S->Top==S->MaxSize){
		printf("Stack Full\n");
		return false;
	}
	else{
		S->Data[S->Top++]=X;
		return true;
	}
}


ElementType Pop( Stack S ){
	if(S->Top==0){
		printf("Stack Empty\n");
		return ERROR;
	}
	else{
		return S->Data[--S->Top];
	}
}

进制转换

本题要求实现十进制转R（R<10 && R>0）进制。

接口参数解释：其中 S 为顺序栈， x 是入栈元素的值；n是要转换的十进制数，R则是要转换成的进制 ，e是出栈元素。函数类型Status代表状态，正确完成入栈运算返回OK，由于栈满无法正常入栈则返回OVERFLOW。

 
Status iniStack(Sqstack &S)
{
    S.base = (int*)malloc(stack_INIT_SIZE*sizeof(SElemType));
    if(!S.base)
        return 0;
    S.top = S.base;
    S.stacksize = stack_INIT_SIZE;
    return 1;
}
Status push(Sqstack &S,SElemType x)
{
    if(!S.base)
        return 0;
    if(S.top - S.base >= S.stacksize)
    {
        S.base = (int*)realloc(S.base,(S.stacksize+ stackINCREMENT)*sizeof(SElemType));
        if(!S.base)
             return 0;
        S.top = S.base + S.stacksize;
    }
    *S.top++ = x;
    return 1;
}
Status pop(Sqstack &S,SElemType &e)
{
    if(!S.base||S.top == S.base)
        return 0;
    e = *--S.top;
    return 1;
}
void conversion(int n,int R)
{
    Sqstack S;
    iniStack(S);
    SElemType e;
    while(n)
    {
        push(S,n%R);
        n /= R;
    }
    while(S.top!=S.base)
    {
        pop(S,e);
        printf("%d",e);
    }
}

排队叫号系统

编写程序实现银行排队叫号系统，采用链队列作为存储结构。

Status InitLinkQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front)
        return 0;
    Q.front->next = NULL;
    return  1;
}
Status EnLinkQueue(LinkQueue &Q,QElemType e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p)
        return 0;
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear  = p;
    return 1;
}
Status DeLinkQueue(LinkQueue &Q,QElemType &e)
{
    QueuePtr p;
    if(Q.front == Q.rear)
        return 0;
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return 1;
}
Status QueueEmpty(LinkQueue Q)
{
    if(Q.front == Q.rear)
        return 1;
    else
        return 0;
}

5.二叉树

 求叶子结点个数

#include <iostream>
using namespace std;
void creat(BiTree &T)//创建
{
    char ch;
    cin>>ch;
    if(ch=='#')
    {
        T=NULL;
        return;
    }
    else
    {
        T= (BiTree)malloc(sizeof(BiTNode));
        T->data=ch;
        creat(T->lchild);
        creat(T->rchild);
    }
}
 
 
    
 
int  countleaf(BiTree T)
{ 
    if (T==NULL) {
        return 0;
    }

    if ((T->lchild == NULL)&& (T->rchild== NULL)) {
        return 1;
    }
    
    else return countleaf(T->lchild)+  countleaf(T->rchild);   
}
 

后缀表达式

本题要求实现一个函数，输出二叉树表示的表达式的后缀式。

void Suffix(BiTree T)
{
    if(T)
    {
        Suffix(T->lchild);
        Suffix(T->rchild);
        printf("%c ",T->data);
    }
}

哈夫曼编码

编写函数实现哈夫曼编码。输入结点个数(保证个数>1)及各结点的权值，为各结点进行编码。

其中 HT 为哈夫曼树，n 为叶子结点个数， HC 为哈夫曼编码。

void CreateHuffman_tree(HuffmanTree &HT,int n)
{
    int m, s1, s2, i;
    if (n <= 1)
        return;
    m = 2 * n - 1;
    HT = new HTNode[m + 1];  //0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点
    for (i = 1; i <= m; ++i) //将1~m号单元中的双亲、左孩子，右孩子的下标都初始化为0
    {
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    for (i = 1; i <= n; ++i) //输入前n个单元中叶子结点的权值
        scanf("%d",&HT[i].weight);
    /*――――――――――初始化工作结束，下面开始创建赫夫曼树――――――――――*/
    for (i = n + 1; i <= m; ++i)
    { //通过n-1次的选择、删除、合并来创建赫夫曼树
        Select(HT, i - 1, s1, s2);
        //在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,
        // 并返回它们在HT中的序号s1和s2
        HT[s1].parent = i;
        HT[s2].parent = i;
        //得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i
        HT[i].lchild = s1;
        HT[i].rchild = s2;                            //s1,s2分别作为i的左右孩子
        HT[i].weight = HT[s1].weight + HT[s2].weight; //i 的权值为左右孩子权值之和
    }                                                 
} 
    
    
/*建立n个叶子结点的哈夫曼树*/
void Huffman_code(HuffmanTree HT,HuffmanCode &HC,int n)
{
    char *cd;
    cd=(char*)malloc((n+1)*sizeof(char));
    int start,c,i,f;
    HC=new char*[n+1];
    cd[n-1]='\0';
    for(i=1;i<=n;++i)
    {
    start=n-1;
        c=i;f=HT[i].parent;
        while(f!=0)
        {
            --start;
            if(HT[f].lchild==c) cd[start]='0';
            else cd[start]='1';
            c=f;f=HT[f].parent;
        }
    HC[i]=new char[n-start];
    strcpy(HC[i],&cd[start]);
    }
    delete cd;
}//求哈夫曼编码

二叉树的遍历

输入二叉树的先序遍历序列，以#代表空树，输出该二叉树的中序遍历序列。例如，有如下二叉树，其先序序列为：ABC##DE#G##F###，输出其中序序列：CBEGDFA

void creat(BiTree &Tree)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        Tree=NULL;
    else
    {
        Tree=(BiTree)malloc(sizeof(BiTree));
        Tree->data = ch;
        creat(Tree->lchild);
        creat(Tree->rchild);
    }
}

void InOrder(BiTree Tree)
{
    if(Tree)
    {
        InOrder(Tree->lchild);
        
        printf("%c",Tree->data);
        
        InOrder(Tree->rchild);
    }
}

统计二叉树结点个数

int NodeCount ( BiTree T)
{
    int nodes;
    if(T==NULL)
        return 0;
    else
        nodes = 1+NodeCount(T->lchild)+NodeCount(T->rchild);
    return nodes;
}

求二叉树的深度

int Depth(BiTree T)
{
    if(T==NULL)
        return 0;
    else
    {
        if(Depth(T->lchild)>Depth(T->rchild))
            return Depth(T->lchild)+1;
        else
            return Depth(T->rchild)+1;
    }
}

6.图

 图的创建（邻接矩阵）

本题要求建立一个无向图，采用邻接矩阵做为存储结构。G 为图，采用邻接矩阵存储结构，v 是顶点的值。

int locate(MGraph G,char v)
{
    int temp=0;
    for(temp=0;temp<G.vexnum;temp++)
    {
        if(G.vexs[temp]==v){
            return temp;
        }
    }
}
void CreatMGraph(MGraph &G)
{
    int i=0,temp,j,h,z,min;
    scanf("%d %d",&G.vexnum,&G.arcnum);
    if(G.vexnum==0||G.arcnum==0)
    {
        return;
    }
    getchar();
    char ch[G.arcnum][2];
    while((G.vexs[i]=getchar())!='\n')
    {
        i++;
    }
    for(i=0;i<G.vexnum;i++)
        for(temp=0;temp<G.vexnum;temp++)
            G.arcs[i][temp]=0;
   for(i=0;i<G.arcnum;i++)
    {
       for(j=0;j<2;j++)
           ch[i][j]=getchar();
       getchar();
       h=locate(G,ch[i][0]);
       z=locate(G,ch[i][1]);
       G.arcs[h][z]=1;
       G.arcs[z][h]=1;
    }
}

图的创建-邻接表

文章来源地址https://www.toymoban.com/news/detail-479128.html

int locate(ALGraph G,char v)
{
    int i;
    for(i=0;i<G.vexnum;i++)
    {
        if(v==G.vertices[i].data)
        {
            return i;
        }
    }
}
void CreatMGraph(ALGraph &G)
{
    int i=0,j,k,temp1,temp2,x;
    ArcNode *e;
    scanf("%d %d",&G.vexnum,&G.arcnum);
    if(G.vexnum==0)
        return;
    char ch[G.arcnum][2];
    getchar();
    while((G.vertices[i].data=getchar())!='\n')
    {
        G.vertices[i].firstarc=NULL;
        i++;
    }
    for(k=0;k<G.arcnum;k++)
    {
        for(x=0;x<2;x++)
        {
            ch[k][x]=getchar();
        }
        getchar();
        temp1=locate(G,ch[k][0]);
        temp2=locate(G,ch[k][1]);
        e=(ArcNode*)malloc(sizeof(ArcNode));
        e->adjvex=temp2;
        e->nextarc=G.vertices[temp1].firstarc;
        G.vertices[temp1].firstarc=e;
        e=(ArcNode*)malloc(sizeof(ArcNode));
        e->adjvex=temp1;
        e->nextarc=G.vertices[temp2].firstarc;
        G.vertices[temp2].firstarc=e;
    }
}

最小生成树（普里姆算法）

#include <iostream>
#define MVNum 100
#define MaxInt 32767 
using namespace std;

struct edge {
    char adjvex;
    int lowcost;
}closedge[MVNum];

typedef struct {
    char vexs[MVNum];
    int arcs[MVNum][MVNum];
    int vexnum, arcnum;
}AMGraph;

int LocateVex(AMGraph G, char v);//实现细节隐藏
int CreateUDN(AMGraph& G);//实现细节隐藏

int Min(AMGraph G) {
    int i;
    int index = -1;
    int min = MaxInt;
    for (i = 0; i < G.vexnum; ++i) {
        if (closedge[i].lowcost > 0 && closedge[i].lowcost < min) 
        {
            min = closedge[i].lowcost;
            index = i;
        }
    }
    return index;
}

void MiniSpanTree_Prim(AMGraph G, char u) {
    int k, j, i;
    char u0, v0;
    k = LocateVex(G, u);
    for (j = 0; j < G.vexnum; ++j) {
        if (j != k) {
            closedge[j].adjvex  = u;
                
            closedge[j].lowcost = G.arcs[k][j];
                
        }
    }
    closedge[k].lowcost = 0;
      
    for (i = 1; i < G.vexnum; ++i) {
        k = Min(closedge);
        u0 = closedge[k].adjvex;
        v0 = G.vexs[k];
        cout << u0 << "->" << v0 << endl;
        closedge[k].lowcost = 0;
        for (j = 0; j < G.vexnum; ++j)
            if (G.arcs[k][j] < closedge[j].lowcost) 
            {
                closedge[j].adjvex  = G.vex[k];  
                closedge[j].lowcost = G.arcs[k][j];      
            }
    }
}

int main() {
    AMGraph G;
    CreateUDN(G);
    char u;
    cin >> u;
    MiniSpanTree_Prim(G, u);
    return 0;
}

 最短路径（迪杰斯特拉算法）

#include <iostream>
using namespace std;

#define MaxInt 32767
#define MVNum 100  
typedef char VerTexType;
typedef int ArcType;

int* D = new int[MVNum];
bool* S = new bool[MVNum];
int* Path = new int[MVNum];

typedef struct {
    VerTexType vexs[MVNum];
    ArcType arcs[MVNum][MVNum];
    int vexnum, arcnum;
}AMGraph;

int LocateVex(AMGraph G, VerTexType v)//该实现细节隐藏
void CreateUDN(AMGraph& G);//该实现细节隐藏

void ShortestPath_DIJ(AMGraph G, int v0) {
    int v, i, w, min;
    int n = G.vexnum;

    for (v = 0; v < n; ++v) {
        S[v] = false;
        D[v] = G.arcs[v0][v];
        if (D[v] < MaxInt)  Path[v] = v0;
        else Path[v] = -1;
    }

    S[v0] = true;
    D[v0] = 0;

    for (i = 1; i < n; ++i) {
        min = MaxInt;
        for (w = 0; w < n; ++w)
            if (!S[w] && D[w] < min) 
            {
                v = w;
                min = D[w];
            }
        S[v] = true;
        for (w = 0; w < n; ++w)
            if (!S[w] && D[v] + G.arcs[v][w] < D[w]) 
            {
                D[w] = D[v] + G.arcs[v][w];
                Path[w] = v;
            }
    }
}

void DisplayPath(AMGraph G, int begin, int temp) {
    if (Path[temp] != -1) {
        DisplayPath(G, begin, Path[temp]);
        cout << G.vexs[Path[temp]] << "->";
    }
}

int main()
{
    AMGraph G;
    int i, j, num_start, num_destination;
    VerTexType start, destination;
    CreateUDN(G);
    cin >> start >> destination;
    num_start = LocateVex(G, start);
    num_destination = LocateVex(G, destination);
    ShortestPath_DIJ(G, num_start);
    DisplayPath(G, num_start, num_destination);
    cout << G.vexs[num_destination] << endl;
    return 0;
}

小岛计数（深度遍历）

#include <iostream>
void DFS(AMGraph G, int v)
{		
    cout<<v;			//访问第v个顶点
	visited[v] = true;
	
	for(int w = 0; w < G.vexnum; w++)		//依次检查邻接矩阵v所在的行
		if(G.arcs[v][w] != 0) && (!visited[w]))		//w是v的邻接点，如果w未访问，则递归调用DFS
			DFS(G, w);
}
int  DFSTraverse(AMGraph G)
{
    for(int i = 0;i<G.vexnum;i++)
        visited[i] = false;
    for(int i = 0;i<G.vexnum;i++)
    {
        if(!visited[i])
            DFS(G,i);
    }
    return 0;
}

广度遍历（邻接表实现）

void BFS(ALGraph *G,int i)
{
    int que[10];
    int front,rear;
    front = rear = 0;
    
    printf(" %d",i);
    visited[i] = 1;
    que[rear++] = i;
    while(rear!=front)
    {
        int j = que[front++];
        ArcNode *tmp = G->vertices[j].firstarc;
        while(tmp)
        {
            if(!visited[tmp->adjvex])
            {
                printf(" %d",tmp->adjvex);
                visited[tmp->adjvex] = 1;
                que[rear++] = tmp->adjvex;
            }
            tmp = tmp->nextarc;
        }
    }
}

 拓扑排序1

void topsort(ALGraph &G)
{
    EdgeNode *p;
    int i=0,k,m=0,a[G.n]={0};
    SeqStack s;
    InitStack_Sq(s);
    for(i=0;i<G.n;i++)
    {
        if(!G.adjlist[i].Indegree)
            Push_SeqStack(s,i);
    }
    while(!Empty_Sq(s))
    {
        Pop_SeqStack(s,i);
        printf("%s ",G.adjlist[i].vertex);
        a[m] = i;
        ++m;
        p=G.adjlist[i].firstedge;
        while(p!=NULL)
        {
            k = p->adjvex;
            --G.adjlist[k].Indegree;
            if(G.adjlist[k].Indegree==0)Push_SeqStack(s,k);
            p = p->next;
        }
    }
    if(m<G.n)
        printf("后续无法输出！");
}

 拓扑排序2（第二个为参考，手动实现栈的功能）

//求每个顶点的入度
void FindInDegree(ALGraph G, int indegree[]) {
	int i;
	//先将入度都初始化为0
	for (i = 0;i < G.vexnum;i++) {
		indegree[i] = 0;
	}
	//循环遍历邻接表
	for (i = 0;i < G.vexnum;i++) {
		ArcNode* p;
		p = G.vertices[i].firstarc;
		while (p) {
			//对应的入度数+1
			indegree[p->adjvex]++;
			p = p->nextarc;
		}
	}
}
int TopologicalSort(ALGraph G, int topo[]) {
	ArcNode* p;
	int i, j,gettop;
	int top = 0;//栈顶
	int stack[100];//辅助栈
	int indegree[100];//存储每个顶点的入度数
	FindInDegree(G, indegree);//求入度
	for (i = 0; i < G.vexnum;i++) {//循环indegree数组将入度为0的点加入栈中
		if (indegree[i] == 0) {
			stack[top++] = i;
		}
	}
	i = 0;
	//开始拓扑排序
	while (top != 0) {
		//取出栈顶元素
		top--;
		gettop = stack[top];//将取出的栈顶元素赋给gettop
		topo[i] = gettop;//将取出的栈顶元素存入topo数组
		i++;
		p = G.vertices[gettop].firstarc;//p记录当前元素的第一个边节点
		while (p) {//循环该顶点的边节点，并将对应的顶点入度数-1
			indegree[p->adjvex]--;//入度数-1
			if (indegree[p->adjvex] == 0) {//如果减1后入度为0，则加入栈中
				stack[top++] = p->adjvex;
			}
			p = p->nextarc;
		}
	}
	return 1;
}

//定义栈
typedef struct{
	int *base;
	int *top;
	int stacksize;
}spStack;
int indegree[100];	/*用indegree存放个顶点的入度*/
spStack S;//定义栈
void InitStack(spStack &S)//初始化栈
{
	S.base=new int[100];
	if(!S.base)
		exit(1);//退出
	S.top=S.base;
	S.stacksize = 100;
}
void Push(spStack &S,int i)//进栈
{
	if(S.top - S.base == S.stacksize)//栈满
		return;
	*S.top++ = i;
}
void Pop(spStack &S , int &i)//出栈
{
	if(S.top == S.base)
		return;
	i = *--S.top;
}
bool StackEmpty(spStack S)//栈空
{	
	if(S.top == S.base)
		return true;
	return false;
}
void FindInDegree(ALGraph G)//统计入度
 { 
   int i;
   ArcNode *p;/*p是指向边表节点的指针*/
   for(i=0;i<G.vexnum;i++)/*遍历赋值*/
     indegree[i]=0; 
   for(i=0;i<G.vexnum;i++)
   {
     p=G.vertices[i].firstarc;
     while(p!=NULL)
     {
       indegree[p->adjvex]++;/*入度加一，p->adjvex是下标*/
       p = p->nextarc;
     }
   }
 }

int TopologicalSort(ALGraph G , int topo[])//拓扑排序 书上原代码
{
	int i , m=0;
    FindInDegree(G);              				
    InitStack(S);/*栈S初始化*/
    for(i = 0; i < G.vexnum; ++i)
	if(!indegree[i])
        Push(S, i); /*入度为0进栈*/
	while(!StackEmpty(S))/*栈S非空*/
	{                		
		Pop(S, i);/*将栈顶顶点vi出栈*/
		topo[m]=i;/*将vi保存在topo中*/
		m++;                             		
		ArcNode *p = G.vertices[i].firstarc;    /*p指向vi的第一个邻接点*/
		while(p){
			int k = p->adjvex;					/*vk为vi的邻接点*/
			--indegree[k];                   	/*vi的每个邻接点的入度减一*/
			if(indegree[k] ==0)  Push(S, k);	/*若入度为0则入栈*/
			p = p->nextarc;                		/*p指向顶点vi下一个邻接结点*/
		}
	}

	if(m < G.vexnum)
		return 0;    			/*该有向图有回路，不能拓扑排序*/
	else 
		return 1;
}

 求采用邻接矩阵作为存储结构的有向图各顶点的出度

void outdegree(MGraph G) 
{
	for(int i = 0; i < G.vexnum; i++) 
    {
		int c = 0;
		for(int j = 0; j < G.vexnum; j++)
			if(G.arcs[i][j] == 1)
				c++;
		printf("%c:%d\n",G.vexs[i],c);
	}
}

 邻接矩阵存储图的深度优先遍历

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) )
{
    Vertex i;
    Visited[V] = 1;
    Visit(V);
    for(i = 0; i < Graph->Nv ; i++)
    {
        if(Graph->G[V][i] ==1&&!Visited[i])
        {
           DFS(Graph, i, Visit);
        }
    }
    return;
}

邻接表存储图的广度优先遍历

void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) )
{
    int queue[1010];
    int l=0,r=0;
    queue[r++]=S;
    (*Visit)(S);
    Visited[S]=true;
    PtrToAdjVNode tmp;
    while(l!=r)
    {
        tmp=Graph->G[queue[l++]].FirstEdge;
        while(tmp)
        {
            Vertex pos=tmp->AdjV;
            if(!Visited[pos])
            {
                Visit(pos);
                Visited[pos]=true;
                queue[r++]=pos;
            }
            tmp=tmp->Next;
        }
    }
}

7.查找和排序

折半查找(带#是考点)

int  Search_Bin(SSTable T, ElemType k)
{  
    int low,high,mid;
    low=1;
    high=T.length;
    while (low<=high)  //#
    {  
        mid= (low + high)/2;  //#
        if (T.R[mid] == k)    //#
            return  mid;
        else  if (k < T.R[mid])   
            high = mid - 1;   //#
        else   
            low = mid + 1;    //#
   }
   return 0 ;
}

 顺序查找(带#是考点)

int  Search_Seq (SSTable  T,ElemType  k)
{   int i; 
    T.R[0] = k;  //#
    for ( i= T.length; T.R[i]!= k ; --i );  //#
    return i ;   //#
}

 快速排序 (带#是考点)

void QuickSort(SqList &L, int low, int high)
{  
    int i;
    if (low<high )
    {  
        i=Partition(L,low,high);  //#
        QuickSort(L,low,i-1);     //#
        QuickSort(L,i+1,high);    //#
    }
}

哈希表的创建及查找(线性探查法)

void CreateHash(HashTable HT[],int n); //输入不大于m的n个不为0（0表示空值）的数，用线性探查法解决冲突构造散列表
int SearchHash(HashTable HT[],int key); //输入一个值key，在散列表中查找key位置

//输入不大于m的n个不为0（0表示空值）的数，
//用线性探查法解决冲突构造散列表
void CreateHash(HashTable HT[], int n) {//创作不易，点个赞吧，新春快乐~
	int hash_table[m];//创建一个辅助数组 
	int temp;//存放余数 
	for(int i=0; i<n; i++)
		cin >> hash_table[i]; 
	for(int i=0; i<m; i++)
		HT[i].key = 0;//初始化HT数组 
	for(int i=0; i<n; i++) {
		temp = hash_table[i] % 13;//求余数 
		if(HT[temp].key==0) {//如果正好有空就放进去 
			HT[temp].key = hash_table[i];
		} else { 
			int flag=0;
			for(int j=temp+1; j<n; j++) {//从余数位置往后看有没有空余位置 
				if(HT[j].key==0) {//如果有位置就放进去 
					HT[j].key = hash_table[i];
					flag = 1;
					break;
				}
			}
			if(flag==0) {//如果还是没有位置 
				for(int j=0; j<temp; j++) {//就从0位置往后找，找到余数位置之前 
					if(HT[j].key==0) {
						HT[j].key = hash_table[i];
						break;
					}
				}
			}
		}
	}
}
//输入一个值key，在散列表中查找key位置
int SearchHash(HashTable HT[],int key) {
	int temp = key % 13;//求余数
	for(int i=temp; i<m; i++) {//从余数位置往后查 
		if(HT[i].key == key)
			return i;
	}
	for(int i=0; i<temp; i++) {//从头查到余数位置之前 
		if(HT[i].key == key)
			return i;
	}
	return -1;
}

二叉排序树(带#是考点)

 void BSTInsert( BSTree &T, BSTree s)
{
    if(T==NULL)
        T=s;
    else if(s->data<T->data)
        BSTInsert(T->lchild,s);  //#
    else 
        BSTInsert(T->rchild,s);  //#
}

void BSTCreate(BSTree  &T)
{   
    ElemType x;  BSTree  s;
    T=NULL;
    cin>>x;
    while (x!=-1)
    {  
        s=new BSTNode;
        s->data=x;
        s->lchild=s->rchild=NULL;
        BSTInsert(T,s);          //#
        cin>>x;
    }
}

BSTree BSTSearch(BSTree T, ElemType k)
{  
    if(!T || k == T->data)    //#
        return T;
    if(k<T->data)
        return  BSTSearch(T->lchild,k);  //#
    else
        return  BSTSearch (T->rchild,k); //#
}

基于顺序表的直接插入排序

到了这里，关于PTA函数题相关接口(未完)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！