(4.1.1)--直播-线性表作业讲解.ppt
第1章 线性结构单链表作业程序设计课程实践常用链表类型一般结点类型定义如下：struct Node DataElem data;struct Node*next;struct Node *p，*q;/声明指针型变量p、q常用链表类型单链表的常用操作单链表的常用操作单链表的常用操作单链表应用举例根据单链表处理知识，直接完成递增有序单链表构造、插入、显示、销毁的典型案例。请输入若干个需要插入的正整数，非正整数代表输入结束:5 2 4 1 9 8 3 01-2-3-4-5-8-9structNode intdata;struct Node*next;/将元素插入有序单链表中，插入后仍然有序void Insert(struct Node*la,int x);/销毁单链表void Destory(struct Node*la);/打印单链表void Print(struct Node*la);9/动态分配一个结点，返回结点指针/分配失败时，简化程序，退出运行struct Node*NewNode()struct Node*p;p=(struct Node*)malloc(sizeof(struct Node);if(p=NULL)/分配失败 printf(Error:out of memoryn);exit(-1);/简化程序，退出运行 return p;10/将元素插入有序单链表中，插入后仍然有序void Insert(struct Node*la,int x)struct Node*q=NewNode();/申请结点 q-data=x;/查找合适插入位置 struct Node*p=la;while(p-next&x p-next-data)p=p-next;/往后移一位置 /将结点插入p所指结点后 q-next=p-next;p-next=q;11/打印单链表void Print(struct Node*la)la=la-next;/头结点无数据 if (la)/数据比-多一个 printf(%d,la-data);la=la-next;while(la)printf(-%d,la-data);la=la-next;printf(n);12/销毁单链表void Destory(struct Node*la)while(la)struct Node*q=la-next;free(la);/释放指针所指结点 la=q;13int main()/建立带头节点的单链表 struct Node*la=NewNode();la-next=NULL;intx;printf(请输入若干个需要插入的正整数，非正整数代表输入结束:n);scanf(%d,&x);while(x 0)/将元素插入有序单链表中，插入后仍然有序 Insert(la,x);scanf(%d,&x);（待续）14 /打印单链表 Print(la);/销毁单链表，避免内存泄漏 Destory(la);return 0;运行情况如下：请输入若干个需要插入的正整数，非正整数代表输入结束:5 2 4 1 9 8 3 01-2-3-4-5-8-915课后作业第1题1.编写程序，建立2个带头结点单链表，输入若干整数将正整数插入第1个单链表，将非正整数插入第2个单链表，插入前和插入后单链表保持递增或相等次序，显示2个单链表，最后销毁。程序不可存在内存泄漏。运行情况如下：-5 2 4 -1 9 8 -3 02-4-8-9-5-3-1-0课后作业第1题（1）定义链表结构体struct Node int data;struct Node*next;课后作业第1题（2）搭建程序整体框架课后作业第1题（3）实现各模块功能课后作业第1题课后作业第1题课后作业第1题课后作业第1题int main()struct Node*la1=NewNode();la1-next=NULL;struct Node*la2=NewNode();la2-next=NULL;intx;while(scanf(%d,&x)!=EOF)if(x 0)Insert(la1,x);else Insert(la2,x);Print(la1);Print(la2);Destory(la1);Destory(la2);return 0;第一章35910-127la1la1la2la2第一章第一章第一章单链表基本操作的实现/链表结点类型struct Node DataElem data;struct Node*next;/线性表类型struct List struct Node*pHead;struct Node*pTail;typedef struct Node*Position;/线性表中位置类型30 1.创建空线性表/空表管理的单链表只有一个头结点，失败时首尾指针为NULLstruct List Create()struct List list;/申请一个结点 list.pHead=list.pTail=(struct Node*)malloc(sizeof(struct Node);if(list.pHead!=NULL)list.pHead-next=NULL;/后续无结点 return list;312.线性表清空/释放链表中除头结点外所有结点void Clear(struct List*pList)struct Node*p=pList-pHead-next;/从头结点后结点开始删除 while(p!=NULL)/直到最后 struct Node*q=p;/记住要释放结点 p=p-next;/准备释放下一个 free(q);/释放结点，释放后不可再访问结点 pList-pHead-next=NULL;/头结点后已无结点 pList-pTail=pList-pHead;323.销毁一个线性表，不再使用，释放所有结点/传入链首指针变量的地址，销毁单链表void Destroy(struct List*pList)Clear(pList);/单链表清空 free(pList-pHead);/释放最后剩余的头结点 pList-pHead=pList-pTail=NULL;/将线性表中指针变量置空334.根据已有线性表，复制一个内容相同的新线性表/传入原线性表，复制原线性表中链表作为新线性表的链表，/返回复制后新线性表，失败时返回线性表的头指针为NULL，struct List Copy(struct List srcList)struct List destList;destList=Create();/创建带头结点的空单链表 if(destList.pHead=NULL)return destList;/创建失败时直接返回 struct Node *p;p=srcList.pHead-next;/跳过原链表头结点 while(p!=NULL)/循环处理原链表 struct Node*s;s=(struct Node*)malloc(sizeof(struct Node);/分配新结点 （待续）34 if(s=NULL)Destroy(&destList);/申请失败时销毁线性表，避免内存泄漏 return destList;s-data=p-data;/复制元素 destList.pTail-next=s;/挂在新链表最后 s-next=NULL;/后面无结点 destList.pTail=s;/最后一个结点已变化 p=p-next;/准备复制下个结点 return destList;/返回复制完的线性表355.线性表判空/判断线性表是否为空表，若是则返回1，否则返回0int IsEmpty(struct List list)return(list.pHead-next=NULL);/头结点后无结点366.线性表求长度/返回线性表中数据元素的个数int Length(struct List list)int iCount=0;struct Node*p=list.pHead-next;/从头结点后结点开始计数 while(p!=NULL)/直到最后 +iCount;p=p-next;/临时变量移至下一结点 return iCount;377.获取起始位置/返回线性表中代表第一个元素的位置，空表返回EndPosition(L)Position BeginPosition(struct List list)return list.pHead;8.获取结束位置/返回代表线性表结束的位置Position EndPosition(struct List list)return list.pTail;389.迭代下一位置/返回线性表中p有效位置的下个位置，主要用于循环遍历线性表Position NextPosition(struct List list,Position pos)return pos-next;3910.获取元素位置/返回线性表代表第i个元素所在位置，1in（设线性表的表长为n）Position LocatePosition(struct List list,int i)Position pos=list.pHead;/从头结点开始 while(-i 0&pos-next!=NULL)/计数完成或直到结束 pos=pos-next;/移至下一结点 return pos;4011.定位元素位置/根据数据元素e查找它在线性表中出现的位置，若存在，则返回它的有效位置；/否则返回EndPosition(L)Position LocateElem(struct List list,DataElem e)Position pos=list.pHead;/从头结点开始 while(pos-next!=NULL&pos-next-data!=e)pos=pos-next;/移至下一结点 return pos;/返回元素所在结点的前一个结点指针4112.获取元素/返回线性表L中pos有效位置的数据元素DataElem GetElem(struct List list,Position pos)assert(pos!=EndPosition(list);/断言，包含头文件assert.h return pos-next-data;13.设置元素/将线性表中pos有效位置的数据元素设置为evoid SetElem(struct List list,Position pos,DataElem e)assert(pos!=EndPosition(list);/断言，包含头文件assert.h pos-next-data=e;4214.插入元素/在线性表的pos位置前插入一新的数据元素，/pos为EndPosition(L)时添加在尾部，线性表长度加1/成功时返回1，失败时返回0int InsertBefore(struct List*pList,Position pos,DataElem e)struct Node*s=(struct Node*)malloc(sizeof(struct Node);/分配新结点 if (s=NULL)return 0;s-data=e;s-next=pos-next;/插入在pos所指结点后 pos-next=s;if(pList-pTail=pos)pList-pTail=s;/插入在线性表最后时，调整尾结点指针 return 1;4315.删除元素/删除线性表中pos有效位置所在数据元素，线性表的表长减1void Delete(struct List*pList,Position pos)assert(pos!=EndPosition(*pList);/断言，包含头文件assert.h struct Node*s=pos-next;/待删除结点 pos-next=s-next;/链表中删除结点 free(s);/释放结点 if(pList-pTail=s)pList-pTail=pos;/删除线性表最后一个结点时，调整尾结点指针44谢谢观看
