7-5 单向链表的创建与输出
本题目要求补充两个函数，实现如下功能：
输入若干个正整数，以-1结束，采取向链表中添加节点的方式来
建立
一个单链表，并
输出
这个单链表。
输入格式:
从键盘输入若干个正整数（空格分隔），以-1结束。
输出格式:
依次输出单链表中各个节点的数据元素值，元素间以逗号分隔。如果链表为空，则输出NULL。参看输出样例。
输入样例:
1 3 5 7 9 -1结尾无空行
输出样例:
1,3,5,7,9结尾无空行
-
输入样例:
-1结尾无空行
输出样例:
NULL结尾无空行
这个题就是一个简单的链表题，设置可以用数组的思想去理解这个（虽然这么说不太准确），这个是由多个结构体指针将结构题链接起来，结构体中存有值。
data | 0x00002 data | 0x00003 data | 0x00004 data | NULL
0x00009 0x00002 0x00003 0x00004
就是以这种方式连接，最后一个指向空指针。
以这个题来看，我们要先知道我们存了多少个数在链表中，所以我们用一个count来当计数器，
然后我们每从键盘输入一个值的时候，我们都要去判断一下，这个值是否不为-1，不为-1我们就存进去，否则就不存进链表并结束储存。
所以，我们代码可以如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
typedef struct sn
{
int data;
struct sn* next;
}SN;
int main()
{
int n;
SN* head, * r, * p;
head = (SN*)malloc(sizeof(SN));
r = p = head;
int count = 0;
while (1)
{
scanf("%d", &n);
if (n == -1)
{
break;
}
else
{
p = (SN*)malloc(sizeof(SN));
p->data = n;
r->next = p;
r = p;
count++;
}
}
r->next = NULL;
p = head->next;
int i = 0;
if (count == 0)
{
printf("NULL");
}
else
{
for (i = 0; i < count; i++)
{
printf("%d", p->data);
if (i < count - 1) printf(",");
p = p->next;
}
}
return 0;
}
那我们如何逆序输出链表？
思路：1、我们可以用for循环的内嵌去实现，第一次去找最后一个结构体指针中存的数，第二次去找倒数第二个结构体中的数，以此类推。
假设第一次找n次，那么第二次找n-1次，第三次找n-3次，第m次找n-m次。
2、我们可以使用尾删法，每输出下一个结构体指针指向NULL的那个结构体就对这个进行free（）
，然后将倒数第二个的下一个指针赋为NULL，即让倒数第二个结构体成为链尾。
这次我们以第一种方法实现，以下面题目为例：
7-7 链表的逆置
输入若干个不超过100的整数，建立单链表，然后将链表中所有结点的链接方向逆置，要求仍利用原表的存储空间。输出逆置后的单链表。
输入格式:
首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据在一行上输入数据个数n及n个不超过100的整数。
输出格式:
对于每组测试，输出逆置后的单链表，每两个数据之间留一个空格。
输入样例:
1
11 55 50 45 40 35 30 25 20 15 10 5
输出样例:
5 10 15 20 25 30 35 40 45 50 55#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
typedef struct sn
{
int data;
struct sn* next;
}SN;
int main()
{
int n;
scanf("%d", &n);
int m;
int a;
while (n--)
{
scanf("%d", &m);
SN* head, * r, * p;
head = (SN*)malloc(sizeof(SN));
r = p = head;
int h = m;
while (m--)
{
scanf("%d", &a);
p = (SN*)malloc(sizeof(SN));
p->data = a;
r->next = p;
r = p;
}
r->next = NULL;
p = head->next;
int i = 0, j = 0;
for (i = 0; i < h; i++)
{
p = head;
for (j = 0; j < h - i; j++)
{
p = p->next;
}
printf("%d", p->data);
if (i < h - 1) printf(" ");
}
printf("\n");
}
return 0;
}
尾删法
上面讲到了尾删法，现在我们就来实现一下尾删的思路：
尾删的思路刚刚已将，但是尾删的细节需要注意：
1、最后一个是否为空（即：是否没有可以删的），
如果为空，我们就不删了（因为没得删了，咋总不能无中生有去删吧）；
2、第一个指向的下一个结构体类型是否为空；
如果为空，我们就删第一个并且给一个赋为NULL（不然就成为野指针了，兄der）；
注意这两个点就好实现了，我以函数的形式写了给代码块
//这是我平时学习的时候喜欢用函数去写
void TestSList()
{
SN* plist = NULL;
//SListPushBack(&plist, 1);//这个是尾插法。
//SListPushBack(&plist, 2);
//SListPushBack(&plist, 3);
//SListPushBack(&plist, 4);
//SListPushBack(&plist, 5);
//SListPushFront(&plist, 6);
//SListPopFront(&plist);
SListPopBack(&plist);//这个就是尾删
SListPrint(plist);//这个是打印函数
}
//这个是尾删代码实现
void SListPopBack(SN** pphead)
{
if (*pphead == NULL)
{
return;
}
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SN* prev = *pphead;
SN* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
还有一个题目
7-3 链表倒数n个结点的乘积
本题要求计算单链表倒数n个结点的乘积。例如，给出单链表1 2 3 4 5，则倒数2个结点的乘积为20。
输入格式:
输入有2行，第一个行为2个非负整数m和n。其中m为链表结点个数，n为链表倒数结点的数量。题目保证计算结果在int范围内。 第二行为链表的m个数，以空格分隔。
输出格式:
在一行中输出倒数n个结点的乘积。
输入样例:
5 2
1 2 3 4 5结尾无空行
输出样例:
20结尾无空行
样例解释：
20 = 4 * 5
这个题的思路其实也和刚刚那些差不多，都很基础入门的，没难度，这是换一种思考方式而已。
对于这个题不用头铁，总想着从最后往前去找，这个不是数组，你必须要从前往后找，还得要一个一个来，心也急不得。
假如有5个数，要你求最后2个数的乘积的话，其实就是从正数第四个乘整数第五个，即
1 3 3 9 5
这组数中，我们其实只要先把结构体类型的指针之到9这里，然后再开始边乘边往后走，对不对。
也就是说先跑到（1 3
3
9 5）这个红色3这个里，我们也即是跑了5-2次。
然后其他地方的代码实现就简单起来了。
你不会以为到这里就完了吧，其实还有坑，即输入的n为0，所以我们还要去判断n是否为0
。
那么：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
typedef struct sn
{
int data;
struct sn* next;
}SN;
int main()
{
int n, a, m;
scanf("%d%d", &n, &m);
int h = n;
SN* prve, * r;
SN* head = (SN*)malloc(sizeof(SN));
prve = r = head;
while (n--)
{
scanf("%d", &a);
prve = (SN*)malloc(sizeof(SN));
prve->data = a;
r->next = prve;
r = prve;
}
r->next = NULL;
prve = head->next;
int i = 0;
for (i = 0; i < h-m; i++)
{
prve = prve->next;
}
int sum = 1;
if (m == 0)
{
printf("0");
}
else
{
while ((prve) != NULL)
{
sum = sum * (prve->data);
prve = prve->next;
}
printf("%d", sum);
}
return 0;
}前面我们提了一下尾删，这里有一个入门点的题
7-10 顺序表（删除）
已知一组数据，采用顺序存储结构存储，其中所有的元素为整数。设计一个算法，删除元素值在[x,y]之间的所有元素
输入格式:
输入包含三行数据，第一行是表中元素个数，第二行是顺序表的各个元素，第三行是区间x和y。
输出格式:
删除元素值在[x,y]之间的所有元素后，输出新的顺序表。(最后无空格)
输入样例:
在这里给出一组输入。例如：
10
55 11 9 15 67 12 18 33 6 22
10 20结尾无空行
输出样例:
在这里给出相应的输出。例如：
55 9 67 33 6 22结尾无空行
其实这个思路很简单，一个一个去比，看看是否在范围内，是就输出，不是就不输出。
但是有一个容易出bug的地方，就是空格的问题。空格最后一个容易多打。
如果你觉得可以用:
for(int i=0;i<n;i++)
{ if(i<n-1) printf(” “);}
来解决的话，你就天真了。
这样可能两个数之间出现多个空格，或者最后多个空格的情况。
如果你想在if（）里面再多加一个范围限定的话，你也天真了，假如最后有多个不在范围的，那是不是又多打空格了呢！？
这里，我想到的解决办法就是用一个计数器count来记录有多少个符合范围的数，符合就count++，然后再从头往后找，找到一个符合的就用一个新的cnt计数器++，如果cnt<count-1就打印空格即可。
代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
typedef struct sn
{
int data;
struct sn* next;
}SN;
int main()
{
int n;
scanf("%d", &n);
int h = n;
int a;
SN* head, * r, * p;
head = (SN*)malloc(sizeof(SN));
r = p = head;
while (n--)
{
scanf("%d", &a);
p = (SN*)malloc(sizeof(SN));
p->data = a;
r->next = p;
r = p;
}
int o, z;
scanf("%d%d", &o, &z);
r->next = NULL;
p = head;
int i = 0;
int count = 0;
for (i = 0; i < h; i++)
{
p = p->next;
if ((p->data) < o || (p->data) > z)
{
count++;
}
}
int l = count;
count = 0;
p = head;
for (i = 0; i < h; i++)
{
p = p->next;
if ((p->data) < o || (p->data) > z)
{
count++;
printf("%d", p->data);
if (count < l)
{
printf(" ");
}
}
}
return 0;
}