严蔚敏数据结构讲义(第02章 线性表)

第02章线性表本章知识结构：线性表的特点：1.有唯一的头；2.唯一的尾；3.除头外都有一个直接前驱；4.除尾外都有一个直接后继。

2.1线性表的类型定义一、线性表是n（n>=0）个数据元素的有限序列——有限个元素；元素之间有次序。

长度：表中元素的个数。

存储容量：整个线性表所占的空间。

位序：元素所在位置的序号，即第几个。

线性表的基本操作：1.访问（元素查询，定位）；2.插入元素；3.删除元素。

线性表的抽象数据类型定义（三元法定义）ADT List{数据对象；数据关系；基本操作}2.2顺序表(sequence)——线性表的顺序表示与实现一、特点：1.逻辑地址相邻，物理地址也相邻；2.优点：可随机访问；缺点：插入、删除不方便。

二、实现：一维数组三、C语言知识复习（一）typedef int DataType；给整型int定义一个别名DataType，之后就可以使用DataType定义整型变量了，例如： DataType x，y=8；（二）结构体类型的定义struct card{int num； char name[20]；……}——定义了一个结构体card（三）结构体变量的定义struct card stu1，stu2；——其中struct card是一个整体，表示结构体类型名（四）给结构体类型名定义别名typedef struct card DataType；给结构体struct card定义一个别名DataType（五）给匿名结构体定义别名typedef struct{int month;int day;int year;} Date； //该结构体为匿名结构体，相当于类的匿名对象。

即该结构体无名称，只有别名class PC； new PC().action()； //匿名对象的使用（六）sizeof函数：返回一个对象或者类型所占的内存字节数。

如：sizeof(int)——2（七）用typedef定义指针型别名typedef char *String； //声明String为字符指针类型typedef struct node{……} *LinkList； //声明LinkList为struct node类型的指针（八）malloc函数和free函数—— memory allocation内存分配1. 函数原型及说明：void *malloc(long NumBytes)：该函数分配了NumBytes个字节，并返回了指向这块内存的指针。

如果分配失败，则返回一个空指针（NULL）。

关于分配失败的原因，应该有多种，比如说空间不足就是一种。

void free(void *FirstByte)：该函数是将之前用malloc分配的空间还给程序或者是操作系统，也就是释放了这块内存，让它重新得到自由。

2. 函数的使用：char *Ptr = NULL;Ptr = (char *)malloc(100 * sizeof(char));//malloc()函数的类型是(void *),任何类型的指针都可以转换成(void *),但是最好还是在前面进行强制类型转换（九）calloc函数功能: 在内存的动态存储区中分配n个长度为size的连续空间，函数返回一个指向分配起始地址的指针；如果分配不成功，返回NULL。

跟malloc的区别：calloc在动态分配完内存后，自动初始化该内存空间为零，而malloc不初始化，里边数据是随机的垃圾数据。

（十）realloc函数原型：extern void *realloc(void *mem_address, unsigned int newsize);语法：指针名=（数据类型*）realloc（要改变内存大小的指针名，新的大小）。

头文件：#include <stdlib.h> 有些编译器需要#include <alloc.h>，在TC2.0中可用alloc.h头文件功能：先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来mem_address所指内存区域，同时返回新分配的内存区域的首地址。

即重新分配存储器块的地址。

返回值：如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。

注意：这里原始内存中的数据还是保持不变的。

当内存不再使用时，应使用free()函数将内存块释放。

四、线性表的结构定义——存储结构typedef struct{ElemTpye *elem； //存储空间首地址int length； //存储长度int ListSize； //存储容量}五、线性表的插入1.检查i值是否超出所允许的范围（1≤i≤n+1），若超出，则进行“超出范围”错误处理；2.检查容量是否已满，若已满则需扩充存储容量；3.将线性表的第i个元素和它后面的所有元素均向后移动一个位置；4.将新元素写入到空出的第i个位置上；5.使线性表的长度增1。

六、顺序表的删除七、顺序表的查找八、线性表合并九、顺序存储优缺点2.3链表——线性表的链式表示与实现一、线性链表/单链表（一）结点结构定义（二）基本运算1.建单链表（1）头插法建单链表ListLink HeadInsertCreateList() //头插法创建单链表{ListLink head,s;char ch;head=NULL;printf("Please input character(#->stop).\n");ch=getchar();while(ch!='#'){s =(ListLink)malloc(sizeof(ListNode)); //申请空间s->data = ch; //结点数据域赋值s->next = head; //将新节点的指针域指向头指针(即指向第一个数据元素地址)head = s; //将头指针指向新结点ch = getchar(); //继续接收键盘字符,循环创建数据元素}return head;}（2）尾插法建单链表ListLink TailInsertCreateList() //尾插法创建单链表{ListLink head,tail,s; //head头指针；tail尾指针；s临时指针char ch;head = NULL;tail = head; //起始时,单链表无数据元素，头指针和尾指针都为空printf("Please input character(#->stop).\n");ch=getchar();while(ch!='#'){s =(ListLink)malloc(sizeof(ListNode)); //申请空间s->data = ch; //结点数据域赋值s->next = NULL; //新结点作为最后一个结点出现，所以将新结点的指针域置空if(tail==NULL) //尾结点为空，此时插入第一个元素，应将头指针指向之，之后头指针保持不变 {head = s;tail = s; //第一个元素进入，尾指针也要指向第一个元素}elsetail->next = s; //第个及以后的元素插入都是直接将元素链入尾部tail = s; //将尾指针指向新结点ch = getchar(); //继续接收键盘字符,循环创建数据元素}return head;}2.查找（1）按值查找linklist *LOCATE(linklist *head,datatype key){ linklist *p;p＝head->next; //头结点不属于表while(p!=NULL)if (p->data!=key)p＝p->next;else break;return p;}（2）按位置(序号)查找——可拓展到遍历linklist *GET(linklist *head,int i){ int j;linklist *p;p ＝head;j ＝0;while((p->next!=NULL)&&(j<i)){ p ＝p->next;j++;}if (i==j) return p;else return NULL;}3.插入元素 （1）单个结点后插操作//后插元素，L 为单链表头指针，在q 所指向的元素后面插入一个元素，值为eListLink ListInsertAfter(ListLink L, ListLink p, DataType e){ListLink q = (ListLink)malloc(sizeof (ListNode));if (q==NULL){printf("Memory allocation Error.\n");exit(0);}q->data = e;q->next = p->next;p->next = q;return L;}（2）单个结点前插操作InsertBefore(linklist *head,linklist *p,datatype x){ linklist *s,*q;s ＝malloc(sizeof(linklist));s->data ＝x;q ＝head;while(q->next!=p) q ＝q->next;s->next ＝p;q->next ＝s;}4.删除元素 （1）删除后继结点二、按位置查找(即访问第i 个元素)的时间复杂度是)1(O ；——Add i =Add 0+(i-1)*d按值查找（即查找值为x 的元素），需要比较(n+1)/2次，时间复杂度为)(n O ；插入元素需要平均移动节点n/2个；——设线性表有n 个元素，如果要在第1个元素位置插入元素，则需要移动n 个元素；如果要在第2个元素位置插入，则需要移动n-1个元素…，如果要在第n 个元素位置插入需要移动1个；如果要在最末尾插入元素，则不需要移动元素，即移动0个元素，列出所有要移动元素的和，n + (n-1) + (n-2) + … + 1 + 0，最终的n(n+1)/2。

插入总次数为n+1，所以移动平均数为[n(n+1)/2]÷(n+1) =n/2。

删除元素的平均时间复杂度为(n-1)/2。

链式存储：查找(访问)第i 个元素的时间复杂度是)(n O ；——从第1个找第2个，再通过第2个找第3个，… 插入元素的平均时间复杂度为)1(O ；删除元素的平均时间复杂度为)1(O 。

二、 静态链表与动态链表静态链表：所有结点都是在程序中定义，不是临时开辟的，也不能用完后释放。