精华内容
下载资源
问答
  • 2018-12-21 21:03:44

    大数加法 

    #include<iostream>
    #include<string.h>
    using namespace std;
    int a[10005],b[10005];
    char s1[10005],s2[10005];
    int main(){
        while(cin>>s1>>s2){
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            int l1=strlen(s1),l2=strlen(s2);
            int k=l1>l2?l1:l2;
            for(int i=l1-1;i>=0;i--){
                a[l1-1-i]=s1[i]-'0';
            }
            for(int i=l2-1;i>=0;i--){
                b[l2-1-i]=s2[i]-'0';
            }
            for(int i=0;i<=k;i++){
                a[i]+=b[i];
                if(a[i]>9){
                    a[i]-=10;
                    a[i+1]++;
                }
            }
            if(a[k]){
                for(int i=k;i>=0;i--) cout<<a[i];
            }
            else{
                for(int i=k-1;i>=0;i--) cout<<a[i];
            }
            cout<<endl;
        }
        return 0;
    }
    

    斐波那契数列

    #include<iostream>
    using namespace std;
    typedef long long ll;
    ll a[10005];
    int fibo(int n){//递归
        if(n==1 || n==2) return 1;
        else return fibo(n-1)+fibo(n-2);
    }
    ll Fibo(int n){//非递归打表
        a[1]=a[2]=1;
        for(int i=3;i<=10000;i++){
            a[i]=a[i-1]+a[i-2];
        }
        return a[n];
    }
    int main(){
        int n;
        while(cin>>n){
            cout<<fibo(n)<<' '<<Fibo(n)<<endl;
        }
        return 0;
    }
    

    进制转化

    #include<iostream>
    #include<string>
    #include<algorithm>
    using namespace std;
    string ch(int n){
        string s="";
        while(n){
            s+=n%2+'0';
            n/=2;
        }
        reverse(s.begin(),s.end());
        return s;
    }
    int main(){
        int n;
        while(cin>>n){
            cout<<ch(n)<<endl;
        }
        return 0;
    }
    

    快排

    #include<iostream>
    using namespace std;
    int a[10005];
    void QSort(int a[],int  l,int r){
        if(l<r){
            int i=l,j=r,temp=a[l];
            while(i<j){
                while(i<j&&a[j]>=temp) j--;
                if(i<j) a[i++]=a[j];
                while(i<j&&a[i]<temp) i++;
                if(i<j) a[j--]=a[i];
            }
            a[i]=temp;
    		QSort(a,l,i-1);
    		QSort(a,i+1,r);
        }
    
    }
    int main(){
        int n;cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        QSort(a,1,n);
        for(int i=1;i<=n;i++) cout<<a[i]<<' ';
        cout<<endl;
        return 0;
    }
    
    

    直接插入排序

    #include<iostream>
    using namespace std;
    int a[10005];
    void InsertSort(int n){
        int j;
        for(int i=2;i<n;i++){
            if(a[i]<a[i-1]){
                a[0]=a[i];
                for(j=i-1;a[j]>a[0];j--)
                    a[j+1]=a[j];
                a[j+1]=a[0];
            }
        }
    }
    int main(){
        int n;cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        InsertSort(n);
        for(int i=1;i<=n;i++) cout<<a[i]<<' ';
        cout<<endl;
        return 0;
    }
    

    简单选择排序

    #include<iostream>
    using namespace std;
    int a[10005];
    void SelectSort(int n){
    
    }
    int main(){
        int n;cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        SelectSort(n);
        for(int i=1;i<=n;i++) cout<<a[i]<<' ';
        cout<<endl;
        return 0;
    }
    

     

    更多相关内容
  • 南航数据结构上机考试题目和所有题目代码。
  • 数据结构上机考试系统开题报告和英文翻译
  • 8576顺序线性表的基本操作 时间限制:1000MS 内存限制:1000K提交次数:9027 通过次数:2456 题型: 编程题语言: G++;GCC ...编写算法,创建初始化容量为LIST_INIT_SIZE的顺序表T,并实现插入、删除、遍历操作。...

    8576 顺序线性表的基本操作

    时间限制:1000MS  内存限制:1000K
    提交次数:9027 通过次数:2456

    题型: 编程题   语言: G++;GCC

     

    Description

     编写算法,创建初始化容量为LIST_INIT_SIZE的顺序表T,并实现插入、删除、遍历操作。本题目给出部分代码,请补全内容。

    #include<stdio.h>
    #include<malloc.h>
    #define OK 1 
    #define ERROR 0
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    #define ElemType int
    
    typedef struct
    {
    	int *elem;
    	int length;
    	int listsize;
    }SqList;
    
    int InitList_Sq(SqList &L)
    {
    // 算法2.3,构造一个空的线性表L,该线性表预定义大小为LIST_INIT_SIZE
    // 请补全代码
    
    }
    
    int Load_Sq(SqList &L)
    {
    // 输出顺序表中的所有元素
    	int i;
    	if(_________________________) printf("The List is empty!");  // 请填空
    	else
    	{
    		printf("The List is: ");
    		for(_________________________) printf("%d ",_________________________);  // 请填空
    	}
    	printf("\n");
    	return OK;
    }
    
    int ListInsert_Sq(SqList &L,int i,int e)
    {
    // 算法2.4,在顺序线性表L中第i个位置之前插入新的元素e
    // i的合法值为1≤i≤L.length +1
    // 请补全代码
    
    }
    
    int ListDelete_Sq(SqList &L,int i, int &e)
    {
    // 算法2.5,在顺序线性表L中删除第i个位置的元素,并用e返回其值
    // i的合法值为1≤i≤L.length
    // 请补全代码
    
    }
    
    int main()
    {
    	SqList T;
    	int a, i;
    	ElemType e, x;
    	if(_________________________)    // 判断顺序表是否创建成功
    	{
    		printf("A Sequence List Has Created.\n");
    	}
    	while(1)
    	{
    		printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
    		scanf("%d",&a);
    		switch(a)
    		{
    			case 1: scanf("%d%d",&i,&x);
    					if(_________________________) printf("Insert Error!\n"); // 判断i值是否合法,请填空
    					else printf("The Element %d is Successfully Inserted!\n", x); 
    					break;
    			case 2: scanf("%d",&i);
    					if(_________________________) printf("Delete Error!\n"); // 判断i值是否合法,请填空
    					else printf("The Element %d is Successfully Deleted!\n", e);
    					break;
    			case 3: Load_Sq(T);
    					break;
    			case 0: return 1;
    		}
    	}
    }
    

     

      1 #include<stdio.h>
      2 #include<malloc.h>
      3 #define OK 1
      4 #define ERROR 0
      5 #define LIST_INIT_SIZE 100
      6 #define LISTINCREMENT 10
      7 #define ElemType int
      8 
      9 typedef struct
     10 {
     11     int *elem;
     12     int length;
     13     int listsize;
     14 }SqList;
     15 
     16 int InitList_Sq(SqList &L)
     17 {
     18     L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
     19     if(!L.elem) return 0;
     20     L.length=0;
     21     L.listsize=LIST_INIT_SIZE;
     22     return OK;
     23 
     24 }
     25 
     26 int Load_Sq(SqList &L)
     27 {
     28 // 输出顺序表中的所有元素
     29     int i;
     30     if(L.length==0) printf("The List is empty!");  // 请填空
     31     else
     32     {
     33         printf("The List is: ");
     34         for(i=0;i<L.length;i++) printf("%d ",L.elem[i]);  // 请填空
     35     }
     36     printf("\n");
     37     return OK;
     38 }
     39 
     40 int ListInsert_Sq(SqList &L,int i,int e)
     41 {
     42 
     43 // 算法2.4,在顺序线性表L中第i个位置之前插入新的元素e
     44 // i的合法值为1≤i≤L.length +1
     45 // 请补全代码
     46     ElemType *q,*p,*newbase;
     47    if(i<1||i>L.length+1) return ERROR;
     48    if(L.length>L.listsize)
     49    {
     50        newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
     51        if(!L.elem)
     52        return ERROR;
     53         L.elem=newbase;
     54        L.listsize+=LISTINCREMENT;
     55    }
     56 
     57    q=&(L.elem[i-1]);
     58    for(p=&(L.elem[L.length-1]);p>=q;--p)
     59 
     60        *(p+1)=*p;
     61        *q=e;
     62        ++L.length;
     63 
     64    return OK;
     65 
     66 }
     67 
     68 int ListDelete_Sq(SqList &L,int i, int &e)
     69 {
     70 // 算法2.5,在顺序线性表L中删除第i个位置的元素,并用e返回其值
     71 // i的合法值为1≤i≤L.length
     72 // 请补全代码
     73     ElemType *q,*p;
     74     if(i<1||i>L.length) return ERROR;
     75     p=&(L.elem[i-1]);
     76     e=*p;
     77     q=L.elem+L.length-1;
     78     for(p++;p<=q;++p)
     79     *(p-1)=*p;
     80     --L.length;
     81     return OK;
     82 }
     83 
     84 int main()
     85 {
     86     SqList T;
     87     int a, i;
     88     ElemType e, x;
     89     if(InitList_Sq(T))    // 判断顺序表是否创建成功
     90     {
     91         printf("A Sequence List Has Created.\n");
     92     }
     93     while(1)
     94     {
     95         printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
     96         scanf("%d",&a);
     97         switch(a)
     98         {
     99             case 1: scanf("%d%d",&i,&x);
    100                     if(!ListInsert_Sq(T,i,x)) printf("Insert Error!\n"); // 判断i值是否合法,请填空
    101                     else printf("The Element %d is Successfully Inserted!\n",x);
    102                     break;
    103             case 2: scanf("%d",&i);
    104                     if(!ListDelete_Sq(T,i,e)) printf("Delete Error!\n"); // 判断i值是否合法,请填空
    105                     else printf("The Element %d is Successfully Deleted!\n",e);
    106                     break;
    107             case 3: Load_Sq(T);
    108                     break;
    109             case 0: return 1;
    110         }
    111     }
    112 }

    8577 合并顺序表

    时间限制:1000MS  内存限制:1000K
    提交次数:5339 通过次数:2251

    题型: 编程题   语言: G++;GCC

     

    Description

    顺序表的基本操作代码如下:
    #include<stdio.h>
    #include<malloc.h>
    #define OK 1
    #define ERROR 0
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    #define ElemType int
    
    typedef int Status;
    typedef struct
    {
        int *elem;
        int length;
        int listsize;
    }SqList;
    
    Status InitList_Sq(SqList &L) 
    {  // 算法2.3
      // 构造一个空的线性表L。
      L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
      if (!L.elem) return OK;        // 存储分配失败
      L.length = 0;                  // 空表长度为0
      L.listsize = LIST_INIT_SIZE;   // 初始存储容量
      return OK;
    } // InitList_Sq
    
    Status ListInsert_Sq(SqList &L, int i, ElemType e) 
    {  // 算法2.4
      // 在顺序线性表L的第i个元素之前插入新的元素e,
      // i的合法值为1≤i≤ListLength_Sq(L)+1
      ElemType *p;
      if (i < 1 || i > L.length+1) return ERROR;  // i值不合法
      if (L.length >= L.listsize) {   // 当前存储空间已满,增加容量
        ElemType *newbase = (ElemType *)realloc(L.elem,
                      (L.listsize+LISTINCREMENT)*sizeof (ElemType));
        if (!newbase) return ERROR;   // 存储分配失败
        L.elem = newbase;             // 新基址
        L.listsize += LISTINCREMENT;  // 增加存储容量
      }
      ElemType *q = &(L.elem[i-1]);   // q为插入位置
      for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;
                                      // 插入位置及之后的元素右移
      *q = e;       // 插入e
      ++L.length;   // 表长增1
      return OK;
    } // ListInsert_Sq
    
    Status ListDelete_Sq(SqList &L, int i, ElemType &e) 
    {  // 算法2.5
      // 在顺序线性表L中删除第i个元素,并用e返回其值。
      // i的合法值为1≤i≤ListLength_Sq(L)。
      ElemType *p, *q;
      if (i<1 || i>L.length) return ERROR;  // i值不合法
      p = &(L.elem[i-1]);                   // p为被删除元素的位置
      e = *p;                               // 被删除元素的值赋给e
      q = L.elem+L.length-1;                // 表尾元素的位置
      for (++p; p<=q; ++p) *(p-1) = *p;     // 被删除元素之后的元素左移
      --L.length;                           // 表长减1
      return OK;
    } // ListDelete_Sq
    
    编写算法,将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C。




    输入格式

    第一行:顺序表A的元素个数
    第二行:顺序表A的各元素(非递减),用空格分开
    第三行:顺序表B的元素个数
    第四行:顺序表B的各元素(非递减),用空格分开
    



    输出格式

    第一行:顺序表A的元素列表
    第二行:顺序表B的元素列表
    第三行:合并后顺序表C的元素列表
    



     

    输入样例

    5
    1 3 5 7 9
    5
    2 4 6 8 10
    



     

    输出样例

    List A:1 3 5 7 9 
    List B:2 4 6 8 10 
    List C:1 2 3 4 5 6 7 8
      1 #include<stdio.h>
      2 #include<malloc.h>
      3 #define OK 1
      4 #define ERROR 0
      5 #define LIST_INIT_SIZE 100
      6 #define LISTINCREMENT 10
      7 #define ElemType int
      8 
      9 typedef int Status;
     10 typedef struct
     11 {
     12     int *elem;
     13     int length;
     14     int listsize;
     15 }SqList;
     16 
     17 Status InitList_Sq(SqList &L)
     18 {  // 算法2.3
     19   // 构造一个空的线性表L。
     20   L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
     21   if (!L.elem) return OK;        // 存储分配失败
     22   L.length = 0;                  // 空表长度为0
     23   L.listsize = LIST_INIT_SIZE;   // 初始存储容量
     24   return OK;
     25 } // InitList_Sq
     26 int Load_Sq(SqList &L)
     27 {
     28     int i;
     29     for(i=0;i<L.length;i++)
     30         printf("%d ",L.elem[i]);
     31     printf("\n");
     32     return 1;
     33 }
     34 int ListLength(SqList L)
     35 {
     36     return L.length;
     37 }
     38 int GetElem(SqList L,int i,ElemType &e)
     39 {
     40     e=L.elem[i-1];
     41     return OK;
     42 }
     43 Status ListInsert_Sq(SqList &L, int i, ElemType e)
     44 {  // 算法2.4
     45   // 在顺序线性表L的第i个元素之前插入新的元素e,
     46   // i的合法值为1≤i≤ListLength_Sq(L)+1
     47   ElemType *p;
     48   if (i < 1 || i > L.length+1) return ERROR;  // i值不合法
     49   if (L.length >= L.listsize) {   // 当前存储空间已满,增加容量
     50     ElemType *newbase = (ElemType *)realloc(L.elem,
     51                   (L.listsize+LISTINCREMENT)*sizeof (ElemType));
     52     if (!newbase) return ERROR;   // 存储分配失败
     53     L.elem = newbase;             // 新基址
     54     L.listsize += LISTINCREMENT;  // 增加存储容量
     55   }
     56   ElemType *q = &(L.elem[i-1]);   // q为插入位置
     57   for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;
     58                                   // 插入位置及之后的元素右移
     59   *q = e;       // 插入e
     60   ++L.length;   // 表长增1
     61   return OK;
     62 } // ListInsert_Sq
     63 
     64 Status ListDelete_Sq(SqList &L, int i, ElemType &e)
     65 {  // 算法2.5
     66   // 在顺序线性表L中删除第i个元素,并用e返回其值。
     67   // i的合法值为1≤i≤ListLength_Sq(L)。
     68   ElemType *p, *q;
     69   if (i<1 || i>L.length) return ERROR;  // i值不合法
     70   p = &(L.elem[i-1]);                   // p为被删除元素的位置
     71   e = *p;                               // 被删除元素的值赋给e
     72   q = L.elem+L.length-1;                // 表尾元素的位置
     73   for (++p; p<=q; ++p) *(p-1) = *p;     // 被删除元素之后的元素左移
     74   --L.length;                           // 表长减1
     75   return OK;
     76 } // ListDelete_Sq
     77 
     78 
     79 void MergeList(SqList La,SqList Lb,SqList &Lc)
     80 {
     81     int i,j,k,La_len,Lb_len,ai,bj;
     82      i=j=1;
     83       k=0;
     84     InitList_Sq(Lc);
     85     La_len=ListLength(La);
     86      Lb_len=ListLength(Lb);
     87       while((i<=La_len)&&(j<=Lb_len))
     88     {   GetElem(La,i,ai);
     89       GetElem(Lb,j,bj);
     90        if(ai<=bj)
     91     {    ListInsert_Sq(Lc,++k,ai);
     92         i++;   }
     93         else
     94             {    ListInsert_Sq(Lc,++k,bj);    j++;   }  }
     95          while(i<=La_len)
     96          {   GetElem(La,i++,ai);
     97          ListInsert_Sq(Lc,++k,ai);  }
     98         while(j<=Lb_len)
     99         {   GetElem(Lb,j++,bj);
    100         ListInsert_Sq(Lc,++k,bj);  }
    101     Load_Sq(Lc); }
    102 int main()
    103 {  int an,bn,i,e;
    104  SqList La,Lb,Lc;
    105  InitList_Sq(La);
    106  scanf("%d",&an);
    107     for(i=1;i<=an;i++)
    108     {
    109         scanf("%d",&e);
    110         ListInsert_Sq(La,i,e);  }
    111         printf("List A:");
    112         Load_Sq(La);
    113         InitList_Sq(Lb);
    114         scanf("%d",&bn);
    115         for(i=1;i<=an;i++)
    116         {
    117              scanf("%d",&e);
    118          ListInsert_Sq(Lb,i,e);  }
    119          printf("List B:");
    120          Load_Sq(Lb);
    121          printf("List C:");
    122           MergeList(La,Lb,Lc);
    123           return 0;
    124 }

     

    8578 顺序表逆置

    时间限制:1000MS  内存限制:1000K
    提交次数:3660 通过次数:2149

    题型: 编程题   语言: G++;GCC

     

    Description

    顺序表的基本操作代码如下:
    #include<stdio.h>
    #include<malloc.h>
    #define OK 1
    #define ERROR 0
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    #define ElemType int
    
    typedef int Status;
    typedef struct
    {
        int *elem;
        int length;
        int listsize;
    }SqList;
    
    Status InitList_Sq(SqList &L) 
    {  // 算法2.3
      // 构造一个空的线性表L。
      L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
      if (!L.elem) return OK;        // 存储分配失败
      L.length = 0;                  // 空表长度为0
      L.listsize = LIST_INIT_SIZE;   // 初始存储容量
      return OK;
    } // InitList_Sq
    
    Status ListInsert_Sq(SqList &L, int i, ElemType e) 
    {  // 算法2.4
      // 在顺序线性表L的第i个元素之前插入新的元素e,
      // i的合法值为1≤i≤ListLength_Sq(L)+1
      ElemType *p;
      if (i < 1 || i > L.length+1) return ERROR;  // i值不合法
      if (L.length >= L.listsize) {   // 当前存储空间已满,增加容量
        ElemType *newbase = (ElemType *)realloc(L.elem,
                      (L.listsize+LISTINCREMENT)*sizeof (ElemType));
        if (!newbase) return ERROR;   // 存储分配失败
        L.elem = newbase;             // 新基址
        L.listsize += LISTINCREMENT;  // 增加存储容量
      }
      ElemType *q = &(L.elem[i-1]);   // q为插入位置
      for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;
                                      // 插入位置及之后的元素右移
      *q = e;       // 插入e
      ++L.length;   // 表长增1
      return OK;
    } // ListInsert_Sq
    
    Status ListDelete_Sq(SqList &L, int i, ElemType &e) 
    {  // 算法2.5
      // 在顺序线性表L中删除第i个元素,并用e返回其值。
      // i的合法值为1≤i≤ListLength_Sq(L)。
      ElemType *p, *q;
      if (i<1 || i>L.length) return ERROR;  // i值不合法
      p = &(L.elem[i-1]);                   // p为被删除元素的位置
      e = *p;                               // 被删除元素的值赋给e
      q = L.elem+L.length-1;                // 表尾元素的位置
      for (++p; p<=q; ++p) *(p-1) = *p;     // 被删除元素之后的元素左移
      --L.length;                           // 表长减1
      return OK;
    } // ListDelete_Sq
    
    设有一顺序表A=(a0,a1,..., ai,...an-1),其逆顺序表定义为A'=( an-1,..., ai,...,a1, a0)。设计一个算法,将顺序表逆置,要求顺序表仍占用原顺序表的空间。




    输入格式

    第一行:输入顺序表的元素个数
    第二行:输入顺序表的各元素,用空格分开
    



    输出格式

    第一行:逆置前的顺序表元素列表
    第二行:逆置后的顺序表元素列表
    



     

    输入样例

    10
    1 2 3 4 5 6 7 8 9 10
    



     

    输出样例

    The List is:1 2 3 4 5 6 7 8 9 10 
    The turned List is:10 9 8 7 6 5 4 3 2 1
     1 #include<stdio.h>
     2 #include<malloc.h>
     3 #define OK 1
     4 #define ERROR 0
     5 #define LIST_INIT_SIZE 100
     6 #define LISTINCREMENT 10
     7 #define ElemType int
     8 
     9 typedef int Status;
    10 typedef struct
    11 {
    12     int *elem;
    13     int length;
    14     int listsize;
    15 }SqList;
    16 
    17 Status InitList_Sq(SqList &L)
    18 {  // 算法2.3
    19   // 构造一个空的线性表L。
    20   L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    21   if (!L.elem) return OK;        // 存储分配失败
    22   L.length = 0;                  // 空表长度为0
    23   L.listsize = LIST_INIT_SIZE;   // 初始存储容量
    24   return OK;
    25 } // InitList_Sq
    26 
    27 Status ListInsert_Sq(SqList &L, int i, ElemType e)
    28 {  // 算法2.4
    29   // 在顺序线性表L的第i个元素之前插入新的元素e,
    30   // i的合法值为1≤i≤ListLength_Sq(L)+1
    31   ElemType *p;
    32   if (i < 1 || i > L.length+1) return ERROR;  // i值不合法
    33   if (L.length >= L.listsize) {   // 当前存储空间已满,增加容量
    34     ElemType *newbase = (ElemType *)realloc(L.elem,
    35                   (L.listsize+LISTINCREMENT)*sizeof (ElemType));
    36     if (!newbase) return ERROR;   // 存储分配失败
    37     L.elem = newbase;             // 新基址
    38     L.listsize += LISTINCREMENT;  // 增加存储容量
    39   }
    40   ElemType *q = &(L.elem[i-1]);   // q为插入位置
    41   for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;
    42                                   // 插入位置及之后的元素右移
    43   *q = e;       // 插入e
    44   ++L.length;   // 表长增1
    45   return OK;
    46 } // ListInsert_Sq
    47 
    48 Status ListDelete_Sq(SqList &L, int i, ElemType &e)
    49 {  // 算法2.5
    50   // 在顺序线性表L中删除第i个元素,并用e返回其值。
    51   // i的合法值为1≤i≤ListLength_Sq(L)。
    52   ElemType *p, *q;
    53   if (i<1 || i>L.length) return ERROR;  // i值不合法
    54   p = &(L.elem[i-1]);                   // p为被删除元素的位置
    55   e = *p;                               // 被删除元素的值赋给e
    56   q = L.elem+L.length-1;                // 表尾元素的位置
    57   for (++p; p<=q; ++p) *(p-1) = *p;     // 被删除元素之后的元素左移
    58   --L.length;                           // 表长减1
    59   return OK;
    60 } // ListDelete_Sq
    61 int load(SqList &L)
    62 {
    63     int i;
    64     for(i=0;i<L.length;i++)
    65     {
    66         printf("%d ",L.elem[i]);
    67     }
    68     printf("\n");
    69     return OK;
    70 }
    71 int load1(SqList &L)
    72 {
    73     int i;
    74     for(i=L.length-1;i>=0;i--)
    75     {
    76         printf("%d ",L.elem[i]);
    77     }
    78     return OK;
    79 }
    80 int main()
    81 {
    82     SqList t;
    83     InitList_Sq(t);
    84    int i,a,b;
    85    scanf("%d",&a);
    86    for(i=1;i<=a;i++)
    87    {
    88        scanf("%d",&b);
    89        ListInsert_Sq(t,i,b);
    90 
    91    }
    92    printf("The List is:");
    93 
    94    load(t);
    95     printf("The turned List is:");
    96    load1(t);
    97 }

    8579 链式线性表的基本操作

    时间限制:1000MS  内存限制:1000K
    提交次数:5567 通过次数:2176

    题型: 编程题   语言: G++;GCC

     

    Description

     编写算法,创建一个含有n个元素的带头结点的单链表L并实现插入、删除、遍历操作。本题目提供部分代码,请补全内容。

    #include<stdio.h>
    #include<malloc.h>
    #define ERROR 0
    #define OK 1 
    #define ElemType int
    
    typedef struct LNode
    {
     int data;
     struct LNode *next;
    }LNode,*LinkList;
    
    int CreateLink_L(LinkList &L,int n){
    // 创建含有n个元素的单链表
      LinkList p,q;
      int i;
      ElemType e;
      L = (LinkList)malloc(sizeof(LNode));
      L->next = NULL;              // 先建立一个带头结点的单链表
      q = (LinkList)malloc(sizeof(LNode));
      q = L;
      for (i=0; i<n; i++) {
    	 scanf("%d", &e);
        p = (LinkList)malloc(sizeof(LNode));  // 生成新结点
        // 请补全代码
    
      }
      return OK;
    }
    
    int LoadLink_L(LinkList &L){
    // 单链表遍历
     LinkList p = L->next;
     if(___________________________)printf("The List is empty!"); // 请填空
     else
     {
    	 printf("The LinkList is:");
    	 while(___________________________)    // 请填空
    	 {
    		printf("%d ",p->data); 
    		___________________________    // 请填空
    	 }
     }
     printf("\n");
     return OK;
    }
    
    int LinkInsert_L(LinkList &L,int i,ElemType e){
    // 算法2.9
    // 在带头结点的单链线性表L中第i个位置之前插入元素e
    // 请补全代码
    
    }
    
    int LinkDelete_L(LinkList &L,int i, ElemType &e){
    // 算法2.10
    // 在带头结点的单链线性表L中,删除第i个元素,并用e返回其值
    // 请补全代码
    
    }
    
    int main()
    {
     LinkList T;
     int a,n,i;
     ElemType x, e;
     printf("Please input the init size of the linklist:\n");
     scanf("%d",&n);
     printf("Please input the %d element of the linklist:\n", n);
     if(___________________________)     // 判断链表是否创建成功,请填空
     {
    	 printf("A Link List Has Created.\n");
    	 LoadLink_L(T);
     }
     while(1)
    	{
    		printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
    		scanf("%d",&a);
    		switch(a)
    		{
    			case 1: scanf("%d%d",&i,&x);
    				  if(___________________________) printf("Insert Error!\n"); // 判断i值是否合法,请填空
    				  else printf("The Element %d is Successfully Inserted!\n", x); 
    				  break;
    			case 2: scanf("%d",&i);
    				  if(___________________________) printf("Delete Error!\n"); // 判断i值是否合法,请填空
    				  else printf("The Element %d is Successfully Deleted!\n", e);
    				  break;
    			case 3: LoadLink_L(T);
    				  break;
    			case 0: return 1;
    		}
    	}
    }
    




    输入格式

    测试样例格式说明:
    根据菜单操作:
    1、输入1,表示要实现插入操作,紧跟着要输入插入的位置和元素,用空格分开
    2、输入2,表示要实现删除操作,紧跟着要输入删除的位置
    3、输入3,表示要输出顺序表的所有元素
    4、输入0,表示程序结束
    



     

    输入样例

    3
    3 6 9
    3
    1
    4 12
    2
    1
    3
    0



     

    输出样例

    Please input the init size of the linklist:
    Please input the 3 element of the linklist:
    A Link List Has Created.
    The LinkList is:3 6 9 
    1:Insert element
    2:Delete element
    3:Load all elements
    0:Exit
    Please choose:
    The LinkList is:3 6 9 
    1:Insert element
    2:Delete element
    3:Load all elements
    0:Exit
    Please choose:
    The Element 12 is Successfully Inserted!
    1:Insert element
    2:Delete element
    3:Load all elements
    0:Exit
    Please choose:
    The Element 3 is Successfully Deleted!
    1:Insert element
    2:Delete element
    3:Load all elements
    0:Exit
    Please choose:
    The LinkList is:6 9 12 
    1:Insert element
    2:Delete element
    3:Load all elements
    0:Exit
    Please choose:

     

      1 #include<stdio.h>
      2 #include<malloc.h>
      3 #define ERROR 0
      4 #define OK 1
      5 #define ElemType int
      6 
      7 typedef struct LNode
      8 {
      9  int data;
     10  struct LNode *next;
     11 }LNode,*LinkList;
     12 
     13 int CreateLink_L(LinkList &L,int n){
     14 // 创建含有n个元素的单链表
     15   LinkList p,q;
     16   int i;
     17   ElemType e;
     18   L = (LinkList)malloc(sizeof(LNode));
     19   L->next = NULL;              // 先建立一个带头结点的单链表
     20   q = (LinkList)malloc(sizeof(LNode));
     21   q = L;
     22   for (i=0; i<n; i++) {
     23      scanf("%d", &e);
     24     p = (LinkList)malloc(sizeof(LNode));  // 生成新结点
     25     p->data=e;
     26     p->next=q->next;
     27     q->next=p;
     28     q=q->next;
     29 
     30       }
     31   return OK;
     32 }
     33 
     34 int LoadLink_L(LinkList &L){
     35 // 单链表遍历
     36  LinkList p = L->next;
     37  if(!p)printf("The List is empty!"); // 请填空
     38  else
     39  {
     40      printf("The LinkList is:");
     41      while(p)    // 请填空
     42      {
     43         printf("%d ",p->data);
     44         p=p->next;  // 请填空
     45      }
     46  }
     47  printf("\n");
     48  return OK;
     49 }
     50 
     51 int LinkInsert_L(LinkList &L,int i,ElemType e)
     52 {
     53 // 算法2.9
     54 // 在带头结点的单链线性表L中第i个位置之前插入元素e
     55 // 请补全代码
     56 LinkList p=L,s;int j=0;
     57 while(p&&j<i-1)
     58 {
     59     p=p->next;
     60     j++;
     61 }
     62 if(!p||j>i-1)
     63 return ERROR;
     64 s=(LinkList)malloc(sizeof(LNode));
     65 s->data=e;s->next=p->next;
     66 p->next=s;
     67 return OK;
     68 
     69 
     70 
     71 }
     72 
     73 int LinkDelete_L(LinkList &L,int i, ElemType &e){
     74 // 算法2.10
     75 // 在带头结点的单链线性表L中,删除第i个元素,并用e返回其值
     76 // 请补全代码
     77     LinkList p=L,q;
     78     int j=0;
     79     while(p->next&&j<i-1)
     80     {
     81         p=p->next;
     82         ++j;
     83     }
     84     if(!(p->next)||j>i-1)
     85     return ERROR;
     86     q=p->next;
     87     p->next=q->next;
     88     e=q->data;free(q);
     89     return OK;
     90 
     91 }
     92 
     93 int main()
     94 {
     95  LinkList T;
     96  int a,n,i;
     97  ElemType x, e;
     98  printf("Please input the init size of the linklist:\n");
     99  scanf("%d",&n);
    100  printf("Please input the %d element of the linklist:\n", n);
    101  if(CreateLink_L(T,n))     // 判断链表是否创建成功,请填空
    102  {
    103      printf("A Link List Has Created.\n");
    104      LoadLink_L(T);
    105  }
    106  while(1)
    107     {
    108         printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
    109         scanf("%d",&a);
    110         switch(a)
    111         {
    112             case 1: scanf("%d%d",&i,&x);
    113                   if(!LinkInsert_L(T,i,x)) printf("Insert Error!\n"); // 判断i值是否合法,请填空
    114                   else printf("The Element %d is Successfully Inserted!\n", x);
    115                   break;
    116             case 2: scanf("%d",&i);
    117                   if(!LinkDelete_L(T,i,e)) printf("Delete Error!\n"); // 判断i值是否合法,请填空
    118                   else printf("The Element %d is Successfully Deleted!\n", e);
    119                   break;
    120             case 3: LoadLink_L(T);
    121                   break;
    122             case 0: return 1;
    123         }
    124     }
    125 }

    8580 合并链表

    时间限制:1000MS  内存限制:1000K
    提交次数:3724 通过次数:2077

    题型: 编程题   语言: G++;GCC

     

    Description

    线性链表的基本操作如下:
    #include<stdio.h>
    #include<malloc.h>
    #define ERROR 0
    #define OK 1 
    #define ElemType int
    
    typedef int Status;
    typedef struct LNode
    {
     int data;
     struct LNode *next;
    }LNode,*LinkList;
    
    
    Status ListInsert_L(LinkList &L, int i, ElemType e) {  // 算法2.9
      // 在带头结点的单链线性表L的第i个元素之前插入元素e
      LinkList p,s;
      p = L;   
      int j = 0;
      while (p && j < i-1) {  // 寻找第i-1个结点
        p = p->next;
        ++j;
      } 
      if (!p || j > i-1) return ERROR;      // i小于1或者大于表长
      s = (LinkList)malloc(sizeof(LNode));  // 生成新结点
      s->data = e;  s->next = p->next;      // 插入L中
      p->next = s;
      return OK;
    } // LinstInsert_L
    
    Status ListDelete_L(LinkList &L, int i, ElemType &e) {  // 算法2.10
      // 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
      LinkList p,q;
      p = L;
      int j = 0;
      while (p->next && j < i-1) {  // 寻找第i个结点,并令p指向其前趋
        p = p->next;
        ++j;
      }
      if (!(p->next) || j > i-1) return ERROR;  // 删除位置不合理
      q = p->next;
      p->next = q->next;           // 删除并释放结点
      e = q->data;
      free(q);
      return OK;
    } // ListDelete_L
    
    设计一个算法将两个非递减有序链表A和B合并成一个新的非递减有序链表C。




    输入格式

    第一行:单链表A的元素个数
    第二行:单链表A的各元素(非递减),用空格分开
    第三行:单链表B的元素个数
    第四行:单链表B的各元素(非递减),用空格分开
    



    输出格式

    第一行:单链表A的元素列表
    第二行:单链表B的元素列表
    第三行:合并后单链表C的元素列表
    



     

    输入样例

    6
    12 24 45 62 84 96
    4
    15 31 75 86
    



     

    输出样例

    List A:12 24 45 62 84 96 
    List B:15 31 75 86 
    List C:12 15 24 31 45 62 75 84 86 96
      1 #include<stdio.h>
      2 #include<malloc.h>
      3 #define ERROR 0
      4 #define OK 1
      5 #define ElemType int
      6 
      7 typedef int Status;
      8 typedef struct LNode
      9 {
     10  int data;
     11  struct LNode *next;
     12 }LNode,*LinkList;
     13 
     14 
     15 Status ListInsert_L(LinkList &L, int i, ElemType e) {  // 算法2.9
     16   // 在带头结点的单链线性表L的第i个元素之前插入元素e
     17   LinkList p,s;
     18   p = L;
     19   int j = 0;
     20   while (p && j < i-1) {  // 寻找第i-1个结点
     21     p = p->next;
     22     ++j;
     23   }
     24   if (!p || j > i-1) return ERROR;      // i小于1或者大于表长
     25   s = (LinkList)malloc(sizeof(LNode));  // 生成新结点
     26   s->data = e;  s->next = p->next;      // 插入L中
     27   p->next = s;
     28   return OK;
     29 } // LinstInsert_L
     30 
     31 Status ListDelete_L(LinkList &L, int i, ElemType &e) {  // 算法2.10
     32   // 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
     33   LinkList p,q;
     34   p = L;
     35   int j = 0;
     36   while (p->next && j < i-1) {  // 寻找第i个结点,并令p指向其前趋
     37     p = p->next;
     38     ++j;
     39   }
     40   if (!(p->next) || j > i-1) return ERROR;  // 删除位置不合理
     41   q = p->next;
     42   p->next = q->next;           // 删除并释放结点
     43   e = q->data;
     44   free(q);
     45   return OK;
     46 } // ListDelete_L
     47 int LoadLink_L(LinkList &L){
     48 // 单链表遍历
     49  LinkList p = L->next;
     50   // 请填空
     51 
     52 
     53      while(p!=NULL)    // 请填空
     54      {
     55         printf("%d ",p->data);
     56         p=p->next;  // 请填空
     57      }
     58 
     59  printf("\n");
     60  return OK;
     61 }
     62 int CreateLink_L(LinkList &L,int n){
     63 // 创建含有n个元素的单链表
     64   LinkList p,q;
     65   int i;
     66   ElemType e;
     67   L = (LinkList)malloc(sizeof(LNode));
     68   L->next = NULL;              // 先建立一个带头结点的单链表
     69   q = (LinkList)malloc(sizeof(LNode));
     70   q = L;
     71   for (i=0; i<n; i++) {
     72      scanf("%d", &e);
     73     p = (LinkList)malloc(sizeof(LNode));  // 生成新结点
     74     p->data=e;
     75     p->next=q->next;
     76     q->next=p;
     77     q=q->next;
     78 
     79       }
     80   return OK;
     81 }
     82 
     83 void mer(LinkList &La,LinkList &Lb,LinkList &Lc)
     84 {
     85     LinkList pa=La->next,pb=Lb->next,pc;
     86     pc=La;
     87     Lc=pc;
     88     while(pa&&pb)
     89     {
     90         if(pa->data<=pb->data)
     91         {
     92             pc->next=pa;pc=pa;pa=pa->next;
     93 
     94         }
     95         else
     96         {
     97             pc->next=pb;
     98             pc=pb;
     99             pb=pb->next;
    100         }
    101     }
    102     pc->next=pa?pa:pb;
    103     free(Lb);
    104 
    105 }
    106 int main()
    107 {
    108     int a,b,c,d,n;
    109     LinkList pa,pb,pc;
    110     scanf("%d",&a);
    111     CreateLink_L(pa,a);
    112 
    113      printf("List A:");
    114     LoadLink_L(pa);
    115     scanf("%d",&d);
    116     CreateLink_L(pb,d);
    117 
    118     printf("List B:");
    119     LoadLink_L(pb);
    120     printf("List C:");
    121     mer(pa,pb,pc);
    122     LoadLink_L(pc);
    123 
    124 }

     

    8581 线性链表逆置

    时间限制:1000MS  内存限制:1000K
    提交次数:2811 通过次数:2032

    题型: 编程题   语言: G++;GCC

     

    Description

    线性链表的基本操作如下:
    #include<stdio.h>
    #include<malloc.h>
    #define ERROR 0
    #define OK 1 
    #define ElemType int
    
    typedef int Status;
    typedef struct LNode
    {
     int data;
     struct LNode *next;
    }LNode,*LinkList;
    
    
    Status ListInsert_L(LinkList &L, int i, ElemType e) {  // 算法2.9
      // 在带头结点的单链线性表L的第i个元素之前插入元素e
      LinkList p,s;
      p = L;   
      int j = 0;
      while (p && j < i-1) {  // 寻找第i-1个结点
        p = p->next;
        ++j;
      } 
      if (!p || j > i-1) return ERROR;      // i小于1或者大于表长
      s = (LinkList)malloc(sizeof(LNode));  // 生成新结点
      s->data = e;  s->next = p->next;      // 插入L中
      p->next = s;
      return OK;
    } // LinstInsert_L
    
    Status ListDelete_L(LinkList &L, int i, ElemType &e) {  // 算法2.10
      // 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
      LinkList p,q;
      p = L;
      int j = 0;
      while (p->next && j < i-1) {  // 寻找第i个结点,并令p指向其前趋
        p = p->next;
        ++j;
      }
      if (!(p->next) || j > i-1) return ERROR;  // 删除位置不合理
      q = p->next;
      p->next = q->next;           // 删除并释放结点
      e = q->data;
      free(q);
      return OK;
    } // ListDelete_L
    
    设有一线性表A=(a0,a1,..., ai,...an-1),其逆线性表定义为A'=( an-1,..., ai,...,a1, a0),设计一个算法,将线性表逆置,要求线性表仍占用原线性表的空间。



    输入格式

    第一行:输入n,表示单链表的元素个数
    第二行:输入单链表的各元素,用空格分开
    


    输出格式

    第一行:输出单链表逆置前的元素列表
    第二行:输出单链表逆置后的元素列表
    


     

    输入样例

    8
    32 97 54 65 35 84 61 75
    


     

    输出样例

    The List is:32 97 54 65 35 84 61 75 
    The turned List is:75 61 84 35 65 54 97 32
      1 #include<stdio.h>
      2 #include<malloc.h>
      3 #define ERROR 0
      4 #define OK 1
      5 #define ElemType int
      6 
      7 typedef int Status;
      8 typedef struct LNode
      9 {
     10  int data;
     11  struct LNode *next;
     12 }LNode,*LinkList;
     13 
     14 
     15 Status ListInsert_L(LinkList &L, int i, ElemType e) {  // 算法2.9
     16   // 在带头结点的单链线性表L的第i个元素之前插入元素e
     17   LinkList p,s;
     18   p = L;
     19   int j = 0;
     20   while (p && j < i-1) {  // 寻找第i-1个结点
     21     p = p->next;
     22     ++j;
     23   }
     24   if (!p || j > i-1) return ERROR;      // i小于1或者大于表长
     25   s = (LinkList)malloc(sizeof(LNode));  // 生成新结点
     26   s->data = e;  s->next = p->next;      // 插入L中
     27   p->next = s;
     28   return OK;
     29 } // LinstInsert_L
     30 
     31 Status ListDelete_L(LinkList &L, int i, ElemType &e) {  // 算法2.10
     32   // 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
     33   LinkList p,q;
     34   p = L;
     35   int j = 0;
     36   while (p->next && j < i-1) {  // 寻找第i个结点,并令p指向其前趋
     37     p = p->next;
     38     ++j;
     39   }
     40   if (!(p->next) || j > i-1) return ERROR;  // 删除位置不合理
     41   q = p->next;
     42   p->next = q->next;           // 删除并释放结点
     43   e = q->data;
     44   free(q);
     45   return OK;
     46 } // ListDelete_L
     47 int CreateLink_L(LinkList &L,int n){
     48 // 创建含有n个元素的单链表
     49   LinkList p,q;
     50   int i;
     51   ElemType e;
     52   L = (LinkList)malloc(sizeof(LNode));
     53   L->next = NULL;              // 先建立一个带头结点的单链表
     54   q = (LinkList)malloc(sizeof(LNode));
     55   q = L;
     56   for (i=0; i<n; i++) {
     57      scanf("%d", &e);
     58     p = (LinkList)malloc(sizeof(LNode));  // 生成新结点
     59     p->data=e;
     60     p->next=q->next;
     61     q->next=p;
     62     q=q->next;
     63 
     64       }
     65   return OK;
     66 }
     67 LinkList ListReverse(LinkList &L)
     68 {
     69     LinkList current,p;
     70 
     71     if (L == NULL)
     72     {
     73         return NULL;
     74     }
     75     current = L->next;
     76     while (current->next != NULL)
     77     {
     78         p = current->next;
     79         current->next = p->next;
     80         p->next = L->next;
     81         L->next = p;
     82 
     83     }
     84     return L;
     85 }
     86 void load(LinkList &L)
     87 {
     88     LinkList p=L->next;
     89     while(p)
     90     {
     91         printf("%d ",p->data);
     92         p=p->next;
     93     }
     94 }
     95 int main()
     96 
     97 {
     98     LinkList L;
     99     int n;
    100     scanf("%d",&n);
    101     CreateLink_L(L,n);
    102     printf("The List is:");
    103     load(L);
    104     printf("\n");
    105     printf("The turned List is:");
    106     ListReverse(L);
    107     load(L);
    108 
    109 
    110 }

     

    转载于:https://www.cnblogs.com/guguchen/p/9281411.html

    展开全文
  • 顺序方式存储的线性表, 动态链接方式存储的线性表, 动态链接结构存储的二叉树, 选择排序的算法,
  • 3、建立一个动态链接结构存储的二叉树,向这棵二叉树进行以下操作: (1)按任中序遍历次序输出二叉树中的所有结点 (2)求二叉树的叶子数 4、编写一个对整型数组A[n+1]中的A[1]至A[n]元素进行选择排序的算法,使得...
  • 福建师范大学20-21数据结构上机期末考试.docx
  • } 该算法在满二叉树的情况下效果最差,但是在题目的数据范围下经过自造数据的多次检验,可以在1s内完美跑完。 code int find (int l, int r, int x) { for (int i = l;i ;i ++) if (mid[i] == x) return i; ...

    Problem318二叉树遍历

    题面

    给定一棵二叉树的先序遍历和中序遍历序列,求其后序遍历序列。

    解答

    用递归的方式进行求解。
    显而易见,任何一个子树的先序遍历序列的首字母一定是该子树的树根。而在中序遍历中,该树根左侧是左子树,右侧是右子树,那么我们只需要不断的递归分解左右子树,即可求出原树。
    需要注意的是,由于我们需要求后序遍历序列,因此对于每一棵子树,都需要在它左右子树分别递归分解完成之后再输出树根结点。

    code

    void getnxt (string pre, string mid, int len) {
    	if (len == 0) return ;//如果当前子树为空
    	if (len == 1) {//如果当前是叶子结点
    		cout << pre;//直接输出
    		return ;
    	}
    	int k = mid.find (pre[0]);//找到中序遍历中根节点的位置
    	getnxt (pre.substr (1, k), mid.substr (0, k), k);//遍历左子树
    	getnxt (pre.substr (k + 1, len - 1 - k), mid.substr (k + 1, len - 1 - k), len - k - 1);//遍历右子树
    	cout << pre[0];
    }
    

    这里的string的substr函数共有两个参数,例如pre.substr(1,k),意思是在取string类型pre的子串[1…k](从下标1处开始,长度为k)

    Problem319将满二叉树转化为求和树

    题面

    在这里插入图片描述

    解答

    大致思路和Problem318一样,细节处理上需要花一些功夫。
    这里,我们getnxt函数设置为int类型,以返回当前结点的左右子树之和。我们需要知道的是,对于每一个结点,它的求和树上对应的结点数值是它左右子树之和(不包括它本身),因此我们这里需要先把它本身的数值记录下来,再赋予它新值。特别地,对于每一个叶子结点,在将它的值返回上一层函数之前,需要将它赋零。
    经过我们的操作,原中序遍历序列就成了答案要求的求和树中序遍历序列。

    code

    int find (int L, int R, int x) {
    	for (int i = L;i <= R;i ++)
    		if (b[i] == x) return i;
    }
    int getnxt (int l, int r, int L, int R) {
    	
    	int len = r - l + 1;//利用l和r算出当前子树的大小
    	if (len == 0) return 0;//如果子树为空
    	if (len == 1) {//如果是叶子结点
    		int tmp = a[l];//先记录下当前叶子结点的数
    		a[l] = b[L] = 0;//将前序遍历和中序遍历的叶子结点赋零
    		return tmp;//返回叶子结点的值
    	}
    	int k = find (L, R, a[l]);//在中序遍历序列中找到根节点的位置
    	int t1 = getnxt (l + 1, l + k - L, L, k - 1);//遍历左子树
    	int t2 = getnxt (l + k - L + 1, r, k + 1, r);//遍历右子树
    	int tmp = a[l];//先记录下当前结点的值
    	a[l] = b[k] = t1 + t2;//将先序遍历序列和中序遍历序列中该结点赋值为两个子树值之和
    	return tmp + a[l];//整个子树的值应为当前左右子树值、根节点值之和
    }
    

    Problem320二叉树的不同形态

    题面

    在这里插入图片描述

    解答

    这道题相对前两道题较复杂。一共分为两个步骤

    1. 根据层次遍历序列和中序遍历序列求出先序遍历序列
    2. 根据先序遍历序列和中序遍历序列求出后序遍历序列

    第二步是前面介绍过的算法。这里着重介绍第一步的算法。
    直观暴力思想
    还是同之前一样,利用递归的手段进行左右子树拆解。但是不同的是,层次遍历序列不像先序遍历序列那样,可以非常容易得知每一棵子树的根节点。但是我们可以发现两个性质:

    1. 在层次遍历序列中,父亲结点永远出现在儿子节点的前面。
    2. 在层次遍历序列中,在父亲结点后出现的第一个存在于左子树的结点,就是该父亲节点的左子树根节点;右子树根节点亦然。

    所以我们可以改进之前的算法:
    若左子树不为空,当遍历左子树前,我们可以通过查找层次遍历序列中,父亲节点后,第一个出现的存在于左子树的结点,作为左子树的根节点,以它为依据划分中序遍历序列,继续拆解二叉树。

    if (k - l > 0) {
    		int t = root + 1;
    		while (find (l, k - 1, dep[t]) == -1) t ++;
    		getpre (l, k - 1, t);
    	}
    

    但是我们发现了一个问题,在寻找一个父亲节点的两个孩子结点时候,需要对层次遍历序列中,父亲孩子之间的所有结点都进行while (find (l, k - 1, dep[t]) == -1) t ++;的操作,粗略估计下时间复杂度大约是 O ( n ) = n 3 O(n)=n^3 O(n)=n3级别,算法还需要改进。我们很容易意识到一个特性:

    • 当一个结点在拆解过程中被作为父亲结点使用后,一定不会使用第二次。

    因此我们可以设置一个新函数(其实就是一个bool类型的标记数组)used[x]。当x没有被当做父亲节点使用时,我们让他为0,代表它需要被查找;一旦被使用后让他为1,代表他不需要再被查找。于是代码可以改为:

    if (k - l > 0) {
    		int t = root + 1;
    		while (used[t] || find (l, k - 1, dep[t]) == -1) t ++;
    		used[t] = 1;
    		getpre (l, k - 1, t);
    	}
    

    该算法在满二叉树的情况下效果最差,但是在题目的数据范围下经过自造数据的多次检验,可以在1s内完美跑完。

    code

    int find (int l, int r, int x) {
    	for (int i = l;i <= r;i ++)
    		if (mid[i] == x) return i;
    	return -1;
    }
    int pre[maxn], top = 0;
    int used[maxn];
    void getpre (int l, int r, int root) {
    	int len = r - l + 1;//当前子树大小
    	if (len == 0) return;//如果子树为空
    	if (len == 1) {//叶子节点
    		printf ("%d ", mid[l]);
    		pre[++ top] = mid[l];//在先序遍历序列中记录叶子结点
    		return ;
    	}
    	int k = find (l, r, dep[root]);
    	pre[++ top] = mid[k];//先序遍历序列,需要先记录根结点
    	if (k - l > 0) {
    		int t = root + 1;
    		while (used[t] || find (l, k - 1, dep[t]) == -1) t ++;
    		used[t] = 1;
    		getpre (l, k - 1, t);
    	}
    	if (r - k > 0) {
    		int t = root + 1;
    		while (used[t] || find (k + 1, r, dep[t]) == -1) t ++;
    		used[t] = 1;
    		getpre (k + 1, r, t);
    	}
    }
    
    展开全文
  • 中大计算机本科课程实践考核(二)数据结构上机考试答案,2008年修订版。
  • 考试必过!线性表实现一个顺序存储的线性表实现一个链接存储的线性表函数第1关 求和第2关 回文数计算第3关 编写函数求表达式的值第4关 阶乘数列第5关 亲密数第6关 公约公倍数一维数组和二维数组第1关 排序问题第2关 ...

    线性表

    实现一个顺序存储的线性表

    /*************************************************************
        date: April 2017
        copyright: Zhu En
        DO NOT distribute this code without my permission.
    **************************************************************/
    // 顺序表操作实现文件
    //
    #include <stdio.h>
    #include <stdlib.h>
    #include "Seqlist.h"
    SeqList* SL_Create(int maxlen)
    // 创建一个顺序表
    // 与SqLst_Free()配对
    {
        SeqList* slist=(SeqList*)malloc(sizeof(SeqList));
        slist->data = (T*)malloc(sizeof(T)*maxlen);
        slist->max=maxlen;
        slist->len=0;
        return slist;
    }
    void SL_Free(SeqList* slist)
    // 释放/删除 顺序表
    // 与SqLst_Create()配对
    {
        free(slist->data);
        free(slist);
    }
    void SL_MakeEmpty(SeqList* slist)
    // 置为空表
    {
        slist->len=0;
    }
    int SL_Length(SeqList* slist)
    // 获取长度
    {
        return slist->len;
    }
    bool SL_IsEmpty(SeqList* slist)
    // 判断顺序表是否空
    {
        return 0==slist->len;
    }
    bool SL_IsFull(SeqList* slist)
    // 判断顺序表是否满
    {
        return slist->len==slist->max;
    }
    T SL_GetAt(SeqList* slist, int i)
    // 获取顺序表slist的第i号结点数据
    // 返回第i号结点的值
    {
        if(i<0||i>=slist->len) 
        {
            printf("SL_GetAt(): location error when reading elements of the slist!\n");        
            SL_Free(slist);
            exit(0);
        }
        else 
        {
         	return slist->data[i];
        }
    }
    void SL_SetAt(SeqList* slist, int i, T x)
    // 设置第i号结点的值(对第i号结点的数据进行写)
    {
        if(i<0||i>=slist->len) 
        {
            printf("SL_SetAt(): location error when setting elements of the slist!\n");        
            SL_Free(slist);
            exit(0);
        }
        else 
        {
         	slist->data[i]=x;
        }
    }
    bool SL_InsAt(SeqList* slist, int i, T x)
    // 在顺序表的位置i插入结点x, 插入d[i]之前
    // i的有效范围[0,plist->len]
    {
        if (i<0 || i>slist->len || slist->len==slist->max)  
        {
            printf("SL_InsAt(): location error, or slist full.\n");
            return false;
        }
        for (int j=slist->len; j>=i+1; j--) 
        {
            slist->data[j]=slist->data[j-1];
        }
        slist->data[i]=x;
        slist->len++;
        return true;
    }
    T SL_DelAt(SeqList* slist, int i)
    // 删除顺序表plist的第i号结点
    // i的有效范围应在[0,plist->len)内,否则会产生异常或错误。
    // 返回被删除的数据元素的值。
    {
        if (i<0 || i>=slist->len) 
        {
            printf("SL_DelAt(): location error!\n");
            SL_Free(slist);
            exit(0);
        }
        T res=slist->data[i];
        for (int j=i; j<slist->len-1; j++) 
        {
            slist->data[j] = slist->data[j+1];
        }
        slist->len--;
        return res;
    }
    int SL_FindValue(SeqList* slist, T x)
    // 在顺序表表中查找第一个值为x的结点,返回结点的编号
    // 返回值大于等于0时表示找到值为x的结点的编号,-1表示没有找到
    {
        int i=0;
        while(i<slist->len && slist->data[i]!=x) i++;
        if (i<slist->len) return i;
        else return -1;
    }
    int SL_DelValue(SeqList* slist, T x)
    // 删除第一个值为x的结点,
    // 存在值为x的结点则返回结点编号, 未找到返回-1
    {
     int i=SL_FindValue(slist, x);
        if (i>=0) 
        {
        	SL_DelAt(slist, i);
        }
        return i;
    }
    void SL_Print(SeqList* slist)
    // 打印整个顺序表
    {
        if (slist->len==0) 
        {
            printf("The slist is empty.\n");        
            return;
        }
        //printf("The slist contains: ");
        for (int i=0; i<slist->len; i++) 
        {
            printf("%d  ", slist->data[i]);
        }
        printf("\n");    
    }
    

    实现一个链接存储的线性表

    /*************************************************************
        date: April 2017
        copyright: Zhu En
        DO NOT distribute this code without my permission.
    **************************************************************/
    // 单链表实现文件
    
    #include <stdio.h>
    #include <stdlib.h>
    #include "LinkList.h"
    LinkList* LL_Create()
    // 创建一个链接存储的线性表,初始为空表,返回llist指针。
    {
        LinkList* llist=(LinkList*)malloc(sizeof(LinkList));
        llist->front=NULL;
        llist->rear=NULL;
        llist->pre=NULL;
        llist->curr=NULL;
        llist->position=0;
        llist->len=0;
        return llist;
    } 
    void LL_Free(LinkList* llist)
    // 释放链表的结点,然后释放llist所指向的结构。
    {
        LinkNode* node=llist->front;
        LinkNode* nextnode;
        while(node)
        {
            nextnode=node->next;
            free(node);
            node=nextnode;
        }
        free(llist);
    } 
    void LL_MakeEmpty(LinkList* llist)
    // 将当前线性表变为一个空表,因此需要释放所有结点。
    {
        LinkNode* node=llist->front;
        LinkNode* nextnode;
        while(node)
        {
            nextnode=node->next;
            free(node);
            node=nextnode;
        }
        llist->front=NULL;
        llist->rear=NULL;
        llist->pre=NULL;
        llist->curr=NULL;
        llist->position=0;
        llist->len=0;
    }   
    int LL_Length(LinkList* llist)
    // 返回线性表的当前长度。
    {
        return llist->len;
    }  
    bool LL_IsEmpty(LinkList* llist)
    // 若当前线性表是空表,则返回true,否则返回TRUE。
    {
        return llist->len==0;
    }
    bool LL_SetPosition(LinkList* llist, int i)
    // 设置线性表的当前位置为i号位置。
    // 设置成功,则返回true,否则返回false(线性表为空,或i不在有效的返回)
    // 假设线性表当前长度为len,那么i的有效范围为[0,len]
    {    
        int k;
        /* 若链表为空,则返回*/
        if (llist->len==0) return false;
        /*若位置越界*/
        if( i < 0 || i > llist->len)
        {    printf("LL_SetPosition(): position error");
            return false;
        }
        /* 寻找对应结点*/
        llist->curr = llist->front;
        llist->pre = NULL;
        llist->position = 0;
        for ( k = 0; k < i; k++)    
        {
            llist->position++;
            llist->pre = llist->curr;
            llist->curr = (llist->curr)->next;
        }
        /* 返回当前结点位置*/
        return true;
    }  
    int LL_GetPosition(LinkList* llist)
    // 获取线性表的当前位置结点的编号
    {
        return llist->position;
    }  
    bool LL_NextPosition(LinkList* llist)
    // 设置线性表的当前位置的下一个位置为当前位置。
    // 设置成功,则返回true,否则返回false(线性表为空,或当前位置为表尾)
    {
        if (llist->position >= 0 && llist->position < llist->len)
        /* 若当前结点存在,则将其后继结点设置为当前结点*/
        {
            llist->position++;
            llist->pre = llist->curr;
            llist->curr = llist->curr->next;
            return true;
        }
        else 
        {
            return false;
        }
    }    
    T LL_GetAt(LinkList* llist)
    // 返回线性表的当前位置的数据元素的值。
    {
        if(llist->curr==NULL)
        {
            printf("LL_GetAt(): Empty list, or End of the List.\n");
            LL_Free(llist);
            exit(1);
        }
        return llist->curr->data;
    }   
    void LL_SetAt(LinkList* llist, T x)
    // 将线性表的当前位置的数据元素的值修改为x。
    {
        if(llist->curr==NULL)
        {
            printf("LL_SetAt(): Empty list, or End of the List.\n");
            LL_Free(llist);
            exit(1);
        }
        llist->curr->data=x;
    }    
    bool LL_InsAt(LinkList* llist, T x)
    // 在线性表的当前位置之前插入数据元素x。当前位置指针指向新数据元素结点。
    // 若插入失败,返回false,否则返回true。
    {    
        LinkNode *newNode=(LinkNode*)malloc(sizeof(LinkNode));
        if (newNode==NULL) 
        {
        	return false;
        }
        newNode->data=x;
        if (llist->len==0)
        {
            /* 在空表中插入*/
            newNode->next=NULL;
            llist->front = llist->rear = newNode;
        }
        //当前位置为表头
        else if (llist->pre==NULL)
        {
            /* 在表头结点处插入*/
            newNode->next = llist->front;
            llist->front = newNode;
        }
        else 
        {  
            /* 在链表的中间位置或表尾后的位置插入*/
            newNode->next = llist->curr;
            llist->pre->next=newNode;
        }
        //插入在表尾后
        if (llist->pre==llist->rear)
            llist->rear=newNode;
        /* 增加链表的大小*/
        llist->len++;
        /* 新插入的结点为当前结点*/
        llist->curr = newNode;
        return true;
    }    
    bool LL_InsAfter(LinkList* llist, T x)
    // 在线性表的当前位置之后插入数据元素x。空表允许插入。当前位置指针将指向新结点。
    // 若插入失败,返回false,否则返回true。
    {
        LinkNode *newNode=(LinkNode*)malloc(sizeof(LinkNode));
        if (newNode==NULL) return false;
        newNode->data=x;
        if (llist->len==0)    
        {
            /* 在空表中插入*/
            newNode->next=NULL;
            llist->front = llist->rear = newNode;
        }
        else if (llist->curr == llist->rear || llist->curr == NULL)    {
            /* 在尾结点后插入*/
            newNode->next = NULL;
            llist->rear->next=newNode;
            llist->pre=llist->rear;
            llist->rear=newNode;
            llist->position=llist->len;
        }
        else
        {
            /* 在中间位置插入*/
            newNode->next = llist->curr->next;
            llist->curr->next=newNode;
            llist->pre=llist->curr;
            llist->position ++;
        }
        /* 增加链表的大小*/
        llist->len ++;
        /* 新插入的结点为当前结点*/
        llist->curr = newNode;
        return true;
    }
    bool LL_DelAt(LinkList* llist)
    // 删除线性表的当前位置的数据元素结点。
    // 若删除失败(为空表,或当前位置为尾结点之后),则返回false,否则返回true。
    {    
        LinkNode *oldNode;
        /* 若表为空或已到表尾之后,则给出错误提示并返回*/
        if (llist->curr==NULL)
        {    
            printf("LL_DelAt(): delete a node that does not exist.\n");
            return false;
        }
        oldNode=llist->curr;
        /* 删除的是表头结点*/
        if (llist->pre==NULL)
        {    
            llist->front = oldNode->next;
        }
        /* 删除的是表中或表尾结点*/
        else if(llist->curr!=NULL)
        {
            llist->pre->next = oldNode->next;
        }
        if (oldNode == llist->rear)    
        {
            /* 删除的是表尾结点,则修改表尾指针和当前结点位置值*/
            llist->rear = llist->pre;
        }
        /* 后继结点作为新的当前结点*/
        llist->curr = oldNode->next;
        /* 释放原当前结点*/
        free(oldNode);
        /* 链表大小减*/
        llist->len --;
        return true;
    }    
    bool LL_DelAfter(LinkList* llist)
    // 删除线性表的当前位置的后面那个数据元素。
    // 若删除失败(为空表,或当前位置时表尾),则返回false,否则返回true。
    {
        LinkNode *oldNode;
        /* 若表为空或已到表尾,则给出错误提示并返回*/
        if (llist->curr==NULL || llist->curr== llist->rear)
        {
            printf("LL_DelAfter():  delete a node that does not exist.\n");
            return false;
        }
        /* 保存被删除结点的指针并从链表中删除该结点*/
        oldNode = llist->curr->next;
        llist->curr->next=oldNode->next;
        if (oldNode == llist->rear)
        {
         /* 删除的是表尾结点*/
            llist->rear = llist->curr;
        }
        /* 释放被删除结点*/
        free(oldNode);
        /* 链表大小减*/
        llist->len --;
        return true;
    }    
    int LL_FindValue(LinkList* llist, T x)
    // 找到线性表中第一个值为x的数据元素的编号。
    // 返回值-1表示没有找到,返回值>=0表示编号。
    {
        LinkNode* p=llist->front;
        int idx=0;
        while(p!=NULL && p->data!=x) 
        {
            idx++;
            p = p->next;
        }
        if (idx>=llist->len) 
        {
      	return -1; 
        }
        else 
        {
      	return idx; 
        }
    }
    int LL_DelValue(LinkList* llist, T x)
    // 删除第一个值为x的数据元素,返回该数据元素的编号。如果不存在值为x的数据元素,则返回-1.
    {
        int idx=LL_FindValue(llist, x);
        if (idx<0) return -1;
        LL_SetPosition(llist, idx);
        LL_DelAt(llist);
        return idx;
    }   
    void LL_Print(LinkList* llist)
    // 打印整个线性表。
    {
        LinkNode* node=llist->front;
        while (node) 
        {
            printf("%d ", node->data);
            node=node->next;
        }
        printf("\n");
    }
    

    函数

    第1关 求和

    #include<stdio.h>
    //编写函数
    /*********Begin*********/
    int sum1(int n){
        int sum = 0;
        for(int i = 1; i <= n; i++){
            sum += i;
        }
        return sum;
    }
    /*********End**********/ 
    int main(void)
    {  
        /*********Begin*********/
        int n = 0;
        scanf("%d", &n);
        int sum = sum1(n);
        printf("%d", sum);
    
        /*********End**********/ 
        return 0;
    }
    
    

    第2关 回文数计算

    #include<stdio.h>
    void solve(){
        /*********Begin*********/
        for(int i=200; i <= 999; i++){
        	int a = i/100; // 百位数字
    		int b = i%100%10; // 个位数字 
    		if(a == b){
    			printf("%d\n",i);
    		}
    	}
    	for(int i=1000; i <= 3000; i++){
        	int a = i/1000; // 千位数字
    		int b = i/100%10; // 百位数字 
    		int c = i/10%100%10; // 十位数字 
    		int d = i%1000%100%10; // 个位数字 
    		if(a == d && b == c){
    			printf("%d\n",i);
    		}
    	}
    	
    
        /*********End**********/ 
    }
    int main(void)
    {  
        solve();
       return 0;
    }
    

    第3关 编写函数求表达式的值

    #include<stdio.h>
    //编写题目要求的函数
    /*********Begin*********/
    double sum1(int n){
    	double sum = 1;
    	if(n==1) 
    	    return 1;
    	else {
    	for(int i = n+1; i >= 2; i--){ // 为啥是n+1呢??因为下面这个公式是用n推导的 
    		sum = 1 + (double)(((i-1)*sum)/(2*i-1));
    	}	
    	return sum;
    	}
    }
    
    /*********End**********/ 
    int main(void)
    {  
        /*********Begin*********/
    // 1+1/3(1+2/5(1+......(1+(n-1)/(2n-1))))
        int n=0;
    	double sum=0;
        scanf("%d", &n);
        sum = sum1(n);
        printf("%.10lf", sum);
    
        /*********End**********/ 
        return 0;
    }
    

    第4关 阶乘数列

    
    #include<stdio.h>
    //编写函数
    /*********Begin*********/
    void sum1(int n){
    	long long int sum = 1;
    	if(n==1) 
    	    printf("1");
    	else {
    	for(int i = n; i >= 2; i--){ 
    		sum = 1 + i*sum;
    	}	
    	printf("%lld",sum);
    	}
    }
    /*********End**********/ 
    int main(void)
    {  
        /*********Begin*********/
        int n=0;
        scanf("%d", &n);
        sum1(n);
    
        /*********End**********/ 
        return 0;
    }
    
    
    

    第5关 亲密数

    #include<stdio.h>
    // 求因子的函数 
    int sum(int n){ 
    	int sum = 0;
    	for(int i = 1; i <= n/2; i++){
    		if(n%i == 0){
    			sum += i;
    		}
    	}
    	return sum;
    }
    void solve(){
        /*********Begin*********/
        for(int i = 1; i <= 3000; i++){ // i是第一个数字 
        	int b = sum(i); // b是i的因子和 
        	int c = sum(b); // c是b的因子和(c与i相同√) 
        	// c==i:确定是亲密数 
    		// b!=i且b<i:不会有6 6 这种出现同时输出结果不会是bi的反向输出 
        	if(c == i && b != i && b < i){
        		printf("(%d,%d)", b,i);
    		}
    
    	}
    
        /*********End**********/ 
    }
    int main(void)
    {   
        solve();
        return 0;
    }
    
    

    第6关 公约公倍数

    #include<stdio.h>
    //编写最大公约数GCD函数
    /*********Begin*********/
     long long int  GCD(long long int a, long long int b){
    	long long int max = 1;
    	for(long long int i = 1; i <= a; i++){ 
    		if(a%i == 0 && b%i == 0){
    			max = i;
    		}
    	}
    	return max;
    	
    }
    /*********End**********/ 
    
    //编写最小公倍数LCM函数
    /*********Begin*********/
    int LCM(int a, int b){
    	
    }
    /*********End**********/ 
    int main(void)
    {  
        long long int a,b;
        /*********Begin*********/
        scanf("%lld %lld",&a,&b);
        if(a>b){
        	long long int temp = a;
        	a = b;
        	b = temp;  	
    	} // a一直小于b
    	if(a<0 || b <0){
    		printf("Input Error");
    	}else {	
    	long long int max = GCD(a,b);
    	long long int min = a * b / max;
    	printf("%lld %lld",max,min);
        } 
        /*********End**********/ 
        return 0;
    }
    
    

    一维数组和二维数组

    第1关 排序问题

    #include<stdio.h>
    int main(void)
    {
        /*********Begin*********/
        int a[10];
        for(int i = 0; i < 10; i++){
        	scanf("%d", &a[i]);
        }
        for(int i = 0; i < 10; i++){
        	for(int j = i; j < 10; j++){
        		if(a[i] < a[j]){
        			int temp = a[i];
        			a[i] = a[j];
        			a[j] = temp;
        		}
        	}
        }
        for(int i = 0; i < 10; i++){
        	printf("%d ", a[i]);
        }
        /*********End**********/
        return 0;
    }
    

    第2关 查找整数

    #include<stdio.h>
    int main(void)
    {
        /*********Begin*********/
        int n = 0;
        scanf("%d", &n);
        int a[n];
        for(int i = 0; i < n; i++){
        	scanf("%d", &a[i]);
        }
        int index = 0;
        int temp = 0;
        scanf("%d", &index);
        for(int i = 0; i < n; i++){
        	if(a[i] == index){
        		printf("%d", i+1);
        		temp++;
        		break;
        	} 	
        }
        if(temp == 0){
        	printf("-1");
        }
        /*********End**********/
        return 0;
    }
    

    第3关 计算数组中元素的最大值及其所在的行列下标值

    /*
    题目描述:按如下函数原型编程从键盘输入一个m行n列的二维数组,
    然后计算数组中元素的最大值及其所在的行列下标值。其
    中m和n的值由用户键盘输入。
    已知m和n的值都不超过10。
    
    相关知识(略)
    输入
    输入数组大小:"%d,%d"
    下面输入数组中元素。
    
    输出
    输出格式:
    数组大小输入提示信息:"Input m, n:"
    数组元素输入提示信息:"Input %d*%d array: "
    输出格式:"max=%d, row=%d, col=%d"
    
    样例输入
    5,5
    1 2 3 4 5
    4 5 6 100 2
    3 2 1 5 6
    1 2 3 5 4
    3 5 6 4 8
    
    样例输出
    Input m, n:Input 5*5 array:
    max=100, row=2, col=4
    */
    #include<stdio.h>
    int main(void)
    {
        /*********Begin*********/
        int m, n;
        scanf("%d,%d", &m, &n);
        int a[m][n];
        for(int i = 0; i < m; i++){
        	for(int j = 0; j < n; j++){
        		scanf("%d", &a[i][j]);
    		}
    	}
    	int max = a[0][0];
    	int row=0, col=0;
    	for(int i = 0; i < m; i++){
        	for(int j = 0; j < n; j++){
        		if(max <= a[i][j]){
        			max = a[i][j];
        			row = i+1;
        			col = j+1;
    			}
    		}
    	}
    	printf("Input m, n:Input %d*%d array:\n", m,n);
        printf("max=%d, row=%d, col=%d", max,row,col);
    	
    
    
        /*********End**********/
        return 0;
    }
    

    第4关 二分查找

    # include<stdio.h>
    # define m 1000
    int main()
    {
    int a[m],n,b;
        scanf("%d",&b);
        for(n=0;n<b;n++){
            scanf("%d",&a[n]);
        }
        int find;
        scanf("%d",&find);
      if(b==1){
        if(find==a[0]){
          printf("1");
        }
    
      }
        for(n=0;n<(b/2);n++) {
            if (find == a[n]) {
                printf("%d", n + 1);
                break;
            }
        }
    if(find!=a[n]) {
        for (n = (b / 2); n < b; n++) {
            if (find == a[n]) {
                printf("%d", n + 1);
                break;
            }
        }
    }
    if(find!=a[n]){
      printf("None");
    }
    return 0;
    }
    
    

    第5关 鞍点

    #define N 10
    #include <stdio.h>
    int Maxcol(int a[][N],int n,int row){
        int i,maxcol=0;
        for(i=1;i<n;i++)
            if (a[row][i]>a[row][maxcol]) maxcol=i;
        return maxcol;
    }
    int Minrow(int a[][N],int m,int col){
        int i,minrow=0;
        for(i=1;i<m;i++)
            if (a[i][col]<a[minrow][col]) minrow=i;
        return minrow;
    }
    int main(){
        int m,n,i,j;
        int maxcol,minrow;
        int a[N][N];
        scanf("%d %d",&m,&n);
        for(i=0;i<m;i++) for(j=0;j<n;j++)
            scanf("%d",&a[i][j]);
        for(i=0;i<m;i++){
            maxcol=Maxcol(a,n,i);
            minrow=Minrow(a,m,maxcol);
            if (i==minrow){
                printf("Array[%d][%d]=%d\n",i,maxcol,a[i][maxcol]);
                break;
            }
        }
        if(i>=m) printf("None\n");
    }
    
    

    第6关 删除最大值

    #include<stdio.h>
    int main(void)
    {
    	int a[10];
    	int b[9];
    	for(int i = 0; i < 10; i++){
    		scanf("%d", &a[i]);
    	}
    	int max = 0;
    	for(int i = 0; i < 10; i++){
    		if(a[i] > max){
    			max = a[i];
    		}
    	}
    	int n = 0;
    	for(int i = 0; i < 10; i++){
    		if(a[i] != max){
    			b[n] = a[i];
    			printf("%d ", b[n]);
    			n++;
    		}
    	}
      
        return 0;
    }
    

    指针

    第1关 用指针法输入12个整数,然后按每行4个数输出

    #include<stdio.h>
    int main(void)
    {
    	int a[12];
    	int *p = a;
    	for(int i = 0; i < 12; i++){
    		scanf("%d", p++);
    	}
    	p = a;
    	for(int i = 0; i < 12; i++){
    		if((i+1)%4==0){
    				printf("%d", *(p+i));
    				printf("\n");
    		}
    		else printf("%d ", *(p+i));
    	}
        
        return 0;
    }
    

    第2关 指针变量作为函数参数实现两变量交换值

    #include<stdio.h>
    /*********Begin*********/
    void exchange(int *a,int *b){
    	printf("%d %d",*b, *a);
    }
    
    /*********End**********/
    int main(void)
    {
    	int a,b;
    	scanf("%d%d",&a,&b);
    	/*********Begin*********/
    	exchange(&a,&b);
    
    
    	/*********End**********/
        return 0;
    }
    

    第3关 报数

    #include<stdio.h>
    int main()
    {
        int n,a[1000];
        int i,j=1,k=0,m=1;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
           a[i]=i;
        while(k<n-1)
        {
            for(i=1;i<=n;i++)
            {
                
               for(j=m;j<=3;)
                {
                     if(a[i]!=0)
                     {
                        a[i]=j;    
                       m++;    
                       if(m==4)
                       {
                         m=1;  
                       }
                     }
                    break; 
                }
                 
               if(a[i]==3)
               {
                 a[i]=0;
                 k++;
               }               
            }       
        }
        for(i=1;i<=n;i++)
        {
            if(a[i]!=0)
              printf("%d",i);
        }
    }
    
    

    第4关 strcmp函数

    #include<stdio.h>
    int strcmp(char *p1, char *p2)
    {
        int t;
        for (; *p1!='\0'||*p2!='\0'; p1++, p2++)
            if (*p1!=*p2){
                t=*p1-*p2;
                break;
            }
        if (*p1=='\0'&&*p2=='\0')
            t=0;
        return t;
    }
    int main(void)
    {
    	char a[110],b[110];
    	scanf("%s%s",a,b);
    	if(strcmp(a,b)>0)
    		printf("%s", a);
    	else
    		printf("%s", b);
    
    
        return 0;
    }
    

    第1关 实现图的宽度优先遍历

    //Graph
    ///
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "Graph.h"
    /
    
    Graph* Graph_Create(int n)
    {
    	Graph* g=(Graph*)malloc(sizeof(Graph));
    	g->n=n;
    	g->vetex=(char**)malloc(sizeof(char*)*n);
    	int i;
    	for (i=0; i<n; i++) g->vetex[i] = NULL;
    	g->adj=(int*)malloc(sizeof(int)*n*n);
    	int j;
    	for(i=0; i<n; i++) {
    		for(j=0; j<n; j++) {
    			g->adj[i*n+j]=0;
    		}
    	}
    	return g;
    }
    
    void Graph_Free(Graph* g)
    {
    	free(g->adj);
    	int i;
    	for (i=0; i<g->n; i++) free(g->vetex[i]);
    	free(g->vetex);
    	free(g);
    }
    
    int Graph_WidthFirst(Graph*g, int start, Edge* tree)
    //从start号顶点出发宽度优先遍历,(编号从0开始)
    //返回访问到的顶点数,
    //tree[]输出遍历树
    //返回的tree[0]是(-1, start), 
    //真正的遍历树保存在tree[1..return-1], return是返回值
    //顶点的访问次序依次为tree[0].to, tree[1].to,  ..., tree[return-1].to
    //输入时,tree[]的长度至少为顶点数
    //返回值是从start出发访问到的顶点数
    {
    	const int MAX=1000;
    	Edge queue[MAX];
    	int head=0, tail=0;
    #define In__(a,b)  {queue[tail].from=a; queue[tail].to=b; tail=(tail+1)%MAX;}/
    #define Out__(a,b)  {a=queue[head].from; b=queue[head].to; head=(head+1)%MAX;}//
    #define QueueNotEmpty (head!=tail?1:0)///
    #define HasEdge(i,j)  (g->adj[(i)*g->n+(j)]==1)
    
    	char* visited=(char*)malloc(sizeof(char)*g->n);
    	memset(visited, 0, sizeof(char)*g->n);
    
    	int parent=-1;  
    	int curr=start;
    	In__(parent, curr); 
    	int k=0; //已经访问的结点数
    	/*请在BEGIN和END之间实现你的代码*/
        /*****BEGIN*****/
         while (QueueNotEmpty) {
            Out__(parent, curr); 
            if (visited[curr]) continue;
            visited[curr]=1;
            tree[k].from=parent; tree[k].to=curr; k++;
            int j;
            for (j=0; j<=g->n-1;j++) {
                if (HasEdge(curr,j) && !visited[j])In__(curr,j);
            }
        }
        /*****END*******/
    	return k;
    #undef In__//
    #undef Out__///
    #undef QueueNotEmpty
    #undef HasEdge
    }
    

    第2关 实现图的深度优先遍历

    //Graph
    ///
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "Graph.h"
    /
    Graph* Graph_Create(int n)
    {
    	Graph* g=(Graph*)malloc(sizeof(Graph));
    	g->n=n;
    	g->vetex=(char**)malloc(sizeof(char*)*n);
    	int i;
    	for (i=0; i<n; i++) g->vetex[i] = NULL;
    	g->adj=(int*)malloc(sizeof(int)*n*n);
    	int j;
    	for(i=0; i<n; i++) {
    		for(j=0; j<n; j++) {
    			g->adj[i*n+j]=0;
    		}
    	}
    	return g;
    }
    
    void Graph_Free(Graph* g)
    {
    	free(g->adj);
    	int i;
    	for (i=0; i<g->n; i++) free(g->vetex[i]);
    	free(g->vetex);
    	free(g);
    }
    
    int Graph_DepthFirst(Graph*g, int start, Edge* tree)
    //从start号顶点出发深度优先遍历,(编号从开始)
    //返回访问到的顶点数,
    //tree[]输出遍历树
    //返回的tree[0]是(-1, start), 
    //真正的遍历树保存在tree[1..return-1], return是返回值
    //顶点的访问次序依次为tree[0].to, tree[1].to, ..., tree[return-1].to
    //输入时,tree[]的长度至少为顶点数
    //返回值是从start出发访问到的顶点数
    {
    	/*请在BEGIN和END之间实现你的代码*/
        /*****BEGIN*****/
        /*请在BEGIN和END之间实现你的代码*/
    /*****BEGIN*****/
    const int MAX=1000;
        Edge stack[MAX];
        int top=-1;
    #define Push__(a,b)  {top++; stack[top].from=a; stack[top].to=b;}
    #define Pop__(a,b)  {a=stack[top].from; b=stack[top].to; top--;}///
    #define StakNotEmpty (top>=0?1:0)
    #define HasEdge(i,j)  (g->adj[(i)*g->n+(j)]==1)
        char* visited=(char*)malloc(sizeof(char)*g->n);
        memset(visited, 0, sizeof(char)*g->n);
        int parent=-1;  
        int curr=start;
        Push__(parent, curr); 
        int k=0; //已经访问的结点数
        while (StakNotEmpty) {
            Pop__(parent, curr); 
            if (visited[curr]) continue;
            visited[curr]=1;
            tree[k].from=parent; tree[k].to=curr; k++;
            int j;
            for (j=g->n-1; j>=0; j--) {
                if (HasEdge(curr,j) && !visited[j]) Push__(curr,j);
            }
        }
        free(visited);
        return k;
    #undef Push__
    #undef Pop__///
    #undef StakNotEmpty//
    #undef HasEdge
    /*****END*******/
        /*****END*******/
    }
    

    第1关 由双遍历序列构造二叉树

    #include <stdio.h>
    
    #include <stdlib.h>
    
    #include <string.h>
    
    #include "ConstructTree.h"
    
    
    
     
    
    /*
    
    InPreToTree(): 由前序遍历序列和中序遍历序列构造二叉树
    
    前序序列为pa[p1:p2]
    
    中序序列为ia[i1:i2]
    
    返回所构造的二叉树的根指针
    
    */
    
    TNode* InPreToTree(char *pa, char *ia, int p1, int p2, int i1, int i2)
    
    {
        /*请在BEGIN和END之间实现你的代码*/
    
        /*****BEGIN*****/
    
        TNode *root=new TNode;
    
        root->data=pa[p1];
    
        root->left=NULL;
    
        root->right=NULL;                  //递归终止条件:先序遍历中只有一个结点
    
        if(pa[p1]==pa[p2])
    
        return root;
    
                                          //数组元素名是其首地址
    
        int a=i1;
    
        while(ia[a]!=root->data&&a<=i2)    //中序里面
    
        a++;
    
        if(ia[a]!=root->data)             //数组2遍历完成
    
            exit(0);
    
        int leftlen=a-i1;  
    
        if(leftlen>0)                   //左子树的个数
    
        root->left=InPreToTree(pa,ia,p1+1,p1+leftlen,i1,a-1);
    
        
    
        int rightlen=i2-a;
    
        if(rightlen>0)
    
        root->right=InPreToTree(pa,ia,p2-rightlen+1,p2,a+1,i2);
    
     return root;
    
        
    
        /******END******/
    
        /*请不要修改[BEGIN,END]区域外的代码*/
    
    } 
    
    void PrintPostTravel(TNode* t)
    
    {
        if(t==NULL) return;
    
        if(t->left) PrintPostTravel(t->left);
    
        if(t->right) PrintPostTravel(t->right);
    
        printf("%c", t->data);
    
    }
    
    void DeleteTree(TNode* t)
    
    {
        if(t==NULL) return;
    
        if(t->left) DeleteTree(t->left);
    
        if(t->right) DeleteTree(t->right);
    
        delete t;
    
    }
    

    第2关 打印二叉树

    ///
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "PrintTree.h"
    /
    
    /*=================================================
    函数:TNode* LayersToTree(char *A, int n) 
    功能:由补充虚结点(‘^’)的层序序列构造二叉树
    参数:A: 补充了虚结点(‘^’)的层序序列
              n: 序列的长度
    输出: 所构造的二叉树的根指针,NULL表示没有构造出二叉树
    ==================================================*/
    TNode* LayersToTree(char *A, int n)
    {
    	TNode**  pnode;
    	TNode* node;
    	int i;
    	if(n<=0)
    		return NULL;
    	pnode= new TNode*[n];
    	for(i=0; i<n; i++){
    		if(A[i]!='^'){
    			node=new TNode;
    			node->data=A[i];
    			node->left=NULL;
    			node->right=NULL;
    			pnode[i]=node;
    		}
    		else 
    			pnode[i]=NULL;
    	}
    	for(i=0; i<n; i++){
    		if(pnode[i]==NULL) continue;
    		if(2*(i+1)<=n && pnode[2*(i+1)-1]!=NULL)
    			pnode[i]->left=pnode[2*(i+1)-1];
    		if(2*(i+1)+1<=n && pnode[2*(i+1)]!=NULL)
    			pnode[i]->right=pnode[2*(i+1)];
    	}
    	node=pnode[0];
    	delete pnode;
    	return node;
    } 
    
    void PrintTreeRootLeft(TNode* r, int layer)
    //r是树中一棵子树的根,打印以结点r为根的子树,
    //layer是r在树中所处的层,约定树的根结点的层号为1
    {
        /*请在BEGIN和END之间实现你的代码*/
        /*****BEGIN*****/
     const int W=5;
        int i,j;
        if (r==NULL) return;
        PrintTreeRootLeft(r->right, layer+1);
        for(i=1; i<layer; i++) {
            for (j=0;j<W;j++) printf("%c", '-');
        }
        for (j=0; j<W-1; j++) printf("%c",'-');
        printf("%c\n", r->data);
        PrintTreeRootLeft(r->left, layer+1);
        /******END******/
        /*请不要修改[BEGIN,END]区域外的代码*/
    }
    
    void DeleteTree(TNode* t)
    {
    	if(t==NULL) return;
    	if(t->left) DeleteTree(t->left);
    	if(t->right) DeleteTree(t->right);
    	delete t;
    }
    

    计算表达式

    第1关 栈的应用 - 计算中缀表达式

    /**********************************************************
    	date: July 2017
        copyright: Zhu En(祝恩)
        DO NOT distribute this code.
    **********************************************************/
    #include <stdio.h>
    #include <stdlib.h>
    #include "LnkStack.h"
    #include "Infix.h"
    
    //
    void compute(LinkStack* so, LinkStack* sd)
    //++++++++++++++++++++++++++++++++++++++++++++++
    //so 运算符栈
    //sd 操作数栈
    //1 从运算符栈出栈一个运算符
    //2 从操作数栈出栈两个操作数
    //3 用出栈的运算符对出栈的操作数进行运算
    //4 将运算结果进操作数栈
    //+++++++++++++++++++++++++++++++++++++++++++++++
    {
    	T a,b,c,d;
    	LS_Pop(so,c);
    	LS_Pop(sd,a);
    	LS_Pop(sd,b);
    	if (c=='*') d=b*a;
    	else if (c=='/') d=b/a;
    	else if (c=='+') d=b+a;
    	else if (c=='-') d=b-a;
    	else printf("never occur!");
    	LS_Push(sd, d);
    }
    
    double ComputeInfix(char* s)
    {
        // 请在此添加代码,补全函数ComputeInfix,计算中缀表达式
        /********** Begin *********/
        int i=0;
        LinkStack* so=LS_Create(); 
        LinkStack* sd=LS_Create(); 
        while(s[i]) {
            if ('0'<=s[i] && s[i]<='9') {
                LS_Push(sd, s[i++]-48);
                continue;
            }
            if(s[i]=='('||LS_IsEmpty(so)) {
                LS_Push(so, s[i++]); 
                continue;
            }
            if(s[i]==')') {
                T topitem;
                while(LS_Top(so,topitem) && topitem !='(' ) 
                    compute(so, sd);
                LS_Pop(so,topitem);
                i++;
                continue;
            }
            if(s[i]=='*'||s[i]=='/') {
                T c;
                LS_Top(so,c);
                if (c=='*' || c=='/') 
                    compute(so, sd);
                LS_Push(so, s[i++]);
                continue;
            }
            if(s[i]=='+'||s[i]=='-') {
                T topitem;
                while(LS_Top(so,topitem) && topitem !='(' ) 
                    compute(so, sd);
                LS_Push(so, s[i++]);
                continue;
            }
        }
        while(!LS_IsEmpty(so)) 
            compute(so, sd);
        T res;
        LS_Top(sd,res);
        LS_Free(so);
        LS_Free(sd);
        return res;
        /********** End **********/
    }
    
    

    第2关 栈的应用 - 计算后缀表达式

    /**********************************************************
    	date: July 2017
        copyright: Zhu En
        DO NOT distribute this code.
    **********************************************************/
    #include <stdio.h>
    #include <stdlib.h>
    #include "LnkStack.h"
    #include "Postfix.h"
    
    double ComputePostfix(char* s)
    {
        // 请在此添加代码,补全函数ComputePostfix,计算后缀表达式
        /********** Begin *********/
        LinkStack* sd=LS_Create();
        int i=0;
        T k,top1,top2;
        while(s[i]) {
            switch (s[i]) {
            case '+':
                LS_Pop(sd,top1);
                LS_Pop(sd,top2);
                k=top1+top2;
                LS_Push(sd,k);
                break;
            case '-':
                LS_Pop(sd,top1);
                LS_Pop(sd,top2);
                k=top2-top1;
                LS_Push(sd,k);
                break;
            case '*':
                LS_Pop(sd,top1);
                LS_Pop(sd,top2);
                k=top1*top2;
                LS_Push(sd,k);
                break;
            case '/':
                LS_Pop(sd,top1);
                LS_Pop(sd,top2);
                k=top2/top1;
                LS_Push(sd,k);
                break;
            default:
                LS_Push(sd, (int)(s[i]-48));
            }
            i++;
        }
        T res;
        LS_Top(sd,res);
        LS_Free(sd);
        return res;
        /********** End **********/
    }
    

    字符串匹配

    第1关 实现朴素的字符串匹配

    int FindSubStr(char* t, char* p)
    /*
    从字符串t查找子字符串p。
    字符串以数值结尾,例如p="str",那么p[0]='s',p[1]='t',p[2]='r',p[3]=0。
    采用朴素的匹配算法,返回子字符串第一次出现的位置,例如t="string ring",p="ring",则返回2。
    若没有找到,则返回-1。
    */
    {
        // 请在此添加代码,补全函数FindSubStr
        /********** Begin *********/
        int i=0, j=0;
        while(p[i]!=0 && t[j]!=0) {
            if (p[i]==t[j]) {
                i ++;
                j ++;
            }
            else {
                j = j-i+1;
                i = 0;
            }
        }
        if (p[i] == 0) return j-i;
        else return -1;
        /********** End **********/
    }
    

    第2关 实现KMP字符串匹配

    /*************************************************************
        date: 
        copyright: Zhu En
        DO NOT distribute this code without my permission.
    **************************************************************/
    //字符串 实现文件
    //
    #include <stdio.h>
    #include <stdlib.h>
    #include "kmp.h"
    /
    
    void KmpGenNext(char* p, int* next)
    //生成p的next数组, next数组长度大于等于字符串p的长度加1
    {
        next[0]= -1;
        int k= -1;
        for (int i=1; p[i-1]!=0; i++) 
        {    
            while(k>=0&&p[k]!=p[i-1])   k=next[k];
            k=k+1;
            if (p[i]==p[k])  next[i]=next[k];
            else    next[i]=k;
        }
    }
    
    
    int KmpFindSubWithNext(char* t, char* p, int* next)
    //从t中查找子串p的第一次出现的位置
    //若找到,返回出现的位置,否则返回-1
    {
    	int i=0, j=0;
    	while(p[i]!=0 && t[j]!=0)	{
    		if(p[i]==t[j]) 	{ 
    			i++;  
    			j++; 
    		}
    		else  if (next[i]>=0) {
    			i = next[i];
    		}
    		else  { 
    			i=0;  
    			j++; 
    		}
    	}
    	if(p[i]==0)  return j-i; //found
    	else  return -1;  //not found
    }
    
    
    

    队列

    第1关 实现一个顺序存储的队列

    #include <stdio.h>
    #include <stdlib.h>
    #include "SeqQueue.h"
    SeqQueue* SQ_Create(int maxlen)
    // 创建顺序队列, 队列最多存储maxlen个队列元素
    {
        SeqQueue* sq=(SeqQueue*)malloc(sizeof(SeqQueue));
        sq->data=(T*)malloc(sizeof(T)*(maxlen+1));
        sq->front=sq->rear=0;
        sq->max=maxlen+1;
        return sq;
    }
    void SQ_Free(SeqQueue* sq)
    // 释放队列空间,以删除队列
    {
        free(sq->data);
        free(sq);
    }
    void SQ_MakeEmpty(SeqQueue* sq)
    // 将队列置空
    {
        sq->front=0;
        sq->rear=0;
    }
    bool SQ_IsEmpty(SeqQueue* sq)
    // 判断队列是否为空,为空返回true,否则返回false。
    {
        return sq->front==sq->rear;
    }
    bool SQ_IsFull(SeqQueue* sq)
    // 判断队列是否为满。为满返回true,否则返回false。
    {
        return (sq->rear+1)%sq->max==sq->front;
    }
    int SQ_Length(SeqQueue* sq)
    // 队列长度
    {
        return (sq->rear-sq->front+sq->max)%sq->max;
    }
    bool SQ_In(SeqQueue* sq, T x)
    // 将x入队。若入队失败(队列满),则返回false,否则返回true。
    {
        if(SQ_IsFull(sq)) 
     {
      return false; 
     }
        else
     {
            T* head=sq->data;
            head[sq->rear]=x;
            sq->rear=(sq->rear+1)%sq->max;
            return true;
        }
    }
    bool SQ_Out(SeqQueue* sq, T& item)
    // 从队列sq出队一个元素,返回时item为出队的元素的值。若出队成功(队列不为空),则返回true,否则(队列空),返回false,此时item不会返回有效值。
    {
        if(SQ_IsEmpty(sq)) 
     {
      return false;
     }
        else
     {
            T* head=sq->data;
            item=head[sq->front];
            sq->front=(sq->front+1)%sq->max;//记得加sq->不要疏忽大意
            return true;
        }
    }
    bool SQ_Head(SeqQueue* sq, T& head)
    // 获取队列头结点元素,返回时head保存头结点元素。
    // 若获取失败(队列空),则返回值为false,否则返回值为true。
    {
        if ( SQ_IsEmpty(sq) )
     {
            return false;
        }
        else 
     {
            head = sq->data[sq->front];
            return true;
        }
    }
    void SQ_Print(SeqQueue* sq)
    // 依次打印出队列中的每个元素
    {
        int i=sq->front;
        if (SQ_IsEmpty(sq)) 
     {
            printf("queue is emtpy");
            return;
        }
        for (i=sq->front; i!=sq->rear; i=(i+1)%sq->max) 
     {
            printf("%d  ", sq->data[i]);
        }
        printf("\n");
    }
    

    第2关 实现一个链接存储的队列

    #include <stdio.h>
    #include <stdlib.h>
    #include "CLnkQueue.h"
    
    LNode* CLQ_Create()
    // 创建一个队列
    {
        LNode* rear=(LNode*)malloc(sizeof(LNode));
        rear->data = 0;
        rear->next = rear;
        return rear;
    }
    void CLQ_Free(LNode* rear)
    // rear指向尾结点
    {
        CLQ_MakeEmpty(rear);
        free(rear);
    }
    
    void CLQ_MakeEmpty(LNode* & rear)
    // rear指向尾结点
    // 将队列变为空队列
    {
        T item;
        while(!CLQ_IsEmpty(rear))
            CLQ_Out(rear,item);
    }
    
    bool CLQ_IsEmpty(LNode* rear)
    // 判断队列是否为空
    {
        // 请在这里补充代码,完成本关任务
        
        return rear->next->data==0;
    	//return rear->next->next==rear->next;
        
    }
    
    int CLQ_Length(LNode* rear)
    // 返回队列长度,rear指向尾结点
    {
        // 请在这里补充代码,完成本关任务
       
        return rear->next->data;
       
    }
    
    void CLQ_In(LNode* & rear, T x)
    // 入队列, 新结点加入链表尾部。rear指向尾结点
    {
        // 请在这里补充代码,完成本关任务
       
    	LNode*node=(LNode*)malloc(sizeof(LNode));
        node->data=x;
        node->next=rear->next;
        rear->next=node;
        rear=node;
        rear->next->data++;
        
    }
    
    bool CLQ_Out(LNode* & rear, T& item)
    // 出队列。空队列时,返回值为false。rear指向尾结点
    {
        if(CLQ_IsEmpty(rear)){
        	return false;
    	}
         if(rear->next->next==rear){
        	LNode*node=rear;
        	item=rear->data;
        	rear->next->next=rear->next;
        	rear=rear->next;
        	free(node);
    	}else{
    		item=rear->next->next->data;
    		LNode*node=rear->next->next;
    		rear->next->next=node->next;
    		free(node);
    		
    	}
    	rear->next->data--;
        return true;
        
    }
    
    bool CLQ_Head(LNode* rear, T& item)
    // rear指向尾结点
    // 获取队列头。空队列时返回值为false。
    {
        if (CLQ_IsEmpty(rear)) 
            return false;
    
        item = rear->next->next->data;
        return true;
    }
    void CLQ_Print(LNode* rear)
    // 打印队列
    {
        if (CLQ_IsEmpty(rear))  {
            printf("The queue is: empty. \n");
            return;
        }
        LNode* node=rear->next->next;
        do {
            printf("%d  ", node->data);
            node = node->next;
        }   while (node != rear->next); 
        //printf("\n");
    }
    
    
    

    第1关 顺序存储的栈

    #include <stdio.h>
    #include <stdlib.h>
    #include "SeqStack.h"
    /*创建一个栈*/
    SeqStack* SS_Create(int maxlen)
    {
        SeqStack* ss=(SeqStack*)malloc(sizeof(SeqStack));
        ss->data=(T*)malloc(maxlen*sizeof(T));
        ss->top=-1;
        ss->max=maxlen;
        return ss;
    }
    /*释放一个栈*/
    void SS_Free(SeqStack* ss)
    {
        free(ss->data);
        free(ss);
    }
    /*清空一个栈*/
    void SS_MakeEmpty(SeqStack* ss)
    {
        ss->top=-1;
    }
    bool SS_IsFull(SeqStack* stack)
    // 判断栈是否为满。为满返回true,否则返回false。
    {
        return stack->top+1>=stack->max;
    }
    bool SS_IsEmpty(SeqStack* stack)
    // 判断栈是否为空。为空返回true,否则返回false。
    {
        return stack->top<0;
    }
    int SS_Length(SeqStack* stack)
    // 获取栈元素个数
    {
        return stack->top+1;
    }
    bool SS_Push(SeqStack* stack, T x)
    // 将元素x进栈,若满栈则无法进栈,返回false,否则返回true
    {
        if (SS_IsFull(stack)) 
        {
            return false;
        }
        stack->top++;
        stack->data[stack->top]=x;
        return true;
    }
    bool SS_Pop(SeqStack* stack, T &item)
    // 出栈的元素放入item。若出栈成功(栈不为空),则返回true;否则(空栈),返回false。
    {
        if (SS_IsEmpty(stack)) 
        {
            return false;
        }
        item = stack->data[stack->top];
        stack->top--;
        return true;
    }
    /*获取栈顶元素放入item中,空栈则返回false*/
    bool SS_Top(SeqStack* ss, T & item)
    {
        if (SS_IsEmpty(ss)) 
        {
            return false;
        }
        item = ss->data[ss->top];
        return true;
    }
    /*从栈底到栈顶打印出所有元素*/
    void SS_Print(SeqStack* ss)
    {
        if (SS_IsEmpty(ss)) 
        { 
            printf("stack data: Empty!\n");
            return;
        }
        printf("stack data (from bottom to top):");
        int curr=0;
        while(curr<=ss->top) 
        {
            printf(" %d", ss->data[curr]);
            curr++;
        }
        //printf("\n");
    }
    

    第2关 实现一个链接存储的栈

    #include <stdio.h>
    #include <stdlib.h>
    #include "LnkStack.h"
    /*创建栈*/
    LinkStack* LS_Create()
    {
        LinkStack* ls=(LinkStack*)malloc(sizeof(LinkStack));
        ls->top = NULL;
        ls->len = 0;
        return ls;
    }
    /*释放栈*/
    void LS_Free(LinkStack* ls)
    {
        LNode* curr = ls->top;
        while(curr) 
        {
            LNode* next = curr->next;
            free(curr);
            curr=next;
        }
        free(ls);
    }
    /*将栈变为空栈*/
    void LS_MakeEmpty(LinkStack* ls)
    {
        LNode* curr = ls->top;
        while(curr) 
        {
            LNode* next = curr->next;
            free(curr);
            curr=next;
        }
        ls->top = NULL;
        ls->len = 0;
    }
    /*判断栈是否为空*/
    bool LS_IsEmpty(LinkStack* ls)
    {
        return ls->len == 0;
    }
    /*获取栈的长度*/
    int LS_Length(LinkStack* ls)
    {
        return ls->len;
    }
    /*将x进栈*/
    void LS_Push(LinkStack* ls, T x)
    {
        LNode* node=(LNode*)malloc(sizeof(LNode));
        node->data=x;
        node->next=ls->top;
        ls->top = node;
        ls->len ++;
    }
    /*出栈。出栈元素放入item;如果空栈,将返回false*/
    bool LS_Pop(LinkStack* ls, T& item)
    {
        LNode* node=ls->top;
        if (node==NULL) 
        {
            return false;
        }
        item = node->data;
        ls->top = node->next;
        ls->len --;
        free(node);
        return true;
    }
    /*读栈顶元素放入item。如果空栈,将返回false*/
    bool LS_Top(LinkStack* ls, T& item)
    {
        LNode* node=ls->top;
        if (node==NULL) 
        {
            return false;
        }
        item = node->data;
        return true;
    }
    /*从栈顶到栈底打印各结点数据*/
    void LS_Print(LinkStack* ls)
    {
        if (ls->len==0)
        { 
            printf("The stack: Empty!");
            return;
        }
        printf("The stack (from top to bottom):");
        LNode* curr=ls->top;
        while(curr) 
        {
            printf(" %d", curr->data);
            curr=curr->next;
        }
       // printf("\n");
    }
    
    展开全文
  • 福州大学2006级《算法与数据结构》期末上机考试试题.pdf
  • 数据结构上机题4.1及参考答案 这只是其中一道题,一共9道题 实践考试基本上就是这几道题 的变=变形罢了...
  • 实现一个链表,并构造一个方法,找到倒数第x个节点的值 # 单链表节点创建 class LNode: def __init__(self,elem,next = None): self.elem = elem self.next = next # 单链表创建 class LList: ...
  • 考试要求:本次考试共列考核试题4大题,考生可以在所列4个考核试题中任选3个小题(即可能只属于2个大题),作为上机考核试题。 考核原则:所选题目在上机编程调试通过后即为考核通过。监考教师依据学生编程及调试...
  • 物理结构是数据结构在计算机中的表示又称为(存储结构) 3.数据元素的逻辑结构包括( 线性(树)和图状结构3种类 型树形结构和图状结构合称为(非线性结构) 4(数据元素)是数据的基本单位(数据项)是数据不可分割的最小单位 ...
  • 数据结构期末考试复习总结PPT
  • 数据结构课程设计实验验优参考(附数据结构上机实验、上机考试代码)
  • 数据结构C语言版期末考试试题(有答案),适合考前复习突击
  • 2015年福师大数据结构期末上机考文件代码
  • 数据结构课程相关上机实验、考试代码
  • 本资源为专栏《数据结构与算法上机实验专栏》对应的上机源代码,可直接上机运行,程序带有良好的注释。本课程考试98分,课程设计96分。
  • 福州大学2005级《算法与数据结构》期末上机考试试题.pdf
  • 时间:2019-05-12 08:38:58 作者:admin数据结构实验报告 课程 数据结构 _ 院 系 专业班级 实验地点姓 名 学 号 实验时间 指导老师 数据结构上机实验报告1 一﹑实验名称: 实验一——链表 二﹑实验目的: 1....
  • 方便、快捷、简单易懂,对那些需要的人有帮助的
  • 数据结构上机题4.2及参考答案 这只是其中一道题,一共9道题 实践考试基本上就是这几道题 的变=变形罢了...
  • 数据结构上机题3.1及参考答案 这只是其中一道题,一共9道题 实践考试基本上就是这几道题 的变=变形罢了...
  • 精选 数据结构上机考试试题 1设有两个有序序列利用归并排序将它们排成有序表并输出 2设有一有序序列从键盘输入一个数判别是否在序列中如果在输出YSE否则将它插入到序列中使它仍然有序并输出排序后的序列 3设有一有序...
  • 这个是严蔚敏老师数据结构教程配套习题集中的上机题,测试数据是用我自己的数据,在vs2005中可以顺利运行~~

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,228
精华内容 2,891
关键字:

数据结构上机考试

数据结构 订阅
友情链接: ISDN-protocol.zip