数据结构与算法——链表

1、定义

#include <stdio.h>
typedef struct Node{
	Elem Type date;
	struct Node *next; 
}LNode,*LinkList;

2、储存——头插法

//储存——头插法：
LinkList CreateFromHead(){
	LinkList L;
	LNode *s;
	int x;
	int flag = 1;
	L = (Linklist)malloc(sizeof(LNode));
	L->next = NULL;
	scanf("%d",&x);
	while(x!=-1){
		s = (LNode*)malloc(sizeof(LNode));
		s -> data = x;
		s -> next = L -> next;
		L -> next = s;
		scanf("%d",&x);
	}
	return L;
}

3、储存——尾插法：

LinkList CreateFromTail(){
	LinkList L;
	LNode *r,*s;
	int x;
	L = (LNode*)malloc(sizeof(LNode));
	L -> next = NULL;
	r = H;
	scanf("%d",&x);
	while(x!=-1){
		s = (LNode*)malloc((sizeof(LNode));
		s -> data = x;
		s -> next = r -> next;
		r -> next = s;
		r = s;
		scanf("%d",&x);
	}
	r -> next  = NULL;
	return L;
}

4、插入

//插入结点
//要在头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点由指针s指示，其数据与的值为e，并修改第i-1个结点的指针使其指向s，使s的指针指向第i个结点
void INsList(LinkList L,int i,ElemType e){
	LNode *pre ,*s;
	int k = 0;
	pre = L;
	while(pre!=NULL&&k<i-1){
		pre = pre -> next;
		k++;
	}
	if(k!=i-1){
	printf("插入错误！！！");
	return ;
	}
	s = (Node*)malloc(sizeof(Node));
	s -> data = e;
	s -> next = pre -> next;
	pre -> next = s;
}

5、删除

//单链表删除
//欲在带头结点的单链表L中删除第1个结点,则首先要通过计数方式找到第1-1个结点并使pre指向第1-1个结点,而后删除第1个结点并释放结点空间。
void DelList(LinkList L,int i,ElemType *e){
	LNode  *pre,*r;
	pre = L;
	int k = 0
	while(pre -> next != NULL && k<i-1){
		pre = pre -> next;
		k++;
	} 
	if(k != i-1){
		printf("删除错误！！！");
		return ERROR;
	}
	r = pre -> next;
	pre -> next = pre -> next -> next;
	free(r);
	return OK;
}

Q：Question

Q1、在单链表L中，做插入运算InsList(L,i,e)时，为什么一定要先找插入位置i的直接前驱元素的地址pre,直接找到第i个位置元素的地址不可以吗？
A：不可以，因为单链表中每个结点会存储直接后继元素的地址，不存储直接前驱元素的地址。因此做插入运算InsList(L,i,e)时，不找插入位置i的直接前驱元素的地址pre会丢失前面结点的信息，使链断开。

Q2、对于单链表而言，头指针和头结点哪一个是必须的？
A：头指针

Q3、在单链表中，有无显式表示出单链表的长度？在单链表中如何得到表长度？
A：没有显式表示出单链表的长度，需要从头到尾遍历单链表得到表长度。

Q4、单链表中，已知结点p,那么从结点p出发是否可以找到其直接前驱结点？
A：不可以，因为单链表只能按从头到尾的顺序访问，不能逆序访问前驱结点

Q5、带头结点的单链表和不带头结点的单链表有何区别？
A:带头节点的单链表，在进行插入和删除操作时，无论删除和插入的位置如何，不需要修改head的值，不带头结点的单链表则需要修改head的值。

Q6、带头结点的单链表有什么优点？
A：带头结点的单链表在进行添加删除操作时，相比于不带头结点的单链表相比，要更加方便，因为不需要对是否头结点进行专门的处理

PS：

1、单链表的头插建立算法也称为反向建立单链表。
2、单链表的插入、删除效率优于顺序表。