网站查询备案信息,专业的深圳网页设计公司,钥匙借用微信小程序免费制作平台,云和建设局网站目录
一、线性表例题#xff1a;
二、分配动态内存#xff1a; 1.动态创建一个空顺序表的算法#xff1a; 2.动态顺序表的插入算法#xff1a;
3.动态顺序表的删除 三、线性表的链式表示和实现 例题1#xff1a;创建链表并插入26个字母
例题2#xff1a;在链表中取…目录
一、线性表例题
二、分配动态内存 1.动态创建一个空顺序表的算法 2.动态顺序表的插入算法
3.动态顺序表的删除 三、线性表的链式表示和实现 例题1创建链表并插入26个字母
例题2在链表中取第i个数据元素
例题3在链表中删除一个结点
四、静态链表 一、线性表例题
例题1求两个线性表的“并”即LA U LB
算法思路
注意集合并的含义
LA和LB都是无序表则从LB种取元素逐一与LA中所有元素比较相同则不插入LA中 Void Union(List LA,List LB) {//将所有在线性表Lb中但不在La中的数据元素插入到La中 La_lenListlength(La); Lb_lenListlength(Lb); for(i1;iLe_len;i) { GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e、 if(!LocateElem(La,e,equal)) { ListInsert(La,La_len,e); } } } 算法复杂度分析LocateElemLa,e,equal) 需La_len次比较
则整个算法需OLa_len×Lb_len 例题2设正整数a的前驱为PRIOR(a)后继NEXT(a)用递归算法计算ab。 首先要对加法算法进行描述。不能用简单的加法语句因为没有加法要考虑如何用给出的两个特定函数来实现ab
思路: 考虑加法的定义若用数轴来描述ab当a不断往0移动b不断往相反方向移动的过程。当a移动到0时b指向的位置即为ab。 a可视为一减计数器前移过程中不断递减而b的后移则是不断加1的过程
平常我们可以用循环来实现但根据本题题意不能用循环而要用递归。
设计要点有二1.递归算法的形式化描述2.不能无限制递归一定要有终止条件。 结果 int add(int a,int b); if(a0) return(b); else return (add(prior(a),next(b))); 若a很大b很小怎么办
解决方法就从小的开始进行减计数。 二、分配动态内存
我的C语言专栏中介绍过基础这里跟数据结构一起编写一些
#define LIST_INIT_SIZE 100//存储空间的初始分配量
#define LISTINCREMENT 10//存储空间的分配增量
Typedef struct{
ElemType *elem; //表基址用指针*elem
int lenght; //表长度表中有多少个元素
int listsize; //当前分配的表尺寸字节单位
}SqList L; 1.动态创建一个空顺序表的算法 Status InitList_Sq(SqList L) { L.elem (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if(!L.elem) exit(OVERFLOW);//分配失败结束程序 L.length0; //暂无元素放入空表 L.listsize LIST_INIT_SIZE; //表尺寸初始分配量 Return OK; }//InitList_Sq 2.动态顺序表的插入算法 Status ListInsert_Sq(SqList L,int i,ElemType e) {//在顺序线性表中第i个位置之前插入新的元素e if(i1||iL.length1) return ERROR;//检验i值得合法性 if(L.lengthL.listsize)//若表长超过表尺寸则要增加尺寸 { newbase (ElemType*)realloc(L.elem,(L.listsizeLISTINCREMENT)*sizeof(ElemType));//realloc*pnewsize函数的意思是新开一片大小为newsize的连续空间并把以*p为首地址的原空间数据都拷贝进去。 if(newbase NULL) exit(OVERFLOW); //分配失败则退出报错 L.elem newbase; //重置新基址 L.listsize L.listsize LISTINCREMENT;}//增加表尺寸 qL.elem[i-1]; //q为插入位置。这里没有头结点的情况 for(pL.elem[L.length-1];pq;--p) *(p1)*p; //插入位置及之后的元素统统后移p为元素位置 *q e; //插入e L.length; //增加1个数据元素则表长1 return OK; }//ListInsert_Sq } 3.动态顺序表的删除
Status ListDelete_Sq(SqList L,int i,ElemType e)
{//在顺序表L中删除第i个元素用e返回其值 if(i1||L.length) return ERROR;//i值不合法返回 pL.elem[i-1]; //p是被删除元素的位置 e*p; //被删除元素的值赋给e qL.elemL.length-1; //q是表尾的位置 for(p;pq;p) *(p-1)*p; //待删除元素后面的统统前移--L.length; //表长-1 return ok;
}//ListDelete_Sq 三、线性表的链式表示和实现
1、链表的表示
1链式存储结构特点
其结点在存储器总的位置是随意的即逻辑上相邻的数据元素在物理上不一定相邻。
设计效率牺牲空间效率换取时间效率
头指针是指向链表中第一个结点或为头结点、或为首结点的指针
头结点是在链表的首元结点之前附设的一个结点数据域内只放空表标志和表长等信息它不计入表长度
首元结点是指链表中存储线性表第一个数据元素a1的结点。
Typedef struct Lnode{
ElemType data; //数据域
struct Lnode *next; //指针域
}Lnode,*LinkList; //*LinkList为Lnode类型的指针 例题1创建链表并插入26个字母
#include stdio.h
#include stdlib.h
typedef struct node{char data;struct node *next;
}node;node *p,*q,*head;
int n;
int msizeof(node);void build() //字母链表的生成。要一个个慢慢链入
{int i;head(node*)malloc(m);// phead;for(i1;i26;i)//因尾结点要特殊处理故i≠26 {p-dataia-1;//第一个结点值为字符a p-next(node*)malloc(m);//为后继结点“挖坑” pp-next; //让指针变量p指向后一个结点 }p-dataia-1;//最后一个元素要单独处理 p-nextNULL; //单链表尾结点的指针域要置空 } void display()//字母链表的输出
{phead;while(p)//当指针不空时循环仅限于无头结点的情况 {printf(%c,p-data);pp-next;}} int main(void){build();display();}
例题2在链表中取第i个数据元素 Status GetElem_L(Linklist L,int i,ElemType e)
{//L为带头结点的单链表的头指针//当第i个元素存在时其值赋给e并返回OK否则返回error pL-next;j1;
//初始化p指向第一个结点j为计数器 while(pji){
//顺指针向后查找直到p指向第i个元素或p为空 pp-next;j;}
//第i个元素不存在 if(!p||ji) return ERROR;ep-data;//取第i个元素 return ok;
}GetElem_L例题3在链表中删除一个结点
Status ListDelete_L(Linklist L,int i,ElemType e)
{//在带头结点的单链表L中删除第i个元素并由e返回其值 pL;j0;while(p-nextji-1){//寻找第i个结点并令p指向其前驱 pp-next;j;} if(!(p-next)p||ji-1) return ERROR;//删除不合理位置 qp-next;p-nextq-next;//删除并释放结点 eq-data;free(q);return ok;}
四、静态链表 定义一个结构型数组每个元素都含有数据域和指示域就可以完全描述链表指示域就相当于动态链表的指针称为游标。
静态链表的类型定义如下
#define MAXSIZE 1000 //预分配最大的元素个数连续空间
typedef struct { ElemType data; //数据域 int cur; //指示域
}component,SLinkList[MAXSIZE]; //这是一维结构型数组
例题4利用静态链表存储s(zhao,qian,sun,li,zhou,wu)。
其原理跟动态差不多写法类似知识不需要在使用指针。
