## 此文章仅用来记录🍎🍚的做题笔记，起备忘作用。
（如有路人看到并认为有用，这边建议点赞呢。
如果您觉得这个人菜的一，可以提出不当之处，我会诚恳地改正。）
6-1 单链表逆转 (20分)
本题要求实现一个函数，将给定的单链表逆转。 裁判测试程序样例： #include #include
typedef int ElementType; typedef struct Node *PtrToNode; struct Node { ElementType Data; PtrToNode Next; }; typedef PtrToNode List;
List Read(); /* 细节在此不表 / void Print( List L ); / 细节在此不表 */
List Reverse( List L );
int main() { List L1, L2; L1 = Read(); L2 = Reverse(L1); Print(L1); Print(L2); return 0; }
/* 你的代码将被嵌在这里 */ 输入样例： 5 1 3 4 5 2 输出样例： 1 2 5 4 3 1
全部代码
//以下是调试代码：
#include
#include
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表 */
List Reverse( List L );
int main()
{
List L1, L2;
L1 = Read();
L2 = Reverse(L1);
Print(L1);
Print(L2);
return 0;
}
List Read()
{
int n,i;
scanf("%d",&n);
struct Node *head=NULL,*s,*r=NULL;
head=(List)malloc(sizeof(struct Node));
if(head==NULL)
{
exit(1);
}
r=head;
s=(List)malloc(sizeof(struct Node));
if(s==NULL)
{
exit(1);
}
for(i=0;iData);
if(s==NULL)
{
exit(1);
}
r->Next=s;
r=r->Next;
}
r->Next=NULL;
return head->Next;//返回的是一个不带头结点的链表
}
void Print( List L )//输出不带头结点的链表
{
struct Node *p;
p=L;
while(p)
{
printf("%d ",p->Data);
p=p->Next;
}
printf("\n");
}
*逆转函数*
List Reverse( List L )
{
if(!L)
return L;
List p=NULL;
List ptemp=NULL;
//p:新链表，ptemp：记住位置，工具人。
//逆置：用一个临时结点，记住L指的结点。然后把L这个结点掰出去，放到另一个链表，相当于头插法。
while(L)
{
ptemp=L->Next; //ptemp记住L的下一个结点。
L->Next=p; //L指向p（新链表的头结点，初始为空）
p=L; //L指谁p就指谁，所以原L变成P（新链表的表头）。
L=ptemp; //ptemp指谁L就指谁，原L的下一个结点作为新的头再次循环。
//如此循环，直到把整个链表逆转。
}
return p ;
}
哇这图大的一。首先，让ptemp（工具人指针）指向L->next，即记录L的下一个结点。
然后让L指向p（p为新链表的表头，初始为NULL）。那么就是L->next是NULL。接下来我们只需要把L赋值为p，那么p就指向了原本链表的第一个结点代表的内容，且next域为NULL。简而言之，就是p就是从原链表中掰出来的第一个结点。之后再循环再循环，p就指向原链表的第二个结点，且其next域是以前的p（即原链表的第一个结点），一直到原链表的最后一个元素，新的逆转的链表就得到了。 
这里，为了循环的继续进行。要把ptemp赋值给L，即ptemp指谁、L就指谁。这样L就指向了原来链表的第二个结点，下次循环就把L也就是第二个结点掰出去放到新链表。
6-5 链式表操作集 (20分)
本题要求实现链式表的操作集。
对于链表的操作，都是基操，但是一些特殊情况经常忘，有时候遍历还会忘了往后指。
还是不熟练阿，还需多加练习。
函数接口定义： Position Find( List L, ElementType X ); List Insert( List L, ElementType X, Position P ); List Delete( List L, Position P ); 其中List结构定义如下：
typedef struct LNode *PtrToLNode; struct LNode { ElementType Data; PtrToLNode Next; }; typedef PtrToLNode Position; typedef PtrToLNode List; 各个操作函数的定义为：
Position Find( List L, ElementType X )：返回线性表中首次出现X的位置。若找不到则返回ERROR；
List Insert( List L, ElementType X, Position P )：将X插入在位置P指向的结点之前，返回链表的表头。如果参数P指向非法位置，则打印“Wrong Position for Insertion”，返回ERROR；
List Delete( List L, Position P )：将位置P的元素删除并返回链表的表头。若参数P指向非法位置，则打印“Wrong Position for Deletion”并返回ERROR。
裁判测试程序样例：
#include
#include
#define ERROR NULL
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
Position Find( List L, ElementType X );
List Insert( List L, ElementType X, Position P );
List Delete( List L, Position P );
int main()
{
List L;
ElementType X;
Position P, tmp;
int N;
L = NULL;
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
L = Insert(L, X, L);
if ( L==ERROR ) printf("Wrong Answer\n");
}
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
P = Find(L, X);
if ( P == ERROR )
printf("Finding Error: %d is not in.\n", X);
else {
L = Delete(L, P);
printf("%d is found and deleted.\n", X);
if ( L==ERROR )
printf("Wrong Answer or Empty List.\n");
}
}
L = Insert(L, X, NULL);
if ( L==ERROR ) printf("Wrong Answer\n");
else
printf("%d is inserted as the last element.\n", X);
P = (Position)malloc(sizeof(struct LNode));
tmp = Insert(L, X, P);
if ( tmp!=ERROR ) printf("Wrong Answer\n");
tmp = Delete(L, P);
if ( tmp!=ERROR ) printf("Wrong Answer\n");
for ( P=L; P; P = P->Next ) printf("%d ", P->Data);
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例： 6 12 2 4 87 10 2 4 2 12 87 5 输出样例： 2 is found and deleted. 12 is found and deleted. 87 is found and deleted. Finding Error: 5 is not in. 5 is inserted as the last element. Wrong Position for Insertion Wrong Position for Deletion 10 4 2 5
/* 你的代码将不会被嵌在这里 */
Position Find( List L, ElementType X )
{
List head=L;
while(head)
{
if(head->Data==X)
{
return head;
}
head = head->Next;
}
return ERROR;
}
List CreatCode(ElementType X) //强哥之加函数
{
List t=(List)malloc(sizeof(struct LNode));
t->Data = X;
t->Next = NULL;
return t;
}
List Insert( List L, ElementType X, Position P )
{
List ptemp = CreatCode(X);
if(L==P) //插入到表头
{
ptemp->Next=L;
L = ptemp;
return L;
}
else //插入到中间位置
{
List head = L;
while(head)
{
if(head->Next==P)
{
ptemp->Next = P; //先栓新绳
head->Next = ptemp; //后栓旧绳
return L;
}
head=head->Next;
}
}
printf("Wrong Position for Insertion\n");
return ERROR;
}
List Delete( List L, Position P )
{
List head = L;
if(L==P) //删除表头结点
{
L = L->Next;
free(P);
return L;
}
else //删除中间结点
{
while(head)
{
if(head->Next==P)
{
head->Next =P->Next;
free(P);
return L;
}
head=head->Next;
}
}
printf("Wrong Position for Deletion\n");
return ERROR;
}
6-6 带头结点的链式表操作集 (20分)
本题要求实现带头结点的链式表操作集。
本题与上一题的差别在于这次有空头，就因为有空头，这两个函数测试了好多次。
我认为我lao的一，有时间就写一下注释，没时间就不写了。
函数接口定义： List MakeEmpty(); Position Find( List L, ElementType X ); bool Insert( List L, ElementType X, Position P ); bool Delete( List L, Position P ); 其中List结构定义如下：
typedef struct LNode *PtrToLNode; struct LNode { ElementType Data; PtrToLNode Next; }; typedef PtrToLNode Position; typedef PtrToLNode List; 各个操作函数的定义为：
List MakeEmpty()：创建并返回一个空的线性表；
Position Find( List L, ElementType X )：返回线性表中X的位置。若找不到则返回ERROR；
bool Insert( List L, ElementType X, Position P )：将X插入在位置P指向的结点之前，返回true。如果参数P指向非法位置，则打印“Wrong Position for Insertion”，返回false；
bool Delete( List L, Position P )：将位置P的元素删除并返回true。若参数P指向非法位置，则打印“Wrong Position for Deletion”并返回false。
裁判测试程序样例：
#include
#include
#define ERROR NULL
typedef enum {false, true} bool;
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
List MakeEmpty();
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );
int main()
{
List L;
ElementType X;
Position P;
int N;
bool flag;
L = MakeEmpty();
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
flag = Insert(L, X, L->Next);
if ( flag==false ) printf("Wrong Answer\n");
}
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
P = Find(L, X);
if ( P == ERROR )
printf("Finding Error: %d is not in.\n", X);
else {
flag = Delete(L, P);
printf("%d is found and deleted.\n", X);
if ( flag==false )
printf("Wrong Answer.\n");
}
}
flag = Insert(L, X, NULL);
if ( flag==false ) printf("Wrong Answer\n");
else
printf("%d is inserted as the last element.\n", X);
P = (Position)malloc(sizeof(struct LNode));
flag = Insert(L, X, P);
if ( flag==true ) printf("Wrong Answer\n");
flag = Delete(L, P);
if ( flag==true ) printf("Wrong Answer\n");
for ( P=L->Next; P; P = P->Next ) printf("%d ", P->Data);
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例： 6 12 2 4 87 10 2 4 2 12 87 5 输出样例： 2 is found and deleted. 12 is found and deleted. 87 is found and deleted. Finding Error: 5 is not in. 5 is inserted as the last element. Wrong Position for Insertion Wrong Position for Deletion 10 4 2 5
//你的代码不会镶嵌在这里
List MakeEmpty() //空表
{
List t = (List ) malloc(sizeof(struct LNode));
t->Next = NULL;
return t;
}
Position Find( List L, ElementType X )
{
L=L->Next; //有空投
if(L==NULL)
{
return ERROR;
}
else
{
List head = L; //要返回表头，用另一个变量去遍历。
while(head)
{
if(head->Data == X)
{
return head;
}
head = head->Next;
}
return ERROR;
}
}
List CreatCode(ElementType X) //强哥之加函数
{
List t=(List)malloc(sizeof(struct LNode));
t->Data = X;
t->Next = NULL;
return t;
}
bool Insert( List L, ElementType X, Position P )
{
List ptemp = CreatCode(X);
if(P==NULL) //特例，如果P是NULL，而链表尾的next域为NULL，所以插入到表尾。
{
while(L->Next)
{
L=L->Next;
}
L->Next = ptemp;
return true;
}
else if(L->Next==NULL) //空表
{
return false;
}
else //注意用L->next遍历,插入到P之前，即L->next的内容为P。
{
while(L->Next)
{
if(L->Next==P)
{
ptemp->Next = P;
L->Next = ptemp;
return true;
}
L=L->Next;
}
}
printf("Wrong Position for Insertion\n");
return false;
}
bool Delete( List L, Position P )
{
if(L->Next==NULL) //空表
{
return false;
}
while(L->Next)
{
if(L->Next==P)
{
L->Next=P->Next; //跨过删除元素。
free(P); //释放内存
return true;
}
L=L->Next;
}
printf("Wrong Position for Deletion\n");
return false;
}
