数据结构上机习题汇总

@[toc]

1.约瑟夫问题

#include <stdio.h>
#include <stdlib.h>

#define LEN sizeof(struct node *)

struct node{
    int data;
    struct node *link;
};

void Josephu(int n, int m, int k){
    int i;
    struct node *H, *d, *p;
    H = (struct node *)malloc(LEN);   
    H->data = 1;           /* 设置第一个结点 */
    d = H;                      /* d 用于指向最后一个结点 */
    for (i = 1; i<n; i++)     /* 循环中产生n-1个结点 */
    { p = (struct node *)malloc(LEN); 
      p->data = i;   d->link = p;   d = p;  /* 新结点链在最后 */  
    }   d->link = H;   /* 封闭形成无头结点的循环链表 */

    p = H;
    for (i=0; i<k-1; i++) p = p->link;  /* 找开始结点 */
    while (p->link != p) /* 未到最后一个结点 */
    { 
        for (i=0; i<m; i++) p = p->link; /* 开始报数 */
        printf(" %-4d",p->link->data); 
        /* 打印结点p->link */
        p->link = p->link->link;   /* 删除已打印结点 */
  } 
    printf("%-4d\n",p->data);  // 打印最后结点 
}

int main(){
    int n,m,k;
    printf("enter three numbers n,m,k:");//n是人数，k是开始序号，m是出列的标志
    scanf("%d %d %d",&n,&m,&k);
    Josephu(n,m,k);

    return 0;
}

2.一元多项式的加法运算

#include <stdio.h>
#include <stdlib.h>
 
typedef struct LinkNode{
    int coef;//系数
    int index;//指数
    struct LinkNode *next; 
}LinkNode,*LinkList; 
 
LinkList createLinkNode(){
    LinkList L=(LinkList) malloc(sizeof(LinkNode));
    L->next=NULL;   
    printf("请输入多项式（系数,指数）：");
    LinkNode *q=L,*p;
    int coef,index;
    scanf("%d,%d",&coef,&index);
    while(!(coef==0&&index==0)){
        p=(LinkNode *)malloc(sizeof(LinkNode));
        p->next=NULL;
        p->coef=coef;
        p->index=index;
        q->next=p;
        q=p;
        printf("请继续输入多项式（系数,指数）：");
        scanf("%d,%d",&coef,&index);
    }
    return L;
}
 
void add(LinkList L1,LinkList L2){
    LinkNode *p1,*temp;
    while(L2->next!=NULL){
        p1=L1;
        while(p1->next!=NULL&&p1->next->index!=L2->next->index){
            p1=p1->next;
        }
        temp=L2->next;
        L2->next=temp->next;
        temp->next=NULL;
        if(p1->next==NULL){
            temp->next=p1->next;
            p1->next=temp;
        }else{
            p1->next->coef+=temp->coef;
            free(temp);
            if(p1->next->coef==0){
                temp=p1->next;
                p1->next=temp->next;
                free(temp);
            }
        }
    }
    free(L2);
}
 
int main(){
    LinkList L1=createLinkNode();
    LinkList L2=createLinkNode();
    add(L1,L2);
    LinkNode *p=L1->next;
    if(p==NULL)return 0;
    while(p!=NULL&&p->next!=NULL){
        printf("%dx^%d+",p->coef,p->index);
        p=p->next;
    }
    if(p!=NULL)printf("%dx^%d",p->coef,p->index);
    return 0;
}

3.计算矩阵鞍点

#include <stdio.h>

void setupmatrix(int m, int n,int M[m][n]){
    int i,j;
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            scanf("%d",&M[i][j]);
        }
    }
}
void printmatrix(int m,int n,int M[m][n]){
    int i,j;
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            printf("%d ",M[i][j]);
        }
        printf("\n");
    }
}
int saddlepoint(int m,int n,int M[m][n]){
    int i,j,k;
    int row,col;
    for(i=0;i<m;i++){
        int min = M[i][0];
        for(j=0;j<n;j++){
            if(min>M[i][j]){
                min = M[i][j];
                col = j;
            }
        }
        int max = M[0][col];
        for(k=0;k<m;k++){
            if(max<M[k][col]){
                max = M[k][col];
                row = k;
            }
        }

        if(max == min){
            printf("the location is (%d,%d)\n",row,col);
            return max;
        }
    }
    return 0;
}
int main(){
    int m,n,num;
    printf("enetr m and n:");
    scanf("%d %d",&m,&n);

    int M[m][n];
    printf("enter a matrix:\n");

    setupmatrix(m,n,M);
    saddlepoint(m,n,M);

    printf("the saddle point is %d\n",saddlepoint(m,n,M));
    //printmatrix(m,n,M);

    return 0;
}

4.n阶魔方（n为奇数）

#include <stdio.h>
# define ROW 5

void MAGIC(int M[ROW][ROW],int n){   
    int i, j, num;
        
    i = 0;    
    j =  n/2;
    for (num = 1;num<=n*n; num++) { 
        //printf("(i,j) = (%d,%d)\n",i,j);
        if(M[i][j] == 0){
            M[i][j] = num;
        }else{
            i+=2;
            M[i][--j] = num;
        }
        if(i==0&&j==n-1){
            i++;
        }else if(i==0){
            i=n-1;j++;
        }else if(j==n-1){
            i--;j=0;
        }else{
            i--;j++;
        }
    }
}

int main(){
    int n = ROW;
    int i,j;
    int M[ROW][ROW];

    for (i=0; i<n; i++){
        for (j=0; j<n; j++){
            M[i][j] = 0;    // 清0 //
            printf("%4d",M[i][j]);
        }
        printf("\n");
    }
    MAGIC(M,n);

    for (i=0; i<ROW; i++){
        for (j=0; j<ROW; j++){
            printf("%4d",M[i][j]);
        }
        printf("\n");
    }
    return 0;
}

程序利用define行数来改变魔方大小，然后注释掉的一行语句可以用来追踪数字的位置变化情况。

5.稀疏矩阵的加法运算

#include <stdio.h>
#include <stdlib.h>

typedef struct threetuple{
    int x;//表示非零元素的行标
    int y;//表示非零元素的列标
    int value;//表示非零元的值
}Triple;//用来存放三元组中每一个非零元素的信息

typedef struct infor{
    int col;//列数
    int row;//行数
    int counts;//存放非零元的个数
}Tripledata;//用来存放三元组矩阵的信息

void printtuple(Triple m[],Tripledata n,int A[n.col][n.row]){//以矩阵形式输出两个三元祖
    int i,j;
    for(i=0;i<n.col;i++){
        for(j=0;j<n.row;j++){
           A[i][j]=0;//将所有元素赋值0
        }
    }
    for(i=0;i<n.counts;i++){
        A[m[i].x-1][m[i].y-1]=m[i].value;//把三元组非零元素在对应位置赋值
    }
    for(i=0;i<n.col;i++){
        printf("\n");
        for(j=0;j<n.row;j++){
           printf("%2d",A[i][j]);//以矩阵形式打印
        }
    }
}
void add_print(Tripledata n,int A[n.col][n.row],int B[n.col][n.row]){
    int i,j;
    int C[n.col][n.row];//定义一个新矩阵用来存储相加后的结果。
    printf("\n执行矩阵相加，并打印结果：\n");
    for(i=0;i<n.col;i++){
        for(j=0;j<n.row;j++){
            C[i][j]=A[i][j]+B[i][j];//进行矩阵相加运算
            printf("%-3d",C[i][j]);//相加和打印同时进行
        }
        printf("\n");
    }
}

int main(){
    Tripledata t[2];//定义两个信息结构体来存放矩阵信息
    int i,j;
    for(i=0;i<=1;i++){//行列数信息
        printf("请输入第%d个元组的信息：\n依次输入行数，列数，非零元个数\n",i+1);
        scanf("%d%d%d",&t[i].col,&t[i].row,&t[i].counts);//对非零元素进行赋值操作
    }
    if(t[0].col!=t[1].col||t[0].row!=t[1].row){
        printf("该情况无法相加，程序退出");
        exit(0);
    }
    int a,b;
    a=t[0].counts;
    b=t[1].counts;
    Triple T1[a],T2[b];//定义两个非零元素信息结构体，前者对应A，后者是B
    printf("请输入每个三元组矩阵的非零元素的信息：\n");
    for(i=1,j=0;i<=t[0].counts;j++,i++){//每个三元组的信息；
        printf("依次输入元组1第%d个非零元素行标,列标,数值",i);
        scanf("%d%d%d",&T1[j].x,&T1[j].y,&T1[j].value);
    }
    for(i=1,j=0;i<=t[0].counts;j++,i++){//每个三元组的信息；
        printf("依次输入元组2第%d个非零元素行标,列标,数值",i);
        scanf("%d%d%d",&T2[j].x,&T2[j].y,&T2[j].value);
    }
    int A[t[0].col][t[0].row];//定义一个二维数组来存放矩阵信息
    int B[t[1].col][t[1].row];//同上
    printf("\nA的矩阵形式：");
    printtuple(T1,t[0],A);//以矩阵形式打印A
    printf("\nB的矩阵形式：");
    printtuple(T2,t[1],B);//以矩阵形式打印B
    add_print(t[0],A,B);
    return 0;
}

6.“八皇后”问题

#include<stdio.h>
#define N 8

char board[N+2][N+2];
int count = 0;

struct Pos{
    int yos;   //行偏移量
    int xos;   //列偏移量
};

struct Pos pos[3] = { { -1, -1 }, { -1, 0 }, { -1, 1 } };

void Init(void){
    for (int row = 0; row < N + 2; row++){
        for (int col = 0; col < N + 2; col++){
            board[0][col] = '#';
            board[N + 1][col] = '#';
            board[row][0] = '#';
            board[row][N + 1] = '#';
        }
    }
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            board[i][j] = ' ';
        }
    }
}

void Show(void){
    for (int i = 0; i < N + 2; i++){
        for (int j = 0; j < N + 2; j++){
            printf("%c", board[i][j]);
        }
        printf("\n");
    }
}

int Check(int row, int col){
    int ret = 1;
    int nr;
    int nc;
    for (int i = 0; i < 3 && ret; i++){
        nr = row;
        nc = col;
        while (ret&&board[nr][nc] != '#'){
            if (board[nr][nc] == '*'){
                ret = 0;
                break;
            }
            nr = nr + pos[i].yos;
            nc = nc + pos[i].xos;
        }
    }
    return ret;
}

void Find(int row){
    if (row>N){
        Show();
        count++;
        printf("%d\n",count);
    }
    else{
        for (int col = 1; col <= N; col++){
            if (Check(row, col)){
                board[row][col] = '*';
                Find(row + 1);
                board[row][col] = ' ';
            }
        }
    }
}
int main(){
    Init();
    Find(1);

    return 0;
}

7.中缀表达式和后缀表达式

#include <stdio.h>
#include <stdlib.h>
struct shu{
    int front;
    int rear;
}OPND;
struct others{
    char *base;
    char *top;
    int size;
}OPTR;
char bijiao(char x, char y) {
    if (x == '+') {
        if (y == '+' || y == '-' || y == ')' || y == '#')
            return('>');
        else
            return('<');
    }
    if (x == '-') {
        if (y == '+' || y == '-' || y == ')' || y == '#')
            return('>');
        else
            return('<');
    }
    if (x == '*') {
        if (y == '(')
            return('<');
        else
            return('>');
    }
    if (x == '/') {
        if (y == '(')
            return('<');
        else
            return('>');
    }
    if (x == '(') {
        if (y == ')')
            return('=');
        if (y == '+' || y == '-' || y == '*' || y == '/' || y == '%' || y == '(')
            return('<');
    }
    if (x == ')') {
        if (y == '+' || y == '-' || y == '*' || y == '/' || y == '%' || y == ')' || y == '#')
            return('>');
    }
    if (x == '#') {
        if (y == '+' || y == '-' || y == '*' || y == '/' || y == '%' || y == '(')
            return('<');
        if (y == '#')
            return('=');
    }
}
void main() {
    int n, i, j, k, s[50], flag;
    char sopnd[50][50], str[50],t;

    scanf("%d", &n);
    getchar();
    for (i = 0;i < n;i++) {
        flag = 0;
 
        OPND.front = 0;
        OPND.rear = 0;
        OPTR.size = 50;
        OPTR.base = (char *)malloc(OPTR.size * sizeof(char));
        OPTR.top = OPTR.base;
        *OPTR.top++ = '#';
 
 
        for (j = 0;j < 50;j++)
            s[j] = 0;
 
        gets(str);
        for (j = 0;str[j] != '#' || *(OPTR.top - 1) != '#';j++) {
            if (str[j] >= '0' && str[j] <= '9') {
                for (k = 0;(str[j] <= '9' && str[j] >= '0') || str[j] == '.';) {
                    sopnd[OPND.rear][k] = str[j];
                    j++;
                    k++;
                }
                sopnd[OPND.rear][k] = '\0';
                OPND.rear++;
                j--;
            } 
             else {
              t= bijiao(*(OPTR.top - 1), str[j]); {
                if(t=='<') {
                    *OPTR.top++ = str[j];
                    
                }
                if(t=='='){
                    OPTR.top--;
                    
                }
                if(t=='>') {
                    for (;OPND.front < OPND.rear;OPND.front++) {
                        if (flag == 1)
                            printf(" %s", sopnd[OPND.front]);
                        else
                            printf("%s", sopnd[OPND.front]);
                        flag = 1;
                    }
                    printf(" %c", *--OPTR.top);
                    j--;
                    
                }
                }
            }
        }
        printf("\n");
    }
}

8.二叉排序树

#include <stdio.h>
#include <stdlib.h>

struct Treenode
{   int Data;
    struct Treenode *Lchild, *Rchild;
};
void Setuptree(struct Treenode **T, int b,  struct Treenode *p, int tag )
{   struct Treenode *x;
    x=(struct Treenode *) malloc(sizeof(struct Treenode));
    x->Data = b; x->Lchild = 0;  x->Rchild = 0;
    if ((*T)==0) (*T)=x;
    else if (p != 0)
       {  if (tag==0) { x->Lchild = p->Lchild;  p->Lchild = x; } 
          else { x->Rchild = p->Rchild; p->Rchild = x;  }
       }
    else  if (tag==0)
    {  p = (*T);
       while (p->Lchild !=0) p=p->Lchild;
       p->Lchild = x;
    }
    else  { p = (*T); 
                  while (p->Rchild !=0) p=p->Rchild;
               p->Rchild = x;
                }
}
void InOrder(struct Treenode *T){ 
    if (T!= 0){ 
        InOrder(T->Lchild);
        printf("%4d",T->Data);
        InOrder(T->Rchild);
    } 
}

int main(){
    struct Treenode *T=0,*p, *(Q[20]);
    int Front,Rear;
    int A[100];  
    int i=0,j=0;
    scanf("%d",&A[0]);
    while(A[j++]!=-1){
        scanf("%d",&A[j]);
    }
    Setuptree(&T, A[i++], p, 0);    // 二叉树根结点  
    //printf("i = %d,j = %d\n",i,j);
    int n = j-1;
    /*for(int k=0;k<n;k++){
        printf("%d ",A[k]);
    }*/
    while (i<n){ 
        Front=0;  
        Rear=0;  
        Q[++Rear] = T;
        while (Front<Rear){ 
            p = Q[++Front];
            if (p->Lchild!=0) Q[++Rear] = p->Lchild;        // 左子树 
            else{  
                if (i<n) Setuptree(&T, A[i++], p, 0); 
            }
            if (p->Rchild!=0) Q[++Rear] = p->Rchild;       // 右子树 
            else{ if (i<n) Setuptree(&T, A[i++], p, 1);  
            }
        }
    }
    InOrder(T);

    return 0;
}

9.有向图与有向路径

#pragma once
#include<stdio.h>
#include<stdlib.h>
#define StackSize 100
typedef int DataType;   //栈元素类型定义
typedef struct{
    DataType stack[StackSize];
    int top;
}SeqStack;
//将栈初始化为空栈只需要把栈顶指针top置为
void InitStack(SeqStack *S){
    S->top=0;//把栈顶指针置为0
}
//判断栈是否为空，栈为空返回1，否则返回0
int StackEmpty(SeqStack S){
    if(S.top==0)
        return 1;
    else
        return 0;
}
//取栈顶元素。将栈顶元素值返回给e，并返回1表示成功；否则返回0表示失败。
int GetTop(SeqStack S,DataType *e){
    if(S.top<=0){       //在取栈顶元素之前，判断栈是否为空
        printf("栈已经空!\n");
        return 0;
    }else{
        *e=S.stack[S.top-1];    //在取栈顶元素
        return 1;
    }
}
//将元素e进栈，元素进栈成功返回1，否则返回0
int PushStack(SeqStack *S,DataType e){
    if(S->top>=StackSize){  //在元素进栈前，判断是否栈已经满
        printf("栈已满，不能进栈！\n");
        return 0;
    }else{
        S->stack[S->top]=e; //元素e进栈
        S->top++;   //修改栈顶指针
        return 1;
    }
}
//出栈操作。将栈顶元素出栈，并将其赋值给e。出栈成功返回1，否则返回0
int PopStack(SeqStack *S,DataType *e){
    if(S->top<=0){  //元素出栈之前，判断栈是否为空
        printf("栈已经没有元素，不能出栈!\n");
        return 0;
    }else{
        S->top--;   //先修改栈顶指针，即出栈
        *e=S->stack[S->top]; //将出栈元素赋值给e
        return 1;
    }
}
//求栈的长度，即栈中元素个数，栈顶指针的值就等于栈中元素的个数
int StackLength(SeqStack S){
    return S.top;
}
//清空栈的操作
void ClearStack(SeqStack *S){
    S->top=0;
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"SeqStack.h"
typedef char VertexType[4];
typedef char InfoPtr;
typedef int VRType;
#define MaxSize 50  //最大顶点个数
typedef enum{DG,DN,UG,UN}GraphKind; //图的类型：有向图、有向网、无向图和无向网
//边结点的类型定义
typedef struct ArcNode{
    int adjvex;     //弧指向的顶点的位置
    InfoPtr *info;  //弧的权值
    struct ArcNode *nextarc;    //指示下一个与该顶点相邻接的顶点
}ArcNode;
//头结点的类型定义
typedef struct VNode{
    VertexType data;    //用于存储顶点
    ArcNode *firstarc;  //指示第一个与该顶点邻接的顶点
}VNode,AdjList[MaxSize];
//图的类型定义
typedef struct{
    AdjList vertex;  //头结点
    int vexnum,arcnum;  //图的顶点数目与弧的数目
    GraphKind kind; //图的类型
}AdjGraph;
//求图G中从顶点u到顶点v的一条简单路径
void BriefPath(AdjGraph G,int u,int v){
    int k,i;
    SeqStack S;
    ArcNode *p;
    int visited[MaxSize];
    int parent[MaxSize];    //存储已经访问顶点的前驱顶点
    InitStack(&S);
    for(k=0;k<G.vexnum;k++)
        visited[k]=0;   //访问标志初始化
    PushStack(&S,u);    //开始顶点入栈
    visited[u]=1;       //访问标志置为1
    while(!StackEmpty(S)){  //广度优先遍历图，访问路径用parent存储
        PopStack(&S,&k);
        p=G.vertex[k].firstarc;
        while(p!=NULL){
            if(p->adjvex==v){   //如果找到顶点v
                parent[p->adjvex]=k;        //顶点v的前驱顶点序号是k
                printf("the path from %s to %s is:",G.vertex[u].data,G.vertex[v].data);
                i=v;
                do{         //从顶点v开始将路径中的顶点依次入栈
                    PushStack(&S,i);
                    i=parent[i];
                }while(i!=u);
                PushStack(&S,u);
                while(!StackEmpty(S)){ //从顶点u开始输出u到v中路径的顶点
                    PopStack(&S,&i);
                    printf("%s ",G.vertex[i].data);
                }
                printf("\n");
            }else if(visited[p->adjvex]==0){    //如果未找到顶点v且邻接点未访问过，则继续寻找
                visited[p->adjvex]=1;
                parent[p->adjvex]=k;
                PushStack(&S,p->adjvex);
            }
            p=p->nextarc;
        }
    }
}
//返回图中顶点对应的位置
int LocateVertex(AdjGraph G,VertexType v){
    int i;
    for(i=0;i<G.vexnum;i++)
        if(strcmp(G.vertex[i].data,v)==0)
            return i;
    return -1;
}
//采用邻接表存储结构，创建无向图N
void CreateGraph(AdjGraph *G){
    int i,j,k,w;
    VertexType v1,v2;                   /*定义两个顶点v1和v2*/
    ArcNode *p;
    printf("please enter node and line: ");
    scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);
    printf("enter %d node:",G->vexnum);
    for(i=0;i<G->vexnum;i++)            /*将顶点存储在头结点中*/
    {
        scanf("%s",G->vertex[i].data);
        G->vertex[i].firstarc=NULL;     /*将相关联的顶点置为空*/
    }
    printf("please two nodes of the line:\n");
    for(k=0;k<G->arcnum;k++)            /*建立边链表*/
    {
        scanf("%s%s",v1,v2);
        i=LocateVertex(*G,v1);
        j=LocateVertex(*G,v2);
        /*j为入边i为出边创建邻接表*/
        p=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=j;
        p->info=(InfoPtr*)malloc(sizeof(InfoPtr));
        /*将p指向的结点插入到边表中*/
        p->nextarc=G->vertex[i].firstarc;
        G->vertex[i].firstarc=p;
        /*i为入边j为出边创建邻接表*/
        p=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=i;
        p->info=NULL;
        p->nextarc=G->vertex[j].firstarc;
        G->vertex[j].firstarc=p;
    }
    (*G).kind=UG;
}
//销毁无向图G
void DestroyGraph(AdjGraph *G){
    int i;
    ArcNode *p,*q;
    for(i=0;i<G->vexnum;++i)        /*释放图中的边表结点*/
    {
        p=G->vertex[i].firstarc;    /*p指向边表的第一个结点*/
        if(p!=NULL)                 /*如果边表不为空，则释放边表的结点*/
        {
            q=p->nextarc;
            free(p);
            p=q;
        }
    }
    (*G).vexnum=0;                  /*将顶点数置为0*/
    (*G).arcnum=0;                  /*将边的数目置为0*/
}
//图G的邻接表的输出
void DisplayGraph(AdjGraph G){
    int i;
    ArcNode *p;
    printf("the number of node is %d",G.vexnum);
    for(i=0;i<G.vexnum;i++)
        printf("%s ",G.vertex[i].data);
    printf("\nthe number of line is:%d\n",2*G.arcnum);
    for(i=0;i<G.vexnum;i++)
    {
        p=G.vertex[i].firstarc;
        while(p)
        {
            printf("(%s,%s) ",G.vertex[i].data,G.vertex[p->adjvex].data);
            p=p->nextarc;
        }
        printf("\n");
    }
}
void main(){
    AdjGraph G;
    CreateGraph(&G);        /*采用邻接表存储结构创建图G*/
    DisplayGraph(G);        /*输出无向图G*/
    BriefPath(G,0,4);       /*求图G中从顶点a到顶点e的简单路径*/
    DestroyGraph(&G);       /*销毁图G*/
    system("pause");
}

10.快速排序和希尔排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void ShellSort(int V[], int n){
    int compcnt=0,movecnt=0;
    
    int d=n, x, i, j,k;
    while (d > 1){   
        d = d/2;
        for (i=d; i<n; i++){     
            x = V[i];   
            j = i-d;
            while (j >= 0 && V[j] > x){
                compcnt++;
                movecnt++;
                V[j+d] = V[j];      
                j = j-d;
            }
            V[j+d] = x;
            movecnt++;
        }
    }
    printf("\nthe compcnt and movecnt of shellsort are %d and %d\n",compcnt,movecnt);
}

void QuickSort(int V[],int low, int high){  
    int i, j, x, k;
    int compcnt=0,movecnt=0;

    if (low <= high){   
        i=low+1;  j=high;  k=V[low];
        while (i<j){
            compcnt++;  
            while (low<j && V[j]>=k) j--;compcnt++;
            while (i<high && V[i]<k) i++;compcnt++;
            if (i<j){
                movecnt++;
                x=V[i];   V[i]=V[j];  V[j]=x;  
            }
        }
        if (low+1==high && V[low]<V[high]) j=low;
        V[low]=V[j];  V[j]=k;
        movecnt++;
        QuickSort(V, low, j-1);    QuickSort(V, j+1, high);
    }    
    printf("the compcnt and movecnt of quicksort are %d and %d\n",compcnt,3*movecnt);   
}

int main(){
    int A[100],B[100],i;
    srand(time(NULL));

    for(i=0;i<100;i++){
        A[i] = rand()%100;
        B[i] = A[i];
        printf("%d ",A[i]);
    }
    int n = sizeof(A)/sizeof(A[0]);

    ShellSort(A,n);
    printf("\n");
    for(i=0;i<100;i++){
        printf("%d ",A[i]);
    }
    QuickSort(B,0,n-1);
    printf("\n");
    for(i=0;i<100;i++){
        printf("%d ",B[i]);
    }
    return 0;
}