《数据结构域算法设计-第2章 线性表 B 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第2章 线性表 B 课件（26页珍藏版）》请在金锄头文库上搜索。
1、动态数组简介先为顺序表空间设定一个初始分 配量，一旦因插入元素而空间不足时 ，可为顺序表增加一个固定长度的空 间增量。#define LIST_INIT_SIZE 100 /存储空间的初始分配量 #define LISTINCREMENT 10/存储空间的分配增量 Typedef structElemType *elem; /表基址(用指针*elem表示）int length; /表长度（表中有多少个元素）int listsize; /当前分配的表尺寸（字节单位 ） SqList;注：三个分量可简写为：L.elem L.length L.listsize存储结构描述如下（见教材P22）：1si
2、zeof(x)算符的意思是： 计算变量x的长度(字节数)malloc (m)函数的意思是：新开一 片大小为m字节的连续空间，并把 该区首址作为函数值。Status InitList_Sq( SqList If(!L.elem) exit(OVERFLOW); /分配失败，结束程序L.length=0; /暂无元素放入，空表L.listsize=LIST_INIT_SIZE; /表尺寸=初始分配量Return OK; /InitList_Sq动态创建一个动态创建一个空空顺序表的算法：顺序表的算法：2realloc (*p, newsize)函数的意思是：新开一 片大小为newsize的连续空间，
3、并把以*p为 首址的原空间数据都拷贝进去。动态顺序表的插入算法动态顺序表的插入算法 Status ListInsert_Sq(SqList / 检验i 值的合法性if ( L.length L.listsize ) /若表长超过表尺寸则要增加尺寸 newbase = ( ElemType* ) realloc ( L.elem , (L.listsize + + LISTLISTINCREMENTINCREMENT )* sizeof ( ElemType ) );if (newbase=NULL )exit( OVERFLOW ) ; /分配失败则退出并报错L.elem = newbase
4、; /重置新基址L.listsize = L.listsize + + LISTINCREMENT LISTINCREMENT ; /增加表尺寸3q = / q为插入位置。这是没有头结点的情况for ( p = p=q ; -p ) *(p+1) = *p ;/插入位置及之后的元素统统后移, p为元素位置*q= e ; /插入e+L.length ; /增加1个数据元素，则表长+1return OK ; /ListInsert_Sq4动态顺序表的删除算法动态顺序表的删除算法 Status ListDelete_Sq(SqList / i 值不合法，返回p= / p 是被删除元素的位置e=*p;
5、 /被删除元素的值赋给 e q=L.elem+L.length-1; / q 是表尾的位置for(+p; pdata=aa; p-next=q q; 方式3： p指向结点地址，然后 (*p).data=aa； (*p).nextq qaabq qp p17设p为指向链表的第i个元素的指针,则第i个元素的 数据域写为 ，指针域写为 。练习：p-dataai的值p-nextai+1的地址附1：介绍C的三个有用的库函数/算符（都在 中）： sizeof(x)计算变量x的长度（字节数）； malloc(m) 开辟m字节长度的地址空间，并返回这段空间 的首地址； free(p) 释放指针p所指变量的存储
6、空间，即彻底删除 一个变量。18size of(x) 计算x的长 度 mall oc(m) 开m字节空 间 free( p) 删除一个 变量问1：自定义结构类型变量node的长度m是多少？问2：结构变量node的首地址(指针p）是多少？问3：怎样删除结构变量node？*nextdatanode，长度为m字节pmsizeof(node) /单位是字节p(node*)malloc(m)free(p) /只能借助node的指针删除！P-data=a; p- next=q19 对于指向结构类型的指针变量，可说明为：nodexnodex *p, *q; /或用 struct nodenode *p ,
7、*q; 类型定义和变量说明可以合写为： typedeftypedef structstruct node /node是自定义结构类型名称 char data; /定义数据域的变量名及其类型structstruct node *next; /定义指针域的变量名及其类型 nodex，*pointer; /nodex是node结构类型的类型替代, *pointer是指针型的node结构类型的替代，也是数据类型*/附2： 补充结构数据类型的C表示法20单链表的抽象数据类型描述如下（参见教材P28）：Typedef struct Lnode ElemType data; /数据域struct Lnode
8、 *next; /指针域 Lnode, *LinkList; / *LinkList为Lnode类型的指针如何具体编程来建立 和访问链表？ 链表的实现212.3.2 链表的实现（1） 单链表的建立和输出（2） 单链表的修改（3） 单链表的插入（4） 单链表的删除22（1） 单链表的建立和输出例：用单链表结构来存放26 个英文字母组成的线性表（a，b ，c，z）,请写出C语言程序。实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。先挖“坑”,后种“萝卜 ”！23#include #include typedef struct node char
9、 data; struct node *next; node; node *p,*q,*head; /一般需要3个指针变量 int n ; / 数据元素的个数 int m=sizeof(node); /*结构类型定义好之后，每个变量 的长度就固定了，m求一次即可*/将全局变量及函数提前说明：24 int i; head=(node*)malloc(m); /m=sizeof(node) 前面已求出 p=head; for( i=1; idata=i+a-1; / 第一个结点值为字符a p-next=(node*)malloc(m); /为后继结点“挖坑”！ p=p-next； /让指针变量P指向后一个结点 p-data=i+a-1; /最后一个元素要单独处理 p-next=NULL ; /单链表尾结点的指针域要置空！void build( ) /字母链表的生成。要一个个慢慢链入25p=head; while (p) /当指针不空时循环，仅限于无头结点的情况 printf(“%c“,p-data);p=p-next; /让指针不断“顺藤摸瓜” 讨论：要统计链表中数据元素的个数，该如何改写？ sum+;sum=0;void display() /*字母链表的输出*/26
