Day 62 单向循环链表 双链表

#include
#include
#include
/* 双向链表的结构 */
struct List
{
int data; //数据域
struct List *next; //向后的指针
struct List *front; //向前的指针
};
typedef struct List NODE;
/*
* 双向链表的创建
*
*/
NODE *CreatList()
{
NODE *head = (NODE *)malloc(sizeof(NODE));
if(head == NULL)
{
printf("malloc error\n");
return NULL;
}
head->next = head->front = NULL; //初始化链表，指针置空
return head;
}
/*
* 双向链表插入节点，头插法
*/
void InsertNode(NODE *head , int data)
{
if( head == NULL )
{
printf("The list is empty.\n"); // 头结点为空，则无法插入
return;
}
NODE *tmpHead = head; // 创建一个临时的头结点指针
if( tmpHead->next == NULL )
{
/* 当双向链表只有一个头结点时 */
NODE *addition = (NODE *)malloc(sizeof(NODE));
if( addition == NULL )
{
printf("malloc error\n");
return;
}
addition->data = data; //数据域赋值
addition->next = tmpHead->next; //后向指针连接
tmpHead->next = addition;
addition->front = tmpHead; //将插入结点的front 指向头结点
}
else
{
/* 当双向链表不只一个头结点时 */
NODE *addition = (NODE *)malloc( sizeof(NODE));
if( addition == NULL )
{
printf("malloc error\n");
return;
}
addition->data = data; // 数据域赋值
tmpHead->next->front = addition; // 头结点的下一个结点的front 指针
addition->front = tmpHead; // 插入的结点的front 指针指向头结点
addition->next = tmpHead->next; // 插入结点的next 指针指向原本头指针的下
一结点
tmpHead->next = addition; // 将头结点的next 指针指向插入结点
}
}
/*
* 删除一个节点
*/
void DeleteNode(NODE *head , int data)
{
if(head == NULL)
{
printf("The list is empty.\n");
return;
}
NODE *tmpHead = head;
while( tmpHead->next != NULL )
{
tmpHead = tmpHead->next;
if( tmpHead->data == data )
{
tmpHead->front->next = tmpHead->next; // 将被删结点的上一个结
点的next 指针指向 被删结点的下一个结点
tmpHead->next->front = tmpHead->front; // 将被删结点的下一个结
点的 front 指针指向 被删结点的上一个结点
break;
}
}
free(tmpHead); //释放内存
tmpHead = NULL;
}
/*
* 修改一个节点的值
*/
void UpdateNode(NODE *head , int oldval,int newval)
{
if(head == NULL)
{
printf("The list is empty.\n");
return;
}
NODE *tmpHead = head;
while( tmpHead->next != NULL )
{
tmpHead = tmpHead->next;
if(tmpHead->data == oldval)
{
tmpHead->data == newval;
continue;
}
}
}
/*
* 查找值为val的节点位置
*/
int FindNode(NODE *head , int val)
{
int count = 0;
if(head == NULL)
{
printf("The list is empty.\n");
return -1;
}
NODE *tmpHead = head;
while( tmpHead->next != NULL )
{
tmpHead = tmpHead->next;
if(tmpHead->data == val)
{
return count;
}
count++;
}
return -1;
}
/*
* 双向链表的遍历
*/
void displayList(NODE *head)
{
printf("-------------------------------\n");
if( head == NULL )
{
printf("The list is empty.\n");
return;
}
NODE *tmpHead = head; //头节点没有数据
while(tmpHead->next != NULL )
{
tmpHead = tmpHead->next; //头结点数据域为空，因此直接从头结点的下一结点开
始遍历
printf("%d->",tmpHead->data);
}
// 此时tmpHead 的地址在链表的最后一个结点处
while( tmpHead->front->front != NULL )
{
printf("%d<-",tmpHead->data); // 最后一个结点要输出
tmpHead = tmpHead->front;
}
printf("%d\n",tmpHead->data);
return;
}
/*
* 销毁一个链表，从头结点开始
*/
void DestroyList(NODE *head)
{
NODE *tmp;
while(head->next != NULL)
{
tmp = head; // 指针不断后移
head = head->next;
free(tmp);
tmp = NULL;
}
free(head);
head = NULL;
}
int main()
{
//创建一个双向链表
NODE *phead = CreatList();
if(phead == NULL)
{
printf("create list error\n");
}
//双向链表的头部插入数据
int i;
for(i=0;i<6;i++)
{
InsertNode(phead , i);
}
//显示链表的数据
displayList(phead);
//删除链表中的一个节点
DeleteNode(phead , 4);
displayList(phead);
//修改链表中的一个节点的值
UpdateNode(phead , 2,222);
displayList(phead);
//查找链表中的一个值
int ret = FindNode(phead , 3);
printf("要找的节点是：%d\n",ret);
return 0;
}