数据结构学习笔记1之单向链表的实现

链表中最简单的一种是单向链表，它包含两个域，一个数据域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

一般来说，头结点的数据域不放入有效数据。最简单的单向链表就是头结点的数据域为NULL,空单向链表

结点结构体设计

1 struct  Node
2 {
3     int data; //数据域
4     struct Node * pNext; //指针域
5 };

创建空单向链表

 1 //创建空链表
 2 struct Node * CreateEmptyList()
 3 {
 4     struct Node * pHead;
 5     pHead = (struct Node *)malloc(sizeof(struct Node));
 6     if (pHead == NULL)
 7     {
 8         printf("申请内存失败。。");
 9         exit(0);
10     }
11     printf("初始化链表成功
");
12     pHead->data = 0;
13     pHead->pNext = NULL;
14 
15     return pHead;
16 }

创建结点

//创建结点
struct Node * CreateNode(int data)
{
	struct Node * pHead;
	pHead = (struct Node *)malloc(sizeof(struct Node));
	if (pHead == NULL)
	{
		printf("申请内存失败。。");
		exit(0);
	}
	pHead->data = data;
	pHead->pNext = NULL;
	printf("创建结点成功，数据域为:%d
", data);
	return pHead;
}

在表尾插入数据

//在表尾插入数据
void InsertNode(struct Node * pHead, struct Node * pNode)
{
	struct Node * pTemp;
	pTemp = pHead;
	while (pTemp ->pNext!= NULL)
	{
		pTemp = pTemp->pNext;
	}
	
	pTemp->pNext = pNode;
	pNode->pNext =NULL;
	printf("在表尾插入成功,数据域为:%d
", pNode->data);
	printf("--------------万恶的分割线-------------------
");
}

　　链表的遍历输出

//遍历链表
void TraverseList(struct Node * pHead)
{
	struct Node * pTemp;
	pTemp = pHead;
	while (pTemp->pNext!= NULL)
	{
		pTemp = pTemp->pNext;
		printf("%d,",pTemp->data);
	}
}

　　全部代码

  1 # include <stdio.h>
  2 # include <stdlib.h>
  3 
  4 struct  Node
  5 {
  6     int data;
  7     struct Node * pNext;
  8 };
  9 
 10 //创建空链表
 11 struct Node * CreateEmptyList();
 12 
 13 //创建结点
 14 struct Node * CreateNode(int data);
 15 
 16 //在表尾插入数据
 17 void InsertNode(struct Node * pHead, struct Node * pNode);
 18 
 19 //遍历链表
 20 void TraverseList(struct Node * pHead);
 21 
 22 int main()
 23 {
 24     int num; //要输入的数据数目
 25     struct Node * phead = NULL; //头指针
 26     struct Node * pData = NULL;
 27 
 28     printf("要插入多少个数？num=");
 29     scanf("%d",&num);
 30 
 31     phead = CreateEmptyList();
 32     for (int i = 0; i < num; i++)
 33     {
 34         int input;//输入的数据
 35         printf("请输入第%d个数据:",i+1);
 36         scanf("%d",&input);
 37         pData = CreateNode(input);
 38         InsertNode(phead, pData);
 39     }
 40 
 41     TraverseList(phead);
 42     return 0;
 43 }
 44 
 45 //创建空链表
 46 struct Node * CreateEmptyList()
 47 {
 48     struct Node * pHead;
 49     pHead = (struct Node *)malloc(sizeof(struct Node));
 50     if (pHead == NULL)
 51     {
 52         printf("申请内存失败。。");
 53         exit(0);
 54     }
 55     printf("初始化链表成功
");
 56     pHead->data = 0;
 57     pHead->pNext = NULL;
 58 
 59     return pHead;
 60 }
 61 
 62 //创建结点
 63 struct Node * CreateNode(int data)
 64 {
 65     struct Node * pHead;
 66     pHead = (struct Node *)malloc(sizeof(struct Node));
 67     if (pHead == NULL)
 68     {
 69         printf("申请内存失败。。");
 70         exit(0);
 71     }
 72     pHead->data = data;
 73     pHead->pNext = NULL;
 74     printf("创建结点成功，数据域为:%d
", data);
 75     return pHead;
 76 }
 77 
 78 //在表尾插入数据
 79 void InsertNode(struct Node * pHead, struct Node * pNode)
 80 {
 81     struct Node * pTemp;
 82     pTemp = pHead;
 83     while (pTemp ->pNext!= NULL)
 84     {
 85         pTemp = pTemp->pNext;
 86     }
 87     
 88     pTemp->pNext = pNode;
 89     pNode->pNext =NULL;
 90     printf("在表尾插入成功,数据域为:%d
", pNode->data);
 91     printf("--------------万恶的分割线-------------------
");
 92 }
 93 
 94 //遍历链表
 95 void TraverseList(struct Node * pHead)
 96 {
 97     struct Node * pTemp;
 98     pTemp = pHead;
 99     while (pTemp->pNext!= NULL)
100     {
101         pTemp = pTemp->pNext;
102         printf("%d,",pTemp->data);
103     }
104 }

View Code