1、1线性表的链式存储结构线性表的链式存储结构 每个元素由结点每个元素由结点(NodeNode)构成构成;结点间的结点间的是线性的，即线性表是线性的，即线性表;结点在计算机中可以结点在计算机中可以不连续存储不连续存储;链表可以扩充，只受存储介质大小的限制链表可以扩充，只受存储介质大小的限制;Node:链表分类链表分类按照链式存储的原则，可以有多种形式的链表按照链式存储的原则，可以有多种形式的链表线性链表（单链表）线性链表（单链表）循环链表循环链表双向链表双向链表a1ana3a2H3 typedef int ElemType;typedef struct LNode ElemType data;/结
2、点的数据域结点的数据域 struct LNode*next;/结点的指针域结点的指针域 LNode,*LinkList;单链表的定义单链表的定义4单链表的存储映像单链表的存储映像Phead初始化：初始化：InitList(&L)销毁：销毁：DestroyList(&L)清空：清空：ClearList(&L)判表空：判表空：ListEmpty(L)求表长：求表长：ListLength(L)取元素值：取元素值：GetElem(L,i,&e)查找某元素：查找某元素：LocateElem(L,e)求前驱：求前驱：PriorElem(L,cur_e,&pre_e)求后继：求后继：NextElem(L,c
3、ur_e,&next_e)插入：插入：ListInsert(&L,i,e)删除：删除：ListDelete(&L,i,&e)遍历：遍历：ListTraverse(L,Visit()单链表的单链表的基本操作基本操作6单链表的插入操作单链表的插入操作当当!当当!当当!万无一失吗万无一失吗?有没有问题呢有没有问题呢?7单链表插入操作的特殊情况（单链表插入操作的特殊情况（1）Xss-nextbahead核心语句：核心语句：；在第一个结点前插入在第一个结点前插入 原语句：原语句：；p8单链表插入操作的特殊情况（单链表插入操作的特殊情况（2）在末尾插入在末尾插入 Xss-next核心语句：核心语句：s-n
4、ext=NULL;p-next=s；pbahead 原语句：原语句：；9单链表插入操作的特殊情况（单链表插入操作的特殊情况（3）空表插入空表插入 核心语句：核心语句：s-next=NULL;head=s；head=NULLXhead s原语句：原语句：；太麻烦了！太麻烦了！赶快想个办法吧！赶快想个办法吧！10解决之道：带解决之道：带的单链表的单链表头指针头指针表头结点表头结点head 空空表：表：头指针头指针表头结点表头结点head首结点：存储第一个数据元素11Xss-next带表头节点单链表的插入操作带表头节点单链表的插入操作abheadp(1)表头插入：表头插入：(2)空表插入：空表插入：
5、headpXs欧耶！欧耶！太给力了太给力了!单链表插入操作的算法描述单链表插入操作的算法描述status ListInsert_L(LinkList&L,int i,ElemType e)/在带头结点的链表中的第在带头结点的链表中的第i个结点前插入元素个结点前插入元素ep=L;j=0;while(p&jnext;+j;/查找第查找第i-1个结点个结点if(!p|ji-1)return-1;/i值不合法值不合法 s=(LNode*)malloc(sizeof(LNode);/申请新结点的空间申请新结点的空间 s-data=e;s-next=p-next;p-next=s;/插入操作插入操作ret
6、urn OK;/ListInsert_L P29 算法算法2.913小结：带表头结点的单链表小结：带表头结点的单链表表头结点位于表的最前端，本身不带数据，仅表头结点位于表的最前端，本身不带数据，仅做标志。有时可用来存储附加信息。做标志。有时可用来存储附加信息。设置表头结点的设置表头结点的：统一了链表第一位置和其他位置的操作；统一了链表第一位置和其他位置的操作；统一了空表和非空表的操作；统一了空表和非空表的操作；以空间赢得时间以空间赢得时间使得各种链表（单向链表、双向链表、单向循使得各种链表（单向链表、双向链表、单向循环链表和双向循环链表）的空链表状态得到区环链表和双向循环链表）的空链表状态得到
7、区分；亦表明各种空链表结构是不同的。分；亦表明各种空链表结构是不同的。14课后作业课后作业对照不带头结点和带头结点两种单链表对照不带头结点和带头结点两种单链表的插入操作，自行分析两种单链表对于的插入操作，自行分析两种单链表对于删除删除操作的不同。（操作的不同。（书面作业书面作业）说明：说明：必须要做！必须要做！虽然不讲，但是是考试内容！虽然不讲，但是是考试内容！2.3.3 链表基本算法实现链表基本算法实现(1)初始化初始化生成一个带头结点的生成一个带头结点的空链表空链表头指针头指针表头结点表头结点headStatus InitList_L(LinkList&L)L=(LinkList)mall
8、oc(sizeof(LNode);L-next=NULL;/创建头结点创建头结点 return OK;/InitList_L;16链表基本算法实现链表基本算法实现(2)建立单链表建立单链表建立链表的过程是一个动态生成的过程：建立链表的过程是一个动态生成的过程：从空表状态，依次建立各元素结点，并逐个插入从空表状态，依次建立各元素结点，并逐个插入head步骤：步骤：（1）找到单链表的末尾；）找到单链表的末尾；（2）将新结点插入。）将新结点插入。方法方法1：调用基本算法调用基本算法 建立链表；建立链表；使用基本算法使用基本算法:void InitList(&L)；void ListInsert(&L
9、,i,e)方法方法2：自编算法建立自编算法建立尾插法建立单链表算法尾插法建立单链表算法18方法方法2：尾插法：尾插法建立单链表建立单链表int CreatListR(LinkList&H)int element;LinkList L;LNode*s,*last;/s指向新结点，指向新结点，last指向链表的最后结点指向链表的最后结点 L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/建立头结点建立头结点 last=L;cinelement;while(element!=0)s=(LNode*)malloc(sizeof(LNode);/申请新结点申请新
10、结点 s-data=element;s-next=NULL;last-next=s;/新结点链入链表新结点链入链表 last=s;/last指向新的最后结点指向新的最后结点 cinelement;H=L；return 0;/CreatListR方法方法1实现：利用基本算法建立链表实现：利用基本算法建立链表输入：输入：67，23，10，45，36L3645102367T(n)=O(n)如果不设如果不设last指针，则指针，则T(n)=O(n2)不省心，总要记住表尾。不省心，总要记住表尾。如何改进？如何改进？尾插法建立单链表性能分析尾插法建立单链表性能分析头插法头插法头插法头插法建立单链表建立单链
11、表（P30 P30 算法算法2.112.11）void CreatList_L(LinkList&L,int n)/逆位序输入逆位序输入n个元素的值，建立带头结点的单链表个元素的值，建立带头结点的单链表L L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/建立头结点建立头结点 for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);cinp-data;p-next=L-next;L-next=p;CreatList_L输入：输入：36，45，10，23，67L364510236722总结：单链表的优缺点总结：单链表
12、的优缺点优点优点能有效利用存储空间；能有效利用存储空间；用用指针指针指示数据元素之间的后继关系，便于进指示数据元素之间的后继关系，便于进行行插入插入、删除删除等操作；等操作；缺点缺点：不能随机存取数据元素。不能随机存取数据元素。同时，还丢失了一些顺序表有的长处，如数据元同时，还丢失了一些顺序表有的长处，如数据元素在线性表中的素在线性表中的“位序位序”，在的单链表中都，在的单链表中都“看看不见不见”了。了。不便于在表尾插入元素，需遍历整个表才能找到不便于在表尾插入元素，需遍历整个表才能找到表尾。表尾。23其他类型的链表其他类型的链表a1ana3a2H空表：空表：H typedef int Ele
13、mType;typedef struct DuLNode ElemType data;struct DuLNode*prior;struct DuLNode*next;DuLNode,*DuLinkList;24小结小结：顺序表和链表的比较：顺序表和链表的比较1.选用原则选用原则 长度已知，且变化不大，则选择顺序表；长度已知，且变化不大，则选择顺序表；长度不定，或变化大，则选用链表。长度不定，或变化大，则选用链表。1.主要操作的特点主要操作的特点 顺序表：插入、删除费时间移动数据，顺序表：插入、删除费时间移动数据，取数据快速；取数据快速；链表：插入、删除快速，取数据费时间。链表：插入、删除快速
14、，取数据费时间。25Pn(x)=a0+a1x+a2x2+anxn =i=0naixi多项式多项式(Polynomial)n阶多项式阶多项式Pn(x)有有n+1项。项。系数为系数为 a0,a1,a2,an x的指数为的指数为 0,1,2,n。按升幂排。按升幂排列列2.4 线性表应用：一元多项式的表示和相加线性表应用：一元多项式的表示和相加26 多项式的存储表示方法方法1 1：按指数从按指数从0至至n的次序保存所有项的系数。的次序保存所有项的系数。每个数据项系数类型为每个数据项系数类型为 float，多项式存储为多项式存储为 float coef maxDegree;问题问题：对于指数不全的多项式
15、：对于指数不全的多项式 如如 P2000(x)=3+5x 1000 14 x 2000 太浪费太浪费.27方法方法2：仅保存非：仅保存非0系数项的系数和指数系数项的系数和指数方法方法2 2：改进的顺序表：改进的顺序表coef exp typedef struct float coef;/系数系数 int exp;/指数指数 Poly_node;Poly_node SqPolym+1;28a1 e1a0 e0a2 e2am em Hcoef exp next方法方法3 3：用单链表实现：用单链表实现 typedef struct Poly_ListNode float coef;/系数系数 in
16、t exp;/指数指数 struct Poly_ListNode *next;Poly_ListNode;Poly_ListNode*SqPoly;1.若学生记录信息为：若学生记录信息为：学号、姓名、成绩学号、姓名、成绩，要求，要求以顺序表实现。请分别以静态存储和动态存储两以顺序表实现。请分别以静态存储和动态存储两种形式写出其数据结构描述。种形式写出其数据结构描述。#define ListSize 100 typedef int ElemType;typedef struct ElemType elemListSize;int length;Sqlist;typedef struct int
17、number;char name10;int score;ElemType;#define ListSize 100 typedef struct int number;char name10;int score;Student;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 10typedef int ElemType;typedef struct ElemType *elem;int length;int listsize;Sqlist;typedef struct int number;char name10;int score;ElemType;应用举例应用举例：编程实现手机电话簿管理：编程实现手机电话簿管理1.数据结构数据结构用用双向循环链表双向循环链表，每个结点的信息是：，每个结点的信息是：
