定义一个结构体Node，第一个成员为int value；第二个成员为指向Node类型的指针
1）创建链表
Node * create()
返回链表首元素的地址，课件有程序
函数中包含了动态输入节点的过程
分头结点和非头结点两种情况接入链表
2）输出链表
void list(Node *pHead)
将pHead作为参数，遍历链表并输出，无需返回值，课件有程序
3）查找节点
Node *search(Node *pHead, int info)
实参用首地址，查找value值为info的节点，若找到，返回指向该节点的指针，课件有程序
4）插入节点，并保持链表value有序
Node* insert(Node *pHead)
在主调函数中用户输入一个要插入的节点，动态内存分配返回指针pTmp
1） pHead为NULL，pTmp直接作为首节点；
2） pHead不为NULL，对比pTmp的value值和链表中当前节点的value值，找到要插入的位置，再分两种情况：
结点插入的位置在链首：当前节点指向原来的第一个节点，头指针指向当前节点。
结点插入的位置不在链首，借助pCur和pPrev实现
5）插入节点到链尾
Node* insert_tail(Node *pHead)
在主调函数中用户输入一个要插入的节点，动态内存分配返回指针pTmp
1) pHead为NULL，pTmp直接作为首节点；
2）pHead不为NULL，遍历链表，找到pTail，pTail指向pTmp；
6）删除节点
Node* delete(Node *pHead, int info)
1） pHead为NULL，打印不能执行删除操作
2） pHead不为NULL，调用search函数，找到info对应 节点的地址，再分两个情况：
要删除的结点在链首
要删除的节点不在链首，借助pCur和pPrev实现
7）删除整个链表
Node* delete_list(Node *pHead)
1） pHead为NULL，打印不能执行删除操作
2） pHead不为NULL，
如果pHead->pNext不为NULL，将pHead赋值给pTmp，pHead后移，释放pTmp空间
如果pHead->pNext为NULL，释放pHead空间，将pHead赋值为0返回。
8）链表中的值按逆序输出
Node* re_list(Node* pHead)
遍历链表，将value存在数组中，倒序输出即可。
9）逆序链表
Node * reverse_list(Node * pHead)
1) pHead为NULL或者pHead->pNext为空，无需执行逆序操作
2）链表有两个以上节点时：
借助三个临时指针pTmp1、pTmp2、pTmp3实现，其中pTmp1和pTmp2实现翻转，pTmp3记录剩下的链表。
pTmp1 = pHead;
pTmp2 = pHead->next;
pHead->pnext = NULL;
while(pTmp2){
pTmp3 = pTmp2->next;
pTmp2->next = pTmp1;
pTmp1 = pTmp2;
pTmp2 = pTmp3;
}
pHead=pTmp1;
return pHead;
主函数中程序为：
int main()
{
Node *pHead=create(); //输入3创建三个节点，分别输入1 5 7作为value值
Node Node1={3, NULL};
Node Node2={9,NULL};
Node *pNode3, *pNode4;
list(pHead); //遍历链表，输出1 5 7
insert( pHead);
list(pHead); //输入3，输出1 3 5 7
insert_tail(pHead);
list(pHead);//输入9，输出1 3 5 7 9
pNode3 = search(pHead, 3);
printf(“%d\n”,pNode3->value); //输出3
delete(pHead,3);
list(pHead);//输出1 5 7 9
re_list(pHead);//输出9 7 5 1
pNode4 = reserve_list(pHead);
list(pNode4);//输出9 7 5 1
delete_list(pNode4); //在该函数最后打印链表被删除。
return 0;
} |
天盟APP下载
