数据结构-链表之单链表

╰+攻爆jí腚メ 2022-05-25 05:20 313阅读 0赞

单链表即每个节点都存在数据域和指针域（特殊节点除外），每个节点都一个直接前驱节点和直接后继节点（头节点无前驱，尾节点无后继），简单来说就是上一个节点的指针域中存放了下一个节点的地址，因此可以实现层层节点依次查找，时间复杂度为O(n)，这也就是相对顺序表而言的缺点，但是对于频繁的插入和删除节点却是相对于顺序表的优点，除了首次查询为O(n)外，插入和删除都是O(1)；

由于顺序表存储单元和长度都是固定的所以可以直接定位到需要查找的元素查找时间复杂的为O(1)，删除和插入会导致其它单元的位置移动所以时间复杂度为O(n)。

接下来介绍下单链表中简单的基本操作实现：

//声明一个单链表结构体
    typedef struct LNode {
    	int data;		//数据域，数据域的类型为泛型（ElementType）
    	LNode *next;	//指针域,指向下一个node的地址
    }LNode,*LinkList;	//声明2个结构体别名（结构体别名和结构体指针别名），方便在外部直接通过别名定义该结构体类型的变量

头插法创建单链表：

/*
    function:头插法创建单链表即将节点依次插入到head节点之后
    */
    LinkList headInsertList(LinkList &L) {
    	LNode *s;
    	int x;
    	L =(LinkList)malloc(sizeof(LNode)); //开辟一块空间,创建头节点
    	L->next = NULL;//初始化空链表
    	scanf_s("%d", &x);//控制台首次输入节点数据
    	while (x != 9999) {
    		s =(LinkList)malloc(sizeof(LNode));//创建一个新节点
    		s->data = x;//指定新节点的数据域
    		s->next = L->next;//指定新节点的指针域
    		L->next = s;//头节点指向新节点
    		scanf_s("%d", &x);//控制台依次输入节点数据
    	}
    	return L;
    }

尾插法创建单链表：

/*
    尾插法创建单链表即将节点依次插入到链表的尾部
    */
    LinkList endInsertList(LinkList &L) {
    	LNode *s;//定义需要创建的节点指针
    	LNode *r;//定义尾节点指针
    	L = (LinkList)malloc(sizeof(LNode));//开辟一块空间,创建头节点
    	r = L;//初始化尾节点为头节点
    	int x;
    	scanf_s("%d", &x);
    	while (x != 9999) {
    		s = (LinkList)malloc(sizeof(LNode));//开辟一块空间存储需要创建的节点
    		s->data = x;
    		//s->next = NULL;	//清空尾节点的指针域
    		r->next = s;
    		r = s;
    		scanf_s("%d", &x);
    	}
    	r->next = NULL;		//清空尾节点的指针域
    	return L;
    }

按序号查找节点：

/*
    按序号查找法
    */
    //*getElem表示返回节点指针类型，不加*则表示返回节点
    LNode *getElemByIndex(LinkList L, int i) {
    	LNode *p = L->next;//把头节点赋值给p
    	int j = 1;//表示从1开始查找
    	if (i < 1) {
    		//线性表下标从1开始
    		return NULL;
    	}
    	//遍历查找：下一个节点存在且还未到达查找点
    	while (p && j<i)
    	{
    		p = p->next;
    		j++;
    	}
    }

按值查找表节点：

/*
    按值查找表节点
    e:需要查找的值，泛型表示法（伪代码）：ElemetnType e，这里简单表示为int
    */
    LNode *getElemByValue(LinkList L, int e) {
    	LNode *q = L->next;//获取头节点
    	int s = q->data;
    	//遍历查找
    	while (q != NULL && s != e)
    	{
    		q = q->next;
    		s = q->data;
    	}
    	return q;
    }

在指定的位置i处插入节点：

/*
    function:插入节点，在指定的位置i处插入节点
    i:需要插入的位置
    e:需要插入的节点
    */
    LinkList insertAtIndex(LinkList &L, int i, LNode *e) {
    	if (i < 1) {
    		return NULL;
    	}
    	LNode *p = L->next;//获取头节点
    	int j = 1;
    	//查找需要插入节点的前驱节点
    	while (p != NULL && j < i-1) {
    		p = p->next;
    	}
    	e->next = p->next;
    	p->next = e;
    }

删除指定的节点:

/*
    删除指定的节点
    i:需要删除的节点位置
    */
    LNode *deleteLNode(LinkList &L,int i) {
    	//查找节点
    	LNode *p = L->next;//获取头节点
    	LNode *q;//需要删除的节点
    	int j = 1;
    	while (p != NULL && j < i-1) {
    		//找到需要删除节点的上一个节点
    		p = p->next;
    		j++;
    	}
    	if (p == NULL) {
    		//没找到
    		return NULL;
    	}
    	q = p->next;
    	p->next = q->next;
    	free(q);//释放删除节点的空间
    	return q;
    }

求链表长度:

/*
    求链表长度即依次遍历累加求和
    */
    int getLength(LinkList &L) {
    	LNode *p = L->next;//获取头节点
    	int j = 1;
    	while (p != NULL) {
    		p = p->next;
    		j++;
    	}
    	return j;
    	
    }

以上为线性表链表中单链表的基本操作。