朔州如何做百度的网站,做一个公司网站多少钱,如何制作网站地图,新手学做网站推荐软件线性表这篇博客写的是线性表相关的内容#xff0c;包括如下部分#xff0c;先看下有木有期待啥是线性表线性表的顺序存储线性表的基本运算在顺序表上的实现线性表的链式存储线性表的基本运算在单链表上的实现循环链表与双向循环链表Over#xff0c;内容还蛮多的#xff01;…线性表这篇博客写的是线性表相关的内容包括如下部分先看下有木有期待啥是线性表线性表的顺序存储线性表的基本运算在顺序表上的实现线性表的链式存储线性表的基本运算在单链表上的实现循环链表与双向循环链表Over内容还蛮多的~ □头大了...首先明确一个非常重要的点线性表是一个线性结构注意上篇博客提过线性结构是数据的逻辑结构中的一种基本概念线性表是由n(n≥0)个数据元素组成的有穷序列大白话在内存上一个个排着找到一个剩下的挨着找就行数据元素又称作结点 吐槽人类在创造术语的路上就是这么带劲上节课刚说数据元素又称元素这又来一个结点得记住吧结点个数叫做表长那么我们用一张完整的图来说明一下 线性表的基本运算需要了解一下初始化 Initiate(L)求表长 Length(L)读表元素 Get(L,i)定位 Locate(L,i)插入Insert(L,x,i)删除Delete(L,i)线性表的顺序存储用顺序存储实现的线性表称为顺序表。一般使用数组来表示顺序表接下就是刺激的时刻了比较难的部分来了因为要用C来实现线性表的基本运算首先假定线性表的数据元素的类型为DataType 这个DataType 可以是自定义的也可以是默认的int,char等类型const int Maxsize 100 ; // 预先定义一个足够大的常数
typedef struct{DataType data[Maxsize]; // 存放数据的数组int length ; // 顺序表的实际长度
} SeqList; // 顺序表类型名为SeqList
SeqList L ; // 定义一个L为顺序表实现插入操作函数名字为InsertSeqList(SeqList L,DataType x,int i) 表示在顺序表第i1≤i≤n1个元素之前插入一个新元素。使得线性表长度加1。上面是逻辑上的C语言实现接下来咱们先引用一个图说明一下如何用C语言在内存上开辟一块空间并且向里面存数据#include stdio.h
#include stdlib.hconst int Maxsize 10;
typedef struct SeqList{int *data; //一个int指针后面用来初始化数组用int length;
} seq;// 顺序表的初始化函数
seq init(){seq s;s.data (int*)malloc(Maxsize*sizeof(int)); // 构造一个空的顺序表动态申请存储空间if(!s.data) // 如果申请失败退出程序{printf(初始化失败);exit(0);}s.length 0; // 空表的长度初始化为0return s;
}上述代码相当于在内存上做了图示的操作 开辟空间之后向每个小格子里面添加数字void display(seq s){for(int i0;is.length;i){printf(%d,s.data[i]);}printf(n);}int main()
{seq s init();//添加一个元素进入for(int i1;i5;i){s.data[i-1] i;s.length;}printf(初始化之后表的数据为:n);display(s);return 0;
}可以看动画理解 添加元素完成之后就是删除元素了删除的基本步骤 1. 结点a~i1~,....a~n~依次向左移动一个元素位置 2. 表长度减1看一下代码吧seq delete_seq(seq s,int i){if(i1||is.length){printf(位置错误);exit(0);}// 第i个元素下标修改为i-1for(int ji;js.length;j){s.data[j-1] s.data[j];}s.length--;return s;
}接下来实现定位的算法说白了就是判断一个值x的位置iC语言的代码如下// 注意这个地方需要返回的为int了也就是位置
int locate(seq s,int x){int i 0;while((is.length)(s.data[i]!x)){i;}if(is.length) return i1;else return -1;
}线性表的顺序存储的时间复杂度|运算| 插入|删除|定位|求表长|读取元素| |--|--|--|--|--|--| | 时间复杂度|O(n) |O(n)|O(n)|O(1)|O(1)| 具体是怎么来的需要你自己看看算法的实现喽通过上述表格知道 顺序表的插入、删除算法在时间性能方面不是很理想接下来我们就采用线性表的链接存储来看一下是否存在优化。线性表的链接存储链式存储结构上来需要记住有三种常见的 单链表、循环链表、双向循环链表首先明确单链表中每个结点由两部分组成 - data表示数据域 - next表示指针域或链域一些简单的结点概念 线性表在单链表上实现基本运算接下来重头戏来了我们要用代码实现一个简单的单链表空的单链表由一个头指针和一个头结点组成初始化初始化之前我们需要先用C语言定义一个新的结构体//链表中的每个结点的实现
//包含数据域与指针域
typedef struct node{int data;// 数据域为了计算方便类型设置为数字struct node *next; // 指针域指向后继元素
} Node,*LinkList;结构体定义好了之后就可以开始初始化操作了 头结点初始化其实就是在内存上开辟一块空间然后将指针域指向NULL 请看代码注意返回的是一个指针类型说白了就是头结点的地址// 初始化
LinkList init(){Node *L; // 定义一个头结点L (LinkList)malloc(sizeof(Node)); //头结点申请地址if(L NULL){printf(初始化失败!n);exit(0);}L-next NULL;return L;
}初始化成功开始插入元素插入元素有头插入、尾插、任意插先说一下头插当头结点初始化完毕之后第一个元素插入进来就比较简单了看动图  这是插入一个元素在用头插法插入第二个元素呢  新生成的pnew2首先将自己的指针域指向头结点的指针域pnew2-next L.next然后L.next pnew2 即可上述的逻辑写成代码如下// 头插入法
void insert_head(Node *L){int i,n,num; // n表示元素的个数 Node *pnew;printf(请输入要插入的元素个数n );scanf(%d,n);for(i0;in;i){printf(请输入第%d个元素 ,i1);scanf(%d,num);pnew (LinkList)malloc(sizeof(Node));pnew-data num; // 将数字存储到数据域pnew-next L-next; // 指针域指向L头结点的指针域L-next pnew; // 头结点指针域指向新结点地址}
}接下来看一下尾插法其实理解起来也不难说白了就是在链表后面追加元素即可  代码如下这个地方看一下里面有一个pL请问直接使用L可以吗为什么不直接用搞清楚了你也就明白了// 尾插法
void insert_tail(Node *L){int i,n,num;Node *p,*pnew;p L;printf(要输入元素的个数n );scanf(%d,n);for(i0;in;i){printf(请输入第%d个元素,i1);scanf(%d,num);pnew (LinkList)malloc(sizeof(Node));if(pnew NULL){printf(初始化失败);exit(0);}pnew-data num;p-next pnew;p pnew;}p-next NULL;}剩下的算法实现就比较简单了例如求表长通过循环的方式计算一下即可//求表长
int get_length(LinkList L){LinkList p;int length 0;p L-next; // p 指向第一个结点while(p){printf(单链表的数据为%dn,p-data);length;p p-next;}return length;
}读表中的元素// 读表中的元素
LinkList get_element(LinkList L,int i){// 在单链表L中查找第i个结点若找到则返回指向该结点的指针否则返回NULLNode *p;p L-next;int position 1;while((positioni)(p!NULL)){ // 当未到第i结点且未到尾结点时继续后移p p-next;position;}if(iposition) return p; //找到第i个结点else return NULL; // 查找失败
}读取表的元素还可以按照值去找返回位置尝试一下吧写起来都是比较容易的int get_element_by_data(LinkList L,int x){Node *p;p L-next;int i 0;while(p!NULL p-data x){p p-next;i;}if (p!NULL) return i1;else return 0;
}写个复杂点的在任意位置插入一个元素这个还是好玩一些的/在任意位置插入元素x为要插入的内容i为插入的位置
void insert(LinkList L,int x,int i){Node *p,*q; //p表示要插入的元素q表示要被插入的元素if(i1) q L; //如果i1,那么pL进行初始化操作else q get_element(L,i-1); // 找到第i-1个元素if(qNULL){printf(找不到位置);exit(0);}else{p (LinkList)malloc(sizeof(Node));p-data x;p-next q-next; // 新生成的p指向q的下一个结点q-next p;//q的指针域指向新生成的p}
}简单说明一下吧 大白话为 要在第i个位置插入一个元素x,那么需要找到i-1位置的元素这个元素叫做 q让新元素p数据域为x指针域为空的指针域指向第i 元素也就是q原先的指针域防止丢失掉然后在叫q的指针域指向p的地址即可如果还不明白看图 对于删除任意位置的节点这个就要留给你自己了如果将a~i~移除链表需要找到直接前驱让直接前驱的指针域指向a~i1~的地址就可以了记得通过free(p)释放结点删除全部结点也需要自己完成一下尽量把代码写完哦~~~单链表的时间复杂度insert(LinkList L,int x,int i) 时间复杂度为O(n^2^)头插法和尾插法时间复杂度为O(n)循环链表环状链表只需要将表中最后一个结点的指针指向头结点链表就形成了一个环 如图 循环链表如何想研究一下可以去实现约瑟夫环由于本教材中不是重点所以选修即可双向循环链表双向循环链表就是在单链表中的每个结点在增加一个指向直接前驱的指针域prior 这样每个结点就有两个指针了 注意点 1. 双向循环链表是一种对称结构即可以直接访问前驱结点又可以直接访问后继结点所以找前驱和后继结点的时间复杂度都是O(1)也可以得到结论双向循环链表适合应用在需要经常查找结点的前驱和后继场合 2. p p-prior-next p-next-prior教材中重点给出了删除和插入的两个逻辑我们看一下// p表示的是待删除的结点
p-prior-next p-next;
p-next-prior p-prior;
free(p)图示如下 大白话 先让p等于要删除的结点然后把p删除前需要将p的前驱和后继结点连接起来刚才的代码干的就是这个事情插入逻辑在p所指的结点后面插入一个新结点*t需要修改四个指针t-prior p;
p-next t; // 这两个步骤将t和p连接起来了t-next p-next;
p-next-prior t; //这两个步骤将t和p后继结点连接起来了期末考试这章是期末考试或者自考的一个比较重要的考试章节一般会出现算法设计题难度系数挺高的建议在能力范围内用C语言实现顺序表的基本运算实现单链表的基本运算懵了吧嘿嘿~多看几遍多看几遍看图看图写代码运行运行欢迎关注梦想橡皮擦公众号哦~
