数据结构实训作业

Sukuna发布

(I)

第一关

本关任务:已知顺序表L中的数据元素递增有序,数据元素类型为int。相关定义如下: 
#define LIST_INIT_SIZE 20 
#define LISTINCREMENT 10 
typedef int ElemType; 
typedef struct { ElemType *elem; 
int length; 
int listsize; } SqList; 
试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。 
函数原型:int insert(SqList &L,ElemType x);

这道题白给

int insert(SqList &L, ElemType x)
{
    /**********begin**********/
    int cnt = 0;
    while (L.elem[cnt] < x && cnt < L.length)
        cnt++;//计算应该到达的位置
//这个时候cnt应该指向刚好比x大的那一位,那这一位后面的所有的元素都往后摞一位,处理即可
    for (int i = L.length; i > cnt; i--)
    {
        L.elem[i] = L.elem[i - 1];//从最后一个元素的下一个空格开始移动
    }
//从后往前进行处理
    L.elem[cnt] = x;
    L.length += 1;
    if (L.length > L.listsize)
    {
        ElemType *newbase;
        newbase = (ElemType *)realloc(L.elem,
                                      (L.listsize + LISTINCREMENT) * sizeof(ElemType));
//溢出的处理
        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }
    return 1;
    /**********end**********/
}

第二关

本关任务:设以带头结点的双向循环链表表示线性表L=(a1,a2,…,an),试编写一个时间复杂度为O(n)的算法,将L改变成L=(a1,a3,…,an,…,a4,a2)。 相关定义如下:
typedef int ElemType; 
typedef struct Dnode { 
ElemType data; 
struct Dnode * prior, * next; 
} * DuLinkList; 
函数原型:void adjust(DuLinkList L);

//思路就是,奇数的节点,往前插,偶数的节点,插后面去
void  adjust(DuLinkList&  L)
{
        DuLinkList Lnew = (DuLinkList)malloc(sizeof(Dnode));
        Lnew->data = 0;
        Lnew->prior = Lnew;
        Lnew->next = Lnew;
        Dnode *p, *q, *pa, *pb;
        q = p = L->next;
        pa = pb = Lnew;
//建一个空的双向链表
//p和q遍历L,pb和pa来构建新的逻辑关系,pb最后,pa最前
        while (p != L)//没有遍历到最后
        {
            if (p != L)
            {
                /*L中奇数个数据插入Lnew*/
                q = p->next;//保留 L 链表
                //pa之后插入p
                p->prior = pa;
//p是当前要插入的偶数节点,q保存了p的下一个节点
                pa->next = p;
//pa往后补一个节点
                p->next = pb;
//p往后指,构建循环
                pb->prior = p;
//最前面的结点指向最后面的结点
                pa = pa->next;
//pa指到最后
                p = q;//p指向 待操作 L
//p指向q(偶数节点)
            }
            if (p != L)
            {
                /*L中偶数个数据插入Lnew*/
                q = p->next;//保留 L 链表
                //pb之前插入p
                p->next = pb;
//p的下一个指向原链表的最后一个指针
                pb->prior = p;
//最后一个指针往回指
                p->prior = pa;
//p往回指向最后的结点,构建循环
                pa->next = p;
//也循环回去
                pb = pb->prior;
//pb往回指,保证pb指向最后
                p = q;//p指向 待操作 L
            }
        }
    L = Lnew;
}
主要是每个链表的逻辑关系
一定要注意!保存原链表L

第三关

已知A、B和C为3个递增有序的线性表,现要求对A表做如下操作,删除那些既在B中出现,也在C中出现的元素。以顺序表作为线性表的物理结构,编写实现上述操作的算法。 
函数原型:void TriSqList(SqList &A,SqList B,SqList C)

void TriSqList(SqList &A, SqList B, SqList C)
{
	/**********Begin**********/
	int pa = 0, pb = 0, pc = 0;
	if (A.length > 0)
	{
		while (pa < A.length && pb < B.length && pc < C.length)
//如果没到末尾
		{
			if(B.elem[pb]==C.elem[pc])
//如果B和C的存在相同的元素
			{
                                 if(A.elem[pa]==B.elem[pb])
//这个时候ABC相同,就可以删除A.elem[pa]了
				{
					int nxt=pa+1,nsiz=1;
					while (A.elem[nxt]==A.elem[pa])//寻找有重复的元素,然后都删除掉
					{
						nxt++;
						nsiz++;
					}
					for(int i=nxt;i<A.length;i++)
					{
			A.elem[i-nsiz]=A.elem[i];
					}
					A.length-=nsiz;//A减少
					pb++;
					pc++;
					//B和C往后移
				}
				else if(A.elem[pa]<B.elem[pb])pa++;
//如果A比B小,那A就往后移动匹配B
				else 
//A比B大,BC往后移动匹配A
				{
					pb++;
					pc++;
				}
			}
			else if(B.elem[pb]<C.elem[pc])
//B比C小,B往后移
			{
                pb++;
			}
			else
			{
				pc++;
			}
		}
	}
	/**********End**********/
}
这个是常见操作,设置双指针,适合处理有大小差别的元素,一遍遍历就可以了,通过指针的比较来判断指针移动的方向

第四关

本关任务:已知A、B和C为3个递增有序的线性表,现要求对A表做如下操作,删除那些既在B中出现,也在C中出现的元素。以带表头结点的单链表作为线性表的物理结构,编写实现上述操作的算法。 
函数原型:void TriLinkList(LinkList A,LinkList B,LinkList C);

void TriLinkList(LinkList ha,LinkList hb,LinkList hc)
{//本算法的前提是三个表都不能为空
    //本算法的功能是除去表a中在表b和表c同时出现的元素

    //删除单链表A中的即在单链表B中又在单链表C中的元素
    //A,B,C均递增有序
    LinkList pa = ha->next;
    LinkList prev = ha;
    LinkList pb = hb->next;
    LinkList pc = hc->next;
    while (pb && pc && pa){
        if (pb->data < pc->data){
            pb = pb->next;
        }
        else if (pb->data > pc->data){
            pc = pc->next;
        }
        //移动使得pb和pc值是一样的
        else{
            if (pa->data < pb->data){//移动使得pa,pb,pc都一样
                prev = pa;
                pa = pa->next;
            }
            else if (pa->data > pb->data){//pa比pb,pc大,那就是pa里找不到,pb和pc往后移
                pc = pc->next;
                pb = pb->next;
            }
            else{//找到了,删除A
                prev->next = pa->next;
                free(pa);
                pa = prev->next;
            }
        }
    }
}
这个是常见操作,设置双指针,适合处理有大小差别的元素,一遍遍历就可以了,通过指针的比较来判断指针移动的方向

II

第一关

本关任务:编写程序实现双向栈。 假定以顺序存储结构实现一个双向栈,即在一个一维数组的存储空间中存在着两个栈,它们的栈底分别设在数组的两个端点。试编写实现着个双向栈的3个函数: 初始化栈inistack、入栈push和出栈pop

双向栈的物理结构示意图如下:

相应地,根据该示意图定义其数据类型:
#define N 100 
typedef struct TWSTACK { ElemType elem[N]; int top1,top2; } TWSTACK;

//在下面的begin和end间填写相应代码
void inistack(TWSTACK &S)
//该函数实现初始化S,得到2个空栈。根据双向栈的示意图,理解初始化要求。
{
/***************begin***************/
    for(int i=0;i<N;i++){
        S.elem[i]=0;//每个元素置0
    }
    S.top1=0;
    S.top2=N-1;//初始化指针
/*************** end ***************/
}
int push(TWSTACK &S,int i,ElemType e)
//i取值1或2,分别对应左或右栈,将元素e压入S的对应栈。成功入栈返回1,否则返回0
{
/***************begin***************/
    if(i==1){
        if(S.top1>S.top2) return 0;
        S.elem[S.top1++]=e;
        return 1;
    }
    else{
        if(S.top1>S.top2) return 0;
        S.elem[S.top2--]=e;
        return 1;
    }
    /*************** end ***************/
}

int pop(TWSTACK &S,int i, ElemType &e)
//i取值1或2,分别对应左或右栈,将S对应栈的栈顶元素出栈,赋值给e。成功出栈返回1,否则返回0
{
/***************begin***************/
    if(i==1){
        if(S.top1==0) return 0;
        e=S.elem[--S.top1];
        return 1;
    }
    else{
        if(S.top2==N-1) return 0;
        e=S.elem[++S.top2];
        return 1;
    }

/*************** end ***************/
}
注意根据栈指针的特性规定前缀还是后缀

第二关

本关任务:编写程序实现循环队列。 假定以循环队列定义为:以域变量front和length分别指示循环队列中的队首元素的位置和内含元素的个数。试编写实现循环队列3个函数: 初始化队列iniQueue、入队enQueue和出队deQueue

为了完成本关任务,你需要掌握:1.队列,2.循环队列。 循环队列数据类型: #define MAXLENGTH 100 
typedef struct QUEUE { ElemType elem[MAXLENGTH];
int front,length; 
} QUEUE;

//在下面的begin和end间填写相应代码
void iniQueue(QUEUE &Q)
//该函数实现初始化Q
{
/***************begin***************/
    for(int i=0;i<MAXLENGTH;i++){
        Q.elem[i]=0;
    }
    Q.front=0;
    Q.length=0;
/*************** end ***************/
}
int enQueue(QUEUE &Q,ElemType e)
//将元素e入队Q。成功入栈返回1,否则返回0
{
/***************begin***************/
    if(Q.length==MAXLENGTH) return 0;
    Q.elem[(Q.front+Q.length)%MAXLENGTH]=e;
    Q.length++;
/*************** end ***************/
}
int deQueue(QUEUE &Q, ElemType &e)
//将Q队首元素出队,赋值给e。成功出队返回1,否则返回0
{
/***************begin***************/
    if(!Q.length) return 0;
    e=Q.elem[Q.front];
    Q.front=(Q.front+1)%MAXLENGTH;
    Q.length--;
/*************** end ***************/
}
注意循环链表的移动规则
判定双向链表为满的规则?

第三关

本关任务:假设称正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’ 是回文,‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为 结束符的字符序列是否是“回文”。

int isPalindrome(char *str)
//判断字符串str是否回文,是则返回1,否则返回0
{
/**********begin**********/
    char x,y;
    TWSTACK S;
    QUEUE Q;
    iniQueue(Q);
    inistack(S);
    while(*str!='@'){
        push(S,1,*str);
        enQueue(Q,*str);
        str++;
    }
    while(S.top1){
        pop(S,1,x);
        deQueue(Q,y);
        if(x!=y) return 0;
    }
    return 1;
/********** end **********/
}

这就是,把字符串分别放进栈和队列里,根据栈和队列的出入特性来判断,队列或者栈空了那就是结束了.

(III)

第一关

本关任务:编写一个算法,将数组A中的n个元素A[0]至A[n-1]循环右移k位。要求算法时间复杂度为O(n),空间复杂度为O(1)

这一关的写出来不难,但是想出好的过程很难,这里就是对数组进行调换,因为我们发现循环之后数组分成两部分,类似于快速排序的分划结果,这个时候我们会思考可不可以用两部分颠倒的的思想来做

void reverse(ElemType a[],int s,int e)
{
	int temp;
	while(s < e)
	{
		temp = a[s];
		a[s] = a[e];
		a[e] = temp;
		s++;
		e--;
	}
	
}
void ShiftRightCircular(ElemType *A,int n,int k)
{
/************** begin *****************/
    if(k >= n)
		k = k%n;
    if(k > 0){
        reverse(A,0,n-k-1);
	reverse(A+(n-k),0,k-1);
	reverse(A,0,n-1);
    }
	if(k < 0){
        reverse(A,0,-k-1);
        reverse(A+(n+k),0,-k-1);
        reverse(A,0,n-1);
    }
/**************  end  *****************/
}

第二关

矩阵加法,矩阵的形式是三元组顺序表

我先写个函数,表示矩阵的插入(往后插),接着就对A和B进行遍历,如果行列值不一样,就插入行列值较少的数,i和j是两个数据指针,指向目前遍历的位置,插入A就i后移,插入B就B往后移,以此类推(行列相等就判断相加是否为0,最后i和j都要加)

void EnterTriple(TSMatrix *Q,int row,int col,int e)
{
    Q->tu++;
    Q->data[Q->tu].i=row;
    Q->data[Q->tu].j=col;
    Q->data[Q->tu].e=e;
}
TSMatrix ADD(TSMatrix A,TSMatrix B)
//返回矩阵A、B相加的结果
{
/************** begin *****************/
    TSMatrix C;
    for(int i=0;i<MAXSIZE+1;i++) {
        C.data[i].i=0;
        C.data[i].j=0;
        C.data[i].e=0;
    }
    C.tu=1;
    C.nu=A.nu;
    C.mu=A.mu;
    int i=1,j=1;
        while(i<=A.tu&&j<=B.tu)
        {
            if(A.data[i].i<B.data[j].i)
            {
                EnterTriple(&C,A.data[i].i,A.data[i].j,A.data[i].e);
                i++;
            }
            else if(A.data[i].i==B.data[j].i)
            {
                if(A.data[i].j<B.data[j].j)
                {
                    EnterTriple(&C,A.data[i].i,A.data[i].j,A.data[i].e);
                    i++;
                }
                else if(A.data[i].j>B.data[j].j)
                {
                    EnterTriple(&C,B.data[j].i,B.data[j].j,B.data[j].e);
                    j++;
                }
                else
                {
                    if(B.data[j].e+A.data[i].e!=0)
                        EnterTriple(&C,B.data[j].i,B.data[j].j,B.data[j].e+A.data[i].e);
                    i++;
                    j++;
                }
            }
            else
            {
                EnterTriple(&C,B.data[j].i,B.data[j].j,B.data[j].e);
                j++;
            }
        }
        while(i<=A.tu)
        {
            EnterTriple(&C,A.data[i].i,A.data[i].j,A.data[i].e);
            i++;
        }
        while(j<=B.tu)
        {
            EnterTriple(&C,B.data[j].i,B.data[j].j,B.data[j].e);
            j++;
        }
    for(int i=0;i<C.tu;i++){
        C.data[i]=C.data[i+1];
    }
    C.tu--;
    return C;
/**************  end  *****************/
}

第三关

思想是这样的首先找到子串出现的位置,然后把子串之后的保存,经过几个操作,temp里存的是字符串后面的元素,pFound由于是指针操作,改变了原地址的值,所以说S.ch目前指向之前的元素加第二个子串,链接即可
由于main函数里面用了fget,所以说要去除回车的影响,把应有的元素设置为0

#include <string.h>
void Replace(HString &S,HString T,HString V)
//
{
/************** begin *****************/
    *(S.ch+S.length)=0;
    *(T.ch+T.length)=0;
    *(V.ch+V.length)=0;
    char *pFound=NULL;
    pFound=strstr(S.ch,T.ch);
    while(pFound){
        char temp[100]={0};
        strcpy(temp,pFound+T.length);
        strcpy(pFound,V.ch);
        strcat(S.ch,temp);
        pFound=strstr(pFound+V.length,T.ch);
    }
    S.length=strlen(S.ch);
/**************  end  *****************/
}

(IV)

二叉搜索树和排序的一些问题

第一题:判断是不是二叉排序树?

status JudgeBiTree(BiTree T)
//判断二叉树T是否为二叉排序树
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    struct BiTNode * St[100], *p;
    int top = 0; 			//置空栈
    if(T){
	    St[top++] = T;
        while(top){
	        p = St[--top]; 
            if(p->rchild != NULL){
                St[top++] = p->rchild;
                if(p->data.key>p->rchild->data.key) return NO;
            }
	        if(p->lchild != NULL){
                St[top++] = p->lchild;
                if(p->data.key<p->lchild->data.key) return NO;
            }
        }
    }
    return YES;
    /********** End **********/
}

前序遍历的非递归实现,每一次访问结点的时候就判断一下是不是满足二叉搜索树的条件,如果能成功安全退出,那就是搜索树了

第二题:线性时间复杂度的排序

想到了计数排序,开个新数组存就完事了

void sort(int a[],int n,int k)
//将a中元素递增排序
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    int c[100]={0};
    int ranked[100]={0};
    for (int i = 0; i < n ; i++){
        c[a[i]]++;
    }
    for (int i = 1; i < k+1; ++i)
        c[i] += c[i-1];
    for (int i = n-1; i >= 0; --i)
        ranked[--c[a[i]]] = a[i];
    for (int i = 0; i < n; i++){
        a[i]=ranked[i];
    }
    /********** End **********/
}

第二题:查找中位数

快速排序

void swap (int *a,int *b){
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

int partition(int L[],int low,int high)
{
	int i,num=low;
	for(i=low+1;i<=high;i++)
	{
		if(L[i]<L[low])
		{
			swap(&L[i],&L[num+1]);
			num++;
		}
	}
	swap(&L[low],&L[num]);
	return num;
}
int MidValue(int a[],int n)
//求a的中位数
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    int low=0,high=n-1,pos;
    int mid=n/2;
    while(1){
        pos=partition(a,low,high);
		if(pos==mid)
			break;
		else if(pos>mid)
			high=pos-1;
		else low=pos+1;
    }
    if(n%2) return a[mid];
    else return (a[mid]+a[mid-1])/2;
    /********** End **********/
}

如果是偶数,怎么样怎么样,如果是奇数,怎么样怎么样……


0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

隐藏

总访问量:1079495    今日访问量:278    您是今天第:278 位访问者