数据结构线性表之单链表（C语言）_一直一个带头结点的单链表l设计算法实现,以表中第一个元素为标准将单链表中

数据结构线性表之单链表（C语言）

C语言中链表是精华所在，最近遇到两道个人感觉不错的单链表的题，由于目前只会C,所以只能用C来做。
先放题：
1. 已知一个带头结点的单链表 L，设计算法实现：以表中第一个元素作为标准， 将单链表中所有值小于第一个元素的结点均放在第一个元素结点之前，所有值大 于第一个元素的结点均放在第一个元素结点之后（请使用函数设计）。
// 单链表中节点的结构体类型定义 …

typedef struct LNode
{
	int data; // 数据 ...
	struct LNode *next; // 链接指针 ...
}LNode, *LinkList;

LinkList L;
1
2
3
4
5
6
7

先说一下我的解题思路。
看了题目之后，我的第一反应是想到了快速排序算法，因为题目描述的操作就是排序算法进行一次的操作。但接下来我就遇到了难点，由于才疏学浅，排序算法只会数组的操作，对链表的快排还是第一次遇到，由于排序需要2个变量用于移动，而单链表中设不了前驱指针，这是一个难点。于是就得转换思路，这里我参考了一个大佬的文章。
用单链表实现快速排序

不过大佬是用java写的，但思路很有用。
没有用前驱指针，只是设了2个用于移动的指针，分别指向链表的首元节点和第二个节点，关键是保证2个指针中间的数据始终大于基准数，此处不在赘述。
下面是我写的C代码：

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode
{
    int data;       //数据域
    struct LNode *next;     //指针域
}LNode,*linklist;

linklist init()
{
    linklist head=(linklist)malloc(sizeof(LNode));
    head->next=NULL;
    return head;
}   //将链表的头节点初始化

void insert(linklist head,int newdata)
{
    linklist temp = (linklist)malloc(sizeof(LNode));
    temp->data=newdata;
    linklist p;
    p=head;
    while(p->next!=NULL)
        p=p->next;
    p->next=temp;
    temp->next=NULL;
}       //尾插法建立链表

void print(linklist head)
{
	linklist temp=head->next;
	while(temp!=NULL)
	{
		printf("%d->",temp->data);
		temp=temp->next;
	}
	printf("NULL\n");
}	    //打印链表

void Swap(int *x,int *y)
{
    int s;
    s=*x;
    *x=*y;
    *y=s;
}       //交换数值

int main(void)
{
    linklist l=init();
    int i;
    while(scanf("%d",&i)!=EOF)
    {
        insert(l,i);        //l一直是头节点，输入 回车 ctrl+z 回车 结束输入
    }
    int temp;
    temp=l->next->data;     //temp用来标记第一个元素节点的数据
    linklist p,q;
    //接下来，本题的代码实现的关键是快速排序算法！！！
    p=l->next;
    q=p->next;      //指针初始化
    while(q!=NULL)
    {
        if(q->data > temp||q->data==temp)
        {
            q=q->next;
        }
        else
        {
            p=p->next;
            Swap(&p->data,&q->data);
            q=q->next;
        }
    }
    Swap(&l->next->data,&p->data);
    print(l);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

运行截图：

接下来是第二题

// 单链表中节点的类型定义 ... 
typedef struct ListNode 
{ 
	char Data; 
	struct ListNode *next; 
}ListNode; 

// 删除单链表中 p 指针指向的节点 ... 
void DeleteListNode( ListNode *p ) 
{ 
	if ( p == NULL )
return; 
// 请补充实现下面的代码 …… 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路：这是一个无头的链表，删除中间一个指定的节点。同样的，题目已经限定了，所给函数形参只能传入待删除的节点，所以无法找到前一个节点。这时候就得转换思路，将后一个节点覆盖掉前一个节点（待删除的），从而达到和删除同样的效果。
在写删除函数时，我先是用直接删除的方法，但运行时会一直在free处出错，最后改换替换删除的方法得以解决。
还有一个重要的地方，在创建单链表时需用头插法才不会出错。若使用尾插，会在读取时出错。

#include<stdio.h>
#include<stdlib.h>

// 单链表中节点的类型定义 ...
typedef struct ListNode
{
	char data;
	struct ListNode *next;
}ListNode;

// 删除单链表中 p 指针指向的节点 ...
void DeleteListNode( ListNode *p )
{
    if(p==NULL)
        return;
    else
    {
    ListNode *cur =p;//替换删除
	cur = cur->next;
	p->data = cur->data;
	p->next = cur->next;
	free(cur);
    }

}
//无头结点尾插法建立链表，最后不会逆序输出！！！
ListNode *tailcreate()
{
    printf("输入的值为EOF(ctrl+z)时停止创建：\n");
	char temp;
	scanf("%c",&temp);
	ListNode *tail,*head,*p;
	head=(ListNode*)malloc(sizeof(ListNode));
	head->data=temp;
	head->next=NULL;
	tail=head;
	while(scanf("%c",&temp)!=EOF)	//ctrl+z即退出
	{
		p=(ListNode*)malloc(sizeof(ListNode));
		p->data=temp;
		p->next=NULL;
		tail->next=p;
		tail=p;
	}
	return head;
}
void print(ListNode *head)
{
    ListNode *temp=head;
    while(temp!=NULL)
    {
        printf("%c",temp->data);
        temp=temp->next;
    }
}

ListNode *Search(ListNode *head,char flag)
{
    ListNode *p=head;       //p用于移动找到要删除的节点
    while(p->data!=flag)
    {
        p=p->next;
        if(p==NULL)
            break;
    }
    return p;
}

int main(void)
{
    ListNode *head;
    head=(ListNode*)malloc(sizeof(ListNode));
    head->next=NULL;
    head=tailcreate();
    printf("请输入要删除的字符：\n");
    char flag;
    scanf("%c",&flag);
    ListNode *ptr;       //用于接收待删除的节点的返回值
    ptr=Search(head,flag);
    DeleteListNode(ptr);
    print(head);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

运行截图：

如果笔者上述有错误，欢迎评论区指出更正！
说一些题外话，入坑csdn也有快半年了，终于鼓起勇气写一写了，这是第一篇博客，对笔者意义不同。
另外，学习要趁早，不要学笔者，平时不努力，考试二百五，哭都没地方。