基本数据结构——线性表.ppt

;1.2 线性表;C={ ‘A’，’B’，...，’Z’ }。;1.2 线性表 一、线性表的概念与运算;1.2 线性表 一、线性表的概念与运算;1.2 线性表 一、线性表的概念与运算;1.2 线性表 ;该结构用高级语言中的一维数组类型表示。数组中的分量下标即为元素在线性表中的序号。 例如：可用一维数组A[n]来存储线性表： （a1, a2 ,...，an）。 这里需要声明：C语言中，数组下标从0开始。 #define MAXSIZE 100 datatype data[MAXSIZE]; ;1.2 线性表 二、线性表的顺序存储结构;1.2 线性表 二、线性表的顺序存储结构;1.2 线性表 二、线性表的顺序存储结构;时间复杂度分析: O(n) ;1.2 线性表 二、线性表的顺序存储结构;1.2 线性表 二、线性表的顺序存储结构;时间复杂度分析: O(n) ;1.2 线性表 二、线性表的顺序存储结构;1.2 线性表 ;1.2 线性表 三、线性表的链式存储结构;存储地址;1.2 线性表 三、线性表的链式存储结构;头指针;例 画出26 个英文字母表的链式存储结构。;例:一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？;上例链表的逻辑结构示意图有以下两种形式：;答：;复习:动态存储分配 链表是动态的分配内存。结点的存储单元在运行时，需要时分配。该存储单元用完就释放。 涉及动态分配内存的库函数(在头文件 malloc.h或stdlib.h中) void *malloc(unsigned int size);//分配size个字节的内存空间,返回该内存空间的首地址 viod *malloc(unsigned n, unsigned size);//分配n个长度为size个字节的连续内存空间,返回该内存空间的首地址 void free(void *p);//释放p所指向的内存区 malloc()和free()成对调用。 calloc()和free()成对调用. ;1.2 线性表 三、线性表的链式存储结构;③;尾插法建立单链表;h;链表的构建（以构建一个记录3个学生信息的单链表为例） 结点的定义 struct stud_node { long num; float score; struct stud_node *next; }; typedef struct stud_node NODE,*head,*p; 建立如下所示的单链表 num 99101 99103 99107 score 89.5 90.0 85.0 next NULL 第一个结点 第二个结点 尾结点;每次插在链尾的建立方法;#define NULL 0 #define LEN sizeof( NODE ) // LEN为每个结点所占内存空间的大小 NODE * listcreate(int n) //n为结点数 { NODE *head, *p, *s; int i; head=NULL; p=( NODE * )malloc(LEN); p-num=NULL; p-score= NULL; p-next=NULL; head=p; for( i=1; i=n; i++) { s=( NODE * )malloc(LEN);//开辟新结点的存储空间 scanf(“ %ld, %f ”, s-num, s-score); s-next=NULL; p-next=s; p=p-next; } return head; };data;1.2 线性表 三、线性表的链式存储结构;1.2 线性表 三、线性表的链式存储结构;1.2 线性表 三、线性表的链式存储结构;1.2 线性表 三、线性表的链式存储结构;1.2 线性表 三、线性表的链式存储结构;（4）单链表的访问;线性链表的 结点查找(按学号查找) NODE* find_node(NODE *head, long num) { NODE *p_this; p_this=head; while(p_this) { if(p_this-num= =num) return p_this; p_this=p_this-next; } printf(“没找到此人!\n); p_this=0;