链表专业术语:
首结点:
存放第一个有效数据的结点
尾结点:
存放最后一个有效数据的结点,指针域的指针为NULL,非循环单链表的结束标志
头结点:
头结点的数据类型和首结点的类型是一模一样的
头结点是首结点前面的那个节点
头结点并不存在有效数据
设置头结点的目的是为了方便对链表的操作
头指针:
存放头结点地址的指针变量
确定一个链表只需要一个参数,头指针
对于每个链表元素,分为左右两部分,左边为数据单元,右边为下一元素地址。
1 链表的建立和遍历
# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>struct Node
{int data; //数据域struct Node * pNext; //指针域
};//函数声明
struct Node * create_list(void);
void traverse_list(struct Node *);int main(void)
{struct Node * pHead = NULL;pHead = create_list(); //create_list():创建一个非循环单链表,并将该链表的头结点的地址赋给pHeadtraverse_list(pHead);return 0;
}struct Node * create_list(void)
{int len; //用来存放有效节点的个数int val; //用来临时存放用户输入的结点的值//分配了一个不存放有效数据的头结点struct Node * pHead = (struct Node *)malloc(sizeof(struct Node));if (NULL == pHead){printf("分配失败, 程序终止!\n");exit(-1);}struct Node * pTail = pHead;pTail->pNext = NULL;printf("请输入您需要生成的链表节点的个数: len = ");scanf("%d", &len);int i; //for (i=0; i<len; ++i){printf("请输入第%d个节点的值: ", i+1);scanf("%d", &val);struct Node * pNew = (struct Node *)malloc(sizeof(struct Node));if (NULL == pNew){printf("分配失败, 程序终止!\n");exit(-1); //终止程序}pNew->data = val;pTail->pNext = pNew;pNew->pNext = NULL;pTail = pNew;}return pHead;
}void traverse_list(struct Node * pHead)
{struct Node * p = pHead->pNext;while (NULL != p){printf("%d ", p->data);p = p->pNext;}printf("\n");return;
}
来自为知笔记(Wiz)