首页 计算机科学 数据结构 线性表

# 单链表

1. 概念

结点：数据元素及直接后继的存储位置组成一个数据元素的存储结构称为一个结点。
结点包括两个域：
数据域：存储元素本身的信息
指针域：存储直接后继的位置，指针域中存储的信息称作指针或链

单链表：由于链表的每个结点中只包含一个指针域，故又称线性链表或单链表
头指针：头指针指示链表中第一个结点的存储位置。

由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为 “空”(NULL)

链式存储结构特点: 存储空间可以不连续。不要求逻辑上相邻的元素在物理位置上也相邻。数据元素间逻辑关系由指针域确定。

头指针 (Head pointer)：头指针指示链表中第一个结点的存储位置
头结点：为了操作方便，在第一个结点之前附设的一个结点
首元结点：链表中存储信息的第一个结点

2. 定义

typedef struct node{
	DataType data;
	struct node *next;
}listnode,*LinkList;
LinkList H; // 定义头指针为 H，表示整个链表
listnode *p; //p 为指向结点的指针变量，工作指针
3. 操作
1) 求单链表长度
int Length_LinkList(LinkList L)
{
	listnode *p;
	p=L->next;
	int j=0; // 计数器
	while(p) //p!=NULL
	{
		p=p->next;
		j++;
	}
	return j;
}
2) 单链表查找
// 按序号查找 (查找第 i 个元素)
Listnode * GetP (LinkList L, int i)
{ 	int j; // 计数器
	Listnode *p=L ;
	j=0;
	while (p!=NULL && j<i){ 
        p=p->next;
		j++;
	}
	if (i==j) return p;
	else return NULL;
}
// 按值查找
listnode * Locate_LinkList(LinkList L,DataType e)
{
	listnode *p=L->next;
	while(p !=NULL && p->data!=e)
		p=p->next;
	return p;
}
// 按值查找操作的时间复杂度为 O (n)。
3) 单链表插入
假设 s 为指向结点 x 的指针，则插入步骤为：
修改 s 指针域，使其指向 p 结点的后继结点:s->next=p->next
修改 p 指针域，使其指向新结点 s: p->next＝s
void ListInsert_L(LinkList &L, DataType x，int i)
{ // 在带头结点的单链线性表 L 中第 i 个位置之前插入元素 x
	ListNode *p; p=L; int j=0;
	while(p!=NULL && j<i-1) // 寻找第 i-1 个结点
	{ 
        p= p->next; j=j+1;}
		if (j==i-1){ // 若存在
			s=(linklist *) malloc (sizeof (struct node ));
			s->data=x; //③
			s->next=p->next; //④
			p->next=s; //⑤
		}
		else error (“不存在第i-1个位置”);
}
4) 单链表删除
先找到 p 的前驱结点 q
删除 p 结点，修改 q 结点指针域 q->next＝p->next
// 删除第 i 个结点
void DeleteList(LinkList L, int i)
{
    ListNode *p，*q;
    while(p->next!=NULL&&j<i-1){ // 查找 i-1 的结点
    	p=p->next;j++;
    }
    if (p->next==NULL || j>i-1) return error;// 位置不合理
    q=p->next; //②
    p->next=q->next; //③将 ai 从链上摘下
    free(q); //④ 释放结点 ai
}
5) 建立单链表
头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和
输入数据的顺序不一致。若希望两者次序致，可采用尾插法。该方法
是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针 r, 使其
始终指向当前链表的尾结点。如下图所示：
//(头插法建立单链表)
LinkList CreatListF(LinkList &L){
    // 从表尾到表头逆向建立单链表 L, 每次均在头结点之后插入元素
    ListNode *s;int x;
    L=(LinkList)malloc(sizeof(ListNode )); // 创建头结点
    L->next=NULL; // 初始为空链表
    scanf("%d", &x); // 输入结点的值
    while(x!= 9999){ // 输入 9999 表示结束
        s=(ListNode *) malloc(sizeof(ListNode )); // 创建新结点
        s->data=x;
        s->next=L->next;
        L->next=s; // 将新结点插入表中，L 为头指针
        scanf("%d", &x);
	} //while 结束
	return L;
}
//（尾插法建立单链表)
LinkList CreatListR(LinkList &L){
    // 从表头到表尾正向建立单链表 L, 每次均在表尾插入元素
    int x; // 设元素类型为整型
    L=(LinkList)malloc(sizeof(ListNode));
    ListNode *s, *r = L; //r 为表尾指针
    scanf ("%d"，&x); // 输入结点的值
    while(x!=9999){ // 输入 9999 表示结束
        s=(ListNode *)malloc(sizeof(ListNode );
        s->data=x; r->next=s;
        r=s; //r 指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL; // 尾结点指针置空
    return L;
}
6) 单链表逆置
Void nizhi(Linklist &L)
{
    ListNode *p, *s;
    P=L->next; L->next=NULL; // 变成两个链表
    While(p!=NILL){
        s=p;
        p=p->next;
        s->next=L->next; // 头插法
        L->next = s; // 头插法
    }
}
7) 单链表合并
// 将两个有序链表并为一个有序链表
void Linklist_Merge(LinkList &La, LinkList &Lb, LinkList &Lc) {
// 已知单链线性表 La 和 Lb 的元素按值非递减排列。
// 归并 La 和 Lb 得到新的单链线性表 Lc,Lc 的元素也按值非递减排列。
    ListNode *pa, *pb, *crear,*s;
    //crear 指向 LC 的尾巴
    pa = La->next; pb = Lb-> next; crear = Lc; 
    while (pa!=NULL && pb!=NULL) {
    	if (pa->data <= pb->data) {
       		s=pa; pa=pa->next;
        	s->next = crear->next; crear->next = s;
            crear = crear->next; 
        }else{
            s=pb; pb=pb->next;
    		s->next = crear->next;
            crear->next = s;
            crear = crear->next;
        }
    }
    if(pa!=NULL)crear->next = pa;
    else crear->next = pb;
} // MergeList_L
-->