本文章依据学校的实验作业完成

目录

前言

一、链表是什么？

1.概念

2.链表的分类

二、单链表的创建，插入，删除以及查找

1.单链表的存储结构

2.单链表的创建

3.单链表的插入

4.单链表的删除

5.单链表的查找

6.主函数

7.完整代码

8.编译结果

三、总结

---

---

前言

链表是一种物理存储单元上非连续、非顺序的存储结构，由一系列结点组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

一、链表是什么？

1.概念

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

逻辑上连续是我们想象的连续，并不是真正的连续。

2.链表的分类

单向双向，带头结点不带头结点，循环非循环，组合起来共有8种

二、单链表的创建，插入，删除以及查找

1.单链表的存储结构

typedef int ElemType;	//便于后期的修改 
 
//定义结点类型 
typedef struct Node {
    ElemType data;              //单链表中的数据域 
    struct Node *next;          //单链表的指针域 
}Node,*LinkedList;

2.单链表的创建

	//单链表的建立（头插法）
	
	LinkedList ListCreatH() {
	    Node *L;
	    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
	    L->next = NULL;                      //初始化一个空链表
	    int i=0;
	    ElemType x;                         //x为链表数据域中的数据
	    while(i<10) {
	        Node *p;
	        p = (Node *)malloc(sizeof(Node));   //申请新的结点 
	        scanf("%d",&x);
	        p->data = x;                     //结点数据域赋值 
	        p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL 
	        L->next = p; 
	        i++;
	    }
	    return L; 
	} 
	 
	 
	//单链表的建立（尾插法）(注：比较常用)
	 
	LinkedList ListCreatT() {
	    Node *L;
		    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
		    L->next = NULL;                  //初始化一个空链表
		    Node *r;
		    r = L;                          //r始终指向终端结点，开始时指向头结点 
			int i=0   ;                   //x为链表数据域中的数据
		    for(i=0;i<10;i++)
			{ 		
				Node *p;
		        p = (Node *)malloc(sizeof(Node));   //申请新的结点 
		        scanf("%d",&p->data);
		        r->next = p;                 //将结点插入到表头L-->|1|-->|2|-->NULL 
		        r = p; 						//将r结点移动到最后一个节点
		    }
		    r->next = NULL;  				//让r结点的指针域置空(链表创建完成)
		    return L; 
	}

3.单链表的插入

//单链表的插入，在链表的第i个位置插入x的元素
/*初始条件：单链表L已存在，1<=i<=ListLength(L)*/
/*在L中第i个位置之前插入新的数据元素e，L的长度加1*/
LinkedList ListInsert(LinkedList L,int i,ElemType x) {
    LinkedList pre;                      //pre为前驱结点 
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
    	pre = pre->next;                 //查找第i个位置的前驱结点 
	}
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;             //主要代码
    p->next = pre->next;          //主要代码
    pre->next = p;
    return L;                           
} 

4.单链表的删除

//单链表的删除，在链表中删除第i个数据元素
/*初始条件：单链表L已存在，1<=i<=ListLength(L)*/
/*操作结果：删除L的第i个数据元素，L的长度减1*/ 
LinkedList ListDelete(LinkedList L,int i)
{
    LinkedList p,q;                   
	int j=2; 
    p = L->next;
    while(p->next&&j<i) {              //查找第i个位置 
        p=p->next;
		++j;
    }
    if(!(p->next)||j>i)			//第i个元素不存在
		printf("第i个元素不存在\n");
    q=p->next;				
	p->next=q->next;			//将q的后继赋值给p的后继 
    free(q);                    //释放q结点
    return L;
} 

5.单链表的查找

//单链表的查找
/*初始条件：单链表L已存在，1<=i<=ListLength(L)*/
/*操作结果：用e打印中第i个数据元素的值*/ 
 void GetElem(LinkedList L)
 {
 	int i,j=1;		//j为计数器 
 	int *e;
 	LinkedList p;		//声明一结点p 
 	printf("请输入查找的位置:");
 	scanf("%d",&i);
 	p=L->next;		//让p指向链表L的第一个结点 
 	while(p&&j<i)        //p不为空且到达i结点
 	{
 		p=p->next;		//让p指向下一个结点 
 		++j;	
 	}
 	if(!p||j>i)        //链表p为空否则链表长度过短
 		printf("第i个元素不存在");		//第i个元素不存在 
 	*e=p->data;				//取第i个元素的数据 
 	printf("%d\n",*e);
 }

6.主函数

int main() {
    LinkedList list,start;
 	printf("请输入单链表的数据：\n"); 
    list = ListCreatT();
    printf("成功创建链表：\n");
    for(start = list->next; start != NULL; start = start->next) {
    	printf("%d ",start->data);
	}
    printf("\n");
    menu();
    int i,option;
    ElemType x;
    do{
		printf("请输入选项：");
		scanf("%d",&option);
		switch(option)
		{
		   	case 1:
			{
			   	printf("请输入插入数据的位置：");
				scanf("%d",&i);
				printf("请输入插入数据的值：");
				scanf("%d",&x);
				ListInsert(list,i,x);
				printf("插入后的链表为：");
				//打印链表 
				for(start = list->next; start != NULL; start = start->next)
				{
					printf("%d ",start->data);
				}
				printf("\n");
					  break;
				}
			case 2:
			{
				int i; 
				printf("请输入删除的位置\n");
				scanf("%d",&i);
				ListDelete(list,i);
				printf("删除后的链表为：");
				//打印链表
				for(start = list->next; start != NULL; start = start->next)
				{
					printf("%d ",start->data);					
				}
				printf("\n");
				break;		
			}
			case 3:GetElem(list);			break;		
			case 0:break;	
			default:printf("输出错误！\n");break;
	   } 		
	}while(option>0);
    return 0;
}

7.完整代码

#include <stdio.h>
#include <stdlib.h>
 
typedef int ElemType;	//便于后期的修改 
 
//定义结点类型 
typedef struct Node {
    ElemType data;              //单链表中的数据域 
    struct Node *next;          //单链表的指针域 
}Node,*LinkedList;
 
 
 //建立菜单 
 void menu()
 {
  printf("*****1.单链表的插入*****\n");
  printf("*****2.单链表的删除*****\n");
  printf("*****3.单链表的查找*****\n");
  printf("*****0.     退出   *****\n");
 }
 
//单链表的初始化
 
LinkedList LinkListInit() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请结点空间 
    if(L == NULL) 	//判断是否有足够的内存空间
	{  
        printf("申请内存空间失败\n");
    }
    L->next = NULL;                  //将next设置为NULL,初始长度为0的单链表 
 	return L;
}
 
 
	//单链表的建立（头插法）
	 
	 
	LinkedList ListCreatH() {
	    Node *L;
	    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
	    L->next = NULL;                      //初始化一个空链表
	    int i=0;
	    ElemType x;                         //x为链表数据域中的数据
	    while(i<10) {
	        Node *p;
	        p = (Node *)malloc(sizeof(Node));   //申请新的结点 
	        scanf("%d",&x);
	        p->data = x;                     //结点数据域赋值 
	        p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL 
	        L->next = p; 
	        i++;
	    }
	    return L; 
	} 
	 
	 
	//单链表的建立（尾插法）
	 
	LinkedList ListCreatT() {
	    Node *L;
		    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
		    L->next = NULL;                  //初始化一个空链表
		    Node *r;
		    r = L;                          //r始终指向终端结点，开始时指向头结点 
			int i=0   ;                   //x为链表数据域中的数据
		    for(i=0;i<10;i++)
			{ 		
				Node *p;
		        p = (Node *)malloc(sizeof(Node));   //申请新的结点 
		        scanf("%d",&p->data);
		        r->next = p;                 //将结点插入到表头L-->|1|-->|2|-->NULL 
		        r = p; 						//将r结点移动到最后一个节点
		    }
		    r->next = NULL;  				//让r结点的指针域置空 
		    return L; 
	}
 
 
//单链表的插入，在链表的第i个位置插入x的元素
/*初始条件：单链表L已存在，1<=i<=ListLength(L)*/
/*在L中第i个位置之前插入新的数据元素e，L的长度加1*/
LinkedList ListInsert(LinkedList L,int i,ElemType x) {
    LinkedList pre;                      //pre为前驱结点 
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
    	pre = pre->next;                 //查找第i个位置的前驱结点 
	}
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x; 
    p->next = pre->next;
    pre->next = p;
    return L;                           
} 
 
 
//单链表的删除，在链表中删除第i个数据元素
/*初始条件：单链表L已存在，1<=i<=ListLength(L)*/
/*操作结果：删除L的第i个数据元素，L的长度减1*/ 
LinkedList ListDelete(LinkedList L,int i)
{
    LinkedList p,q;                   
	int j=2; 
    p = L->next;
    while(p->next&&j<i) {              //查找第i个位置 
        p=p->next;
		++j;
    }
    if(!(p->next)||j>i)			//第i个元素不存在
		printf("第i个元素不存在\n");
    q=p->next;				
	p->next=q->next;			//将q的后继赋值给p的后继 
    free(q);
    return L;
} 
 
//单链表的查找
/*初始条件：单链表L已存在，1<=i<=ListLength(L)*/
/*操作结果：用e打印中第i个数据元素的值*/ 
 void GetElem(LinkedList L)
 {
 	int i,j=1;		//j为计数器 
 	int *e;
 	LinkedList p;		//声明一结点p 
 	printf("请输入查找的位置:");
 	scanf("%d",&i);
 	p=L->next;		//让p指向链表L的第一个结点 
 	while(p&&j<i)
 	{
 		p=p->next;		//让p指向下一个结点 
 		++j;	
 	}
 	if(!p||j>i)
 		printf("第i个元素不存在");		//第i个元素不存在 
 	*e=p->data;				//取第i个元素的数据 
 	printf("%d\n",*e);
 }
 
 
int main() {
    LinkedList list,start;
 	printf("请输入单链表的数据：\n"); 
    list = ListCreatT();
    printf("成功创建链表：\n");
    for(start = list->next; start != NULL; start = start->next) {
    	printf("%d ",start->data);
	}
    printf("\n");
    menu();
    int i,option;
    ElemType x;
    do{
		printf("请输入选项：");
		scanf("%d",&option);
		switch(option)
		{
		   	case 1:
			{
			   	printf("请输入插入数据的位置：");
				scanf("%d",&i);
				printf("请输入插入数据的值：");
				scanf("%d",&x);
				ListInsert(list,i,x);
				printf("插入后的链表为：");
				//打印链表 
				for(start = list->next; start != NULL; start = start->next)
				{
					printf("%d ",start->data);
				}
				printf("\n");
					  break;
				}
			case 2:
			{
				int i; 
				printf("请输入删除的位置\n");
				scanf("%d",&i);
				ListDelete(list,i);
				printf("删除后的链表为：");
				//打印链表
				for(start = list->next; start != NULL; start = start->next)
				{
					printf("%d ",start->data);					
				}
				printf("\n");
				break;		
			}
			case 3:GetElem(list);			break;		
			case 0:break;	
			default:printf("输出错误！\n");break;
	   } 		
	}while(option>0);
    return 0;
}

8.编译结果

---

三、总结

常考的知识点：链表的插入，删除的关键语句、在头部插入，中间插入，尾部插入的时间复杂度，以及单链表和顺序表的区别

在链表尾部添加（addLast()）需要从头遍历，时间复杂度为O(n)
在链表头部添加（addFirst()），时间复杂度为O(1)
在链表任意位置添加(add(int index,E e))，平均情况下为O(n/2)=O(n)

单链表和顺序表的区别：

顺序表的优点：

1. 元素可以随机存储
2. 节省存储空间
3. 元素位置可用一个简单、直观的公式表示并在常量时间内访问

                                                                顺序表的缺点：

1. 在作插入或删除操作时，需要移动大量元素

单链表的优点：

1. 链表是线性表的链式存储表示
2. 链表中逻辑关系相邻的元素不一定在存储位置上相连，用一个链(指针)表示元素之间的邻接关系即：链表中结点的逻辑顺序和物理顺序不一定相同
3. 在插入和删除时，不需要大量移动数据元素，只需找到结点，对该结点做删除和插入的工作即可

                                                                      单链表的缺点：

在访问第i个位置的元素时，需要遍历链表，不能想顺序表一样直接找到第i个位置。