第1章线性数据结构一

第1章线性数据结构一内容摘要：

else 30 /70  { for (k=last1。 K=i1。 k)  list[k+1]=list[k]。  list [i1] =x。  ++last。  }  } 31 /70 算法 11 插入算法主程序  define MAXLENGTH 100 /* 例 11主程序 */  int list[MAXLENGTH]={5,3,1,10,7,8,1,4}。  int last=7。 /* last为全局变量 */  main（）  { int x,j,loc。  printf(“Enter x、 loc\n”)。  scanf(“%d,%d”,amp。 x,amp。 loc)。  for (j=0。 j last+1。 j++)  printf(“%d “,list[j])。 32 /70  printf(“\n”)。  insert(loc,x)。 /* 调用插入函数 */  for (j=0。 j last+1,j++)  printf(“%d “,list[j])。  printf(“\n”)。  } 33 /70 算法 12 —— 线性表删除元素  算法步骤 :  step1 判别指定的位置是否合法；  step2 若合法，则将位置 i+1至 n的元素前移一个存储位置。  step3 表的长度 1。 34 /70 算法 12 —— 线性表删除算法  delete(int i) /*第 i 个元素的下标为 I1 */  { int k。  if( i 1 || i last )  { printf(“表中不存在位置为 i的元素 \n”)。  exit(1)。  }  for(k= i1。 k=last1。 k++)  list[k]=list[k+1]。  last。  } 35 /70 算法 12 —— 线性表删除算法  define MAXLENGTH 100 /* 例 12主程序 */  int list[MAXLENGTH]={5,3,1,10,7,8,1,4}。  int last=7。  main（）  { int j,loc。  printf(“Enter loc\n”)。  scanf(“%d”,amp。 loc)。  for (j=0。 j last+1。 j++)  printf(“%d “,list[j])。 36 /70  printf(“\n”)。  delete(loc)。 /* 删除子函数 */  for (j=0。 j last+1。 j++)  printf(“%d “,list[j])。 printf(“\n”)。  } 37 /70 顺序存储结构的特点  1. 数据连续存放、随机存取  2. 逻辑上相邻，物理上也相邻  3. 存储结构简单、易实现  4. 存储密度大，空间利用率高  5. 插入、删除操作移动数据 ,不方便  结论：  适合于表中元素变动较少的情况 38 /70 （三 ）线性表的链式存储结构  顺序存储结构容易实现，可以随机存取表中的任意元素。  顺序表缺点： – 难于插入、删除操作； – 需要预先分配空间，不管这些空间能否最大限度地利用。  链表存储结构在这两个方面恰好是优点： – 容易插入、删除操作 – 不需要预分空间。 39 /70 链表的有关概念  结点（ NODE） 表中元素的存储单元。  结点的结构：  结点的 C语言描述： – struct node – { int data。 – struct node *next。 – }。 – typedef struct node NODE； data next 数据域 指针域 40 /70 基本概念  1) 链表 : 由结点组成的表。  2) 头结点 : 为方便操作，在头指针和第一个结点之间设置的结点。  3) 首元结点 : 链表的 第一个结点  4) 头指针 : 指向链表中头结点的指针。 head a1 头指针 头结点 首元结点 a i ... 第 i个结点 41 /70 设置头结点的目的 (一 )  使空表和非空表表示形式在头结点上得到统一  (1)有头结点  空表 : – head next = NULL  非空表 : – head next = 地址 head NULL 头结点 head 头结点 42 /70 设置头结点的目的 (二 )  (2) 没有头结点  表示形式不统一  空表 : – head = NULL  非空表 : – head next = 地址 head head。