566-数据结构2课程安排 计划学时：32学时 时间：8周 讲课：24学时 实.pptVIP

* 数据结构2课程安排 计划学时：32学时 时间：8周 讲课：24学时 实验：8学时 考核 考试：70% 平时：30%（实验、作业、出勤） 第2章 线性表 线性表是n个数据元素的有限序列。 （a1, a2, …… an) 线性表存储结构: 顺序存储结构 链式存储结构 线性表顺序存储结构 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType * elem ; int length ; int listsize ; } SqList ; 线性表的链式存储结构（单链表） typedef struct LNode { ElemType data ; struct LNode * next ; } LNode , * LinkList ; 顺序存储结构特点： 逻辑关系相邻，物理位置相邻 可随机存取任一元素 存储空间使用紧凑 插入、删除操作需要移动大量的元素 预先分配固定大小空间，利用不充分 链式存储结构特点： 是一种动态结构 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢 1、静态链表 1 0 ZHAO 2 1 QIAN 3 2 SUN 4 3 LI 5 4 ZHOU 6 5 WU 7 6 ZHENG 8 7 WANG 0 8 9 10 SHI 5 -- 9 这种结构具有链式存储的主要优点：插入删除时不需移动元素，但需预先分配一个较大的空间，查找时从头开始 #define MAXSIZE 1000 typedef struct { ElemType data ; int cur ; } component , SLinkList [ MAXSIZE ] ; 例：求集合运算(A-B)∪(B-A),假设由终端输入集合A和集合B的元素，建立表示结果集合的静态链表S。 初始化静态链表 void InitSpace_SL ( SLinkList space ) { for ( i = 0 ; i MAXSIZE – 1 ; ++ i ) space [ i ].cur = i + 1 ; space [ MAXSIZE –1 ].cur = 0 ; } 分配一个结点空间 int Malloc_SL ( SLinkList space ) { i = space [ 0 ].cur ; if(space[0].cur) space[0].cur = space[i].cur ; return i ; } 回收备用链表 void Free_SL ( SLinkList space , int k ) { space[k].cur = space[0].cur ; space[0].cur = k ; } void difference ( SLinkList space , int s ) { InitSpace_SL ( space ) ; s = Malloc_SL ( space ) ; r = s ; scanf ( m , n ) ; for ( j = 1 ; j = m ; ++ j ) { i = Malloc_SL ( space ) ; scanf ( space [ i ].data ) ; space [ r ].cur = i ; r = i ; } space [ r ].cur = 0 ; for ( j = 1 ; j = n ; ++ j ) { scanf ( b ) ; p = s ; k = space [ s ].cur ; while ( k != space [ r ].cur space [ k ].data != b ) { p = k ; k = space [ k ].cur ; } if ( k == space