DBS第02章结构与联合、数组、链表.pptVIP

作 业 P33 2-4 2-9 2-12 void Invert(T elements[], int length) { //length数组长度 // elements[]为需要逆序的数组 T e; for (int i=1;i=length/2;i++) { e=elements[i-1]; elements[i-1]=elements[length-i]; elements[length-i]=e; } } 它包含的元素又是一个一维数组 使用指针使C语言程序设计十分灵活和高效，但如果使用不当会带来很大的程序隐患。 空指针NULL不指向任何实际的对象，间接引用一个空指针，常会带来不可预期的结果。 int * p = NULL; *p = 10; 2.3.2 单链表 (1) 单链表的结点结构 element link 存放元素的域 存放指向后继结点的指针域 a0 a1 a2 an-1 … first ∧ (2) 单链表结构 起始结点 头指针 尾结点 a0 a1 a3 a4 a2 单链表在内存中的示意图 a0 a1 a2 an-1 … first ∧ 非空单链表 注意： ●单链表头指针first不能少 ●最后一个结点的指针域为? ●逻辑上相邻的元素在物理上不一定相邻 ●不能出现“断链”现象 ? = NULL 指针变量的存储单元 first ∧ 单链表的结点结构 typedef struct node{ T Element; struct node* Link; } Node; 单链表的结点类型Node 用户自定义的元素类型 typedef int T； 在C语言环境中，元素类型T必须由用户在应用时，用typedef语句定义为具体的类型。 typedef struct entry{ int Key; char Data ; }Entry; typedef Entry T; （1）T* InputElement(); 后置条件：已构造一个类型为T的新元素对象，并赋以所需的元素值，返回新元素对象的地址。 （2）void PrintElement(T e) 后置条件：输出元素e。 两个重要运算 【程序2－3】 创建和显示元素。 typedef int T; T* InputElement() { static T a; scanf(%d, a); return a; } void PrintElement(T x) { printf(%d , x); } 返回a的地址 【程序2－4】 构造新结点。 #define IS_FULL(ptr) (!(ptr)) Node* NewNode() { Node* p=(Node*)malloc(sizeof(Node)); if (IS_FULL(p)){ fprintf(stderr, The memory is full\n); exit(1); } p-Link=NULL; return p; } p ∧ Node* NewNode1() { Node* p=(Node*)malloc(sizeof(Node)); if (IS_FULL(p)){ fprintf(stderr, The memory is full\n); exit(1); } p-Element=*InputElement(); p-Link=NULL; return p; } p ∧ 1 Node* NewNode2(T x) { Node* p=(Node*)malloc(sizeof(Node)); if (IS_FULL(p)){ fprintf(stderr, The memery is full\n); exit(1); } p-Element=x; p-Link=NULL; return p; } p ∧ x 2. 单链表类型 单链表类型List : typedef Node* List; a0 a1 a2 an-1 … first ∧ 非空单链表 List first; List f