第三节 - 线性表的链式存储结构（三）
发布时间：2020-09-20 10:32来源：未知
第三节 线性表的链式存储结构（三）
3、插入运算
将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。
算法思想：先使p指向ai-1的位置，然后生成一个数据域值为x的新结点*s，再进行插入操作。
算法描述
void InsertList(LinkList head，int i，DataType X)
{ //在以head为头指针的带头结点的单链表中第i个结点的位置上
//插入一个数据域值为X的新结点
ListNode *p，*s；int j；
p=head；j=O;
while(p!=NULL&&j<i-1) //使p指向第i-1个结点
{p=p->next；++j；
}
if(p==NULL) //N入位置错误
{ printf("ERROR＼n"); return；
}
else
{ s=(ListNode*)malloc(Sizeof(ListNode)); //申请新结点
s->data=X；s->next=p->next； //进行插入
p->next=s;
}
}
算法分析：算法的时间复杂性是O（n）
真题选解
（例题·单选题）1、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为( )
A．O(1) B．O(n) C．O(m) D．O(m+n)
4、删除运算
将链表的第i个结点从表中删去。
算法思想：先使p指向ai-1的位置，然后执行p->next指向第i+1个结点，再将第i个结点释放掉。
算法描述
DataType DeleteList(LinkList head，int i)
{ //在以head为头指针的带头结点的单链表中删除第i个结点
ListNode *p，*s；
dataType x； int j；
p=head；j=O；
while(p!=NULL&&j<i-1) //使p指向第i-1个结点
{p=p->next j++；
}
if(p==NULL) //删除位置错误
{ printf("位置错误\n");
exit(O)； //出错退出处理
}
else
{ s=p->next; //s指向第i个结点
p->next=s->next; //使p->next指向第i+1个结点
x=s->data; //保存被删除结点的值
free(s)；return x; //删除第i个结点，返回结点值
}
}
算法分析：算法的时间复杂性是O（n）
真题选解
（例题·算法阅读题）1、阅读下面的算法
LinkList mynote(LinkList L) //L是不带头结点的单链表的头指针
{if(L&&L->next)
{q=L；L=L->next；p=L；
S1：while(p->next) p=p->next；
S2：p->next=q；
q->next=NULL；
}
return L；
｝
请回答下列问题：
(1)说明语句Sl的功能；
(2)说明语句组S2的功能；
(3)设链表表示的线性表为(a1，a2，…，an)，写出算法执行后的返回值所表示的线性表。
5、单链表上的运算举例
例：试写一个算法，将一个头结点指针为a的带头结点的单链表A分解成两个单链表A和B，其中头结点指针分别为a和b，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，并保持原来的相对顺序。
分析：遍历整个链表A，当遇到序号为奇数的结点时将其链接到A表上，序号为偶数结点时，将其链接到B表中，一直到遍历结束。
算法描述
void split(LinkList a， LinkList b)
{ //按序号奇偶分解单链表，注意b在调用该算法前是一个带头结点的空链表
ListNode *p，*r，*s;
p=a->next; //p指向表头结点,p负责扫描整个链表
r=a; //r指向A表的当前结点
s=b； //s指向B表的当前结点
while(p!=NULL)
{ r->next=p； //序号为奇数的结点链接到A表上
r=p； //r总是指向A链表的最后一个结点
p=p->next; //p指向原链表A中的偶数序号的结点
if(p)
{ s->next=p； //序号为偶数的结点链接到B表上
s=p； //s总是指向B链表的最后一个结点
p=p->next； //p指向原链表A中的奇数数序号的结点
}
}
r->next=s->next=NULL；
}
算法分析：算法要从头至尾扫描整个链表，算法的时间复杂性是O（n）
例：假设头指针为La和Lb的单链表(带头结点)分别为线性表A和B的存储结构，两个链表都是按结点数据值递增有序的。试写一个算法，将这两个单链表合并为一个有序链表Lc。
分析：设立三个指针pa、pb和pc，其中pa和pb分别指向La表和Lb表中当前待比较插入的结点，而pc则指向Lc表当前的最后一个结点，若pa->data≤pb->data，则将pa所指向的结点链接到pc所指的结点之后，否则将pb所指向的结点链接到pc所指的结点之后。
算法描述
LinkList MergeL．ist(LinkList La，LinkList Lb)
{ //归并两个有序链表La和Lb为有序链表Lc
ListNode *pa，*pb，*pc；
LinkList Lc;
pa=La->next; pb=Lb->next； //pa和pb分别指向两个链表的开始结点
Lc=pc=La； //用La的头结点作为的Lc头结点
while(pa!=NULL&&pb!=NULL)
{ if(pa->data<=pb->data)
{pc->next=pa; pc=pa； pa=pa->next；
} //将pa所指向的结点链接到pc所指的结点之后
else
{ pc->next=pb； pc=pb； pb=pb->next;
} //将pb所指向的结点链接到pc所指的结点之后
}
pc->next=pa!=NULL?pa：pb； //插入链表剩余部分
free(Lb)； //释放Lb的头结点
return Lc； //返回合并后的表
｝
算法分析：算法要从头至尾扫描两个链表，算法的时间复杂性是O（n）
真题选解
（例题·单选题）1、在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( )。
A．O (1)
B．O (n)
C．O (nlogn)
D．O (n2)
（例题·算法阅读题）2、设有单链表类型定义如下：
typedef struct node {
int data;
struct node *next;
} *LinkList;
阅读下列算法，并回答问题：
void f33(LinkList head, int A, int B)
{
LinkList p=NULL;
while(head!=NULL)
{
if(head->data>A&&head->data<B)
p=head;
head=head->next;
}
if (p!=NULL)
printf("%d\n",p->data);
}
(1)已知链表h如下图所示，给出执行f33(h，5，8)之后的输出结果；
(2)简述算法f33的功能。
