头插法创建无头结点单链表

#include <iostream>
using namespace std;
 
 
/*
*writer:yaojinhui
*/
#define Eletype char
typedef struct LNode
{
	Eletype data;
	struct LNode *next;
}LNode,*Linklist;
void createList(Linklist &L)
{
	LNode *q;
	L=NULL;

	char ch;
	while(1)
	{
		cin>>ch;
		if(ch=='#')
			break;
		q=new LNode;
		q->data=ch;

		q->next=L;
		L=q;
	}
}
void print(Linklist L)
{
	LNode *p;
	p=L;
	while(p)
	{
		cout<<p->data;
		p=p->next;
	}
	cout<<endl;
}
int main() {
	Linklist L;
	createList(L);
	print(L);
	return 0;
}

已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点。回答下题
1、在P结点后插入S结点的语句序列是

s->next = p->next;//1
p->next = s;//2

如下图所示

2、在P结点前插入S结点的语句序列是
（1）循序交换数据的情况

• 先在P结点之后插入S结点
• 定义一个中间变量将S和P的数据交换

s->next = p->next;
p->next = s;
ElemType tmp = s->data;
s->data = p->data;
p->data = tmp;

（2）不允许交换数据
单链表不能回退，不能获取到P之前的结点，但是我们又得找到P结点之前的结点

Q = P;
P = L;
while(P->next != Q)
{
	P = P->next;
}
	s->next = Q;//s->next = p->next
	P->next = s;

如下图所示：

3、在表首插入S结点的语句序列是
（1）链表中有数据时

s->next = L;
L = s;

如下图所示：

（2）链表中无数据时
通过分析，我们发现上面的代码也能处理我们边界的问题。所以链表中无数据时代码依然是

s->next = L;
L = s;

如下图所示：

4、在表尾插入S结点的语句序列是
（1）链表中有数据

P = L;
while(P->next != NULL)
{
	P = P->next;
}
s->next = P->next;
P->next = s;

如下图所示：

（2）链表中无元素时

s->next = L;
L = s;

如下图所示：

因为是无头结点单链表L，L指向第一个结点，所以在插入元素时要考虑插入位置是否在表头，如果是，则要将新结点的next指针指向第一个结点，同时将L重新指向新结点。

重点在于❗❗【指针作为参数时，如何改变它所指向的值】❗❗

在C语言中， 一般而言，在子函数内，要想改变传进来的参数（全局变量）的值，必须要用到指针。

• 比如 int a = 0，子函数应该这样写：xxxx(int *a），表示传进来的参数类型为指针类型，并且在子函数内部，单一个 （a） 表示的是 （原a）的地址，（*a）才是原来的（a），❗（*a）才等于0，要想改变（原a） 的值，对 （*a）❗重新赋值即可。（注意区分：①&为取址运算符，②为指针类型标识符。）

• 对于指针同理，这里以指向链表第一个结点的指针L为例。当新元素插入位置位于链表开头时，需要将指针L重新指向新结点，即需要改变L所指向的值。L原本就是一个指针，对指针取值，子函数参数里要写成 **L，这里L是LinkList类型的指针变量，所以在参数里写成（*L）即可。同理，在函数内部，在未改变L所指向的值时，（*L）的值才是第一个结点的地址，想改变L所指向的值，对❗（*L）重新赋值即可。

#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
#define error -1;
#define OK 1;

typedef int ElemType;
typedef int status;

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;


LinkList creat()
{//使用尾插法建表；
    LinkList L;
//    L = (LinkList)malloc(sizeof(LNode));
//    if(!L)   printf("memory malloc error!\n");
//    LinkList p = L;
    ElemType a;
    int len;
    
    printf("请输入待建表的表长：");
    scanf("%d", &len);
    if(len>1)
    {
        printf("请输入第1个元素的值:");
        scanf("%d", &a);
        L = (LinkList)malloc(sizeof(LNode));
        if(!L)   
            printf("memory malloc error!\n");
        L->data = a;
        LinkList p = L;
        
        for(int i=1; i<len; i++)
        {   
            printf("请输入第%d个元素的值:", i+1);
            scanf("%d", &a);
            p->next = (LinkList)malloc(sizeof(LNode));
            p->next->data = a;
            p = p->next;
    }
    
    p->next = NULL;
    
    return L;
    }
    
}

void print(LinkList L)
{
    LinkList p = L;
    while(p != NULL)
    {
        printf("%d\n", p->data);
        p = p->next;
    }
}

status insert(LinkList *L, int i, int b)    
{//这里形参取的是指向指针L的指针，即L的地址，*在这里表示指针类型
//因为有可能要改变指针L的值，即改变L的指向
    LinkList p = NULL;
    if (i<1)     return error;
    
    if (i == 1)
    { 
        p = (LinkList)malloc(sizeof(LNode));
        if(!p)   
            printf("memory malloc error!\n");
        p->data = b;
        p->next = *L;   //注意这里！！！*L才是原L,*的意思是【取】指针所指向的值
                        //此时L是原L的地址，想要取/改变原L的值，用*L
        *L = p;         //改变原L的指向，就用*L
        
        return OK;
    }
    else
    {
        p = (LinkList)malloc(sizeof(LNode));
        if(!p)   
            printf("memory malloc error!\n");
        p->data = b;
        
        LinkList q = *L;     //q用于查找插入位置
        LinkList qpre = NULL;   //qpre用于指向待插入位置的前一结点
        
        while(i>1)
        {
            qpre = q;
            q = q->next;
            i --;
        }//退出时，q指向待插入位置
        
        p->next = q;
        qpre->next = p;
        
        return OK;
    }
}



int main()
{
    LinkList L = creat();
    int i;
    printf("请输入待插入的位置：");
    scanf("%d", &i);
    int b;
    printf("请输入待插入的元素值：");
    scanf("%d", &b);
    
    insert(&L, i, b);       
//！！&取地址符，要将指针L的地址作为参数传进去，因为L所指向的值可能会发生改变
    
    print(L);
    
    return 0;
}