软件参考课件数据结构

1、连续存储方式（顺序表） 优点：存储利用率高，存取速度快 缺点：插入、删除等操作时需要移动大量数据链式存储方式（链表） 特点：适应表的动态增长和删除 缺点：需要额外的指针存储空间(2)链表的操作单链表 (Singly Linked List)特点 每个元素(结点node)由数据和指针构成。 线性结构。结点之间可以连续，可以不连续存储;结点的逻辑顺序与物理顺序可以不一致;表可扩充。data linka0a1a2a3a4headA386A194A4NULLA222A1A2A3A4 22388694存储地址 数据域 指针域head38head链表存储结构示意图如下：指针操作假如p为指向某一结点的指针则

2、该结点的数据域用p-data表示该结点的指针域用p-link表示它们都是变量，可以被赋值，也可向其他变量赋值。例如: 假定data为整型变量,则p-data=5; p-next=NULL; 将结点变为: p p-data p-linkpaiai-1ai+1aiai-1ai+1qqpp 如果q为指向结点ai的指针，那么q-link就是指向ai后继结点ai+1的指针；若p为另一同类型指针变量 指针操作p=q-link p指向q所指结点的后继p=q 指针p指向指针q所指的结点节点操作示例 -用类class Nodepublic: /实际使用时较少这样定义,注意后面链表类的定义 int value;

3、Node * link; public: Node(int i) value = i; link = NULL; ;void main () Node *p1, *p2; p1 = ; p2 =p110p220new Node(10)new Node(20);p1-link=p2;p p-data p-link class ListNode /定义链表结点类 friend class LinkedList; /定义链表类为其友元类 private: int data; /结点数据 ListNode * link; /结点指针 public: ListNode(int i) data = i;

4、link= NULL; ; class LinkedList /定义链表类 private: ListNode *head , *tail; /定义表头指针、表尾指针 public: .;单链表类的定义方式作为结点类的友元类一个类的友元类可以访问该类的私有成员定义LinkedList类(作为结点类的友元类):class LinkedList private: ListNode *head; ListNode * tail;public: LinkedList() head= NULL; tail = NULL; void addNode(int value);/在表尾加一结点 void pri

5、nt();/遍历全表,输出所有结点 void insert(int value); /顺序插入一结点 void delNode(int value);/删除一结点 ;class ListNode friend class LinkedList; private: int data; ListNode * link; public: ListNode(int i) data = i; link= NULL; ;假设以上定义存放于文件linkedlist.h中实现部分存放于文件 linkedlist.cpp中#include iostream.h#include linkedlist.hvoid

6、LinkedList:addNode(int value) ListNode *newNode; newNode = new ListNode(value); if (head = NULL) ; ; else ; ; void LinkedList: print() ListNode *temp=head; while (temp!=NULL) coutdatalink = newNodetail = newNodetemp = temp-link单链表中的插入 第一种情况：在链表最前端插入 ; ;（插入前） （插入后） headnewnodenewnodeheadnewnode-link

7、= headhead = newnode(插入前) (插入后) 第二种情况：在链表中间插入(插入到指针p所指向的节点之后) ; ；newnode pnewnode pnewnode-link = p-linkp-link = newnode 第三种情况：在链表末尾插入 ;(插入前) (插入后)newnodenewnode p pp-link = newnodenewnode-link = NULL;假定已有一个链表的表头为head,其data域的值由小到大排列,现插入一个新的结点newnode,要求插入后仍保持由小到大的顺序,通过前面的讨论,可将插入操作分为如下几种:1.若链表为空,则将new

8、node的link置为NULL,并将head指向newnode2.若链表不是空表，则首先确定newnode的插入位置。 则分三种情况: 插在第一个结点之前： 将newnode的link指向head的第一个结点,再将head指向newnode 插在链表中间(假设在p指向的结点后插入)： 将newnode的link指向p的link ,再将p的link指向newnode 插在链表的末尾： 将最后一个结点的link指向newnode，将newnode的link置为NULL。顺序单链表的插入方法:void LinkedList:insert(int value)ListNode *p1,*p2,*new

9、node;newnode= ;p1=head;if(head=NULL) /空表 head=newnode; newnode-link=NULL; /此语句可省，构造函数中已实现此功能 else /非空表while(p1!=NULL&valuep1-data)/找插入位置p2=p1; /p2为p1的前驱指针 ;new ListNode(value)p1=p1-link if(p1=head) /插到第一个结点前 ; ; else if(p1=NULL) /插到最后一个结点后 ; newnode-link=NULL; /此语句可省，构造函数中已实现此功能 else /插到p2之后,p1之前 ;

10、; newnode-link=headhead=newnodep2-link=newnodep2-link=newnodenewnode-link=p1单链表中的删除第一种情况: 删除表中第一个元素第二种情况: 删除表中或表尾元素在单链表中删除含ai的结点ai-1ai-1aiaiai+1ai+1p2p1删除前删除后p2-link=p1-linkdelete p1;void LinkedList: delNode(int value) ListNode *p1,*p2; /p1为工作指针,p2为p1的前驱 p1 = head; if(head=NULL) /空表 coutlink; if(p1=

11、 =head) /删除第一个结点 ; delete p1; /释放被删除结点占用的空间 else if(p1!=NULL) /删除非表头结点 ; delete p1; else /未找到要删除的元素 coutvaluedata!= valuehead=p1-linkp2-link=p1-linkvoid main() LinkedList ll; /定义链表类对象 int x; for (int i=0;ix; ll.addNode(x); /向表尾添加结点 /ll.insert(x); /向表中顺序插入结点 ll.print(); cinx; ll.delNode(x); /删除一结点 ll

12、.print();(3)带表头结点的单链表表头结点位于表的最前端，本身不带数据，仅标志表头。设置表头结点的目的是统一空表与非空表、表头和表中位置的操作形式，简化链表操作的实现。非空表 空表0an-1a0headhead0思考带表头结点的链表类的构造函数与不带表头结点的有何不同?class LinkedList private: ListNode *head; ListNode * tail; public: LinkedList( ) head=new ListNode(-1); /-1不是有效数据 tail = head; .;class ListNode friend class Link

13、edList; private: int data; ListNode * link; public: ListNode(int i) data = i; link= NULL; ;注意-1仅是为调用ListNode 类的构造函数提供一个初值，该值不是链表中有效数据，访问链表中数据时从第二个数据开始在带表头结点的单链表最前端插入新结点 newnode-link = p-link; p-link = newnode;headnewnodeheadnewnode插入headnewnodeheadnewnode插入pppp非空表空表q = p-link;p-link = q-link;delete q; 从带表头结点的单链表中删除最前端的结点headhead