2. 数据结构——单链表的主要操作(考研专业课学习)

1.内容

单链表的初始化、求长、按位查找、按值查找、插入节点、删除节点、头插法和尾插法建立单链表，以及其部分时间复杂度的分析。

2. 主要功能代码

#include<stdio.h>
#include<stdlib.h> 
 
//函数结果状态代码
#define OK 1
#define OVERFLOW -2
#define ERROR 0
#define MAXSIZE 100
 
typedef int ElemType;  //顺序表每个数据元素存储类型
typedef int Status; 
 
typdef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode *, LinkList;
 
 
//1. 单链表的初始化
Status InitList(LinkList &L){
//	L=new LNode;  //生成节点作为头节点
	L=(LNode*)malloc(sizeof(LNode));
	L->next=NULL;
	//如果不带头节点
//	L=NULL; 
	return OK;
} 
 
//2.求表长(遍历整个链表)
//时间复杂度O(n) 
Status Length(LinkList L){
	int len=0;
	LinkList p=L;  
	while(p->next!=null){
		p=p->next;
		len++;
	}
	return len; 
} 
 
//3. 按序号查找结点(查找第i个位置的指针) 
//时间复杂度O(n) 
LNode* GetElem(LinkList L,int i){
	LinkList p=L;
	int j=0;  //临时记录位置
	while(p!=NULL&&j<i){  //查看当前指针是否指向空 
		p=p->next;
		j++;
	}
	return p;   //返回第i个节点的指针或者NULL(NULL可能是i不合法) 
}
 
//4. 按值查找表节点
//时间复杂度O(n) 
LNode *LocateElem(LinkList L,Elemtype e){
	LinkList p=L->next;
	while(p!=NULL&&p->data!=e){   //从第一个节点开始查找 
		p=p->next;
	}
	return p; 
} 
 
//5.插入节点操作(在第i个位置插入节点e->前插)
//时间复杂度O(n) 
Status ListInsert(LinkList &L,int i,ElemType e){
	LinkList p=L;
	int j=0;  //访问的位置 
	//找到L的第i-1个位置
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++; 
	}
	if(j==NULL)
		return ERROR;  //超出范围
	LNode *s=(LNode*)malloc(sizeof(LNode));  //重新开辟一个节点
	s->data=e;
	s->next=p->next;
	p->next=s;
	return OK; 
} 
 
//6.删除节点操作(删除第i个位置节点，并将其值赋值给e)
//时间复杂度O(n) 
Status ListDelete(LinkList &L,int i,Elemtype &e){
	LinkList p=L;
	int j=0;
	//找到第i-1节点 
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++;
	}
	if(p==NULL||p->next==NULL)	
		return ERROR;
	LNode * q=p->next;
	e=q->data;
	p->next=q->next;
	free(q);  //记得释放q的资源 
	return OK; 
} 
 
//头插法建立单链表->链表生成与输入值呈逆序 
//每个结点插入时间O(1),长度为n的链表总时间复杂度为O(n) 
Status List_HeadInsert(LinkList &L){
	LNode * s;
	int x;
	//初始化链表
	L=(LNode*)malloc(sizeof(LNode));
	L->next=NULL; 
	scanf("%d",&x);	 
	while(x!=9999){   //9999为结束标志 
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		s->next=L->next;
		L->next=s; 
		scanf("%d",&x);
	}
	return OK;
} 
 
//尾插法建立单链表->顺序
//每个结点插入时间O(1),长度为n的链表总时间复杂度为O(n) 
Status List_TailInsert(LinkList &L){
	LNode *s;
	int x;
	L=(LNode*)malloc(sizeof(LNode));
	L->next=NULL;
	LNode *r=L;  //r指针用于指向链表的最后一个元素 
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		s->next=NULL;  //防止指针乱指 
		r->next=s;
		r=s;    //r指向新的表尾指针 
		scanf("%d",&x);
	}
	return OK; 
}