一、简介
手写链表实现以下功能
- 尾插
- 获取指定下标的元素
- 按照指定位置插入元素
- 打印链表内容
- 删除指定元素
- 释放整个链表
- 链表反转
- 链表中相邻元素的和最大的两个元素的第一个节点,且返回和的最大值
二、源代码
LinkedList.h
#ifndef _LINKEDLIST_H
#define _LINKEDLIST_H
#include <stdio.h>
// define a struct node
typedef int dataType;
typedef struct node
{
dataType data;
struct node *next;
} linkedlist, *pLinkedlist;
// fuctions
pLinkedlist ListCreate();
int ListTailInsert(pLinkedlist list, dataType value); // head
pLinkedlist ListGet(pLinkedlist list, int pos);
int ListInsert(pLinkedlist list, dataType value, int pos);
int ListShow(pLinkedlist list);
int ListElementDelete(pLinkedlist list, int pos);
pLinkedlist ListFree(pLinkedlist list);
int ListReverse(pLinkedlist list);
pLinkedlist ListAdjMax(pLinkedlist list, dataType *value);
#endif
LinkedList.c
#include <stdlib.h>
#include "LinkedList.h"
#include <errno.h>
/**
* @brief create a linked list
*
* @return pLinkedlist: Address of the head node
*/
pLinkedlist ListCreate()
{
pLinkedlist list = (pLinkedlist)malloc(sizeof(linkedlist));
if (list == NULL)
{
printf("malloc error\n");
return NULL;
}
list->data = 0;
list->next = NULL;
return list;
}
int ListTailInsert(pLinkedlist list, dataType value)
{
if (list == NULL)
{
printf("TailInsert error:arg list is invalid\n");
return -1;
}
// Apply for a new space
pLinkedlist newNode = (pLinkedlist)malloc(sizeof(linkedlist));
if (newNode == NULL)
{
printf("malloc error\n");
return -1;
}
// update value
newNode->data = value;
newNode->next = NULL;
// Find the last element of the old linked list
pLinkedlist p = list;
while (p->next)
{
p = p->next;
}
// update list
p->next = newNode;
return 0;
}
/**
* @brief Gets the address of the element at the specified location
*
* @param list
* @param pos
* @return pLinkedlist
*/
pLinkedlist ListGet(pLinkedlist list, int pos)
{
if (list == NULL)
{
printf("ListGet error:arg list is invalid\n");
return NULL;
}
if (pos == -1)
{
return list;
}
pLinkedlist p = list;
for (int i = 0; i < pos + 1; i++)
{
p = p->next;
if (p == NULL)
{
printf("pos is invalid\n");
return NULL;
}
}
return p;
}
/**
* @brief Insert an element into the specified position
*
* @param list
* @param value
* @param pos
* @return int 0:success -1:failed
*/
int ListInsert(pLinkedlist list, dataType value, int pos)
{
if (list == NULL)
{
printf("ListInsert error:arg list is invalid\n");
return -1;
}
// Apply for a new space
pLinkedlist newNode = (pLinkedlist)malloc(sizeof(linkedlist));
if (newNode == NULL)
{
printf("malloc error\n");
return -1;
}
// update value
newNode->data = value;
newNode->next = NULL;
// Find the location to be inserted
pLinkedlist lastNode = ListGet(list, pos - 1);
if (lastNode == NULL)
{
printf("Insert an invalid position\n");
return -1;
}
// Complete insertion operation
newNode->next = lastNode->next;
lastNode->next = newNode;
return 0;
}
int ListShow(pLinkedlist list)
{
if (list == NULL)
{
printf("ListShow error:arg list is invalid\n");
return -1;
}
pLinkedlist p = list;
while (p->next)
{
p = p->next;
printf("%d ", p->data);
}
printf("\n");
return 0;
}
int ListElementDelete(pLinkedlist list, int pos)
{
if (list == NULL)
{
perror("(ListElementDelete) invalid arg list");
return -1;
}
if (pos < 0)
{
perror("(ListElementDelete) invalid arg pos");
return -1;
}
// Find the element at the current position
pLinkedlist p = ListGet(list, pos);
if (p == NULL)
{
perror("(ListElementDelete) invalid arg pos");
return -1;
}
// Find the previous element of the element at the current position
pLinkedlist q = ListGet(list, pos - 1);
q->next = p->next;
free(p);
p = NULL;
return 0;
}
pLinkedlist ListFree(pLinkedlist list)
{
if (list == NULL)
{
printf("ListFree error:arg list is invalid\n");
return list;
}
pLinkedlist p = list;
while (list != NULL)
{
p = list;
list = list->next;
free(p);
}
p = NULL;
return NULL;
}
int ListReverse(pLinkedlist list)
{
pLinkedlist p, q;
if (list == NULL)
{
printf("ListReverse: arg is invalid.\n");
return -1;
}
if (list->next == NULL || list->next->next == NULL)
{
return 0;
}
p = list->next->next;
list->next->next = NULL;
while (p != NULL)
{
q = p;
p = p->next;
q->next = list->next;
list->next = q;
}
return 0;
}
/**
* @brief Find the first node with the largest sum of two adjacent elements in the entire linked list
*
* @param list
* @param value sum
* @return pLinkedlist
*/
pLinkedlist ListAdjMax(pLinkedlist list, dataType *value)
{
int sum = 0;
pLinkedlist p, q, r;
if (list == NULL)
{
printf("ListAdjMax: arg list is invalid.\n");
return NULL;
}
if (list->next == NULL || list->next->next == NULL || list->next->next->next == NULL)
{
return list;
}
p = list->next;
q = list->next->next;
sum = p->data + q->data;
r = p;
while (q->next != NULL)
{
p = p->next;
q = q->next;
if (sum < (p->data + q->data))
{
r = p;
sum = p->data + q->data;
}
}
*value = sum;
return r;
}
main.c
#include <stdio.h>
#include "LinkedList.h"
void test_insert();
void test_ListGet();
void test_ListInsert();
void test_ListElementDelete();
void test_ListFree();
void test_ListReverse();
void test_ListAdjMax();
int main(int argc, char const *argv[])
{
// test_insert();
// test_ListGet();
// test_ListInsert();
// test_ListElementDelete();
// test_ListFree();
// test_ListReverse();
test_ListAdjMax();
return 0;
}
void test_insert()
{
pLinkedlist list = ListCreate();
ListTailInsert(list, 10);
ListTailInsert(list, 20);
ListTailInsert(list, 30);
ListTailInsert(list, 40);
ListTailInsert(list, 50);
ListShow(list);
}
void test_ListGet()
{
pLinkedlist list = ListCreate();
ListTailInsert(list, 10);
ListTailInsert(list, 20);
ListTailInsert(list, 30);
ListTailInsert(list, 40);
ListTailInsert(list, 50);
ListShow(list);
for (int i = 0; i < 5; i++)
{
printf("list[%d] = %d\n", i, (ListGet(list, i))->data);
}
}
void test_ListInsert()
{
pLinkedlist list = ListCreate();
ListTailInsert(list, 10);
ListTailInsert(list, 20);
ListTailInsert(list, 30);
ListTailInsert(list, 40);
ListTailInsert(list, 50);
ListShow(list);
printf("-------------------\n");
ListInsert(list, 200, 1);
ListShow(list);
}
void test_ListElementDelete()
{
pLinkedlist list = ListCreate();
ListTailInsert(list, 10);
ListTailInsert(list, 20);
ListTailInsert(list, 30);
ListTailInsert(list, 40);
ListTailInsert(list, 50);
ListShow(list);
printf("-------------------\n");
ListElementDelete(list, 4);
ListShow(list);
}
void test_ListFree()
{
pLinkedlist list = ListCreate();
ListTailInsert(list, 10);
ListTailInsert(list, 20);
ListTailInsert(list, 30);
ListTailInsert(list, 40);
ListTailInsert(list, 50);
ListShow(list);
list = ListFree(list);
ListTailInsert(list, 50);
ListShow(list);
}
void test_ListReverse()
{
pLinkedlist list = ListCreate();
ListTailInsert(list, 10);
ListTailInsert(list, 20);
ListTailInsert(list, 30);
ListTailInsert(list, 40);
ListTailInsert(list, 50);
ListShow(list);
printf("-------------------\n");
ListReverse(list);
ListShow(list);
}
void test_ListAdjMax()
{
int max = 0;
pLinkedlist list = ListCreate();
ListTailInsert(list, 10);
ListTailInsert(list, 20);
ListTailInsert(list, 30);
ListTailInsert(list, 40);
ListTailInsert(list, 50);
ListShow(list);
pLinkedlist p = ListAdjMax(list, &max);
printf("p->data = %d,max = %d", p->data, max);
}
总结
未实现的接口
- 合并两个链表
- 求两个链表的并集
- 元素排序
- 消除链表中的相同元素