数据结构第二章线性表Word格式.docx

1、c顺序表的存储结构定义：形式：define MAXNUM 100DataType elementMAXNUM;Int n;形式2：struct SeqList DataType elementMAXNUM;int n; 比较这两种定义顺序表的方法，后者概念较为清晰，符合数据抽象的原则，今后我们的定义一般采用后者。 在实际应用中，为了使用方便，通常定义一个struct SeqList类型的指针类型： typedef struct SeqList *PSeqList; pSeqList palist; /*指针变量*/ f函数的首部为： void f（PSeqList pl） 在主函数中调用函数f

2、采用以下语句： pl=&L1; f（pl）;顺序表示中基本运算的实现算法2.1 创建空顺序表PSeqList createNullList_seq（ void ） PSeqList palist; palist = （PSeqList）malloc（sizeof（struct SeqList）; if （palist!=NULL） palist -n = 0; /* 空表长度为0 */ else printf（Out of space!n）; /* 存储分配失败 */ return （palist）;算法2.2 顺序表的插入 int insert_seq（ PSeqList palist, i

3、nt p, DataType x ） /* 在palist所指顺序表中下标为p的元素之前插入元素x */ int q; if （ palist-n = MAXNUM ） /* 溢出 */ printf（Overflow! return （ FALSE ）; if （ ppalist-n ） /* 不存在下标为p的元素 */Not exist! n for（q=palist-n - 1; q=p; q-） /* 插入位置及之后的元素均后移一个位置 */ palist-elementq+1 = palist-elementq;elementp = x; /* 插入元素x */n = palist-

4、n + 1; /* 元素个数加1 */ return （ TRUE ）;算法2.3 顺序表的删除 int delete_seq（ PSeqList palist, int p ）/* 在palist所指顺序表中删除下标为的元素 */n 1 ） /* 不存在下标为p的元素 */n return （FALSE）; for（q=p; qelementq+1; /* 元素个数减1 */ 算法分析: 在有n个元素的线性表里，在下标为i（第i+1个）的元素之前插入一个元素需要移动n - i 个元素；删除下标为i（第i+1个）的元素需要移动n - i - 1个元素。如果在下标为i的位置上插入和删除元素的概率

5、分别是Pi和Pi，则插入时的平均移动数是：设在n+1个插入位置都是等概率的，则有， 删除的平均移动数是（）： 所以顺序表的插入和删除操作的时间代价为O（n）。 类似地，在顺序表中进行定位（locate_seq）操作，则要依次与表中元素进行比较，当定位的概率平均分布在所有元素上时，一次定位平均需要和n/2个元素进行比较，其时间代价为O（n）。算法2.4 在顺序表中求某元素的下标 int locate_seq（ PSeqList palist, DataType x ） /* 求x在palist所指顺序表中的下标 */ for （ q=0;n ; q+）elementq = x） return （

6、q）; return （-1）;算法2.5 求palist所指顺序表中下标为的元素值DataType retrieve_seq（ PSeqList palist, int p ） /* 求palist所指顺序表中下标为p的元素值 */ if （ p=0 & pelementp ）; printf（Not exist.n return（SPECIAL）; /* 返回一个顺序表中没有的特殊值 */算法2.6 判断线性表是否为空int isNullList_seq（ PSeqList palist ） return （ palist-n = 0 ）;由上述操作可知：顺序存储的优点:不需要附加空间,随

7、机存取任一个元素;缺点: 很难估计所需空间的大小,且开始就要分配足够大的一片连续的内存空间.2.3 线性表的链接表示链式存储结构单链表：每个元素除了需要存储自身的信息外，还要存储一个指示其后继的信息（即后继元素存储位置），这两部分信息组成了一个数据元素的存储结构，称为一个结点（注意：每个结点所占用的存储单元应该是连续的）。每个结点包括两个域：数据域（info）存放数据元素本身的信息；指针域（link）存放其后继结点的存储位置。假设一线性表有n个元素，则这n个元素所对应的n个结点就通过指针链接成一个链表，由于这种链表中每个结点只有一个指针域，故又称为单链表。头指针指示单链表中第一个结点的存储位置

8、。如图2.5所示图2.5 链表示例struct LinkList /* 单链表类型定义 */ PNode head; /* 指向单链表中的第一个结点 */ ;/* 单链表类型的指针类型 */typedef struct LinkList *PLinkList;PLinkList pllist; /* pllist是指向单链表的一个指针变量 */ 循环链表：将单链表的形式稍作改变，让最后一个结点的指针指向头一个结点，这样就得到了循环链表。 使用循环链表的主要优点是：从循环链表中任一结点出发，都能访问遍所有结点。图2.11 循环链表双链表：双链表中每个结点除了数据域以外有两个指针域：一个指向其前驱

9、结点，一个指向其后继结点。每个结点的实际结构可以形象地描述如下：struct DoubleNode; /* 双链表结点 */typedef struct DoubleNode *PDoubleNode;/* 结点指针类型 */struct DoubleNode /* 双链表结点结构 */ DataType info; PDoubleNode llink, rlink;为了灵活地处理，可对双链表进行封装，引入双链表结构：struct DoubleList /* 双链表类型 */ PDoubleNode head; /* 指向第一个结点 */PDoubleNode rear; /* 指向最后一个结

10、点 */ 双链表带来的最大好处是可以很容易地找到前驱和后继。运算的实现：单链表上的算法的实现：算法2.7 创建空链表LinkList createNullList_link（ void ）/* 创建一个带头结点的空链表 */ LinkList llist; llist = （LinkList）malloc（ sizeof（ struct Node ） ）; /* 申请表头结点空间 */ if（ llist != NULL ） llist-link = NULL; return （llist）;算法2.8 单链表的插入int insert_link（LinkList llist, int i,

11、DataType x）/* 在llist带头结点的单链表中下标为i的（第i+1个）结点前插入元素x */ PNode p,q; int j; p = llist; j = 0; while （p!=NULL & jlink; j+; if （j!=i） /* iinfo = x;link = p- p-link = q; /* 注意该句必须在上句后执行 */ return（1）; 算法2.9 单链表的删除void delete_link（ LinkList llist, DataType x ）/* 在llist带有头结点的单链表中删除第一个值为x的结点 */ PNode p, q; /*找值

12、为x的结点的前驱结点的存储位置 */ while（ p-link != NULL & p-link-info != x ） p = p- if（ p-link = NULL ） /* 没找到值为x的结点 */ printf（”Not exist!n ”）; else q = p- /* 找到值为x的结点 */ /* 删除该结点 */ free（ q ）;算法2.10 在单链表中求某元素的存储位置 PNode locate_link（LinkList llist, DataType x ）/* 在llist带有头结点的单链表中找第一个值为x的结点存储位置 */ PNode p; if （llis

13、t=NULL） return（NULL）; p = llist- while（ p ! p = p- return （p）;算法2.11 求单链表中下标为i的（第i+1个）元素的存储位置 PNode find_link（ LinkList llist, int i ） /* 在带有头结点的单链表llist中求下标为i的（第i+1个）结点的存储位置;当表中无下标为i的（第i+1个）元素时，返回值为NULL */ PNode p; if （i0） /* 检查i的值 */The value of i=%d is not reasonable.n return （NULL）; p=llist; for

14、 （ j=0;j if （ p = NULL ） return （NULL）;算法2.12 判断单链表是否为空int isNullList_link（ LinkList llist）/* 判断llist带有头结点的单链表是否是空链表 */ if （llist=NULL） else return （llist-link = NULL）;线性表的周游：根据线性表的存储表示不同,其周游算法也不同:顺序表示的周游线性表的顺序表示的遍历void visit_seq（Pseqlist palist） int i=0; for（i=0;ielementi）;线性表的单链表表示的遍历周游void visit_

15、link（LinkList llist） Pnode p=llist; for（p=llist;p!=NULL;p=p-link） visit（p）;单链表与顺序表的比较： 单链表的存储密度比顺序表低，它多占用了存储空间。存储密度单链表数据项所占的空间/结点所占的空间 在单链表里进行插入、删除运算比在顺序表里容易得多。 对于顺序表，可随机访问任一个元素，而在单链表中，需要顺着链逐个进行查找，因此单链表适合于成批地、顺序地处理线性表中的元素时采用。 静态数据结构顺序表，在程序的运行期间数组的大小不再变化 动态数据结构链表，在程序的运行期间大小可自由变化2.4 应用举例Josephus问题问题提出

16、设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此反复直到所有的人全部出列为止。Josephus问题是：对于任意给定的n,s和m，求出按出列次序得到的n个人员的序列。问题解答思路数据结构Josephus问题讨论的是一个圆链，所以自然想到使用线性表作为存储这个圆链的数据结构。根据线性表种类的不同，就可以有2种不同的方法来表示圆链：顺序表表示，循环单链表表示。算法 在建立好线性表后，重复的对表中的元素实行检索和删除操作，将删除的元素依次输出就得到了Josephus问题的答案。解答框架1. 对n,s,m进行赋值2. 插入元

17、素构造Josephus表（对线性表初始化）3. 报数出列过程源程序顺序表子程序顺序表程序中对n,s,m进行赋值void inputnsm（int* n,int* s,int* m）printf（n please input the values（100） of n = scanf（%d,n）;n please input the values of s = ,s）;n please input the values of m = ,m）;插入元素构造Josephus表（对线性表初始化）顺序表的初始化void initlist（PSeqList jos_alist,int n） int i,k;

18、if （jos_alist=NULL） exit（1）;for（ i = 0; i i0; i-） s1 = （ s1 + m - 1 ） % i ;w = retrieve_seq（palist,s1）; /* 求下标为s1的元素的值 */Out element %d n,w）; /* 元素出列 */delete_seq（palist,s1）; /* 删除出列的元素 */顺序表的主程序#define MAXNUM 100#define FALSE 0#define TRUE 1typedef int DataType;main（ ） PSeqList jos_alist;int n,s,m;

19、inputnsm（&n,&s,&m）;jos_alist=createNullList_seq（ ）; /* 创建空顺序表 */initlist（jos_alist,n）;josephus_seq（jos_alist,s,m）;free（jos_alist）;return 0;顺序存储结构Josephus算法时间复杂性：循环单链表的子程序对n,s,m进行赋值报数出列过程循环单链表的报数出列过程void josephus_clink（ PLinkList pclist, int s,int m ） PNode p,pre; int i; p=*pclist; /* 找第s个元素 */if （s=

20、1） pre =p; p=p-while （p!=*pclist）pre =p;else for（i=1;s;=p-link） /* 当链表中结点个数大于1时 */ for （i=1;m;i+） /* 找第m个结点 */ pre = p; out element: %d n,p-info）; /* 输出该结点 */if （*pclist =p） /* 该结点是第一个结点时，删除时需特殊处理一下 */*pclist =p-pre-free（p）; p = pre- /* 输出最后一个结点 */*pclist=NULL; free（p）;简单示范程序：#include stdio.hconio.h

21、#define N 10#define s 1#define m 4typedef struct Student int No; char Name15; StudentData;typedef struct LNode StudentData StuData; struct LNode *link; LNode,*PList;PList clist;StudentData StuDataN= 1,Chen Nan, 2,Chen Xiaobo, 3,Chen Ying, 4,Cheng Liang, 5,Chent Wenping, 6,Dai Guoxiong 7,Gao Huan, 8,

22、Gong Fanghua, 9,Gou Jianting 10,Guan Qiang;PList CreatLinkList（） int i; PList p, q, cl=NULL;N; p=（PList）malloc（sizeof（LNode）;StuData.No=StuDatai.No; strcpy（p-StuData.Name, StuDatai.Name）; if（cl=NULL） cl=p; q=p; else q-link=p; q-link=cl; return cl; void Josephus（int sta, int ms, PList clst） PList p,q; p=clst; for（i=1;s