05. C Pro 摘录的链表基本操作
原文引用：https://blog.csdn.net/qq_42366014/article/details/105000993
#include
#include
#include
typedef struct mylist {
int v;
struct mylist *next;
}MY_LIST;
void InitList(MY_LIST **pHead);
void InsertItem(MY_LIST *pItem, int a, MY_LIST *pHead);
void PrintList(MY_LIST *pHead);
void DelItem(MY_LIST *pHead, int item);
void CleanMyList(MY_LIST *pHead);
void ReverseMyList(MY_LIST *pHead);
void SortList(MY_LIST *pHead);
MY_LIST *FindElem(MY_LIST *pHead, int a, bool pos);
//初始化一个空链表，以及一个链表头节点（非元节点）
void InitList(MY_LIST **pHead) {
*pHead = (MY_LIST *)malloc(sizeof(MY_LIST));
if (NULL == *pHead) {
printf("pHead Failed!\n");
exit(1);
}
(*pHead)->next = NULL;
return;
}
//链表的遍历
void PrintList(MY_LIST *pHead) {
if (pHead->next == NULL) {
printf("Empty List!\n");
return;
}
MY_LIST *temp = pHead->next; //这个才是：元节点
while (temp) {
printf("***Current Item is %d***\n", temp->v);
temp = temp->next;
}
}
//查找给定元素的节点信息:pos 标记返回当前节点还是前一个节点
MY_LIST *FindElem(MY_LIST *pHead, int a,bool pos) {
MY_LIST *temp = pHead;
MY_LIST *prev = NULL;
while (temp) {
if (temp->v == a) break;
prev = temp;
temp = temp->next;
}
return (!pos)?prev:temp;
}
//指定节点位置之后插入新节点，若无则入队尾
void InsertItem(MY_LIST *pItem, int a, MY_LIST *pHead) {
MY_LIST *node = (MY_LIST *)malloc(sizeof(MY_LIST));
node->v = a;
node->next = NULL;
//移动指针到pItem，或者到队尾
MY_LIST *end = pHead;
while (end) {
if (end->next == NULL) break;
if (end->next == pItem) {
end = pItem;
break;
}
end = end->next;
}
node->next = end->next;
end->next = node;
printf("***Add Item is %d***\n", node->v);
return;
}
//删除指定元素节点
void DelItem(MY_LIST *pHead, int item) {
MY_LIST *pItemPrev = FindElem(pHead, item, 0);
if (pItemPrev == NULL)
printf("%d is not exists!\n", item);
MY_LIST *pItem = pItemPrev->next; //当前节点
pItemPrev->next = pItem->next; //重置前一节点的next指针
free(pItem);
pItem = NULL;
}
//销毁除头节点之外的所有链表节点
void CleanMyList(MY_LIST *pHead) {
MY_LIST *temp = pHead->next;
MY_LIST *pNext = NULL;
while (temp) {
pNext = temp->next;
pHead->next = pNext;
free(temp);
temp = pNext;
}
if (pHead->next == NULL)
printf("Clean MyList Done!\n");
return;
}
//链表反转
void ReverseMyList(MY_LIST *pHead) {
MY_LIST *cur = pHead->next;
MY_LIST *curNext = NULL;
MY_LIST *temp = NULL;
while (cur) {
curNext = cur->next;
cur->next = temp;
temp = cur;
cur = curNext;
}
pHead->next = temp;
}
//链表排序
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void SortList(MY_LIST *pHead) {
MY_LIST* pPrev = pHead;
MY_LIST* pEnd = NULL;
MY_LIST* pCur = NULL;
while (pHead != pEnd) {
pPrev = pHead;
while (pPrev->next != pEnd) {
pCur = pPrev->next;
if (pPrev->v < pCur->v) swap(&pPrev->v, &pCur->v);
pPrev = pPrev->next;
}
pEnd = pPrev;
}
}
/*__ 工具书参考，已验证，需要注意的是链表的表头指针问题！ __ */
#include
#include
#include
typedef struct Node {
int element;
Node* next;
}Node;
/* 1.Initialize Linked:表头指针为空 */
void initList(Node** pNode) {
*pNode = NULL;
printf("\n1.开始执行initList函数：初始化成功\n");
}
/* 2.打印链表 */
void printList(Node* pHead) {
printf("\n2.开始执行printList函数：");
if (NULL == pHead)
{
printf("链表为空\n");
return;
}
else {
while (NULL != pHead) {
printf("%d\t", pHead->element);
pHead = pHead->next;
}
printf("\n");
}
}
/* 3.创建链表，若输入负数则终止读取数据 */
Node * creatList(Node *pHead) {
printf("\n3.开始执行creatList函数：\n");
//分配节点p1,p2，并初始化
Node* p1, *p2;
p1 = p2 = (Node*)malloc(sizeof(Node));
if (NULL == p1 || NULL == p2) { printf("内存申请失败\n"); exit(1); }
memset(p1, 0, sizeof(Node));
printf("请输入链表元素值：\n");
scanf("%d", &p1->element);
p1->next = NULL;
while (p1->element > 0) {
if (pHead == NULL) {
pHead = p1;
}
else {
p2->next = p1;
}
p2 = p1;
p1 = (Node*)malloc(sizeof(Node));
memset(p1, 0, sizeof(Node));
scanf("%d", &p1->element);
p1->next = NULL;
}
printf("创建链表成功\n");
return pHead; //下移的是p2,所以pHead位置未曾改变
}
/* 4.清空链表 */
void clearList(Node* pHead) {
Node* pNext;
printf("\n4.开始执行clearList函数：\n");
if (NULL == pHead) {
printf("链表是空的\n");
return;
}
while (pHead->next != NULL) {
pNext = pHead->next;
free(pHead);
pHead = pNext;
}
printf("链表已清空\n");
}
/* 5.返回链表长度 */
int sizeList(Node* pHead) {
int i = 0;
while (pHead != NULL) {
i++; //因为表头的存在，size比链表的实际长度小1
pHead = pHead->next;
}
printf("\n5.开始执行sizeList函数：链表长度为%d\n", i);
return i;
}
/* 6.检查链表是否为空 */
int isEmptyList(Node* pHead) {
printf("\n6.开始执行isEmptyList函数：");
if (pHead == NULL) {
printf("链表为空\n");
return 1;
}
printf("链表非空\n");
return 0;
}
/* 7.返回链表中第pos个节点的元素 */
int getElement(Node* pHead, int pos) {
int i = 0;
printf("\n7.开始执行getElement函数：");
if (pos < 0) {
printf("pos值非法\n");
return 0;
}
if (pHead == NULL) {
printf("链表为空\n");
return 0;
}
while (pHead != NULL) {
++i;
if (i == pos) {
break;
}
pHead = pHead->next;
}
if (i < pos) {
printf("pos值超出链表长度\n");
return 0;
}
return pHead->element;
}
/* 8.从链表中找出第一个给定值x的元素 */
int* getElemAddr(Node* pHead, int x) {
printf("\n8.开始执行getElemAddr函数，从链表中找出第一个给定值为%d的元素：\n", x);
if (pHead == NULL || x <= 0) {
printf("非法\n");
return NULL;
}
while (pHead->element != x && NULL != pHead->next) {
pHead = pHead->next;
}
if (pHead->element != x && pHead != NULL) {
printf("链表中找不到%d值\n", x);
return NULL;
}
if (pHead->element == x)
printf("元素%d的地址为0x%x\n", x, &(pHead->element));
return &(pHead->element);
}
/* 8.从链表中找出第一个给定值x的元素所在链表指针 */
Node* getAddress(Node* pHead, int x) {
printf("\n8.开始执行getAddress函数，从链表中找出第一个给定值为%d的元素节点地址：\n", x);
if (pHead == NULL || x <= 0) {
printf("非法\n");
return NULL;
}
while (pHead->element != x && NULL != pHead->next) {
pHead = pHead->next;
}
if (pHead->element != x && pHead != NULL) {
printf("链表中找不到%d值\n", x);
return NULL;
}
if (pHead->element == x)
return pHead;
}
/* 9.将链表中第pos个节点的值修改为x */
int modifyElem(Node* pHead, int pos, int x) {
int i = 0;
printf("\n9.开始执行ModifyElem函数：");
if (pHead == NULL || x <= 0) {
printf("非法\n");
return NULL;
}
while (pHead != NULL) {
++i;
if (i == pos) break;
pHead = pHead->next;
}
if (i < pos) {
printf("pos值超出链表长度\n");
return 0;
}
printf("将链表中第%d个节点的值由%d修改为%d：", pos, pHead->element, x);
pHead->element = x;
printf("Done\n");
return 1;
}
/* 10.向链表头插入一个元素 */
int insertHeadList(Node **pHead, int insertElem) {
Node *pInsert;
pInsert = (Node*)malloc(sizeof(Node));
memset(pInsert, 0, sizeof(Node));
pInsert->element = insertElem;
pInsert->next = *pHead;
*pHead = pInsert;
printf("\n10.开始执行insertHeadList函数：成功向表头插入元素%d\n",insertElem);
return 1;
}
/* 11.向表尾添加一个元素 */
int insertLastList(Node **pNode, int insertElem) {
Node* pInsert;
Node* pHead;
pHead = *pNode;
pInsert = (Node*)malloc(sizeof(Node));
memset(pInsert, 0, sizeof(Node));
pInsert->element = insertElem;
while (pHead->next != NULL) {
pHead = pHead->next;
}
pHead->next = pInsert;
printf("\n11.开始执行insertLastList函数：成功向表尾添加元素%d\n",insertElem);
return 1;
}
int main(void) {
Node* pList = NULL; //空链表
Node * posModify;
int length = 0;
int posElem;
initList(&pList);
isEmptyList(pList);
pList = creatList(pList);
length=sizeList(pList);
printList(pList);
posElem = getElement(pList, 3);
printf("获取链表中位置为3的元素值：%d\n", posElem);
getElemAddr(pList, 5);
modifyElem(pList, 4, 1);
printList(pList);
posModify = getAddress(pList, 3);
printf("0x%x", posModify);
posModify->element = 30;
printf("\nAfter modify element value:");
printList(pList);
insertHeadList(&pList,5);
sizeList(pList);
printList(pList);
insertLastList(&pList,10);
sizeList(pList);
printList(pList);
clearList(pList);
getchar(); return 0;
}