C语言单链表去重,C语言字符串逆置

悠悠 2024-03-26 07:17 42阅读 0赞

## C语言单链表去重 ##

已知单链表的结点结构定义如下：

typedef struct _NODE_
    {
        
        int data;
        struct _NODE_ *next;
    } NODE;

说明：data 为数据域。next 为指针域，指示后继结点。

请编写函数，删除带附加头结点的单链表中重复的数据结点。

函数原型  
void Unique(NODE \*head);  
说明：参数 head 为单链表的头指针，函数将对单链表作去重处理：每个数据结点只保留第 1 个，后面与之重复的数据结点都被删去。

裁判程序

int main()
    {
        
        NODE *h;
        Create(&h);
        Input(h);
        Unique(h);
        Output(h);
        putchar('\n');
        Destroy(&h);
        return 0;
    }

说明：Create 函数用于创建链表，Destroy 函数用于销毁链表。Input 函数用于输入链表：首先输入结点数，然后输入这些数据元素。Output 函数用于输出单链表，数据元素之间以空格间隔。

输入样例

16
    28 47 52 28 36 47 52 47 28 28 95 47 36 28 47 95

输出样例

28 47 52 36 95

要求：时间复杂度为 O(n 2 )，空间复杂度为 O(1)。

提交代码：  
算法思路：  
首先是默认链表的默认节点是不重复的，然后以第一个节点为开头，然后一个个的往后走，如果后一个节点的值与当前的值相同了，那么就把当前节点的前一个节点的指针指向当前节点的后一个节点，然后再把当前节点给释放掉，这样就完成了，这个链表的去重了。

需要注意的是，在原来的链表的基础之上还需要创建两个新节点，便于进行操作。

void Unique(NODE *head)
    {
        
    	NODE *p = head->next, *q, *s;
    	while(p)
    	{
        
    		s = p;
    		q = p->next;  // 默认第一个不重复
    		while (q)
    		{
        
    			if (p->data == q->data)
    			{
        
    				s->next = q->next;
    				q->next = NULL;
    				free(q);
    			}
    			else
    			{
        
    				s = s->next;
    			}
    			q = s->next;
    		}
    		p = p->next;
    	}
    }

## C语言字符串逆置 ##

请编写函数，将字符串逆置。

函数原型  
`char* StrReverse(char *str);`  
说明：str 为字符串起始地址。函数将字符串内容逆置，函数值为 str。

裁判程序

#include <stdio.h>
    
    void ChrSwap(char *x, char *y);
    char* StrReverse(char *str);
    
    int main()
    {
        char a[1024];
        gets(a);
        StrReverse(a);
        puts(a);
        return 0;
    }

…

/\* 你的代码将被嵌在这里 \*/  
说明：ChrSwap 函数用于交换两个字符。

输入样例  
`roma`  
输出样例  
`amor`

**提交代码**  
算法思路：该算法的思路为使用二分交换的方法，以中间的那个字符的索引为标记，然后左右两边的互相交换。

char* StrReverse(char *str)
    {
        
        int i = 0;
        int cnt = 0;
        while(str[i++] != '\0')
        {
        
            cnt++;
        }
        int m = cnt / 2;
        for(int i = 0;i < m; i++)
        {
        
            ChrSwap(&(str[i]), &(str[cnt - 1 - i]));
        }
        return str;
    }