数据结构专升本第二周Word下载.docx
《数据结构专升本第二周Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构专升本第二周Word下载.docx（11页珍藏版）》请在冰点文库上搜索。
/*结点的数据域*/
structnode*next;
/*结点的指针域*/
}ListNode;
typedefListNode*LinkList;
1、建立
头插法建立单链表
LinkListCreateListF（void）
{charch;
LinkListhead;
/*头指针*/
ListNode*s;
/*工作指针*/
head=NULL;
/*链表开始为空*/
ch=getchar（）;
while（ch!
='
\n'
）
{s=（ListNode*）malloc（sizeof（ListNode））;
/*生成新结点*/
s->
data=ch;
next=head;
head=s;
ch=getchar（）;
}
returnhead;
/*返回头指针*/
}
尾插法建立单链表
LinkListCreateListR（void）
ListNode*s,*r;
r=NULL;
/*链表尾指针开始为空*/
while（（ch=getchar（））!
if（head==NULL）
head=s;
/*新结点插入空表*/
elser->
next=s;
r=s;
if（r!
=NULL）
r->
next=NULL;
/*对于非空表，将尾结点指针域置空*/
在链表开始之前附加一个头结点的优点：
1）由于开始结点的位置被存放在头结点的指针域中，所以链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理；
2）无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表处理一致。
LinkListCreateListR1（void）
LinkListhead=（ListNode*）malloc（sizeof（ListNode））;
r=head;
/*尾指针初值指向头结点*/
r->
以上三个算法的时间复杂度均为O（n）
2、查找
LinkListGetNode（LinkListhead,inti）
{/*在带头结点的单链表head中查找第i个结点*/
intj;
ListNode*p;
p=head;
j=0;
/*从头结点开始扫描*/
while（p->
next&
&
j<
i）/*顺指针向后扫描，直到链表尾或找到为止*/
{p=p->
next;
j++;
if（i==j）
returnp;
/*找到了第i个结点*/
else
returnNULL;
/*找不到满足条件的结点*/
LinkListLocateNode（LinkListhead,DataTypekey）
{/*在带头结点的单链表head中查找其值为key的结点*/
ListNode*p=head->
/*从开始结点比较*/
while（p&
p->
data!
=key）/*直到p为NULL或p->
data是key为止*/
p=p->
/*扫描下一结点*/
returnp;
以上两个算法的时间复杂度均为O（n）
3、插入
voidInsertList（LinkListhead,DataTypex,inti）
{/*将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上*/
ListNode*p,*s;
p=GetNode（head,i-1）;
/*寻找第i-1个结点*/
if（p==NULL）
{
printf（"
插入位置非法\n"
）;
exit（0）;
s=（ListNode*）malloc（sizeof（ListNode））;
s->
data=x;
next=p->
p->
4、删除
/*单链表的删除*/
voidDeleteList（LinkListhead,inti）
{/*删除带头结点的单链表中的第i个结点*/
ListNode*p,*r;
if（p==NULL||p->
next==NULL）
删除位置非法\n"
r=p->
next=r->
free（r）;
/*释放第i个结点*/
以上算法的时间复杂度都为O（n）
2.3.2循环链表
循环链表（CircularLinkedList）：
就是将单向链表中的最后一个结点的指针指向链表中第一个结点，使整个链表构成一个环形。
循环链表特点：
从链表中的任意一个结点出发都可以找到表中其他结点。
循环链表的运算和单链表基本一样，差别在于：
当需要从头到尾扫描整个链表时，是否到表尾的条件不同。
在单链表中判断某结点链域值是否为“空”（p->
next!
=NULL||p->
next），在循环链表中则判断某结点的链域值是否等于头指针（p->
=head）。
在用头指针表示的单循环链表中，找开始结点的时间是O
（1），找终端结点的的时间为O（n），实用中多采用尾指针表示单循环链表。
2.3.3双向链表
双（向）链表（DoubleLinkedList）：
有两种不同方向链的链表称为双向循环链表。
双链表特点：
双链表的每一个结点除含数据域外，还有两个指针域，一个指针指向其前驱结点，另一个指针指向其后继结点。
可以给双链表加一表头结点。
双链表可以循环，也可以不循环。
优点：
这样的设计弥补了简单链表的单向性的缺陷（单链表的NEXT操作的时间复杂度是O
（1），PRIOR操作的时间复杂度是O（n））。
双链表和单链表相比，每一个结点增加了一个指针域，双向链表虽然多占用了空间，但它给数据运算带来了方便。
双链表的基本运算：
存储结构：
typedefstructDuLNode{
ElemTypedata;
structDuLNode*prior;
structDuLNode*next;
}DuLNode,*DuLinkList;
1、插入
voidDInsertBefore（DLinkListp,DataTypex）
{//将值为x的新结点插入到带头结点的双链表的*p之前
DListNode*s=（DListNode*）malloc（sizeof（DListNode））;
//生成新结点
prior=p->
prior;
next=p;
prior->
prior=s;
2、删除
//双链表的删除
voidDDeleteNode（DLinkListp）
{//删除带头结点双链表中的*p结点
next->
free（p）;
2.4顺序表和链表的比较
一、基于空间的考虑
1、空间分配
顺序表是静态分配，链表是动态分配，若线性表的长度变化较大，难以估计其存储规模，采用链表为好。
2、存储密度
顺序表的存储密度为1，而链表小于1，节约存储空间，采用顺序表为好。
二、基于时间的考虑
若对线性表的操作主要是进行查找，采用顺序表为好；
若对线性表频繁进行插入和删除操作，采用链表为好。
习题：
1、带头结点：
voidInverseList（LinkList*head）
{ListNode*p,*t,*h;
h=（*head）->
p=h->
h->
while（p!
{t=p->
next=h;
h=p;
p=t;
（*head）->
不带头结点：
p=（*head）->
h=*head;
*head=h;
2、voidInsertSortList（LinkList*L,DataTypex）
{LinkNode*p,*s;
p=*L;
if（p==NULL||x>
=p->
data）
{s=（ListNode*）malloc（sizeof（ListNode））;
*L=s;
{while（p->
=NULL&
x<
p=p->
s=（ListNode*）malloc（sizeof（ListNode））;
3、带头结点
intListlength（LinkListL）
{inti=0;
for（p=L->
p;
next）
i++;
return（i）;
4、LinkListConnect（LinkListL1,LinkListL2）
{LinkNode*p,*q;
p=L1;
q=L2->
while（p->
next=q;
free（L2）;
returnL1;
5、voidMergeList（LinkListA,LinkListB,LinkList*C）
{LinkNode*qa,*qb,*qc;
qc=*C=A;
qa=A->
qb=B->
while（qa&
qb）
{if（qa->
data<
qb->
{qc->
next=qa;
qc=qc->
qa=qa->
next=qb;
qb=qb->
qc->
next=qa?
qa:
qb;
free（B）;
升级会员 