一.准备工作
- 我们建立单链表准备采用
头插法和尾插法两种方法来建立单链表。 - 单链表的准备工作和顺序表的准备工作基本相同，点击—>顺序表的准备工作+建立工作即可查看。
- 头部函数：
[] 两个头文件stdio.h和stdlib.h
[] 定义状态函数
[] 定义结点数据域的数据类型
#include<stdio.h> #include<stdlib.h> typedef int Status;//状态函数 typedef int ElemType;//结点数据域的数据类型
1.通过结构类型来定义单链表存储类型与定义
typedef struct Node { ElemType data;//数据域 struct Node* next;//指针域 }Node;
通过以上结构类型我们定义了一个数据域data数组和指针域Node* next。
我们知道单链表的结构如图：
由单链表的结构组成可知：
- 单链表的每个结点是由两部分组成的，分别是
数据域和指针域。 - 我们通常将
数据域里的数据用数组data来存储 - 我们通常将
指针域里的数据用数组next来存储
所以单链表可以表示成如下图：
我们需要知道图中的信息：
- 每个
data数组是用来存放结点的值 - 每个
next指针都是用来存放下一个结点的地址 - 定义指向指针的结点类型
typedef struct Node* LinkList;
这条语句通常都会加到typedef定义的结构类型后面，它的含义是：
把struct Node*定义成了一个新的类型LinkList，这个类型是一个结构体指针。
换句话说就是：
LinkList和struct Node*等价，他有两个名字。
二.操作函数的声明
1.单链表的初始化
2.尾插法建立单链表
3.头插法建立单链表
4.输出链表的数据域
LinkList InitList_List(void); LinkList CreateListTail(ElemType a[],int n); LinkList CreateListHead(ElemType a[],int n); void PrintList_List(LinkList head);
三.主函数的编写
1.主函数的编写
int main() { ElemType d[4]={17,24,39,45}; /*===================================*/ LinkList Tail_Head;//尾插法 Tail_Head=CreateListTail(d,4);//尾插法 /*===================================*/ LinkList H_Head;//头插法 H_Head=CreateListHead(d,4);//头插法 /*=====================================*/ printf("单链表是：\n"); PrintList_List(Tail_Head);//尾插法调用功能函数 PrintList_List(H_Head);//头插法调用功能函数 /*=====================================*/ printf("\n"); return 0;
四.功能函数的编写
1.尾插法
LinkList CreateListTail(ElemType a[],int n) { LinkList head,p,q; int i; head=Initlist_List(); q=head; for(i=0;i<n;i++) { p=(Node*)malloc(sizeof(Node)); p->data=a[i]; q->next=p; q=p; } p->next=NULL; return head; }
2.头插法
LinkList CreateHead(ElemType a[],int n) { LinkList head,p; int i; head=InitList_List(); for(i=n-1;i>=0;i--) { p=(Node*)malloc(sizeof(Node)); p->data=a[i]; p->next=head->next; head->next=p; } return head; }
3.线性表输出函数
void PrintList_List(LinkList head) { LinkList p; p=head; while(p->next!=NULL) { p=p->next; printf("%d",p->data); } }
4.线性表的初始化
LinkList InitList_List(void) { LinkList head;//定义头指针 /*动态内存分配空间给head指针*/ head=(Node *)malloc(sizeof(Node));//申请一个结点给head指针 if(head==NULL)//动态内存分配失败 exit(1); head->next=NULL;//只有一个结点 return head;//返回头指针 }
五.函数接口的说明
1.链表的初始化
LinkList InitList_List(void);
接口：无
[注意点]：为什么初始化函数的形参为void空类型呢？
- 我们知道了链表的存储结构，还需要了解单链表的两种形式。
- 单链表的两种形式为：
（1）.不带头结点的单链表
（2）.带头结点的单链表
以上多出来的头结点是指：位于单链表最前面的一个摆设，哈哈，之所以理解成摆设是因为它的数据域里不存放东西，也就是NULL了，而且头结点不计入单链表表长，说到底它就是没有存在感般的存在。所以我们以上形参直接定义成void，其实还有个等价的方法写出来，便于你理解。
void InitList_List(LinkList *L)//初始化单链表 { L=(LinkList_List *)malloc(sizeof(LinkList_List)); L->next=NULL; }
我们用一个指针L来代表形参，在动态内存开辟空间申请新结点给L，L指向的头结点为NULL，其实这个指针L就是头指针了。
2.尾插法建立单链表函数
LinkList CreateListTail(ElemType a[],int n);
函数接口1：ElemType a[]表示结点的值
函数接口2：int n表示结点的个数
3.头插法建立单链表函数
LinkList CreateListHead(ElemType a[],int n);
函数接口1：ElemType a[]表示结点的值
函数接口2：int n表示结点的个数
4.单链表输出函数
void PrintList_List(LinkList head);
函数接口：链表头指针LinkList
别问为什么形参是头指针啊，单链表执行逻辑就是从头指针开始的呀，不像顺序表那样支持随机访问，单链表这里还是得好好老老实实从头开始。
六.头插法和尾插法的算法分析
为什么我们要在后边来讨论头插法和尾插法的算法分析呢？
因为我们前面已经提到了单链表的两种形式，知道了有无头结点的单链表。
<1>.在带有头结点的单链表中进行头插法
我们通过改变结点指针域指向的方式就可以将新结点a1插入其中。
<2>.在带无头结点的单链表中进行头插法
尾插法算法分析也是如此，可以试着自己分析一下。
