C语言-实现单向链表

 1、什么是链表：

链表是一种在逻辑上连续，物理存储上不一定连续的存储结构。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 

链表的结构，我们可以用下图描述：

2、代码实现链表：

链表所涉及的基本功能主要有：

创建链表、插入结点、求链表的长度、查找、排序、遍历、删除结点、链表逆置、链表销毁。

在下面的代码中：我们约定链表为单向链表，带有头结点，并且头结点是空的不放数据（这样做好处就是后面所有操作不需要更新头指针）。

#include 
#include 
#include 
/*实现的功能：
创建链表、插入结点、求链表的长度、查找、排序、遍历、删除结点、链表逆置、链表销毁*/
typedef struct node
{int data;node *next;
}node;node *creatList()	//创建空链表
{node *head = (node *)malloc(sizeof(node));if (NULL == head){exit(-1);}head->next = NULL;return head;
}void insertList(node *head, int nodeData)	//插入链表节点----头插法
{node *cur = (node *)malloc(sizeof(node));if (NULL == head){exit(-1);}cur->data = nodeData;cur->next = head->next;head->next = cur;
}int lenList(node *head)	//求链表的长度
{head = head->next;    /*我们约定头链表是空的，不放数据*/int len = 0;while (head != NULL){len++;head = head->next;}return len;
}node *searchList(node *head, int findData)	//查找
{head = head->next;while (head != NULL){if (head->data == findData){break;}head = head->next;}return head;
}//void deleteNodeOfList(node *head, node *pfind)	//删除
//{
//	while (head->next != pfind)
//	{
//		head = head->next;
//	}
//	head->next = pfind->next;
//	free(pfind);
//	pfind = NULL;
//}void deleteNodeOfList(node *head, node *pfind) //删除优化
{if (pfind->next == NULL){while (head->next != pfind){head = head->next;}head->next = pfind->next;free(pfind);pfind = NULL;}else{node *t = pfind->next;  //起牵线搭桥作用pfind->data = pfind->next->data;  //后一个数据覆盖前一个pfind->next = pfind->next->next;  //然后删除后一个节点free(t);}
}//void popsortList(node *head)	//冒泡排序
//{
//	int len = lenList(head);
//	head = head->next;
//	node *p ;
//	node *q ;
//	for (int i = 0; i < len-1; i++)
//	{
//		p = head;	//	每次内层循环从头开始
//		q = p->next;//  q总是指向p的下一个节点，也就是被比较的节点
//		for (int j = 0; j < len - 1 - i; j++)
//		{
//			if (p->data > q->data)
//			{
//				p->data ^= q->data;
//				q->data ^= p->data;
//				p->data ^= q->data;
//			}
//			p = p->next;
//			q = p->next;
//		}
//	}
//}void popsortList(node *head)	//优化----冒泡排序
{int len = lenList(head);node *prep, *p, *q,*t;for (int i = 0; i < len - 1; i++){prep = head;p = head->next;q = p->next;for (int j = 0; j < len - 1 - i; j++){if (p->data > q->data){prep->next = q;p->next = q->next;q->next = p;//由于q跑到p的前面，更换一下顺序t = p;p = q;q = t;}prep = prep->next;p = p->next;q = p->next;}}
}void reverseList(node *head)	//链表逆置
{node *cur = head->next;head->next = NULL;node *t;while (cur != NULL){t = cur;cur = cur->next;t->next = head->next;head->next = t;}
}void traverseList(node *head)	//遍历
{head = head->next;while (head != NULL){printf("%d\n", head->data);head = head->next;}
}void destoryList(node *head)	//销毁链表
{node *t;while (head!=NULL){t = head;head = head->next;free(t);}
}int main()
{srand(time(NULL));node *head = creatList();for (int i = 0; i < 10; i++){insertList(head, rand()%100);}traverseList(head);printf("len of all list:%d\n", lenList(head));node *pfind = searchList(head, 8);if (pfind == NULL){printf("find none\n");}else{//pfind->data = 1000;        //修改数据printf("your find in list\n");//deleteNodeOfList(head, pfind);}printf("---------排序---------\n");popsortList(head);		//排序traverseList(head);printf("---------逆置---------\n");reverseList(head);traverseList(head);destoryList(head);system("pause");return 0;
}

3、总结：

1） 链表插入结点的方式主要有两种：头插法（常用）和尾插法。

      头插法的关键在于：让新插入的结点先有所指向，避免打断原有的指向。

2）在删除操作中，重点是如何找到前驱，这里我们使用while循环的方式，特别要注意循环条件的设置。

3）这里使用的排序算法是冒泡排序，且对冒泡排序做了优化。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！