软件技术基础新课件.ppt

2. 数据的逻辑结构 ? 数据的逻辑结构就是数据元素之间的逻辑关系。可以用一个二元组，给出其形式定义为 Data?Structure =(D，R) 其中，D是组成数据的数据元素的有限集合，R是数据元素之间的关系集合。 顺序结构“线性表”插入算法 已知线性表的当前状态是(a1，a2，…，ai-1，ai，…，an)，要在第i个元素前插入一个元素x，线性表变为(a1，a2，…，ai-1，x，ai，…，an)。 其实施步骤为： (1) 将第n至第i个元素后移一个存储位置； (2) 将x插入到第i个位置； (3) 线性表的长度加1。 第i个数据元素之间插入一个新的数据元素。 int Insert_list(list * L , int x, int i) { int j; if ( (i1)||(i(L-final)+2))） return (NULL);\\ if ( (L- final =m-1) return (0); for (j= L- final ；j=i-1；j- -) L-array[j+1]= L-array[j]； //从i开始的元素后移 L-array[i-1]=x； L- final =L- final +1； return (L- final +1); } 顺序结构“线性表”删除算法 已知线性表的当前状态是(a1，a2，…，ai-1，ai，ai+1，…，an)，若要删除第i个元素ai，则线性表成为(a1，a2，…，ai-1，ai+1，…，an)。 具体实施步骤为： (1) 若i值合法，则将第i+1至第n个位置上的元素依次向前移动一个存储单位； (2) 将线性表的长度减1。 在表长为n的线性表中删除第i个数据元素 int Delete_list(list *L ,int i) { int j; if ((i1)||(iL-final+1)) return (0); for (j=i; j= L-final; j++) L-array[j-1]= L-array[j]； L-final= L-final –1; return (L-final+1); } 顺序结构线性表的查找算法 在线性表中查找关键字为x的元素，并返回位置。 int Locate_list(list *L , int x) { int i; for (i=1; i=L-final; i++) if (array[i-1]==x) return (i); return (-1); } (1）线性链表(单链表):链式存储的线性表 结点除信息域外还含有一个指针域，用来指出其后继结点的位置 最后一个结点没有后继结点，指向它的指针域为空(记为NIL 或∧)。另外还需要设置一个头指针head，指向单链表的第一个结点，如下图示： 链表的重要特点是：插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可。 单链表(的结点)的C语言描述 typedef struct Linear_chain_node { Element data; struct Linear_chain_node *link; } NODE; 或者： struct Linear_chain_node { Element data; struct Linear_chain_node *link; }; typedef struct Linear_chain_node NODE; 结点的表示 建立单链表（算法） 创建有n个结点的单链表，结点数值从键盘输入，函数返回链表的 头结点(算法中将已将结点的数值域简化为int简单类型)。 NODE *Create_single_chain (int n) { NODE *head, *p, *q; int i; p=(NODE *)malloc(sizeof(NODE)); p-data=0; p-link=NULL; head=p; for (i=1;i=n;i++) { q=(NODE *)malloc(sizeof(NODE)); scanf(“%d”,q-data); q-link=NULL; p-link=q; p=q; } return (head); } 查找单链