数据结构课件2线性表幻灯片.ppt

* 头插法建表 LinkList createListF( void ) { //返回链表头指针 char ch;  LinkList head=NULL; LinkNode *s; while ((ch = getchar())!= ‘\n’ ) { s = (LinkNode *)malloc(sizeof(LinkNode)); s-data = ch; s-next = head; head = s; } return head; } * 尾插法建表 LinkList createListR( void ) { //返回链表头指针 char ch;  LinkList head=NULL; LinkNode *s, *tail= NULL; while ((ch = getchar())!= ‘\n’ ) { s = (LinkNode *)malloc(sizeof(LinkNode)); s-data = ch; if(head == NULL) head = s; else tail -next = s; tail = s; } if(tail != NULL) tail -next = NULL; return head; } * 带头结点，尾插法建表 LinkList createListR1( void ) { //返回链表头指针 char ch; LinkList head= (LinkNode *)malloc(sizeof(LinkNode)); LinkNode *s, *tail= head; while ((ch = getchar())!= ‘\n’ ) { s = (LinkNode *)malloc(sizeof(LinkNode)); s-data = ch; tail -next = s; tail = s; } tail -next = NULL; return head; } * 单链表特点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢 插入、删除操作方便 * 静态链表结构 利用数组定义,配合游标（指示器），运算过程中存储空间大小不变 * 循环链表(circular linked list) 循环链表是表中最后一个结点的指针指向头结点，使链表构成环状 特点：从表中任一结点出发均可找到表中其他结点，提高查找效率 操作与单链表基本一致,循环条件不同 单链表p或p-next=NULL 循环链表p或p-next=h h h 空表 * 双向链表（double linked list） 单链表具有单向性的缺点 结点定义 typedef struct node { datatype element; struct node *prior,*next; }JD; prior element next L 空双向循环链表： 非空双向循环链表： L A B b c a p p-prior-next= p= p-next-proir; * b c a P void del_dulist(JD *p) {p-prior-next=p-next; p-next-prior=p-prior; free(p); } 删除 算法描述 算法评价：T(n)=O(1) p-prior-next=p-next; p-next-prior=p-prior; * void ins_dulist(JD* p,int x) {JD *s; s=(JD*)malloc(sizeof(JD)); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; } 算法描述 算法评价：T(n)=O(1) x S b a P 插入 * 2.4 线性表的应用举例 一元多项式的表示及相加 一元多项式的表示： 可用线性表P表示 但对S(x)这样的多项式浪费空间 一般 其中 用数据域含两个数据项的线性表表示 其存储结构可以用顺序存储结构，也可以用单链表 * 单链表的结点定义 coef exp next -1 A 7