软件技术基础线性结构

1、课程内容数据结构（重点）操作系统软件工程数据库技术（略）网络技术 （略） 数值 非数值第一章 数据结构1.1.1 什么是数据结构数 据： 能被计算机识别、存储和加工处理的符号的集合，是计算机的操作对象的总称。例：1）图书馆的书目检索系统自动化问题2）人机对弈问题3）邮递员送信问题数据元素：数据的基本单位。计算机通常将其作为一个整体进行处理。 数据结构：数据元素相互之间的联系或组织形式。可以看作是相互之间存在着某种特定关系的数据元素的集合。 四种基本结构示意图 (a) 集合结构； (b) 线性结构； (c) 树形结构； (d) 图结构研究内容（3方面）1）逻辑结构2）存储结构3）操作集合例子：

2、有一个学生表如下所示。这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和成绩)组成。学号姓名性别成绩1张斌M902刘丽F923李英F814陈华M925王奇M896董强M997王萍F851.1.3 基本概念1.逻辑结构：线性：开始-终点，一个直接前趋，直接后继，线性表非线性：图结构，树结构2.存储结构：顺序：线性表，数组链接：指针索引：索引表（关键字，地址） 稠密索引： 稀疏索引：散列：散列函数数据*3.操作集合 遍历(所有) 插入 更新 删除 查找 排序结合：逻辑结构存储结构操作线性线性表顺序 顺序表链接 链接表索引 索引表散列 散列表一端 栈两端 队列非线性1.2

3、线性结构逻辑特征特点：有序，有限 序列线性表，栈，队列，数组，串1.2.1 线性表（n个数据元素的有限序列）逻辑结构 同一类型的数据元素，1in，（表长n）数据元素，可为数或记录或其他。 1.定义数据元素 typedef int elemtype ;或 typedef struct student elemtype ;存储结构操作集合initiate_list（L）length_list（L）get_list（L，i）locate_list（L，x）insert_list（L，i，x）delete_list（L，i）一、顺序表内存存储地址Loc(a1)Loc(a1)+kLoc(a1)+(i-1

4、)*kLoc(a1)+(n-1)*k 地址连续顺序表的描述 struct list_type elemtype dataMAXNUM; int num; typedef listtype; 顺序表的基本操作1.顺序表的初始化 void initiate_list(listtype *l) l-num=0;2. 顺序表的插入算法 原表已有n个元素a0ai an-2a0 xai+1an-1an i ian-1 #define true 1 #define false 0 int insert_list(listtype *l,int i,elemtype x) int j; if(l-num=MA

5、XNUM) printf(“the list is full,can not insert”); return(false); if(il-num) printf(“i is invalid value”); return(false); for(j=l-num-1;j=i;j-) l-dataj+1= l-dataj; l-datai=x; l-num+; return(true);顺序表的删除算法a0aian-2an-1a0ai+1 an-1 原表已有n个元素 int delete_list(listtype *l,int i) int j; if(il-num-1) printf(“i

6、is invalid value”); return(false); for(j=i;jnum-1; j+) l-dataj= l-dataj+1; l-num-; return(true);顺序表的优缺点优点：逻辑关系隐含在地址中，无需额外表示，由编号可以直接访问缺点：插入删除效率低，固定分配数大于元素个数二、线性链表单向链表双向链表循环单向链表循环双向链表1.单向链表数据元素： struct node1 elemtype data; struct node1 *next; ;datanexta1 a2 a3 an h NULLtypedef struct node1 node; void

7、initiate_sl(node *h) *h=(node *)malloc(sizeof(node); (*h)-next=NULL;空链：(1)访问单链表 elemtype access_sl(node *h,int i) node *p; int j=0; p=h; while(p-next!=NULL & jnext; j+; if(j!=i) return(-1); else return(p-data);(2)插入运算 void insert_sl(node *h,int i,elemtype x) node *p,*t; int j=0; p=h; while(p!=NULL&j

8、next; j+; if(j!=i-1) printf(“i is invalid”); return; t=(node *)malloc(sizeof(node); t-data=x; t-next=p-next; p-next=t;(3)单链表的删除运算 void delete_sl(node *h,int i) node *p,*s; int j=0; p=h; while(p-next!=NULL&jnext; j+; if(j!=i-1) pintf(“i is invalid”); return; s=p-next; p-next=s-next; free(s); (4)单链表的建

9、立先建立一个空链表，然后插入新的数据单链表生成算法(设每个节点为int,-1为结束标记) void create_sl(node *h) node *p,*s; int j; int x; *h = (node*) malloc (sizeof(node)； (*h)-next=NULL; pread(&x); while(x!=-1) s=(node *)malloc(sizeof(node); s-data=x; if(*h)-next=NULL) (*h)-next=s; else p-next=s; p=s; pread(&x); p-next=NULL;2.双链表 struct no

10、de2 elemtype data; struct node2 *prior,*next;priordatanextbcapp-prior-next= p= p-next-proir;typedef struct node2 dnode;算法7双链表的插入xSbaP void insert_dl(dnode *p,elemtype x) node *t; t=(node *)malloc(sizeof(node); t-data=x; p-prior-next=t; t-next=p; t-prior=p-prior; p-prior=t;算法8双链表的删除bcp-prior-next=p-next;p-next-prior=p-prior;pa void delete_dl(dnode *p) p-prior-next=p-next; p-next-prior=p-prior;3.循环链表:h采用尾指针r来命名h空表单链表： rL空双向循环链表：非空双向循环链表：LAB r例：实现两个线性表（ ）和（ ）链成一个线性表（ , , , ）上的运算。haa1anhbb1 void connect_a(node *ha,node *hb)node *p; p=h