// 1.cpp : 定义控制台应用程序的入口点。
//
#include
"stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <
string.h>
#include <limits.h>
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
typedef struct node
{
int data;
struct node*
next;
}Link;
//链表的建立--无头结点
int create(Link* &L,
int A[],
int n)
{
//尾插法
int i =
0;
L = (Link*)malloc(
sizeof(Link));
L->data = A[
0];
L->next =
NULL;
Link* p =
L;
Link* q =
NULL;
for(i=
1;i<n;i++
)
{
q = (Link*)malloc(
sizeof(Link));
if(q==
NULL)
return 0;
q->data =
A[i];
p->next =
q;
p =
q;
}
q->next =
NULL;
return 1;
}
//遍历链表
void printLink(Link*
L)
{
if(L!=
NULL)
{
Link* p =
L;
while(p!=
NULL)
{
printf("%d ",p->
data);
p = p->
next;
}
printf("\n");
}
}
//插入---在第i个元素前插入
int Insert_Link(Link* &L,
int x,
int i)
{
if(L!=NULL && i>
0)
{
/****************************************/
//链表的查找过程，查找第i个元素
//p指向第i个元素，q指向p的前一个元素
int j =
1;
Link* p =
L;
Link* q = NULL;
//很重要
while(p!=NULL && j<
i)
{
j++
;
q =
p;
p = p->
next;
}
if(p==NULL || j>
i)
return 0;
/****************************************/
Link* T = (Link*)malloc(
sizeof(Link));
T->data =
x;
/****************************************/
//在第一个元素前的插入操作和在其他元素前的操作有区别
//（这就是为什么有些链表会建立一个不存放数据的头结点的原因）。
if(q == NULL)
//表明是在第1个元素前面进行插入的
{
T->next =
p;
L = T;
//更新链表首结点
}
else //不是在第一个元素前面插入
{
q->next =
T;
T->next =
p;
}
/****************************************/
return 1;
}
return 0;
}
//链表的删除--删除第i个元素
int delete_Link(Link* &L,
int i)
{
if(L!=NULL && i>
0)
{
Link* p =
L;
Link* q =
NULL;
int k =
1;
while(p!=NULL && k <
i)
{
q =
p;
p = p->
next;
k++
;
}
if(p==NULL || k>
i)
return 0;
if(q==NULL)
//删除的是第一个元素
{
L = p->
next;
free(p);
}
else
{
q->next = p->
next;
free(p);
}
return 1;
}
return 0;
}
int main()
{
Link* L =
NULL;
int A[] = {
1,
3,
2,
0,
9};
create(L,A,sizeof(A)/
sizeof(
int));
printf("建立单链表-------------:\n");
printLink(L);
printf("在第一个元素前插入7-------------:\n");
Insert_Link(L,7,
1);
printLink(L);
printf("删除第一个元素-------------:\n");
delete_Link(L,1);
printLink(L);
return 0;
}
原以为很简单，自己写了才知道，有很多不明白的地方，俗话说“书读百遍，其义自现”，古人诚不欺我。
要注意的地方:
1、单链表无头结点和有头结点时，其插入和删除操作中，对第一个元素的操作和其他元素的操作有区别（这也就是为什么有些书上，建立单链表时会加个头结点，因为这样，对第一个元素的操作就和其他元素的操作统一起来了。）
2、注意头指针的变化情况。
//链表的就地逆置
void reverse(Link* &
L)
{
//空表或只有一个元素
if(L==NULL || L->next==
NULL)
return;
Link* BeforeP =
NULL;
Link* P =
L;
Link* AfterP = L->
next;
while(AfterP!=
NULL)
{
P->next =
BeforeP;
BeforeP =
P;
P =
AfterP;
AfterP = AfterP->
next;
}
P->next =
BeforeP;
L =
P;
}
转载于:https://www.cnblogs.com/welsh-android-learning/p/3500486.html
