一、概念
链表作为线性表的链式存储结构，将线性表L = （a0,...ai-1,ai,ai+1...an-1) 中的各元素分布在存储器的不同存储块，称为结点。结点之间通过指针建立联系
其中：data作为数据域，next作为指针域，指向ai的直接后继ai+1结点
由此也能看出，头结点的重要性，有了头结点，其他结点都很方便找出
特别地，头结点的数据域无意义，尾结点的指针域为NULL
二、结构模型
typedef int data_t;
typedef struct node{
data_t data;
struct node *next;
}LinkList,*pLinkList;
//因为动态内存方便我们按需开辟，所以我们经常使用如下方式创建结点
pLinkList p;
p = (pLinkList)malloc(sizeof(LinkList));三、链表运算操作
typedef int data_t;
typedef struct node{
data_t data;
struct node *next;
}LinkList,*pLinkList;
pLinkList list_create(void);//创建空链表
int list_tail_insert(pLinkList Head, data_t value);//尾插结点
pLinkList list_getpos(pLinkList Head, int pos);//按位置寻找结点
int list_insert_byPos(pLinkList Head, data_t value, int pos);//按位置插入结点
int list_delete_byPos(pLinkList Head, int pos);//按位置删除结点
int list_show(pLinkList Head);//打印链表
pLinkList list_free(pLinkList Head);//释放链表
int list_reverse(pLinkList Head);//链表反转
pLinkList list_FindMaxTwo(pLinkList Head);//找相邻结点数据之和最大的结点四、实现原理
4.1创建空链表
因为头结点在链表当中是非常重要的，创建一个空链表当然是围绕它来展开
- 申请空间
- 初始化
pLinkList list_create()
{
pLinkList Head;
//创建头结点并为其申请内存
Head = (pLinkList)malloc(sizeof(LinkList));
if(Head == NULL)
{
printf("list_creat:malloc failed!\n");
return NULL;
}
//初始化头结点
Head->data = 0;
Head->next = NULL;
return Head;
}4.2尾部插入结点
尾部插入实际上还是寻找尾结点（特征是指针域为空），同时插入新的结点势必需要为其分配内存+初始化
- 新建结点（申请内存）
- 初始化
- 寻找尾结点
- 插入新结点
int list_tail_insert(pLinkList Head, data_t value)
{
pLinkList new;
pLinkList Index = Head;
if(Head == NULL)
{
printf("list_tail_insert:Head is NULL!\n");
return -1;
}
//新建结点
new = (pLinkList)malloc(sizeof(LinkList));
if(new == NULL)
{
printf("list_tail_insert:malloc failed!\n");
return -1;
}
//赋值结点
new->data = value;
new->next = NULL;
//寻找尾结点
while(Index->next != NULL)
{
Index = Index->next;
}
//插入结点
Index->next = new;
return 1;
}头部插入其实很简单，新结点先指向结点0，头结点再指向新结点即可（操作顺序不可变！）
4.3按位置寻找结点
注意是线性表，L = （a0,...ai-1,ai,ai+1...an-1)。头结点就看作-1即可
- 对寻找位置进行检查
- <-1 没必要进行
- == -1 返回头结点
- 进行循环寻找，链表指针从头结点开始移动，需要移动pos+1次
//传入-1 返回头结点 传入0返回第一个结点 依次类推
pLinkList list_getpos(pLinkList Head, int pos)
{
pLinkList Index = Head;
int i;
if(Head == NULL)
{
printf("list_getpos:Head is NULL!\n");
return NULL;
}
if(pos < -1)
{
printf("list_getpos:pos is invalid!\n");
return NULL;
}
if(pos == -1)
{
return Head;
}
//因为总共需要移动pos+1次 所以从头结点开始遍历
i = -1;
while(i++ < pos)//这里pos肯定是0以上的值
{
Index = Index->next;
if(Index == NULL)//找到尾结点
{
printf("list_getpos:pos is invalid!\n");
break;
return NULL;
}
}
return Index;
}4.4按位置插入结点
按位置插入结点，是要取代原来位置的结点，势必需要先找到它的前一个结点，这里用指针pre寻找，通过4.3实现的函数获得
int list_insert_byPos(pLinkList Head, data_t value, int pos)
{
pLinkList new;
pLinkList pre = list_getpos(Head,pos-1);//插入位置的前一个结点
if(Head == NULL)
{
printf("list_insert_byPos:Head is NULL!\n");
return -1;
}
if(pre == NULL)//pos过大导致前结点都找不到 这里即使前一个结点是尾结点也没事，追加即可
{
printf("list_insert_byPos:find pre failed!\n");
return -1;
}
//创建结点
new = (pLinkList)malloc(sizeof(LinkList));
if(new == NULL)
{
printf("list_insert_byPos:malloc failed!\n");
return -1;
}
new->data = value;
//更新指向
new->next = pre->next;//新结点指向pre的下一个结点
pre->next = new; //pre指向new
return 1;
}4.5按位置删除结点
删除结点要注意的是，链表中每个结点都是使用的动态内存同时涉及指针，及时释放和赋值为空是避免野指针的好习惯！
此外，删除结点也需要找到它的前一个，因为删除的结点撤走后，不能影响其他结点的连接
int list_delete_byPos(pLinkList Head, int pos)
{
pLinkList pre = list_getpos(Head,pos-1);//插入位置的前一个结点
pLinkList delete;
if(Head == NULL)
{
printf("list_delete_byPos:Head is NULL!\n");
return -1;
}
if(pre == NULL || pre->next == NULL)//pos过大导致前结点都找不到 或者 pre是尾结点那就没必要删除了
{
printf("list_delete_byPos:delete pos is invalid!\n");
return -1;
}
//更新指向
delete = pre->next;
pre->next = delete->next; //相当于pre->next = pre->next->next 为了方便释放空间 delete保存
//再释放要删除的结点的空间
printf("delete pos:%d,delete:data:%d\n",pos,delete->data);
free(delete);
delete = NULL;
return 1;
}4.6打印链表
int list_show(pLinkList Head)
{
pLinkList Index = Head;
if(Head == NULL)
{
printf("list_show:Head is NULL!\n");
return -1;
}
//遍历链表并且打印
while(Index->next != NULL)
{
printf("%d ",Index->next->data);
Index = Index->next;
}
puts("");
return 1;
}4.7释放链表
pLinkList list_free(pLinkList Head)
{
pLinkList WaittoFree;
if(Head == NULL)
{
printf("list_free:Head is NULL!\n");
return NULL;
}
while(Head != NULL)
{
WaittoFree = Head;
Head = Head->next;//先移动头结点
free(WaittoFree);//再释放
}
return NULL;
}4.8链表反转
思路是把链表一分为二，循环把list2中的结点插入到list1中，直到遍历到list2中的尾结点
int list_reverse(pLinkList Head)
{
pLinkList list1 = Head;
pLinkList list2;
pLinkList Index;//用于执行插入
//参数检查: 链表非法或只有头结点或只有一个结点0
if(Head == NULL || Head->next == NULL || Head->next->next == NULL)
{
printf("list_reverse:Head doesn't need to be reversed!\n");
return -1;
}
//list2 接手 结点0之后的所有结点
list2 = Head->next->next;
//list1断开结点0和其他结点的连接
list1->next->next = NULL;
//遍历list2
while(list2 != NULL)
{
Index = list2;//获得list2的第一个结点
list2 = list2->next;//list2断开第一个结点
Index->next = list1->next;//list2的第一个结点指向list1的结点0
list1->next = Index;//list2的第一个结点成为list1新的结点0
}
return 1;
}4.9寻找相邻结点数据之和最大
pLinkList list_FindMaxTwo(pLinkList Head)
{
int CurMax;
pLinkList p,q;//用于在链表中前后移动
pLinkList ret;
if(Head == NULL)
{
printf("list_FindMaxTwo:Head is NULL!\n");
return NULL;
}
//只有头结点或者只有结点0
if(Head->next == NULL || Head->next->next == NULL)
{
printf("list_FindMaxTwo:list is not enough!\n");
return Head;
}
//如果只有结点0和结点1 返回结点0即可
if(Head->next->next->next == NULL)
{
return Head->next;
}
//初始化p、q、最大值
p = Head->next;//指向结点0
q = Head->next->next;//指向结点1 相当于q = p->next;
ret = p;
CurMax = p->data + q->data;
//遍历链表
while(q->next != NULL)
{
//先移动p、q再进行比较
p = p->next;
q = q->next;
if((p->data + q->data) > CurMax)
{
CurMax = p->data + q->data;
ret = p;
}
}
return ret;
}
