提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

数据结构实训作业(I)

数据结构 作业 实训
2023-06-13 09:15:43 时间

数据结构实训作业(I)

于2020年10月8日2020年10月8日由Sukuna发布

第一关

本关任务：已知顺序表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;
            }
        }
    }
}
这个是常见操作,设置双指针,适合处理有大小差别的元素,一遍遍历就可以了,通过指针的比较来判断指针移动的方向

相关文章