线性表的概念及运算.ppt

2.3.1 单链表 单链表的存储示例图 单链表的存储结构描述 2.3.2 单链表上的基本运算 1. 建立单链表 头插法建表算法 尾插法建表算法 2.单链表查找 按序号查找算法实现 按值查找算法实现 1) 头插法建表（逆序） 操作步骤： 建立一个“空表”； 输入数据元素an， 建立结点并插入； 输入数据元素an-1， 建立结点并插入； an an an-1 依次类推，直至输入a1为止。 s s Linklist CreateFromHead() { LinkList L;Node *s;int flag=1;//标志flag初值为1 L=(Linklist)malloc(sizeof(Node));//分配头结点 L-next=NULL; while(flag) //输入“$”时, flag置0, 建表结束 { c=getchar(); if(c!=’$’) //为新结点分配存储空间 { s=(Node*)malloc(sizeof(Node)); s-data=c; s-next=L-next; L-next=s; } //链接 else flag=0; } return L； } r c1 ∧ s L ∧ cn ∧ s r r 2) 尾插法建表：设尾指针r 建立一个“空表”, r 指向头结点; 输入数据元素C1, 建立结点并链接, r指向该结点； 输入数据元素C2, 建立结点并链接, r指向该结点； … 输入数据元素Cn, 建立结点并链接, r指向该结点； c2 ∧ s r … Linklist CreateFromTail() //新结点加到链表末尾 { LinkList L;Node *r,*s;int flag =1;//flag初值 L=(Node *)malloc(sizeof(Node)); //分配头结点 L-next=NULL; r=L; //r始终指向链表的表尾 while(flag) //输入“$”时flag为0，建表结束 { c=getchar(); if(c!=’$’) { s=(Node*)malloc(sizeof(Node));s-data=c; r-next=s; r=s } //链接 else { flag=0; r-next=NULL; } } return L； } 1) 按序号查找 算法描述：设带头结点的单链表的长度为n, 要查找表中第i个结点, 则需要从单链表的头指针L出发, 从头结点（L-next）开始顺着链域扫描, 用指针p指向当前扫描到的结点,初值指向头结点 (pL-next), 用j做记数器, 累计当前扫描过的结点数(初值为0), 当j=i 时, 指针p所指的结点就是要找的第i个结点。算法实现, 算法演示。 L 线性表的操作 Get (L, i) 在单链表中i=3时,Get的实现过程: 21 18 30 75 42 56 ∧ p p p j 1 2 3 P-data=30 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 。 令指针 p 始终指向线性表中第 j 个数据元素。 单链表是一种顺序存取的结构, 为找第 i 个数据元素, 必须先找到第 i-1个数据元素。 //找第i个结点,找到返回指向它的指针;否则返回空 Node * Get(LinkList L, int i) { Node *p； p=L；j=0； // 从头结点开始扫描 while ((p-next!=NULL)(ji) { p=p-next； j++； // 扫描下一结点 } if（i= =j）return p； // 找到了第i个结点 else return NULL； // 找不到,i≤0或in } 算法时间复杂度为: O(Length(*L)) 2) 按值查找 算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。算法实现，算法演示。 //查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL * / Node *Locate( LinkList L,ElemType key) { Node *p; p=L-nex