C语言线性链表.ppt

1、1,线性表的链式存储结构,每个元素由结点(Node)构成; 结点间的逻辑关系是线性的，即线性表; 结点在计算机中可以不连续存储; 链表可以扩充，只受存储介质大小的限制;,数据和数据间的关系分别存储,Node:,链表分类,按照链式存储的原则，可以有多种形式的链表 线性链表（单链表） 循环链表 双向链表,3,typedef int ElemType; typedef struct LNode ElemType data; /结点的数据域 struct LNode *next; /结点的指针域 LNode, *LinkList;,单链表的定义,4,单链表的存储映像,初始化：InitList( Ste

2、p 2：p-next=s ；,当!当!当! 万无一失吗?有没有问题呢?,7,单链表插入操作的特殊情况（1）,核心语句： s-next=p;/head; head=s ；,在第一个结点前插入,原语句： s-next=p-next; p-next=s ；,p,8,单链表插入操作的特殊情况（2）,在末尾插入,核心语句： s-next=NULL; p-next =s ；,p,b,a,head,原语句： s-next=p-next; p-next=s ；,9,单链表插入操作的特殊情况（3）,空表插入,核心语句： s-next=NULL; head =s ；,head=NULL,原语句： s-next=p

3、-next; p-next=s ；,太麻烦了！ 赶快想个办法吧！,10,解决之道：带表头结点的单链表,空表：,首结点：存储第一个数据元素,11,s-next=p-next; p-next=s ；,带表头节点单链表的插入操作,(1)表头插入：,(2)空表插入：,欧耶！ 太给力了!,单链表插入操作的算法描述,status ListInsert_L( LinkList / ListInsert_L P29 算法2.9,13,小结：带表头结点的单链表,表头结点位于表的最前端，本身不带数据，仅做标志。有时可用来存储附加信息。 设置表头结点的好处： 统一了链表第一位置和其他位置的操作； 统一了空表和非空表

4、的操作；,以空间赢得时间,使得各种链表（单向链表、双向链表、单向循环链表和双向循环链表）的空链表状态得到区分；亦表明各种空链表结构是不同的。,Note：只要不特殊说明，用的就是带头结点的链表。,14,课后作业,对照不带头结点和带头结点两种单链表的插入操作，自行分析两种单链表对于删除操作的不同。（书面作业） 说明： 必须要做！ 虽然不讲，但是是考试内容！,2.3.3 链表基本算法实现(1)初始化,生成一个带头结点的空链表,Status InitList_L(LinkList ,16,链表基本算法实现(2)建立单链表,建立链表的过程是一个动态生成的过程： 从空表状态，依次建立各元素结点，并逐个插入

5、,head,步骤： （1）找到单链表的末尾； （2）将新结点插入。,尾插法,方法1：调用基本算法 建立链表；,使用基本算法: void InitList( int i=0; InitList(L); /初始化链表 i=1; scanf( ,输入：67，23，10，45，36,T(n)=O(n) 如果不设last指针，则T(n)=O(n2) 不省心，总要记住表尾。 如何改进？,尾插法建立单链表性能分析,头插法,头插法建立单链表（P30 算法2.11）,void CreatList_L(LinkList CreatList_L,输入：36，45，10，23，67,22,总结：单链表的优缺点,优点

6、能有效利用存储空间； 用指针指示数据元素之间的后继关系，便于进行插入、删除等操作； 缺点： 不能随机存取数据元素。 同时，还丢失了一些顺序表有的长处，如数据元素在线性表中的“位序”，在的单链表中都“看不见”了。 不便于在表尾插入元素，需遍历整个表才能找到表尾。,23,其他类型的链表双向链表,a1,an,a3,a2,H,typedef int ElemType ; typedef struct DuLNode ElemType data ; struct DuLNode *prior ; struct DuLNode *next ; DuLNode, *DuLinkList ;,24,小结：顺序

7、表和链表的比较,选用原则 长度已知，且变化不大，则选择顺序表； 长度不定，或变化大，则选用链表。 主要操作的特点 顺序表：插入、删除费时间移动数据， 取数据快速； 链表：插入、删除快速，取数据费时间。,25,多项式 (Polynomial),n阶多项式Pn(x)有n+1项。 系数为 a0, a1, a2, , an x的指数为 0, 1, 2, , n。按升幂排列,2.4 线性表应用：一元多项式的表示和相加,26,多项式的存储表示,方法1：按指数从0至n的次序保存所有项的系数。,每个数据项系数类型为 float， 多项式存储为 float coef maxDegree;,问题：对于指数不全的多

8、项式 如 P2000(x) = 3 + 5x 1000 14 x 2000 太浪费.,27,方法2：仅保存非0系数项的系数和指数,方法2：改进的顺序表,typedef struct float coef; /系数 int exp; /指数 Poly_node; Poly_node SqPolym+1;,28,方法3：用单链表实现,typedef struct Poly_ListNode float coef; /系数 int exp; /指数 struct Poly_ListNode *next; Poly_ListNode ; Poly_ListNode *SqPoly;,1.若学生记录信息

9、为：学号、姓名、成绩，要求以顺序表实现。请分别以静态存储和动态存储两种形式写出其数据结构描述。,#define ListSize 100 typedef int ElemType; typedef struct ElemType elemListSize; int length; Sqlist;,typedef struct int number; char name10; int score; ElemType;,静态分配存储结构,#define ListSize 100 typedef struct int number; char name10; int score; Student;

10、typedef struct Student elemListSize; int length; Sqlist;,#define ListSize 100 typedef int ElemType; typedef struct ElemType elemListSize; int length; Sqlist; typedef struct int number; char name10; int score; Student;,动态分配存储结构,#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int ElemType; typedef struct ElemType *elem; int length; int listsize; Sqlist;,typedef struct int num