【PTA】数据结构第二次上机实验：2-1 逆序数据建立链表2-3 链式表的按序号查找2-4 求链式表的表长2-5 单链表逆转2-6 两个有序链表序列的合并2-7 单链表 - 20. 单值化(去重)

青旅半醒 2023-09-27 12:21 54阅读 0赞

2-1 逆序数据建立链表

分数 20

全屏浏览题目

切换布局

作者 C课程组

单位 浙江大学

本题要求实现一个函数，按输入数据的逆序建立一个链表。

#### 函数接口定义： ####

`struct ListNode *createlist();`

函数`createlist`利用`scanf`从输入中获取一系列正整数，当读到−1时表示输入结束。按输入数据的逆序建立一个链表，并返回链表头指针。链表节点结构定义如

struct ListNode *createlist(){
        int n = 0;
        struct ListNode* head = NULL;
        scanf("%d",&n);
        while(n != -1){
            struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
            node->data = n;
            node->next = head;
            head = node;
            scanf("%d",&n);
        }
        
        return head;
    }

2-2 链式表操作集

分数 20

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

本题要求实现链式表的操作集。

#### 函数接口定义： ####

`Position Find( List L, ElementType X ); List Insert( List L, ElementType X, Position P ); List Delete( List L, Position P );`

Position Find( List L, ElementType X ){
        while(L!=NULL){
            if(L->Data==X){
                return L;
            }
            L=L->Next;
        }
    return ERROR;
    }
    List Insert(List L, ElementType X, Position P) {
     struct LNode *n = (struct LNode*)malloc(sizeof(struct LNode));
    	List p1, p2;
    	p1 = p2=L;
        if (p1 == P)//在头插入 
        {
    		n->Next = p1;
    		L = n;
    		n->Data=X;
    		return L;
    	}
    	p2 = p1->Next;
    	while (p2 != NULL) //在中间插入
        {
    		if (p2 == P) {
    			n->Next = p2;
    			p1->Next = n;
    			n->Data=X;
    			return L;
    		}
    		p1 = p2;
    		p2 = p1->Next;
    
    	}
    	if (P == NULL)
        {
            p1->Next=n;
            n->Data=X;
            n->Next=NULL;
            return L;
    	}
        else {
    		printf("Wrong Position for Insertion\n");
    		return ERROR;
    	}
    }
    
    List Delete( List L, Position P ){
        List p1,p2;
        p1=L;
        p2=p1->Next;
        //删除头且头不为空
       if(P==L&&L){
           p1=p1->Next;
           free(L);
           return p1;
       }
       //删除中间
    while(p2!=NULL){
        if(p2==P){
            p1->Next=p2->Next;
            free(p2);
            return L;
        }
        else{
            p1=p2;
        }
        p2=p1->Next;
    }
    //非法位置删除，包括链表为空和不在链表中的位置
    printf("Wrong Position for Deletion\n");
    return ERROR;
    }

2-3 链式表的按序号查找

分数 10

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

本题要求实现一个函数，找到并返回链式表的第K个元素。

#### 函数接口定义： ####

`ElementType FindKth( List L, int K );`

ElementType FindKth( List L, int k ){
        if(L == NULL){
            return ERROR;
        }
        while(k != 1){
            L = L->Next;
            k--;
            if(L == NULL){
                return ERROR;
            }
        }
        
        return L->Data;
    }

2-4 求链式表的表长

分数 5

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

本题要求实现一个函数，求链式表的表长。

int Length( List L )
    {
        int size = 0;
        while(L != NULL){
            size++;
            L = L->Next;
        }
        return size;
    }

2-5 单链表逆转

分数 20

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

本题要求实现一个函数，将给定的单链表逆转。

#### 函数接口定义： ####

`List Reverse( List L );`

List Reverse( List L ){
        if(L == NULL){
            return NULL;
        }
        
        List cur = L->Next;
        L->Next = NULL;
        while(cur != NULL){
            List next = cur->Next;
            cur->Next = L;
            L = cur;
            cur = next;
        }
        return L;
    }

2-6两个有序链表序列的合并

分数 15

全屏浏览题目

切换布局

作者 DS课程组

单位 浙江大学

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

#### 函数接口定义： ####

`List Merge( List L1, List L2 );`

List Merge(List L1, List L2)
    {
        List tmp1, tmp2, L, head;			
        head = (List)malloc(sizeof(struct Node));
        L = head;				
        tmp1 = L1->Next;		
        tmp2 = L2->Next;
        while (tmp1 && tmp2) {
            if (tmp1->Data < tmp2->Data) {
                L->Next = tmp1;
                tmp1 = tmp1->Next;
            }
            else {
                L->Next = tmp2;
                tmp2 = tmp2->Next;
            }
            L = L->Next;
        }
        for (; tmp1; tmp1 = tmp1->Next, L=L->Next) L->Next = tmp1;			
        for (; tmp2; tmp2 = tmp2->Next, L=L->Next) L->Next = tmp2;
        L1->Next = NULL;		
        L2->Next = NULL;
        return head;
    }

2-7 单链表 - 20. 单值化(去重)

分数 10

全屏浏览题目

切换布局

作者 李祥

单位 湖北经济学院

请编写函数，对线性表进行单值化处理：删除表中重复的数据元素。

函数原型

`void LListUnique(LLIST *list);`

void LListUnique(LLIST *list)
    {
        LNODE *p=list->head->next;//头结点的指针域才指向第一个元素
         LNODE *pre=NULL;//被检测的元素的前驱节点
        LNODE *r,*t;//r是被检测元素，t是临时用来做为媒介删除的
        while(p)
        {
            r=p->next;
           pre=p;
            while(r)
            {
                if(LElementEq( &r->data, &p->data)==1)
                {
                    pre->next=r->next;
                    t=r;
                    r=r->next;
                    free(t); 
                    list->length--;
                }
                else
                {
                    pre=r;
                    r=r->next;
                        
                }
            }
            p=p->next;
        }
    }