数据结构专升本第二周Word下载.docx

1、 /*结点的数据域*/ struct node *next; /*结点的指针域*/ListNode;typedef ListNode *LinkList;1、 建立头插法建立单链表LinkList CreateListF（void） char ch; LinkList head; /*头指针*/ ListNode *s; /*工作指针*/ head=NULL; /*链表开始为空*/ ch=getchar（）; while （ch!=n） s=（ListNode *）malloc（sizeof（ListNode）; /*生成新结点*/ s-data=ch;next=head; head=s; c

2、h=getchar（）; return head; /*返回头指针*/尾插法建立单链表LinkList CreateListR（void） ListNode *s,*r; r=NULL; /*链表尾指针开始为空*/ while （ch=getchar（）! if （head=NULL） head=s; /*新结点插入空表*/ else r-next=s; r=s; if （r!=NULL） r-next=NULL; /*对于非空表，将尾结点指针域置空*/在链表开始之前附加一个头结点的优点：1） 由于开始结点的位置被存放在头结点的指针域中，所以链表的第一个位置上的操作和在表的其他位置上的操作一致

3、，无须进行特殊处理；2） 无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表处理一致。LinkList CreateListR1（void） LinkList head=（ListNode *）malloc（sizeof（ListNode）; r=head; /*尾指针初值指向头结点*/ r-以上三个算法的时间复杂度均为O（n）2、查找LinkList GetNode（LinkList head,int i）/*在带头结点的单链表head中查找第i个结点*/ int j; ListNode *p; p=head;j=0; /*从头结点开始扫描*/while （p-next &

4、jnext; j+; if （i=j） return p; /*找到了第i个结点*/ else return NULL; /*找不到满足条件的结点*/LinkList LocateNode（LinkList head,DataType key）/*在带头结点的单链表head中查找其值为key的结点*/ ListNode *p=head- /*从开始结点比较*/ while （p&p-data!=key） /*直到p为NULL或p-data是key为止*/ p=p- /*扫描下一结点*/ return p;以上两个算法的时间复杂度均为O（n）3、插入void InsertList（LinkLis

5、t head,DataType x,int i）/*将值为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、删除/*单链表的删除*/void DeleteList（LinkList head,int i）/*删除带头结点的单链表中的第i个结点*/ ListNode *p,*r; if（

6、p=NULL|p-next=NULL）删除位置非法n r=p-next=r- free（r）; /*释放第i个结点*/以上算法的时间复杂度都为O（n）2.3.2 循环链表循环链表（Circular Linked List）：就是将单向链表中的最后一个结点的指针指向链表中第一个结点，使整个链表构成一个环形。循环链表特点：从链表中的任意一个结点出发都可以找到表中其他结点。循环链表的运算和单链表基本一样，差别在于：当需要从头到尾扫描整个链表时，是否到表尾的条件不同。在单链表中判断某结点链域值是否为“空”（p-next!=NULL|p-next），在循环链表中则判断某结点的链域值是否等于头指针（p-=

7、head）。在用头指针表示的单循环链表中，找开始结点的时间是O（1），找终端结点的的时间为O（n），实用中多采用尾指针表示单循环链表。2.3.3 双向链表双（向）链表（Double Linked List）：有两种不同方向链的链表称为双向循环链表。双链表特点：双链表的每一个结点除含数据域外，还有两个指针域，一个指针指向其前驱结点，另一个指针指向其后继结点。可以给双链表加一表头结点。双链表可以循环，也可以不循环。优点：这样的设计弥补了简单链表的单向性的缺陷（单链表的NEXT操作的时间复杂度是O（1），PRIOR操作的时间复杂度是O（n）。双链表和单链表相比，每一个结点增加了一个指针域，双向链表虽

8、然多占用了空间，但它给数据运算带来了方便。双链表的基本运算：存储结构：typedef struct DuLNode ElemType data; struct DuLNode *prior;struct DuLNode *next;DuLNode,*DuLinkList;1、 插入void DInsertBefore（DLinkList p,DataType x）/将值为x的新结点插入到带头结点的双链表的*p之前 DListNode *s=（DListNode *）malloc（sizeof（DListNode）; /生成新结点prior=p-prior;next=p;prior-prior=

9、s;2、 删除/双链表的删除void DDeleteNode（DLinkList p）/删除带头结点双链表中的*p结点next- free（p）;2.4 顺序表和链表的比较一、基于空间的考虑1、空间分配 顺序表是静态分配，链表是动态分配，若线性表的长度变化较大，难以估计其存储规模，采用链表为好。2、存储密度 顺序表的存储密度为1，而链表小于1，节约存储空间，采用顺序表为好。二、基于时间的考虑若对线性表的操作主要是进行查找，采用顺序表为好；若对线性表频繁进行插入和删除操作，采用链表为好。习题：1、带头结点：void InverseList （LinkList *head） ListNode *p

10、, *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、void InsertSortList （LinkList *L, DataType x） LinkNode *p, *s; p=*L; if （p=NULL|x=p-data） s=（ListNode *） malloc （sizeof （ListNode）; *L=s; while （p-=NULL &x s=（ListNode *） malloc （sizeof （ListNode

11、）;3、 带头结点int Listlength （LinkList L） int i=0; for （p=L- p;next） i+; return（i）;4、 LinkList Connect （LinkList L1, LinkList L2） LinkNode *p,*q; p=L1; q=L2-while （ p-next=q; free（L2）; return L1;5、 void MergeList （LinkList A, LinkList B , LinkList *C） LinkNode *qa, *qb, *qc; qc=*C=A; qa=A- qb=B- while （qa &qb） if （qa-data qc-next=qa; qc=qc- qa=qa-next=qb; qb=qb- qc-next=qa? qa:qb; free（B）;