链表

线性表链式存储结构通过“链”建立起数据元素之间的逻辑关系，这种用链接方式的线性表简称链表（Link List），在链表上做插入、删除运算不需要移动数据元素。

顺序表和链表的比较

顺序表的优点：

（1）用数组存储数据元素，操作方法简单，容易实现。

（2）不用为表示结点间的逻辑关系而增加额外的存储开销。

（3）存储密度高。

（4）可以随机访问（使用下标访问）。

顺序表的缺点：

（1）做插入，删除操作时，要大量地移动数据元素，效率比较低。

（2）要占用连续的存储空间，且大小要固定，不适合动态存储。

链表的优点：

（1）插入、删除操作简单

（2）大小可变，适合动态存储。

链表的缺点：

（1）查找效率低。

（2）不支持随机存储。

#include<stdio.h>#include<stdlib.h>/*结点定义 */typedef int ElemType;typedef struct node{	ElemType data;			//数据域	struct node *next; 		//指针域 }LNode, *LinkList;  /* 单链表的建立 单链表的建立有两种方法：在链表的头部插入结点和在链表的尾部插入结点（头插法和尾插法）。  */ //头插法建立单链表 LinkList creat_LinkList1(){ 	LinkList H = (LinkList)malloc(sizeof(LNode));	//生成头结点。	LNode *s;	H->next = NULL;										int x;											//设数据元素的类型为int	scanf("%d", &x);	while(x != -1){		s = (LinkList)malloc(sizeof(LNode));		s->data = x;		s->next = H->next;		H->next = s;		scanf("%d", &x);	}	 return H; } //尾插法建立单链表 LinkList creat_LinkList2(){ 	LinkList H = (LinkList)malloc(sizeof(LNode)); 	H->next = NULL; 	LNode *s, *r = H; 	int x; 	scanf("%d", &x); 	while(x != -1){ 		s = (LinkList)malloc(sizeof(LNode)); 		s->data = x; 		s->next = r->next; 		r->next = s; 		r = s; 		scanf("%d", &x);	 }	 return H; }    //求表长 /* 思路：设一个指针p和计数器length，初始化使p指向头结点H，j = 0。若p所指结点还有后继结点， p向后移动，计数器加1（长度不包括头结点），重复上述过程，直到p->next=NULL为止。  */  int length_LinkList(LinkList H){ 	LNode *p = H; 	int length = 0; 	while(p->next != NULL){ 		p = p->next; 		length++;	 }	 return length; }   //查找操作 /* 按序号查找  思路：从链表的第一个元素结点开始判断当前结点是否是dik个，若是，则返回该结点的指针， 否则继续查找下一个，直到表结束为止。没有第k个节点是返回空。  */  LNode * get_LinkList(LinkList H, int k){ 	LNode *p = H;	 int j = 0;	 while(p->next != NULL && j < k){	 	p = p->next;	 	j++;	 } 	 if(j == k){	 	return p;	 }else{	 	return NULL;	 } }  /* 按值查找 思路：从链表的第一个元素结点开始=，判断当前结点的值是否等于x，若是，  返回该结点的指针，否则继续向后查找，直到表结束为止，若查找不到则返回空。  */ LNode * locate_LinkList(LinkList H, ElemType x) { 	LNode * p = H->next; 	while(p != NULL && p->data != x){ 		p = p->next;	 }	 return p; } //单链表的插入 //在单链表H的第i个位置上插入值为x的元素  int insert_LinkList(LinkList H, int i, ElemType x){ 	LNode *p, *s;	p = get_LinkList(H, i-1);	if(p == NULL){		PRintf("插入位置i错误");		return -1; 	} else{		s = (LinkList)malloc(sizeof(LNode));		s->data = x;		s->next = p->next;		p->next = s;		return 0;	} }  //删除操作  int del_LinkList(LinkList H, int i){ 	LinkList p, q; 	p = get_LinkList(H, i-1); 	if(p == NULL){ 		printf("第i-1个结点不存在"); 		return -1;	 }else{	 	if(p->next == NULL){	 		printf("第i个结点不存在");	 		return -1;		 }else{		 	q = p->next;		 	p->next = q->next;		 	free(q);		 	return 0;		 }	 } }  //单链表的倒置/*思路：链表建立时，采用尾插法建立的链表和输入的顺序相反。 */ void reverse(LinkList H){	LNode *p, *q;	p = H->next;	H->next = NULL;	while(p){		q = p;		p = p->next;		q->next = H->next;		H->next = q;	}}   void print_LinkList(LinkList H){ 	LinkList p = H->next; 	while(p != NULL){ 		printf("%d ",p->data); 		p = p->next;	 }	 printf("/n"); }  int main(void){	LinkList H = creat_LinkList2();	print_LinkList(H);//	int length = length_LinkList(H);//	printf("%d/n", length);//	LNode *p = get_LinkList(H, 5);//	if(p != NULL)//	printf("%d", p->data);//	insert_LinkList(H, 4, 4);//	print_LinkList(H);//	del_LinkList(H, 4);	reverse(H);	print_LinkList(H);	return 0;}