《软件技术_线性结构_线性表》由会员分享，可在线阅读，更多相关《软件技术_线性结构_线性表（45页珍藏版）》请在金锄头文库上搜索。
1、计算机软件技术基础 机械工业出版社第三章 线性结构本章基本内容与要求n基本内容q线性表、栈、队列和数组等线性结构的概念、 存储结构、逻辑结构、相关运算及应用 n要求q掌握线性表、栈、队列的数据结构、能够根据 实际应用选择相应的数据结构及其运算q掌握数组的逻辑结构定义以及存储方式,了解特 殊结构的矩阵：如三角矩阵，三对角阵和稀疏 矩阵的存储及其相应的运算。 1数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构 B非线性结构A 顺序存储B 链式存储 线性表 栈 队树形结构图形结构数据结构的三个方面 数据结构可描述为 Group=（D，R）数组本节重点：
2、 1。线性表的定义，线性表的数据结构、逻辑结构、存储结构 、运算2。线性表的顺序存储结构、链式存储结构第一节 线性表一 线性表的定义及其运算1线性表的定义线性表（linear list）是n（n0）个数据元素a1，a2，,an组成 的有限序列。其中n称为数据元素的个数或线性表的长度，当n=0时 称为空表，n0时称为非空表 线性表中的数据元素的类型是相同的；线性表中数据元素的个 数是有穷的；线性表中的相邻数据元素是一对序偶。即相邻的数据 元素ai-1，ai（1in）存在序偶关系(ai-1，ai）；a1无前驱，an无 后继，其它每个元素有且仅有一个前驱和一个后继。 2线性表的特征 1）有且仅有一个
3、开始结点(表头结点) a1，它没有直接前驱 ，只有一个直接后继； 2）有且仅有一个终端结点(表尾结点) an，它没有直接后继 ，只有一个直接前驱； 3）其它结点都有一个直接前驱和直接后继； 4）元素之间为一对一的线性关系。 线性表是一种典型的线性结构，用二元组表示为：linear_list=(A,R) 其中 A=ai 1in, n0, aielemtypeR=rr= 1in-1线性表的存储结构1.顺序存储结构：顺序存储结构的线性表称为顺序表2.链式存储结构链式存储结构的线性表称为线性链表三 线性表的顺序存储结构线性表的顺序存储结构,也称为顺序表。其存储方式为：在内存中开 辟一片连续存储空间，但
4、该连续存储空间的大小要大于或等于顺序表的长 度，然后让线性表中第一个元素存放在连续存储空间的第一个位置，第二 个元素紧跟着第一个之后，其余依此类推 顺序表可用C+语言描述为: const int maxsize = maxlen； /maxlen表示线性表允许的最大长度 struct sequenlist elemtype amaxsize; /表示线性表（a1，a2，.,an）int len; /len表示线性表的实际长度 ；C输入输出C中无专门的输入、输出语句用输入 、输出流来实现输入流cin输出流cout使用输入输出法时，必须在文件开始加入 下列语句n include输入流cinn一般格
5、式n cinvar1var2varn抽取符 暂停程序执行，等待用户从键盘上输入数据 抽取符后面只能跟一个变量名；但”var” 可以重复多次至少需要一个变量可选输入cinu输入10进制整数和实数int i,j; cinij; 从键盘输入: 35 77或输入: 35 77 则i=35,j=77 float x,y; cinxy; 输入:3.141592 100 或输入：3.141592100 则x=3.141592,y=100.0 注意： 从键盘上输入的数据的个数、类型及顺序必须与 在cin中列举的一一对应。 输出coutn一般格式n cout=maxsize-1) coutL.len+1) co
6、ut=i;j-)L.aj+1=L.aj; /元素后移 L.ai=x; /插入元素 L.len+; /表长度增加1 顺序表的删除运算ai-1aiai+1an前移void Delete(sequenlist if(iL.len)cout datap-nextpstruct student int num;char name20;char sex;int age;float score;char addr30; struct student stu1,stu2; 线性链表的基本操作n指针赋值n指针移动pss = pp = p - nextpp线性链表的基本操作n后插n前插sp s-next= p-n
7、extspq headq=head While (q-next!=p)q=q-next p-next=s q-next=s s-next=panaiPai-1单链表的插入运算void lbcr (node *p, int x) / 在P所指向的结点之后插入新的结点node *s; / 定义指向结点类型的指针s=new node; /生成新结点s-data=x; s-next=p-next;p-next=s;return struct node int data; node *next; ;void lbcr (node *p, int x) / 在P所指向的结点之后插入新的结点node *s;
8、 / 定义指向结点类型的指针s=new node; /生成新结点s-data=x; s-next=p-next;p-next=s;return anaiPai-1单链表的插入运算struct node int data; node *next; ;Ss=(node *)malloc(sizeof(node);void lbcr (node *p, int x) / 在P所指向的结点之后插入新的数据域为x的结点node *s; / 定义指向结点类型的指针s=new node; /生成新结点s-data=x; s-next=p-next;p-next=s;return anaiPai-1单链表的插
9、入运算struct node int data; node *next; ;xSvoid lbcr (node *p, int x) / 在P所指向的结点之后插入新的新的数据域为x结点node *s; / 定义指向结点类型的指针s=new node; /生成新结点s-data=x; s-next=p-next;p-next=s;return anaiPai-1单链表的插入运算struct node int data; node *next; ;xSvoid lbcr (node *p, int x) / 在P所指向的结点之后插入新的新的数据域为x结点node *s; / 定义指向结点类型的指针
10、s=new node; /生成新结点s-data=x; s-next=p-next;p-next=s;return anaiai-1单链表的插入运算struct node int data; node *next; ;x SPPai-1a1aiai+1 Lpvoid lbsc(node *p) / 删除p指针指向结点的后一个结点 node *q; if(p-next !=NULL) q=p-next ; /q指向p的后继结点 p-next=q-next; / 修改p结点的指针域 delete q ; / 删除并释放结点 单链表的删除运算struct node int data; node *n
11、ext; ;ai-1a1aiai+1 Lpvoid lbsc(node *p) / 删除p指针指向结点的后一个结点 node *q; if(p-next !=NULL) q=p-next ; /q指向p的后继结点 p-next=q-next; / 修改p结点的指针域 delete q ; / 删除并释放结点 单链表的删除运算struct node int data; node *next; ;qai-1a1aiai+1 Lpvoid lbsc(node *p) / 删除p指针指向结点的后一个结点 node *q; if(p-next !=NULL) q=p-next ; /q指向p的后继结点
12、p-next=q-next; / 修改p结点的指针域 delete q ; / 删除并释放结点 单链表的删除运算struct node int data; node *next; ;qai-1a1aiai+1 Lpvoid lbsc(node *p) / 删除p指针指向结点的后一个结点 node *q; if(p-next !=NULL) q=p-next ; /q指向p的后继结点 p-next=q-next; / 修改p结点的指针域 delete q ; / 删除并释放结点 单链表的删除运算struct node int data; node *next; ;qfree(q);带头结点的线性
13、链表a1a2ana3L.带头结点的线性链表La1a2a3.an不带头结点的线性链表2链表运算（1）头插法建立单链表 从左边插入结点，此链表为不带头结点的 单链表。每次生成的新结点，插入到表头。 link *hcreat( ) link *s,*p; int i;cini; /输入结点数值，为0时算法结束p=NULL;while(i) s=new link; s-data=i; /s指向生成的新结点s-next=p; p=s; /插入到表头cini; return p; （2）尾插法建立单链表 从右边插入结点，此链表为带头结点的 单链表。每次生成的新结点，插入到表尾。 link *rcreat( ) link *s,*r,*p; int i;p=r=new link; p-next=NULL; /生成一个头结点cini;while(i) s=new link; s-data=i; /s指向生成的新结点 r-next=s; /s指向的结点插入到最后一个结点r=s; / r总指向表尾结点 cini; r-next=NULL; return p; （3）单链表上的查找运算 1) 按值查找Locate(head,x) 在单链表head中，查找值为x的结点，若找 到，返回它的地址，否则返回
