[理学]数据结构课件2.ppt

可用C语言描述顺序存储结构下的线性表（顺序表）如下： typedef struct Linear_list { datatype elem[MAXSIZE]; /*定义数组域*/ int last; /*线性表中最后一个元素在数组中的位置*/ } SeqList; 基本思路： 从第二个元素开始到最后一个元素，逐一向后扫描： ① 当前数据元素ai比a1大时，表明它已经在a1的后面，不必改变它与a1之间的位置，继续比较下一个。 ② 当前结点若比a1小，说明它应该在a1的前面，此时将它前面的元素都依次向后移动一个位置，然后将它置入a1前。 【C源程序】 #include?stdio.h #include?stdlib.h #define?NULL?0 #define?OK?1 #define?ERROR?0 #define?OVERFLOW?-2 typedef?int?Status; typedef?int?Elemtype;/*定义数据元素类型??*/ typedef?struct?Cnode ??{??Elemtype?data; ?????struct?Cnode?*next; ???}CNode; CNode?*joseph;/*定义一个全局变量??*/ Status?Create_clist(CNode?*clist, int?n) {?? CNode?*p,*q; int?i; clist=NULL; for(i=n; i=1; i--) ?????{? p=(CNode?*)malloc(sizeof(CNode)); ?????? if (p==NULL)?return?OVERFLOW;?/*存储分配失败??*/ ?????? ?p-data=i; ??????? p-next=clist ?????? ?clist=p; ?????? ?if(i==n) ?q=p; /*用q指向链表的最后一个结点??*/ } q-next=clist;?/*把链表的最后一个结点的链域指向链表的第一个结点 joseph=clist;??/*把创建好的循环链表头指针赋给全局变量??*/ return?OK; }????? /*end??*/ Status?Joseph(CNode?*clist, int?m, int?n, int?k) {??int?i; CNode?*p,*q; if(mn)?return?ERROR; if (! Create_clist(clist,n) )???? ?return?ERROR; p=joseph; for(i=1;im;i++) ???? ??p=p-next; while(p) ???{? for (i=1; ik-1; i++) ???????????p=p-next; ?????? ?q=p-next; ????? ??printf(%d?,q-data); ?????? ?if (p-next==p) ?? p=NULL; ?????????else?{? p-next=q-next; ??????????????? ? p=p-next; free(q);?}?????? ?}??/*while??*/???? ??clist=NULL; ?}?/*?end?*/ void?main(?) {?int?m,n,k,i; ??CNode?*clist; ??clist=NULL;/*初始化clist??*/ printf(\n请输入围坐在圆桌周围的人数n：); scanf(%d,n); printf(\n请输入第一次开始报数人的位置m：); scanf(%d,m); printf(\n你希望报数到第几个数的人出列?); scanf(%d,k); Create_clist(clist,n);/*创建一个有n个结点的循环链表clist??*/ printf(\n出列的顺序如下：\n); Joseph(clist,m,n,k); getch(); }/*main??*/ 2.3.4 双向链表 在单链表的每个结点里再增加一个指向其前驱的指针域prior。 这样形成的链表中就有两条方向不同的链，我们可称之为双(向)链表(Double Linked List)。 双链表的结构定义如下: typedef struct DNode { ElemType data