数据结构PPt——1

课后作业
对照不带头结点和带头结点两种单链表
的插入操作，自行分析两种单链表对于 删除操作的不同。（书面作业）
说明：
必须要做！ 虽然不讲，但是是考试内容！
21
2.3.3 链表基本算法实现(1)——初始化
生成一个带头结点的空链表
头指针 head
表头结点
^
Status InitList_L(LinkList &L){ L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;//创建头结点 return OK; }//InitList_L;
删除
T(n) = O(n)
1 n 1 ( n 1)n n 1 Tdl = ( n i ) n i 1 n 2 2
10
查找操作的时间复杂度分析
若查找成功, (设pi查找概率，ci 比较次数)
平均查找长度 ASL = pi ci
i 1 n
若查找概率 pi 均相等，则
3
顺序表算法：构造空表 InitList(Sqlist &L)
采用动态分配存储结构 实现步骤 1. 获取表存储空间 L
0 1 2
n-1
maxlen-1
elem length
0
L.elem=(ElemType *)malloc( LIST_INIT_SIZE *sizeof(ElemType) );
18
解决之道：带表头结点的单链表

空表：
头指针
表头结点
head
头指针 head 表头结点
^
…
^
首结点：存储第一个数据元素
19
单链表插入操作的算法描述
status ListInsert_L( LinkList &L, int i, ElemType e ) { // 在带头结点的链表中的第i个结点前插入元素e p=L; j=0;
1 n 1 ASL = i (1 2 n ) … n i 1 n 1 (1 n ) n 1 n n 2 2
查找不成功，数据比较 n 次。 查找操作的最坏情况时间复杂度 T(n) = O(n)
11
Summary: 顺序表
本质：逻辑上相邻，物理也相邻
if (i<1 || i>L.length+1) return -1; //i值不合法 插入位置是否合法？ //如果当前空间已满，则 增加分配空间 空间是否够用？ if (L.length>=L.listsize) increment (L) ; q=&L.elem[i-1]; //插入位置 找到插入位置； for (p=&(L.elem[L.length-1]); p>=q; --p) *(p+1)=*p; 插入位置及之后的元素右移； *q=e; 插入 e； for (j=length;j>=i;j--) L.elem[j]= L.elem[j-1]; ++L.length; 表长增 1； L.elem[i-1]=e; return 0; } // ListInsert_Sq
常见复杂度量级比较
c < log2n < n < nlog2n < n2 < n3 < 2n < 3n < n!
一般情况下，尽可能选择多项式阶O(nk)的算
法，而尽量避免指数阶的算法。
顺序表的存储结构（1）
静态分配存储结构
#define ListSize 100 //线性表的最大长度 typedef int ElemType; //线性表数据类型 typedef struct { ElemType elem[ListSize]; //静态分配的线性表空间 int length; //线性表当前长度 } Sqlist;
head a b ……
s
X
s->next 原语句： s->next=p->next; p->next=s ；
16
核心语句： s->next=head; head=s ；
单链表插入操作的特殊情况（2）

在末尾插入
head a
p
b
s
X
s->next
核心语句： s->next=NULL; p->next =s ；
方法1实现：利用基本算法建立链表
LinkList CallFunc_CreatLinkList( ) { LinkList L; int i=0; InitList(L); //初始化链表 i=1; scanf(&x); while (x!=flag)//建立链表,flag结束标志 { ListInsert(L, i, x);//结点插入链表末尾 i++; 输入：67，23，10，45，36 scanf(&x); } 67 23 10 L return L; }
int CreatListR(LinkList &H ) { int element; LinkList L; LNode *s, *last; //s指向新结点，last指向链表的最后结点 L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; //建立头结点 last=L; cin>>element; while (element !=0) { s =(LNode *)malloc(sizeof(LNode)); //申请新结点 s ->data=element; s->next=NULL; last->next= s; //新结点链入链表 last=s; //last指向新的最后结点 cin>>element; } H=L； return 0; }// CreatListR 25
}
8
插入操作时间复杂度分析
插入 前提：假设每 个位置都是等 概率的.
T(n) = O(n)
1 n1 1 Tin = ( n i 1) (n … 1 0) n 1 i 1 n 1 1 n( n 1) n ( n 1) 2 2
…
9
删除操作时间复杂度分析
13
2.3.1 单链表的定义
typedef int ElemType; typedef struct LNode{ ElemType data; //结点的数据域 struct LNode *next; //结点的指针域 }LNode, *LinkList; LNode *p; //p 是指向某个结点的指针 LNode *p; //p 是指向某个结点的指针 LNode *p; //p 是指向某个结点的指针 LinkList head ； //head 是指向单链表的头指针 LinkList head ； //head 是指向单链表的头指针 LinkList head；//head 是指向单链表的头指针 …… …… ……
静态分配的特点：线性表大小固定。
2
顺序表的存储结构（2）
动态分配存储结构：课本上主要采用的结构
#define LIST_INIT_SIZE 100 //初始空间分配大小 #define LISTINCREMENT 10 //线性表空间分配增量 typedef int ElemType; //线性表数据类型 typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的空间大小 } Sqlist; 动态分配的特点：顺序表空间可以根据需要增加。
使用基本算法: void InitList(&L)； void ListInsert(&L, i, e)
方法2：自编算法建立
思想： 1.初始化链表； 2.申请一个结点； 3.初始化它的值； 4.结点链入表尾； 5.结束否？ 6.Yes，结束创建操作； 7.No，重复步骤2-6；
方法2：尾插法建立单链表
45
36 ^
尾插法建立单链表性能分析
T(n)=O(n)
如果不设last指针，则T(n)=O(n2) 不省心，总要记住表尾。
如何改进？
头插法
头插法建立单链表（P30 算法2.11）
void CreatList_L(LinkList &L, int n) { //逆位序输入n个元素的值，建立带头结点的单链表L L=(LinkList) malloc (sizeof(LNode) ); L->next=NULL; //建立头结点 for (i=n; i>0; - -i) { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; p->next=L->next; 输入：36，45，10，23，67 L->next=p; } 67 23 10 45 36 ^ L } CreatList_L
原语句： s->next=p->next; p->next=s ；
17
单链表插入操作的特殊情况（3）

空表插入 head==NULL
核心语句： s->next=NULL; head =s ； 原语句： s->next=p->next; p->next=s ；
head
X s
太麻烦了！！！ 赶快想个办法吧！
链表基本算法实现(2)——建立单链表
建立链表的过程是一个动态生成的过程： 从空表状态，依次建立各元素结点，并逐个插入
head
^
步骤：
（1）找到单链表的末尾； （2）将新结点插入。