陈海明 副教授 信息学院 计算机系 http://www.chenhaiming.cn 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系 http://www.chenhaiming.cn

数据结构 线性表 顺序表 链表 线性结构 栈 队列 树结构 图结构 操作系统->进程管理 服务器->进程线程管理 线性表 顺序表 链表 栈 队列 线性结构 操作系统->进程管理 服务器->进程线程管理 人工智能->博弈树 数据挖掘->决策树 多媒体技术->哈夫曼树 树结构 图结构 人工智能->神经网络，贝叶斯网络

线性表的顺序存储（顺序表） 优点： 缺点： 1、不需要额外空间来表示结点的逻辑关系 2、随机存储方便 1、插入/删除效率低 2、需事先确定存储规模

改进的顺序表

线性表的链式存储（链表） 1、初始化链表 2、插入（头部插入，尾部插入，指定位置前插入，指定位置后插入） 3、求链表长度 data ^ … Linklist1 typedef struct _node{ ElemType data; struct _node *next; }Node,*LinkList; 在链表中引入 头指针节点，可以使程序设计更简洁，因为这样可以避免把空表作为一种特殊情况来对待。 1、初始化链表 2、插入（头部插入，尾部插入，指定位置前插入，指定位置后插入） 3、求链表长度 4、查找：按序号/按值（顺链域逐个搜索） 5、删除

链表——初始化 LinkList LinkList1=(LinkList)malloc(sizeof（Node）); memset(LinkList1, 0, sizeof(Node)); Linklist1

链表——插入 Node *pNewNode=（Node *）malloc(sizeof(Node)); pNewNode->data 赋值； 头插法： pNewNode->next=LinkList1->next; LinkList1->next=pNewNode; 尾插法： Node *pNode=LinkList1; while (pNode->next) pNode=pNode->next； pNewNode->next=pNode->next; pNode->next=pNewNode; 指定位置后插入

如何用指定位置后插入实现头插法和尾插法？ 链表—插入（指定位置后插入） pNode data ^ … Linklist1 pNewNode data pNewNode->next=pNode->next; pNode->next=pNewNode; 如何用指定位置后插入实现头插法和尾插法？

链表——求长度 Node *pNode=LinkList1->next; int length=0; while (pNode) { length++; pNode=pNode->next; } return length;

链表——查找 按序号 按值 Node *pNode=LinkList1->next; 输入index; /*index从1开始*/ for (int i=1; i<index; i++) pNode=pNode->next; return (pNode); 按值 while (pNode && pNode->data与要找的值不等) { pNode=pNode->next； } If (pNode==NULL) 没有找到；else return (pNode);

链表—插入（指定位置前插入） preNode pNode Node *preNode=LinkList1; data ^ … Linklist1 pNewNode data Node *preNode=LinkList1; while (preNode->next !=pNode) preNode=preNode->next； 指定位置后插入（preNode）;

链表—删除 preNode pNode Node *preNode=LinkList1; data ^ … Linklist1 Node *preNode=LinkList1; while (preNode->next !=pNode) preNode=preNode->next; preNode->next=pNode->next; free(pNode);

链表—空间循环利用 删除节点时，将删除的节点插入到spCollector链表中 data ^ … Linklist1 data ^ … SpCollector 删除节点时，将删除的节点插入到spCollector链表中 建立和插入链表时，先看spCollector的长度是否大于0，如果是，则从中获取空间，否则malloc新空间；

链表 ADT LinkList{ } LinkList Initialize(); int Length(LinkList linklist); Node *IndexOfList(LinkList linklist, int index); Node *SearchList(LinkList linklist, T data); Node *SurInsert(Node *pNewNode, Node *pNode); Node *Delete(Node *pNode); void Output(LinkList linklist); }

链表——扩展 单向列表 单向循环列表 双向列表 双向循环列表

单向循环链表 ADT LinkList{ } LinkList Initialize(); int Length(LinkList linklist); Node *IndexOfList(LinkList linklist, int index); Node *SearchList(LinkList linklist, T data); Node *SurInsert(Node *pNewNode, Node *pNode); Node *Delete(Node *pNode); void Output(LinkList linklist); }

单向循环列表——初始化、查找 Node *SearchList(LinkList linklist, T data) { … Linklist1 Node *SearchList(LinkList linklist, T data) { Node* pNode=linklist->next; while (pNode !=linklist && pNode->data !=data) pNode=pNode->next; if (pNode!=linklist) return pNode; } Linklist1

单向循环列表——指定位置后插入 pNode pNode data … Linklist1 pNewNode Node *SurInsert(LinkList linklist, Node *pNewNode, Node *pNode); pNewNode->next=pNode->next; pNode->next=pNewNode; }

作业 1425 1396 2438 完成时间10月7日23：55之前

双向列表和双向循环列表